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

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

Исходные тела циклов Преобразованные тела циклов

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)

Параллельные циклы

DO ... [ENDDO]
Определяет параллельный цикл.

Клауза SCHEDULE определяет способ распределения итераций по нитям:

• STATIC,m - статически, блоками по m итераций

• DYNAMIC,m - динамически, блоками по m (каждая нить берет на выполнение первый еще невзятый блок итераций)

• GUIDED,m - размер блока итераций уменьшается экспоненциально до величины m

• RUNTIME - выбирается во время выполнения .

По умолчанию, в конце цикла происходит неявная синхронизация; эту синхронизацию можно запретить с помощью ENDDO NOWAIT.

Параллельные секции

SECTIONS ... END SECTIONS
Не-итеративная параллельная конструкция. Определяет набор независимых секций кода (т.н., "конечный" параллелизм). Секции отделяются друг от друга директивой SECTION.

Примечание. Если внутри PARALLEL содержится только одна конструкция DO или только одна конструкия SECTIONS, то можно использовать укороченную запись: PARALLEL DO или PARALLEL SECTIONS.

Исполнение одной нитью

SINGLE ... END SINGLE
Определяет блок кода, который будет исполнен только одной нитью (первой, которая дойдет до этого блока).

Явное управление распределением работы

С помощью функций OMP_GET_THREAD_NUM() и OMP_GET_NUM_THREADS нить может узнать свой номер и общее число нитей, а затем выполнять свою часть работы в зависимости от своего номера (этот подход широко используется в программах на базе интерфейса MPI).

Директивы синхронизации

• MASTER ... END MASTER
  Определяет блок кода, который будет выполнен только master-ом (нулевой нитью).

• CRITICAL ... END CRITICAL
  Определяет критическую секцию, то есть блок кода, который не должен выполняться одновременно двумя или более нитями

• BARRIER
  Определяет точку барьерной синхронизации, в которой каждая нить дожидается всех остальных.

• ATOMIC
  Определяет переменную в левой части оператора "атомарного" присваивания, которая должна корректно обновляться несколькими нитями.

• ORDERED ... END ORDERED
  Определяет блок внутри тела цикла, который должен выполняться в том порядке, в котором итерации идут в последовательном цикле. Может использоваться для упорядочения вывода от параллельных нитей.

• FLUSH
  Явно определяет точку, в которой реализация должна обеспечить одинаковый вид памяти для всех нитей. Неявно FLUSH присутствует в следующих директивах: BARRIER, CRITICAL, END CRITICAL, END DO, END PARALLEL, END SECTIONS, END SINGLE, ORDERED, END ORDERED.

В целях синхронизации можно также пользоваться механизмом замков (locks).

В OpenMP переменные в параллельных областях программы разделяются на два основных класса:

• SHARED (общие; под именем A все нити видят одну переменную) и

• PRIVATE (приватные; под именем A каждая нить видит свою переменную).

Отдельные правила определяют поведение переменных при входе и выходе из параллельной области или параллельного цикла: REDUCTION, FIRSTPRIVATE, LASTPRIVATE, COPYIN.

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

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

Список файлов ответов (шпаргалок)