РАМПА - система автоматизации разработки мобильных параллельных программ

____________________________

Задыхайло И.Б., Крюков В.А., Поздняков Л.А

В настоящее время главным направлением повышения производительности ЭВМ является создание многопроцессорных систем с распределенной памятью. В мире имеется уже достаточно большое число таких систем, которые по уровню производительности не уступают традиционным суперЭВМ конвейерного типа. Ведется разработка и реализация проектов создания подобных систем (например, Тега 3D, CM-5, KSR1, Paragon), которые нацелены на достижение к концу 90-х годов терафлопной производительности. Все они представляют собой многопроцессорные системы с распределенной памятью, состоящие из тысяч микропроцессоров, т. е. так называемые системы с массовым параллелизмом. Создание прикладных программ для подобных распределенных систем наталкивается на ряд серьезных трудностей.
Разработка параллельной программы требует выбора или создания подходящего вычислительного метода. При этом для достижения требуемой эффективности приходится многократно проходить путь от спецификации алгоритма к программе на языке программирования, который для параллельных вычислительных систем (ВС) оказывается гораздо более сложным, чем для последовательных.
Возникающие при разработке параллельных программ трудности усугубляются отсутствием задела параллельных алгоритмов и программ, на который мог бы опереться в своей работе программист. В связи с этим возникает настоятельная потребность в использовании для параллельных ВС громадного задела в виде программ и алгоритмов, написанных на традиционных языках последовательного программирования.
Существуют и чисто психологические трудности, связанные с тем, что многим программистам, особенно имеющим большой опыт работы с традиционными ЭВМ, проще иметь дело с последовательными алгоритмами и программами, так что переход к использованию распределенных систем значительно усложняет их работу и существенно замедляет разработку программ. Поэтому желательно дать возможность программисту при работе с многопроцессорными системами пользоваться помимо новых параллельных языков программирования и традиционными последовательными языками, возможно модифицированными для повышения эффективности автоматического распараллеливания.
Разработанные с помощью имеющихся для распределенных систем языковых средств параллельные программы требуют серьезных усилий для переноса не только на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с общей памятью), но и на аналогичные ЭВМ другой конфигурации. Компоновка параллельных программ из более простых, накопление банка общеиспользуемых параллельных программ и программных модулей — это проблемы, требующие исследования и решения.
Наконец, следует отметить отсутствие адекватных методов и средств отладки и мониторинга параллельных программ, а также отсутствие доступных инструментальных
систем, позволяющих организовать для широкого круга специалистов обучение методам распараллеливания.
Чтобы преодолеть указанные трудности и сделать удобным и эффективным использование перспективных вычислительных систем с массовым параллелизмом, в ИПМ РАН развернуты работы по созданию системы автоматизации разработки мобильных параллельных программ — системы РАМПА (Разработка Мобильных Параллельных Алгоритмов).
При этом система РАМПА должна интегрировать три различных подхода к языкам программирования для распределенных ВС, базирующихся соответственно на следующих языках:
параллельного программирования, ориентированных на распределенные системы (основанных на взаимодействии посредством передачи сообщений);
последовательного программирования, расширенных оформляемыми в виде специальных комментариев указаниями о распределении вычислений между процессорами;

Назначение и состав системы РАМПА


Система РАМПА предназначена для создания, отладки и мониторинга параллельных программ для многопроцессорных ЭВМ с распределенной памятью. Основными языками программирования являются Fortran DVM и Норма [1 ]. Программы на этих языках смогут эффективно отображаться не только на распределенные системы различной конфигурации, но и (при наличии соответствующих трансляторов) на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с общей памятью). Эти программы должны легко использоваться в качестве модулей при компоновке более сложных программ, что позволит существенно сократить затраты на разработку новых программ и создать широко доступные банки параллельных алгоритмов.
Система будет обеспечивать также разработку программ на языке Fortran GNS и языках Fortran 77 и С, расширенных средствами библиотеки поддержки параллелизма LIB-GNS, однако в этом случае трудоемкость разработки будет существенно выше, а мобильность создаваемых параллельных программ будет заметно ниже. Кроме того, система позволит на инструментальной ЭВМ (например, на IBM PC) имитировать выполнение программы на ЭВМ различной архитектуры и оценивать эффективность распараллеливания. При этом она должна помочь прикладному программисту осуществлять постепенное преобразование своей последовательной программы в параллельную. Таким образом, система сможет широко использоваться для обучения параллельному программированию.
В состав разрабатываемой системы входят компиляторы с языков Fortran GNS, Fortran DVM и Норма в расширенный язык Fortran 77, библиотеки поддержки параллелизма ЫВ-DVM и LIB-GNS, а также средства отладки и мониторинга.


