СКИПОДы 2007 полная версия (1127795), страница 48
Текст из файла (страница 48)
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 — смаксимально возможным шагом (в данном случае равным трем). Таким образом, внутрикаждого параллелепипеда оказалось по шесть независимых итераций, которые можно выполнитьпараллельно.
Если в цикле есть информационные связи между операторами, запрещающиепараллельное выполнение, то можно попытаться устранить эти связи, применив методкоординат. Данный метод предполагает осуществление в теле цикла некоторых преобразований, аименно: перестановку операторов, введение дополнительных переменных и массивов.Подобные преобразования производятся таким образом, чтобы изменить направление илиустранитьзапрещающие связи между операторами в различных итерациях. При этом результатвычислений не должен изменяться.
В качестве примера использования метода координатрассмотрим следующий цикл:DO 4 I = 2, N1 X (I) = Y (I) + Z (I)2 Z (I) = Y (I - 1)3 Y (I) = X (I + 1) ∗∗ 24 CONTINUEЗапрещающими связями в данном примере является связь между использованиемпеременной Y(I-1) во втором и генерацией Y(I) в третьем операторах, а также связьгенерации X(I) в первомоператоре с использованием генерации X(I + 1) в третьем операторе. Направление первойсвязи по Y можно изменить на противоположное перестановкой второго и третьегооператоров.
Вторуюсвязь по X можно устранить введением дополнительного массива T. Таким образом,эквивалентный исходному преобразованный цикл, который можно выполнитьодновременно для всех значений индекса I, будет иметь такой вид:DO 4 I = 2, NR (I) = X (I + 1)1 X(I) = Y (I) + Z (I)3 Y (I) = R (I) ∗∗ 22 Z (I) = Y (I - 1)4 CONTINUEНеобходимо отметить, что методом параллелепипедов и методом координат можнораспараллеливать как одномерные, так и многомерные тесногнездовые циклы.В рассматриваемых методах распараллеливания индексные выражения элементов массивовдолжны быть линейными функциями относительно параметров цикла, т.
е. иметь видA∗I±B, где A160и B — целые константы; I — параметр цикла DO. Необходимо также, чтобы в индексныхвыражениях использовались одноименные индексные переменные. Не допускаетсяприменение нелинейных индексов типа X(I∗J∗K) или косвенной индексации, напримерX(N(I)).Основным препятствием к распараллеливанию циклов является так называемое условиеРассела — использование в теле цикла простой неиндексированной переменной раньше,чем этой переменной присваивается в цикле некоторое значение, например:DO 1 I = 1, N DO 1 I = 1, N1 S = S + X (I) или X (I) = S ∗ Y (I)1 S = Z (I) ∗∗ 2Распараллеливанию препятствуют и обратные информационные и конкуренционные связимежду операторами тела цикла.Рассмотрим пример:DO 1 I = 1, N1 X (I) = X (I - 1)Итерации этого цикла связаны обратной информационной зависимостью с шагом, равнымединице. Вообще говоря, конструкции видаDO 1 I = 1, N...X (I) = X (I + K)...1 CONTINUEгде K — целочисленная переменная, векторизуются только в том случае, если знакпеременной K совпадает со знаком инкремента цикла.
В большинстве же случаев знакчисла K не может быть определен на этапе компиляции, поэтому такие конструкциисчитаются невекторизуемыми. Из соотношения (5.4) следует, что если в теле цикла нетодноименных входных и выходных переменных, то подобный цикл векторизуется. Если вцикле генерация простой переменной встречается раньше, чем ее использование, то этотцикл также векторизуется:DO 1 I = 1, NS = X (I) + Y (I)1 Z (I) = Z (I) - SИнформационная зависимость между итерациями появляется только в том случае, если втеле цикла имеются одноименные входные и выходные переменные с несовпадающимииндексными выражениями, например X(I) и X(I - 1).
Направление связи (прямоеили обратное) зависит от номеров операторов, в которых используются эти переменные.Если совпадающие индексные выраженияи связи между итерациями отсутствуют, то такие циклы распараллеливаются:DO 1 I = 1, NX (I) = Y (I + 1) + Z (I)1 Y (I + 1) = X (I) ∗∗ 2В этом случае одноименные пары X(I) и Y(I + 1) имеют совпадающие индексы и непрепятствуют векторизации. Рассмотрим часто встречающуюся на практике циклическуюконструкцию, в которой переменная целого типа используется в качестве неявногопараметра цикла:J=0DO 1 I = 1, NJ=J+21 X (I) = Y (I)В этом случае в массив X заносятся четные элементы из массива Y. Роль второго параметрацикла играет переменная J, и хотя для J формально выполняется условие Рассела, этот циклможно распараллелить.Иногда цикл, в котором выполняется условие Рассела, оказы161вается вложенным в другой цикл, например:DO 1 I = 1, NS=0DO 2 J = 1, N2 S = S + X (I, J)Y (I) = S1 CONTINUEВ вектор Y заносятся значения суммы элементов строк матрицы X.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
