DVMH-Indirect (1158460), страница 2

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

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

6) Работа с теневыми гранями.

Обновление, добавлен вариант в shadow_renew:

shadow-spec ::= var-name [ subscript-range... ] [ ( corner ) ] | var-name [ ( shadow-name-list ) ]

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

Расширение локальной части цикла (shadow_compute):

shadow_compute [ ( shadow-name-list ) ]

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

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

red-spec ::= red-func ( var-name [ , var-name , int-expr ] ) | red-func ( var-name ( shadow-name-list ) )

Несводящиеся к редукционным функциям манипуляции с теневыми гранями. Предлагается такая конструкция:

across ( irreg-across-spec-list )

irreg-across-spec ::= var-name ( [ flow-shadow-name-list ] : [ anti-shadow-name-list ] )

flow-shadow-name ::= shadow-name

anti-shadow-name ::= shadow-name [ ( inout ) ]

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

Если в графе зависимостей, наводимых записываемыми теневыми гранями есть циклы (т. е. невозможно установить порядок), то предполагается, что порядок записей в записываемые теневые грани не имеет значения (однако между чтением и записью записываемой теневой грани не должно быть ее записи другим процессором). В остальном — очередность не регламентирована. При этом на усмотрение системы поддержки выполнения программ процессоры могут выполнять части цикла параллельно, имея в виду один из допустимых порядков выполнения. Получение flow и anti с inout across-теневых граней происходит непосредственно перед выполнением части цикла процессором, таким образом получая изменения всех ранее выполнивших свои части процессоров. Те across-теневые грани, которые помечены как inout, рассылаются своим владельцам после после обработки части цикла конкретным процессором. Присутствующие при таком цикле теневые обмены (shadow_renew) выполняются как обычно — коллективно перед циклом, а с ними и anti across-теневые грани, не имеющие указания inout.

После окончания всего цикла записываемые теневые грани автоматически не обновляются. Для получения актуальных данных в них следует использовать shadow_renew в следующем (или где они понадобятся) цикле.

Замечание. Если просто нужна нередукционная запись в теневые грани (пример — формирование матрицы коэффициентов связей узлов сетки (по форме — матрица смежности) путем обхода локальной части ячеек) без необходимости сохранения порядка, то указывается только anti зависимость с inout. Однако, более эффективным будет завести теневую грань ячеек и сделать цикл с shadow_compute, тем самым повторяя некоторые вычисления, но получая возможность независимого заполнения коэффициентов в матрице смежности.

Пример программы. Разреженные матрицы. Компиляция программы

Новые конструкции помечены комментарием «Новая конструкция».

Пример — Алгоритм Якоби на кольце, реализованный через перемножение матрицы на вектор.

Исходная программа:

Program test1

Parameter (n = 1000, itcount = 100)

Real a(2 * n)

Integer cols(2 * n)

Integer rows(2, n)

Real y(n), x(n), s

! Init

! Matrix’s form

! Или как-то вводим rows, cols, a

Do i = 1, n

rows(1, i) = (i - 1) * 2 + 1

rows(2, i) = i * 2 + 1

Enddo

cols(1) = 2

cols(2) = n

Do i = 2, n - 1

cols(2 * i - 1) = i - 1

cols(2 * i) = i + 1

Enddo

cols(2 * n - 1) = 1

cols(2 * n) = n - 1

! Matrix’s values

Do i = 1, 2 * n

a(i) = 0.5

Enddo

! Initial values

Do i = 1, n

y(i) = i

Enddo

! Calculate

Do it = 1, itcount

Do i = 1, n

x(i) = y(i)

Enddo

Do i = 1, n

s = 0

Do j = rows(1, i), rows(2, i) - 1

s = s + a(j) * x(cols(j))

Enddo

y(i) = s

Enddo

Enddo

End

DVM-программа:

Program test1dvm

Parameter (n = 1000, itcount = 100)

Real a(2 * n)

Integer cols(2 * n)

Integer rows(2, n)

! Дополнительная переменная для поэлементного распределения с помощью METIS

Integer map(n)

Real y(n), x(n), s

!DVM$ DYNAMIC :: x, y, a, cols, rows

! Предварительное распределение, для ввода структуры матрицы

!DVM$ DISTRIBUTE(BLOCK) :: rows, cols

! Обычное распределение равномерными блоками, по-умолчанию имеют теневые грани шириной 1

! Init

! Matrix’s form

! Или как-то вводим rows, cols, a

! Цикл отображен на блочно-распределенный массив (выясняется в рантайме) и все используемые в нем массивы распределены блочно => будет индексация всех массивов вестись по-старому

!DVM$ PARALLEL(i) ON rows(*, i)

Do i = 1, n

rows(1, i) = (i - 1) * 2 + 1

rows(2, i) = i * 2 + 1

Enddo

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

! Новая конструкция:

!DVM$ REALIGN cols(rows(1, i):rows(2, i) - 1) WITH rows(*, i)

! Такое выравнивание - это нечто вроде поэлементного распределения. Теневые грани также по-умолчанию отсутствуют.

cols(1) = 2

cols(2) = n

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

!DVM$ PARALLEL(i) ON rows(*, i)

Do i = 2, n - 1

cols(2 * i - 1) = i - 1

cols(2 * i) = i + 1

Enddo

cols(2 * n - 1) = 1

cols(2 * n) = n - 1

