Технологии высокопроизводительных вычислений

6.6. Модели, производные от явного двустороннего обмена сообщениями.

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

6.6.1. Модель библиотек коллективных операций над распределенными массивами.

Наиболее известная и типичная технология этой модели – библиотека ScaLAPACK [19]. Это версия изначально однопроцессорной библиотеки линейной алгебры LAPACK, ориентированная на многопроцессорные вычислители без общей памяти.

На практике прикладные программы часто выполняют вычислительно емкие фрагменты обработки данных путем обращения к стандартным библиотечным функциям. Например, в программе, работающей с векторами и матрицами, скорее всего, будут присутствовать обращения к библиотечным функциям: «перемножить две матрицы», «найти собственные числа», «обратить матрицу» и т. п. Если программа в основном использует массивы, в которых хранятся матрицы и векторы, в качестве аргументов, передаваемых в функции, почему бы не «спрятать» внутрь этих функций весь параллелизм, то есть обращения к MPI? Массивы, вычисляемые в одних функциях и тут же передаваемые в качестве аргументов в другие, теперь будут представлять собой не матрицы и векторы, а их локальные порции, хранящиеся на данном процессоре. Когда все процессоры «хором» (логически одновременно) обращаются к функции «перемножить матрицы», соответствующая функция на каждом процессоре, зная свой номер и общее число участников, «соображает», какая часть работы ей досталась, какие обмены данными с себе подобными следует выполнить. С точки зрения прикладного программиста текст ветви параллельной программы становится очень похожим на текст обычной, последовательной программы (добавляются лишь некоторые «настроечные» обращения к библиотечным функциям в начале текста). Вся логика параллельного взаимодействия, включая всевозможные проверки условий, связанных с передачей тех или иных сообщений, скрыты от прикладного программиста. Массивы, в которых хранятся локальные порции векторов и матриц, можно рассматривать как абстрактные объекты (в духе объектно – ориентированного программирования), библиотечные функции – как методы. Называется этот абстрактный объект, конечно же, распределенным массивом, а метод, реализуемый логически одновременным обращением к одной и той же библиотечной функции на всех процессорах – коллективной операцией.

На практике потребовалось некоторое усложнение этой схемы. Дело в том, что не все распределенные массивы распределены по процессорам одинаково. Например, программисту может потребоваться один массив, распределенный блоками по всем процессорам, кроме нулевого, и еще один, распределенный по всем процессорам, кроме последнего. При выполнении коллективной операции в первом случае нулевой процессор должен «сообразить», что ему ничего делать не надо, во втором случае то же самое должен «понять» последний процессор. Значит, в распределенном массиве должна храниться информация о конкретном виде его распределения по процессорам. Будь библиотека написана на объектно – ориентированном языке, например, C++, и предназначена для использования в программах, написанных на нем же, об этой совершенно естественной детали не стоило бы даже говорить. Довольно естественно, что внутри объекта много всего полезного хранится, на то он и объект, чтобы скрывать в себе детали реализации. Но библиотека ScaLAPACK написана на Фортране и ориентирована, преимущественно, на использование в программах, написанных на нем же, причем проектировалась еще в те времена, когда ни структур, ни указателей в Фортране не было. Поэтому о передаче дополнительных сведений о характере распределения аргумента – массива в коллективную операцию должна заботиться прикладная программа. Сделано это очень простым и понятным для «Фортрановского» программиста способом. По сравнению с функциями LAPACK (однопроцессорными) в аналогичные им функции ScaLAPACK (параллельные) к каждому аргументу – массиву добавляется еще один аргумент – дескриптор распределенного массива. По смыслу это – структура, в которой хранится информация о конкретном формате распределения предыдущего аргумента. В Фортране, в котором структур нет, эта структура стала одномерным целочисленным массивом (длиной 9). В начале работы программы дескрипторы всех распределенных массивов инициализируются обращением к специальной функции «создать распределенный массив». Затем пользователь должен самостоятельно следить, чтобы при использовании в качестве аргумента коллективной операции локальной порции распределенного массива вместе с ней передавался соответствующий дескриптор. Если несколько массивов распределены одинаково, дескриптор у них будет один и тот же.

