ПОД конспект (1184369), страница 19
Текст из файла (страница 19)
Для многомерных циклов для всех пар (f,q) определяютсянаправляющие вектора, элементы которых состоят из символов (=, >, <) в позиции соответствующегоиндекса, которая определяется порядком индексов в гнезде цикла. В примере Лемпорта (исходном) для Авектор имеет вид: (<,=).Для тела цикла, состоящего из одного оператора, отношения, и соответственно, семантика выполнения,могут быть: < > = и их сочетание. Например, тело цикла: A(I) = (А(I)+A(I+1))/2 допускает векторноевыполнение; оно невозможно при наличии в операторе хотя бы одного соотношения: f>q. Для тела цикла:A(I) = A(I+C))/2 при С>0 возможно синхронное выполнение, при С=0 кроме синхронного, возможнопараллельное асинхронное; а при С<0 параллельное выполнение невозможно.Для многомерных (тесногнездовых) циклов такое исследование может проводиться для каждогопараметра, а для распараллеливания выбираться наиболее оптимальный вариант.
Для самого внутреннегоцикла определение следования можно проводить, считая его одномерным. Для любого другого цикла,исследование можно проводить по такой же схеме, если семантика цикла допускает перестановку его напозицию самого внутреннего. Перестановка допустима, если для всех новых направляющих векторовкрайне левый, отличный от = , элемент сохранил направление. Например, для двумерного цикла, наличиевектора (<,>) делает перестановку некорректной.
Так для цикла:DO 99 J=2,M45DO 99 K=2,M99 U(J,K) = (U(J+1,K)+U(J,K+1)+U(J-1,K)+U(J,K-1)) .25направляющие вектора:1 <U(J,K),U(J+1,K)> = (<,=)2 <U(J,K),U(J,K+1)> = (=,<)3 <U(J,K),U(J-1,K)> = (>,=)2 <U(J,K),U(J,K-1)> = (=,>)Отсюда:- операторы циклов по I и J можно менять местами,- часть оператора, включающая вхождения из векторов 1 и 2, можно вынести в отдельный оператор,который векторизуется как по I так и по J.Для двухоператоровтела цикла отношения следования переменных с индексами можносистематизировать и кодировать так (qi в общем случае, список - информационные поля q и f) : А независимые отношения В - (qi>qj) , C - (qi<qj) , K - (qi=qj) G - B+K,B+C,B+K+C , Н - неоднозначныеотношения.
Тогда по координатам приводимой ниже таблице можно определить типы связей и методвыполнения цикла для этих операторов. Если объединить информационные поля двух операторов , тотаблицу можно использовать для анализа третьего оператора и т.д.*Таблица решений для метода координат* Оператор 1O1 = I1Oi,Ii - список переменных с индексами* Оператор 2O2 = I2-> - порядок анализа отношений*--------------------------------------------------------------------*.O2 -> I1.*.A.B.K.C.G.H .*. HEЗАВ. . O > I . O = I . O < I . O <=>I*.* I2 -> O1.......*---------------------------------------------------------------------*.......*A HEЗАВ.
.P.R.S.M. R(K,C).T.*______________________________________________________________________*.......*B I > O .R.R. M(B). M(B). R(K,C).T.*______________________________________________________________________*.......*K I = O .S.T.S.M.T.T.*______________________________________________________________________*.......*C I < O .M.T.M.M.T.T.*______________________________________________________________________*.......*G I <=> O.
M(B).T. M(B). M(B).T.T.*______________________________________________________________________*.......*H*.T.T.T.T.T.T.*______________________________________________________________________*Кодировка отношений следования*А - независимые отношения*В - (qi>qj) , C - (qi<qj) , K - (qi=qj)*G - B+K,B+C,B+K+C*Н - неоднозначные отношения* TИПЫ CBЯЗEЙ*P - независимые операторы*M - SIMD , M(EA) - SIMD с защитой EA*R - SIMD с реверсом, R(EA) - и с защитой EA*S - PAR (асинхронная параллельность)*T - запрет векторизации* Защита ЕА - копирование массивов ЕА передВ общем случае, алгоритм векторизации методом координат с использования данной таблицыследующий.Обработка тела цикла начинается с анализа на возможность векторного выполнения каждого операторатела в отдельности.
Затем к первому оператору добавляется второй и проводится анализ на возможную ихвекторизацию. Пара получает тип, определяющий возможность векторизации ее компонент,информационные поля операторов сливаются,и наследующем шаге применения процедурывекторизации пара рассматривается как единый супероператор. Таким образом из всех операторов телацикла образуется один супероператор и, если его тип есть Т, то векторизация тела цикла невозможна. Длявсех других типов производится обратный анализ полученного графа (супероператора). Если при этомсвязки имели тип R или R(EA),M(EA), то хотя они и допускают асинхронное параллельное выполнение, нонеобходимы преобразование тела цикла.
Связки типа Т дают операторы, векторизация которыхневозможна. Интерпретация остальных типов связок очевидна. В процессе формирования супероператоров46к связкам типа Т могут применяться процедуры поиска минимальных границ области типа Т и чисткиобласти Т.Примеры векторизацииИсходные тела цикловПреобразованные тела циклов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)A(I) = B(I) + B(I+1)B(I) = A(I+1)D(I) = B(I)B(I) = A(I+1)A(I) = D(I) + B(I+1)A(I) = B(I) + B(I-)B(I) = A(I)Векторизация невозможна65. Схема преобразования программ методом гиперплоскостей.Метод гиперплоскостей применим только к многомерным циклам. В пространстве итераций ищетсяпрямая (плоскость), на которой возможно параллельное асинхронное выполнение тела цикла, причем вотличие от метода координат, эта прямая (плоскость) может иметь наклон по отношению к осямкоординат.
Цикл вида:DO 5 I = 2,NDO 5 J = 2,M5 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 и т.д., на последнем ((N2)+(M-2)+1) - ом шаге - на прямой I+J=M+N.В общем случае для n-мерного тесногнездового цикла ищется семейство параллельных гиперплоскостей вn-мерном пространстве итераций, таких что во всех точках каждой из этих гиперплоскостей возможнопараллельное выполнение тела цикла.Для приведенного примера множество точек, в которых возможно параллельное выполнение, являетсяоднопараметрическим (прямая) и определяется из решения уравнения 1I+J=K 0. Цикл (5) может бытьпреобразован к виду:DOTнTкDOIJ55K = 4,M+N= MMAX(2,K-N)= MMIN(M,K-2)5 T = Tн,Tк 1: PAR= T= K - TA(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5Функция MMAX(X,Y) выбирает ближайшее целое, большее или равное максимуму из чисел X и Y ,а функция MMIN(X,Y) - ближайшее целое, меньшее или равное минимуму из X и Y .47Внутренний цикл по переменной T может выполняться параллельно для всех значений T .
Границыизменения переменной цикла T меняются при переходе с одной прямой (гиперплоскости) на другую,поэтому их необходимо перевычислять во внешнем цикле. Число итераций внутреннего цикла, то естьпотенциальная длина векторной операции, меняется с изменением K . Для приведенного примерадиапазон изменения T сначала возрастает, а потом убывает, причем для начального и конечного значенияK он равен единице. В некоторых случаях для отдельных значений K накладные расходы наорганизацию векторного вычисления могут превысить эффект ускорения от векторного выполнения.Вопрос оценки целесообразности проведения векторизации данным методом должен рассматриваться длякаждого конкретного случая отдельно.66.
Метод параллелепипедов.Идея методазаключаетсяввыявлении зависимых итераций цикла и объединении их впоследовательности - ветви, которые могут быть выполнены независимо друг от друга. П ри этом впространстве итераций определяются области (параллелепипеды), все точки которых принадлежат разнымветвям. Задача максимального распараллеливания заключается в поиске параллелепипеда наибольшегообъема; тогда исходный цикл выполняется наибольшим числом параллельных ветвей, каждая из которыхпредставляет собой исходный цикл, но с другим шагом изменения индекса.Для исходного цикла:DO 7 I = 1,7DO 7 J = 1,37 X(I,J) = X(I-2,J-1)параллельное представление в виде:DO 7 (K,L) = (1,1) (P1,P2)1: PARDO 7 I = K,7,P1DO 7 J = L,3,P27 X(I,J) = X(I-2,J-1)допускается для различных разбиений пространства итераций: пара (P1,P2) может иметь, например,значения (2,1), (2,3) или (7,1).
Таким образом, исходный цикл (7) преобразуется в последовательностьпараллельных ветвей, имеющих циклический вид.В общем виде задача, рассматриваемая методом параллелепипедов, для одномерных циклов состоит вопределении возможности представления цикла:DO L I = 1,rL T(I)(где T(i) - тело цикла) в виде следующей языковой конструкции:DO L K = 1,p1: PARDO L I = K,r,pL T(I)67.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
