10 Continue

После использования метода пирамид получаются конструкции вида:

DO 10 CONC FOR ALL K{1,…,R_r}

DO 10 I₁=1,R₁

DO 10 I₂=MAX{1,K-[(R₁-I₁)G₂/G₁]}, MIN{R₂,K+[(R₁-I₁)H₂/H₁]}

<ТЕЛО ЦИКЛА>

10 Continue

Д ля векторно-конвейерной системы (SIMD) метод пирамид очень неэффективен.

Элементы языка Fortran.

Фортран - язык фиксировано-свободных форматов записи. Любой оператор состоит из 80-ти символов. Состоит из метки (5 символов), далее пробел и до конца - операнды. Если не хватает 80 символов, то можно писать на следующей строке при условии, что шестым символом идет символ, отличный от пробела.

В качестве метки используются только целые положительные числа. Алфавит – только заглавные латинские буквы, знаки арифметических операций.

Если буква С в первой позиции то далее будет комментарий.

Типы данных

INREGER

REAL

LOGICAL (bool)

Все, которые начинаются с I,J,K,L,M,N – по умолчанию целые, а прочие – вещественные.

Явное описание, возможно, любым INTEGER B5.

Неявное описание IMPLICIT REAL J.

Массивы.

Массивы описываются словом DIMENSION A(10,10), в скобках указываются верхние границы индексов, а нижние всегда единица. Максимальное измерение 7. В памяти располагаются по столбцам.

Структура программы.

ОСНОВНАЯ

ПРОГРАММА

ПРОДПРОГРАММА1

ПРОДПРОГРАММА2

…

ПРОДПРОГРАММАn

Каждый раздел заканчивается словом «END». Описание переменных идет сначала раздела.

Подпрограммы начинаются со слов SUBROUTINE или FUNCTION.

Операторы:

1. Оператор присваивания: <переменная> = <выражение>

** - возведение в степень

2. Логические отношения:

.EQ

.NE

.LT

.GT

.GE

.LE

3. Логические операции

.NOT

.AND

.OR

.XOR

4. Логические константы

.TRUE

.FALSE

Переход GOTO <метка>

Логический IF <логическое выражение> <оператор1> <оператор2>

Арифметический IF <арифметическое выражение> (M1, M2, M3)

Если меньше нуля, то переход на M1, равно нулю M2, больше M3.

Цикл

DO <метка> <оператор цикла> = <начальное значение>, <верхняя граница>

<тело цикла>

<метка>

Оператор CONTINUE – аналогия break

Вызов процедуры CALL <имя процедуры> (список операторов)

ЭЛЕМЕНТЫ ЯЗЫКА FORTRAN (продолжение)

25/09

Операторы ввода и вывода

В языке фортран осуществляется форматный ввод и вывод. Это означает что операторы ввода и вывода применяются в паре с форматом, которое может быть помещено в любой части программы.

Обычно номер канала: для ввода 5, для вывода 6.

READ (номер канала, метка формата) список ввода.

WRITE (номер канала) список вывода.

Метка формата это FORMAT (I4, F8.3 …). Каждая спецификация может иметь кратность повторения и заключаться в скобки, например 2(4I4,5F8.3). Работает как цикл. Первый вывод при выводе является управляющим: 1X.

Для размещения введенного формата используются спецификации целых I, (доп. еще E, F), затем идет число позиции, например I4.

Для F – F8.3, затем число позиций после запятой.

Для плавающей запятой E10.5.1 , где второе – для мантиссы, а последнее для изображения чисел после запятой.

Для порядка обозначатся E+01.

Спецификация L – для логических переменных (например, L4), спецификация X – пробег (2X – два пробега)

Для ввода/вывода массива можно использовать неявный цикл

DIMENSION A(5), B(3,3)

…

WRITE (6,1) ((B(I,J), J=1,3), I=1,3)

1FORMAT(1X,3F8.3)

Структура первой лабораторной работы

Описание массивов

<S=10>

