ПОД (пособие) (1184372), страница 49
Текст из файла (страница 49)
Данный метод предполагает осуществление в теле цикла некоторых преобразований, аименно: перестановку операторов, введение дополнительных переменных и массивов.Подобные преобразования производятся таким образом, чтобы изменить направление илиустранитьзапрещающие связи между операторами в различных итерациях. При этом результатвычислений не должен изменяться.
В качестве примера использования метода координатрассмотрим следующий цикл: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.
Внутренний цикл по J нераспараллеливается (выполняется условие Рассела для переменной S), а внешний цикл по I можнораспараллелить, так как переменная S в нем получает значение перед входом во внутренний цикл.Рассмотрим общую структуру ВК (рис. 5.5). Как правило, ВК состоит из синтаксическогоанализатора, распараллеливателя циклов, модуля оценки качества распараллеливания, генераторовпрограмм на параллельном ЯВУ или в машинных кодах.Схема преобразования программ методом гиперплоскостей.Метод гиперплоскостей применим только к многомерным циклам. В пространствеитераций ищется прямая (плоскость), на которой возможно параллельное асинхронноевыполнение тела цикла, причем в отличие от метода координат, эта прямая (плоскость)может иметь наклон по отношению к осям координат.
Цикл вида: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 и т.д., на последнем ((N-2)+(M-2)+1) - ом шаге - на прямойI+J=M+N.В общем случае для n-мерного тесногнездового цикла ищется семейство параллельныхгиперплоскостей в n-мерном пространстве итераций, таких что во всех точках каждой изэтих гиперплоскостей возможно параллельное выполнение тела цикла.Для приведенного примера множество точек, в которых возможно параллельноевыполнение, является однопараметрическим (прямая) и определяется из решенияуравнения 1I+J=K 0.
Цикл (5) может быть преобразован к виду:DO 5 K = 4,M+NTн = MMAX(2,K-N)Tк = MMIN(M,K-2)DO 5 T = Tн,Tк 1: PARI =T162J =K-T5 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,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,p 1: PARDO L I = K,r,p163L T(I)Оценить возможность параллельного выполнения цикла:DO i = 2,NA(i) = (B(i) + C(i))/A(i+CONST)ENDDOПараллельное выполнение цикла видаDO i=2,N A(I) =(B(i)+C(i))/A(i+const) ENDDO.Если const = 0, то все итерации цикла независимы и токой цикл может быть выполнен налюбой многопроцессорной ЭВМ, влючая Иллиак-4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
