Fortran-DVM - оглавление Часть 1(1-4) Часть 2(5-6) Часть 3
(7-15)
Часть 4 (Приложения)
создан: октябрь, 2009 - последнее обновление 18.10.10 -

7.  Параллелизм задач

Модель параллелизма DVM объединяет параллелизм по данным и параллелизм задач.

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

Параллелизм задач реализуется независимыми вычислениями на секциях массива процессоров.

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

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

1)    Описание массива задач (директива TASK).

2)    Отображение массива задач на секции массива процессоров (директива MAP).

3)    Распределение массивов по задачам (директива REDISTRIBUTE).

4)    Распределение вычислений (блоков операторов или витков параллельного цикла) по задачам (конструкция TASK_REGION).

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

7.1. Описание массива задач

Массив задач описывается следующей директивой: 

task-directive

is   TASK  task-list

 

 

task

is   task-name ( max-task )

 

 

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

7.2. Отображение задач на процессоры. Директива MAP

Отображение задачи на секцию массива процессоров выполняется директивой MAP

map-directive

is  MAP task-name ( task-index )

 

    ONTO  processors-name( processors-section-subscript-list)

 На одну секцию могут отображаться несколько задач.

7.3. Распределение массивов по задачам

Распределение массивов по задачам осуществляется директивой REDISTRIBUTE со следующим расширением: 

dist-target

is   .   .   .

 

or  task-name ( task-index )

 Массив распределяется на секцию массива процессоров, на которую уже была отображена задача.

7.4. Распределение вычислений. Директива TASK_REGION

Распределение блоков операторов по задачам описывается конструкцией TASK_REGION

block-task-region

is   task-region-directive

 

              on-block

 

            [ on-block ]...

 

       end-task-region-directive

 

 

task-region-directive

is   TASK_REGION  task-name   [ , reduction-clause ]

 

      [ , consistent-clause ]

 

 

end-task-region-directive

is    END  TASK_REGION

 

 

 

 

on-block

is   on-directive

 

             block

 

      end-on-directive

 

 

on-directive

is   ON   task-name ( task-index ) [ , new-clause ]

 

 

end-on-directive

is   END ON

 Область задач и каждый on-block являются последовательностями операторов с одним входом (первый оператор) и одним выходом (после последнего оператора). Для блоков операторов конструкция TASK_REGION по семантике эквивалентна конструкции параллельных секций для модели с общей памятью. Отличием является то, что блок операторов может выполняться на нескольких процессорах в модели параллелизма по данным.

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

loop-task-region

is   task-region-directive

 

              parallel-task-loop

 

      end-task-region-directive

 

 

parallel-task-loop

is   parallel-task-loop-directive

 

                   do-loop

 

 

parallel-task-loop-directive

