В.А. Фисун - Параллельная обработка данных (2005) (1127758), страница 8
Текст из файла (страница 8)
Синхронный и асинхронный способы передачисообщенийВ MPI имеется три режима коммуникаций - стандартный, режим готовности исинхронный.29В стандартном режиме последовательность выдачи операций send и receiveпроизвольна, операция send завершается тогда, когда сообщение изъято избуфера и он уже может использоваться процессом.В режиме готовности операция send может быть выдана только послевыдачи соответствующей операции receive, иначе программа считаетсяошибочной и результат ее работы неопределен. В синхронном режимепоследовательностьвыдачи операций произвольна, но операция sendзавершается только после выдачи и начала выполнения операции receive. Вовсех трех режимах операция receive завершается после получения сообщения взаданный пользователем буфер приема.Неблокирующие операции не приостанавливают процесс до своегозавершения , а возвращают ссылку на коммуникационный объект, позволяющийопрашивать состояние операции или дожидаться ее окончания.
Имеютсяоперации проверки поступающих процессу сообщений, без чтения их в буфер(например, для определения длины сообщения и запроса затем памяти под него).31. Параллельное выполнение цикла видаDO i=2,N A(I) =(B(i)+C(i))/A(i+const) ENDDO.Если const = 0, то все итерации цикла независимы и токой цикл может быть выполненна любой многопроцессорной ЭВМ, влючая Иллиак-4. (каждый виток циклавыполняется на отдельном процессоре)Если const > 0 (пусть =1) то при параллельное выполнение цикла на ЭВМ классаМКМД без дополнительных мер по синхронизации работы процессоров невозможно.Например, пусть N=3 и два процессора вычисляют параллельно эти итерации, тогда,первый процессор вычисляет А2 по В2, С2, А3, а второй, А3 по В2, С2, А4 .
Приотсутствии синхронизации может случиться ситуация, при которой второй процессорзавершит свою работу до начала работы первого. Тогда первый процессор длявычислений будет использовать А3, которое обновил второй процессор, что неверно,ибо здесь нужно “старое” значение А3. Однако, этот цикл выполняется параллельнона ЭВМ ОКМД (SIMD) так как там этот цикл может быть выполнен такимикомандами:1.
Считать Вi в сумматоры каждого из n АЛУ.2. Сложить Сi со своим содержимом сумматора.3. Разделить содержимое каждого i-сумматора на Аi+1.4. Записать содержимое i- сумматоров в Аi.Из за того, что выборка из памяти и запись в память производится синхронно(одновременно), то работа цикла – корректна.Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполненияочередной итерации цикла необходимы результаты работы предыдущей (рекурсия).Однако известны приемы преобразования такого рода циклов к виду, допускающиепараллельное выполнение.3024. Статический и динамический способы образования параллельных процессов."Процесс - группа ячеек памяти, содержимое которых меняется по определеннымправилам.
Эти правила описываются программой, которую интерпретируетпроцессор” /Цикритзис Д./.32. Распараллеливание алгоритмов сложения методом редукции.Рекурсия - последовательность вычислений, при котором, значение самогопоследнего терма в последовательности зависит от одного или несколько ранеевычисленных термов. Пусть группа вычислений может производитьсяпараллельно, использую результаты вычислений, выполненных на предыдущихэтапах (полученных в виде начальных данных).
Тогда, каждая группа вычисленийназывается "ярусом" параллельной формы, число групп - "высотой", максимальноечисло операций в группе "шириной" параллельной формы. Один и тот жеалгоритм может иметь несколько представлений в виде параллельных форм,различающиеся как шириной, так и высотой. Редукционный алгоритм сдваиваниядля суммирования чисел с получением частных сумм может иметь вид:Данные А1 А2 А3 А4 А5 А6 А7 А8Ярус 1 А1+А2А3+А4А5+А6А7+А8Ярус 2 А12+А3 А12+А34 А56+А7А56+А78Ярус 3 А1234+А5 А1234+А56 А1234+А567 А1234+А5678Высота параллельной формы равна трем, ширина - четырем, причем загрузкавычислителей (четырех) полная.
В данном алгоритме производится вычисленияпяти "лишних" чисел по сравнению с последовательным алгоритмом сложениявосьми чисел.33. Метод распараллеливания алгоритма общей рекурсии 1-го порядка.Редукция - упрощение, в биологии уменьшение размера органа вплоть до егополного исчезновения. Циклическая редукция - алгоритмы численного анализа дляраспараллеливанияпоследовательныхалгоритмов,основанныйнапоследовательном, циклическом применении параллельных вычислений, числокоторых на каждом этапе уменьшается (делится пополам).Общей линейной рекурсией первого порядка называется система уравненийвида:X1 = D1X2 = X1 * A2 + D2Xi = Xi-1 * Ai + DiXn = Xn-1 * An + Dnв общем виде: Xi = Xi-1 * Ai + Di, i = 2,3,...n, X1 = D1Последовательный алгоритм вычислений может быть записан так:X(1) = A(1) + D(1)DO i = 2,nX(i) = X(i-1) * A(i) + D(i)31ENDDOРекурсивная зависимость итераций цикла не позволяет ускорить вычисления засчет параллельной работы оборудования.
Преобразуем данный алгоритм впараллельный методом циклической редукции. Рассмотрим два соседнихуравнения:Xi-1 = Xi-2 * Ai-1 + Di-1Xi = Xi-1 * Ai + Diи подставив первое во второе, получаем:Xi = (Xi-2 * Ai-1 + Di-1) * Ai + Di = Xi-2 * A1i + D1i , гдеA1i = Ai * Ai-1 ,D1i = Ai * Di-1 + DiТогда, проведя эту операцию для всей системы уравнений, получим системууравнений порядка n/2. Если повторить процедуру l раз (если n = 2**l), то врезультате получается значение: Xn = Dnl. Для получения полного вектора Xнеобходимо модифицировать алгоритм, например, по аналогии с алгоритмамисуммирования.Очевидно, что вычисления Aji и Dji можно проводить параллельно методомкаскадных сумм с сохранением частных сумм.
Приведенные уравнения для уровняi имеют вид:Xi = Ali * Xi-2**l + Dli , где l = 0,1,..,log2n , i = 1,2,..,nAli = Al-1i * Al-1(i-2**l-1)Dli = Al-1i * Dl-1(i-2**l-1) + Dl-1iНачальные данные: A0i = Ai, D0i = DiЕсли индекс i у любого Ali, Dli и Xi попадает вне диапазона 1 <= i <= n , то ондолжен быть приравнен к нулю. Тогда , при l = log2n в уравнениях: Xi = Ali * Xi2**l + Dli индекс Xi-2**l = Xi-n находится вне диапазона, и, следовательно,решением системы уравнений будет:вектор: Xi = Dli, Векторная нотация Хокни для данного алгоритма: X = DDO L = 1,LOG2(N)X = A * SHIFTR(X,2**(L-1)) + XA = A * SHIFTR(A,2**(L-1))ENDDO24.
Системы счисления.Подмножество вещественных чисел, которое может быть представлено вЭВМ в форме чисел с плавающей запятой, принято обозначать буквой F иопределять его элементы для конкретной архитектуры - "машинные числа", (поФорсайту и др.) четырмя целочисленными параметрами: базой b, точностью t иинтервалом значений показателя [L,U]. Множество F содержит число нуль и все fчисла вида: f = (+/-).d1d2...dt * b**e, где е называется показателем, число .d1d2...dt= (d1/b+ ....+dt/(b**t)) - дробной частью - мантиссой, причем: 0<=di<b, L<=e<=U.32Каноническая или нормализованная форма F определяется дополнительнымсоотношением d1 =/= 0 ; это условие позволяет устранить неоднозначностьпредставления одинаковых чисел, дает наивысшую возможную точностьпредставления чисел.
Особенности F:- для каждого ненулевого f верно: m<=|f|<=M, где m = b**(L-1),M = (b**U) * (1-b**(-t));- множество F конечно и содержит 2*(b-1)*(b**(t-1))*(U-L+1)+1 чисел, которыеотстоят друг от друга на числовой оси на неравные промежутки.35. Определить минимальное значение числа с плавающей запятой- для каждого ненулевого f верно: m<=|f|<=M, где m = b**(L-1),M = (b**U) * (1-b**(-t));36. Определить количество элементов чисел с плавающей запятой.- множество F конечно и содержит 2*(b-1)*(b**(t-1))*(U-L+1)+1 чисел, которыеотстоят друг от друга на числовой оси на неравные промежутки.37. Машинный эпсилон, определение разрядной сетки ЭВМ.Точность плавающей арифметики можно характеризовать посредствоммашинного эпсилона.
Максимальное число Е такое, что 1.+ Е = 1. является меройточности представления чисел на данной ЭВМ (машинное эпсилон). Грубая схемавычисления эпсилона:EPS = 1.01 EPS = 0.5 * EPSEPS1 = EPS + 1.0IF (EPS1 .GT. 1.0) GO TO 1 >Задача. Написать программу, определяющую количество разрядов, используемыхдля представления мантиссы чисел с плавающей запятой. (Пусть наиспытываемой ЭВМ мантисса числа хранится в нормализованном виде 1A2A3...An).38. Источники погрешности при вычислениях на параллельных системах.В общем случае, арифметические операции над элементами дискретногоподмножества вещественных чисел F не корректны.Результат арифметических операций чисел с плавающей запятой может:- иметь абсолютное значение, больше M (максимального числа) - машинноепереполнение;- иметь ненулевое значение, меньшее m (минимального числа) по абсолютнойвеличине - машинный нуль;- иметь значение в диапазоне [m:M] и тем не не менее не принадлежатьмножеству F (произведение двух чисел из F, как правило, записываетсяпосредством 2t либо 2t-1 значащих цифр);33Поэтому, на множестве чисел с плавающей запятой определяются и"плавающие" арифметические операции, за результаты которых, если они невыходит за границы множества F, принимается ближайшие по значениюэлементы F.
Примеры из четырехразрядной десятичной арифметики по Н. Вирту.А) Пусть x=9.900 y=1.000 z=-0.999 и тогда:1 (x+y)+z = 9.9102 x+(y+z) = 9.901В) Пусть x=1100. y=-5.000 z=5.001 и тогда:1 (x*y)+(x*z) = 1.0002 x*(y+z)= 1.100Здесь операции + и * - плавающие машинные операции. Такие 'чиcленные'процессы называют иногда 'неточными', здесь нарушаются ассоциативный идистрибутивный законы арифметики..39.
Оценить полную ошибку для суммирования положительных чисел.Пример расчета полной ошибки для суммирования положительных чиселФормула полной ошибки для суммирования положительных чиселAi(i=1,..,n) имеет вид: Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n1)*(A1+..+An) + dn , гдеdai - относительные ошибки представления чисел в ЭВМ, а di - относительныеошибки округления чисел при каждой следующей операции сложения. Пусть: всеdai = da и di = d , a Ks = A1+A2+..+An, тогда: Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2+...+ 2*A(n-1) + An]Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, суммируемые вначале. Следовательно, если суммируемые положительные числаупорядочить по возрастанию, максимально возможная ошибка суммы будетминимальной.
Изменяя порядок суммирования чисел можно получать различныерезультаты. Но если даже слагаемые отличаются друг от друга незначительно, наточность результата может оказать влияние способ суммирования. Пустьсуммируются 15 положительных чисел, тогда ошибка результата: Ds = da*Ks +d*(14*A1+14*A2+13*A3+....+2*A14+A15).Слагаемое da*Ks не зависит от способа суммирования, и далее не учитывается. Пустьслагаемые имеют вид: Ai = А0+ei, где i=1,...,15, тогда: Dss = 199*(A0+em)*d, где em =max(ei), d - ошибка округления при выполнении арифметической операции сложения.Если провести суммирование этих чисел по группам (три группы по четыречисла и одна группа из трех чисел), то ошибки частных сумм имеют вид:Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em)Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em)Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em)Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em)а полная оценка ошибок округления будет Ds <= 32*d*(A0+em), что меньшеDss.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
