3. Язык HPF

Цели процесса разработки HPF были довольно простыми:

• Обеспечить удобную поддержку программирования для масштабируемых параллельных компьютерных систем, обращая особое внимание на параллелизм по данным.
• Предоставить понятную машинно-независимую модель программирования, обладающую тремя основными качествами:
  1. У разработчиков приложений должна иметься возможность представлять память как единое совместно используемое адресное пространство даже на машинах с распределенной памятью; другими словами, массивы должны являться глобально доступными, но распределенными по памятям процессоров, участвующих в вычислениях.
  2. Должно казаться, что у программ, написанных на новом языке, имеется единственный поток управления, чтобы такая программа могла бы корректно выполняться на одном процессоре; таким образом, весь параллелизм должен происходить из параллельного применения операций к распределенным структурам данных.
  3. Код коммуникаций должен генерироваться неявно, чтобы от программиста не требовалось заботиться о деталях определения межпроцессорных обменов сообщениями и управлении ими.
• Обеспечить возможности генерации кода, эффективность которого была бы сопоставима с эффективностью наилучшей «ручной» реализации того же приложения с использованием MPI.

Для достижения этих целей в стандарте HPF 1.0 определялся язык с рядом новых характеристик.

Во-первых, язык основывался на Fortran 90, а расширения определялись как набор «директив», представляемых в форме комментариев Fortran 90. Эти директивы могли интерпретироваться компиляторами HPF как рекомендации относительно того, как генерировать параллельные программы. На скалярных машинах HPF-программы могли выполняться без изменений путем игнорирования этих директив, если машины располагали памятью достаточного объема. Этот подход, который позже был перенят группой по стандартизации OpenMP, позволял точно отделить параллельные расширения HPF от основной программы на Fortran 90: в программу по-прежнему требовалось встроить алгоритм распараллеливания по данным, но одна и та же программа могла работать как на последовательных, так и на параллельных системах. От компиляторов для последовательных систем не требовалось распознавание каких-либо директив HPF. Следует заметить, что возможность выполнения по-существу одной и той же программы на последовательной и параллельной машинах обеспечивает огромное преимущество программистам при отладке алгоритма.

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

REAL A(1000,1000), B(1000,1000)
DO J = 2, N
  DO I = 2, N
    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&          + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25
  ENDDO
ENDDO

Директива DISTRIBUTE указывает, как следует разделить массив данных по памятям реальной параллельной машины. В данном случае наиболее естественно распределить первое измерение, поскольку итерации по нему могут выполняться в параллель. Например, программист может распределить данные смежными участками между доступными участками, введя директиву

!HPF$ DISTRIBUTE A(BLOCK,*)

после объявления массива A. В HPF также обеспечиваются другие стандартные схемы распределений, включая CYCLIC, в которой элементы назначаются процессорам циклически, и CYCLIC(K), в которой процессорам циклически назначаются блоки из K элементов. Вообще говоря, схема BLOCK обеспечивает предпочтительное распределение для вычислений с поэлементными коммуникациями ближайших соседей, в то время как варианты схемы CYCLIC допускают более тонкую балансировку некоторых вычислений.

Кроме того, во многих вычислениях (включая приведенный выше пример) для разных массивов данных следует использовать одну и ту же схему размещения данных или родственные схемы. В этих случаях директива ALIGN указывает поэлементное соответствие между массивами. Например, чтобы придать массиву B то же распределение, что и у массива A, программист мог бы использовать директиву

!HPF$ ALIGN B(I,J) WITH A(I,J).

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

При использовании этих директив приведенному выше фрагменту программы соответствовал бы следующий HPF-вариант:

REAL A(1000,1000), B(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,*)
!HPF$ ALIGN B(I,J) WITH A(I,J)
DO J = 2, N
  DO I = 2, N
    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&          + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25
  ENDDO
ENDDO

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

Как показывали проекты Fortran D и Vienna Fortran, особенно сложно было определять распределения данных аргументов подпрограмм. Механизм, который, в конце концов, был принят в HPF, можно кратко описать следующим образом. Формальные аргументы подпрограммы (т.е. переменные, объявленные внутри подпрограммы) можно было ассоциировать с директивами ALIGN и DISTRIBUTE. Если эти директивы полностью специфицировали распределение данных, то действительные аргументы (т.е. объекты, передаваемые вызывающей программой) должны были перераспределяться в соответствии с этой новой схемой распределения данных при обработке вызовы и подвергаться обратному перераспределению при возврате из подпрограммы. Конечно, предполагалось, что, если распределения вызывающей и вызываемой программ находились в соответствии, то компилятор или система поддержки времени исполнение воздержатся от копирования данных, требуемого для их перераспределения. В HPF также определялась система «унаследованных» распределений, при использовании которой распределение формальных аргументов являлось идентичным распределению действительных аргументов. Для такого объявления требовалось наличие явного интерфейса подпрограммы, такого как блок INTERFACE в Fortran 90. В этом случае отсутствовала необходимость в каком-либо копировании, но генерация кода подпрограммы становилась более сложной, поскольку требовалось обрабатывать все возможные входные распределения. На самом деле, эта сложность была настолько велика, что, насколько известно авторам, такой подход не был полностью реализован ни в одном компиляторе.

