СКИПОДы конспект лекций (1127769), страница 19
Текст из файла (страница 19)
Метод предназначен для синхронной векторизации одномерных циклов(многомерные циклы можно рассматривать по каждому параметру отдельно). Идея данного метода состоитв том, что для индексов, содержащих параметры цикла, рассматривается порядок следования, который иопределяет очередность выборки/записи соответствующего элемента массива. Так как рассматриваютсятолько линейные индексные выражения, порядок следования определяется значениями соответствующихалгебраических выражений.
Строится граф характеристических множеств всех индексов, и приотсутствии в графе петель делается заключение о возможности векторизации всего цикла.В некоторых случаях (устранимая векторная зависимость) векторизация возможна лишь в случаепереупорядочивания - перестановки операторов цикла или путем введения временной переменной(массива), куда будут копироваться элементы вектора для защиты перед их изменением дляпоследующего использования в исходном виде. Итак, метод координат:- позволяет определить возможность выполнения цикла в синхронном режиме;- содержит алгоритмы преобразования тела цикла к синхронному виду.Например, по Лэмпорту, цикл:DO 24 I=2,MDO 24 J=2,N21A(I,J) = B(I,J)+C(I)22C(I) = B(I-1,J)23B(I,J) = A(I+1,J) ** 224CONTINUEпреобразуется в цикл:C21232224DO 24 J=2,NDO 24 SIM FOR ALL I {i:2<=i<=M}SIM - SI Multeneusly (одновременно)TEMP(I) = A(I+1,J)A(I,J) = B(I,J)+C(I)B(I,J) = TEMP(I) ** 2C(I) = B(I-1,J)CONTINUEКонструктивный алгоритм реализации метода координат.Пусть, цикл одномерный, все операторы тела - операторы присваивания, в левых частях которых переменные с индексом - параметром цикла.
Индексы линейные, т.е. имеют вид i+/-b,где b - константа.Определяются отношения следования для всех пар одноименных переменных с индексами: генерируемыхпеременных (переменные в левой части операторов присваивания - f) и используемых переменных(входящих в формулы правых частей - q). Отношение следования для одной пары зависит от порядкаобращения к одному и тому же элементу массива при выполнении цикла. Так, для A(I) = A(I+1)отношение можно кодировать: f<q .
Для многомерных циклов для всех пар (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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
