HPF

Высоко Производительный Фортран (High Performance Fortran - HPF) является языком программирования спроектированным для того, чтобы поддержать стиль программирования, использующий параллелизм обработки данных (data parallel). Главной целью при проектировании HPF было сформулировать такой язык, который позволил бы получить наивысшую производительность на параллельных компьютерах, и который бы не ограничивал переносимость программ.

Программирование c использованием параллелизма данных было определено как программирование для параллельной среды со следующими свойствами:

• однопоточное управление (single threaded control) (Программа может активизировать несколько процессов, однако таким образом, что в каждый момент времени активным оказывается только один из них.);
• общее пространство имен (global name space);
• слабо синхронное выполнение (loosely synchronous execution).

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

Первые встречи HPF форума (High Performance Fortran Forum - HPFF), объединивщего более 40 организаций, происходили в интервале с марта 1992 по март 1993. Их целью было обсудить проблемы написания и трансляции программ c параллелизмом данных, то есть программ, где распределение данных между процессорами увеличивает производительность программ. Форум определил набор расширений языка Фортран, названный Высоко Производительным Фортраном версии 1.0. Вторая серия встреч форума HPFF состоялась в период с апреля 1994 по октябрь 1994. Е§ целью было рассмотреть предложения по корректировке версии 1.0, прояснить и проинтерпретировать описание HPF. Были проанализированы предложения пользователей по дальнейшим изменениям в HPF. Окончательный отчет форума, определивший HPF версии 1.1, был принят 11 ноября 1994. Сейчас ведется работа над подготовкой HPF версии 2.

Набор расширений языка Фортран, названный Высоко Производительный Фортран был нацелен на то, чтобы предоставить пользователям Фортрана следующие возможности:

• Программирование c использованием параллелизма данных
  (операции над массивами Фортрана 90, оператор FORALL, директива INDEPENDENT и несколько внутренних функций HPF).
• Наивысшую производительность на MIMD и SIMD компьютерах с неоднородным доступом к памяти, но без ухудшения производительности на других архитектурах
  (директивы распределения данных между процессорами и несколько других директив).
• Настройку программ на различные архитектуры компьютеров, как параллельные, так и последовательные
  (внешние (extrinsic) процедуры, предоставляющие возможность низкоуровневого программирования, и ряд других конструкций HPF).

Привязка к Фортрану 90

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

• элементарные операции над целыми массивами (монолитные операции);
• возможность ссылаться на подмножества массивов;
• условные операторы, выделяющие подмножества элементов массива на основании значения условия над элементами массива;
• операции редукции, отображающие массив значений в скалярное значение;
• операции сдвига для массивов;
• префиксные (суффиксные) операции - операции над векторами такие, что каждый i-и элемент результирующего вектора есть результат применения операции ко всем предыдущим [0 . . i-1] (последующим - [i+1 . .n]) элементам исходного вектора;
• управление распределением элементов массива между процессорами

Поскольку Фортрана 90 включает в себя Фортран 77 и добавляет много новых свойств таких, как

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

то это сделало его естественной базой для HPF. HPF расширяет возможности Фортрана 90 в следующих направлениях:

• распределение данных;
• параллельная обработка данных;
• встроенные и стандартные функции;
• внешние функции;

Расширения HPF затрагивают следующие стороны Фортрана:

Директивы.

Директивы являются комментариями, которые предлагают компилятору стратегию реализации программы. Они воздействуют на производительность программы, но не изменяют вычисляемый ею результат.

Cинтаксис.

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

Библиотечные процедуры.

HPF библиотека стандартных функций включает ряд подпрограмм, которые необходимы для высоко эффективных вычислений, Это дополнительные функции редукции, префиксные и суффиксные функции, функции сортировки.

Изменения и ограничения языка.

Введены ограничения на динамическое выделение памяти, на манипулирование ею.

Поскольку для императивных языков современная технология, используемая для построения компиляторов, не позволяет автоматически принять такое решение о распределении данных между процессорами, которое давало бы приемлемую эффективность, то в HPF были введены директивы, позволяющие программисту задать распределение данных. В HPF распределение данных между реальными процессорами осуществляется в несколько этапов:

• Для каждой пары совместно используемых массивов программист может указать соответствие между их элементами с тем, чтобы соответствующие элементы были распределены на один и тот же процессор. Например, для оператора A(i,j) = B(i-1,j+2) желательно, чтобы каждый элемент A(i,j) был распределен так же, как и элемент B(i-1,j+2), что позволит избежать лишних коммуникационных обменов. Такой процесс называют выравниванием или сопоставлением (alignment) объектов. Для этого служат директивы ALIGN, REALIGN
• С помощью директив DISTRIBUITE, REDISTRIBUITE группы сопоставленных массивов распределяются между виртуальными процессорами, образующими прямоугольную решетку.
• Отображение виртуальных процессоров на физические процессоры зависит от реализации и осуществляется компилятором.

На следующем рисунке массивы A и B выровнены друг относительно друга так, что каждый элемент A(i+1,j+1) будет распределен так же, как и элемент B(i,j).

Несколько видов возможных распределений массивов A и B на множество из 4-х виртуальных процессоров показаны ниже.

В HPF имеется возможность указать, что массивы распределяются на множество виртуальных процессоров, имеющее определенную организацию. Например, если в следующем примере

	REAL A(16, 16), B(14,14)
	!HPF$ ALIGN B(I,J) WITH A(I+1,J+1) 
	!HPF$ PROCESSORS P(NUMBER_OF_PROCESSORS()/3,3 )
	!HPF$ DISTRIBUTE A(CYCLIC,BLOCK) ONTO P 

встроенная функция NUMBER_OF_PROCESSORS, указывающая количество имеющихся в наличии процессоров, возвращает 6, то директива PROCESSORS определяет двумерную матрицу 2x3 ( P_ij, где i=1,2 и j=1,2,3 ). В этом случае элементы массива A распределяются следующим образом:

A(1:15:2,:) отображаются на процессоры P(1,1:3)
A(2:16:2,:) отображаются на процессоры P(2,1:3)

В дополнение к оператору FORALL HPF предоставляет директиву INDEPENDENT, которая позволяет программисту указать компилятору, что в следующем за директивой цикле нет меж итерационных зависимостей, что итерации DO-цикла можно выполнять в произвольном порядке. Хотя компилятор во многих случаях может обнаружить наличие или отсутствие меж итерационных зависимостей, существуют циклы, в которых это сделать не возможно. В этом случае указание директива INDEPENDENT позволит компилятору сгенерировать значительно более эффективный код. Например, в следующем примере

	!HPF$ INDEPENDENT
        DO I=1,n
                B( index(I) ) = A(I)
        END DO

директива INDEPENDENT указывает компилятору, что массив index не содержит повторяющихся значений.