Модели параллельного программирования (стр. 6 )

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

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

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

shadow-compute-clause

is SHADOW_COMPUTE

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

CDVM$ PARALLEL (I1 , I2, …, In) ON A(f1,f2 ,…,fk)

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

Пусть

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

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

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

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

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

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

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

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).

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

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

DO 10 I = 2, N-1

DO 10 J = 2, N-1

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

10 CONTINUE

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

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

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

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

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

Цикл с регулярными вычислениями, в котором существуют регулярные зависимости по распределенным массивам, можно распределять с помощью директивы PARALLEL, указывая спецификацию ACROSS.

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).

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

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

CDVM$ PARALLEL ( I, J ) ON A( I, J ) , ACROSS ( A( 1:1, 1:1 ))

DO 10 I = 2, N-1

DO 10 J = 2, N-1

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

10 CONTINUE

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

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

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

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

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

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

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

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

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

CDVM$ DISTRIBUTE A( BLOCK, * )

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

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) Распределено только одно рекуррентное измерение. Остальные измерения локализованы на каждом процессоре. Система поддержки организует конвейерное распараллеливание (см. рис.6.4). При этом размер ступени конвейера автоматически определяется на каждой ЭВМ, в зависимости от времени выполнения цикла и времени передачи данных при обновлении теневых граней.

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

CDVM$ DISTRIBUTE A( BLOCK, * )

CDVM$ PARALLEL ( I, J ) ON A( I, J ) , ACROSS ( A( 1:1, 1:1 ))

DO 40 I = 2,N1-1

DO 40 J = 2,N2-1

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

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

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

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

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

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

CDVM$ DISTRIBUTE A( BLOCK, BLOCK )

CDVM$ PARALLEL ( I, J ) ON A( I, J ) , ACROSS ( A( 1:1, 1:1 ))

DO 50 I = 2,N1-1

DO 50 J = 2,N2-1

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

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

i

p0	t1
p1	t2
p2	t3

.

.

.

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

j

i

p0	t1	t2	t3
p1	t2	t3
p2	t3

.

.

.

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

j

 

i

t1
t2
t3

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