fdvmLDr (1158337), страница 8

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

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

По каждому измерению массива А существует прямая и обратная зависимость длиной 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

.

.

.

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

j

i

.

.

.

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

j

i

t1
t2
t3

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

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

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

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

• запуск обмена,

• ожидание значений.

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

Асинхронное обновление теневых граней для именованной группы распределенных массивов описывается следующими директивами.

Определение группы.

Запуск обновления теневых граней.

Ожидание значений теневых граней.

Директива SHADOW_START должна выполняться после директивы SHADOW_GROUP. После выполнения директивы SHADOW_GROUP директивы SHADOW_START и SHADOW_WAIT могут выполняться многократно. Новые значения в теневых гранях могут использоваться только после выполнения директивы SHADOW_WAIT.

Особым вариантом является использование директив SHADOW_START и SHADOW_WAIT в спецификации shadow-renew-clause параллельного цикла.

Синтаксис спецификации shadow-renew-clause расширен следующим образом:

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

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

Пример 6.8. Совмещение счета и обновления теневых граней.

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

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

CDVM$ DISTRIBUTE ( BLOCK, BLOCK ) :: C

. . .

CDVM$ SHADOW_GROUP AB ( A, B )

. . .

CDVM$ SHADOW_START AB

. . .

CDVM$ PARALLEL ( I, J ) ON C ( I, J ), SHADOW_WAIT AB

DO 10 I = 2, 99

DO 10 J = 2, 99

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

D(I,J) = (B(I-1,J) + B(I+1,J) + B(I,J-1) + B(I,J+1) ) / 4

10 CONTINUE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если в директиве REMOTE_ACCESS не указано имя группы (remote-group-name), то выполнение такой директивы происходит в синхронном режиме. В пределах нижестоящего оператора или параллельного цикла компилятор заменяет все вхождения удаленной ссылки ссылкой на буфер. Пересылка удаленных данных производится перед выполнением оператора или цикла.

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

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