Краткий_Курс (Краткий курс ПОД), страница 7

В синхронном режимепоследовательностьвыдачи операций произвольна, но операция sendзавершается только после выдачи и начала выполнения операции receive. Вовсех трех режимах операция receive завершается после получения сообщения взаданный пользователем буфер приема.Неблокирующие операции не приостанавливают процесс до своегозавершения , а возвращают ссылку на коммуникационный объект, позволяющийопрашивать состояние операции или дожидаться ее окончания.

Имеютсяоперации проверки поступающих процессу сообщений, без чтения их в буфер(например, для определения длины сообщения и запроса затем памяти под него).27. Распараллеливание последовательных программ. ( Метод гиперплоскостей)Метод гиперплоскостей применим только к многомерным циклам. Впространстве итераций ищется прямая (плоскость), на которой возможнопараллельное асинхронное выполнение тела цикла, причем в отличие от метода27координат, эта прямая (плоскость) может иметь наклон по отношению к осямкоординат.

Цикл вида:DO I = 2,NDO J = 2,MA(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5методом координат не векторизуется. Действительно, при фиксированномзначении переменной I(I = i) значение, вычисленное в точке (i,j)пространства итераций, зависит от результата вычислений в предыдущейточке (i,j-1), так что параллельное выполнение тела цикла по переменной Jневозможно. Аналогично нельзя проводить параллельные вычисления попеременной I.Однако можно заметить, что результат будет также правильным, есливычисления проводить в следующем порядке:на 1-м шаге - в точке (2,2),на 2-м шаге - в точках (3,2) и (2,3),на 3-м шаге - в точках (4,2), (3,3) и (2,4),на 4-м шаге - в точках (5,2), (4,3), (3,4) и (2,5) и т.д.Вычисления в указанных точках для каждого шага, начиная со второго, можнопроводить параллельно и асинхронно.

Перечисленные кортежи точек лежат напараллельных прямых вида I+J=K, а именно: на первом шаге - на прямой I+J=4, навтором - I+J=5, на третьем шаге - I+J=6 и т.д., на последнем ((N-2)+(M-2)+1) - омшаге - на прямой I+J=M+N.Для приведенного примера множество точек, в которых возможно параллельноевыполнение, является однопараметрическим (прямая) и определяется из решенияуравнения I+J=K. Цикл (5) может быть преобразован к виду: DO 5 K = 4,M+NTн = MMAX(2,K-N)Tк = MMIN(M,K-2)DO 5 T = Tн,Tк : PARI=TJ=K-T5 A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5Функция MMAX(X,Y) выбирает ближайшее целое, большее или равное максимуму изчисел X и Y, а функция MMIN(X,Y) - ближайшее целое, меньшее или равное минимумуиз X и Y.Внутренний цикл по переменной T может выполняться параллельно для всехзначений T.

Границы изменения переменной цикла T меняются при переходе с однойпрямой (гиперплоскости) на другую, поэтому их необходимо перевычислять вовнешнем цикле. Число итераций внутреннего цикла, то есть потенциальная длинавекторной операции, меняется с изменением28. Ограничения на распараллеливание циклов.28Распараллеливание циклов возможно, если все итерации цикла независимы.

Телоцикла не должны содержать:- операторов перехода- операторов ввода-выводаИндексные выражения не должны иметь индекс в индексе А(В(С))29. Алгоритмы преобразования программ методом координатМетод координат:- позволяет определить возможность выполнения цикла в синхронномрежиме(для архитектуры SIMD);- содержит алгоритмы преобразования тела цикла к синхронному виду.Например, по Лэмпорту, цикл:DO 24 I=2,MDO 24 J=2,N21 A(I,J) = B(I,J)+C(I)22 C(I) = B(I-1,J)23 B(I,J) = A(I+1,J) ** 224 CONTINUEпреобразуется в цикл:DO 24 J=2,NDO 24 SIM FOR ALL I i:2<=i<=M C SIM - SI Multeneusly(одновременно)TEMP(I) = A(I+1,J)21 A(I,J) = B(I,J)+C(I)23 B(I,J) = TEMP(I) ** 222 C(I) = B(I-1,J)24 CONTINUEПримеры векторизацииИсходные тела циклов Преобразованные тела цикловA(I) = B(I)C(I) = A(I+1)C(I) = A(I+1)A(I) = B(I)A(I) = B(I)C(I) = A(I) + A(I+1)D(I) = A(I)A(I) = B(I)C(I) = A(I) + D(I+1)30.

Синхронный и асинхронный способы передачисообщенийВ 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 можно проводить параллельно методомкаскадных сумм с сохранением частных сумм.