И.Б.Задыхайло, В.А.Крюков, Л.А.Поздняков
Институт прикладной математики им. М.В.Келдыша РАН
Оглавление
2. Назначение и состав системы РАМПА.
4.1. Описание модели FDVM.
4.2. Основные отличия Fortran DVM от HPF.
6. Средства отладки и мониторинга.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант 93-012-628.
В настоящее время главным направлением повышения производительности ЭВМ является создание многопроцессорных систем с распределенной памятью. В мире имеется уже достаточно большое число таких систем, которые по уровню производительности не уступают традиционным супер-ЭВМ конвейерного типа. Ведется разработка и реализация проектов создания подобных систем (например, Тera 3D, СМ-5, KSR1, Paragon), которые нацелены на достижение к концу 90-х годов терафлопной производительности. Все они представляют собой многопроцессорные системы с распределенной памятью, состоящие из тысяч микропроцессоров, т.е. так называемые системы с массовым параллелизмом. Cоздание прикладных программ для подобных распределенных систем наталкивается на ряд серьезных трудностей.
Разработка параллельной программы требует выбора или создания подходящего вычислительного метода. При этом для достижения требуемой эффективности приходится многократно проходить путь от спецификации алгоритма к программе на языке программирования, который для параллельных вычислительных систем (ВС) оказывается гораздо более сложным, чем для последовательных.
Возникающие при разработке параллельных программ трудности усугубляются отсутствием задела параллельных алгоритмов и программ, на который мог бы опереться в своей работе программист. В связи с этим возникает настоятельная потребность в использовании для параллельных ВС громадного задела в виде программ и алгоритмов, написанных на традиционных языках последовательного программирования.
Существуют и чисто психологические трудности, связанные с тем, что многим программистам, особенно имеющим большой опыт работы с традиционными ЭВМ, проще иметь дело с последовательными алгоритмами и программами, так что переход к использованию распределенных систем значительно усложняет их работу и существенно замедляет разработку программ. Поэтому желательно дать возможность программисту при работе с многопроцессорными системами пользоваться помимо новых параллельных языков программирования и традиционными последовательными языками, возможно модифицированными для повышения эффективности автоматического распараллеливания.
Разработанные с помощью имеющихся для распределенных систем языковых средств параллельные программы требуют серьезных усилий для переноса не только на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с общей памятью), но и на аналогичные ЭВМ другой конфигурации. Компоновка параллельных программ из более простых, накопление банка общеиспользуемых параллельных программ и программных модулей - это проблемы, требующие исследования и решения.
Наконец, следует отметить отсутствие адекватных методов и средств отладки и мониторинга параллельных программ, а также отсутствие доступных инструментальных систем, позволяющих организовать для широкого круга специалистов обучение методам распараллеливания.
Чтобы преодолеть указанные трудности и сделать удобным и эффективным использование перспективных вычислительных систем с массовым параллелизмом, в ИПМ РАН развернуты работы по созданию системы автоматизации разработки мобильных параллельных программ - системы РАМПА (РАзработка Мобильных Параллельных Алгоритмов).
При этом система РАМПА должна интегрировать три различных подход к языкам пр*ограммирования для распределенных ВС, базирующихся соответственно на:
Система РАМПА предназначена для создания, отладки и мониторинга параллельных программ для многопроцессорных ЭВМ с распределенной памятью. Основными языками программирования являются Fortran DVM и Норма [4]. Программы на этих языках смогут эффективно отображаться не только на распределенные системы различной конфигурации, но и (при наличии соответствующих трансляторов) на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с общей памятью). Эти программы должны легко использоваться в качестве модулей при компоновке более сложных программ, что позволит существенно сократить затраты на разработку новых программ и создавать широко доступные банки параллельных алгоритмов.
Система будет обеспечивать также разработку программ на языке Fortran GNS и языках Fortran 77 и СИ, расширенных средствами библиотеки поддержки параллелизма LIB-GNS, однако в этом случае трудоемкость разработки будет существенно выше, а мобильность создаваемых параллельных программ будет заметно ниже.
Кроме того, система позволит на инструментальной ЭВМ (например, на IBM PC) имитировать выполнение программы на ЭВМ различной архитектуры и оценивать эффективность распараллеливания. При этом она должна помочь прикладному программисту осуществлять постепенное преобразование своей последовательной программы в параллельную.
Таким образом, система сможет широко использоваться для обучения параллельному программированию.
В состав разрабатываемой системы входят компиляторы с языков Fortran DVM, НОРМА и Fortran GNS в расширенный язык Fortran 77, библиотеки поддержки параллелизма LIB-DVM и LIB-GNS, а также средства отладки и мониторинга.
Язык Fortran GNS является расширением языка Fortran 77 в соответствии с предложениями С.A.Thole [3], базирующимися на концепции абстрактной GENESIS-машины. В соответствии с этой концепцией задача пользователя представляет собой множество подзадач, которые динамически создаются на указанных процессорах распределенной системы и взаимодействуют между собой путем передачи и приема сообщений в любом из трех режимов - синхронном, асинхронном и режиме без ожидания.
Концепция абстрактной GENESIS-машины реализуется в виде библиотеки LIB-GNS, что делает ее доступной и для программ на языках СИ и Fortran 77.
При реализации библиотеки принят следующий подход к разделению функций между ней и языком описания конфигурации, обычно используемым для распределения подзадач по процессорам распределенной системы: библиотека должна позволять осуществлять распределение программ по разным процессорам некоторой виртуальной параллельной машины (GNS-машины) и организовывать их взаимодействие между собой, а язык конфигурации должен позволять задавать эффективное отображение виртуальной параллельной машины на имеющиеся аппаратные средства.
Виртуальная параллельная машина представляет собой совокупность нескольких многомерных решеток из виртуальных процессоров. При отображении этой машины на физическую ЭВМ несколько виртуальных процессоров могут быть отображены на один физический процессор, что позволяет не только упростить адаптацию программы к конкретной конфигурации аппаратуры, но и расширяет возможности отладки программ.
Возможности, предоставляемые языком Fortran GNS для программирования параллельной задачи, можно кратко описать следующим образом.
* Инициализация и завершение задачи:
* Свойства подзадачи:
* Передача сообщений:
* Функции редукции:
Язык Fortran DVM (Distributed Virtual Memory) предназначен для создания мобильных программ, ориентированных на эффективное выполнение на массово-параллельных ЭВМ с распределенной памятью, но допускающих и достаточно эффективную трансляцию на ЭВМ другой архитектуры (последовательные, векторно-конвейерные, многопроцессорные с общей памятью). В основу языка положены идея управления распараллеливанием через отображение данных на распределенную память ЭВМ и идея управления доступом к виртуальной памяти. Первая идея известна по работам, связанным с языками Fortran D и HPF [1,2], а вторая была предложена и успешно использована при реализации виртуальной памяти в программах на языке Fortran IV [5].
С целью упростить изложение представим себе, что написание FDVM-программы осуществляется поэтапно следующим образом.
На первом этапе программирование ведется с использованием только средств языка Fortran 77 (или Fortran 90). Однако семантика этих средств меняется таким образом, что полученная программа рассматривается как программа для некоторой абстрактной многопроцессорной ЭВМ с общей памятью, в которой количество процессоров равно числу переменных (включая элементы массивов) в программе. При этом вычисление и присваивание значений каждой переменной осуществляется на отдельном выделенном для этой переменной процессоре.
Определяемая управляющими конструкциями языка последовательность присваиваний в программе интерпретируется на указанной абстрактной параллельной машине (АПМ1) следующим образом.
Во-первых, она полностью определяет порядок присваиваний значений каждой переменной на соответствующем процессоре, а во-вторых, в соответствии с этой исходной последовательностью должна осуществляться синхронизация работы процессоров в тех случаях, когда вычисления на одном процессоре зависят от присваиваний переменным на других процессорах.
На втором этапе программист настраивает свою программу для выполнения на абстрактной параллельной машине с физически распределенной памятью, доступ к которой осуществляется как к единой логически однородной виртуальной памяти. Будем называть эту машину абстрактной параллельной машиной с распределенной виртуальной памятью (АПМ2). Она представляет собой совокупность связанных между собой многомерных решеток из процессоров, каждый из которых имеет свою локальную память и связан каналами обмена со своими непосредственными соседями. При этом надо понимать, что доступ к локальной памяти осуществляется на такой машине гораздо эффективнее, чем к памяти других процессоров. Доступ к нелокальной памяти, в свою очередь, зависит от близости соответствующих процессоров.
Для настройки программы на АПМ2 программисту предоставляются следующие возможности.
Во-первых, он может сгруппировать вычисления различных переменных или элементов различных массивов и выделить для всех них один процессор. Это следует делать в тех случаях, когда выгоднее выполнить последовательно на одном процессоре несколько тесно связанных между собой (по данным) вычислений, чем выполнять их на разных процессорах и тратить много времени на доступ к нелокальной памяти.
Во-вторых, он может указать, что некоторые вычисления выгоднее выполнять многократно на разных процессорах вместо того, чтобы заниматься пересылкой их результатов между процессорами.
В-третьих, можно указать, что доступ к виртуальной памяти при обращении к некоторым массивам надо производить не поэлементно (по требованию на каждом процессоре), а путем массовых упреждающих пересылок сразу для нескольких процессоров одновременно (и, следовательно, с синхронизацией их работы с завершением вычисления всех требуемых значений некоторой группой процессоров). Поскольку в случае конвейеризации вычислений на разных процессорах такие указания определяют длину ступени одного или сразу нескольких конвейеров, то программист должен найти компромисс между стремлением сократить число обменов и актов синхронизации, с одной стороны, и желанием ускорить появление результатов на выходе конвейера, с другой.
И, наконец, программист может изменить направление обмена между владельцем данных и потребителем, указав откуда и куда надо перемещать данные. Это позволяет заменить, например, три "дальних" обмена от процессора А к процессорам X,Y и Z, на один "дальний" от А до W и три "близких" - от W до X, от W до Y и от Y до Z.
На четвертом, заключительном этапе программист снабжает программу указаниями, как транслятор должен отобразить абстрактную машину АПМ2 на виртуальную параллельную машину с распределенной памятью.
Главное отличие этой машины от АПМ2 заключается в том, что она должна быть максимально близка по своей архитектуре (количество узлов и связи между ними) к физической объектной ЭВМ или ее части, выделяемой для решения данной задачи. При этом надо подчеркнуть, что виртуальная машина (как и АПМ2) должна представлять собой совокупность многомерных решеток. В системе РАМПА такой виртуальной машиной является GNS-машина. Отображение будет заключаться в том, что транслятор на каждом процессоре GNS-машины разместит вычисления, которые должны были выполняться на каком-то одном или, как правило, на нескольких процессорах АПМ2, а также обеспечит доступ к данным путем их передачи между процессорами посредством операций SEND-RECEIVE.
Имеются два принципиальных отличия в подходах к разработке языков Fortran DVM и High Performance Fortran.
Во-первых, пользователь FDVM имеет возможность полностью управлять распределением вычислений между процессорами, а пользователь HPF не может даже рассчитывать на то, что ему будет известно, как конкретный компилятор выполнит такое распределение.
Во-вторых, пользователь FDVM может полностью управлять передачей информации между процессорами и ее буферизацией.
Пользователь HPF вынужден полагаться в этих вопросах на "интеллект" компилятора.
Главным следствием этих отличий в подходах является то, что ценой некоторых дополнительных усилий пользователь FDVM может всегда добиться той же эффективности своей программы, которую он мог бы достичь при использовании традиционных средств распараллеливания и обмена сообщениями. При этом переносимость его программы не уменьшается.
Для достижения эффективности FDVM-программы пользователю предоставляются следующие основные возможности, отсутствующие в HPF.
* Средства балансировки вычислительной нагрузки между процессорами
* Средства оптимизации межпроцессорных обменов
Различие подходов FDVM и HPF привело также к различным взглядам на роль оптимизации при компиляции. Отсутствие оптимизирующего компилятора с FDVM не мешает пользователю достичь требуемой эффективности программы, однако наличие такого компилятора во многих случаях позволило бы ему обойтись без применения описанных выше дополнительных возможностей FDVM.
Первая версия языка Fortran DVM будет являться расширением языка Fortran 77 в соответствии с описанной выше FDVM-моделью посредством изменения семантики некоторых его конструкций и добавления новых конструкций, оформляемых в виде комментариев специального вида. Такой подход позволит транслировать и выполнять FDVM-программы на любых последовательных ЭВМ, на которых в настоящее время пользователи работают со своими программами на языке Fortran 77, что по мнению авторов должно существенно облегчить внедрение нового языка.
Выходом транслятора с языка Fortran DVM будет программа на языке Fortran 77, расширенном средствами библиотеки LIB-DVM, которая, в свою очередь, является надстройкой над библиотекой LIB-GNS.
Непроцедурный язык Норма предназначен для записи численных методов решения задач математической физики разностными методами.
Главная идея, положенная в основу языка Норма, заключается в том, что полученное прикладным специалистом описание решения задачи (расчетные формулы), почти непосредственно используется для ввода его в вычислительную систему и проведения счета.
Таким образом, язык Норма дает прикладному математику возможность сформулировать свою задачу в привычных для него терминах. Организация процесса вычислений с учетом архитектуры ЭВМ - это задача транслятора с языка Норма.
Исследования, связанные с разработкой и реализацией непроцедурного языка Норма показывает, что проблема синтеза программ для класса задач математической физики, решаемых сеточными методами, разрешима в ограничениях, приемлемых с практической точки зрения.
В настоящее время разработаны версии транслятора с языка Норма в последовательный Fortran 77 и в векторно-параллельный Фортран ВП (расширение языка Fortran 8Х).
Язык программирования Норма уже применялся для решения практических задач математической физики, в частности, трехмерной задачи обтекания тела вязкой несжимаемой жидкостью.
Средства отладки и мониторинга ориентированы на работу в следующих трех режимах.
Отладка параллельных программ требует гораздо больше усилий от программиста, чем отладка последовательных программ. Это объясняется более сложным восприятием человеком параллельных алгоритмов, а также недетерминизмом выполнения параллельных программ. С этими проблемами уже давно имеют дело разработчики операционных систем и систем реального времени. Поэтому вполне естественно заимствовать из их арсенала такие средства отладки, как трассировка и средства ее автоматизированного анализа, а также средства автоматизированного анализа зафиксированных состояний выполнения программ. Кроме того, важное значение имеют средства визуализации процесса выполнения программ, позволяющие наглядно отобразить структуру параллельной программы, характеристики выполнения ее компонент и их взаимодействие посредством передачи сообщений.
Средства отладки должны обеспечивать возможность многократного повторения хода и результатов выполнения параллельной программы, т.е. позволять при локализации ошибок избегать недетерминизма поведения программ.
Будут реализованы и традиционные средства диалоговой отладки - установка контролируемых точек, визуализация значений указанных переменных, и т.п.
Средства мониторинга могут рассматриваться как составная часть средств отладки, поскольку они позволяют программисту глубже понять поведение своей программы. В число таких средств должны входить средства сбора статистики и средства профилирования программ.
В режиме имитации выполнения параллельной программы на инструментальной машине пользователь сможет отлаживать программы, написанные на языках Fortran DVM, НОРМА, Fortran GNS, а также языках Fortran 77 и СИ, расширенных средствами библиотеки LIB-GNS.
Кроме того, при отладке на инструментальной машине пользователь сможет осуществлять постепенное преобразование своей последовательной программы в параллельную программу на языке Fortran DVM. При этом добавление в программу управляющих указаний не будет влиять на правильность результатов выполнения программы, а лишь будет отражаться на оценке времени ее работы на параллельной ЭВМ.
Для обеспечения такого режима транслятор будет готовить программу специальным образом, позволяя во время имитации ее выполнения осуществлять динамический анализ зависимостей операторов по данным и использовать его для проверки правильности управляющих указаний и оценки временных затрат на синхронизацию и пересылку сообщений. При этом пользователь сможет в ходе имитации выполнения программы получить исчерпывающую информацию о своих неверных или неоптимальных указаниях, а также информацию о поведении программы, облегчающую его работу по дальнейшему распараллеливанию этой программы.
Возможность постепенного распараллеливания при гарантированной правильности выполнения программы не только существенно облегчает этот процесс, но и позволяет в некоторых случаях ограничиться только получением оценки эффективности параллельной программы после задания отображения вычислений на процессоры (например, в случае выбора или разработки метода вычислений).
В настоящее время разработка системы РАМПА находится в следующем состоянии.
* Библиотека LIB-GNS.
- мультитранспьютерная система;
- распределенная система с узлами, каждый из которых состоит из пары процессоров - транспьютера Т800 и процессора Intel 860;
- IBM PC под управлением MS-DOS;
- IBM PC под управлением OS/2.
* Транслятор с языка Fortran GNS.
* Транслятор с языка Fortran DVM.
* Транслятор с языка Норма.
* Средства отладки и мониторинга.