Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

* 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

* Н - неоднозначные отношения

* 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)

1. Схема преобразования программ методом гиперплоскостей.

Метод гиперплоскостей применим только к многомерным циклам. В пространстве итераций ищется прямая (плоскость), на которой возможно параллельное асинхронное выполнение тела цикла, причем в отличие от метода координат, эта прямая (плоскость) может иметь наклон по отношению к осям координат. Цикл вида:

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 накладные расходы на организацию векторного вычисления могут превысить эффект ускорения от векторного выполнения.

Вопрос оценки целесообразности проведения векторизации данным методом должен рассматриваться для каждого конкретного случая отдельно.

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

Идея метода заключается в выявлении зависимых итераций цикла и объединении их в последовательности - ветви, которые могут быть выполнены независимо друг от друга. П ри этом в пространстве итераций определяются области (параллелепипеды), все точки которых принадлежат разным ветвям. Задача максимального распараллеливания заключается в поиске параллелепипеда наибольшего объема; тогда исходный цикл выполняется наибольшим числом параллельных ветвей, каждая из которых представляет собой исходный цикл, но с другим шагом изменения индекса.

Для исходного цикла:

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)

1. Оценить возможность параллельного выполнения цикла: DO i = 2,N A(i) = (B(i) + (i))/A(i+CONST) ENDDO

Если const = 0, то все итерации цикла независимы и такой цикл может быть выполнен на любой многопроцессорной ЭВМ, включая Иллиак-4. (каждый виток цикла выполняется на отдельном процессоре)

Если const > 0 (пусть =1) то при параллельное выполнение цикла на ЭВМ класса МКМД без дополнительных мер по синхронизации работы процессоров невозможно. Например, пусть N=3 и два процессора вычисляют параллельно эти итерации, тогда, первый процессор вычисляет А2 по В2, С2, А3, а второй, А3 по В2, С2, А4 . При отсутствии синхронизации может случиться ситуация, при которой второй процессор завершит свою работу до начала работы первого. Тогда первый процессор для вычислений будет использовать А3, которое обновил второй процессор, что неверно, ибо здесь нужно “старое” значение А3.

Однако, этот цикл выполняется параллельно на ЭВМ ОКМД (SIMD) так как там этот цикл может быть выполнен такими командами:

1. Считать Вi в сумматоры каждого из n АЛУ.

2. Сложить Сi со своим содержимом сумматора.

3. Разделить содержимое каждого i-сумматора на Аi+1.

4. Записать содержимое i- сумматоров в Аi.

Из за того, что выборка из памяти и запись в память производится синхронно (одновременно), то работа цикла – корректна.

Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполнения очередной итерации цикла необходимы результаты работы предыдущей (рекурсия). Однако известны приемы преобразования такого рода циклов к виду, допускающие параллельное выполнение.

1. Стандарты OpenMP.

Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах (SSMP,ccNUMA, etc.) в модели общей памяти (shared memory model). В стандарт OpenMP входят спецификации набора директив компилятора, процедур и переменных среды.

До появления OpenMP не было подходящего стандарта для эффективного программирования на SMP-системах.

Наиболее гибким, переносимым и общепринятым интерфейсом параллельного программирования является MPI (интерфейс передачи сообщений). Однако модель передачи сообщений 1) недостаточно эффективна на SMP-системах; 2) относительно сложна в освоении, так как требует мышления в "невычислительных" терминах.

Проект стандарта X3H5 провалился, так как был предложен во время всеобщего интереса к MPP-системам, а также из-за того, что в нем поддерживается только параллелизм на уровне циклов. OpenMP развивает многие идеи X3H5.

POSIX-интерфейс для организации нитей (Pthreads) поддерживается широко (практически на всех UNIX-системах), однако по многим причинам не подходит для практического параллельного программирования:

• нет поддержки Fortran-а,

• слишком низкий уровень,

• нет поддержки параллелизма по данным,

• механизм нитей изначально разрабатывался не для целей организации параллелизма.

OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (или аналогичными библиотеками нитей).

Многие поставщики SMP-архитектур (Sun,HP,SGI) в своих компиляторах поддерживают спецдирективы для распараллеливания циклов. Однако эти наборы директив, как правило, 1) весьма ограничены; 2) несовместимы между собой; в результате чего разработчикам приходится распараллеливать приложение отдельно для каждой платформы. OpenMP является во многом обобщением и расширением упомянутых наборов директив.

Директивы OpenMP с точки зрения Фортрана являются комментариями и начинаются с комбинации символов "!$OMP". Директивы можно разделить на 3 категории: определение параллельной секции, разделение работы, синхронизация. Каждая директива может иметь несколько дополнительных атрибутов - клауз. Отдельно специфицируются клаузы для назначения классов переменных, которые могут быть атрибутами различных директив.

Порождение нитей

PARALLEL ... END PARALLEL
Определяет параллельную область программы. При входе в эту область порождаются новые (N-1), образуется "команда" из N нитей, а порождающая нить получает номер 0 и становится основной нитью команды (т.н. "master thread"). При выходе из параллельной области основная нить дожидается завершения остальных нитей, и продолжает выполнение в одном экземпляре. Предполагается, что в SMP-системе нити будут распределены по различным процессорам (однако это, как правило, находится в ведении операционной системы).

Каким образом между порожденными нитями распределяется работа - определяется директивами DO,SECTIONS и SINGLE. Возможно также явное управление распределением работы (а-ля MPI) с помощью функций, возвращающих номер текущей нити и общее число нитей. По умолчанию (вне этих директив), код внутри PARALLEL исполняется всеми нитями одинаково.

Вместе с PARALLEL может использоваться клауза IF(условие) - й параллельная работа инициируется только при выполнении указанного в ней условия.

Параллельные области могут динамически вложенными. По умолчанию (если вложенный параллелизм не разрешен явно), внутренняя параллельная область исполняется одной нитью.

Разделение работы (work-sharing constructs)

Характеристики

Список файлов лекций