2. Обзор языка

3. Массивы виртуальных узлов. Директива NODES

4. Распределение данных

5. Распределение вычислений

6. Размноженные по узлам данные.

7. Cпецификация удаленных данных

8. Cинхронизация нитей на узле.

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

10. COMMON и EQUIVALENCE

11. Процедуры

12. Ввод-вывод

Литература

Приложение 1. Синтаксис директив языка Fortran Openmp-DVM

Приложение 2. Примеры программ

1.2. Модель параллелизма DVM

1.3. Модель параллелизма OpenMP

1.4. Гибридная модель

2.1. Модель программирования и модель параллелизма

2.2. Синтаксис директив Fortran OpenMP-DVM

2.3. Компиляция Fortran OpenMP-DVM программ

2.4. Условная компиляция

4.1. Директивы DISTRIBUTE и REDISTRIBUTE

4.3. Распределение через выравнивание

4.4. Директивы DYNAMIC и NEW_VALUE

4.5. Распределение по умолчанию

5.1. Неитеративные вычисления

5.2. Распределение витков цикла

7.1. Определение удаленных ссылок

7.2. Удаленные ссылки типа SHADOW

7.3. Удаленные ссылки типа REMOTE

8.1. Директива MASTER.

8.2. Директива BARRIER.

8.3. Директива CRITICAL.

8.4. Директива ATOMIC.

8.5. Директива FLUSH.

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

9.2. Отображение задач по узлам. Директива MAP

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

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

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

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

4.1.1. Формат BLOCK

4.1.2. Формат WGT_BLOCK

4.1.3. Формат MULT_BLOCK

4.1.4. Формат *

4.1.5. Многомерные распределения

4.3.1. Директивы ALIGN и REALIGN

4.3.2. Директива TEMPLATE

5.1.1 Параллельная область

5.1.2 Распределение работы между нитями на узле

5.2.1. Распределение витков цикла между узлами. Директива PARALLEL ON

5.2.2. Распределение витков цикла между нитями внутри узла. Директивы DO и PARALLEL DO

5.2.3. Распределение витков распределенного параллельного цикла между нитями.

5.2.4. Редукционные операции и переменные. Спецификация REDUCTION

6.1. Общие данные. Спецификация SHARED

6.2. Приватные данные. Спецификация PRIVATE

6.3. Приватные данные. Спецификация FIRSTPRIVATE

6.4. Приватные данные. Директива THREADPRIVATE. Спецификация COPYIN

6.5. Спецификация DEFAULT

6.6. Спецификация COPYPRIVATE

7.2.1. Спецификация массива с теневыми гранями

7.2.2. Спецификация независимых ссылок типа SHADOW для одного цикла

7.2.3. Вычисление значений в теневых гранях. Спецификация SHADOW_COMPUTE

7.2.4. Спецификация ACROSS зависимых ссылок типа SHADOW для одного цикла

7.3.1. Директива REMOTE_ACCESS

7.3.2. Синхронная спецификация удаленных ссылок типа REMOTE

7.3.4. Асинхронное копирование по ссылкам типа REMOTE

5.1.2.1. Директива SECTIONS

5.1.2.2. Директива SINGLE

5.1.2.3. Директива WORKSHARE

5.1.2.4. Программирование в нитях

7.3.4.1. Цикл и операторы копирования

7.3.4.2. Директивы асинхронного копирования

7.3.4.2.1. Директива ASYNCID

7.3.4.2.2. Директива F90

7.3.4.2.3. Директивы ASYNCHRONOUS и END ASYNCHRONOUS

7.3.4.2.4. Директива ASYNCWAIT

В настоящее время в области научно-технических расчетов превалируют три модели параллельного программирования: модель передачи сообщений (МПС), модель с общей памятью (МОП) и модель параллелизма по данным (МПД).

Модель передачи сообщений. В модели передачи сообщений каждый процесс имеет собственное локальное адресное пространство. Обработка общих данных и синхронизация осуществляется посредством передачи сообщений. Обобщение и стандартизация различных библиотек передачи сообщений привели к разработке стандарта MPI [1].

Модель с общей памятью. В модели с общей памятью процессы разделяют общее адресное пространство. Так как нет ограничений на использование общих данных, то программист должен явно специфицировать общие данные и упорядочивать доступ к ним с помощью средств синхронизации. В языках высокого уровня логически независимые нити (потоки) вычислений определяются на уровне функциональных задач или витков цикла. Обобщение и стандартизация моделей с общей памятью привели к созданию стандарта OpenMP [2].

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

По сравнению с двумя предыдущими моделями МПД имеет явные преимущества. Эта модель освобождает программиста от рутинной и трудоемкой работы по распределению глобальных массивов на локальные массивы процессов, по управлению передачей сообщений и синхронизации доступа к общим данным. Однако область применения этой модели является предметом исследований. Результаты этих исследований показывают, что эффективность многих алгоритмов научно-технических расчетов в модели МПД сравнима с эффективностью реализации в моделях МПС и МОП.

Первой попыткой стандартизации МПД для научно-технических расчетов явилась разработка HPF1 [3]. Стандартизация моделей МПС и МОП проводилась на базе обобщения большого опыта реализации и практического применения этих моделей. Стандарт HPF1 разрабатывался на базе теоретических исследований и 2-3 экспериментальных реализаций. Кроме этого, стандарт базировался на полной автоматизации распараллеливания вычислений и синхронизации работы с общими данными. Первые реализации HPF1 показали неэффективность стандарта для современных методов вычислений (в частности, для нерегулярных вычислений). В следующей версии стандарта HPF2 [4] сделан шаг в сторону «ручного» управления эффективностью параллельного выполнения. В частности, определены средства распределения вычислений и спецификации общих редукционных переменных.

Рис.1.1. Три модели параллельного программирования

DVM-система [6] предоставляет единый комплекс средств для разработки параллельных программ научно-технических расчетов на языках Си и Фортран 90.

Модель параллелизма DVM базируется на модели параллелизма по данным. Аббревиатура DVM отражает два названия модели: распределенная виртуальная память (Distributed Virtual Memory) и распределенная виртуальная машина (Distributed Virtual Mashine). Эти два названия указывают на адаптацию модели DVM как для систем с общей памятью, так и для систем с распределенной памятью. Высокоуровневая модель DVM позволяет не только снизить трудоемкость разработки параллельных программ, но и определяет единую формализованную базу для систем поддержки выполнения, отладки, оценки и прогноза производительности.

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

Единая модель параллелизма встроена в языки Си и Фортран 90 на базе конструкций, которые “невидимы” для стандартных компиляторов, что позволяет иметь один экземпляр программы для последовательного и параллельного выполнения.

Стандарт OpenMP[2], появившийся в октябре 1997 года, является обобщением низкоуровневых моделей параллелизма на общей памяти для языков Фортран 77, Фортран 90, Си и Си++. OpenMP встроен в языки программирования в виде директив, описывающих параллелизм программы.

При использовании OpenMP, программист разбивает программу с помощью соответствующих директив на последовательные и параллельные области. В начальный момент времени порождается "основная" нить, которая начинает выполнение программы со стартовой точки. Основная нить и только она исполняет все последовательные области программы. При входе в параллельную область, которая определяется с помощью директив PARALLEL и END PARALLEL, порождаются дополнительные нити, количество которых задается при помощи функций системы поддержки выполнения OpenMP-программ или при помощи переменных среды. Все нити исполняют один и тот же код, соответствующий параллельной области. При выходе из параллельной области основная нить дожидается завершения остальных нитей, и дальнейшее выполнение программы продолжает только она.

Если в параллельной секции встретился оператор цикла, то, согласно общему правилу, он будет выполнен всеми нитями, т.е. каждая нить выполнит все итерации данного цикла. Для распределения итераций цикла между различными нитями используется директива DO. Параллелизм на уровне независимых фрагментов оформляется в OpenMP с помощью директивы SECTION. Каждый из таких фрагментов будет выполнен какой-либо одной нитью. Если в параллельной секции какой-то участок кода должен быть выполнен лишь один раз (такая ситуация иногда возникает, например, при работе с общими переменными), то его нужно поставить между директивами SINGLE : END SINGLE. Такой участок кода будет выполнен нитью, первой дошедшей до данной точки программы.

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

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

В последнее время для вычислительных систем, сочетающих в себе одновременно характеристики архитектур, как с общей, так и с распределенной памятью, используется так называемая “гибридная” модель: OpenMP + MPI. При этом программа представляет собой систему взаимодействующих MPI-процессов, а каждый процесс программируется на OpenMP. Используя такую модель, можно добиться хорошей эффективности в том случае, когда в программе есть два уровня параллелизма - параллелизм между подзадачами и параллелизм внутри подзадачи (многоблочные методы). Использование OpenMP на мультипроцессорном узле для некоторых задач (например, вычислений на неструктурных сетках) может дать заметный выигрыш в эффективности. Основной недостаток – сложность написания таких программ. Программист должен знать и уметь использовать две разные модели параллелизма и разные инструментальные средства. Более того, прикладному программисту приходится описывать алгоритм не в терминах массива целиком (как это делается на последовательных компьютерах), а манипулировать локальными частями массива, размер которых зависит от числа используемых процессоров (узлов).

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

Язык Fortran OpenMP-DVM представляет собой язык Fortran 90, расширенный спецификациями параллелизма (OpenMP и DVM-спецификациями). Эти спецификации оформлены в виде специальных комментариев, которые называются директивами. Директивы “невидимы” для стандартных компиляторов, что позволяет иметь один экземпляр программы для последовательного и параллельного выполнения.

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

Рис.2.1. Модель параллелизма OpenMP Fortran DVM.

На каждом узле выполняется параллельная Fortran OpenMP программа. Распределение данных между узлами и доступ к удаленным данным выполняется по модели, аналогичной модели DVM[5].

Пользователь вначале определяет многомерный массив виртуальных узлов, на секции которого будут распределяться данные(см. раздел 4). При этом секция может варьироваться от полного массива узлов до отдельного узла. На каждую такую секцию могут быть отображены не только данные, но и независимые вычисления – задачи (см. раздел 9).

На следующем этапе определяются массивы, которые должны быть распределены между узлами (распределенные данные). Используя высокоуровневые директивы распределения данных (разделы 5), программист отображает массивы между узлами вычислительной системы. Остальные переменные (распределяемые по умолчанию) отображаются по одному экземпляру на каждый узел (размноженные по узлам данные). Размноженная по узлам переменная должна иметь одно и то же значение на каждом узле за исключением переменных в параллельных конструкциях (см. раздел 5.2.4, 6.2, 6.3 и 6.4).

Отобразив по узлам данные, пользователь тем самым отображает и вычисления по узлам. На каждом узле будут выполняться только те операторы присваивания, которые изменяют значения переменных, размещенных на данном узле. В свою очередь, на узле эти вычисления распределяются между нитями средствами OpenMP

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

В Fortran OpenMP-DVM программе можно описать следующие уровни параллелизма:

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

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

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

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

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

Параллелизм распределенных многомерных циклов реализуется распределением витков тесно-гнездового цикла между узлами (раздел 5). При этом каждый виток такого параллельного цикла полностью выполняется на одном узле одной нитью. Операторы вне параллельного цикла выполняются по правилу собственных вычислений (раздел 5.2).

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

Синтаксис директив Fortran OpenMP-DVM описывается следующей БНФ формой:

is по определению

or альтернатива

[ ] необязательная конструкция

[ ]… повторение конструкции 0 или более раз

x-list x [ , x ]…

Синтаксис директивы.

openmpdvm-directive	Is specification-directive
	Or executable-directive

specification-directive	Is dvm-nodes-directive
	Or dvm-align-directive
	Or dvm-distribute-directive
	Or dvm-template-directive
	Or dvm-shadow-directive
	Or dvm-dynamic-directive
	Or dvm-inherit-directive
	Or dvm-remote-group-directive
	Or dvm-task-directive
	Or dvm-asyncid-directive
	or omp-threadprivate-directive

executable-directive	is dvm-realign-directive
	or dvm-redistribute-directive
	or dvm-parallelon-directive
	or dvm-remote-access-directive
	or dvm-new-value-directive
	or dvm-prefetch-directive
	Or dvm-reset-directive
	Or dvm-map-directive
	Or dvm-f90-directive
	Or dvm-asynchronous-directive
	Or dvm-end-asynchronous-directive
	Or dvm-asyncwait-directive
	Or omp-parallel-directive
	Or omp-do-directive
	Or omp-sections-directive
	or omp-single-directive or omp-workshare-directive
	Or omp-paralleldo-directive
	Or omp-parallelsections-directive
	Or omp-parallelworkshare-directive

Замечение:

Директивы, обозначение которых начинается c префикса “dvm”(DVM-спецификации), взяты из языка Fortran-DVM [7], а директивы, начинающиеся с префикса “omp” (OpenMP-спецификации) - из OpenMP[2].

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

· Cпецкомментарий openmpdvm-directive подчиняется правилам написания комментария в фиксированной форме.

· Директивы спецификации должны находиться в разделе спецификаций.

· Исполняемые директивы должны находиться среди исполняемых операторов.

· Любое выражение, входящее в директиву спецификации, должно быть выражением спецификации.

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

CDVM$ ALIGN SPACE1( I, J, K )

CDVM$* WITH SPACE(J , K, I )

Программа, написанная на языке Fortran OpenMP-DVM, компилируется в два этапа.

На первом этапе используется компилятор Fortran OpenMP-DVM, который переводит эту программу в программу на языке Fortran OpenMP, с вызовами функций системы поддержки параллельного выполнения (библиотеки Lib-DVM[8]), основные функции которой:

1. Инициализация системы поддержки и завершение работы с ней.

2. Построение абстрактной машины.

3. Отображение абстрактной машины.

4. Создание и уничтожение распределенного массива.

5. Отображение распределенного массива по узлам.

6. Отображение параллельного цикла по узлам.

7. Отображение параллельных задач по узлам.

8. Выполнение редукционных операций.

9. Обновление теневых граней распределенных массивов.