Язык Fortran GNS

Является расширением языка Fortran 77 [2], базирующимся на концепции абстрактной GENESIS-машины. В соответствии с этой концепцией задача пользователя представляет собой множество подзадач, которые динамически создаются на указанных процессорах распределенной системы и взаимодействуют между собой путем передачи и приема сообщений в любом из трех режимов: синхронном, асинхронном и режиме без ожидания.
Концепция абстрактной GENESIS-машины реализуется в виде библиотеки LIB-GNS, что делает ее доступной и для программ на языках С и Fortran 77.
При реализации библиотеки принят следующий подход к разделению функций между ней и языком описания конфигурации, обычно используемым для распределения подзадач по процессорам распределенной системы: библиотека должна позволять осуществлять распределение программ по разным процессорам некоторой виртуальной параллельной машины (GNS-машины) и организовывать их взаимодействие между собой, а язык конфигурации должен позволять задавать эффективное отображение виртуальной параллельной машины на имеющиеся аппаратные средства.
Виртуальная параллельная машина представляет собой совокупность нескольких многомерных решеток из виртуальных процессоров. При отображении этой машины на физическую ЭВМ несколько виртуальных процессоров могут быть отображены на один физический процессор, что позволяет не только упростить адаптацию программы к конкретной конфигурации аппаратуры, но и расширяет возможности отладки программ.
Возможности, предоставляемые языком Fortran GNS для программирования параллельной задачи, можно кратко описать следующим образом. задача начинает выполняться с запуска указанной в задании на командном языке начальной подзадачи на указанном процессоре. Эта подзадача создает какие-то другие подзадачи на том же самом или на других процессорах;
выполнение задачи завершается в случае окончания выполнения начальной подзадачи или аварийного завершения любой подзадачи. каждая подзадача использует только локальную память, общей с другими подзадачами памяти нет; каждая подзадача может динамически создавать другие подзадачи на любых выделенных задаче процессорах, при этом число подзадач не ограничивается числом процессоров; сообщение содержит список объектов, каждый из которых может быть скаляром, массивом или секцией массива. Списки в операторах передачи и приема должны соответствовать друг другу по числу элементов, а также по типу данных и размерностям каждого элемента;
дескриптором адресата является идентификатор подзадачи. Для широковещательного режима может быть специфицировано множество адресатов;
обеспечивается автоматическая маршрутизация сообщений к любой адресуемой подзадаче;
при асинхронной передаче сообщений выполнение оператора посылки не прерывает подзадачу-отправитель, а выполнение оператора приема прерывает подзадачу до получения соответствующего сообщения. Для того чтобы различать сообщения различных типов они снабжаются так называемыми тегами, имеющими целочисленные значения. Выбор сообщения при выполнении оператора приема делается на основании тега и, возможно, идентификатора отправителя. Бели несколько сообщений от одного отправителя удовлетворяют оператору приема, то берется первое из них; имеются неблокирующие операторы передачи и приема сообщений для реализации однобуферного режима коммуникации. На каждой стороне путем опроса с помощью специальной встроенной функции той логической переменной, которая была указана в операторе, можно проверить; выполнился ли заданный таким оператором обмен;
обеспечивается альтернативный прием асинхронных сообщений различного типа и, возможно, от различных отправителей. имеется множество встроенных функций для параллельного выполнения операций редукции (определение максимального и минимального значений, суммирование и т. п.). Каждая участвующая в операции подзадача обращается к функции с указанием списка идентификаторов всех подзадач-участников. Результат операции возвращается всем этим подзадачам.


Язык Fortran DVM (Distributed Virtual Memory) — FDVH

