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

Пусть NB( 1:P ) - массив целых чисел. Следующая директива

CDVM$ DISTRIBUTE A( GEN_BLOCK(NB)) ONTO R

разделяет массив A на P блоков. Блок i размера NB( i ) распределяется на процессор R( i ). При этом

	P
	å NB( i ) = N
	i=1

Пример 4.2. Распределение неравными блоками.

		A
	R(1)	1
CDVM$ PROCESSORS R( 4 )		2
	R(2)	3
INTEGER BS(4)		4
		5
		6
REAL A(12)
	R(3)	7
		8
CDVM$ DISTRIBUTE A ( GEN_BLOCK( BS ) ) ONTO R		9
		10
DATA BS / 2, 4, 4, 2 /	R(4)	11
		12

4.1.3. Формат WGT_BLOCK

Формат WGT_BLOCK определяет распределение блоками по их относительным “весам”.

Пусть задан формат WGT_BLOCK(WB, NBL).

Для 1£ i £ NBL, WB(i) определяет вес i‑ого блока. Блоки распределяются на P процессоров с балансировкой сумм весов блоков на каждом процессоре. При этом должно выполняться условие

P £ NBL

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

Формат BLOCK является частным случаем формата WGT_BLOCK(WB,P), где WB(i) = 1 для 1£ i £ P и NBL = P.

Формат GEN_BLOCK с некоторой точностью является частным случаем формата WGT_BLOCK.

Пример 4.2 можно переписать с использованием формата WGT_BLOCK следующим образом.

Пример 4.3. Распределение блоками по весам.

CDVM$ PROCESSORS R( 4 )

DOUBLE PRECISION WB(12)

REAL A(12)

