СКИПОД ответы на билеты (1127807), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Ярус 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

Высота параллельной формы равна трем, ширина - четырем, причем загрузка вычислителей (четырех) полная. В данном алгоритме производится вычисления пяти "лишних" чисел по сравнению с последовательным алгоритмом сложения восьми чисел.

[править] Распараллеливание алгоритмов рекурсии первого порядка.

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

Остановимся на простейшем примере линейной рекурсии первого порядка для вычисления суммы всех элементов вектора для нахождения этой суммы можно воспользоваться рекурсивным соотношением

Информационный граф на Рис.1а иллюстрирует рекурсивный способ вычисления суммы, и поскольку каждый из операндов используется однократно, такой граф представляет собой бинарное дерево. Если выполнение каждой примитивной операции занимает интервал t, то суммарные затраты времени (и длина графа q) при реализации этого ИГ составят T = (L − 1) * t;q = (L − 1).

При наличии нескольких вычислителей очевидно, что такой алгоритм будет неэффективным, и задача состоит в том, чтобы минимизировать высоту дерева. Преобразование выполняется в соответствии с законами коммутативности, ассоциативности и дистрибутивности, в результате чего может быть получен трансформированный ИГ, показанный на Рис.1б.

Высота такого дерева q' = log₂L, а длительность реализации составит T' = t * log₂L в предположении, что операции реализуются за то же время t и что затраты времени на обмен между отдельными вычислителями эквивалентны затратам времени на обмен между ячейкой памяти и вычислителем в последовательной структуре. Такой метод нахождения суммы элементов вектора получил название метода сдваивания или метода нахождения параллельных каскадных сумм.

Максимальное ускорение T / T' можно оценить как O(L / log₂L), оно достигается при числе вычислителей не менее N = L / 2, причем полностью все L / 2 вычислители загружены только на первом шаге вычислений, на последнем шаге используется лишь один вычислитель.

Не используемые на каждом шаге вычислители можно отразить на ИГ в виде "пустых" операторов, которые показаны на Рис.1б в виде заштрихованных кружочков. Эти пустые операторы не имеют входных и выходных дуг. Теперь можно оценить эффективность полученного алгоритма как отношение числа действительных к общему действительных и пустых операторов. Очевидно, что понятие эффективности сродни понятию коэффициента полезного действия.

Для рассматриваемого алгоритма эффективность составляет 1/2 и не зависит от L.

[править] Векторизация последовательных программ.

Под векторизацией понимается распараллеливание. Наибольшим внутренним параллелизмом, который можно использовать для векторизации программ, являются циклические участки, так как на них приходится основное время вычислений, и в случае распараллеливания вычисления в каждой ветви производится по одному и тому же алгоритму. В методах распараллеливания циклов используется довольно сложный математический аппарат. Наиболее распространенными методами распараллеливания являются: метод параллелепипедов, метод координат, метод гиперплоскостей. Объектами векторизации в этих методах являются циклы типа DО в Фортране.

[править] Метод координат

Обеспечивает векторизацию циклов для синхронных ЭВМ (ОКМД - SIMD архитектуры). Семантика синхронных циклов следующая:

• для каждой итерации цикла назначается процессор;

• вычисления должны производиться всеми процессорами (процессорными элементами) параллельно и синхронно.

Операторы тела цикла выполняются по очереди, но каждый оператор выполняется всеми процессорами одновременно. При выполнении оператора присваивания сначала вычисляется правая часть, затем одновременно выполняется операция присваивания для всех элементов массива левой части.

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

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

• позволяет определить возможность выполнения цикла в синхронном режиме;

• содержит алгоритмы преобразования тела цикла к синхронному виду.

