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