Инициализация переменной (присваиваем по одной переменной)

CSBEG

Последовательный участок

CSEND

CPBEG

Параллельный участок

CPEND

Сравнение результатов последовательного и параллельного участка

END

Рекуррентные соотношения

DIMENSION A(10), B(10)

EQUIVALENCE A(1), B(2)

В данном соотношении происходит привязывание переменных A(1) и B(2) к одному и тому же участку памяти.

РАСПАРАЛЛЕЛИВАНИЕ ЦИКЛОВ

Существует несколько методов:

• Метод гиперплоскостей

• Метод координат

• Метод параллелепипедов

• Метод пирамид

Метод гиперплоскостей.

Метод координат.

Метод параллелепипедов.

Метод пирамид.

МЕТОД ГИПЕРПЛОСКОСТЕЙ.

Пусть дан гнездовой циклический алгоритм вида:

DO 99 I=1,L

DO 99 J=2,M

DO 99 K=2,N

V(J,K)=(V(J+1,K)+V(J-1,K)+V(J,K-1)+V(J,K+1))*0,25

99 CONTINUE

Вычисляет среднее арифметическое между четырьмя точками.

Уравнение плоскости: 2*I+J+K = const

Для перехода к параллельному циклу используем переменные:

1 конструкция	2 конструкция	Результирующий (параллельный) цикл
I1, J1, K1: I1=2*I+J+K J1=I K1=K	I, J, K I = J1 J=I1-2*J1-K1 K=K1	DO 99 I=6,2*L+N+M DO 99 CONC FOR ALL (J1, K1)  { ( J1, K1): 1 ≤ J1 ≤ K1, 2 ≤ I1-2*J1-K1 ≤ M, 2 ≤ K1 ≤ N } V ( I1-2*J1-K1, K1 ) = ( V ( I1-2*J1-K1+1,K1 ) + V (I1-2*J1-K1, K1+1 ) + V (I1-2*J1-K1, K1 ) + V (I1-2*J1-K1, K1-1 ) ) *0.25 99 CONTINUE

В 1 конструкции количество повторений равно L*(M-1)*(N-1)

Во 2 новой конструкции 2*L+M+N-5.

Замечание: результирующий цикл записан на параллельном Фортране.

Общая постановка задачи:

Дан

DO A I¹=l¹, U¹

.

.

.

DO A Iⁿ=lⁿ, Uⁿ

<тело цикла>

A CONTINUE

Для использования метода гиперплоскостей необходимо, чтобы тело цикла не содержало:

• операторов ввода–вывода

• передач управления вне цикла

• обращений к процедурам и функциям, которые изменяют переменные в теле цикла.

Индексные выражения в операторах тела цикла должны иметь вид lⁱ+mⁱ, где lⁱ – i-я переменная, mⁱ - i-я константа. Разрешено I+2; запрещено I+J, I*2, I*J.

В результате применения метода гиперплоскостей исходный цикл преобразуется к виду:

DO A J¹=L¹, M¹

.

.

.

DO A J^k=L^k,M^k

DO A CONC FOR ALL (J^k+1, … Jⁿ)  S_Y¹_...Yⁿ

< тело цикла>

A CONTINUE

Происходит свертывание пространственных операций, то есть изменение размерности на N-K

МЕТОД ГИПЕРПЛОСКОСТЕЙ. (продолжение)

9/10

Для нахождения уравнения гиперплоскости строится взаимно-однозначное отображение переменных в теле исходного цикла в новые переменные. Это отображение ищется в виде:

Для нахождения коэффициентов а_jⁿ решается задача линейного целочисленного программирования, в которой формулируется ряд ограничений на коэффициенты а: в исходном и результирующем цикле все использования переменных должны следовать за их генерациями в теле цикла.

a=b.

a – использование, b – генерация.

В лабораторной работе надо будет перейти к двумерным переменным и подобрать коэффициенты:

I₁ = a_{11 *} I + a_{12 *} J

J₂ = a_{21 *} I + a_{22 *} J