10. Создание и загрузка буферов для доступа к удаленным данным.

11. Выполнение операций ввода-вывода.

Большинство операций библиотеки Lib-DVM является коллективными (например, создание распределенного массива и его перераспределение), и должны быть вызваны на всех узлах. Причем, на любом узле каждую операцию библиотеки Lib-DVM вызывает какая-то одна нить (разные операции могут вызываться разными нитями), а остальные нити должны ждать выполнения этой операции. Это обеспечивается с помощью монопольной секции SINGLE.

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

На втором этапе, полученная программа компилируется штатным Fortran компилятором, поддерживающим стандарт OpenMP, в режиме компиляции OpenMP спецификаций.

Спецификации параллелизма языка Fortran OpenMP-DVM оформляются как спецкомментарии и позволяют опустить любой из этапов компиляции. Опустив первый этап, можно получить программу, которая будет работать только на одном узле. Опустив второй - программу, которая будет работать на нескольких узлах, но при этом внутри узла распределения работы между нитями не будет. Опустив оба этапа – получим последовательную программу.

В стандарте OpenMP[2] предусмотрена возможность условной компиляции операторов OpenMP. Для этого могут использоваться спецсимволы комментария: “!$”, “*$” или “C$”.

Пример 2.1. Условная компиляция оператора.

!$ iam = omp_get_thread_num()

В данном случае, этот оператор будет выполняться в программе, только если включен режим OpenMP-компиляции этой программы.

В Fortran OpenMP-DVM программе необходимо все OpenMP-операторы (к таким операторам можно отнести: обращения к функциям системы поддержки OpenMP, объявление и использование различных переменных необходимых для работы нитей внутри узла и др.) оформлять, используя символы условной компиляции. Это дает возможность отделить в программе операторы, которые должны выполняться только на узле и не должны учитываться при распределении работы между узлами.

Директива NODES определяет один или несколько массивов виртуальных узлов.

Синтаксис.

dvm-nodes-directive	is CDVM$ NODES nodes-decl-list
nodes-decl	is nodes-name ( explicit-shape-spec-list )
explicit-shape-spec	is [ lower-bound : ] upper-bound
lower-bound	is int-expr
upper-bound	is int-expr

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

Разрешается использовать несколько массивов виртуальных узлов разной формы при следующем условии: количество узлов в каждом массиве должно быть равно значению встроенной функции NUMBER_OF_NODES ( ). Если два массива виртуальных узлов имеют одинаковую форму, то соответствующие элементы этих массивов ссылаются на один виртуальный узел.

Пример 3.1. Описание массивов виртуальных узлов.

CDVM$ NODES P( N )

CDVM$ NODES Q( NUMBER_OF_NODES( ) ),

CDVM$* R(2, NUMBER_OF_NODES( )/2)

Значение N должно быть равно значению функции NUMBER_OF_NODES ( ).

Массивы узлов являются локальными объектами процедуры. Массивы данных с атрибутами COMMON и SAVE могут быть отображены на локальные массивы виртуальных узлов при следующем условии: при каждом вызове процедуры локальный массив узлов имеет одно и то же определение.

В модели Fortran OpenMP-DVM все переменные можно разделить на два основных класса:

· распределенные, которые распределены между узлами, используя высокоуровневые директивы распределения данных, о которых пойдет речь далее, и

· размноженные по узлам, которые отображаются по одному экземпляру на каждый узел и имеют одно и то же значение на каждом узле за исключением переменных в параллельных конструкциях (5.1.4, 6.2, 6.3, 6.4)

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

Fortran OpenMP-DVM поддерживает распределение блоками (равными и неравными), наследуемое распределение, распределение динамических массивов и распределение через выравнивание.

Синтаксис.

dvm-distribute-directive	is CDVM$ dist-action distributee dist-directive-stuff
	or CDVM$ dist-action [ dist-directive-stuff ] :: distributee-list

Dist-action	Is DISTRIBUTE
	or REDISTRIBUTE

Dist-directive-stuff

Is dist-format-list [ dist-onto-clause ]

distributee	Is array-name
	or pointer-name

dist-format	Is BLOCK
	or WGT_BLOCK ( block-weight-array , nblock)
	or MULT_BLOCK ( block-size)
	or *

dist-onto-clause

Is ONTO dist-target

dist-target	Is nodes-name [(nodes-section-subscript-list )]

nodes-section-subscript	Is [ subscript ] : [ subscript ]

subscript	Is int-expr

nblock	Is int-expr

block-size	Is int-expr

block-weight-array	Is array-name

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

· Длина списка dist-format-list должна быть равна количеству измерений массива. Т.е. для каждого измерения должен быть задан формат распределения.

· Количество распределенных измерений массива (формат задан не *) должно быть равно количеству измерений dist-target.

· Массив block-weight-array в спецификации WGT_BLOCK, должен быть одномерным массивом типа DOUBLE PRECISION.

· Директива REDISTRIBUTE может применяться только к массивам со спецификацией DYNAMIC.

· Отсутствие dist-directive-stuff допустимо только в директиве DISTRIBUTE. В этом случае распределяемый массив может использоваться только после выполнения директивы REDISTRIBUTE.

В результате выполнения этой директивы, массив оказывается разбитым на прямоугольные блоки элементов – локальные части массива. Размер этих блоков статически не известен. Блок создается и размещается на узле системой поддержки OpenMP-DVM программ динамически. Массив заменяется «дескриптором локальной части массива», а обращения к его элементам выполняются специальным образом (с пересчетом глобальных индексов элемента в локальные индекс в блоке).

Спецификация ONTO указывает массив или секцию массива виртуальных узлов. Если спецификация ONTO не указана, то распределение осуществляется по базовому массиву виртуальных узлов, который является параметром запуска программы на выполнение. Когда директива REDISTRIBUTE без спецификации ONTO выполняется в ON‑блоке, то распределение осуществляется на секцию массива узлов этого ON‑блока (см. раздел 9).

Несколько одинаково распределяемых массивов (A1, A2,…) можно распределить одной директивой вида

CDVM$ DISTRIBUTE dist-directive-stuff :: A1, A2, …

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

Рассмотрим форматы распределения для одного измерения массива (одномерный массив A(N) ) и для одного измерения массива узлов (одномерный массив R(P) ). Многомерные распределения рассматриваются в разделе 4.1.5.

На каждом узле распределяется блок размером ë(N-1)/Pû +1 элементов. При некоторых соотношениях N и P несколько последних узлов могут не содержать значений элементов массива.

Пример 4.1. Распределение по формату BLOCK

		A	B	C
	R(1)	1	1	1
		2	2	2
CDVM$ NODES R( 4 )		3	3	3
			4

REAL A (12), B(13), C(11)	R(2)	4	5	4
		5	6	5
		6	7	6
CDVM$ DISTRIBUTE A (BLOCK) ONTO R			8

	R(3)	7	9	7
CDVM$ DISTRIBUTE (BLOCK) ONTO R :: B		8	10	8
		9	11	9
			12
CDVM$ DISTRIBUTE C (BLOCK)
	R(4)	10	13	10
		11		11
		12

Формат WGT_BLOCK определяет распределение блоками по их относительным “весам”.

Пусть задан формат WGT_BLOCK(WB, NBL).

Для 1£ i £ NBL, WB(i) определяет вес i‑ого блока. Блоки распределяются на P узлов с балансировкой сумм весов блоков на каждом узле. При этом должно выполняться условие

P £ NBL

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

Формат BLOCK является частным случаем формата WGT_BLOCK(WB,P), где WB(i) = 1 для 1£ i £ P и NBL = P.

Пример 4.3. Распределение блоками по весам.

CDVM$ NODES R( 4 )

DOUBLE PRECISION WB(12)

REAL A(12)

CDVM$ DISTRIBUTE A ( WGT_BLOCK( WB, 12 ) ) ONTO R

DATA WB / 2., 2.,1., 1., 1., 1., 1., 1., 1., 1., 2., 2. /

В примере 4.3 P = 4 и распределение идентично примеру 4.2.

В отличие от распределения неравными блоками, распределение по формату WGT_BLOCK можно выполнить для любого числа узлов в диапазоне 1 £ P £ NBL. Для данного примера размер массива узлов R может изменяться от 1 до 12.

Формат MULT_BLOCK(M) определяет распределение массива блоками кратными M.

Пример 4.4. Распределение блоками кратными заданному числу.

PARAMETER( NEL=2, N=8, NBL=N/NEL )

CDVM$ NODES R( 4 )

INTEGER A (N)

CDVM$ DISTRIBUTE A ( MULT_BLOCK(NEL) ) ONTO R

В данном случае, на каждый узел будут распределены по 2 элемента матрицы A.

Формат * означает, что измерение будет полностью локализовано на каждом узле (нераспределенное или локальное измерение).

При многомерных распределениях формат распределения указывается для каждого измерения. Между измерениями распределяемого массива и массива узлов устанавливается следующее соответствие.

Пусть массив узлов имеет n измерений. Пронумеруем измерения массива без формата * слева направо d₁, ..., d_k.. Тогда измерение d_i будет распределяться на i-ое измерение массива узлов. При этом должно выполняться условие k£n.

Пример 4.5. Одномерное распределение.

Пример 4.6. Двумерное распределение.

CDVM$ NODES R2( 2, 2 )	Блоки A		Узлы
REAL A(100,100)				1	2
CDVM$ DISTRIBUTE A (BLOCK,BLOCK)	1	2	1	1	2
CDVM$* ONTO R2	3	4	2	3	4

Выравнивание массива А на распределенный массив В ставит в соответствие каждому элементу массива А элемент или секцию массива В. При распределении массива В одновременно будет распределяться массив А. Если на данный узел распределен элемент В, то на этот же узел будет распределен элемент массива А, поставленный в соответствие выравниванием.

Метод распределения через выравнивание выполняет следующие две функции.

1) Одинаковое распределение массивов одной формы на один массив узлов не всегда гарантирует, что соответствующие элементы будут размещены на одном узле. Это вынуждает специфицировать удаленный доступ (см. Раздел 7.) там, где его возможно нет. Гарантию размещения на одном узле дает только выравнивание соответствующих элементов массивов.

2) На один массив может быть выровнено несколько массивов. Изменение распределения одного массива директивой REDISTRIBUTE вызовет соответствующее изменение распределения группы массивов.

Выравнивание массива описывается следующими директивами:

dvm-align-directive	is CDVM$ align-action alignee align-directive-stuff
	or CDVM$ align-action [ align-directive-stuff ] :: alignee‑list
align-action	Is ALIGN
	or REALIGN

align-directive-stuff	is ( align-source-list ) align-with-clause

Alignee	is array-name

align-source	is *
	or align-dummy

align-dummy

is scalar-int-variable

align-with-clause	is WITH align-spec

align-spec	is align-target ( align-subscript-list )

align-target	is array-name
	or template-name
	or pointer-name

align-subscript	is int-expr
	or align-dummy-use
	or *

align-dummy-use

is [ primary-expr * ] align‑dummy [ add-op primary-expr ]

primary-expr	is int-constant
	or int-variable
	or ( int-expr )

add-op	is +
	or -

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

· Длина списка align-source-list должна быть равна количеству измерений выравниваемого массива.

· Длина списка align-subscript-list должна быть равна количеству измерений базового массива align-target.

· Директива REALIGN может применяться только к массивам со спецификацией DYNAMIC.

· Отсутствие align-directive-stuff допустимо только в директиве ALIGN. В этом случае распределяемый массив может использоваться только после выполнения директивы REALIGN.

Пусть задано выравнивание двух массивов с помощью директивы

CDVM$ ALIGN A(d₁,…,d_n) WITH B(ard₁,…,ard_m)

где d_i - спецификация i-го измерения выравниваемого массива А,

ard_j - спецификация j-го измерения базового массива В,

Если d_i задано целочисленной переменной I , то обязательно должно существовать одно и только одно измерение массива В , специфицированное линейной функцией ard_j = a*I + b. Следовательно, количество измерений массива А, специфицированных идентификаторами (align-dummy) должно быть равно количеству измерений массива В, специфицированных линейной функцией.

Пусть i-ое измерение массива А имеет границы LA_i : HA_i , а j-ое измерение массива В, специфицированное линейной функцией a*I + b , имеет границы LB_j : HB_jТ.к. параметр I определен над множеством значений LA_i : HA_i , то должны выполняться следующие условия

a*LA_i + b ³ LB_j, а* HA_i + b £ HB_j

Если d_i= * , то i-ое измерение массива А будет локальным на каждом узле при любом распределении массива В (аналог локального измерения в директиве DISTRIBUTE ).

Если ard_i= * , то массив А будет размножен по j-му измерению массива В (аналог частичного размножения по массиву узлов).

Если ard_i= int-expr, то массив А выравнивается на секцию массива В.

Пример 4.8. Выравнивание массивов

REAL A(10), B(10,10), C(22,22), D(20), E(20), F(10), G(20), H(10,10)

CDVM$ DISTRIBUTE B ( BLOCK , BLOCK )

CDVM$ DISTRIBUTE D ( BLOCK )

C выравнивание на секцию массива (вектор на первую строку матрицы А)

CDVM$ ALIGN A( I ) WITH B( 1, I )

С размножение вектора - выравнивание на каждую строку

CDVM$ ALIGN F( I ) WITH B( *, I )

С сжатие матрицы - столбец матрицы соответствует элементу вектора

CDVM$ ALIGN C( *, I ) WITH D( I )

С выравнивание вектора на вектор с раздвижкой

CDVM$ ALIGN E( I ) WITH D( 2*I )

С выравнивание вектора на вектор с реверсом

CDVM$ ALIGN G( I ) WITH D( -I + 21)

С выравнивание матрицы на матрицу с поворотом и раздвижкой

CDVM$ ALIGN H( I, J ) WITH C( 2*J, 2*I )

Несколько массивов (A1, A2,…) можно выровнять одинаковым образом на один и тот же массив B одной директивой вида

CDVM$ ALIGN (d₁,…,d_n) WITH B(ard₁,…,ard_m) :: A1, A2, …

