- последнее обновление 28.04.01 -

Оглавление

1 Введение
2 Директивы подмножества HPF-DVM
3 Синтаксис директив
4 Директивы DISTRIBUTE и REDISTRIBUTE
5 Директивы ALIGN и REALIGN
6 Директива PROCESSORS
7 Директива INDEPENDENT
8 Процедуры
9 Операторы COMMON и EQUIVALENCE
10 Операторы ввода-вывода
Литература
Приложение. Примеры программ

Пример 1. Алгоритм метода исключения Гаусса
Пример 2. Алгоритм Якоби
Пример 3. "Красно-черная" последовательная верхняя релаксация

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.

Другие директивы 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 должно удовлетворять следующим синтаксическим правилам:

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).
2. Вызов процедуры вне параллельного цикла.
   Если фактическим аргументом является явно распределенный массив (с атрибутомDISTRIBUTE или ALIGN), то он должен передаваться без изменения формы. Это означает, что фактический аргумент является ссылкой на начало массива, а соответствующий формальный аргумент имеет конфигурацию, полностью совпадающую с конфигурацией фактического аргумента.
3. Формальные аргументы.
   Если фактический аргумент имеет атрибут 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	решение системы линейных уравнений Ax = 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
	   DO  5  K = I+1, N+1
	      A(J,K) = A(J,K) - A(J,I) * A(I,K) / A(I,I)
5	   CONTINUE
1	CONTINUE
C	сначала вычисляется X(N)
	X(N) = A(N,N+1) / A(N,N)
C
C	Нахождение X(N-1), X(N-2), ...,X(1) обратной подстановкой
C
	DO  6  J = N-1, 1, -1
*HPF$	INDEPENDENT
	   DO  7  I = 1, J
	     A(I,N+1) = A(I,N+1) - A(I,J+1) * X(J+1)
7	   CONTINUE
	   X(J) = A(J,N+1) / A(J,J)
6	CONTINUE
	PRINT *,  X
	END

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

	PROGRAM   JACOBI
	PARAMETER  (K=8,  ITMAX=20)
	REAL  A(K,K), B(K,K)
*HPF$	DISTRIBUTE  A  (BLOCK, BLOCK) 
*HPF$	ALIGN  B(I,J)  WITH  A(I,J) 
C	массивы A и B распределяются блоками
	PRINT *,  '********  TEST_JACOBI_HPF   ********'
C	гнездо из двух циклов INDEPENDENT, итерация (i,j) выполняется
C	на том процессоре, где размещен элемент A(i,j)
*HPF$	INDEPENDENT
	DO  1  J = 1, K
*HPF$	INDEPENDENT
	DO  1  I = 1, K
	   A(I,J) = 0.
	   IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.K .OR. J.EQ.K) THEN
		B(I,J) = 0.
	   ELSE
		B(I,J)  = 1. + I + J 
	   ENDIF
1	CONTINUE
	DO  2  IT = 1, ITMAX
*HPF$	INDEPENDENT
	DO  21  J = 2, K-1
*HPF$	INDEPENDENT
	DO  21  I = 2, K-1
		A(I,J) = B(I,J)
21	CONTINUE
*HPF$	INDEPENDENT
	DO  22  J = 2, K-1
*HPF$	INDEPENDENT
	DO  22  I = 2, K-1
		B(I,J) = (A(I-1,J) + A(I,J-1) + A(I+1,J) + A(I,J+1)) / 4
22	CONTINUE
2	CONTINUE
3	OPEN (3,  FILE='JACH.DAT',  FORM='FORMATTED')
	WRITE (3,*)  B
	CLOSE (3)
	END

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

	PROGRAM REDBLACK
	PARAMETER (N1 = 20,N2 = 10)
	REAL  A(N1,N2),W
	INTEGER  ITMAX
*HPF$	DISTRIBUTE (BLOCK,BLOCK) :: A
	ITMAX = 20
	W = 0.5
*HPF$	INDEPENDENT 
	DO 1 J = 1,N2
*HPF$	  INDEPENDENT
	  DO 1 I = 1,N1
	     IF (I.EQ.J) THEN 
	        A(I,J) = N1+2
	     ELSE
	        A(I,J) = (-(1.))
	     ENDIF
1	CONTINUE
	DO 2 IT = 1,ITMAX
*HPF$	INDEPENDENT
	DO 21 J = 1,N2/2-1
*HPF$	  INDEPENDENT
	  DO 21 I = 1,N1/2-1
	     A(2*I+1,2*J+1) = W/4*(A(2*I,2*J+1)+A(2*I+2,2*J+1)+ 
     +	     A(2*I+1,2*J)+A(2*I+1,2*J+2))+(1-W)*A(2*I+1,2*J+1)
21	  CONTINUE
*HPF$	INDEPENDENT
	DO 22 J = 1, N2/2-1
*HPF$	  INDEPENDENT
	  DO 22 I = 1,N1/2-1
	     A(2*I,2*J) = W/4*(A(2*I-1,2*J)+A(2*I+1,2*J)+A(2*I,2*J-1)+ 
     +	     A(2*I,2*J+1))+(1-W)*A(2*I,2*J)
22	  CONTINUE
*HPF$	INDEPENDENT
	DO 23 J = 1,N2/2-1
*HPF$	  INDEPENDENT
	  DO 23 I = 1,N1/2-1
	     A(2*I,2*J+1) = W/4*(A(2*I-1,2*J+1)+A(2*I+1,2*J+1)+
     +	     A(2*I,2*J)+A(2*I,2*J+2))+(1-W)*A(2*I,2*J+1)
23	  CONTINUE
*HPF$	INDEPENDENT
	DO 24 J = 1,N2/2-1
*HPF$	  INDEPENDENT
	  DO 24 I = 1,N1/2-1
	     A(2*I+1,2*J) = W/4*(A(2*I,2*J)+A(2*I+2,2*J)+
     +	     A(2*I+1,2*J-1)+A(2*I+1,2*J+1))+(1-W)*A(2*I+1,2*J)
24	  CONTINUE
	PRINT *,'IT= ',IT
2	CONTINUE
	END