[-1 ÷ +1]

+1 – поворот на 45 градусов против часовой

-1 – по часовой.

Должен получиться один цикл перебора, но с вызовом #CALL () для каждой текущей линии.

Недостатки и достоинства метода.

Достоинством метода гиперплоскостей является то, что он хорошо формализован и, следовательно, он может быть использован в трансляторах с параллельных языков программирования для автоматического распараллеливания циклов.

Недостатком метода является сложность получения алгоритма гиперплоскости а также неприменимость для некоторых видов циклов (в частности для простых циклов).

МЕТОД КООРДИНАТ.

Рассмотрим следующий пример:

Исходный цикл:

DO 24 I=2,M

DO 24 J=1,N

21 A(I,J)=B(I,J)+C(I)

22 C(I)=B(I+1,J)

23 B(I,J)=A(I+1,J)*2

24 CONTINUE

Методом координат этот цикл будет преобразован следующим образом:

DO 24 I=1,N

DO 24 SIM FOR ALL I  {I: 2 ≤ I ≤ M}

21 A(I,J)=B(I,J)+C(I)

23 B(I,J)=TEMP(I)**2

22 C(I)=B(I-1,J)

24 CONTINUE

Здесь, в отличии от метода гиперплоскостей, употребляется конструкция SIM.

SIM конструкция: тело цикла можно выполнять параллельно для нескольких итераций, но необходимо пооператорная синхронизация, т.е. параллельно выполняется первый оператор цикла для всех итераций, и только по окончании выполнения этого оператора во всех итерациях осуществляется переход ко второму оператору и так далее.

Из примера видно, что значения, вычисленные оператором 23 в i-той итерации используется в операторе 22 в i+1-ой итерации, что и мешает их независимой работе.

Из этого примера так же видно, что для эквивалентности исходного и полученного цикла пришлось вводить дополнительную переменную TEMP и менять метами 23 и 22 операторы, то есть осуществлять неформальные преобразования.

Достоинства метода:

1. Если рассмотренный пример решать методом гиперплоскостей, то при переходе к новым переменным

получаем M+N-2 повторений, а для метода координат - N повторений.

2. Метод координат не требует сложных преобразований индексов.

3. Метод применим и для простых циклов. Наиболее целесообразно использовать метод координат при распараллеливании в системах класса SIMD.

Рассмотренный ранее пример для метода гиперплоскостей не может быть решен методом координат. Для каждого вида цикла подходит тот или иной метод.

МЕТОД ПАРАЛЛЕЛЕПИПЕДОВ.

В этом методе подмножества независимо выполняемых операций ищутся в форме прямоугольных параллелепипедов. Данный метод так же применим и для простых циклов.

Рассмотрим следующий пример.

DO 2 I=1,15

X(I)=X(G*I-27)

2 CONTINUE

В этом примере рассматривается одномерный случай пространства итераций, и в результате параллельный счет осуществляется для точек, принадлежащий отрезку прямой длиной = 4.

DO 2 I=1, 4

DO 2 CONC FOR ALL J  { 4*(I-1) ≤ J ≤ MIN {4*I,15} }

X(I)=X(G*I-27)

2 CONTINUE

Общая постановка задачи.

Пусть I={I₁,I₂,…,I_n} – исходное пространство итераций. Требуется найти такие целые числа, P₁,P₂,…,P_n, называемые ребрами параллелепипеда, при которых исходные конструкции вида

DO 1 I₁=1,R₁

DO 1 I₂=1,R₂

……

DO 1 I_n=1,R_n

<ТЕЛО ЦИКЛА>

1 CONTINUE

ставится в соответствие эквивалентная конструкция вида

DO 2 CONC FOR ALL J  {1,N}

DO 2 K_j=1, P_j

DO 2 I₁=K₁, R₁, P₁

DO 2 I₂=K₂, R₂, P₂

……

DO 2 I_n=K_n, R_n, P_n

<ТЕЛО ЦИКЛА>