ПОД (пособие) (1184372), страница 48
Текст из файла (страница 48)
Для многомерных циклов для всех пар (f,q)определяются направляющие вектора, элементы которых состоят из символов (=, >, <) впозиции соответствующего индекса, которая определяется порядком индексов в гнездецикла. В примере Лемпорта (исходном) для А вектор имеет вид: (<,=).Для тела цикла, состоящего из одного оператора, отношения, и соответственно,семантика выполнения, могут быть: < > = и их сочетание. Например, тело цикла: A(I) =(А(I)+A(I+1))/2 допускает векторное выполнение; оно невозможно при наличии воператоре хотя бы одного соотношения: f>q.
Для тела цикла: A(I) = A(I+C))/2 при С>0возможно синхронное выполнение, при С=0 кроме синхронного, возможно параллельноеасинхронное; а при С<0 параллельное выполнение невозможно.Для многомерных (тесногнездовых) циклов такое исследование может проводиться длякаждого параметра, а для распараллеливания выбираться наиболее оптимальный вариант.Для самого внутреннего цикла определение следования можно проводить, считая егоодномерным. Для любого другого цикла, исследование можно проводить по такой жесхеме, если семантика цикла допускает перестановку его на позицию самого внутреннего.Перестановка допустима, если для всех новых направляющих векторов крайне левый,отличный от = , элемент сохранил направление. Например, для двумерного цикла,наличие вектора (<,>) делает перестановку некорректной.
Так для цикла:156DO 99 J=2,MDO 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 ,Н - неоднозначные отношения.
Тогда по координатам приводимой ниже таблице можноопределить типы связей и метод выполнения цикла для этих операторов. Если объединитьинформационные поля двух операторов , то таблицу можно использовать для анализатретьего оператора и т.д.* Таблица решений для метода координат* Оператор 1 O1 = I1 Oi,Ii - список переменных с индексами* Оператор 2 O2 = 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* Н - неоднозначные отношения157* TИПЫ CBЯЗEЙ* P - независимые операторы* M - SIMD , M(EA) - SIMD с защитой EA* R - SIMD с реверсом, R(EA) - и с защитой EA* S - PAR (асинхронная параллельность)* T - запрет векторизации* Защита ЕА - копирование массивов ЕА передВ общем случае, алгоритм векторизации методом координат с использования даннойтаблицы следующий.Обработка тела цикла начинается с анализа на возможность векторного выполнениякаждого оператора тела в отдельности.
Затем к первому оператору добавляется второй ипроводится анализ на возможную их векторизацию. Пара получает тип, определяющийвозможность векторизации ее компонент, информационные поля операторов сливаются, ина следующем шаге применения процедуры векторизации пара рассматривается какединый супероператор. Таким образом из всех операторов тела цикла образуется одинсупероператор и, если его тип есть Т, то векторизация тела цикла невозможна. Для всехдругих типов производится обратный анализ полученного графа (супероператора).
Еслипри этом связки имели тип R или R(EA),M(EA), то хотя они и допускают асинхронноепараллельное выполнение, но необходимы преобразование тела цикла. Связки типа Т даютоператоры, векторизация которых невозможна. Интерпретация остальных типов связокочевидна. В процессе формирования супероператоров к связкам типа Т могут применятьсяпроцедуры поиска минимальных границ области типа Т и чистки области Т.Примеры векторизацииИсходные тела циклов Преобразованные тела циклов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-)B(I) = A(I)Векторизация невозможнаДополнениеНаибольшим внутренним параллелизмом, который можно использовать для векторизациипрограмм, являются циклические участки, так как на них приходится основное времявычислений, и в случае распараллеливания вычисления в каждой ветви производится поодному и тому же алгоритму.
В методах распараллеливания циклов используется довольносложный математический аппарат. Наиболее распространеннымиметодами распараллеливания являются: метод параллелепипедов, метод координат, методгиперплоскостей. Объектами векторизации в этих методах являются циклы типа DО вФортране. При постановке в общем виде задачи распараллеливания циклов вводитсяпонятие “пространство итераций” — n-мерное целочисленное пространство с158координатными осями I1,K,In, соответствующими индексным переменным исходногоцикла.
Каждая итерация (повторение тела цикла при различных значениях индексов) представляет собой точку в этом пространстве и характеризуется значением вектора(i1,K,in), где ij — номер выполнения итерации на j-м уровне вложенности. Исходныйтесногнездовой цикл имеет видDO 1 I1 = 1, M1...DO 1 In = 1, MnS(i1, ..., in)1 CONTINUEШаг изменения цикла предполагается равным единице. Тело цикла S i in ( 1,K, ) состоит изпоследовательности пронумерованных по порядку операторов. На тело цикла, как правило,накладываются некоторые ограничения, зависящие от типа ЭВМ и методараспараллеливания: все индексные выражения должны быть линейными функциями отпараметров цикла; не допускаются условные и безусловные переходы из тела цикла за егопределы, а внутри цикла передача управления может осуществляться только вперед, т. е.операторы IF и GO TO нельзя применять для организации цикла.
Не допускаетсяиспользование в теле цикла операторов ввода-вывода и обращений к подпрограммам.Для цикла (5.3) пространство итераций представляет собойнабор целочисленных векторов I = { i1,K,in }, 1≤ij≤Mj. Распараллеливание цикла (5.3)заключается в разбиении этого пространства на подобласти, внутри которых все итерациимогут выполняться одновременно и при этом будет сохраняться порядок информационных связей исходного цикла. Порции независимых итераций можно искать ввиде n-мерных параллелепипедов, гиперплоскостей и т. д. в соответствии с методомраспараллеливания.Необходимое условие параллельного выполнения i-й и j-й итераций цикла записывается ввиде(OUT(i)∧IN(j))∨(IN(i)∧OUT(j))∨(OUT(i)∧OUT(j))=∅ (5.
4)Здесь IN(i) и OUT(i) — множества входных и выходных переменных i-й итерации. Двапервых дизъюнктивных члена из (5.2) задают учет информационной зависимости междуитерациями, т. е. параллельное выполнение может быть невозможным, если однаи та же переменная используется в теле цикла как входная и как выходная. Третий членучитывает конкуренционную зависимость, которая появляется в теле цикла в качествевыходной больше одного раза.Отношение зависимости между итерациями можно представить в виде графа D.
Вершиныграфа соответствуют итерациям цикла. Вершины i и j соединяет дуга, если они зависимы, итогда D(i, j) = 1. Задачу распараллеливания цикла можно сформулиро вать как задачуразбиения графа D на несвязные подграфы Di. Вершины, входящие в один подграф,должны быть независимыми и иметь смежные номера. Проиллюстрируем применениеметода параллелепипедов на примере следующего цикла [10]:DO 1 I = 2, 5DO 1 J = 2, 4 (5.
5)1 X (I, J) = X (I - 1, J - 1) ∗∗ 2Пространство итераций и информационные связи приведены на рис. 5.4, а. В данном случаевершины, лежащие вдоль диагонали прямоугольника, информационно связаны. Так, витерации с номером (2. 2) генерируется переменная X(2, 2), которая затем используется вкачестве входной переменной в итерации (3.
3). Разбиение итераций на параллелепипедыможно осуществить вдоль осей I и J (см. рис. 5.4, а).159Проиллюстрируем применение метода параллелепипедов для другого цикла:DO 1 I = 2, 5DO 1 J = 2, 4 (5. 6)1 X (I, J) = X (I - 2, J) ∗∗ 2Пространство итераций и информационные связи приводятся на рис. 5.4, б. Разбиение напараллелепипеды можно провести вдоль оси I с шагом, равным двум, а вдоль оси J — смаксимально возможным шагом (в данном случае равным трем). Таким образом, внутрикаждого параллелепипеда оказалось по шесть независимых итераций, которые можно выполнитьпараллельно. Если в цикле есть информационные связи между операторами, запрещающиепараллельное выполнение, то можно попытаться устранить эти связи, применив методкоординат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