Кроме директив, определяющих распределения, в HPF имелись специальные директивы, которые можно было использовать для поддержки распознавания параллелизма. Поскольку HPF основывался на Fortran 90, в нем присутствовали операции над массивами, позволяющие явно выразить свойство поэлементного параллелизма. Эти операции были особенно уместными, когда применялись к распределенному измерению; в этом случае компилятор мог (относительно) простым образом управлять как синхронизацией, так и перемещением данных. При использовании нотации операций над массивами, приведенный выше пример мог бы выглядеть следующим образом:

REAL A(1000,1000), B(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,*)
!HPF$ ALIGN B(I,J) WITH A(I,J)
DO J = 2, N
    A(2:N,J) = &
&    (A(2:N,J+1)+2*A(2:N,J)+A(I,J-1))*0.25 &
&   + (B(3:N+1,J)+2*B(2:N,J)+B(1:N-1,J))*0.25
ENDDO

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

REAL A(1000,1000), B(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,*)
!HPF$ ALIGN B(I,J) WITH A(I,J)
DO J = 2, N
  !HPF$ INDEPENDENT
  DO I = 2, N
    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&          + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25
  ENDDO
ENDDO

Использование этой директивы обеспечивало генерацию кода с параллельным циклом любым компилятором HPF, которому была бы представлена подобная программа. Многие компиляторы могли сами обнаруживать возможность параллельного выполнения цикла путем анализа программ, в которых индексные выражения в переменных цикла были линейными, на основе анализа зависимостей и информации о распределениях. Однако директива INDEPENDENT существенно важна для циклов, которые теоретически не поддаются анализу, – например, для циклов, итерирующих над ребрами неструктурированной сетки, которые содержат проиндексированные индексы. Часто у программиста имеется специализированное знание, позволяющее выполнять такие циклы в параллель.

Хотя наличие директивы INDEPENDENT противоречит цели поддержки единственного потока управления, в стандарте удалось обойти эту проблему, определив эту директиву как утверждение, что в цикле отсутствуют зависимости между итерациями, которые могли бы вызвать «гонки данных» (data races); если это утверждение оказывалось неверным, то программа объявлялась не соответствующей стандарту. Таким образом, HPF-программа, соответствующая стандарту, всегда должна была производить одни и те же результаты на скалярной и параллельной машинах. К сожалению, из-за наличия этого средства было невозможно установить во время компиляции, соответствует ли стандарту данная программа.

В HPF также имелся оператор FORALL, позаимствованный из CM Fortran и ранних вариантов Fortran 90, обеспечивающий альтернативные средства для выражения присваивания массивов. Вложенный цикл из примера релаксационного цикла можно было записать следующим образом:

FORALL (J = 2:N, I=2:N) &
&    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&           + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25

Семантически оператор FORALL был идентичен оператору присваивания массивов; он вычислял значения в правой части для всех значений индексов до того, как сохранить результаты в какой-либо области памяти правой части. (Имелся также мультиоператор FORALL, который применял это семантическое правило по очереди ко всем присваиваниям в своем теле.) Наличие явной индексации позволяет использовать FORALL для удобного выражения более широкого набора видов массивов и вычислений, чем это возможно при использовании стандартного присваивания массивов. Это демонстрирует следующий пример:

! Assignment to a diagonal, computed its index
FORALL (I=1:N) A(I,I) = I*I

High Performance Fortran был одним из первых языков, в стандарте которого специфицировалась соответствующая библиотека HPF Library. В библиотеке обеспечивались специальные глобальные операции, такие как sum reduction, gather и scatter, частичные префиксные операции. В библиотеку были включены многие параллельные операции над глобальными массивами, показавшие себя полезными в других языках с распараллеливанием по данными, таких как CM Fortran. Эта библиотека невероятно повысила мощность языка. Спецификация ассоциированной библиотеки теперь является стандартной практикой для языков C, C++ и Java.

Наконец, HPF включал ряд средств, способствующих совместимости и интероперабельности с другими языками и моделями программирования. В частности, поддержка интерфейса EXTRINSIC позволяла вызывать подпрограммы, написанные на других языках, таких как скалярный Fortran и C. Особенно важной была возможность вызова подпрограмм, написанных на основе MPI, что позволяло более эффективно переписывать подпрограммы HPF.