52

Институт Прикладной Математики им. М.В.Келдыша

Российская Академия наук

C-DVM

Версия 2.0

Описание языка

Апрель, 2001

Оглавление

1 Введение 4

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

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

2.2 Синтаксис директив C-DVM 7

3 Массивы виртуальных процессоров. Директива PROCESSORS 8

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

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

4.1.1 Формат BLOCK 10

4.1.2 Формат GENBLOCK 10

4.1.3 Формат WGTBLOCK 11

4.1.4 Формат [] 12

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

4.2 Многомерные динамические массивы 13

4.2.1 Динамические массивы в языке Си 13

4.2.2 Использование многомерных массивов Си 13

4.2.3 Моделирование многомерных массивов одномерными 14

4.3 Распределение выравниванием 14

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

4.3.2 Директивы TEMPLATE и CREATE_TEMPLATE 16

4.4 Нераспределяемые данные 17

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

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

5.1.1 Определение параллельного цикла 18

5.1.2 Распределение витков цикла. Директива PARALLEL 18

5.1.3 Приватные переменные 20

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

5.2 Вычисления вне параллельного цикла 21

6 Cпецификация удаленных данных 22

6.1 Определение удаленных ссылок 22

6.2 Удаленные ссылки типа SHADOW 23

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

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

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

6.2.4 Асинхронная cпецификация независимых ссылок типа SHADOW 26

6.3 Удаленные ссылки типа REMOTE 28

6.3.1 Директива REMOTE_ACCESS 28

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

6.3.3 Асинхронная спецификация удаленных ссылок типа REMOTE 29

6.4 Удаленные ссылки типа REDUCTION 31

6.4.1 Синхронная спецификация удаленных ссылок типа REDUCTION 31

6.4.2 Асинхронная спецификация удаленных ссылок типа REDUCTION 31

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

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

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

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

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

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

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

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

8 Процедуры 36

9 Ввод/вывод 37

10 Ограничения на использование языка СИ 37

11 Отличия версии 2.0 от версии 1.0 38

11.1 Копирование секций массивов 39

Литература 40

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

Пример 1. Алгоритм метода исключения Гаусса 41

Пример 2. Алгоритм Якоби 42

Пример 3. Асинхронная версия алгоритма Якоби 43

Пример 4. "Красно-черная" последовательная верхняя релаксация 44

Пример 5. Многосеточная задача 46

Пример 6. Многообластная задача 47

Приложение 2. Сводный синтаксис директив C-DVM 50

1Введение

Язык C-DVM предназначен для разработки мобильных и эффективных параллельных программ вычислительного характера. Он представляет собой расширение языка Си в соответствии с моделью DVM, разработанной в ИПМ им М.В.Келдыша РАН [1].

Вычислительные программы для последовательных ЭВМ традиционно создавались на языках Фортран 77 и Cи. Для многопроцессорных ЭВМ с распределенной памятью и сетей ЭВМ такие программы в настоящее время, как правило, создаются на языках Фортран 77 и Cи, расширенных библиотеками передачи сообщений (PVM, MPI). Разработка таких параллельных программ требует от прикладного программиста гораздо больших усилий, чем разработка последовательных программ, поскольку ему требуется не только распределить данные и вычисления между разными процессорами, но и организовать взаимодействие процессоров посредством обмена сообщениями. Фактически, параллельная программа представляет собой систему взаимодействующих программ, каждая из которых выполняется на своем процессоре. Программы на разных процессорах могут быть совершенно различными, могут различаться лишь незначительно, а могут являться одной программой, поведение которой зависит от номера процессора. Но даже в этом последнем случае, программист обычно вынужден разрабатывать и сопровождать два различных варианта своей программы -- последовательный и параллельный.

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

Таким образом, язык C-DVM представляет собой стандартный язык Си, дополненный средствами спецификации параллельного выполнения программы:

• распределение элементов массива между процессорами;

• распределение витков цикла между процессорами;

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

• организация эффективного доступа к удаленным (расположенным на других процессорах) данным;

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

Для создания программ на языке C-DVM служит специальная система автоматизации разработки параллельных программ – DVM-система.

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

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

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

Единая модель параллелизма встроена в языки Си и Фортран 77 на базе конструкций, которые “невидимы” для стандартных компиляторов, что позволяет иметь один экземпляр программы для последовательного и параллельного выполнения. Компиляторы с языков C-DVM и Fortran DVM переводят DVM-программу в программу на соответствующем последовательном языке (Си или Фортран 77) с вызовами функций системы поддержки параллельного выполнения (Lib-DVM). Поэтому единственным требованием к параллельной системе является наличие компиляторов с языков Си и Фортран 77.

Технология выполнения и отладки. Единая модель параллелизма позволяет иметь для двух языков единую систему поддержки выполнения и, как следствие, единую систему отладки, анализа и прогноза производительности. Выполнение и отладка DVM-программ может осуществляться в следующих режимах:

• Последовательное выполнение и отладка средствами стандартных компиляторов с языков Си и Фортран 77.

• Псевдо-параллельное выполнение и отладка на рабочей станции (среда WINDOWS и UNIX).

• Параллельное выполнение и отладка на параллельной ЭВМ.

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

• автоматическая проверка правильности директив параллелизма;

• трассировка и сравнение результатов параллельного и последовательного выполнения;

• накопление и визуализация трассировки данных;

• накопление данных о производительности и прогноз производительности параллельного выполнения.

2Обзор языка

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

Язык C-DVM является расширением ANSI-C специальными аннотациями (DVM-директивами). Директивы записываются как параметры макроса

DVM(<directive>)

который в последовательной программе “расширяется” в пустую строку.

DVM-директивы могут быть условно разбиты на три класса:

• директивы распределения данных (раздел 4);

• директивы распределения вычислений (разделы 5, 7);

• спецификации удаленного доступа (раздел 6).

Модель параллелизма DVM базируется на специальной форме параллелизма по данным: одна программа – множество потоков данных (SPMD). В этой модели одна и та же программа выполняется на каждом процессоре, но каждый процессор выполняет свое подмножество операторов в соответствии с распределением данных.

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

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

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

Модель DVM определяет два уровня параллелизма:

• параллелизм по данным;

• параллелизм задач.

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

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

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

2.2Синтаксис директив C-DVM

Синтаксис DVM-директив описывается расширенной БНФ. Используются следующие обозначения:

::=	есть по определению,
x | y	альтернативы,
[ x ]	необязательный элемент/конструкция,
[ x ]…	повторение 0 или более раз,
x...	повторение 1 или более раз; эквивалентно x [ x ]…

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

directive	::=	DVM ( DVM-directive [ ; DVM-directive ]… )
DVM-directive	::=	specification-directive | executable-directive
specification-directive	::=	processors-directive | align-directive | distribute-directive | template-directive | shadow-directive | shadow-group-directive | reduction-group-directive | remote-group-directive | task-directive
executable-directive	::=	realign-directive | redistribute-directive | create-template-directive | parallel-directive | remote-access-directive | create-shadow-group-directive | shadow-start-directive | shadow-wait-directive | reduction-start-directive | reduction-wait-directive | prefetch-directive | reset-directive | map-directive | task-region-directive | on-directive

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

• Описательные директивы (specification-directive) пишутся перед описаниями Си распределяемых массивов данных или DVM-объектов.

• Выполняемые директивы (executable-directive) пишутся перед операторами Си (или точкой с запятой – т.е. пустым оператором).

3Массивы виртуальных процессоров. Директива PROCESSORS

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

Синтаксис:

processors-directive

::= PROCESSORS

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