Предназначен для создания мобильных программ, ориентированных на эффективное выполнение на массово-параллельных ЭВМ с распределенной памятью, но допускающих и достаточно эффективную трансляцию на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с общей памятью). В основу языка положены идея управления распараллеливанием через отображение данных на распределенную память ЭВМ и идея управления доступом к виртуальной памяти. Первая идея известна по работам, связанным с языками Fortran D и HPF [3, 4 ], а вторая была предложена и успешно использована при реализации виртуальной памяти в программах на языке Fortran IV [5 ]. Представим себе, что написание FDVM-программы осуществляется поэтапно, следующим образом.
На первом этапе программирования ведется с использованием только средств языка Fortran 77 (или Fortran 90). Однако семантика этих средств меняется таким образом, что полученная программа рассматривается как программа для некоторой абстрактной многопроцессорной ЭВМ с общей памятью, в которой количество процессоров равно числу переменных (включая элементы массивов) в программе. При этом вычисление и присваивание значений каждой переменной осуществляется на отдельном выделенном для этой переменной процессоре.
Определяемая управляющими конструкциями языка последовательность присваиваний в программе интерпретируется на указанной абстрактной параллельной машине (АПМ1) следующим образом: она полностью определяет порядок присваиваний значений каждой переменной на соответствующем процессоре, и в соответствии с этой исходной последовательностью должна осуществляться синхронизация работы процессоров в тех случаях, когда вычисления на одном процессоре зависят от присваиваний переменным на других процессорах.
На втором этапе программист настраивает свою программу для обеспечения ее выполнения на абстрактной параллельной машине с физически распределенной памятью, доступ к которой осуществляется как к единой логически однородной виртуальной памяти. Будем называть эту машину абстрактной параллельной машиной с распределенной виртуальной памятью (АПМ2). Она представляет собой совокупность связанных между собой многомерных решеток из процессоров, каждый из которых имеет свою локальную память и связан каналами обмена со своими .непосредственными соседями. При этом надо понимать, что доступ к локальной памяти осуществляется на такой машине гораздо эффективнее, чем к памяти других процессоров. Доступ к нелокальной памяти, в свою очередь, зависит от близости соответствующих процессоров. возможность сгруппирования вычислений различных переменных или элементов различных массивов и выделение для всех них одного процессора. Это следует делать в тех случаях, когда выгоднее выполнить последовательно на одном процессоре несколько тесно связанных между собой (по данным) вычислений, чем выполнять их на разных процессорах и тратить много времени на доступ к нелокальной памяти;
возможность указания, что некоторые вычисления выгоднее выполнять многократно на разных процессорах вместо того, чтобы заниматься пересылкой их результатов между процессорами;
возможность указания, что доступ к виртуальной памяти при обращении к некоторым массивам надо производить не поэлементно (по требованию на каждом процессоре), а путем массовых упреждающих пересылок сразу для нескольких процессоров одновременно (и, следовательно, с синхронизацией их работы с завершением вычисления всех требуемых значений некоторой группой процессоров). Поскольку в случае конвейеризации вычислений на разных процессорах такие указания определяют длину ступени одного или сразу нескольких конвейеров, то программист должен найти компромисс между стремлением сократить число обменов и актов синхронизации, с одной стороны, и желанием ускорить появление результатов на выходе конвейера, с другой. И, наконец, программист может изменить направление обмена между владельцем данных и потребителем, указав откуда и куда надо перемещать данные. Это позволяет заменить, например, три "дальних" обмена от процессора А к процессорам X, У и Z, на один "дальний" от А до W и три "близких" — от W до X, от W до У йот У до Z;
возможность снабжения программы указаниями, как транслятор должен отобразить абстрактную машину АПМ2 на виртуальную параллельную машину с распределенной памятью.
главное отличие этой машины от АПМ2 заключается в том, что она должна быть максимально близка по своей архитектуре (количество узлов и связи между ними) к физической объектной ЭВМ или ее части, выделяемой для решения данной задачи). При этом надо подчеркнуть, что виртуальная машина (как и АПМ2) должна представлять собой совокупность многомерных решеток. В системе РАМПА такой виртуальной машиной является GNS-машина. Отображение будет заключаться в том, что транслятор на каждом процессоре GNS-машины разместит вычисления, которые должны были выполняться на каком-то одном или, как правило, на нескольких процессорах АПМ2, а также обеспечит доступ к данным путем их передачи между процессорами посредством операций SEND-RECE1VE. Имеются два принципиальных отличия в подходах к разработке языков Fortran DVM и High Performance Fortran (HPF).
Пользователь FDVM имеет возможность полностью управлять распределением вычислений между процессорами, а пользователь HPF не может даже рассчитывать на то, что ему будет известно, как конкретный компилятор выполнит такое распределение.
Пользователь FDVM может полностью управлять передачей информации между процессорами и ее буферизацией.
Пользователь HPF вынужден полагаться в этих вопросах на "интеллект" компилятора.
Главным следствием этих отличий в подходах является то, что ценой некоторых дополнительных усилий пользователь FDVM может всегда добиться той же эффективности своей программы, которую он мог бы достичь при использовании традиционных средств распараллеливания и обмена сообщениями. При этом переносимость его программы не уменьшается.
Для достижения эффективности FD УМ-программы пользователю предоставляются следующие основные возможности, отсутствующие в HPF.
Средства балансировки вычислительной нагрузки между процессами обеспечивают:
возможность описания групп процессоров, различающихся не только формой, но и составом;
возможность модифицировать или вообще отменить правило собственных вычислений для выполнения на указанных процессорах отмеченных в программе параллельных секций и витков некоторых циклов.
Средства оптимизации межпроцессорных обменов предоставляют возможности задания: Различие подходов FDVM и HPF привело также к различным взглядам на роль оптимизации при компиляции. Отсутствие оптимизирующего компилятора с FDVM не мешает пользователю достичь требуемой эффективности программы, однако наличие такого компилятора во многих случаях позволило бы ему обойтись без применяя описанных выше дополнительных возможностей FDVM.
Первая версия языка Fortran DVM будет являться расширением языка Fortran DVM 77 в соответствии с описанной выше FDVM-моделью посредством изменения семантики некоторых его конструкций и добавления новых конструкций, оформляемых в виде комментариев специального вида. Такой подход позволит транслировать и выполнять FDVM-программы на любых последовательных ЭВМ, на которых в настоящее время пользователи работают со своими программами на языке Fortran 77, что, по мнению авторов, должно существенно облегчить внедрение нового языка.
Выходом транслятора с языка Fortran DVM будет программа на языке Fortran 77, расширенном средствами библиотеки LIB-DVM, которая, в свою очередь, является надстройкой над библиотекой LIB-GNS. Непроцедурный язык Норма предназначен для записи численных методов решения задач математической физики разностными методами.
Главная идея, положенная в основу языка Норма, заключается в том, что полученное специалистом описание решения задачи (расчетные формулы), почти непосредственно используется для ввода его в вычислительную систему и проведения счета.
Таким образом, язык Норма дает специалисту по прикладной математике возможность сформулировать свою задачу в привычных для него терминах. Организация процесса вычислений с учетом архитектуры ЭВМ — это задача транслятора с языка Норма.
Исследования, связанные с разработкой и реализацией непроцедурного языка Норма, показывают, что проблема синтеза программ для класса задач математической физики, решаемых сеточными методами, разрешима в ограничениях, приемлемых с практической точки зрения.
В настоящее время разработаны версии транслятора с языка Норма в последовательный Fortran 77 и векторно-параллельный Fortran VP (расширение языка Fortran 8X).
Язык программирования Норма уже применялся для решения практических задач математической физики, в частности трехмерной задачи обтекания тела вязкой несжимаемой жидкостью.