При этом массивы A1, A2… должны иметь одинаковое число измерений (n), но необязательно одинаковые размеры измерений.

Пусть задана цепочка выравниваний A f1 B f2 C, где f2 - выравнивание массива В на массив С , а f1 - выравнивание массива А на массив В. По определению массивы А и В считаются выровненными на массив С. Массив В выровнен непосредственно функцией f2, а массив А выровнен опосредовано составной функцией f1(f2). Поэтому применение директивы REALIGN к массиву В не вызовет перераспределения массива А.

В общем случае множество спецификаций ALIGN образует лес деревьев. При этом корень каждого дерева должен быть распределен директивами DISTRIBUTE или REDISTRIBUTE. При выполнении директивы REDISTRIBUTE перераспределяется все дерево выравниваний.

Если значения линейной функции a*I + b выходят за пределы измерения базового массива, то необходимо определить фиктивный массив - шаблон выравнивания следующей директивой:

dvm-template-directive

is CDVM$ TEMPLATE template-decl-list

template-decl

is template-name [ ( explicit-shape-spec-list ) ]

Затем необходимо произвести выравнивание обоих массивов на этот шаблон. Шаблон распределяется с помощью директив DISTRIBUTE и REDISTRIBUTE. Элементы шаблона не требуют памяти, они указывают узел, на который должны быть распределены элементы выровненных массивов.

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

Пример 4.9. Выравнивание по шаблону.

REAL A(100), B(100), C(100)

CDVM$ TEMPLATE TABC (102)

CDVM$ ALIGN B( I ) WITH TABC( I )

CDVM$ ALIGN A( I ) WITH TABC( I + 1 )

CDVM$ ALIGN C( I ) WITH TABC( I + 2 )

CDVM$ DISTRIBUTE TABC ( BLOCK )

. . .

DO 10 I = 2, 98

A(I) = C(I-1) + B(I+1)

10 CONTINUE

Для того, чтобы не было обмена между узлами необходимо разместить элементы A(I), C(I-1) и B(I+1) на одном узле. Выравнивание массивов С и В на массив А невозможно, т.к. функции выравнивания I-1 и I+1 выводят за пределы индексов измерения А. Поэтому описывается шаблон TABC. На один элемент шаблона TABC выравниваются элементы массивов A, В и С, которые должны быть размещены на одном узле.

Массивы, перераспределяемые директивами REDISTRIBUTE и REALIGN, необходимо специфицировать в директиве DYNAMIC.

dvm-dynamic-directive	is CDVM$ DYNAMIC alignee-or-distributee-list

alignee-or-distributee	is alignee
	or distribute

Если после выполнения директив REDISTRIBUTE и REALIGN перераспределяемые массивы получают новые значения, то перед этими директивами следует указать дополнительную (оптимизирующую) директиву NEW_VALUE.

dvm-new-value-directive

is CDVM$ NEW_VALUE

Эта директива отменяет пересылку значений распределенного массива.

Если массив указан в спецификации DYNAMIC и для него нет спецификации DISTRIBUTE или ALIGN , то его распределение откладывается до первого оператора REDISTRIBUTE или REALIGN. Такая необходимость возникает в двух случаях:

· распределение (выравнивание) динамического массива с указателем, который является элементом массива указателей;

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

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

Таким образом, в памяти узла будет размещен не весь массив, а только один блок его (или ничего).

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

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

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

IF p THEN lh = rh

где p – логическое выражение,

lh – левая часть оператора присваивания (ссылка на скаляр или элемент массива),

rh – правая часть оператора присваивания (выражение).

Тогда этот оператор будет выполняться на узле, где распределены данные со ссылкой lh (узел own( lh )). Все данные в выражениях p и rh должны быть размещены на узле own( lh ). Если какие-либо данные из выражений p и rh отсутствуют на узле own( lh ), то их необходимо указать в директиве удаленного доступа (см. 7.1.) перед этим оператором.

Если lh является ссылкой на распределенный массив А и существует зависимость по данным между rh и lh, то распределенный массив необходимо размножить по узлам с помощью директивы

REDISTRIBUTE А( *,...,* ) или REALIGN А( *,...,* )

перед выполнением оператора.

Пример 5.1. Оператор собственных вычислений.

PARAMETER (N = 100)

REAL A(N, N+1), X(N)

CDVM$ ALIGN X( I ) WITH A( I, N+1)

CDVM$ DISTRIBUTE ( BLOCK, * ) :: A

. . .

С оператор собственных вычислений

С левая и правая части – на одном узле

X(N) = A(N,N+1) / A(N,N)

DO 10 J = N-1, 1, -1

...

C собственные вычисления в последовательном цикле

X(J) = A(J,N+1) / A(J,J)

10 CONTINUE

Отметим, что A(J,N+1) и A(J,J) локализованы на том узле, где размещается X(J).

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

Выполнение операторов на узле может быть распределено между нитями при помощи средств OpenMP.

В начальный момент времени порождается "основная" нить, которая начинает выполнение программы на узле со стартовой точки. Основная нить и только она исполняет все последовательные области программы. При помощи OpenMP-директивы PARALLEL[2 раздел 2.4], создаются нити, между которыми и может распределяться вся работа на узле.

Omp-parallel–directive

Is !$OMP PARALLEL

[[ ,] ompreduction-clause]

[[ ,] ompshared-clause]

[[ ,] ompdefault-clause]

[[ ,] ompprivate-clause]

[[ ,] ompfirstprivate-clause]

[[ ,] ompcopyin-clause]

[[ ,] ompif-clause]

[[ ,] ompnumthreads-clause]

block

!$OMP END PARALLEL

Директива PARALLEL определяет параллельную область. Блок кода внутри этой области будет выполняться всеми нитями параллельно. Количество нитей, которые будут выполнять этот блок, задается или с помощи переменных окружения, или с помощью вызова функции системы поддержки (см. [2]), или с помощью ompnumthreads-clause:

Ompnumthreads–clause

Is NUM_THREADS (int-expr)

Если условие в клаузе ompif-clause равно .FALSE., то область будет выполнена одной главной нитью:

Ompif–clause

is IF(logical-expr)

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

ompshared-clause раздел 6.1

ompprivate-clause раздел 6.2

ompfirstprivate-clause раздел 6.3

ompcopyin-clause раздел 6.4

ompdefault-clause раздел 6.5

ompreduction-clause раздел 5.2.4

В OpenMP [2 в разделе 2.5] определены следующие директивы, которые могут быть использованы для распределения работы между нитями:

· директива распределения витков цикла DO(см. раздел 5.2.2),

· директива распределения неитеративных вычислений SECTIONS,

· директива SINGLE,

· и директива WORKSHARE.

Параллелизм на уровне независимых фрагментов в OpenMP оформляется с помощью директивы SECTIONS:

Omp-sections-directive	Is !$OMP SECTIONS [section-clause-list] [omp-section-directive] block [omp-section-directive block] … !$OMP END SECTIONS [NOWAIT]

Omp-section-directive	Is !$OMP SECTION

Section-clause	Is ompprivate-clause Or ompfirstprivate-clause Or ompreduction-clause

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

ompprivate-clause раздел 6.2

ompfirstprivate-clause раздел 6.3

ompreduction-clause раздел 5.2.4

Директива SECTIONS определяет независимые блоки кода, отделяемые друг от друга при помощи спецификации SECTION, которые могут выполняться одновременно. Каждый такой блок будет выполнен какой-либо одной нитью.

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

В разделе 2.1 определен порядок вложенности уровней параллелизма в Fortran OpenMP-DVM программе. Согласно этого порядка, распределенные параллельные циклы (см. раздел 5.2) не могут использоваться внутри директивы SECTIONS.

Пример 5.2. Использование спецификации SECTIONS.

PARAMETER (N = 100)

REAL A(N, N), B(N, N), X

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

CDVM$ DISTRIBUTE ( BLOCK, BLOCK ) :: A

. . .

С начало параллельной области

С массивы A и B – распределены между узлами, переменная X – общая

C$OMP PARALLEL, SHARED ( A, B, X )

. . .

C$OMP SECTIONS

C$DVM REMOTE_ACCESS ( B ( 100, 100 ) )