Например, по Лэмпорту, цикл: {{{

DO 24 I=2,M

DO 24 J=2,N

21 A(I,J) = B(I,J)+C(I)

22 C(I) = B(I-1,J)

23 B(I,J) = A(I+1,J) ** 2

24 CONTINUE

}}} преобразуется в цикл: {{{

DO 24 J=2,N

DO 24 SIM FOR ALL I {i:2<=i<=M}

/* SIM - SIMulteneusly (одновременно)*/

TEMP(I) = A(I+1,J)

21 A(I,J) = B(I,J)+C(I)

23 B(I,J) = TEMP(I) ** 2

22 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) D(I) = A(I)

C(I) = A(I) + A(I+1) A(I) = B(I)

C(I) = A(I) + D(I+1)

A(I) = B(I) + B(I+1) D(I) = B(I)

B(I) = A(I+1) B(I) = A(I+1)

A(I) = D(I) + B(I+1)

A(I) = B(I) + B(I-1) Векторизация невозможна

B(I) = A(I)

[править] Метод гиперплоскостей

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

DO 5 I = 2,N

DO 5 J = 2,M

5 A(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.

В общем случае для n-мерного тесногнездового цикла ищется семейство параллельных гиперплоскостей в n-мерном пространстве итераций, таких что во всех точках каждой из этих гиперплоскостей возможно параллельное выполнение тела цикла.

Для приведенного примера множество точек, в которых возможно параллельное выполнение, является однопараметрическим (прямая) и определяется из решения уравнения 1I+J=K 0. Цикл (5) может быть преобразован к виду:

DO 5 K = 4,M+N

Tн = MMAX(2,K-N)

Tк = MMIN(M,K-2)

DO 5 T = Tн,Tк 1: PAR

I = T

J = K - T

5 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 меняются при переходе с одной прямой (гиперплоскости) на другую, поэтому их необходимо перевычислять во внешнем цикле. Число итераций внутреннего цикла, то есть потенциальная длина векторной операции, меняется с изменением K . Для приведенного примера диапазон изменения T сначала возрастает, а потом убывает, причем для начального и конечного значения K он равен единице. В некоторых случаях для отдельных значений K накладные расходы на организацию векторного вычисления могут превысить эффект ускорения от векторного выполнения.

[править] Метод параллелепипедов

Идея метода заключается в выявлении зависимых итераций цикла и объединении их в последовательности - ветви, которые могут быть выполнены независимо друг от друга. При этом в пространстве итераций определяются области (параллелепипеды), все точки которых принадлежат разным ветвям. Задача максимального распараллеливания заключается в поиске параллелепипеда наибольшего объема; тогда исходный цикл выполняется наибольшим числом параллельных ветвей, каждая из которых представляет собой исходный цикл, но с другим шагом изменения индекса. Для исходного цикла:

DO 7 I = 1,7

DO 7 J = 1,3

7 X(I,J) = X(I-2,J-1)

параллельное представление в виде:

DO 7 (K,L) = (1,1) (P1,P2) 1: PAR

DO 7 I = K,7,P1

DO 7 J = L,3,P2

7 X(I,J) = X(I-2,J-1)

допускается для различных разбиений пространства итераций: пара (P1,P2) может иметь, например, значения (2,1), (2,3) или (7,1). Таким образом, исходный цикл (7) преобразуется в последовательность параллельных ветвей, имеющих циклический вид.

В общем виде задача, рассматриваемая методом параллелепипедов, для одномерных циклов состоит в определении возможности представления цикла:

DO L I = 1,r

L T(I)

(где T(i) - тело цикла) в виде следующей языковой конструкции:

DO L K = 1,p 1: PAR

DO L I = K,r,p

L T(I)

[править] Оценка возможности векторизации

Оценить возможность параллельного выполнения цикла:

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) так как там этот цикл может быть выполнен такими командами:

• Считать Вi в сумматоры каждого из n АЛУ.

• Сложить Сi со своим содержимом сумматора.

• Разделить содержимое каждого i-сумматора на Аi+1.

• Записать содержимое i- сумматоров в Аi.

Из за того, что выборка из памяти и запись в память производится синхронно (одновременно), то работа цикла – корректна. Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполнения очередной итерации цикла необходимы результаты работы предыдущей (рекурсия). Однако известны приемы преобразования такого рода циклов к виду, допускающие параллельное выполнение.

Характеристики

Список файлов ответов (шпаргалок)