Вторая версия (1158279), страница 2

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

Текст из файла (страница 2)

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

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

Распределение вычислений внутри узла

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

В начальный момент времени порождается "основная" нить, которая начинает выполнение программы на узле со стартовой точки. Основная нить и только она исполняет все последовательные области программы. При помощи OpenMP-директивы PARALLEL (см. раздел 3.6.1), создается параллельная область – множество нитей, между которыми и может распределяться вся работа на узле.

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

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

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

• директива SINGLE.

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

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

CDVM$ DISTRIBUTE A ( f₁…f_k )

где f_i - формат распределения для i-го измерения,

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

Если fi = BLOCK , то измерение «разрезается» на равные блоки и распределяется по одному блоку на узел. Если fi = MULT_BLOCK(m), то измерение распределяется блоками кратности m. Такое измерение будем называть распределенным измерением.

Если fi = *, то на каждый узел распределяется целое измерение (локальное измерение).

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

Пример.

CDVM$ DISTRIBUTE A (BLOCK, * , BLOCK)

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

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

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

CDVM$ ALIGN A ( a₁… a_n ) WITH B (b₁… b_m )

где 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 и семантика.

CDVM$ ALIGN A( I) WITH B(2*I+1)

Распределить элемент A( I ) и B( 2*I+1) на один узел

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

Распределить элемент A( I,J ) и B( J,I) на один узел.

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

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

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

Распределить I-ую строку A и элемент B( I ) на один узел, т.е. размножить второе измерение массива А.

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

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

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

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

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

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

CDVM$ PARALLEL ( I_{1 ,}… I_n ) ON A ( e_1,… 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 ON каждый виток параллельного цикла ставит в соответствие некоторому элементу массива. Это означает, что виток цикла будет выполняться на том узле, где распределен соответствующий элемент массива. По семантике директива PARALLEL ON аналогична директиве ALIGN. Отличием является то, что вместо выравниваемого массива данных используется массив витков параллельного цикла.

Пример.

CDVM$ PARALLEL ( I, J ) ON A( 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) = D(I,J) - C(I,J)

1. CONTINUE

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

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

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

Пример.

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

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

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

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

• нет DVM-директив в теле цикла.

3.5Удаленные данные. Их типы и спецификация

В следующих разделах будем использовать фрагмент программы

CDVM$ DISTRIBUTE A ( BLOCK)

. . .

CDVM$ PARALLEL ( I ) ON A ( I)

DO 10 I =1,N

A(I) = expr

10 CONTINUE

где expr - выражение.

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

3.5.1Локализация данных

Пусть

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

Если A( I ), B( I ) и C( I ) для каждого I распределены на одном узле, то для этого оператора не существует удаленных данных. Локализацию данных можно выполнить директивами ALIGN:

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

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

Рассмотрим оператор

A( I ) = B( I+d1 )+ C( I-d2 )

где d1,d2 – положительные константы.

Полную локализацию данных для этого оператора невозможно выполнить используя массив A, т.к. смещение +d1 и -d2 выводят за пределы индексного пространства массива A. Поэтому необходимо применить шаблон следующим образом.

CDVM$ TEMPLATE TABC ( N )

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

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

CDVM$ ALIGN C( I ) WITH TABC( I + d1+d2)

CDVM$ DISTRIBUTE TABC ( BLOCK )

В этом случае A( I ) , B( I+d1 ) и C( I-d2 ) для каждого I будут распределены на один узел. Шаблон TABC определяет некоторое индексное пространство, которое является посредником между массивом данных и массивом виртуальных узлов. Элементы шаблона не имеют физического представления в памяти. Они указывают узлы, на которые должны быть распределены соответствующие элементы массивов данных.

3.5.2Удаленные данные типа SHADOW

A( I ) = B( I-d1 )+ B( I+d2 )

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

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

После выполнения этой директивы точно определяется местонахождение удаленных данных. Для вычисления всех A(I) на одном узле будут использоваться d1 элементов массива B с левого соседнего узла и d2 с правого соседнего узла. Такие данные будем называть удаленными данными типа SHADOW (теневые).

Для спецификации размера этих данных служит директива SHADOW:

Характеристики

Список файлов книги