С пересылка значения В(100,100) в буфер узла own(A(1,1)

A ( 1, 1 ) = B ( 100, 100 )

C$OMP SECTION

C$DVM REMOTE_ACCESS ( B ( 50, 50 ) )

С пересылка значения В(50,50) в буфер всех узлов

X = B ( 50, 50 )

C$OMP END SECTIONS

. . .

C$OMP END PARALLEL

В данном примере с помощью директивы SECTIONS описаны два програмных блока, которые информационно независимы друг от друга (модификация переменной X и модификация элемента массива A(1,1)). Для модификации переменных требуются удаленные данные(см. раздел 7.1). Применение спецификации SECTIONS дает возможность выполнить эти модификации одновременно разными нитями, причем обмены, необходимые для закачки удаленных данных будут также запущены одновренно.

Omp-single-directive	Is !$OMP SINGLE[single-clause-list] block !$OMP END SINGLE [end-single-clause-list]

single-clause	Is ompprivate-clause Or ompfirstprivate-clause

End-single-clause	Is ompcopyprivate-clause

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

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

ompprivate-clause раздел 6.2

ompfirstprivate-clause раздел 6.3

ompcopyprivate-clause раздел 6.6

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

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

Пример 5.3. Работа с распределенным массивом внутри параллельной области.

PARAMETER (N = 100)

REAL A(N, N), B(N, N), X

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

CDVM$ DISTRIBUTE ( BLOCK, BLOCK ) :: A

. . .

С начало параллельной области

С массивы A и B – распределены между узлами, переменная X – общая

C$OMP PARALLEL, SHARED ( A, B, X )

. . .

C$OMP SINGLE

C$DVM REMOTE_ACCESS ( B ( 100, 100 ) )

С пересылка значения В(100,100) в буфер узла own(A(1,1)

A ( 1, 1 ) = B ( 100, 100 )

C$OMP END SINGLE

. . .

C$OMP SINGLE

C$DVM REMOTE_ACCESS ( B ( 50, 50 ) )

С пересылка значения В(50,50) в буфер всех узлов

X = B ( 50, 50 )

C$OMP END SINGLE

. . .

C$OMP END PARALLEL

В данном примере директива SINGLE используется для модификации общей переменной X и элементов распределенного массива A. Для выполнения этих операторов требуются удаленные данные (элементы B(100, 100) и B(50,50)), и если бы каждая нить на узле занималась пересылкой удаленных данных (см. раздел 7.3), то это привело бы к лишним коммуникациям. Такую пересылку и модификацию данных на узле достаточно выполнить лишь один раз одной из нитей.

Omp-workshare-directive

Is !$OMP WORKSHARE

block

!$OMP END WORKSHARE [NOWAIT]

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

Внутри блока WORKSHARE разрешается использовать только следующие конструкции [2 раздел 2.5.4]:

· операторы присваивания для скаляров и элементов массивов,

· операторы присваивания секций массивов,

· операторы FORALL,

· операторы WHERE,

· директиву ATOMIC,

· конструкции CRITICAL,

· и конструкции PARALLEL.

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

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

Существующие в стандарте OpenMP функции системы поддержки позволяют распределять работу между нитями на самом низком уровне. Например, используя функции OMP_GET_NUM_THREADS и OMP_GET_THREAD_NUM, возвращающих соответственно общее количество созданных нитей и номер нити:

Пример 5.4. Программирование в нитях.

IF( OMP_GET_THREAD_NUM() .EQ. 1 ) THEN

ELSE

ENDIF

В данном случае, в зависимости от номера нити, будет выполняться разный код. Нить с номером 1 выполнит block1, а все остальные нити выполнят блок кода block2.

В программе на языке Fortran OpenMP-DVM запрещается такое низкоуровневое распределение работы между нитями. Как уже говорилось (в разделе 2.3), все обращения к функциям системы поддержки Lib-DVM, которые генерируются при компиляции программы, оформляются внутри секций SINGLE/END SINGLE, поэтому, например, если внутри block1, осуществляется работа с распределенным массивом, то добавление внутри block1 секции SINGLE с обращениями к функциям системы подержки приведет к тому, что программа перестанет работать (поскольку по окончании секции SINGLE осуществляется барьерная синхронизация всех нитей, а данный блок не будет выполняться всемя нитями).

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

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

Эту спецификацию разрешается использовать только для циклов, которые удовлетворяют следующим условиям:

· цикл является тесно-гнездовым циклом с прямоугольным индексным пространством; (исключение цикл с ACROSS – раздел 7.2.4)

· распределенные измерения массивов индексируются только регулярными выражениями типа a*I + b , где I - индекс цикла;

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

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

· левая часть оператора присваивания является ссылкой на распределенный массив, редукционную переменную, приватную переменную;

· нет операторов ввода-вывода и dvm-директив в теле цикла.

Цикл, удовлетворяющий этим условиям, будем называть распределенным параллельным циклом. Управляющая переменная последовательного цикла, охватывающего распределенный параллельный цикл или вложенного в него, может индексировать только локальные (размноженные) измерения распределенных массивов.

Распределенный параллельный цикл специфицируется следующей директивой:

dvm-parallel-on-directive

Is CDVM$ PARALLEL ( do-variable-list )

ON iteration-align-spec

[ , ompprivate-clause] [ , ompreduction-clause]

[ , ompfirstprivate-clause] [ , shadow-renew-clause]

[ , shadow-compute-clause][ , remote-access-clause ]

[ , across-clause ]

Iteration-align-spec

Is align-target ( iteration-align-subscript-list )

Iteration-align-subscript	Is int-expr
	Or do-variable-use
	Or *

do-variable-use	Is [ primary-expr * ] do-variable [ add-op primary-expr ]

Замечание

Данная директива взята из языка Fortran DVM[7] с небольшими изменениями: изменен формат описания редукционных и приватных переменных.

Директива PARALLEL ON размещается перед заголовком цикла и распределяет витки циклов в соответствии с распределением массива или шаблона. Семантика директивы аналогична семантике директивы ALIGN, где индексное пространство выравниваемого массива заменяется индексным пространством цикла. Индексы циклов в списке do-variable-list перечисляются в том порядке, в котором размещены соответствующие операторы DO в тесно-гнездовом цикле.

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

ompprivate-clause раздел 6.2

ompfirstprivate-clause раздел 6.3

ompreduction-clause раздел 5.2.4

shadow-renew-clause раздел 7.2.2

shadow-compute-clause раздел 7.2.3

across-clause раздел 7.2.4

remote-access-clause раздел 7.3.1

Пример 5.5. Распределение витков параллельного цикла с регулярными вычислениями.

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

CDVM$ ALIGN ( I, J ) WITH B( I, J+1 ) :: A, C, D

CDVM$ DISTRIBUTE B ( BLOCK , BLOCK )

. . .

CDVM$ PARALLEL ( I, J ) ON B( I, J+1 )

DO 10 I = 1, N

DO 10 J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

10 CONTINUE

Цикл удовлетворяет всем условиям распределенного параллельного цикла. В частности, левые части операторов присваивания одного витка цикла A(I,J) и B(I,J+1) размещаются на одном узле через выравнивание массивов А и В.

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

Пример 5.6. Разделение цикла

	*CDVM$ PARALLEL ( I ) ON A( 2I )**
DO 10 I = 1, N	DO 10 I = 1, N
A(2*I) = . . .	10 A(2*I) = . . .
B(3*I) = . . .	*CDVM$ PARALLEL ( I) ON B( 3I )**
10 CONTINUE	DO 11 I = 1, N
	11 B(3*I) = . . .

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

Если в параллельной области (определяемой парой директив PARALLEL/END PARALLEL) встретился оператор цикла, то, согласно общему правилу, он будет выполнен всеми нитями, т.е. каждая нить выполнит все итерации данного цикла. Для распределения итераций цикла между различными нитями используется директива DO:

Omp-do–directive

is !$OMP DO

[[ ,] ompschedule-clause]

[[ ,] ompreduction-clause]

[[ ,] ompprivate-clause]

[[ ,] ompfirstprivate-clause]

do-loop

[!$OMP END DO [NOWAIT]]

Замечание

В стандарте OpenMP[2] описаны и другие дополнительные спецификации у директивы DO, однако использовать их в Fortran OpenMP-DVM программе не разрешается. Например, спецификация ORDERED. Ее реализация затруднена тем, что необходимо не только синхронизовать нити внутри узла, но также и нити, расположенные на разных узлах, что в общем случае является довольно сложной задачей.

Данная директива распределяет витки цикла между нитями в соответствии с ompschedule-клаузой:

ompschedule–clause

is SCHEDULE (schedule-expr)

где

schedule-expr

is STATIC [, int-expr]

or DYNAMIC [, int-expr]

or GUIDED[, int-expr]

or RUNTIME

Если задана спецификация STATIC, то витки цикла распределяются между нитями статически блоками заданного размера. Если задана спецификация DYNAMIC- динамически блоками заданного размера (каждая нить берет на выполнение первый еще невзятый блок итераций). Если задана спецификация GUIDED, то размер блока итераций уменьшается экспоненциально до заданной величины. При наличии спецификации RUNTIME способ распределения итераций по нитям выбирается во время выполнения.

Замечание.

Спецификация SCHEDULE действует только внутри узла и никаким образом не влияет на распределение витков цикла между узлами.

По окончании выполнения витков цикла осуществляется барьерная синхронизация нитей, если не указана спецификация NOWAIT.

Синтаксис и семантика ompnumthreads-clause и ompif-clause описана в разделе 5.

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

ompshared-clause раздел 6.1

ompprivate-clause раздел 6.2

ompfirstprivate-clause раздел 6.3

ompreduction-clause раздел 5.2.4

Пример 5.7. Распределение витков цикла.

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

!$OMP PARALLEL SHARED (A, B, D, C)

! . . .

!$OMP DO PRIVATE (I,J)

DO 10 I = 1, N

DO 10 J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

10 CONTINUE

Если параллельная область состоит только из одного цикла, то такой цикл можно описать при помощи следующей директивы PARALLEL DO:

Omp-paralleldo–directive

Is !$OMP PARALLEL DO

[[ ,] ompschedule-clause]

[[ ,] ompreduction-clause]

[[ ,] ompdefault-clause]

[[ ,] ompshared-clause]

[[ ,] ompprivate-clause]

[[ ,] ompfirstprivate-clause]

[[ ,] ompcopyin-clause]

[[ ,] ompif-clause]

[[ ,] ompnumthreads-clause]

do-loop

[!$OMP END PARALLEL DO]

Пример 5.8. Распределение витков цикла c помощью объединенной директивы.

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

! . . .

!$OMP PARALLEL DO PRIVATE (I,J) SHARED (A, B, C, D)

DO 10 I = 1, N

DO 10 J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

10 CONTINUE

Витки распределенного параллельного цикла, специфицированного при помощи директивы PARALLEL ON, можно распределить между нитями, при помощи директив DO или PARALLEL DO.

Пример 5.9. Распределение витков распределенного цикла между нитями

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

CDVM$ ALIGN ( I, J ) WITH B( I, J+1 ) :: A, C, D

CDVM$ DISTRIBUTE B ( BLOCK , BLOCK )

. . .

CDVM$ PARALLEL ( I, J ) ON B( I, J+1 )

!$OMP DO

DO I = 1, N

DO J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

ENDDO

!$OMP ENDDO

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

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

· Внутри распределенных параллельных циклов запрещается использовать конструкцию NOWAIT.

· В разделе 2.1 определен порядок вложенности уровней параллелизма в Fortran OpenMP-DVM программе. Согласно этого порядка, распределенные параллельные циклы не могут использоваться внутри OpenMP конструкций разделения работы. Поэтому, например, такая ситуация некорректна:

Пример 5.10. Ошибка. Нарушен порядок вложенности уровней параллелизма.

REAL A(N, N)

CDVM$ DISTRIBUTE B ( BLOCK , *)

. . .

!$OMP PARALLEL DO PRIVATE ( I, J ) SHARED ( A )

DO J = 1, N

CDVM$ PARALLEL ( I ) ON B( I, * )

DO I = 1, N

B(I,J) = 1.0

ENDDO

В стандарте OpenMP допускаются вложенные параллельные области. Если внутри параллельной области, встретилась директива PARALLEL, то создается новая группа нитей, между которыми в дальнейшем и будет распределяться работа, а нить, выполнившая эту директиву, становится “основной” нитью этой группы. Количество создаваемых нитей зависит от реализации компилятора, в настоящее время компиляторы OpenMP, как правило, не поддерживают вложенный параллелизм – все вложенные параллельные области выполняются одной нитью. Если вложенный параллелизм поддерживается, то количество создаваемых нитей может быть задано или с помощи переменных окружения, или с помощью функции системы поддержки (см. [2]), или с помощью спецификации ompnumthreads-clause.

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

Пример 5.11. Распределение витков распределенного цикла между нитями. Вложенный OpenMP – параллелизм.

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

CDVM$ ALIGN ( I, J ) WITH B( I, J+1 ) :: A, C, D

CDVM$ DISTRIBUTE B ( BLOCK , BLOCK )

. . .

CDVM$ PARALLEL ( I, J ) ON B( I, J+1 )

!$OMP DO

DO I = 1, N

!$OMP PARALLEL DO

DO J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

ENDDO

!$OMP END PARALLEL DO

ENDDO

!$OMP ENDDO

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

Очень часто в программе встречаются циклы, в которых выполняются редукционные операции - в некоторой переменной суммируются элементы массива или вычисляется максимальное (минимальное) значение. Витки таких циклов можно распределять, если указать спецификацию REDUCTION.

ompreduction-clause

is REDUCTION (reduction-op-name : reduction-variable-list)

reduction-variable	is array-name
	or scalar-variable-name
reduction-op-name	is +
	or *
	or MAX
	or MIN
	or .AND.
	or .OR.
	or .EQV.
	or .NEQV.

Замечание

В языке Fortran DVM[7] допускаются и другие редукционные операции, например MAXLOC и MINLOC, однако данные операции не поддерживаются в OpenMP, поэтому эти операции не включены в язык Fortran OpenMP-DVM

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

Введем следующие обозначения

rv	- редукционная переменная
er	- выражение, не содержащее rv
I_k	- целая переменная
op	- одна из следующих операций языка Фортран: +, -, .OR., .AND., .EQV., .NEQV.
ol	- одна из следующих операций языка Фортран: .GE., .GT., .LE., .LT.
f	- функция max или min

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

1) rv = rv op er

rv = er op rv

2) rv = f( rv, er )

rv = f( er, rv )

3) if( rv ol er ) rv = er

if( er ol rv ) rv = er

Пример 5.12. Спецификация редукции.

S = 0

X = -1.

CDVM$ PARALLEL ( I ) ON A( I ), REDUCTION (+:S), REDUCTION (MAX:X)

C$OMP DO REDUCTION (+:S) REDUCTION (MAX:X)

DO 10 I = 1, N

S = S + A(I)

X = MAX(X, A(I))

10 CONTINUE

Замечание

В данном примере спецификация REDUCTION используется и в DVM, и в OpenMP-спецификации параллелизма. Информация о редукционных переменных дублируется, но это дает возможность скомпилировать эту программу и как OpenMP, и как DVM (см. раздел 2.3). Если опустить какую-то одну спецификацию REDUCTION, то программа станет работать неверно.

Вычисление значения редукционной операции, происходит в два этапа:

1) На первом этапе на каждом узле вычисляется локальное значение редукции для той части данных, которые распределены на данном узле (для этого используется соответствующая OpenMP-редукционная операция).

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

Как уже говорилось, в модели Fortran OpenMP-DVM все переменные можно разделить на два основных класса:

· распределенные, которые распределены между узлами, используя высокоуровневые директивы распределения данных (см. раздел 4), и

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

В свою очередь размноженные по узлам данные внутри параллельной области можно разделить на:

· общие - под именем A все нити видят одну переменную и

· приватные - под именем A каждая нить видит свою переменную.

По умолчанию, все COMMON-блоки, а также переменные, порожденные вне параллельной области, при входе в эту область остаются общими. Исключение составляют переменные - счетчики итераций в цикле. Переменные, порожденные внутри параллельной области, являются приватными.

Ompshared–clause

is SHARED (list)

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

ompprivate–clause

is PRIVATE (list)

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

ompfirstprivate–clause

is FIRSTPRIVATE (list)

Семантика данной спецификации совпадает с PRIVATE-спецификацией. Отличием является то, что все созданные объекты для приватных переменных будут инициализированы значениями этих переменных до начала параллельной области.

ompthreadprivate-directive

is C$OMP THREADPRIVATE (list)

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

Для того чтобы приватные копии COMMON-блоков, которые помечены как THREADPRIVATE, при входе в параллельную область были проинициализированы оригинальными значениями, используется следующая директива:

ompcopyin–clause

is COPYIN(list)

ompdefault–clause

Is DEFAULT (PRIVATE)

or DEFAULT (SHARED)

or DEFAULT (NONE)

Данная спецификация позволяет задать: являются ли все переменные внутри параллельной области общими или приватными. Спецификация NONE требует, чтобы для каждой переменной, используемой внутри параллельной области, была явно задана спецификафия PRIVATE, FIRSTPRIVATE или SHARED.

ompcopyprivate-clause

Is COPYPRIVATE(list)

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

Удаленными данными будем называть данные, размещенные на одном узле и используемые на другом узле. Фактически эти данные являются разделяемыми данными для этих узлов. Ссылки на такие данные будем называть удаленными ссылками. Рассмотрим обобщенный оператор

IF (…A(inda)…) B(indb) = …C(indc)…

где A, B, C - распределенные массивы,

inda, indb, indc - индексные выражения.

В модели Fortran OpenMP-DVM этот оператор будет выполняться на узле own(B(indb)), т.е. на том узле, где размещен элемент B(indb). Ссылка A(inda) и C(indc) не являются удаленными ссылками, если соответствующие им элементы массивов A и C размещены на узле own(B(indb)). Единственной гарантией этого является выравнивание A(inda), B(indb) и C(indc) в одну точку шаблона выравнивания. Если выравнивание невозможно или невыполнено, то ссылки A(inda) и/или C(indc) необходимо специфицировать как удаленные ссылки. В случае многомерных массивов данное правило применяется к каждому распределенному измерению.

По степени эффективности обработки удаленные ссылки разделены на два типа: SHADOW и REMOTE.

Если массивы B и C выровнены и

inda = indc ± d ( d – положительная целочисленная константа),

то удаленная ссылка C(indc) принадлежит типу SHADOW. Удаленная ссылка на многомерный массив принадлежит типу SHADOW, если распределяемые измерения удовлетворяют определению типа SHADOW.

Удаленные ссылки, не принадлежащие типу SHADOW, составляют множество ссылок типа REMOTE.

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

Удаленная ссылка типа SHADOW означает, что обработка удаленных данных будет происходить через “теневые” грани. Теневая грань представляет собой буфер, который является непрерывным продолжением локальной секции массива в памяти узла (см. рис.7.1.).Рассмотрим оператор

A( i ) = B( i + d2) + B( i – d1)

где d1, d2 – целые положительные константы. Если обе ссылки на массив B являются удаленными ссылками типа SHADOW, то массив B необходимо специфицировать в директиве SHADOW как B( d1 : d2 ), где d1 – ширина левой грани, а d2 – ширина правой грани. Для многомерных массивов необходимо специфицировать грани по каждому измерению. При спецификации теневых граней указывается максимальная ширина по всем удаленным ссылкам типа SHADOW.

Синтаксис директивы SHADOW.

dvm-shadow-directive	is CDVM$ SHADOW dist-array ( shadow-edge-list )
	or CDVM$ SHADOW ( shadow-edge-list ) :: dist-array-list

dist-array	is array-name
	or pointer-name

shadow-edge	is width
	or low-width : high-width

Width

is int-expr

low-width

is int-expr

High-width

is int-expr

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

