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

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

Замечание. Заголовки в гнезде циклов должны быть записаны с помощью макросов DO(var,first,last,step) или FOR(var,times) (сокращение для DO(var,0,times-1,1)).

Директива PARALLEL размещается перед заголовком цикла и распределяет витки циклов в соответствии с распределением массива или шаблона. Семантика директивы аналогична семантике директивы ALIGN, где индексное пространство выравниваемого массива заменяется индексным пространством цикла. Индексы циклов в списке loop-variable... перечисляются в том порядке, в котором размещены соответствующие операторы DO в тесно-гнездовом цикле.

Синтаксис и семантика отдельных частей директивы описаны в следующих разделах:

reduction-clause раздел 5.1.4,

shadow-renew-clause раздел 6.2.2,

remote-access-clause раздел 6.3.1,

across-clause раздел 6.2.3.

Пример 5.1. Распределение витков цикла с регулярными вычислениями.

DVM(DISTRIBUTE B[BLOCK][BLOCK]) float B[N][M+1];

DVM(ALIGN [i][j] WITH B[i][j+1]) float A[N][M], C[N][M], D[N][M];

. . .

DVM(PARALLEL [i][j] ON B[i][j+1])

DO(i, 0, N-1, 1)

DO(j, 0, M-2, 1)

{

A[i][j] = D[i][j] + C[i][j];

B[i][j+1] = D[i][j] – C[i][j];

}

Цикл удовлетворяет всем условиям параллельного цикла. В частности, левые части операторов присваивания одного витка цикла A[I][J] и B[I][J+1] размещаются на одном процессоре благодаря выравниванию массивов А и В.

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

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

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

Пример 5.3. Объявление приватной переменной.

DVM(PARALLEL [i]]j] ON A[i][j] )

FOR(i, N)

FOR(j, N)

{float x; /* variable private for every iteration */

x = B[i][j] + C[i][j];

A[i][j] = x;

}

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

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

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

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

Пример 5.4. Спецификация редукции.

S = 0;

X = A[0];

Y = A[0];

MINi = 0;

DVM(PARALLEL [i] ON A[i];

REDUCTION SUM(S) MAX(X) MINLOC(Y,MIMi))

FOR(i, N)

{

S = S + A[i];

X = max(X, A[i]);

if(A[i] < Y) {

Y = A[i];

MINi = i;

}

}

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

Вычисления вне параллельного цикла выполняются по правилу собственных вычислений. Оператор присваивания lh = rh; может быть выполнен на некотором процессоре, только если lh присутствует на нем. Если lh – элемент распределенного массива (и присутствует не на всех процессорах), то такой оператор (оператор собственных вычислений) будет выполняться только на том процессоре (или на тех процессорах), где присутствует данный элемент распределенного массива. Все данные, используемые в выражениях rh, должны также присутствовать на этом процессоре. Если какие-либо данные из выражений lh и rh отсутствуют на нем, то их необходимо указать в директиве удаленного доступа (см. 6.1.2) перед этим оператором.

Если lh является ссылкой на распределенный массив А и существует зависимость по данным между rh и lh, то распределенный массив необходимо размножить с помощью директивы REDISTRIBUTE А[]…[] или REALIGN А[]…[].

Пример 5.5. Собственные вычисления.

#define N 100

DVM(DISTRIBUTE [BLOCK][]) float A[N][N+1];

DVM(ALIGN [I] WITH A[I][N+1]) float X[N];

. . .

/* reverse substitution of Gauss algorithm */

/* own computations outside the loops */

X[N-1] = A[N-1][N] / A[N-1][N]

DO(J, N-2,0, -1)

DVM(PARALLEL [I] ON A [I][]; REMOTE_ACCESS X[j+1])

DO(I, 0, J, 1)

A[I][N] = A[I][N] – A[I][J+1] * X[J+1];

/* own computations in sequential loop, */

/* surrounding the parallel loop */

X[J] = A[J][N] / A[J][J]

}

Отметим, что A[J][N+1] и A[J][J] локализованы на том процессоре, где размещается X[J].

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

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

Удаленными данными будем называть данные, используемые на данном процессоре, но размещенные на другом процессоре. Ссылки на такие данные будем называть удаленными ссылками. Рассмотрим обобщенный оператор

if (…A[inda]…) B[indb] = …C[indc]…

где

A, B, C - распределенные массивы,

inda, indb, indc - индексные выражения.

В модели DVM этот оператор будет выполняться на процессоре, на котором размещен элемент B(indb). Ссылки A(inda) и C(indc) не являются удаленными ссылками, если соответствующие им элементы массивов A и C размещены на процессоре том же процессоре. Единственной гарантией этого является выравнивание A(inda), B(indb) и C(indc) в одну точку шаблона выравнивания. Если выравнивание невозможно или не было выполнено, то ссылки A(inda) и/или C(indc) необходимо специфицировать как удаленные ссылки. В случае многомерных массивов данное правило применяется к каждому распределенному измерению.

По степени эффективности обработки удаленные ссылки разделены на два типа: SHADOW и REMOTE.

Если массивы B и C выровнены и

inda = indc  d ( d – положительная целочисленная константа),

то удаленная ссылка C(indc) принадлежит типу SHADOW. Удаленная ссылка на многомерный массив принадлежит типу SHADOW, если распределяемые измерения удовлетворяют определению типа SHADOW.

Удаленные ссылки, не принадлежащие типу SHADOW, составляют множество ссылок типа REMOTE.

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

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

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

Асинхронная спецификация позволяет совместить вычисления с межпроцессорными обменами. Она объединяет удаленные ссылки нескольких операторов и циклов. Для запуска операции обработки ссылок и ожидания ее завершения служат специальные директивы. Между этими директивами могут выполняться другие вычисления, в которых отсутствуют ссылки на специфицированные переменные.

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

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

Удаленная ссылка типа SHADOW означает, что обработка удаленных данных будет происходить через “теневые” грани. Теневая грань представляет собой буфер, который является непрерывным продолжением локальной секции массива в памяти процессора (см. рис.6.1.).Рассмотрим оператор

A[i] = B[i + d2] + B[ i – d1]

где d1, d2 – целые положительные константы. Если обе ссылки на массив B являются удаленными ссылками типа SHADOW, то для массива B необходимо использовать поддирективу SHADOW [ d1 : d2], где d1 – ширина левой грани, а d2 – ширина правой грани. Для многомерных массивов необходимо специфицировать грани по каждому измерению. При спецификации теневых граней в описании массива указывается максимальная ширина по всем удаленным ссылкам типа SHADOW.

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

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

Размер левой теневой грани (low-width) и размер правой теневой грани (high-width) должны быть целыми константными выражениями, значения которых больше или равны 0.

Задание размера теневых граней как width эквивалентно заданию width : width.

По умолчанию, распределенный массив имеет теневые грани шириной 1 с обеих сторон каждого распределенного измерения.

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

Спецификация синхронного обновления теневых граней является частью директивы PARALLEL:

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

• Размер обновляемых теневых граней не должен превышать максимального размера, описанного в директиве SHADOW.

• Если размеры теневых граней не указаны, то используются максимальные размеры.

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

Пример 6.1. Спецификация SHADOW-ссылок без угловых элементов

DVM(DISTRIBUTE [BLOCK]) float A[100];

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

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