CDVM$ DISTRIBUTE A ( WGT_BLOCK( WB,ONTO R

DATA WB / 2., 2.,1., 1., 1., 1., 1., 1., 1., 1., 2., 2. /

В примере 4.3 P = 4 и распределение идентично примеру 4.2.

В отличие от распределения неравными блоками, распределение по формату WGT_BLOCK можно выполнить для любого числа процессоров в диапазоне 1 £ P £ NBL. Для данного примера размер массива процессоров R может изменяться от 1 до 12.

4.1.4. Формат *

Формат * означает, что измерение будет полностью локализовано на каждом процессоре (нераспределенное или локальное измерение).

4.1.5. Многомерные распределения

При многомерных распределениях формат распределения указывается для каждого измерения. Между измерениями распределяемого массива и массива процессоров устанавливается следующее соответствие.

Пусть массив процессоров имеет n измерений. Пронумеруем измерения массива без формата * слева направо d1, ..., dk.. Тогда измерение di будет распределяться на i-ое измерение массива процессоров. При этом должно выполняться условие k£n.

Пример 4.4. Одномерное распределение.

CDVM$ PROCESSORS R1( 2 )		Блоки A	Процессоры
REAL A(100,100)
CDVM$ DISTRIBUTE A (BLOCK, *) ONTO R1	1	A( 1: 50,1:100)	1	1
	2	A(51:100,1:100)	2	2

Пример 4.5. Двумерное распределение.

CDVM$ PROCESSORS R2( 2, 2 )	Блоки A	Процессоры
REAL A(100,100)				1	2
CDVM$ DISTRIBUTE A (BLOCK, BLOCK)	1	2	1	1	2
CDVM$* ONTO R2	3	4	2	3	4

4.2. Распределение динамических массивов

4.2.1. Динамические массивы в программе на языке Фортран 77

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

Пример 4.6. Использование рабочего массива.

REAL HEAP(100000)

READ (6 , *) N, M

C в программе требуются динамические массивы размера N´ N и M´ M

CALL SUB1(HEAP(1), N, HEAP(1+N*N), M)

END

SUBROUTINE SUB1(A, N, B, M)

DIMENSION A(N, N), B(M , M)

. . .

END

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

4.2.2. Динамические массивы в модели FDVM. Директива POINTER

Предлагаемая модель является подмножеством модели динамических массивов Фортран 90 и позволяет без изменений выполнять эту модель в трех средах программирования

·  последовательная программа на языке Фортран 77,

·  параллельная программа на языке FDVM,

·  параллельная программа на языке HPF.

Для динамических массивов, распределяемых по умолчанию, FDVM разрешает использовать любые способы моделирования динамической памяти. Для динамических массивов, распределяемых директивами DISTRIBUTE и ALIGN, FDVM определяет следующую дисциплину размещения и использования динамических массивов.

*   Все явно распределяемые динамические массивы размещаются в пуле динамической памяти с именем HEAP

REAL HEAP (MAXM)

где MAXM - количество слов динамической памяти.

*   Тип данных и количество измерений динамического массива фиксируется следующей директивой FDVM

pointer-directive	is type , POINTER ( dimension-list ) :: pointer-name-list

dimension

is :

pointer-name	is scalar-int-variable-name
	or int-array-name

type определяет тип данных динамического массива. Переменные, специфицированные директивой POINTER, имеют следующие ограничения.

·  Переменной с атрибутом POINTER может быть присвоено только значение функции ALLOCATE или значение другой переменной с атрибутом POINTER.

·  Переменные с атрибутом POINTER в левой и правой части оператора присваивания должны иметь одинаковое количество измерений.

*   Размеры каждого измерения и размещение динамического массива в HEAP фиксируется следующим оператором

pointer = ALLOCATE ( sdim ,... )

где

pointer -	ссылка на целочисленную переменную (скаляр или элемент массива) с атрибутом POINTER
sdim -	целочисленный одномерный массив размера ndim. ndim - количество измерений многомерного массива, размещаемого в динамической памяти HEAP. Значение sdim( i ) определяет размер i-ого измерения. Размер выделяемого сегмента равен sdim( 1 )´ sdim( 2 )´....´ sdim( ndim ).

Целочисленная функция ALLOCATE выдает номер начального элемента выделяемого сегмента динамической памяти HEAP. Функция ALLOCATE программируется пользователем, поэтому она может иметь дополнительные параметры помимо обязательного параметра sdim.

*   В процедуре, где производится размещение динамического массива, разрешается только следующий тип ссылки на динамический массив

HEAP( pointer )

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

Пусть в программе используется несколько пулов динамической памяти с идентификаторами ID1 , …, IDn. Нет необходимости переписывать программу с одним пулом динамической памяти HEAP. Достаточно указать следующую спецификацию

CDVM$ HEAP ID1 , …, IDn

Но каждый пул IDi должен удовлетворять вышеуказанным требованиям пула HEAP.

Пул может содержать только массивы, распределяемые директивами DISTRIBUTE и ALIGN.

4.2.3. Директива DISTRIBUTE и REDISTRIBUTE для динамических массивов

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

distributee	is. . .
	or pointer-name

Если в качестве distributee указан скаляр или массив с атрибутом POINTER , то распределение откладывается до выполнения функции ALLOCATE, которая присваивает значение данному указателю. Вместо функции ALLOCATE выполняется создание массива и его распределение по форматам директивы DISTRIBUTE.

Директива REDISTRIBUTE для динамического массива может выполняться только после выполнения функции ALLOCATE, которая присваивает значение соответствующей переменной POINTER.

Если указатель динамического массива является элементом массива указателей, то распределить динамический массив можно только директивой REDISTRIBUTE. Т. к. директива REDISTRIBUTE допускает лишь ссылку на имя указателя, то элемент массива указателей необходимо предварительно переслать в скалярную переменную-указатель. Распределить массив с указателем PT(I) можно с помощью следующей последовательности операторов:

P1 = PT( I )

CDVM$ REDISTRIBUTE P1( BLOCK, BLOCK )

Программу, приведенную в примере 4.6, необходимо трансформировать в следующую FDVM программу.

Пример 4.7. Распределение динамических массивов FDVM.

REAL HEAP(100000)

INTEGER ALLOCATE

CDVM$ REAL, POINTER ( : , : ) :: PA, PB

INTEGER PA, PB

C дескрипторы динамических массивов

INTEGER DESCA(2), DESCB(2)

CDVM$ DISTRIBUTE (BLOCK, BLOCK) :: PA, PB

C в программе требуются массивы размера N´ N и M´ M

READ (6 , *) N, M

C конфигурация первого массива

DESCA(1) = N

DESCA(2) = N

C размещение и распределение первого массива

PA = ALLOCATE (DESCA,1)

C конфигурация второго массива

DESCB(1) = M

DESCB(2) = M

C размещение и распределение второго массива

PB = ALLOCATE ( DESCB, N*N+1 )

CALL SUB1(HEAP(PA), N, HEAP(PB), M)

END

SUBROUTINE SUB1(A, N, B, M)

DIMENSION A(N, N), B(M , M)

CDVM$ DISTRIBUTE *(BLOCK , BLOCK) :: A, B

. . .

END

FUNCTION ALLOCATE(DESC, P)

INTEGER DESC(2), P

ALLOCATE = P

END

Другие примеры распределения динамических массивов см. в разделе 7.7.

4.3. Распределение через выравнивание

Выравнивание массива А на распределенный массив В ставит в соответствие каждому элементу массива А элемент или секцию массива В. При распределении массива В одновременно будет распределяться массив А. Если на данный процессор распределен элемент В, то на этот же процессор будет распределен элемент массива А, поставленный в соответствие выравниванием.

Метод распределения через выравнивание выполняет следующие две функции.

1)  Одинаковое распределение массивов одной формы на один массив процессоров не всегда гарантирует, что соответствующие элементы будут размещены на одном процессоре. Это вынуждает специфицировать удаленный доступ (см. Раздел 6.) там, где его возможно нет. Гарантию размещения на одном процессоре дает только выравнивание соответствующих элементов массивов.

2)  На один массив может быть выровнено несколько массивов. Изменение распределения одного массива директивой REDISTRIBUTE вызовет соответствующее изменение распределения группы массивов.