· Размер левой теневой грани (low-width) и размер правой теневой грани (high-width) должны быть целыми константными выражениями, значения которых больше или равны 0.

Задание размера теневых граней как width эквивалентно заданию width : width.

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

Синхронная спецификация является частью директивы ON:

Shadow-renew-clause

is SHADOW_RENEW ( renewee‑list )

Renewee

is dist-array-name [ ( shadow-edge-list ) ] [ (CORNER) ]

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

· Размер теневых граней, заполняемых значениями, не должен превышать максимального размера, описанного в директиве SHADOW.

· Если размеры теневых граней не указаны, то используются максимальные размеры.

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

Пример 7.1. Спецификация SHADOW-ссылок без угловых элементов.

REAL A(100), B(100)

CDVM$ ALIGN B( I ) WITH A( I )

CDVM$ DISTRIBUTE ( BLOCK) :: A

CDVM$ SHADOW B( 1:2 )

. . .

CDVM$ PARALLEL ( I ) ON A ( I ), SHADOW_RENEW ( B )

C$OMP PARALLEL DO

DO 10 I = 2, 98

A(I) = (B(I-1) + B(I+1) + B(I+2) ) / 3

10 CONTINUE

При обновлении значений в теневых гранях используются максимальные размеры 1:2 , заданные в директиве SHADOW.

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

Рис.7.1. Распределение массива с теневыми гранями.

На каждом узле распределяются два буфера, которые являются непрерывным продолжением локальной секции массива. Левая теневая грань имеет размер в 1 элемент (для B(I-1)), правая теневая грань имеет размер в 2 элемента (для B(I+1) и B(I+2)). Если перед выполнением цикла произвести обмен между узлами по схеме на рис.7.1., то цикл может выполняться на каждом узле без замены ссылок на массивы ссылками на буфер.

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

Пример 7.2. Спецификация SHADOW-ссылок с угловыми элементами.

REAL A(100,100), B(100,100)

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

CDVM$ DISTRIBUTE A ( BLOCK,BLOCK)

. . .

CDVM$ PARALLEL ( I, J ) ON A ( I, J ), SHADOW_RENEW ( B (CORNER))

C$OMP PARALLEL DO

DO 10 I = 2, 99

DO 10 J = 2, 99

A(I,J) = (B(I,J+1) + B(I+1,J) + B(I+1,J+1) ) / 3

10 CONTINUE

Теневые грани для массива В распределяются по умолчанию размером в 1 элемент по каждому измерению. Т.к. имеется удаленная "угловая" ссылка B(I+1,J+1) , то указывается параметр CORNER.

Рис. 7.2. Схема локальной секции массива с теневыми гранями.

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

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

shadow-compute-clause

is SHADOW_COMPUTE

Рассмотрим некоторый распределенный параллельный цикл

CDVM$ PARALLEL (i₁,i₂ ,…,i_k) ON A(f₁,f₂ ,…,f_k)

где A – идентификатор массива, в соответствии с которым распределяются витки цикла.

Пусть

{LH} - множество ссылок на распределенные массивы в левых частях операторов присваивания цикла;

{RH} - множество ссылок на распределенные массивы в правых частях (выражениях) операторов присваивания цикла.

Для применения спецификации SHADOW_COMPUTE необходимо выполнение следующих условий:

1) ширина теневых граней распределенных измерений массивов из множеств {LH} и {RH} должна быть не меньше ширины теневых граней соответствующих измерений массива A;

2) теневые грани массивов из множества {RH} должны содержать значения, соответствующие значениям массивов.

Во время выполнения цикла значения в теневых гранях массивов из множества {LH} обновляются. Ширина обновленной части каждой теневой грани равна ширине соответствующей теневой грани массива A.

Пример 7.3. Спецификация SHADOW_COMPUTE.

CDVM$ DISTRIBUTE (BLOCK) :: A, B, C, D

CDVM$ SHADOW A(1:2)

CDVM$ SHADOW B(2:2)

CDVM$ PARALLEL ( I ) ON C( I ), SHADOW_COMPUTE,

CDVM$* SHADOW_RENEW( A, B )

C$OMP PARALLEL DO

DO 10 I = 1, N

C( I ) = A( I ) + B( I )

D( I ) = A( I ) - B( I )

10 CONTINUE

Так как по умолчанию ширина теневых граней для массивов C и D равна 1, то условие 1) удовлетворяется. Выполнение спецификации SHADOW_RENEW удовлетворяет условие 2).

Рассмотрим следующий цикл

DO J = 2, N-1

DO I = 2, N-1

A(I,J) = (A(I,J-1) + A(I,J+1) + A(I-1,J) + A(I+1,J)) / 4

ENDDO

Между витками цикла с индексами i1 и i2 ( i1<i2 ) существует зависимость по данным (информационная связь) массива A, если оба эти витка осуществляют обращение к одному элементу массива по схеме запись‑чтение или чтение‑запись.

Если виток i1 записывает значение, а виток i2 читает это значение, то между этими витками существует потоковая зависимость или просто зависимость i1® i2.

Если виток i1 читает “старое” значение, а виток i2 записывает “новое” значение, то между этими витками существует обратная зависимость i1¬ i2.

В обоих случаях виток i2 может выполняться только после витка i1.

Значение i2 - i1 называется диапазоном или длиной зависимости. Если для любого витка i существует зависимый виток i + d (d - константа), тогда зависимость называется регулярной или зависимостью с постоянной длиной.

Пусть массив A не распределен между узлами. Тогда такой цикл с регулярными вычислениями можно распараллелить, используя средства OpenMP:

Пример 7.4. Спецификация цикла с регулярной зависимостью по данным для нераспределенного массива.

!$OMP PARALLEL, PRIVATE ( IAM, J, I, J1)

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

!$ OMP_GET_NUM_THREADS ( ) – количество нитей

!$ подробное описание функций системы поддержки можно найти в [2]

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS ( ) - 1

!$ J = J1 – IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

Рассмотрим более подробно, как работает данный алгоритм. Все витки цикла по J выполняются всеми нитями, а витки цикла по I распределяются между ними при помощи директивы omp-do-directive. В начальный момент времени начинает работать нить с номером 0 (нить0). Для нее значение J равно 2 и условие внутри цикла не выполняется. Нить0 вычисляет свою часть витков цикла по I. Все остальные нити (для них условие выполнено), дожидаются пока нить0 посчитает свою часть массива A для J=2. Далее работают нить0 и нить1: нить0 вычисляет свою порцию витков цикла по I для J = 3, а нить1 - для J = 2. И так далее, последняя нить включится в работу через NUMT - 1 шагов.

Пусть теперь массив A является распределенным между узлами. Тогда помимо синхронизации между нитями внутри узла, необходимо организовать выполнение витков данного цикла на узлах таким образом, чтобы для витков цикла с индексами i1 и i2 (i1<i2) виток i2 выполнялся бы только после витка i1 (витки i2 и i1 могут выполняться на разных узлах). Такой цикл с регулярными вычислениями, в котором существуют регулярные зависимости по распределенным массивам, можно распределять, указав спецификацию ACROSS после директивы PARALLEL ON.

across-clause

is ACROSS ( dependent-array-list )

dependent-array

is dist-array-name ( dependence-list ) [(section-spec-list)]

Dependence	is flow-dep-length : anti-dep-length

Flow-dep-length	is int-constant

Anti-dep-length	is int-constant

section-spec	is SECTION ( section-subscript-list )

В спецификации ACROSS перечисляются все распределенные массивы, по которым существует регулярная зависимость по данным. Для каждого измерения массива указывается длина прямой зависимости (flow-dep-length) и длина обратной зависимости (anti-dep-length). Нулевое значение длины зависимости означает отсутствие зависимости по данным.

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

· В каждой ссылке на массив может существовать зависимость по данным только по одному распределенному измерению. Например, разрешены ссылки A(I-1,J), A(I,J+1), но запрещены ссылки A(I‑1,J+1), A(I+1,J-1).

· Для организации в узле конвейерного выполнения допускается только алгоритм, описанный в примере 7.4. Все конструкции, используемые для синхронизации нитей внутри узла, должны быть описаны при помощи спецсимволов условной компиляции (см. раздел 2.4).

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

Пример 7.5. Спецификация цикла с регулярной зависимостью по данным для распределенного массива.

!$OMP PARALLEL, PRIVATE ( IAM, NUMT, J, I, J1)

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 ))

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

По каждому измерению массива А существует прямая и обратная зависимость длиной 1.

Замечание

В данном алгоритме используется функция OMP_GET_NUM_THREADS, которая возвращает количество нитей внутри параллельной области. При компиляции данной программы, компилятор Fortran OpenMP-DVM не генерирует обращение к данной функции на каждой J1-ой итерации цикла. Вычисление данной фунции выносится за пределы цикла и выполняется один раз. В данном случае, использование этой функции помогает компилятору определить “настоящие” границы цикла (от 2 до N-1).

Спецификация ACROSS реализуется через теневые грани. Длина обратной зависимости определяет ширину обновления правой грани, а длина прямой зависимости – ширину обновления левой грани. Обновление значений правых граней производится перед выполнением цикла (как для директивы SHADOW_RENEW). Обновление левых граней производится во время выполнения цикла по мере вычисления значений удаленных данных. Фактически, ACROSS-ссылки являются подмножеством SHADOW–ссылок, между которыми существует зависимость по данным.

Эффективность параллельного выполнения цикла ACROSS

Измерение массива, по которому существует зависимость по данным, будем называть рекуррентным измерением.

Степень эффективности параллельного выполнения цикла ACROSS зависит от количества распределенных рекуррентных измерений.

Одномерный массив. Для одномерного распределенного массива с рекуррентным измерением возможно только последовательное выполнение (см. рис. 7.3).

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

1) существует хотя бы одно не рекуррентное измерение. Массив и цикл распределяются только по этому измерению. Цикл выполняется как обычный параллельный цикл без спецификации ACROSS.

Пример 7.6. Распараллеливание по не рекуррентному измерению.

CDVM$ DISTRIBUTE A( BLOCK, * )

CDVM$ PARALLEL ( I ) ON A( I, * )

C$OMP PARALLEL DO

DO 30 I = 1,N1

DO 30 J = 2,N2-1

30 A(I,J) = A(I,J-1) + A(I,J+1)

Отметим, что этот способ может быть не самым эффективным, если N1 значительно меньше N2 и количества процессоров (недостаточный параллелизм)

2) Распределено только одно рекуррентное измерение. Остальные измерения локализованы на каждом узле. Между узлами система поддержки организует конвейерное распараллеливание (см. рис.7.4). При этом размер ступени конвейера автоматически определяется на каждой ЭВМ, в зависимости от времени выполнения цикла и времени передачи данных при обновлении теневых граней.

Пример 7.7. Конвейерное распараллеливание.

CDVM$ DISTRIBUTE A( BLOCK, * )

!$OMP PARALLEL, PRIVATE ( IAM, NUMT, J, I, J1)

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

!$ NUMT = OMP_GET_NUM_THREADS ( )

С NUMT – количество нитей

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 ))

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

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

· Директива PARALLEL ON специфицирует как минимум два заголовка цикла. Один цикл специфицирует распределенное рекуррентное измерение, другой цикл специфицирует локальное измерение массива.

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

3) Существует m>1 распределенных рекуррентных измерений. Массив виртуальных узлов содержит также m измерений. Между узлами система поддержки автоматически организует параллельное выполнение по гиперплоскостям массива узлов. Каждая гиперплоскость имеет m-1 измерение.

Пример 7.8. Распараллеливание по гиперплоскостям.

CDVM$ DISTRIBUTE A( BLOCK, BLOCK )

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 ))

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

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

Рис.7.3. Последовательное выполнение

Рис.7.4. Конвейерное выполнение

Рис.7.5. Распараллеливание по гиперплоскостям

решетки виртуальных узлов.

Удаленные ссылки типа REMOTE специфицируются директивой REMOTE_ACCESS.

dvm-remote-access-directive	is CDVM$ REMOTE_ACCESS ( [ remote-group-name : ] regular-reference-list )

regular-reference	is dist-array-name [( regular-subscript-list )]

regular-subscript	is int-expr
	or do-variable-use
	or :

remote-access-clause	is remote-access-directive

Директива REMOTE_ACCESS может быть отдельной директивой (область действия - следующий оператор) или дополнительной спецификацией в директиве PARALLEL ON (область действия – тело параллельного цикла).

Если удаленная ссылка задается как имя массива без списка индексов, то все ссылки на этот массив в параллельном цикле (операторе) являются удаленными ссылками типа REMOTE.

Рассмотрим удаленную ссылку на многомерный распределенный массив

A( ind₁, ind₂,…,ind_k )

Пусть ind_j – индексное выражение по j-ому измерению.

В директиве REMOTE_ACCESS индексное выражение указывается без изменений, если

· j-ое измерение является распределенным измерением,

· ind_j = a * i + b, где a и b не изменяются в процессе выполнения цикла (инварианты).

Во всех остальных случаях в директиве REMOTE_ACCESS вместо ind_j указывается “:” (все измерение).

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

Пример 7.9. Синхронная спецификация удаленных ссылок типа REMOTE.

DIMENSION A(100,100), B(100,100)

CDVM$ DISTRIBUTE (*,BLOCK) :: A

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

. . .

С начало параллельной области

С массивы A и B – распределены между узлами, переменная X – общая

C$OMP PARALLEL, SHARED ( A, B, X )

. . .

C$OMP SINGLE

CDVM$ REMOTE_ACCESS ( A(50,50) )

С замена ссылки A(50,50) ссылкой на буфер

С рассылка значения A(50,50) по всем узлам

X = A(50,50)

C$OMP END SINGLE

. . .

C$OMP SINGLE

CDVM$ REMOTE_ACCESS ( B(100,100) )

