Н.А.Коновалов, В.А.Крюков, С.Н.Михайлов, А.А.Погребцов
Институт прикладной математики им М.В.Келдыша РАН
3.1. Описание абстрактной параллельной машины (АПМ).
3.2. Разработка программы для АПМ.
3.3. Задание расположения данных в памяти
3.4. Управление доступом к нелокальным данным.
3.5. Задание отображения абстрактной параллельной машины на виртуальную параллельную машину (ВПМ)
4. Сравнение модели FDVM с другими известными моделями.
4.1. Модели, базирующиеся на передаче сообщений.
4.2. Модели, базирующиеся на использовании разделяемой памяти.
4.3. Модель HPF.
Предлагается новая языковая модель, которая должна позволить легко выражать функциональный параллелизм и параллелизм данных в научных и инженерных приложениях для ЭВМ с массовым параллелизмом. Модель объединяет в себе основные достоинства моделей PCF Fortran и HPF и ориентирована на создание мобильных приложений, которые смогут эффективно выполняться на ЭВМ с распределенной памятью и ЭВМ с разделяемой памятью. Модель поддерживает разработку библиотек стандартных параллельных программ и конструирование параллельных программ из параллельных модулей. Модель обеспечивает также средства для динамической балансировки вычислительной нагрузки процессоров.
Ключевые слова: мобильные параллельные программы, ЭВМ с массовым параллелизмом, распределенная память, разделяемая память, динамическая балансировка нагрузки.
Эта работа частично поддерживается Российским Фондом Фундаментальных Исследований, грант N 93-012-528.
Работы по созданию языка Fortran DVM (Distributed Virtual Memory) и соответствующих инструментальных средств ведутся в ИПМ им. М.В.Келдыша РАН в рамках проекта РАМПА [1]. Главной целью этого проекта является автоматизация разработки мобильных прикладных программ для проведения научных и инженерных расчетов на массово-параллельных ЭВМ с распределенной памятью.
Cоздание прикладных программ для подобных распределенных систем наталкивается на ряд серьезных трудностей, главной из которых является проблема мобильности. При этом следует выделить два аспекта этой проблемы.
Во-первых, разрабатываемые с помощью имеющихся для распределенных систем языковых средств параллельные программы требуют серьезных усилий для переноса не только на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с разделяемой памятью), но и на аналогичные ЭВМ другой конфигурации.
Во-вторых, компоновка параллельных программ из более простых, накопление банка общеиспользуемых параллельных программ и программных модулей - это вопросы, которые до сих пор не нашли удовлетворительного решения.
Пока не решена проблема мобильности, трудно расчитывать на широкое использование распределенных систем. Поэтому главной целью разработки языка Fortran DVM (FDVM) является обеспечение мобильности параллельных программ.
Кроме того, язык FDVM должен обеспечивать создание эффективных программ для ЭВМ с массовым параллелизмом. На таких ЭВМ эффективность определяется прежде всего сбалансированностью вычислительной нагрузки процессоров и временными затратами на межпроцессорные обмены и синхронизацию.
В основу языка положены следующие основные идеи.
* Параллельное выполнение программы должно осуществляться в соответствии с ее потенциальным параллелизмом, явно описанным пользователем с помощью специальных директив или параллельных конструкций. Метод автоматического распараллеливания, даже усиленный указаниями о распределении данных, имеет очень существенный и принципиальный недостаток - отсутствие явной (и ясной) модели параллельного выполнения не позволяет предоставить пользователю удобные средства анализа поведения его программы и повышения эффективности ее выполнения. Лля описания потенциального параллелизма программы вполне естественно использовать средства, предложенные в стандарте PCF Fortran [2] в результате обобщения огромного опыта, полученного при работе на многопроцессорных ЭВМ с разделяемой памятью. При этом, конечно, необходимо адаптировать эти средства к особенностям ЭВМ с распределенной памятью.
* Для ЭВМ с неоднородной памятью (в их число входят распределенные системы, включая и ЭВМ с логически разделяемой но физически распределенной памятью) необходимо предоставить пользователю возможность управлять расположением данных в памяти и распределением вычислений между процессорами. Для этого вполне подходят средства, предложенные в языке HPF [3].
* Для ЭВМ с неоднородной памятью существенное влияние на эффективность выполнения программы может оказать предоставление пользователю средств управления доступом к виртуальной памяти, алогичных тем, которые были предложены и успешно использованы при реализации виртуальной памяти в программах на языке Fortran для ЭВМ БЭСМ-6 [4].
* Наконец, в языке должны быть средства, позволяющие пользователю обеспечить динамическую балансировку вычислительной нагрузки между процессорами.
С целью упростить изложение представим себе, что написание FDVM-программы осуществляется поэтапно следующим образом.
Описание параллельной машины необходимо пользователю для управления отображением вычислений на процессоры, а также для управления размещением данных в случае ЭВМ с распределенной памятью. Заметим, что поскольку PCF Fortran ориентирован на однородные многопроцессорные ЭВМ с разделяемой памятью, то пользователю предоставляются только ограниченные возможности управления количеством процессоров, выделяемых для выполнения различных частей программы. В случае распределенных систем отображение вычислений на процессоры требует более аккуратного планирования и не может осуществляться с той же степенью динамизма, которая допустима на ЭВМ с разделяемой памятью.
Абстрактная параллельная машина вводится для того, чтобы пользователь мог при отображении на нее своей программы раскрыть весь ее внутренний потенциальный параллелизм. Поэтому АПМ представляет собой иерархию абстрактных параллельных подсистем, каждая из которых может являться многомерным массивом подсистем следующего уровня иерархии. При этом допускается одновременное существование нескольких вариантов представления каждой подсистемы.
АПМ может быть описана статически, либо может быть построена динамически при выполнении программы. Динамическое построение необходимо при работе с динамическими массивами, а также для организации использования библиотек стандартных параллельных программ, хранящихся в виде объектных модулей и не требующих никакой специальной предварительной настройки.
При написании программы пользователь исходит из следующей модели ее выполнения.
В момент запуска программы существует единственная ее ветвь (поток управления), которая начинает свое выполнение на АПМ с первого оператора программы.
При входе в параллельную конструкцию (параллельный цикл или группу параллельных секций) ветвь разбивается на некоторое количество параллельных ветвей, каждая из которых выполняется на указанной подсистеме АПМ. Причем, ветвление осуществляется в соответствии с указанным вариантом представления текущей подсистемы в виде массива подсистем следующего уровня иерархии.
При выходе из параллельной конструкции все ветви сливаются в ту же самую ветвь, которая выполнялась до входа в параллельную конструкцию. В этот момент все изменения разделяемых переменных, которые были произведены параллельными ветвями, становятся виднывсем процессорам, выполняющим данную ветвь.
Для устранения формальной зависимости параллельных ветвей по данным, препятствующей их независимому выполнению, некоторые переменные могут быть объявлены приватными. В этом случае для каждой параллельной ветви заводится своя копия (неинициализированная) таких переменных, которая используется независимо от других. Описание приватных данных, кроме того, сужает область существования данных и позволяет избавиться от ненужной работы по приведению их в согласованное состояние.
Все остальные данные, используемые параллельными ветвями считаются разделяемыми. Режим доступа к ним в параллельных ветвях должен быть специфицирован. Возможны следующие режимы:
В последнем случае программист должен осуществить явную синхронизацию параллельных ветвей. Для синхронизации используются события, синхронизаторы арифметическими последовательностями, а также критические секции (PCF Fortran).
Теперь уточним, что означают слова "ветвь выполняется на подсистеме". Их можно интерпретировать двумя различными способами, в зависимости от того, как пользователь представляет себе АПМ. В случае машины с разделяемой памятью последовательные части программы (до входа в параллельную конструкцию и после выхода из нее) выполняются на одном, "головном" процессоре подсистемы. В случае машины с распределенной памятью каждый процессор подсистемы может выполнять одну и ту же последовательность операторов для того, чтобы обладать своей собственной копией некоторых переменных.
Для распределенной системы пользователь должен задать расположение данных в локальных памятях процессоров АПМ. Это осуществляется посредством выравнивания массивов между собой и отображением их на подсистему АПМ в соответствии с указанным ее представлением в виде многомерного массива подсистем следующего уровня иерархии (аналогично ALIGN в HPF). При этом допускается сжимающее отображение (все элементы какого-то измерения отображаются на одну подсистему) и размножающее отображение (один элемент массива дублируется на многих подсистемах.
Дублирование данных производится программистом в тех случаях, когда он считает, что их вычисления выгоднее выполнять многократно на разных процессорах вместо того, чтобы заниматься пересылкой этих данных между процессорами. По умолчанию, все данные, о расположении которых пользователь указаний не задал, дублируются по всем процессорам той подсистемы, на которой выполняется ветвь - владелец этих данных (в которой они описаны или созданы динамически).
Пользователь может указать, что доступ к виртуальной памяти при обращении к некоторым массивам надо производить не поэлементно (по требованию на каждом процессоре), а путем массовых упреждающих пересылок сразу для нескольких витков цикла одновременно (после завершения вычисления всех требуемых значений соответствующими процессорами). В случае конвейеризации вычислений на разных процессорах программист должен найти компромисс между стремлением сократить число обменов и актов синхронизации, с одной стороны, и желанием ускорить появление результатов на выходе конвейера, с другой.
Кроме того, пользователь может задать режим буферизации нелокальных данных в памяти процессоров, что позволит избежать лишних межпроцессорных обменов при повторных обращениях к ним.
Виртуальной параллельной машиной называется та машина, которая предоставляется задаче пользователя аппаратурой и базовым системным программным обеспечением. Эта машина по своей структуре и количеству процессоров должна быть близка к реальной параллельной ЭВМ или ее части. Для распределенной ЭВМ примером такой машины может служить MPI-машина [5].
Как и АПМ, виртуальная машина также может быть представлена в виде иерархии подсистем. При этом должен быть однозначно определен состав каждой подсистемы - номера входящих в нее виртуальных процессоров. Причем любая подсистема может содержать только те процессоры, которые входят в состав материнской подсистемы.
Отображение заключается в задании соответствия между подсистемами АПМ и ВПМ, в результате которого каждая подсистема АПМ будет отображена на подсистему или процессор ВПМ. Предлагается обеспечить три способа отображения АПМ на ВПМ.
Во-первых, отображение может задаваться с помощью языковых конструкций, обрабатываемых на стадии компиляции (аналогично DISTRIBUTE в HPF). Этот способ является наименее гибким, но зато наиболее эффективным с точки зрения накладных расходов во время выполнения программы.
Во-вторых, отображение может быть задано через операционную систему (например, через параметры командной строки UNIX).
В-третьих, оно может быть произведено динамически при выполнении программы с помощью специальных операторов (аналогичных REDISTRIBUTE в HPF).
Этот способ отображения, а также возможности работы с динамическими массивами и средства динамического построения АПМ и ВПМ, необходим пользователю для осуществления динамической балансировки нагрузки.
Сравним модель FDVM с другими моделями, которые могут использоваться на распределенных системах.
Эти модели в основном и используются в настоящее время. В этих моделях программист явно распределяет данные и вычисления по процессорам и обеспечивает взаимодействие процессов посредством передачи сообщений. На первый взгляд, такой подход позволяет достигнуть максимальной эффективности выполнения программы. Однако, это не всегда верно по следующим причинам.
* Очень значительное влияние на эффективность может оказывать выполнение функций редукции (SUM,MAX,MIN). Их оптимальное программирование на прикладном уровне, как правило, просто невозможно. Встроенных функций редукции большинство моделей, включая PVM [6], не имеют, хотя в MPI и EXPRESS [7] такие возможности программисту предоставлены.
* Трудно на прикладном уровне организовать эффективный доступ к файлам, если распределенная система имеет несколько путей доступа к магнитным дискам.
* Эффективность выполнения программы на ЭВМ с массовым параллелизмом существенно зависит от балансировки нагрузки процессоров, а она в этих моделях очень затруднена.
Кроме того, необходимо отметить, что хотя эти модели достаточно удобны для выражения функционального параллелизма, однако, при реализации параллелизма данных возникают серьезные затруднения из-за отсутствия глобального адресного пространства (пространства имен).
Главным же недостатком рассматриваемых моделей является жесткая привязка программ к архитектуре ЭВМ, включая количество процессоров и связей между ними. Разработка библиотечных программ представляется прктически неразрешимой проблемой.
Несомненным достоинством этих моделей является отсутствие необходимости создания специальных компиляторов и возможность использования этих моделей в традиционных языках посредством их расширения библиотечными функциями.
Эти модели исходят из наличия глобального адресного пространства. Наиболее яркими представителями таких моделей являются PCF Fortran и Fortran S [8].
Хотя в стандарте PCF Fortran и указано, что он годится не только для ЭВМ с разделяемой памятью, но и для ЭВМ с распределенной памятью, однако это заявление скорее относится к таким распределенным системам, как CRAY T3D и CONVEX SPP1000, которые относятся к классу систем с распределенной разделяемой памятью и обеспечивают доступ к нелокальным данным практически также быстро, как к локальным.
Использование этой модели на большинстве распределенных систем практически невозможно из-за отсутствия возможностей управления отображением данных и вычислений на процессоры.
Модель языка Fortran S предоставляет пользователю средства отображения вычислений на процессоры. Однако, использование в ней программно реализуемой виртуальной памяти без средств ее управления со стороны программиста неизбежно вызовет проблемы с эффективностью выполнения серьезных приложений.
Достоинством этих моделей (впрочем, как и предлагаемой модели FDVM) является относительная простота компиляции.
Эта модель основана на наличии глобального пространства имен и управлении пользователем распределением данных по локальным памятям процессоров. Модель поддерживает параллелизм данных и не поддерживает функциональный параллелизм.
Однако мы сконцентрируем внимание на следующих двух принципиальных отличиях в подходах к разработке языков Fortran DVM и High Performance Fortran.
Во-первых, пользователь FDVM имеет возможность полностью управлять распределением вычислений между процессорами, а пользователь HPF не может даже рассчитывать на то, что ему будет известно, как конкретный компилятор выполнит такое распределение.
Во-вторых, пользователь FDVM может полностью управлять передачей информации между процессорами и ее буферизацией. Пользователь HPF вынужден полагаться в этих вопросах на "интеллект" компилятора.
Главным следствием этих отличий в подходах является то, что ценой некоторых дополнительных усилий пользователь FDVM может всегда добиться той же эффективности своей программы, которую он мог бы достичь при использовании традиционных средств распараллеливания и обмена сообщениями. При этом переносимость его программы не уменьшается.
Для достижения эффективности FDVM-программы пользователю предоставляются следующие основные возможности, отсутствующие в HPF.
* Средства балансировки вычислительной нагрузки между процессорами
* Средства оптимизации межпроцессорных обменов
Различие подходов FDVM и HPF привело также к различным взглядам на роль оптимизации при компиляции. Отсутствие оптимизирующего компилятора с FDVM не мешает пользователю достичь требуемой эффективности программы, однако наличие такого компилятора во многих случаях позволило бы ему обойтись без применения описанных выше дополнительных возможностей FDVM.
По мнению авторов, успех данной разработки зависит прежде всего от того, насколько удачно будет разработана модель FDVM, которая, с одной стороны должна удовлетворять поставленным целям (мобильность и эффективность прикладных программ), а, с другой стороны, должна быть понятна прикладному программисту и быть относительно проста для реализации. Поэтому все усилия разработчиков были сконцентрированы на проектировании этой модели, которая в течение 1993-1994 годов трижды подверглась существенным пересмотрам.
В настоящее время завершается проектирование системы поддержки выполнения параллельной программы (библиотека LIB-DVM). Именно эта система несет на себе основную тяжесть реализации предлагаемой DVM-модели.
Следующим этапом разработки языка станет отработка предложенной модели посредством ручного программирования (возможно с использованиемпростейшегоэкспериментального компилятора-препроцессора) нескольких прикладных программ на языках Fortran 77 или С, расширенных средствами LIB-DVM.
Только после завершения этого этапа планируется разработка формального описания языка FDVM. Если к этому моменту в языке HPF появятся средства функционального распараллеливания и динамической балансировки нагрузки, то это будет соответствующим образом отражено в FDVM.