11

Институт прикладной математики им. М.В.Келдыша

Российская Академия наук

Расширенное подмножество языка HPF

(HPF-DVM)

Спецификация языка

Апрель, 2001

Оглавление

1 Введение 3

2 Директивы подмножества HPF-DVM 3

3 Синтаксис директив 3

4 Директивы DISTRIBUTE и REDISTRIBUTE 4

5 Директивы ALIGN и REALIGN 4

6 Директива PROCESSORS 4

7 Директива INDEPENDENT 4

8 Процедуры 5

9 Операторы COMMON и EQUIVALENCE 5

10 Операторы ввода-вывода 6

Литература 6

Приложение. Примеры программ 7

Пример 1. Алгоритм метода исключения Гаусса 7

Пример 2. Алгоритм Якоби 8

Пример 3. "Красно-черная" последовательная верхняя релаксация 9

1Введение

Документ определяет язык HPF‑DVM, представляющий собой подмножество HPF [1].

Подмножество HPF‑DVM включает:

• стандарт языка Фортран 77 [2] с некоторыми исключениями (см. разделы 8,9,10);

• подмножество директив языка HPF1(см. раздел 2).

Конструкции языка HPF1, включенные в HPF‑DVM, удовлетворяют следующим критериям:

• эффективность параллельного выполнения;

• мобильность;

• легкость использования.

Выбор стандарта Фортран 77 в качестве базового языка обеспечивает мобильность программ, т.к. не для всех современных ЭВМ существуют компиляторы с языка Фортран 90.

Подмножество HPF‑DVM реализовано в рамках модели DVM.

2Директивы подмножества HPF-DVM

Подмножество HPF‑DVM базируется на языке Фортран 77 и включает следующие директивы языка HPF1.

Директивы	Ограничения
PROCESSORS	раздел 6
DISTRIBUTE	раздел 4
REDISTRIBUTE	раздел 4
ALIGN	раздел 5
REALIGN	раздел 5
INHERIT	нет
DYNAMIC	нет
TEMPLATE	нет
INDEPENDENT	раздел 7

Другие директивы HPF1 и расширения языка Фортран не включены в подмножество HPF‑DVM.

3Синтаксис директив

Строка спецкомментария hpf-directive-line должна удовлетворять правилам написания комментария в фиксированной форме.

4Директивы DISTRIBUTE и REDISTRIBUTE

Директивы DISTRIBUTE и REDISTRIBUTE имеют следующие ограничения:

• Форматом распределения dist-format может быть только BLOCK or *.

• dist-target не может быть * processors-name или * (см. раздел 8).

5Директивы ALIGN и REALIGN

Директивы ALIGN и REALIGN имеют следующие ограничения:

• Запрещено выравнивание с реверсированием измерения, т.е. выравнивание типа

CHPF$ ALIGN A(I) WITH B(100–I)

• Спецификация align-spec не может иметь вид * align-target(см. раздел 8).

• Выражение align-subscript-use должно удовлетворять следующим синтаксическим правилам:

align-subscript-use	is [ primary-expr * ] align‑dummy [ add-op primary-expr ]
primary-expr	is int-constant
	or int-variable
	or ( int-expr )

6Директива PROCESSORS

В директиве PROCESSORS должен обязательно указываться список explicit‑shape-spec-list.

Для определения количества физических процессоров может использоваться только встроенная функция NUMBER_OF_PROCESSORS().

7Директива INDEPENDENT

Директивы INDEPENDENT могут специфицировать только тесно гнездовые циклы.

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

Левые части операторов присваивания в теле цикла могут быть только ссылками на переменные с атрибутом DISTRIBUTE , ALIGN, INHERIT, NEW или REDUCTION.

Левые части операторов присваивания одного витка цикла должны быть размещены на одном процессоре и, следовательно, виток цикла полностью выполняется на одном процессоре.

Переменная цикла ( I ) может индексировать распределенное измерение массива только линейным выражением вида

a * I ± b

Целочисленные выражения a и b должны быть инвариантными относительно цикла.

Последовательные циклы (без INDEPENDENT) могут охватывать цикл INDEPENDENT или быть вложенными в него. DO-переменные вложенных циклов могут индексировать только не распределенные (локальные) измерения массивов.

Синтаксис и семантика спецификации REDUCTION соответствуют HPF2 [3].

8Процедуры

1. Вызов процедуры из параллельного цикла.

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