С пересылка значения В(100,100) в буфер узла own(A(1,1)

A(1,1) = B(100,100)

C$OMP END SINGLE

. . .

CDVM$ PARALLEL (I, J ) ON A(I,J) , REMOTE_ACCESS ( B(:,N) )

С рассылка значений B(:,N) по узлам own(A(:,J))

C$OMP DO

DO 10 I = 1, 100

DO 10 J = 1, 100

10 A(I,J) = B(I,J) + B(I,N)

C$OMP ENDDO

. . .

C$OMP END PARALLEL

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

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

Рассмотрим следующий цикл

DO 10 I₁ = L₁,H₁,S₁

. . .

DO 10 I_n = L_n,H_n,S_n

10A(f₁,…,f_k) = B (g₁,…,g_m)

где A, B - идентификаторы разных распределенных массивов.

L_i,H_i,S_i– инварианты цикла

f_i = a_i *I_i + b_i

g_j = c_j *I_j + d_j

a_i, b_i, c_j, d_j – целые выражения, инварианты цикла (выражения, значения которых не изменяются в процессе выполнения цикла).

Каждая переменная цикла I_l может быть использована не более чем в одном выражении f_i и не более чем в одном выражении g_j.

Цикл может содержать несколько операторов, удовлетворяющих вышеуказанным ограничениям. Такой цикл будем называть циклом копирования (copy-loop).

Цикл копирования может быть описан одним или несколькими операторами копирования (copy-statement) следующего вида

A(a₁,…,a_k) = B(b₁,…,b_m)

где

a_i = l_i : h_i : s_i

b_j = l_j : h_j : s_j

a_i, b_j - являются триплетами языка Фортран 90.

Оператор копирования является аналогом оператора присваивания секций массивов Фортран 90.

Для триплетов существуют правила сокращенной записи. Определим эти правила на примере триплета a_i.

1) Если в копировании участвует все измерение массива, то

a_i = :

2) Если s_i = 1, то

a_i = l_i : h_i

3) Если L_i = h_i , то

a_i = l_i

Для цикла копирования 10 выражения триплетов определяются следующим образом

Для a_i Для b_j

l_i = a_i *L_i + b_il_j = c_j *L_j + d_j

h_i = a_i *H_i + b_ih_j = c_j *H_j + d_j

s_i = a_i *S_is_j = c_j *S_j

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

REAL A(N1,N2,N3), B(N1,N3)

DO 10 I1 = 1, N1

DO 10 I2 = 2, N3-1

10 A(I1, 5, I2+1) = B(I1, I2-1)

Этому циклу соответствует следующий оператор копирования

A( :, 5, 3:N3 ) = B( :, 1:N3-2 )

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

Асинхронное копирование определяется комбинацией директивы начала копирования (ASYNCHRONOUS ID) и директивой ожидания окончания копирования (ASYNCWAIT ID). Соответствие директив определяется одним идентификатором ID.

Директива ASYNCID описывает отдельный идентификатор для каждой пары директив асинхронного копирования.

Синтаксис директивы:

dvm-asyncid-directive

is CDVM$ ASYNCID async-name-list

Директива F90 является префиксом для каждого оператора копирования.

Синтаксис.

dvm-F90-directive	is CDVM$ F90 copy-statement

Copy-statement	is array-section = array-section

array-section	is array-name [( section-subscript-list )]

section-subscript	is subscript
	or subscript-triplet

subscript-triplet	is [ subscript ] : [ subscript ] [ : stride]

Subscript	is int-expr

Stride	is int-expr

Директивы ASYNCHRONOUS и END ASYNCHRONOUS задают блочную конструкцию.

Синтаксис.

Dvm-asynchronous-construct	is dvm-asynchronous-directive
	f90-directive [ f90-directive ] … copy-loop [ copy-loop ] …
	dvm-end-asynchronous-directive

dvm-asynchronous-directive	is CDVM$ ASYNCHRONOUS async-name

dvm-end-asynchronous-directive	is CDVM$ END ASYNCHRONOUS

Все операторы присваивания в циклах копирования (copy-loop) должны быть описаны директивами F90 с соответствующим оператором копирования.

Синтаксис.

dvm-asyncwait-directive

is CDVM$ ASYNCWAIT async-name

Пример из раздела 7.3.4.1 можно специфицировать как асинхронное копирование следующим образом.

CDVM$ ASYNCID TR

REAL A(N1,N2,N3), B(N1,N3)

. . .

CDVM$ ASYNCHRONOUS TR

CDVM$ F90 A( :, 5, 3:N3 ) = B( :, 1:N3-2 )

DO 10 I1 = 1, N1

DO 10 I2 = 2, N3-1

10 A(I1, 5, I2+1) = B(I1, I2-1)

CDVM$ END ASYNCHRONOUS

. . .

последовательность операторов,

которая выполняется на фоне передачи данных

. . .

CDVM$ ASYNCWAIT TR

В состав OpenMP[2] включены следующие синхронизационные конструкции, которые также можно использовать и в программе на Fortran OpenMP-DVM:

omp-master-directive

Is !$OMP MASTER

block

!$OMP END MASTER

Блок кода, расположенный внутри спецификации MASTER/END MASTER будет выполнен только одной “основной” нитью. Все остальные нити группы не дожидаются, пока основная нить выполнит свою работу.

Пример 8.1. Модификация общих данных внутри параллельной области.

DIMENSION A(100,100), B(100,100)

CDVM$ DISTRIBUTE (*,BLOCK) :: A

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

C$OMP PARALLEL

...

C$OMP MASTER

CDVM$ REMOTE_ACCESS ( B(100,100) )

С пересылка значения В(1,1) в буфер узла own(A(100,100)

A(100,100) = B(1,1)

C$OMP END MASTER

C$OMP BARRIER

CDVM$ PARALLEL ( J, I ) ON B( I, J )

C$OMP DO PRIVATE (J, I)

DO J = 1, 100

DO I = 1, 100

B(I,J) = A(I,J)

ENDDO

...

C$OMP END PARALLEL

Замечание.

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

Omp-barrier-directive

Is !$OMP BARRIER

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

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

Omp-critical-directive

Is !$OMP CRITICAL[(name)]

block

!$OMP END CRITICAL[(name)]

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

Пример 8.1. Редукция в цикле с регулярной зависимостью. Директива CRITICAL

…

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 )),

CDVM$ * REDUCTION (MAX: EPS)

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

S = A( I, J )

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

S = ABS (S - A( I, J ))

!$OMP CRITICAL

IF (EPS .LT. S) EPS = S

!$OMP END CRITICAL

ENDDO

!$OMP ENDDO

ENDDO

В данном примере мы не можем использовать для вычисления редукционной операции внутри узла спецификацию REDUCTION, которая может использоваться или в описании параллельного цикла DO, или в описании параллельной области. Определение параллельной области (директива PARALLEL) в данном примере отсутствует (вообще говоря, оно может находиться, например, в другом модуле – стандарт OpenMP это допускает). Внешний цикл не распределяется между нитями. Поэтому для вычисления редукции, необходимо использовать критическую секцию.

Замечание.

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

Omp-atomic-directive

Is !$OMP ATOMIC

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

Информацию о том, перед какими операторами можно использовать директиву ATOMIC, можно найти в [2] (раздел 2.7.4)

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

Пример 8.2. Редукция в цикле с регулярной зависимостью. Директива ATOMIC

…

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 )),

CDVM$ * REDUCTION (MAX: EPS)

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

S = A( I, J )

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

S = ABS (S - A( I, J ))

!$OMP ATOMIC

EPS = MAX ( EPS, ABS( S - A( I, J )))

ENDDO

!$OMP ENDDO

ENDDO

Замечание.

Рекомендуется вместо директивы CRITICAL, там где есть возможность, использовать директиву ATOMIC. Атомарное выполнение оператора может быть более эффективным, поскольку могут существовать аппаратные механизмы, поддерживающие атомарное выполнение оператора, которые и могут быть задействованы компилятором OpenMP.

Omp-flush-directive

Is !$OMP FLUSH[(list)]

Данная директива определяет точку в программе, в которой память для всех нитей приводится в консистентное состяние. Более подробную информацию о директиве FLUSH, можно найти в [2] (раздел 2.7.5)

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

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

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

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

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

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

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

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

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

dvm-task-directive	is CDVM$ TASK task-list

Task	is task-name ( max-task )

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

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

dvm-map-directive	is CDVM$ MAP task-name ( task-index )
	ONTO nodes-name( nodes-section-subscript-list)

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

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

dist-target	is . . .
	or task-name ( task-index )

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

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

dvm-block-task-region	is dvm-task-region-directive
	on-block
	[ on-block ]...
	dvm-end-task-region-directive

Dvm-task-region-directive	is CDVM$ TASK_REGION task-name [ , ompreduction-clause ]

dvm-end-task-region-directive	is CDVM$ END TASK_REGION



on-block	is dvm-on-directive
	Block
	end-on-directive

dvm-on-directive	is CDVM$ ON task-name ( task-index ) [ , ompprivate-clause ] [ , ompfirstprivate-clause ]

end-on-directive	is CDVM$ END ON

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

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

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 CDVM$ PARALLEL ( do-variable ) ON task-name ( do-variable ) [ , ompfirstprivate-clause ] [ , ompprivate-clause ]

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

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

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

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

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

· нет зависимостей по данным;

· все используемые и вычисляемые данные размещены (локализованы) на секции массива узлов данной задачи;

· задача может изменять только значения массивов, распределенных на эту секцию, значения редукционных переменных и значения приватных переменных (перечисленных в спецификациях ompprivate и ompfirstprivate-clause).

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

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

CDVM$ NODES P( NUMBER_OF_NODES( ) )

С массивы 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

. . .

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

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

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

NP = NUMBER_OF_NODES( ) / 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$ 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

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

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

· COMMON блок должен быть описан в главной программной единице.

· Каждое описание COMMON блока должно иметь одно и то же количество компонент, а соответствующие компоненты - последовательности памяти одинакового размера.

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

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

1. Вызов процедуры из параллельной области.

Процедура может быть вызвана как и из параллельной области, так и из блока SINGLE/ END SINGLE, который находится внутри параллельной области или, например, блока MASTER/END MASTER., или секции SECTION. В OpenMP нет возможности определить откуда вызывалась процедура.

Если внутри процедуры осуществляется работа с распределенными массивами, то от того откуда вызывалась процедура зависит код, генерируемый компилятором Fortran OpenMP-DVM внутри процедуры.

Если процедура вызывается из параллельной области, то все обращения внутри процедуры к системе поддержки LibDVM генерируются компилятором из блока SINGLE/END SINGLE.

Если процедура вызывается из блока SINGLE/END SINGLE, то добавление внутри процедуры блока SINGLE/END SINGLE, приведет к тому, что программа перестанет работать (в OpenMP запрещены вложенные конструкции распределения работы).

Поскольку эти две ситуации отличить друг от друга очень тяжело (для этого потребуется делать межпроцедурный анализ программы), в Fortran OpenMP-DVM введена дополнительная директива, которая позволяет существенно упростить компилятор и управляет тем, как генерировать обращения к системе поддержки внутри процедуры:

from-one-thread- directive

Is CDVM$ FROM ONE THREAD

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

Замечание.

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

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

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

· операторов ввода-вывода;

· директив Fortran-DVM;

· присваивание значений переменным COMMON блоков.

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

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

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

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

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

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


inherit-directive	is INHERIT dummy-array-name-list

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

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

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

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

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

· Директива DISTRIBUTE или ALIGN имеет идентичные параметры при каждом вызове процедуры.

· Массив не может использоваться в директивах REDISTRIBUTE и REALIGN.

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

SUBROUTINE DIST( A, B, C, N )

CDVM$ NODES PA ( ACTIVE_NUM_NODES ( ) )

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

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

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

· Список ввода-вывода должен состоять только из одного имени распределенного массива и не может содержать других объектов ввода-вывода.

· В операторах ввода-вывода по формату допускается только формат, задаваемый *.

· Список управляющей информации не должен содержать параметры ERR, ЕND и IOSTAT.

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

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

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

· Список управляющей информации не должен содержать параметры ERR и ЕND.

· Допускается лишь следующая упрощенная форма списка с неявным циклом:

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

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

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

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

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

1. Message-Passing Interface Forum, Document for a Standard Message-Passing Interface, 1993. Version 1.0. http://www.unix.mcs.anl.gov/mpi

2. OpenMP Consortium: OpenMP Application Program Interface, Version 2.5 Public Draft, November 2004. http://www.openmp.org

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. Konovalov N.A., Krukov V.A., Mihailov S.N. and Pogrebtsov A.A. Fortran DVM - a Language for Portable Parallel Program Development. Proceedings of Software For Multiprocessors & Supercomputers: Theory, Practice, Experience. Institute for System Programming, RAS, Moscow, 1994. http://www.keldysh.ru/dvm/dvmhtm1107/publishe/fdvm94.html

6. DVM-система. http://www.keldysh.ru/dvm

7. Fortran DVM. Описание языка. Версия 2.0. Апрель 2001 http://www.keldysh.ru/dvm/dvmhtm1107/rus/usr/fdvm/fdvmLDr.html

8. Система поддержки выполнения параллельных программ (библиотека Lib-DVM). Откябрь 2000

http://www.keldysh.ru/dvm/dvmhtm1107/rus/sys/libdvm/rtsPDr.html

9. The NAS Parallel Benchmarks 3.0, Multi-Zone Versions. NAS, NASA Ames Research Center, Moffett Field, CA. http://www.nas.nasa.gov/Research/Reports/Techreports/2003/nas-03-010-abstract.html

10. ANSI X3.9-1978 Programming Language Fotran. New York 1978.

openmpdvm-directive	is specification-directive
	or executable-directive

specification-directive	is nodes-directive
	or align-directive
	or distribute-directive
	or template-directive
	or shadow-directive
	or dynamic-directive
	or inherit-directive
	or remote-group-directive
	or task-directive
	or asyncid-directive
	or omp-threadprivate-directive