Средства отладки и мониторинга

Средства отладки и мониторинга ориентированы на работу в следующих трех режимах: псевдовыполнение программы на инструментальной ЭВМ, базирующийся на обработке трассировки, накопленной во время выполнения программы на параллельной ЭВМ;
имитация на инструментальной ЭВМ выполнения программы на параллельной ЭВМ.
Отладка параллельных программ требует гораздо больше усилий от программиста, чем отладка последовательных программ. Это объясняется более сложным восприятием человеком параллельных алгоритмов, а также недетерминизмом выполнения параллельных программ. С этими проблемами уже давно имеют дело разработчики операционных систем реального времени. Поэтому вполне естественно заимствовать из их арсенала такие средства отладки, как трассировка и средства ее автоматизированного анализа, а также средства автоматизированного анализа зафиксированных состояний выполнения программ. Кроме того, важное значение имеют средства визуализации процесса выполнения программ, позволяющие наглядно отобразить структуру параллельной программы, характеристики выполнения ее компонент и их взаимодействие посредством передачи сообщений.
Средства отладки должны обеспечивать возможность многократного повторения хода и результатов выполнения параллельной программы, т. е. позволять при локализации ошибок избегать недетерминизма поведения программ.
Будут реализованы и традиционные средства диалоговой отладки — установка контролируемых точек, визуализация значений указанных переменных и т. п.
Средства мониторинга могут рассматриваться как составная часть средств отладки, поскольку они позволяют программисту глубже понять поведение своей программы. В число таких средств должны входить средства сбора статистики и средства профилирования программ.
В режиме имитации выполнения параллельной программы на инструментальной машине пользователь сможет отлаживать программы, написанные на языках Fortran DVM, Норма, Fortran GNS, а также языках Fortran 77 и С, расширенных средствами библиотеки LIB-GNS.