1. Вызов процедуры вне параллельного цикла.

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

1. Формальные аргументы.

Если фактический аргумент имеет атрибут DISTRIBUTE или ALIGN,то формальный параметр должен быть специфицирован директивой INHERIT. Т.е. распределенные формальные параметры всегда имеют наследуемое распределение.

9Операторы COMMON и EQUIVALENCE

Массивы, распределяемые по умолчанию, могут без ограничений использоваться в COMMON блоках и операторах EQUIVALENCE.

Массивы, распределяемые директивами DISTRIBUTE и ALIGN, не могут использоваться в операторах EQUIVALENCE. Кроме того, эти массивы не могут ассоциироваться с другими объектами данных. Явно распределяемые массивы могут быть компонентами COMMON блока при следующих условиях:

• COMMON блок должен быть описан в главной программной единице.

• Каждое описание COMMON блока должно иметь одно и то же количество компонент, а соответствующие компоненты - последовательности памяти одинакового размера.

• Если компонентой COMMON блока является явно распределяемый массив, то объявления массива в разных программных единицах должны специфицировать один и тот же тип данных и одинаковую конфигурацию. Директивы DISTRIBUTE и ALIGN для этого массива должны иметь идентичные параметры.

10Операторы ввода-вывода

HPF-DVM допускает только ограниченную форму операторов ввода-вывода для распределенных массивов:

• Список ввода-вывода должен состоять только из одного имени распределенного массива и не может содержать других объектов ввода-вывода.

• В операторах ввода-вывода по формату допускается только формат, задаваемый *.

• Список управляющей информации не должен содержать параметры ERR, ЕND и IOSTAT.

• В списке управляющей информации допускается использование только размноженных переменных.

Не разрешается использовать операторы ввода-вывода распределенных массивов в цикле INDEPENDENT.

На операторы ввода-вывода размноженных данных распространяются следующие ограничения:

• Список управляющей информации не должен содержать параметры ERR и ЕND.

• Допускается лишь следующая упрощенная форма списка с неявным циклом:

(A(i1,i2,...,I), I = n1,n2)

при вводе размноженного массива неопределенного размера.

Оператор ввода, оператор INQUIRE, а также любой другой оператор ввода-вывода с управляющим параметром IOSTAT не должны использоваться в цикле INDEPENDENT.

Литература

1. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 1.0.

2. ANSI X3.9-1978 Programming Language Fortran. New York 1978.

3. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 2.0.

Приложение. Примеры программ

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

A x = b

где A – матрица коэффициентов,

b – вектор свободных членов,

x – вектор неизвестных.

Для решения этой системы используются следующие основные методы.

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

Явные итерационные методы. Наиболее известным алгоритмом этого класса является метод релаксации Якоби. Алгоритм выполняет следующие итерационные вычисления

x_i,j^new = (x_i-1,j^old + x_i,j-1^old + x_i+1,j^old + x_i,j+1^old ) / 4

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

x_i,j^new = ( w / 4 ) * (x_i-1,j^new + x_i,j-1^new + x_i+1,j^old + x_i,j+1^old ) + (1-w) * x_i,j^old

При использовании "красно-черного" упорядочивания переменных каждый итерационный шаг разделяется на два полушага Якоби. На одном полушаге вычисляются значения "красных" переменных, на другом – "черных" переменных. "Красно-черное" упорядочивание делает независимыми по данным вычисления на каждом полушаге.

Пример 1. Алгоритм метода исключения Гаусса

PROGRAM GAUSS

C решение системы линейных уравнений Ax = b

PARAMETER ( N = 100 )

REAL A( N, N+1 ), X( N )

C A : матрица коэффициентов (N,N+1)

C вектор правых частей линейных уравнений хранится

C в (N+1)-ом столбце матрицы A

C X : вектор неизвестных

C N : число линейных уравнений

*HPF$ DISTRIBUTE A (BLOCK,*)

*HPF$ ALIGN X(I) WITH A(I,N+1)

С

C Инициализация

*HPF$ INDEPENDENT

DO 100 I = 1, N

DO 100 J = 1, N+1

IF (( I .EQ. J ) THEN

A(I,J) = 2.0

ELSE

IF ( J .EQ. N+1) THEN

A(I,J) = 0.0

ENDIF

ENDIF

100 CONTINUE

C

C Исключение

C

DO 1 I = 1, N

*HPF$ INDEPENDENT

DO 5 J = I+1, N