ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ
УДК 681.3.06
ОСОБЕННОСТИ РЕАЛИЗАЦИИ ИНТЕРПРЕТАТОРА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В СРЕДЕ ParJava
© 2009 г. В. П. Иванников, А. И. Аветисян, С. С. Гайсарян, М. С. Акопян
Институт системного программирования РАН 109004 Москва, ул. Б. Коммунистическая, 25 E-mail: {ivan, arut, ssg, manuk} @ispras.ru Поступила в редакцию 01.07.2008 г.
В работе рассматриваются особенности реализации системы программирования ParJava, которая позволяет разрабатывать параллельные приложения на современном языке Java, оставаясь в рамках промышленного стандарта MPI.
Описывается внутреннее представление модели SPMD-программы, построенное таким образом, чтобы возложить как можно большую часть процесса интерпретации параллельной Java-программы на JavaVM. Рассматриваются особенности генерации модели и ее подготовки к интерпретации. Генератор модели преобразует абстрактное синтаксическое дерево каждого метода моделируемой программы в модель потока управления, формирует модель вычислений, которая будет выполняться на JavaVM, и модуль оценки времени выполнения базовых блоков. Интерпретация модели, выполняющейся на p узлах параллельной вычислительной системы (кластера), реализуется в p логических процессах, каждый из которых выполняется в отдельном потоке. Интерпретация логического процесса состоит в интерпретации составляющих его методов, начиная со стартового. Интерпретация каждого метода заключается в выполнении модели вычислений этого метода на JavaVM, при этом порядок интерпретации базовых блоков, входящих в состав метода, определяется системным интерпретатором модели указанного метода. В системе реализована возможность редукции частей модели и интерпретация модели по частям. Обсуждаются проблемы моделирования и интерпретации коммуникационных функций. Коммуникационные функции описываются с помощью девяти базовых операций обмена. Для оценки времени передачи данных между процессами используется эмпирическая зависимость между объемом передаваемых данных и временем передачи данных, получаемая на тестах. Приводится краткое описание графического интерфейса системы ParJava.
Система обеспечивает как платформо-независимость разрабатываемых приложений, так и существенное уменьшение накладных расходов на разработку, доводку и сопровождение. Тем самым решается важная проблема разработки высокопродуктивных параллельных приложений.
1. ВВЕДЕНИЕ
Одними из фундаментальных проблем параллельного программирования является проблема сокращения неприемлемо высоких затрат времени и человеческих ресурсов на разработку масштабируемых параллельных программ и проблема уменьшения трудоемкости переноса разработанных программ на другие платформы. Эти проблемы стоят настолько остро, что даже На-
циональная программа США "Высокопроизводительные вычисления" была переименована в "Высокопродуктивные вычисления", имея в виду, что оценивать параллельные программы следует не только по времени выполнения, но и по ресурсам, затраченным на их разработку.
Наиболее кардинальным решением было бы создание нового языка высокого уровня (или расширение одного из имеющихся языков), который обеспечил бы возможность разрабатывать
параллельные программы с помощью оптимизирующих компиляторов. К сожалению, исследования по высокоуровневым языкам параллельного программирования, проводившиеся, начиная с 1988 года, не увенчались успехом. Ни один из разработанных языков: HPF [1] (и его Java-версия HPJava [2]), Cilk [3], UPC [4] (и его Java-версия Titanium [5]), - не сумел решить поставленных перед ним задач и получить статус стандартного языка параллельного программирования. Анализ причин неудач содержится в работе [6], написанной авторами языка HPF. Главную причину неудачи они видят в том, что, несмотря на значительные усилия, до сих пор не удалось разработать компиляторные технологии, позволяющие генерировать эффективный параллельный код.
В настоящее время ведутся активные исследования по созданию языков нового поколения, можно отметить такие языки, как X10 [7], Chapel [8], Fortress [9]. К сожалению, несмотря на то, что эти языки требуют более детально описывать структуру параллельной вычислительной среды, и для них пока не удалось разработать методы оптимизации, обеспечивающие эффективную компиляцию параллельных программ. Это значит, что даже если такие методы оптимизации будут разработаны в ближайшее время, надеяться на их скорое внедрение не приходится: пройдет около десяти лет, пока будет разработан промышленный компилятор и необходимые прикладному программисту инструментальные средства, в том числе отладчик. Только в этом случае можно будет начать реальное внедрение, в том числе и в систему образования.
Таким образом, промышленную разработку прикладных параллельных программ, обеспечивающих необходимое качество, еще долго придется вести на так называемом "ассемблерном уровне", т.е. на последовательных языках программирования с явным использованием обращений к коммуникационной библиотеке MPI (для систем с распределенной памятью) или прагм OpenMP (для систем с общей памятью и многоядерных процессоров). Ручная доводка программ (распределение данных, шаблоны коммуникаций и др.), требуемая при такой техно-
логии, связана со значительными затратами ресурсов и требует высокой квалификации прикладных программистов. В этих условиях возникает потребность в инструментальных средствах, помогающих программисту решить стоящие перед ним задачи.
Цель статьи - описать особенности реализации среды ParJava [10], предоставляющей прикладному программисту набор инструментов, поддерживающих разработку параллельных программ для вычислительных систем с распределенной памятью (высокопроизводительных кластеров) на языке Java, расширенном стандартной библиотекой передачи сообщений MPI.
Среда ParJava позволяет выполнять большую часть разработки параллельной Java-программы на инструментальном компьютере. Для этого строится модель параллельной Java-программы [11], интерпретируя которую на инструментальном компьютере можно получить оценки времени выполнения программы на заданном кластере (кластер определяется числом узлов, параметрами платформы, используемой в качестве его узлов, и параметрами его коммуникационной сети), а также оценки других динамических атрибутов программы, получить модели ее профилей и трасс. Полученная информация о динамических свойствах параллельной программы позволяет оценить границы ее области масштабируемости, помогает прикладному программисту вручную оптимизировать программу, проверяя на интерпретаторе, как отразились произведенные изменения на ее масштабируемости. Возможность использования инструментального компьютера для оптимизации и настройки параллельной программы избавляет программиста от большей части отладочных запусков программы на целевой вычислительной системе, сокращая период отладки и настройки программы и обеспечивая более комфортные условия для прикладного программиста.
Первой задачей, которую было необходимо решить при разработке среды ParJava, была эффективная реализация стандартной библиотеки MPI для окружения Java. В настоящее время известно несколько реализаций библиотеки MPI для окружения Java [12, 13, 14], но ни одну из них
нельзя было использовать, так как они не обеспечивали достаточной эффективности, и в них были реализованы не все функции библиотеки MPI. Поэтому для среды ParJava была разработана оригинальная реализация библиотеки MPI для окружения Java - пакет mpiJava. В настоящее время в mpiJava поддерживаются все функции, включенные в стандарт MPI 1.1 [15], а также параллельные операции ввода-вывода из стандарта MPI 2 [16]. Таким образом, реализована возможность программирования на языке Java с явными обращениями к функциям библиотеки MPI.
Настоящая работа состоит из девяти разделов. В разделе 2 описывается уточненная модель SPMD-программы и внутреннее представление модели SPMD-программы в среде ParJava. Уточнения были связаны со стремлением возложить как можно большую часть процесса интерпретации параллельной Java-программы на JavaVM. В связи с этим предлагается представить модель каждого метода параллельной Java-программы в виде пары {модель потока управления, модель вычислений), где модель потока управления выполняется с помощью интерпретатора, а модель вычислений выполняется на JavaVM. Такое решение существенно упростило реализацию интерпретатора и обеспечило достаточно высокую скорость процесса интерпретации.
В разделе 3 рассматривается генерация модели и ее подготовка к интерпретации. Генератор модели преобразует абстрактное синтаксическое дерево каждого метода моделируемой программы в модель потока управления, формирует модель вычислений, которая будет выполняться на JavaVM, и модуль оценки времени выполнения базовых блоков. Последний вместе с тестовым набором начальных данных моделируемой параллельной программы (эти данные предоставляются пользователем) выполняется на узле целевой вычислительной системы, в результате получается файл с оценками времени выполнения базовых блоков, которые на инструментальном компьютере вносятся в дескрипторы базовых блоков модели потока управления.
В разделе 4 описывается процесс интерпретации модели. Интерпретация модели SPMD-программы, выполняющейся на p узлах парал-
лельной вычислительной системы (кластера), реализуется в p логических процессах, каждый из которых выполняется в отдельном потоке1. Интерпретация логического процесса состоит в интерпретации составляющих его методов, начиная со стартового. Интерпретация каждого метода заключается в выполнении модели вычислений этого метода на JavaVM, при этом порядок интерпретации базовых блоков, входящих в состав метода, определяется системным интерпретатором модели указанного метода.
В разделе 5 рассматривается редукция частей модели и интерпретация модели по частям. Редукция базового блока состоит в замене этого блока редуцированным блоком, т.е. блоком с пустым телом и фиксированным значением динамических атрибутов. Редукция внутренней вершины, представляющей оператор языка Java, состоит в обходе соответствующего поддерева в глубину, во вре
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.