Целью диссертационной работы является исследование возможностей эффективного выполнения SPMD-программ в среде Java в различных аппаратных окружениях и реализация первой версии прототипа инструментальной системы ParJava, поддерживающей разработку масштабируемых, переносимых, объектно-ориентированных параллельных программ для параллельных вычислительных систем с распределенной памятью. Реализация инструментальной системы в полном объеме должна опираться на исследования методики применения средств динамического анализа программ, выявляющих возможности распараллеливания программы, методов преобразования параллельных программ, обеспечивающих высокую степень параллелизма вычислений, методов отладки, тестирования и мониторинга параллельных программ. Проведение перечисленных исследований не входило в задачу данной диссертации. Разработанный прототип инструментальной системы ParJava носит предварительный характер и должен рассматриваться как базовое средство, которое обеспечит проведение перечисленных исследований.
Актуальность. В настоящее время в связи с появлением дешевого коммуникационного оборудования все более широкое распространение получают параллельные вычислительные системы с распределенной памятью (кластеры). Такие системы установлены во многих учебных заведениях. Параллельные программы применяются для решения широкого класса задач. Практически все новые вычислительные системы являются параллельными. В связи с этим возникает проблема разработки большого количества параллельных программ. Современные системы параллельного программирования не обеспечивают переносимости параллельных программ с сохранением их свойств. На практике это означает, что каждая параллельная программа разрабатывается для конкретной вычислительной системы, а ее перенос на другую систему требует дополнительных затрат, сравнимых с затратами на разработку новой программы. Это делает невозможным организацию серийного производства параллельных программ, резко повышая их стоимость. Среда ParJava поддерживает разработку переносимых параллельных программ, предоставляя основу для решения перечисленных проблем. После полной реализации среды ParJava можно будет разрабатывать эффективно-переносимые параллельные программы.
Средой программирования, которая обеспечивает полную переносимость для последовательных программ, является среда Java. Утверждается, что программа, написанная с использованием спецификаций системы Java и откомпилированная на одной из платформ, работает на любой программно-аппаратной платформе, на которой установлена система Java, без каких-либо модификаций или преобразований. Именно поэтому, в качестве среды реализации ParJava была выбрана среда Java. Однако программы, разработанные в среде Java, выполняются медленнее, чем аналогичные программы на C/C++. С точки зрения разработки параллельных программ замедление происходит также вследствие использования механизма сериализации при обмене данными в сети JavaVM. В среде ParJava необходимо было предусмотреть средства позволяющие компенсировать указанные недостатки.
Основные результаты. В диссертации получены следующие результаты:
• Создана инструментальная среда ParJava, поддерживающая разработку масштабируемых переносимых параллельных программ для параллельных вычислительных систем с распределенной памятью.
• В составе среды ParJava разработаны и реализованы библиотеки интерфейсов и классов, обеспечивающие организацию SPMD-вычислений.
• Обеспечена возможность моделирования однородной сети JavaVM на неоднородной вычислительной сети с балансировкой нагрузки, что позволяет использовать локальные сети в качестве инструментальной среды для разработки и отладки масштабируемых параллельных программ.
• Исследованы возможности эффективного выполнения параллельных программ на вычислительных системах с распределенной памятью. Получены теоретические оценки ускорения параллельных программ при их выполнении на однородных и неоднородных компьютерных сетях, подтвержденные численными экспериментами. Из оценок следует, что параллельные вычисления на неоднородных компьютерных сетях возможны лишь для узкого класса задач.
• Спроектированы специализированные инструментальные средства (анализаторы и преобразователи программ), поддерживающие разработку и отладку масштабируемых SPMD-программ.
На защиту выносится.
• Инструментальная интегрированная среда ParJava, поддерживающая разработку масштабируемых переносимых параллельных программ для вычислительных систем с распределенной памятью.
• Теоретические оценки ускорения параллельных программ при их выполнении на однородных и неоднородных компьютерных сетях и результаты численных экспериментов, подтверждающие эти оценки.
• Специализированные инструментальные средства (анализаторы и преобразователи программ), поддерживающие разработку и отладку масштабируемых параллельных Java-nporpaMM.
Практическая значимость работы определяется тем, что в его рамках была создана и помещена в Internet для свободного доступа инструментальная среда ParJava. Среда ParJava является основой для реализации различных объектных моделей параллельного программирования высокого уровня (например, DPJ, DVM).
Среда ParJava используется для обучения студентов кафедры системного программирования факультета ВМиК МГУ и кафедры системного программирования МФТИ. В рамках среды ParJava выполняются курсовые и дипломные работы.
Апробация работы.
Основные результаты работы опубликованы в статьях [1] - [9J. Результаты работы обсуждались на следующих конференциях и семинарах:
• Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения», г. Черноголовка, 30 октября — 2 ноября. 2000 г.
• Международном семинаре «Супервычисления и математическое моделирование», г. Саров, 13−15 июня 2001 г.
• Международной конференции «Parallel Computing Technologies (РаСТГ. Novosibirsk, September 3−7, 2001.
• Международной, конференции «Computer Science and Information Technologies (CSIT)», Yerevan, September 17 — 20, 2001.
• Международной конференции «Parallel Computations and Control Problems (PACO'2001)», Moscow, October 2−4, 2001.
Подготовлена страница ParJava в Internet (www.ispras.ru/~javap). Она включает переводы на английский язык публикаций 1−9, возможность загрузки программного обеспечения среды и некоторые другие материалы.
Краткое содержание работы. В разделе 2 приводятся обзоры аппаратных средств параллельных вычислительных систем с распределенной памятью и систем параллельного программирования, а также обсуждаются результаты исследований по проблеме оптимального выполнения однородных и неоднородных параллельных циклов на однородных и неоднородных вычислительных системах с распределенной памятью.
В разделе 3 вводятся определения используемых терминов (п. 3.1) и выводятся оценки ускорения при параллельном выполнении однородного цикла на однородной (п. 3.3) и неоднородной (п. 3.4) вычислительной системе. В п. 3.5 исследуются возможности оптимального выполнения итерированного цикла (параллельный цикл, вложенный в последовательный цикл) на параллельной вычислительной системе (однородной и неоднородной). Исследование проводится на качественном уровне.
В разделе 4 приводятся спецификации интерфейсов, расширяющих среду Java стандартным интерфейсом MPI и другими возможностями низкоуровневого SPMD-программирования. Предлагаемые интерфейсы и реализующие их классы позволяют не только организовывать обмен данными в сети JavaVM, но и балансировать нагрузку в сети JavaVM, а также моделировать однородную сеть JavaVM на имеющейся неоднородной вычислительной системе (в частности, на локальной сети рабочих станций).
В разделе 5 приводится описание среды ParJava, которая включает набор инструментальных средств, поддерживающих процесс разработки эффективных, масштабируемых параллельных Java-nporpaMM, для параллельных вычислительных систем с распределенной памятью (в частности, для сетей JavaVM). Эти инструментальные средства обеспечивают возможность низкоуровневого SPMD-программирования в среде Java, помогая прикладным программистам выявлять возможности распараллеливания разрабатываемых ими параллельных программ, а также определять параметры разрабатываемых программ, влияющие на их масштабируемость, и подбирать такие значения этих параметров, при которых обеспечивается максимальная эффективность выполнения программ на вычислительных системах с распределенной памятью. Переносимость программ обеспечивается тем, что они разрабатываются на языке Java.
В разделе 6 обсуждаются результаты модельных расчетов и обсуждаются результаты экспериментальной проверки полученных в разделе 3 оценок. Параллельные программы выполнялись на однородном кластере, содержащем 18 двухпроцессорных узлов, на неоднородном кластере с масштабируемой коммуникационной подсистемой, содержащем 18 двухпроцессорных узлов, и на неоднородной локальной сети (Ethernet) с немасштабируемой коммуникационной подсистемой, содержащей 5 однопроцессорных узлов. Расчеты показали, что применение неоднородных параллельных вычислительных систем приводит к потере эффективности даже в том случае, когда их коммуникационные подсистемы масштабируемы. Использование локальных сетей (неоднородных параллельных вычислительных систем с немасштабируемыми коммуникационными подсистемами) для параллельных вычислений, в которых имеется зависимость по данным между узлами, даже в случае, когда используемый алгоритм удовлетворяет условию локальности (т.е. количество данных, передаваемых с каждого узла на соседние узлы, не зависит от числа узлов и ограничено), невыгодно и возможно только для небольшого числа узлов.
Раздел 7 содержит выводы и направления дальнейших исследований.
В заключение рассмотрим наиболее важные выводы из диссертационной работы. В работе исследовались аппаратные и программные средства разработки эффективных параллельных программ, реализующих вычисления в которых имеется зависимость по данным между узлами, при условии, что используемый алгоритм удовлетворяет условию локальности (см. определение 7 на стр. 20) на однородных и неоднородных вычислительных системах с распределенной памятью.
Установлено, что использование локальных сетей рабочих станций для параллельных вычислений, в которых имеется зависимость по данным между узлами, даже в случае, когда используемый алгоритм удовлетворяет условию локальности (т.е. количество данных, передаваемых с каждого узла на соседние узлы, не зависит от числа узлов и ограничено), невыгодно и возможно только для сетей с небольшим числом узлов. Это связано с тем, что коммуникационная подсистема локальной сети не является масштабируемой (см. определение 3 на стр. 14). В разделе 3 показано, что если для параллельных вычислительных систем с масштабируемыми коммуникационными подсистемами параллельная программа остается масштабируемой при числе узлов, не превосходящем значения М, то у параллельных вычислительных систем с немасштабируемыми коммуникационными подсистемами масштабируемость прекращается при числе узлов равном 4 м (см. стр. 28). Этот вывод подтверждается модельными расчетами, рассмотренными в разделе 6. Более того, у немасштабируемых коммуникационных подсистем (например, Ethernet) латентность каналов на несколько порядков больше, чем у масштабируемых коммуникационных подсистем, хотя, как показано в п. 6.1 даже небольшое увеличение латентности каналов существенно снижает производительность параллельной вычислительной системы.
Выяснено, что даже в случае масштабируемых коммуникационных подсистем использование неоднородных кластеров приводит к деградации коммуникационной подсистемы и, следовательно, к потере масштабируемости (см. п. 6.1). Модельные расчеты, рассмотренные в разделе 6, подтверждают этот вывод.
Таким образом, современная компьютерная аппаратура не поддерживает масштабируемые параллельные вычисления на неоднородных вычислительных сетях, и однородные вычислительные системы с распределенной памятью (суперкомпьютеры и кластеры) — единственный класс параллельных вычислительных систем с распределенной памятью, на которых возможны эффективные масштабируемые параллельные вычисления для широкого класса задач.
Неоднородные вычислительные системы могут использоваться для выполнения параллельных программ, для которых ограничения, рассмотренные в разделе 3, не существенны.
В частности, на неоднородных вычислительных системах с распределенной памятью можно выполнять параллельные вычисления без обмена данными между узлами. Однако, для таких вычислений понятие масштабируемости не имеет смысла, так как в этом случае каждый узел выполняет программу, никак не связанную с программами, выполняемыми на других узлах. Балансировка нагрузки возможна и во всех случаях приводит к повышению скорости вычислений. Поэтому для выполнения таких программ обычно используют более дешевые параллельные вычислительные системы с немасштабируемой коммуникационной подсистемой (локальные сети, Intranet и Internet). Интерфейс MPI в этих случаях, как правило, не используется. Известно несколько открытых и коммерческих систем, позволяющих организовать такие вычисления (см., например, [55], [56], [57]). Модельные расчеты, рассмотренные в п, 6.3, подтверждают этот вывод.
Реализован прототип инструментальной среды разработки параллельных программ (ParJava), в состав которой входят инструменты, позволяющие в интерактивном режиме улучшать характеристики разрабатываемой параллельной программы. Среда ParJava позволяет разрабатывать и отлаживать масштабируемые SPMD-программы для суперкомпьютеров и кластеров на локальных сетях рабочих станций.
Таким образом, в диссертации получены следующие результаты:
• Разработана инструментальная среда ParJava, поддерживающая разработку масштабируемых переносимых параллельных программ для вычислительных систем с распределенной памятью.
• В составе среды ParJava разработаны и реализованы библиотеки интерфейсов и классов, обеспечивающие организацию SPMD-вычислений.
• Обеспечена возможность моделирования однородной сети JavaVM на неоднородной вычислительной сети с балансировкой нагрузки, что позволяет использовать локальные сети в качестве инструментальной среды для разработки и отладки масштабируемых параллельных программ.
• Исследованы возможности эффективного выполнения параллельных программ на вычислительных системах с распределенной памятью.
• Спроектированы специализированные инструментальные средства (анализаторы и преобразователи программ), поддерживающие разработку и отладку масштабируемых SPMD-программ.
Среда ParJava находится в состоянии развития. Разрабатывается отладчик параллельных программ, использующий в своей работе отладочную библиотеку и средства инструментирования программ и с их помощью поддерживающий процесс разработки масштабируемых параллельных программ. Предполагается реализовать конвертор параллельных Java-nporpaMM на язык С, расширенный библиотекой MPI.
Расширение языка Java низкоуровневыми возможностями параллельного программирования дает возможность эффективно реализовывать объектные модели.
76 параллельного программирования более высокого уровня DPJ[58], DVM[59] и др. Включение этих моделей в среду ParJava позволит существенно облегчить разработку параллельных программ, так как оптимальное распределение данных по узлам параллельных вычислительных систем будет производиться автоматически.
Основным достоинством среды ParJava является то, что параллельная программа, разработанная при помощи этой среды, может выполняться на любой масштабируемой вычислительной системе без каких-либо модификаций или преобразований, с сохранением условия масштабируемости. Это снимает многие проблемы по распространению параллельных программ.