! Вызываем METIS для получения поэлементного распределения строк

call METIS_...(..., map, ...)

! Новая конструкция:

!DVM$ REDISTRIBUTE rows(*, INDIRECT(map))

! Распределенный с помощью INDIRECT массив не имеет теневых граней по-умолчанию и они ему могут добавляться по ходу программы.

!DVM$ REALIGN x(i) WITH rows(*, i)

!DVM$ REALIGN y(i) WITH rows(*, i)

! Новая конструкция:

!DVM$ REALIGN cols(rows(1, i):rows(2, i) - 1) WITH rows(*, i)

!DVM$ REALIGN a(i) WITH cols(i)

! Новая конструкция:

!DVM$ SHADOW x(cols(rows(1, i):rows(2, i) - 1)) NAME=own

! Можно завести несколько теневых граней, каждая со своим именем (используется в SHADOW_RENEW), каждая описывается объединением таких диапазонов

! Matrix’s values

! Цикл с дополнительным указанием REFERENCE, которое означает, что переменная цикла i используется исключительно как ссылка на массив a и массив a индексируется исключительно переменной цикла => ведется в локальных индексах. В правой части допустимо указывать только переменную цикла. В левой части допустимо указывать несколько массивов, но требуется выполнение свойства связанности (TIED)

!DVM$ PARALLEL(i) ON a(i), REFERENCE(a(:) <= i)

Do i = 1, 2 * n

a(i) = 0.5

Enddo

! Initial values

! Цикл без дополнительных указаний => ведется в глобальных индексах.

!DVM$ PARALLEL(i) ON y(i)

Do i = 1, n

y(i) = i

Enddo

! Новая конструкция:

!DVM$ STRICT REFERENCING REGION, REFERENCE(x(:), y(:), rows(*, :) <= cols(i)), REFERENCE(a(:), cols(:) <= rows(1, i):rows(2, i) - 1)

! Состоит из перечисления пар: в левой части находятся строго выровненные массивы (требования TIED: совпадение набора локальных для процесса глобальных индексов, монотонность по включению теневых граней по этому измерению), у каждого из которых должно быть ровно одно двоеточие, которое показывает измерение, на которое будет ссылка; в правой части находится выражение от i, где просто i обозначает переменную параллельного цикла, а NAME(i) обозначает 1) или обращение NAME(i), где i - переменная параллельного цикла, 2) или корректное с точки зрения этой директивы косвенное обращение (т.е. надо смотреть на тот REFERENCE, в котором NAME стоит в левой части). Справа допустимо указание диапазонов, такие диапазоны остаются неразрывными при реорганизации и перевычисляются соответствующим образом (не точка в точку, а концы в концы). При этом считается, что переменной параллельного цикла можно ссылаться на любой из массивов, упомянутых в левой части, т.е. REFERENCE(g1(:), g2(:) <= i) нужен только для связывания массивов g1 и g2. Появление массива допустимо в левой части только единожды, а также в правой части только единожды. Конструкция говорит о том, что следует подготовить косвенную индексацию по локальным индексам для указанных в ней сочетаний. Такая индексация включается в циклах, имеющих указание BYREF, а остальные параллельные циклы в таком регионе обрабатываются так же, как и вне его. В циклах с BYREF, равно как и без, допустимо расширение свойства ссылочности как описано выше, т.е. только REFERENCE с переменной цикла в правой части (такое указание не вносит накладных расходов (разве что расходы на связывание массивов, которые могли быть реорганизованы по-разному), а потому его указание допустимо прямо при цикле). При этом так как связывание может вести к доп.расходам, то и вводится в этом регионе возможность объявить связывание сразу на регион.

! Calculate

Do it = 1, itcount

! Цикл находится (статически) в регионе строгих ссылок и имеет указание BYREF, следовательно цикл проводится по локальным индексам, все обращения к массивам x,rows,y,a,cols идут в локальных индексах, i принимает локальные для x(i) значения индексов. Если бы x(:) отсутствовал в левых частях правил ссылаемости, то уже нельзя было бы этот цикл проводить по локальным индексам, но BYREF все равно имел бы смысл, т.к. далее от i можно перейти к чему-то, указанному в правой части REFERENCE, но не указанному в левой (в нашем примере таких массивов нет), а затем от него индексировать локальными индексами все те массивы, которые указаны в левой части того же REFERENCE, и так далее каскадно.

!DVM$ PARALLEL(i) ON x(i), BYREF

Do i = 1, n

x(i) = y(i)

Enddo

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

!DVM$ PARALLEL(i) ON y(i), BYREF, SHADOW_RENEW(x(own))

Do i = 1, n

s = 0

Do j = rows(1, i), rows(2, i) - 1

s = s + a(j) * x(cols(j))

Enddo

y(i) = s

Enddo

Enddo

! Новая конструкция:

!DVM$ END STRICT REFERENCING REGION

End

Большинство пояснений дано в самом тексте в виде комментариев.

Здесь в основном уделим внимание тому, как это компилировать и выполнять.

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

If (is_block_distributed(rows))

cur_loop = loop_create(1, ..., rows, ...)

call loop_register_handler(..., rows)

call loop_perform()

Else

cur_loop = loop_create(1, ..., rows, ...)

call loop_register_handler(..., rows)

call loop_perform()

Endif

С соответствующими обработчиками:

Do i = begIdx, endIdx

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

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