is   PARALLEL ( do-variable
      ON 
task-name ( do-variable [ , new-clause ]

 Единицей распределенных вычислений является виток одномерного параллельного цикла. Отличием от обычного параллельного цикла является распределение витка на секцию массива процессоров. При этом секция определяется ссылкой на элемент массива задач.

Спецификации reduction-clause и new-clause имеют ту же семантику, что и для параллельного цикла. Значение редукционной переменной должно быть вычислено в каждой задаче. После окончания задач (END TASK_REGION) в случае синхронной спецификации автоматически выполняется редукция над значениями редукционной переменной по всем задачам. В случае асинхронной спецификации запуск редукции осуществляется директивой REDUCTION_START.

Ограничение:

7.5. Локализация данных в задачах

Задачей является on-block или виток цикла. Задачи одной группы имеют следующие ограничения по данным

После окончания задачи каждый массив должен иметь точно такое же распределение, какое существовало до запуска задачи. Если в задаче изменяется распределение массива, то оно должно быть восстановлено перед окончанием задачи.

7.6. Фрагмент статической многообластной задачи

Ниже приведен фрагмент программы, описывающей реализацию 3-х областной задачи (рис. 6.6.) в модели параллелизма по данным.

      CDVM$  PROCESSORS  P( NUMBER_OF_PROCESSORS( ) )

     С            массивы A1,А2,А3 - значения функции на предыдущей итерации

     С            массивы В1,В2,В3 - значения функции на текущей итерации

                   REAL  A1( M, N1+1 ),       B1( M, N1+1 )

                   REAL  A2( M1+1, N2+1 ), B2(M1+1, N2+1 )

                   REAL  A3( M2+1, N2+1 ), B3(M2+1, N2+1 )

     С            описание массива задач

     CDVM$  TASK  MB (3)

     С            выравнивание массивов в каждой области

     CDVM$  ALIGN  B1( I, J )      WITH    A1( I, J )

     CDVM$  ALIGN  B2( I, J )      WITH    A2( I, J )

     CDVM$  ALIGN  B3( I, J )      WITH    A3( I, J )

     С           

     CDVM$  DISTRIBUTE  :: A1, A2, A3

     CDVM$  REMOTE_GROUP  RS

                   .   .   .

     C            распределение задач на секции массива процессоров и

     С            распределение массивов по задачам

     С            (каждая секция содержит треть всех процессоров)

                   NP = NUMBER_OF_PROCESSORS( ) / 3

     CDVM$  MAP MB( 1 )  ONTO  P( 1 : NP )

     CDVM$  REDISTRIBUTE  ( *, BLOCK )  ONTO  MB( 1 ) :: A1

     CDVM$  MAP MB( 2 )  ONTO  P( NP+1 : 2*NP )

     CDVM$  REDISTRIBUTE  ( *, BLOCK )  ONTO  MB( 2 ) :: A2

     CDVM$  MAP MB( 3 )  ONTO  P( 2*NP+1 : 3*NP )

     CDVM$  REDISTRIBUTE  ( *, BLOCK )  ONTO  MB( 3 ) :: A3

                   .   .   .

                   DO  10  IT = 1, MAXIT

                   .   .   .

     CDVM$  PREFETCH  RS

     C            обмен границами смежных областей

                   .   .   .

     С            распределение вычислений (блоков операторов) по задачам

     CDVM$  TASK_REGION   MB

     CDVM$  ON   MB( 1 )

                        CALL JACOBY( A1, B1, M, N1+1 )

     CDVM$  END  ON

     CDVM$  ON  MB( 2 )

                        CALL JACOBY( A2, B2, M1+1, N2+1 )

     CDVM$  END  ON

     CDVM$  ON   MB( 3 )

                        CALL JACOBY( A3, B3, M2+1, N2+1 )

     CDVM$  END  ON

     CDVM$  END  TASK_REGION

     10           CONTINUE

7.7. Фрагмент динамической многообластной задачи

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

      С            NA - максимальное количество областей

                   PARAMETER ( NA=20 )

     CDVM$  PROCESSORS  P( NUMBER_OF_PROCESSORS( ) )

     С            размеры динамических массивов

                   INTEGER  SIZE( 2, NA )

                   TYPE GR_TYPE

                   REAL, POINTER, DIMENSION (:,:) :: A, B

     CDVM$  DISTRIBUTE  :: A

     CDVM$  ALIGN  :: B

     CDVM$  DYNAMIC  A,B

                   END TYPE GR_TYPE

                   TYPE (GR_TYPE) :: array(NA)

     CDVM$  TASK  TP ( NA )

                   .   .   .

                   NP = NUMBER_OF_PROCESSORS( )

     С            распределение массивов по задачам

     С            динамическое размещение массивов и выполнение отложенных директив

     С            DISTRIBUTE и ALIGN

                   IP = 1

                   DO  20  I = 1, NA

     CDVM$  MAP  TP( I )  ONTO  P( IP : IP+1 )

                   ALLOCATE (array(I)%A(SIZE(1, I), SIZE(2, I)))

     CDVM$  REDISTRIBUTE  ( *, BLOCK )  ONTO  TP( I )  :: array(I)%A

                   ALLOCATE (array(I)%B(SIZE(1, I), SIZE(2, I)))

     CDVM$  REALIGN  ( I1, I2 )  WITH  array(I)%A( I1, I2 ) :: array(I)%B

                   IP = IP + 2

                   IF( IP .GT. NP )  THEN  IP = 1

     20           CONTINUE

                   .   .   .

     С            распределение вычислений по задачам

     CDVM$  TASK_REGION   TP

     CDVM$  PARALLEL  ( I )  ON  TP( I )

                   DO 30  I = 1,NA

                        CALL JACOBY( array(I)%A, array(I)%B, SIZE(1, I), SIZE(2, I) )

     30           CONTINUE

     CDVM$  END  TASK_REGION

Массивы (области) циклически распределяются на секции из 2-х процессоров. Если NA > NP/2 , то на некоторые секции будет распределено несколько массивов. Витки циклов, распределенные на одну секцию, будут выполняться последовательно в модели параллелизма по данным.

8. Распределенные вычисления на размноженных массивах

8.1.  Параллельные циклы и размноженные массивы

Размноженным массивом будем называть массив, в котором каждое измерение локализовано (размножено) на каждом процессоре.

В языках системы DVM существуют два типа размноженных массивов: DVM‑массивы (т.е. массивы, специфицированные директивами распределения данных), в которых каждое измерение локализовано на каждом процессоре, и обычные массивы.

Гнездо параллельных циклов DVM можно разделить на два множества:

Ldis - распределенные циклы, которые отображены на распределенные измерения массива или шаблона

Lloc - локальные (последовательные) циклы, к которым относятся циклы, отображенные на локальные измерения, а также охватывающие и вложенные последовательные циклы.

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

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

Единственным исключением является обычный массив, который специфицирован опцией  NEW.

Поэтому для реализации распределенных вычислений на размноженных массивах необходимо произвести следующие преобразования:

Такая реализация не позволяет эффективно распараллеливать некоторые классы задач (например, интегральные вычисления). Поэтому необходимы директивы, которые более эффективно приводят массив в консистентное состояние.

8.2.  Приведение размноженного массива в консистентное состояние

Рассмотрим следующий фрагмент программы на языке FDVM.

Пример 8.1.

                   REAL  A(N,N,N)

     CDVM$ TEMPLATE TM( N )

     CDVM$  DISTRIBUTE  TM (BLOCK)

                   .   .   .

                   DO  10  K=1, N

     CDVM$  PARALLEL (J)  ON TM( f(J) )

                   DO  20  J=JL, JH

                   .   .   .

                   DO  30  I=1, N

                   .   .   .

                        A(I,J,K) = . . .

                   .   .   .

     30           CONTINUE

                   .   .   .

     20           CONTINUE

                   .   .   .

     10           CONTINUE

Пусть на процессоре P отображены ( в соответствии с TM ) следующий диапазон витков параллельного цикла JLP : JHP. После выполнения параллельного цикла на этом процессоре новые значения элементов массива будут вычислены в следующей секции

A( :, f(JLP) : f(JHP), K)

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

8.3.  Спецификация приведения в консистентное состояние

Для спецификации приведения в консистентное состояние, необходимо следующее расширение языка FDVM.

8.3.1.  Директива CONSISTENT

Синтаксис.

consistent-directive

is   CONSISTENT  array-name-list 

 8.3.2.  Опция CONSISTENT

Синтаксис.

consistent-clause

is   CONSISTENT 
      
([consistent-group-name : ] array-reference-list)

array-reference

is   array-name  ( regular-subscript-list )

regular-subscript

is   int-expr

 

or    do-variable-use

 

or    :

В опции CONSISTENT можно указывать только массивы, удовлетворяющие следующим требованиям:

Рассмотрим следующую ссылку на элемент размноженного массива в правой части оператора присваивания параллельного цикла

A(l1, …, ln)

где lj – индексное выражение по j-ому измерению. Если массив A удовлетворяет требованиям консистентности, то ссылка переносится в опцию CONSISTENT со следующим преобразованием индексных выражений:

индексное выражение заменяется знаком : (все измерение), если оно является функцией от индекса вложенного последовательного цикла, в противном случае индексное выражение не изменяется.

8.3.3.  Спецификация асинхронного выполнения приведения в консистентное состояние

Если в опции CONSISTENT отсутствует имя группы (consistent-group-name), то приведение в консистентное состояние автоматически выполняется после окончания параллельного цикла.

Для асинхронного выполнения необходимы следующие директивы.

consistent-group-directive

is   CONSISTENT_GROUP consistent-group-name-list

consistent-start-directive

is   CONSISTENT_START consistent-group-name

consistent-start-directive

is   CONSISTENT_WAIT consistent-group-name

Если в опции CONSISTENT указано имя группы, то ссылка на массив включается в группу, а выполнение откладывается до директивы CONSISTENT_START с этим именем группы.

Общие условия и ограничения асинхронного выполнения приведения в консистентное состояние аналогичны условиям асинхронного выполнения редукции.

8.4.  Параллелизм задач и распределенные вычисления на размноженных массивах

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

Т.к. единственным распределенным индексом является индекс (номер) задачи, то можно разрешить распределенное присваивание по индексу задачи. При этом номером задачи должно индексироваться одно и то же измерение размноженного массива во всех задачах. Остальные измерения должны индексироваться индексами последовательных циклов.

Если присваивание размноженному массиву удовлетворяет вышеуказанным требованиям, то его необходимо указать в опции CONSISTENT директивы TASK_REGION. В отличие от параллельного цикла ссылка на массив содержит только один параметр по некоторому измерению, который означает номер задачи. Все остальные измерения специфицируются знаком : (все измерение). Если в опции CONSISTENT не указано имя группы, то приведение в консистентное состояние выполняется автоматически после окончания задач (END TASK_REGION).

Если имя группы указано, то выполнение откладывается до директивы CONSISTENT_START.

9.  COMMON и EQUIVALENCE

Массивы, распределяемые по умолчанию, могут без ограничений использоваться в COMMON блоках и операторах EQUIVALENCE.

Массивы, распределяемые директивами DISTRIBUTE и ALIGN, не могут использоваться в операторах EQUIVALENCE. Кроме того, эти массивы не могут ассоциироваться с другими объектами данных. Явно распределяемые массивы могут быть компонентами COMMON блока при следующих условиях:

Пример 9.1. Явно распределяемый массив в COMMON блоке.

Описание в главной программе.

                   PROGRAM  MAIN

     CDVM$  DISTRIBUTE  B ( *, BLOCK )

                   COMMON /COM1/  X, Y(12), B(12,30)

Описание в подпрограмме. Ошибка: другое количество компонент.

                   SUBROUTINE  SUB1

      CDVM$  DISTRIBUTE  B1 ( *, BLOCK )

                   COMMON /COM1/  X, Y(12), Z, B1(12,30)

Описание в подпрограмме. Ошибка: другое распределение массива.

                   SUBROUTINE  SUB2

     CDVM$  DISTRIBUTE  B2 ( BLOCK, BLOCK )

                   COMMON /COM1/  X, Y(12), B2(12,30)

Описание в подпрограмме. Ошибка: другая конфигурация массива.

                   SUBROUTINE  SUB3

     CDVM$  DISTRIBUTE  B3 ( *, BLOCK )

                   COMMON /COM1/  X, Y(12), B(30,12)

Описание в подпрограмме. Нет ошибок.

                   SUBROUTINE  SUB4

     CDVM$  DISTRIBUTE  B4 ( *, BLOCK )

                   COMMON /COM1/  X, Y(12), B(12,30)

10.  Процедуры

1.    Вызов процедуры из параллельного цикла.

Процедура, вызываемая из параллельного цикла, не должна иметь побочных эффектов и содержать обменов между процессорами (прозрачная процедура). Как следствие этого, прозрачная процедура не содержит

2.   Вызов процедуры вне параллельного цикла.

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

3.   Формальные аргументы.

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

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

Наследуемое распределение описывается директивой

 

 

inherit-directive

is   INHERIT   dummy-array-name-list

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

Директивы REDISTRIBUTE и REALIGN могут применяться к формальным аргументам, если фактический и формальный аргументы имеют атрибут DYNAMIC.

4.   Локальные массивы.

Локальные массивы могут распределяться в процедуре директивами DISTRIBUTE и ALIGN. Локальный массив может быть выровнен на формальный аргумент. Директива DISTRIBUTE распределяет локальный массив на ту подсистему процессоров, на которой была вызвана процедура (текущая подсистема). Если в директиве DISTRIBUTE указана секция массива процессоров, то количество этих процессоров должно быть равно количеству процессоров текущей подсистемы. Количество процессоров текущей подсистемы определяется встроенной функцией ACTIVE_NUM_PROCS( ).

Особым случаем является распределенный локальный массив с атрибутом SAVE. Для этого массива должны выполняться следующие условия:

Пример 10.1. Распределение локальных массивов и формальных аргументов.

                   SUBROUTINE  DIST( A, B, C, N )

     CDVM$  PROCESSORS  PA ( ACTIVE_NUM_PROCS( ) )

                   DIMENSION  A(N,N), B(N,N), C(N,N), X(N,N), Y(N,N)

     C            явное распределение формального аргумента

      CDVM$  DISTRIBUTE  A ( *, BLOCK )

     C            выравниваемый формальный аргумент

     CDVM$  ALIGN  B( I, JWITH  A( I, J )

     C            наследуемое распределение формального аргумента

     CDVM$  INHERIT  C

     C            выравнивание локального массива на формальный аргумент

     CDVM$  ALIGN  X( I, J )  WITH  C( I, J )

     C            распределение локального массива

      CDVM$  DISTRIBUTE  Y ( *, BLOCKONTO  PA

                   .   .   .

                   END

11.  Ввод-вывод

Для организации ввода-вывода данных в FDVM программе используются операторы стандарта Фортран.

FDVM допускает только ограниченную форму операторов ввода-вывода для распределенных массивов:

Не разрешается использовать операторы ввода-вывода распределенных массивов в параллельном цикле и в блоке TASK_REGION.

На операторы ввода-вывода размноженных данных распространяются следующие ограничения:

(A(i1,i2,...,I), I = n1,n2)

при вводе размноженного массива неопределенного размера.

Оператор ввода, оператор INQUIRE, а также любой другой оператор ввода-вывода с управляющим параметром IOSTAT не должны использоваться в параллельном цикле.

Использование операторов ввода-вывода в задачах. Если каждая задача (on-block) использует собственные файлы, то для ввода-вывода действуют вышеуказанные ограничения. Если несколько задач используют один файл, то возникают дополнительные отличия от стандарта Фортрана. При работе с файлом последовательного доступа все задачи осуществляют ввод с начала файла, а при выводе записи разных задач размещаются в файле в непредсказуемом порядке.

Отметим, что FDVM программа, выполняющая бесформатный ввод-вывод распределенных массивов, в общем случае не совместима с последовательной программой на Фортране. Данные, записанные одной программой, не могут быть прочитаны другой, вследствие разницы длин записей.

12. Совместимость с HPF

Директивы распределения данных   базируются на следующих директивах HPF2: DISTRIBUTE, REDISTRIBUTE, ALIGN, REALIGN, PROCESSORS, TEMPLATE, DYNAMIC, SHADOW и INHERIT. Семантика и синтаксис директив имеют следующие ограничения:

Директивы распределения вычислений семантически являются подмножеством соответствующих директив HPF2. В частности директива PARALLEL является подмножеством директивы INDEPENDENT в HPF2.

Директивы спецификации удаленных данных не имеют аналогов в HPF2. , т.к. предполагается, что компилятор HPF2 автоматически определяет оптимальный доступ к удаленным данным.

Следовательно, множество директив FDVM может автоматически трансформироваться во множество директив HPF2.

13. Отличие версии FDVM 2.0 от версии FDVM 1.0

Версия FDVM 1.0 является подмножеством версии FDVM 2.0. Дополнительно определены следующие возможности:

14. Отличие версии FDVM 3.0 от версии FDVM 2.0

В отличие от версий 1.0 и 2.0, данная версия 3.0 базируется на языке Фортран 95, а не Фортран 77 [6].

Версия FDVM 2.0 является подмножеством версии FDVM 3.0. Дополнительно определены следующие возможности:

15. Ограничения на использование распределенных массивов в операторах Фортран 95

Распределенные массивы (т.е. массивы, специфицированные директивами распределения данных DISTRIBUTE, ALIGN или INHERIT) можно использовать в операторах присваивания массиву только двух видов:

секция-массива = скалярное-выражение

секция-массива = секция-массива

и только вне параллельного цикла.

Распределенный массив или его секцию нельзя использовать в качестве операнда операции над массивами, как то A(:,1) + B(:,L,N).

Распределенный массив целиком или его секция не может быть передана в качестве фактического параметра встроенной функции Фортран 95.

Распределенные массивы нельзя использовать в операторах FORALL.

Литература

1.    Message-Passing Interface Forum, Document for a Standard Message-Passing Interface, 1993. Version 1.0.

2.    OpenMP Consortium: OpenMP Fortran Application Program Interface, Version 1.0, October 1997.

3.    High Performance Fortran Forum. High Performance Fortran Language Specification. Version 1.0

4.    High Performance Fortran Forum. High Performance Fortran Language Specification. Version 2.0, January 31, 1997.

5.    ISO/IEC 1539-1:1997. Information technology - Programming Languages – Fotran - Part 1: Base Language.

6.    ISO/IEC 1539:1980.  Programming Language Fotran.

 


Fortran-DVM - оглавление Часть 1(1-4) Часть 2(5-6) Часть 3
(7-15)
Часть 4 (Приложения)