executable-directive	is realign-directive
	or redistribute-directive
	or parallel-directive
	or remote-access-directive
	or shadow-group-directive
	or shadow-start-directive
	or shadow-wait-directive
	or new-value-directive
	or prefetch-directive
	or reset-directive
	or map-directive
	or f90-directive
	or asynchronous-directive
	or end-asynchronous-directive
	or asyncwait-directive
	or omp-parallel-directive
	or omp-do-directive
	or omp-sections-directive
	or Omp-single-directive
	or omp-workshare-directive
	or omp-paralleldo-directive
	or omp-parallelsections-directive
	or omp-parallelworkshare-directive
	or dvmopenmp-paralleldo-directive
	or dvmomp-parallelacross-directive

Параллельная область

omp-parallel-directive	Is omp-parallel-begin-directSive block omp-parallel-end-directive
omp-parallel-begin-directive	Is !$OMP PARALLEL [parallel-clause-list]
omp-parallel-end-directive	Is !$OMP END PARALLEL
parallel-clause	Is private-clause Or shared-clause Or default-clause Or firstprivate-clause Or lastprivate-clause Or reduction-clause Or copyin-clause Or if-clause Or numthreads-clause

private-clause	Is PRIVATE(list)
firstprivate-clause	Is FIRSTPRIVATE(list)
Lastprivate-clause	Is LASTPRIVATE(list)
default-clause	Is DEFAULT(PRIVATE) or DEFAULT(SHARED) or DEFAULT(NONE)

copyin-clause	Is COPYIN(list)
reduction-clause	Is REDUCTION(reduction:list)
Reduction	Is reduction-operator Or reduction-intrinsic-procedure-name

reduction-operator	Is + Or – Or * Or .AND. Or .OR. Or .EQV. Or .NEQV.

reduction-intrinsic-procedure-name	Is MAX Or MIN Or IAND Or IOR Or IEOR

if-clause	Is IF(scalar_logical_expression)
numthreads-clause	Is NUM_THREADS (scalar_logical_expression)

2. Распределение работы между нитями.

2.1 Распределение витков цикла между нитями.

Omp-do-directive	Is Omp-do-begin-directive do_loop [Omp-do-end-directive]

Omp-do-begin-directive	Is !$OMP DO [do-clause-list]

Omp-do-end-directive	Is !$OMP END DO [NOWAIT]

do-clause	Is private-clause Or firstprivate-clause Or lastprivate-clause Or reduction-clause Or schedule-clause Or ordered-clause

Schedule-clause	IS SCHEDULE(STATIC[,int]) or SCHEDULE(DYNAMIC[,int]) or SCHEDULE(GUIDED[,int]) or SCHEDULE(RUNTIME)

ordered-clause	IS ORDERED
2.2 Распределение неитерационной работы между нитями.
omp-sections-directive	Is omp-sections-begin-directive [omp-section-directive] block [omp-section-directive block] … omp-sections-end-directive

omp-sections-begin-directive	Is !$OMP SECTIONS [section-clause-list]

omp-sections-end-directive	Is !$OMP END SECTIONS [NOWAIT]

Omp-section-directive	Is !$OMP SECTION

Section-clause	Is private-clause Or firstprivate-clause Or lastprivate-clause Or reduction-clause

2.3 Директива SINGLE.

Omp-single-directive	Is !$OMP SINGLE[single-clause-list] block !$OMP END SINGLE [end-single-clause-list]

single-clause	Is private-clause Or firstprivate-clause

end-single-clause	Is copyprivate-clause Or NOWAIT

copyprivate-clause	Is COPYPRIVATE(list)

2.4 Директива WORKSHARE.

omp-workshare-directive

Is !$OMP WORKSHARE

block

!$OMP END WORKSHARE[NOWAIT]

3. Комбинированные директивы (параллельные циклы, секции)

omp-paralleldo-directive	Is omp-paralleldo-begin-directive do_loop [omp-paralleldo-end-directive]

omp-paralleldo-begin-directive	Is !$OMP PARALLEL DO [parallel-clause-list]

omp-paralleldo-end-directive	Is !$OMP END PARALLEL DO

omp-parallelsections-directive

Is omp-parallelsections-begin-directive

omp-section-directive

block

[Omp-section-directive

block]

…

omp-parallelsections-end-directive

omp-parallelsections-begin-directive

Is !$OMP PARALLEL SECTIONS [parallel-clause-list]

omp-parallelsections-end-directive

Is !$OMP END PARALLEL SECTIONS

omp-parallelworkshare-directive

Is !$OMP PARALLEL WORKSHARE [parallel-clause-list]

block

!$OMP END PARALLEL WORKSHARE

4.1 Массивы виртуальных узлов. Директива NODES

Nodes-directive	is CDVM$ NODES nodes-decl-list

Nodes-decl	is nodes-name ( explicit-shape-spec-list )
explicit-shape-spec	is [ lower-bound : ] upper-bound
Lower-bound	is int-expr
Upper-bound	is int-expr

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

· Разрешается использовать несколько массивов виртуальных узлов разной формы при следующем условии: количество узлов в каждом массиве должно быть равно значению встроенной функции NUMBER_OF_NODES ( ).

· Массивы данных с атрибутами COMMON и SAVE могут быть отображены на локальные массивы виртуальных узлов при следующем условии: при каждом вызове процедуры локальный массив узлов имеет одно и то же определение.

4.2. Директивы DISTRIBUTE и REDISTRIBUTE

distribute-directive	is CDVM$ dist-action distributee dist-directive-stuff
	or CDVM$ dist-action [ dist-directive-stuff ] :: distributee-list

Dist-action	is DISTRIBUTE
	or REDISTRIBUTE

Dist-directive-stuff

is dist-format-list [ dist-onto-clause ]

Distribute	is array-name
	or template-name

Dist-format	is BLOCK
	or WGT_BLOCK ( block-weight-array , nblock)
	or MULT_BLOCK ( block-size)
	or *

Dist-onto-clause

is ONTO dist-target

Dist-target	is nodes-name [(nodes-section-subscript-list )]
	or task-name ( task-index )

nodes-section-subscript	is [ subscript ] : [ subscript ]

subscript	is int-expr

nblock	is int-expr

Block-size	is int-expr

Block-weight-array	is array-name

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

· Количество распределенных измерений массива (формат задан не *) должно быть равно количеству измерений массива узлов в dist-target.

· Массив block-weight-array в спецификации WGT_BLOCK, должен быть одномерным массивом типа DOUBLE PRECISION.

· Директива REDISTRIBUTE может применяться только к массивам со спецификацией DYNAMIC.

4.3. Директивы ALIGN и REALIGN

align-directive	is CDVM$ align-action alignee align-directive-stuff
	or CDVM$ align-action [ align-directive-stuff ] :: alignee‑list
align-action	is ALIGN
	or REALIGN

align-directive-stuff	is ( align-source-list ) align-with-clause

Alignee	is array-name
align-source	is *
	or align-dummy

align-dummy

is scalar-int-variable

align-with-clause	is WITH align-spec

align-spec	is align-target ( align-subscript-list )

align-target	is array-name
	or template-name

align-subscript	is int-expr
	or align-dummy-use
	or *

align-dummy-use

is [ primary-expr * ] align‑dummy [ add-op primary-expr ]

primary-expr	is int-constant
	or int-variable
	or ( int-expr )

Add-op	is +
	or -

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

· Длина списка align-source-list должна быть равна количеству измерений выравниваемого массива.

· Длина списка align-subscript-list должна быть равна количеству измерений базового массива align-target.

· Директива REALIGN может применяться только к массивам со спецификацией DYNAMIC.

4.4. Директива TEMPLATE

template-directive

is CDVM$ TEMPLATE template-decl-list

template-decl

is template-name [ ( explicit-shape-spec-list ) ]

4.5. Директивы DYNAMIC и NEW_VALUE

dynamic-directive	is CDVM$ DYNAMIC alignee-or-distributee-list

alignee-or-distributee	is alignee
	or distribute

New-value-directive

is CDVM$ NEW_VALUE

5. Распределение витков цикла с распределенными массивами. Директива PARALLEL ON

parallel-directive

is PARALLEL ( do-variable-list )

ON iteration-align-spec

[ , ompfirstprivate-clause ] [ , ompreduction-clause]

[ , shadow-renew-clause] [ , shadow-compute-clause]

[ , remote-access-clause ] [ , across-clause ]

iteration-align-spec

is align-target ( iteration-align-subscript-list )

iteration-align-subscript	is int-expr
	or do-variable-use
	or *

do-variable-use	is [ primary-expr * ] do-variable [ add-op primary-expr ]

6.1.Спецификация массива с теневыми гранями

shadow-directive	is SHADOW dist-array ( shadow-edge-list )
	or SHADOW ( shadow-edge-list ) :: dist-array-list

dist-array

is array-name

shadow-edge	is width
	or low-width : high-width

Width

is int-expr

Low-width

is int-expr

high-width

is int-expr

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

· Задание размера теневых граней как width эквивалентно заданию width : width.

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

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

shadow-renew-clause	is SHADOW_RENEW ( renewee‑list )
	or shadow-start-directive
	or shadow-wait-directive

Renewee

is dist-array-name [ ( shadow-edge-list ) ] [ (CORNER) ]

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

· Если размеры теневых граней не указаны, то используются максимальные размеры.

6.2.2. Вычисление значений в теневых гранях. Спецификация SHADOW_COMPUTE

shadow-compute-clause

is SHADOW_COMPUTE

6.2.3. Спецификация AСROSS зависимых ссылок типа SHADOW для одного цикла

across-clause

is ACROSS ( dependent-array-list )

dependent-array

is dist-array-name ( dependence-list ) [(section-spec-list)]

dependence	is flow-dep-length : anti-dep-length

Flow-dep-length	is int-constant

Anti-dep-length	is int-constant

section-spec	is SECTION ( section-subscript-list )

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

· В каждой ссылке на массив может существовать зависимость по данным только по одному распределенному измерению.

6.3.1. Директива REMOTE_ACCESS

remote-access-directive	is CDVM$ REMOTE_ACCESS ( [ remote-group-name ] regular-reference-list)

regular-reference	is dist-array-name [( regular-subscript-list )]

Regular-subscript	is int-expr
	or do-variable-use
	or :

remote-access-clause	is remote-access-directive

7.1. Директива ASYNCID

asyncid-directive	Is CDVM$ ASYNCID async-name-list

7.2. Директива F90

f90-directive	Is CDVM$ F90 copy-statement

Copy-statement	is array-section = array-section

array-section	is array-name [( section-subscript-list )]

section-subscript	is subscript
	or subscript-triplet

subscript-triplet	is [ subscript ] : [ subscript ] [ : stride]

subscript	is int-expr

stride	is int-expr

7.3. Директивы ASYNCHRONOUS и END ASYNCHRONOUS

asynchronous-construct	is asynchronous-directive
	f90-directive [ f90-directive ] … copy-loop [ copy-loop ] …
	end-asynchronous-directive

asynchronous-directive	is CDVM$ ASYNCHRONOUS async-name

end-asynchronous-directive	is CDVM$ END ASYNCHRONOUS

7.4. Директива ASYNCWAIT

asyncwait-directive

Is CDVM$ ASYNCWAIT async-name

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

task-directive	Is CDVM$ TASK task-list

Task	Is task-name ( max-task )

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

map-directive	Is CDVM$ MAP task-name ( task-index )
	ONTO nodes-name( nodes-section-subscript-list)

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

Dvmomp-sections-directive

Is omp-sections-begin-directive

CDVM$ ON task-name ( task-index )

omp-section-directive

block

[CDVM$ ON task-name ( task-index )

omp-section-directive

block]

omp-sections-end-directive

9. Процедуры

inherit-directive

is CDVM$ INHERIT dummy-array-name-list

Синхронизационные директивы. Директива MASTER

Omp-master-directive

Is !$OMP MASTER

block

!$OMP END MASTER

Omp-critical-directive

Is !$OMP CRITICAL[(name)]

block

!$OMP END CRITICAL[(name)]

Omp-barrier-directive

Is !$OMP BARRIER

Omp-atomic-directive

Is !$OMP ATOMIC

Omp-flush-directive

Is !$OMP FLUSH[(list)]

Директива FLUSH применяется для следующих директив:

• BARRIER

• CRITICAL и END CRITICAL

• END DO

• END SECTIONS

• END SINGLE

• END WORKSHARE

• ORDERED и END ORDERED

• PARALLEL и END PARALLEL

• PARALLEL DO и END PARALLEL DO

• PARALLEL SECTIONS и END PARALLEL SECTIONS

• PARALLEL WORKSHARE и END PARALLEL WORKSHARE

Директива FLUSH не будет выполняться, если присутствует спецификация NOWAIT.

omp-ordered -directive

is !$OMP ORDERED

block

!$OMP END ORDERED

Работа с common-блоками.

Omp-threadprivate -directive

Is !$OMP THREADPRIVATE (list)

Функции системы подержки.

· OMP_SET_NUM_THREADS Subroutine

SUBROUTINE OMP_SET_NUM_THREADS(scalar_integer_expression)

· OMP_GET_NUM_THREADS Function

INTEGER FUNCTION OMP_GET_NUM_THREADS()

· OMP_GET_MAX_THREADS Function

INTEGER FUNCTION OMP_GET_MAX_THREADS()

· OMP_GET_THREAD_NUM Function

INTEGER FUNCTION OMP_GET_THREAD_NUM()

· OMP_GET_NUM_PROCS Function

INTEGER FUNCTION OMP_GET_NUM_PROCS()

Все предыдущие функции возвращают (устанавливают) количество нитей и процессоров на том узле, где они вызваны (а не суммарное количество нитей, процессоров на всех узлах).

· OMP_IN_PARALLEL Function

LOGICAL FUNCTION OMP_IN_PARALLEL()

· OMP_SET_DYNAMIC Subroutine

SUBROUTINE OMP_SET_DYNAMIC(scalar_logical_expression)

· OMP_GET_DYNAMIC Function

LOGICAL FUNCTION OMP_GET_DYNAMIC()

· OMP_SET_NESTED Subroutine

SUBROUTINE OMP_SET_NESTED(scalar_logical_expression)

· OMP_GET_NESTED Function

LOGICAL FUNCTION OMP_GET_NESTED()

Синхронизационные функции