4.3.1. Директивы ALIGN и REALIGN

Выравнивание массива описывается следующими директивами:

align-directive	is align-action alignee align-directive-stuff
	or align-action [ align-directive-stuff ] :: alignee‑list
align-action	is ALIGN
	or REALIGN
align-directive-stuff	is ( align-source-list ) align-with-clause

alignee

is array-name

align-source	is *
	or align-dummy

align-dummy

is scalar-int-variable

align-with-clause	is WITH align-spec
align-spec	is align-target ( align-subscript-list )

align-target	is array-name
	or template-name

align-subscript	is int-expr
	or align-dummy-use
	or *

align-dummy-use

is [ primary-expr * ] align‑dummy [ add-op primary-expr ]

primary-expr	is int-constant
	or int-variable
	or ( int-expr )
add-op	is +
	or -

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

·  Длина списка align-source-list должна быть равна количеству измерений выравниваемого массива.

·  Длина списка align-subscript-list должна быть равна количеству измерений базового массива align-target.

·  Директива REALIGN может применяться только к массивам со спецификацией DYNAMIC.

·  Отсутствие align-directive-stuff допустимо только в директиве ALIGN. В этом случае распределяемый массив может использоваться только после выполнения директивы REALIGN.

Пусть задано выравнивание двух массивов с помощью директивы

CDVM$ ALIGN A(d1,…,dn) WITH B(ard1,…,ardm)

где di - спецификация i-го измерения выравниваемого массива А,

ardj - спецификация j-го измерения базового массива В,

Если di задано целочисленной переменной I , то обязательно должно существовать одно и только одно измерение массива В , специфицированное линейной функцией ardj = a*I + b. Следовательно, количество измерений массива А, специфицированных идентификаторами (align-dummy) должно быть равно количеству измерений массива В, специфицированных линейной функцией.

Пусть i-ое измерение массива А имеет границы LAi : HAi , а j-ое измерение массива В, специфицированное линейной функцией a*I + b , имеет границы LBj : HBj Т. к. параметр I определен над множеством значений LAi : HAi , то должны выполняться следующие условия

a*LAi + b ³ LBj , а* HAi + b £ HBj

Если di = * , то i-ое измерение массива А будет локальным на каждом процессоре при любом распределении массива В (аналог локального измерения в директиве DISTRIBUTE ).

Если ardi = * , то массив А будет размножен по j-му измерению массива В (аналог частичного размножения по массиву процессоров).

Если ardi = int-expr, то массив А выравнивается на секцию массива В.

Пример 4.8. Выравнивание массивов

REAL A(10), B(10,10), C(22,22), D(20), E(20), F(10), G(20), H(10,10)

CDVM$ DISTRIBUTE B ( BLOCK, BLOCK )

CDVM$ DISTRIBUTE D ( BLOCK )

C выравнивание на секцию массива (вектор на первую строку матрицы А)

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

С размножение вектора - выравнивание на каждую строку

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

С сжатие матрицы - столбец матрицы соответствует элементу вектора

CDVM$ ALIGN C( *, I ) WITH D( I )

С выравнивание вектора на вектор с раздвижкой

CDVM$ ALIGN E( I ) WITH D( 2*I )