В связи с эскизно изложенной здесь технологией возникают две проблемы.

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

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

Вторая проблема коренится в самой природе понятия коллективной операции. Она связана с соображениями о двух способах параллельной обработки данных, которые мы высказывали выше, в Разделе 6.1. Легко видеть, что «логически одновременный вызов коллективной операции на всех процессорах» как нельзя лучше отвечает первому способу – собственно параллельной обработке, или, применительно к нашим модельным задачам, методу Якоби. Конвейерный параллелизм (в наших терминах – метод верхней релаксации) в коллективных операциях записывается очень плохо, если записывается вообще – ведь там весь смысл организации передачи данных состоит в том, что все происходит «не в фазе», то есть не одновременно по всем процессорам. Это не страшно, если вся работа конвейера, от запуска до остановки, спрятана внутрь одной коллективной операции. Если же мы хотим самостоятельно выписать конвейерную логику в прикладной программе, опираясь на технологию более мелких коллективных операций, получится, в лучшем случае, довольно тяжеловесно.

Это – известная проблема всех технологий, основанных на понятии коллективной операции, и хорошего решения она не имеет.

Библиотеки коллективных операций обычно сочетают в себе в некоторой пропорции средства проблемно – ориентированные (перемножить матрицы, например) и средства универсальные (скопировать вырезку из распределенного массива). Бывают чисто проблемно – ориентированные библиотеки – как правило, «решатели» разреженных матриц специального вида. К решению систем линейных алгебраических уравнений с такими матрицами сводятся многие численные методы задач математической физики. Бывают библиотеки коллективных операций с высокоразвитой логикой низкоуровневых, универсальных возможностей – всевозможных манипуляций с векторами, матрицами, строками, столбцами и т. п. Наиболее известной на сегодня библиотекой такого рода является библиотека PETSc [20]. В противоположность ScaLAPACK, она написана на C, для представления обрабатываемых данных используется развитая система специальных типов – тип «вектор», тип «матрица» и т. п. Часто складывается ощущение, что со сложностью специально разработанной системы типов данных разработчики несколько перестарались. Для первоначального освоения библиотеки надо обладать заметной обще – программистской  культурой, «Фортрановскому программисту» освоить ее тяжело.

Следующим шагом на пути развития технологии коллективных операций над распределенными массивами было оформление этой технологии в виде специализированных языков (здесь прослеживается аналогия с переходом от технологии «библиотечной» записи односторонних обменов к технологии UPC и co-array Fortran). Например, был разработан язык pFortran [21], очень похожий внешне на co-array Fortran, то есть тоже «Фортран с процессорной размерностью». Однако, основой его являются не односторонние, а двусторонние обмены, точнее, коллективные операции на их базе. Скажем, присваивание вырезок из распределенных массивов, как и в случае библиотек коллективных операций, выступает в роли универсального средства перемещения данных между процессами, но записывается оно теперь не как обращение к библиотечной функции, а как обычный оператор присваивания. Это подразумевает дополнительные ограничения на совместное «поведение» ветвей параллельной программы. Так, если в программе есть оператор присваивания вырезок из распределенных массивов, в ходе выполнения которого  данные как – то перемещаются между 10-ю процессорами, и на одном из этих процессоров данный оператор не выполняется (обходится по «IF»), программа «зависнет». В co-array Fortran такого ограничения нет – там каждый «заинтересованный» процессор односторонним образом выполняет свою часть перемещения данных.

Язык pFortran заметного распространения не получил. Возможно, это объясняется тем, что стандартных технологий создания классов и шаблонов в C++ вполне достаточно, чтобы изготовить для себя (или для заинтересованного коллектива прикладных программистов) такого рода «язык с процессорной размерностью» самостоятельно.

6.6.2. Модель параллельных трансляторов в стиле HPF.

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