· OMP_INIT_LOCK and OMP_INIT_NEST_LOCK Subroutines

SUBROUTINE OMP_INIT_LOCK(svar)

SUBROUTINE OMP_INIT_NEST_LOCK(nvar)

· OMP_DESTROY_LOCK and OMP_DESTROY_NEST_LOCK Subroutines

SUBROUTINE OMP_DESTROY_LOCK(svar)

SUBROUTINE OMP_DESTROY_NEST_LOCK(nvar)

· OMP_SET_LOCK and OMP_SET_NEST_LOCK Subroutines

SUBROUTINE OMP_UNSET_LOCK(svar)

SUBROUTINE OMP_UNSET_NEST_LOCK(nvar)

· OMP_TEST_LOCK and OMP_TEST_NEST_LOCK Functions

LOGICAL FUNCTION OMP_TEST_LOCK(svar)

INTEGER FUNCTION OMP_TEST_NEST_LOCK(nvar)

Функции работы с временем.

· OMP_GET_WTIME Function

DOUBLE PRECISION FUNCTION OMP_GET_WTICK()

Количество узлов в системе .

INTEGER FUNCTION NUMBER_OF_NODES( )

Определяет суммарное количество узлов в системе.

Количество узлов текущей подсистемы определяется встроенной функцией :

INTEGER FUNCTION ACTIVE_NUM_NODES( )

CDVM$ NODES R1( 2 )

REAL A(100,100)

CDVM$ DISTRIBUTE A (BLOCK, *) ONTO R1

A( 1: 50,1:100)

A(51:100,1:100)

Семь небольших программ из научной области приводятся для иллюстрации свойств языка Fortran DVM. Они предназначены для решения систем линейных уравнений:

A x = b

где A – матрица коэффициентов,

b – вектор свободных членов,

x – вектор неизвестных.

Для решения этой системы используются следующие основные методы.

Прямые методы. Хорошо известный метод исключения Гаусса является наиболее широко используемым алгоритмом этого класса. Основная идея алгоритма заключается в преобразовании матрицы А в верхнетреугольную матрицу и использовании затем обратной подстановки, чтобы привести ее к диагональной форме.

Явные итерационные методы. Наиболее известным алгоритмом этого класса является метод релаксации Якоби. Алгоритм выполняет следующие итерационные вычисления

x_i_,_j^new= (x_i_-1,_j^old+ x_i_,_j_-1^old+ x_i_+1,_j^old+ x_i_,_j₊₁^old ) / 4

Неявные итерационные методы. К этому классу относится метод последовательной верхней релаксации. Итерационное приближение вычисляется по формуле

x_i_,_j^new= ( w / 4 ) * (x_i_-1,_j^new+ x_i_,_j_-1^new+ x_i_+1,_j^old+ x_i_,_j₊₁^old ) + (1-w) * x_i_,_j^old

При использовании "красно-черного" упорядочивания переменных каждый итерационный шаг разделяется на два полушага Якоби. На одном полушаге вычисляются значения "красных" переменных, на другом – "черных" переменных. "Красно-черное" упорядочивание позволяет совместить вычисления и обмены данными.

Пример 1. Алгоритм метода исключения Гаусса

PROGRAM GAUSS

C решение системы линейных уравнений A´ x = b

PARAMETER ( N = 100 )

REAL A( N, N+1 ), X( N )

C A : матрица коэффициентов (N,N+1).

C вектор правых частей линейных уравнений хранится

C в (N+1)-ом столбце матрицы A

C X : вектор неизвестных

C N : число линейных уравнений

CDVM$ DISTRIBUTE A ( BLOCK, *)

CDVM$ ALIGN X(I) WITH A(I, N+1)

C Инициализация

C$OMP PARALLEL DO

CDVM$ PARALLEL (I) ON A( I , * )

DO 100 I = 1, N

DO 100 J = 1, N+1

IF (( I .EQ. J ) THEN

A( I, J ) = 2.0

ELSE

IF ( J .EQ. N+1) THEN

A( I, J ) = 0.0

ENDIF

100 CONTINUE

C Исключение

DO 1 I = 1, N

C I-ая строка матрицы A буферизуется перед

C обработкой I-ого уравнения, и ссылки A(I,K), A(I, I)

C заменяются соответствующими ссылками на буфер

CDVM$ PARALLEL ( J ) ON A( J, * ) , REMOTE_ACCESS (A ( I, : ))

C$OMP PARALLEL DO

DO 5 J = I+1, N

DO 5 K = I+1, N+1

A( J, K ) = A( J, K ) - A( J, I ) * A( I, K ) / A( I, I )

5 CONTINUE

1 CONTINUE

C сначала вычисляется X(N)

X( N ) = A( N, N+1 ) / A( N, N )

C Нахождение X(N-1), X(N-2), ...,X(1) обратной подстановкой

DO 6 J = N-1, 1, -1

C (J+1)-ый элемент массива X буферизуется перед

C обработкой J-ого уравнения, и ссылка X(J+1)

C заменяется соответствующей ссылкой на буфер

CDVM$ PARALLEL ( I ) ON A( I , * ) , REMOTE_ACCESS ( X( J+1 ))

C$OMP PARALLEL DO

DO 7 I = 1, J

A( I, N+1 ) = A( I, N+1 ) - A( I, J+1 ) * X( J+1 )

7 CONTINUE

X( J ) = A( J, N+1 ) / A( J, J)

6 CONTINUE

PRINT *, X

END

Пример 2. Алгоритм Якоби

PROGRAM JACOB

PARAMETER (K=8, ITMAX=20)

REAL A(K,K), B(K,K), EPS, MAXEPS

CDVM$ DISTRIBUTE A ( BLOCK, BLOCK)

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

C массивы A и B распределяются блоками

PRINT *, '********** TEST_JACOBI **********'

MAXEPS = 0.5E – 7

CDVM$ PARALLEL ( J, I ) ON A(I, J)

C$OMP PARALLEL DO

C гнездо из двух параллельных циклов, итерация (i,j) выполняется,

C на том узле, где размещен элемент A(i,j)

DO 1 J = 1, K

DO 1 I = 1, K

A(I, J) = 0.

IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.K .OR. J.EQ.K) THEN

B(I, J) = 0.

ELSE

B(I, J) = ( 1. + I + J )

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

C$OMP PARALLEL SHARED ( A, B) PRIVATE ( I, J )

CDVM$ PARALLEL ( J, I ) ON A(I, J), REDUCTION ( MAX( EPS ))

C$OMP DO, REDUCTION ( MAX : EPS )

C переменная EPS используется для вычисления максимального значения

DO 21 J = 2, K-1

DO 21 I = 2, K-1

EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))

A(I, J) = B(I, J)

21 CONTINUE

CDVM$ PARALLEL ( J, I ) ON B(I, J), SHADOW_RENEW (A)

C$OMP DO

C копирование теневых элементов массива A

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

DO 22 J = 2, K-1

DO 22 I = 2, K-1

B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J) + A( I, J+1 )) / 4

22 CONTINUE

C$OMP END PARALLEL

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF ( EPS . LT . MAXEPS ) GO TO 3

2 CONTINUE

3 OPEN (3, FILE='JACOBI.DAT', FORM='FORMATTED')

WRITE (3,*) B

CLOSE (3)

END

Пример 3. Последовательная верхняя релаксация

PROGRAM SOR

PARAMETER ( N = 100 )

REAL A( N, N ), EPS, MAXEPS, W

INTEGER ITMAX

!$ INTEGER IAM,

!$ INTEGER OMP_GET_THREAD_NUM, OMP_GET_NUM_THREADS

*DVM$ DISTRIBUTE A ( BLOCK, BLOCK )

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

*DVM$ PARALLEL ( J , I ) ON A( I, J )

C$OMP PARALLEL DO PRIVATE ( J, I )

DO J = 1, N

DO I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

ENDDO

DO IT = 1, ITMAX

EPS = 0.

!$OMP PARALLEL, PRIVATE(S, IAM, J, J1, I), REDUCTION (MAX : EPS)

C переменные S,IAM,J,J1,I – приватные переменные

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

C переменная EPS используется для вычисления максимума

!$ IAM = OMP_GET_THREAD_NUM()

С IAM-номер нити

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 )),

CDVM$* PRIVATE (S)

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

* A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF (EPS .LT. MAXEPS ) GO TO 4

ENDDO

4 PRINT *, A

END

Пример 4. "Красно-черная" последовательная верхняя релаксация

PROGRAM REDBLACK

PARAMETER ( N = 100 )

REAL A( N, N ), EPS, MAXEPS, W

INTEGER ITMAX

*DVM$ DISTRIBUTE A ( BLOCK, BLOCK )

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

*DVM$ PARALLEL ( J, I ) ON A( I, J )

C$OMP PARALLEL DO

DO 1 J = 1, N

DO 1 I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

C цикл для красных и черных переменных

DO 3 IRB = 1,2

*DVM$ PARALLEL (I,J) ON A(I,J), SHADOW_RENEW(A) , REDUCTION (MAX:EPS)

*DVM$* PRIVATE (S)

C$OMP PARALLEL DO, PRIVATE(S, I, J) REDUCTION (MAX:EPS)

C переменная S – приватная переменная

С (ее использование локализовано в пределах одного витка)

C переменная EPS используется для вычисления максимума

C Исключение : непрямоугольное итерационное пространство

DO 21 I = 2, N-1

DO 21 J = 2 + MOD ( I+ IRB, 2 ), N-1, 2

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

* A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

21 CONTINUE

3 CONTINUE

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF (EPS .LT. MAXEPS ) GO TO 4

2 CONTINUE

4 PRINT *, A

END

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

PROGRAM TASKS

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

		K
C	N1	A1, B1
C	N2	A2, B2

PARAMETER (K=100, N1 = 50, ITMAX=10, N2 = K – N1 )

CDVM$ NODES P(NUMBER_OF_NODES( ))

REAL A1(N1+1,K), A2(N2+1,K), B1(N1+1,K), B2(N2+1,K)

INTEGER LP(2), HP(2)

CDVM$ TASK MB( 2 )

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

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

CDVM$ DISTRIBUTE :: A1, A2

CALL DPT(LP, HP, 2)

C Распределение задач (областей) по узлам.

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

CDVM$ MAP MB( 1 ) ONTO P( LP(1) : HP(1) )

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

CDVM$ MAP MB( 2 ) ONTO P( LP(2) : HP(2) )

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

C Инициализация

CDVM$ PARALLEL (J , I) ON A1(I, J)

C$OMP PARALLEL DO PRIVATE (J, I)

DO 10 J = 1, K

DO 10 I = 1, N1

IF(I.EQ.1 .OR. J.EQ.1 .OR. J.EQ.K) THEN

A1(I, J) = 0.

B1(I, J) = 0.

ELSE

B1(I, J) = 1. + I + J

A1(I, J) = B1(I, J)

ENDIF

10 CONTINUE

CDVM$ PARALLEL (J , I) ON A2(I, J)

C$OMP PARALLEL DO PRIVATE (J , I)

DO 20 J = 1, K

DO 20 I = 2, N2+1

IF(I.EQ.N2+1 .OR. J.EQ.1 .OR. J.EQ.K) THEN

A2(I, J) = 0.

B2(I, J) = 0.

ELSE

B2(I, J) = 1. + ( I + N1 – 1 ) + J

A2(I, J) = B2(I, J)

ENDIF

20 CONTINUE

DO 2 IT = 1, ITMAX

C$OMP PARALLEL PRIVATE (J)

CDVM$ PARALLEL (J ) ON A1(N1+1, J), REMOTE_ACCESS (B2( 2, J ) )

C$OMP DO

DO 30 J = 1, K

30 A1(N1+1, J) = B2(2, J)

CDVM$ PARALLEL (J ) ON A2( 1, J), REMOTE_ACCESS (B1( N1, J ) )

C$OMP DO

DO 40 J = 1, K

40 A2(1, J) = B1(N1, J)

C$OMP END PARALEL

CDVM$ TASK_REGION MB

CDVM$ ON MB( 1 )

C$OMP PARALEL PRIVATE (J,I)

CDVM$ PARALLEL ( J, I ) ON B1(I, J),

CDVM$* SHADOW_RENEW ( A1 )

$OMP DO

DO 50 J = 2, K-1

DO 50 I = 2, N1

50 B1(I, J) = (A1( I-1, J ) + A1( I, J-1 ) + A1( I+1, J) + A1( I, J+1 )) / 4

CDVM$ PARALLEL ( J, I ) ON A1(I, J)

$OMP DO

DO 60 J = 2, K-1

DO 60 I = 2, N1

60 A1(I, J) = B1( I, J )

C$OMP END PARALLEL

CDVM$ END ON

CDVM$ ON MB( 2 )

C$OMP PARALEL PRIVATE (J,I)

CDVM$ PARALLEL ( J, I ) ON B2(I, J),

CDVM$* SHADOW_RENEW ( A2 )

$OMP DO

DO 70 J = 2, K-1

DO 70 I = 2, N2

70 B2(I, J) = (A2( I-1, J ) + A2( I, J-1 ) + A2( I+1, J) + A2( I, J+1 )) / 4

CDVM$ PARALLEL ( J, I ) ON A2(I, J)

$OMP DO

DO 80 J = 2, K-1

DO 80 I = 2, N2

80 A2(I, J) = B2( I, J )

C$OMP END PARALLEL

CDVM$ END ON

CDVM$ END TASK_REGION

2 CONTINUE

PRINT *, 'A1 '

PRINT *, A1

PRINT *, 'A2 '

PRINT *, A2

END

SUBROUTINE DPT( LP, HP, NT )

C распределение узлов для NT задач (NT = 2)

INTEGER LP(2), HP(2)

NUMBER_OF_NODES( ) = 1

NP = NUMBER_OF_NODES( )

NTP = NP/NT

IF(NP.EQ.1) THEN

LP(1) = 1

HP(1) = 1

LP(2) = 1

HP(2) = 1

ELSE

LP(1) = 1

HP(1) = NTP

LP(2) = NTP+1

HP(2) = NP

END IF

END