Кроме того, при отладке на инструментальной машине пользователь сможет осуществлять постепенное преобразование своей последовательной программы в параллельную программу на языке Fortran DVM. При этом добавление в программу управляющих указаний не будет влиять на правильность результатов выполнения программы, а лишь будет отражаться на оценке времени ее работы на параллельной ЭВМ.
Для обеспечения такого режима транслятор будет готовить программу специальным образом, позволяя во время имитации ее выполнения осуществлять динамический анализ 15
Вестник-3
7
Вестник-3
зависимостей операторов по данным и использовать его для проверки правильности управляющих указаний и оценки временных затрат на синхронизацию и пересылку сообщений. При этом пользователь сможет в ходе имитации выполнения программы получить исчерпывающую информацию о своих неверных или неоптимальных указаниях, а также информацию о поведении программы, облегчающую его работу по дальнейшему распараллеливанию этой программы.
Возможность постепенного распараллеливания при гарантированной правильности выполнения программы не только существенно облегчает этот процесс, но и позволяет в некоторых случаях ограничиться только получением оценки эффективности параллельной программы после задания отображения вычислений на процессоры (например, в случае выбора или разработки метода вычислений).


Заключение

В настоящее время разработка системы РАМПА находится в следующем состоянии.
Библиотека LIB-GNS. Разработаны точные спецификации библиотеки и завершаются работы по ее реализации сразу для следующих четырех платформ: мультитранспьютерная система;
распределенная система с узлами, каждый из которых состоит из пары процессоров — транспьютера Т800 и процессора Intel 860; IBM PC под управлением MS-DOS; IBM PC под управлением OS/2.
При этом внутри библиотеки выделена и точно специфицирована машинно-независимая компонента — пакет функций для накопления трассировки.
Транслятор с языка Fortran GNS. Разработано строгое описание языка и первая версия транслятора, работающая на IBM PC под управлением MS-DOS.
Транслятор с языка Fortran DVM. Завершается подготовка точного описания языка и библиотеки LIB-DVM.
Транслятор с языка Норма. Завершается реализация первой версии транслятора, работающей на IBM PC под MS-DOS.
Средства отладки и мониторинга. На IBM PC под MS-DOS реализован режим имитации выполнения параллельных программ на GNS-машине и созданы средства анализа трассировки.

* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант 93-012-628.

ЛИТЕРАТУРА

1. Андрианов А. Н., Е ф и м к и н К. Н., Задыхайло И. Б. Язык Норма. Препринт ИПМ им. М. В. Келдыша АН СССР, № 165,1985.
2. Т h о 1 е С. A.: A proposal for the Abstract GENESIS Machine. In: Report on the GENESIS definition phase October 1988 — June 1989,1989.
3. HiranandaniS., Kennedy К., Tseng С. Compiling Fortran D for MIMD Distributed-Memory Machines. Comm. ACM, Vol. 35, No. 8 (Aug. 1992), 66—80.

  1. DRAFT. High Performance Fortran. Language Specification. Version 1.0, Jan. 25,1993.
4. Коновалов H. А., Крюков В. А.,Любимский Э. 3. Управляемая виртуальная память. Программирование, № 1,1977.
Статья поступила в редакцию в феврале 1994 г.
Институт прикладной математики им. М. В. Келдыша РАН

_________________________________________________________

И. Б. Задыхайло - канд. физ.-мат. наук;
В. А. Крюков - д-р. физ.-мат. наук;
Л. А. Поздняков - канд. физ.-мат. наук

© Информационное общество, 1994, вып. 3, с. 8-15.