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

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

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

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

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

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

1. Описание массива задач (директива TASK).
2. Отображение массива задач на секции массива процессоров (директива MAP).
3. Распределение массивов по задачам (директива REDISTRIBUTE).
4. Распределение вычислений (блоков операторов или витков параллельного цикла) по задачам (конструкция TASK_REGION).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• нет зависимостей по данным;
• все используемые и вычисляемые данные размещены (локализованы) на секции массива процессоров данной задачи;
• задача может изменять только значения массивов, распределенных на эту секцию, значения редукционных переменных и значения NEW-переменных.
• После окончания задачи каждый массив должен иметь точно такое же распределение, какое существовало до запуска задачи. Если в задаче изменяется распределение массива, то оно должно быть восстановлено перед окончанием задачи.

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 R( NUMBER_OF_PROCESSORS( ) )
С              память для динамических массивов
                 REAL HEAP(100000)
С              размеры динамических массивов
                 INTEGER SIZE( 2, NA )
С              массивы указателей для А и В
CDVM$  REAL, POINTER ( :, : ) :: PA, PB, P1, P2
                 INTEGER P1, P2, PA(NA), PB(NA)
CDVM$  TASK PT ( NA )
CDVM$  ALIGN :: PB, P2
CDVM$  DISTRIBUTE :: PA, P1
                . . .
                 NP = NUMBER_OF_PROCESSORS( )
С              распределение массивов по задачам
С              динамическое размещение массивов и выполнение отложенных директив
С              DISTRIBUTE и ALIGN
                 IP = 1
                 DO 20 I = 1, NA
CDVM$  MAP PT( I ) ONTO R( IP : IP+1 )
                 PA(I) = ALLOCATE ( SIZE(1,I), HEAP )
                 P1 = PA(I)
CDVM$  REDISTRIBUTE ( *, BLOCK ) ONTO PT( I ) :: P1
                 PB(I) = ALLOCATE ( SIZE(1,I), HEAP )
                 P2 = PB(I)
CDVM$  REALIGN P2( I, J ) WITH P1( I, J )
                 IP = IP + 2
                 IF( IP .GT. NP ) THEN IP = 1
20            CONTINUE
                . . .
С               распределение вычислений по задачам
CDVM$  TASK_REGION PT
CDVM$  PARALLEL ( I ) ON PT( I )
                 DO 50 I = 1,NA
                       CALL JACOBY( HEAP(PA(I)), HEAP(PB(I)), SIZE(1, I), SIZE(2, I) )
50             CONTINUE
CDVM$  END TASK_REGION

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

8. COMMON и EQUIVALENCE

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

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

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

Пример 8.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)

9. Процедуры

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

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

• операторов ввода-вывода;
• директив FDVM;
• присваивание значений переменным COMMON блоков.

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

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

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

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

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

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

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

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

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

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

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

• Директива DISTRIBUTE или ALIGN имеет идентичные параметры при каждом вызове процедуры.
• Массив не может использоваться в директивах REDISTRIBUTE и REALIGN.

Пример 9.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, J ) WITH A( I, J )
C              наследуемое распределение формального аргумента
CDVM$  INHERIT C
C              выравнивание локального массива на формальный аргумент
CDVM$  ALIGN X( I, J ) WITH C( I, J )
C              распределение локального массива
CDVM$  DISTRIBUTE Y ( *, BLOCK ) ONTO PA
                . . .
                END

10. Ввод-вывод

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

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

• Список ввода-вывода должен состоять только из одного имени распределенного массива и не может содержать других объектов ввода-вывода.
• В операторах ввода-вывода по формату допускается только формат, задаваемый *.
• Список управляющей информации не должен содержать параметры ERR, ЕND и IOSTAT.
• В списке управляющей информации допускается использование только размноженных переменных.

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

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

• Список управляющей информации не должен содержать параметры ERR и ЕND.
• Допускается лишь следующая упрощенная форма списка с неявным циклом:
            (A(i1,i2,...,I), I = n1,n2)
• при вводе размноженного массива неопределенного размера.

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

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

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

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

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

• Директивы DISTRIBUTE и REDISTRIBUTE имеют только форматы распределения: BLOCK, GEN_BLOCK и *.
• В директивах ALIGN и REALIGN нет выравнивания по триплету.
• Для спецификации формальных аргументов возможны только две формы: явное распределение и наследуемое распределение.
• Не допускается использование оператора EQUIVALENCE для распределенных массивов.

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

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

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

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

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

• Модель динамических массивов. Эта модель может быть автоматически трансформирована для выполнения в языках F77, FDVM и HPF (раздел 4.2).
• Параллелизм задач (раздел 7).
• Форматы GEN_BLOCK и WGT_BLOCK для распределения массивов (разделы 4.1.2, 4.1.3).
• Распределение цикла с регулярной зависимостью по данным (раздел 6.2.3).
• Более точная спецификация удаленных данных, обеспечивающая эффективный доступ к ним (раздел 6.3).
• Совмещение счета и обмена данными (разделы 6.2.5, 6.3.3, 6.4.2).

Литература

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. ANSI X3.9-1978 Programming Language Fotran. New York 1978.