Наиболее известной технологией этой модели является HPF (High Performance Fortran, Фортран высокой производительности) [3,22].

              Программа на HPF пишется как однопроцессорная, и представляет собой правильную программу на обычном, «однопроцессорном» Фортране. Она снабжается дополнительными директивами параллельного выполнения, которые с точки зрения транслятора HPF являются операторами языка, а с точки зрения обычного Фортрана – комментариями. Так, в Фортране комментарием является любая строка, содержащая в первой позиции символ “C”. В HPF директивой параллельного выполнения является любая строка, содержащая в первых пяти позициях текст “CHPF$”.

Первоначально предполагалось, что директивы параллельного исполнения будут просты и немногочисленны. В самом деле, если попросить программиста специфицировать необходимое ему распределение обрабатываемых массивов по процессорам, то транслятор самостоятельно «сообразит», как построить параллельную обработку этих массивов (ведь ясно, что данные надо стараться обрабатывать там, где они расположены). Так появились две первых директивы – CHPF$ DISTRIBUTE и CHPF$ ALIGN, и был построен пример для метода Якоби:

          PROGRAM LAPLACE

C Solving the laplace pde

      PARAMETER ( MX = 300, MY = 400 )

      REAL F( 0:MX+1, 0:MY+1 ), DF( 1:MX, 1:MY )

C Массив DF распределяется блоками,

C а массив F – так, чтобы элементы

C F и DF с одинаковыми значениями

C индексов попадали на один и тот

C же процессор:

CHPF$              DISTRIBUTE DF  (BLOCK, BLOCK)

CHPF$              ALIGN  F(I,J)  WITH  DF(I,J)

C

C Витки следующего цикла независимы,

C выполнять на том процессоре, где

C расположена левая часть присваивания:

CHPF$  INDEPENDENT

      DO 2 J = 0, MY+1

       F( 0, J ) = 1.0

       F( MX+1, J ) = 1.0

  2   CONTINUE

CHPF$  INDEPENDENT

      DO 3 I = 1, MX

       F( I, 0 ) = 1.0

       F( I, MY+1 ) = 1.0

3                       CONTINUE

CHPF$  INDEPENDENT  

      DO 4 I = 1, MX

CHPF$  INDEPENDENT

       DO 5 J = 1, MY

       F( I, J ) = 0.0

  5    CONTINUE

  4   CONTINUE

CHPF$  INDEPENDENT

      DO 6 I = 1, MX

CHPF$  INDEPENDENT

       DO 7 J = 1, MY

       DF( I, J ) = 0.0

  7    CONTINUE

  6   CONTINUE

C Iteration

      DO 8 K = 1, 10000

CHPF$  INDEPENDENT

       DO 9 I = 1, MX

CHPF$  INDEPENDENT

        DO 10 J = 1, MY

         DF(I, J) = ( F(I, J+1) + F(I, J-1)

     &               +F(I-1, J) + F(I+1, J) )

     &               *0.25 - F(I, J)

10     CONTINUE

8                       CONTINUE

CHPF$  INDEPENDENT

       DO 11 I = 1, MX

CHPF$  INDEPENDENT

        DO 12 J = 1, MY

         F(I, J) = F(I, J) + DF(I, J)

12     CONTINUE

11    CONTINUE

  8   CONTINUE

       OPEN (10, FILE='F')                                                           

       WRITE (10,*)F                                                                  

       CLOSE (10)

      END

С этой модельной программой любой транслятор HPF справится просто блестяще. С реальными программами, к сожалению, все несколько сложнее.

Уже в этом примере присутствует намек на проблему, с которой пришлось столкнуться впоследствии – директива CHPF$ INDEPENDENT. Эта директива говорит транслятору, что витки данного цикла независимы и, следовательно, их можно «разбросать» по процессорам, вслед за элементами обрабатываемых в них массивов. В данном, простом, случае транслятор мог бы и сам понять, что витки цикла независимы – соответствующие методы анализа программ существуют. Но в реальной программе, например, в цикле могло бы встретиться обращение к подпрограмме, транслируемой отдельно. Вносит ли она зависимость между витками цикла? Это знает программист, транслятор этого знать не может. Значит, нужна директива CHPF$ INDEPENDENT, утверждающая, что витки этого цикла – независимы. Постепенно таких дополнительных директив, необходимость которых не была очевидна на первоначальном этапе, накопилось довольно много. Язык усложнился.