- 11 - 30.12.2003 03:52:00 PM

Модели параллельных вычислений и DVM–технология разработки параллельных программ

Лекция 2. Параллельное программирование в модели DVM (2 часа)

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

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

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

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

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

2. Распараллеливание программ на языке C-DVM

2.1. Абстрактная модель распараллеливания

Параллелизм последовательной программы описывается на языке C-DVM с помощью директив. Каждая директива оформляется в виде спецмакроса следующего вида:

DVM(<директива-DVM>)

Формальный синтаксис директив приведен в Приложении 2 к Описанию языка C‑DVM.

Распараллеливание программы в модели DVM можно разделить на два этапа.

1. Распределение данных (массивов) и вычислений (параллельных циклов) на массив виртуальных процессоров.

2. Определение и спецификация удаленных (общих) данных.

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

На первом этапе используются директивы DISTRIBUTE, ALIGN и PARALLEL. Если рассматривать эти директивы на абстрактном уровне, то они устанавливают соответствие между точками индексных (дискретных) пространств двух объектов. При этом используются индексные пространства следующих объектов:

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

A_i - индексное пространство i–го массива данных

L_j - индексное пространство j–го параллельного цикла. Параллельный цикл рассматривается как массив, элементом которого является виток цикла. Количество измерений этого массива определяется количеством заголовков цикла.

Директивы устанавливают соответствие между точками (элементами) следующих объектов:

ALIGN: A_i1  A_i2. Каждой точке (элементу массива) A_i2 ставится в соответствие подмножество точек (элементов массива) A_i1.

PARALLEL: L_j  A_i. Каждой точке (элементу массива) A_i ставится в соответствие подмножество точек (витков цикла) L_j.

DISTRIBUTE: A_i  P. Каждой точке (виртуальному процессору) P ставится в соответствие подмножество точек (элементов массива) A_i.

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

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

Определение общих (удаленных) данных

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

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

Цель распараллеливания - максимальный параллелизм при минимизации удаленных данных (максимум локализации).

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

2.2. Распределение данных. Директивы DISTRIBUTE и REDISTRIBUTE

Первоначальное распределение массива описывается следующей директивой

DVM( DISTRIBUTE f₁…f_k ) <описание-массива-на-языке-Си>

где f_i = [ BLOCK ] - распределение равными блоками

= [ ] - распределение целым измерением.

k - количество измерений массива.

Для каждого измерения массива задается формат распределения. Если задан формат [ BLOCK ], то измерение «разрезается» на равные блоки и распределяется по одному блоку на процессор. Такое измерение будем называть распределенным измерением. Если задан формат [ ], то на каждый процессор распределяется целое измерение (локальное измерение).

Количество форматов [ BLOCK ] определяет количество измерений массива виртуальных процессоров. Если мы пронумеруем форматы [ BLOCK ], как fb₁,…,fb_n, то измерение с форматом fb_i отображается на i–ое измерение массива виртуальных процессоров, а количество блоков определяется размером i–го измерения массива виртуальных процессоров. В этом случае при запуске программы на выполнение можно задавать любой n–мерный массив виртуальных процессоров.

Пример.

DVM(DISTRIBUTE [BLOCK] [ ] [BLOCK]) float A[N][N][N};

Такое описание указывает на то, что пользователь работает с двумерным массивом виртуальных процессоров (количество форматов [ BLOCK ] равно 2). Пусть при запуске программы на выполнение задан массив виртуальных процессоров P(M1,M2). Тогда эта директива распределит первое измерение массива А на первое измерение P блоками размера N/M1, третье измерение А - на второе измерение P блоками размера N/M2, а второе измерение А будет целиком распределено на каждый виртуальный процессор.

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

DVM( REDISTRIBUTE f₁…f_k ) <идентификатор-массива>

2.3. Локализация данных. Директивы ALIGN и REALIGN

Основным способом локализации данных (т.е. уменьшения удаленных данных) является совместное распределение нескольких массивов. Совместное распределение двух массивов А и В описывается следующей директивой выравнивания массивов.

DVM( ALIGN a₁… a_n WITH B b₁… b_m ) <описание-массива-A-на-языке-Си>

где a_i - параметр i–го измерения выравниваемого массива А

b_j - параметр j–го измерения базового массива B

n - количество измерений массива А

m - количество измерений массива В

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

a_i =[ ID_i ] b_j =[ c*ID_j+d ]

=[ ] =[ ]

где ID_i , ID_j - идентификаторы

c, d - целочисленные константы

Рассмотрим семантику этих обозначений.

Если a_i =[ ] , то i–тое измерение массива А целиком распределяется на каждый процессор, где распределен хотя бы один элемент В (размножение, локальное измерение).

Если b_j =[ ] , то выполнение директивы ALIGN не зависит от j-ого измерения массива В (коллапс, т.е. измерение как бы не существует при установлении соответствия).

Если a_i =[ ID_i ] , то обязательно существует одно и только одно b_j =[ c*ID_j+d ] , где ID_i=ID_j. Равенство ID_i=ID_j означает, что i–тое измерение массива А ставится в соответствие j-ому измерению массива В. Соответствие элементов устанавливается функцией c*ID_j+d .

Примеры директивы ALIGN и семантика.

DVM(ALIGN [i] WITH B[2*i+1] ) float A[N];

Распределить элемент A[ i ] и B[2*i+1] на один процессор.

DVM(ALIGN [i][j] WITH B[j][i]) float A[N][N];

Распределить элемент A[ i ] [ j ] и B[ j ] [ i ] на один процессор.

DVM(ALIGN [i] WITH B[][i]) float A[N];

Распределить элемент A[ i ] на те процессоры, где размещен хотя бы один элемент i-ого столбца B.

DVM(ALIGN [i] [ ] WITH B[i]) float A[N][N];

Распределить i-ую строку A и элемент B[ i ] на один процессор, т.е. размножить второе измерение массива А.

Изменить параметры выравнивания и/или базовый массив можно с помощью директивы

DVM( ALIGN a₁… a_n WITH C c₁… c_k ) <описание-массива-A-на-языке-Си>

2.4. Распределение витков параллельного цикла. Директива PARALLEL

Заголовки параллельных циклов описываются макросами DO( ) или FOR( ):

#define DO(v,f,u,s) for(v=f; v<=u; v+=s)

#define FOR(v,h) for(v=0; v<=h-1; v+=1)

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

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

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

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

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

DVM( PARALLEL [ I₁ ]… [ I_n ] ON A e₁… e_m )

где

I_j - переменная (индекс) j–го заголовка параллельного цикла,

n - количество заголовков цикла,

A - идентификатор массива,

m - количество измерений массива,

e_i=[a* I_k+b], a, b – целочисленные переменные

I_k - переменная(индекс) k-го заголовка цикла.

Это выражение означает следующее:

• k-ое измерение (заголовок цикла) массива витков цикла ставится в соответствие i–ому измерению массива данных,

• соответствие витка цикла и элемента массива устанавливается линейной функцией a*I_k+b.

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