автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка методов оценки масштабируемости и производительности программ, параллельных по данным

Московский государственный университет им. М.В. Ломоносова

На правах рукопис

¡'КОПИС!^.

Падарян Вартан Андроникович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ОЦЕНКИ МАСШТАБИРУЕМОСТИ И ПРОИЗВОДИТЕЛЬНОСТИ ПРОГРАММ, ПАРАЛЛЕЛЬНЫХ ПО ДАННЫМ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2005

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова (ВМиК МГУ).

Научный руководитель:

кандидат физико-математических наук, доцент

Гайсарян Сергей Суренович.

Официальные оппоненты: доктор физико-математических наук

Крюков Виктор Алексеевич; кандидат физико-математических наук Эйсымонт Леонид Константинович.

Ведущая организация:

Научно-исследовательский вычислительный центр Московского государственного университета им. М.В. Ломоносова

Защита диссертации состоится "17" июня 2005 г. в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ

Автореферат разослан " " _2005 г.

Ученый секретарь диссертационного совета

профессор ^и^я/ь- Н.П. Трифонов

~\4Гьб7

Общая характеристика работы

Высокопроизводительные вычислительные системы с распределенной памятью (кластеры) становятся все более распространенными. Многие этапы современных методик разработки и отладки параллельных программ для кластеров выполняются непосредственно на целевом кластере. Прежде всего, это этапы, на которых разработчик прикладной программы выясняет границы области ее масштабируемости, оценивает время ее выполнения, ищет ошибки в организации параллельных вычислений (узкие места, взаимоблокировки и т.п.). Таким образом, в цикл разработки программы включается регулярная работа на ресурсах коллективного пользования, что сопряжено со значительными накладными расходами как по времени разработки, так и по используемым ресурсам.

Целью диссертационной работы является исследование и разработка методов оценки масштабируемости, производительности и других динамических характеристик программы, параллельной по данным, которые позволяют значительно сократить использование целевого вычислительного кластера, перенеся большую часть разработки на средство индивидуального пользования - инструментальный компьютер (рабочую станцию).

Актуальность. В настоящее время параллельные вычисления широко применяются для решения инженерных и научных задач. Для оптимальной организации параллельных вычислений необходимо знание динамических характеристик параллельной программы. Эти характеристики получаются с помощью частотных и временных профилей, анализа трасс, графов коммуникаций и т.п. Как уже было отмечено, при использовании современных методик разработки параллельных программ для получения этих данных используется целевой вычислительный кластер, что существенно удорожает разработку таких программ. Поэтому важной задачей является разработка методик, позволяющих получать достаточно точные оценки динамических характеристик параллельной программы, используя инструментальный компьютер. Следует отметить, что такие методики ставят разработчика в более комфортные условия, способствуя повышению качества разрабатываемой программы.

В работе предложена и обоснована модель параллельной программы и на ее основе спроектированы и реализованы программные средства, которые позволяют на инструментальном компьютере определять границы области масштабируемости параллельной программы, прогнозировать время ее работы на любом заданном вычислительном кластере, получать профили, трассы и другие динамические характеристики, а также использовать их для нахождения ошибок в организации параллельных вычислений.

Более того, разработанная методика может применяться для качественного моделирования поведения программы на нескольких кластерах с разными характеристиками, что позволяет выбрать кластер, который лучше всего удовлетворяет требованиям прикладного программиста. Следует отметить, что в этом случае оценки динамических характеристик будут достаточно грубыми. Поэтому после выбора кластера необходимо повторно вычислить динамические характеристики, используя точное знание параметров кластера.

Анализируя существующие системы, поддерживающие разработку параллельных программ, среди них можно выделить три типа: (1) среды разработки, выявляющие характеристики параллельной программы во время ее выполнения на целевом вычислительном кластере, (2) интерпретаторы параллельных программ, выполняющиеся на инструментальном кластере (как правило, менее мощном, чем целевой) и прогнозирующие время их работы, и (3) среды разработки, обеспечивающие оценку динамических характеристик параллельной программы с помощью инструментальных программ, работающих на инструментальном компьютере.

Однако существующие методы оценки динамических характеристик либо существенно ограничивают возможность варьирования параметров целевого кластера, либо не обеспечивают должной точности прогноза. Методика, предложенная в диссертации, обеспечивает возможность оценивать динамические характеристики параллельной программы с требуемой точностью на инструментальном компьютере. Это позволяет осуществлять большую часть «доводки» параллельной программы без использования целевого кластера.

Основные результаты. В диссертации получены следующие результаты, характеризующиеся научной новизной.

1. Разработана модель программы, параллельной по данным, предложены алгоритмы ее построения и интерпретации. Показано, что интерпретация модели может выполняться на инструментальном компьютере с учетом параметров целевого кластера.

2. Введено понятие частичной интерпретации, позволяющее автономно интерпретировать фрагменты программы (процедуры, циклы, гнезда циклов и т.п.). Сформулированы и обоснованы условия, которым должны удовлетворять фрагменты программы, чтобы их частичная интерпретация была корректной.

3. Предложен метод прогнозирования времени выполнения параллельной программы или ее фрагмента, основанный на интерпретации ее модели. Получены оценки абсолютной и относительной погрешностей прогноза.

4. Разработан интерпретатор модели параллельной программы. Интерпретатор реализован и включен в среду разработки параллельных программ ParJava.

Практическая ценность работы. Все разработанные средства интегрированы в инструментальную среду ParJava (среда ParJava является интегрированной средой разработки переносимых параллельных программ для вычислительных систем с распределенной памятью). Предложенная методика прогнозирования времени работы параллельной программы и инструментальные средства, поддерживающие эту методику, могут быть адаптированы для определения других динамических характеристик. В частности, интерпретатор может использоваться для выявления ошибок в организации параллельных вычислений, таких, например, как взаимоблокировка процессов параллельной программы, потеря данных при коммуникациях, узкие места и т.п.

Среда ParJava, разработанная в Институте Системного Программирования Российской академии наук (ИСП РАН), используется в учебном процессе базовой кафедры системного программирования факультета управления и прикладной математики Московского физико-технического института (ФУПМ МФТИ) при ИСП РАН и кафедры системного программирования факультета ВМиК МГУ. Кроме того, среда ParJava используется как средство разработки в проекте по созданию библиотеки методов параллельного символьного решения задач линейной алгебры PolyCalc в Тамбовском государственным университете. Проект ParJava поддержан грантами Российского фонда фундаментальных исследований (РФФИ) и Минпромнауки России. Среда ParJava доступна для загрузки из сети Internet1. Апробация работы.

Основные результаты работы опубликованы в статьях [1] - [14]. Результаты работы обсуждались на следующих конференциях и семинарах:

1. Международная конференция «Avances en la Ciencia de la Computación, ENC'04», Colima, Mexico. Septiembre 20 - 24,2004.

2. Всероссийская научная конференция «Научный сервис в сети Интернет», Новороссийск, 20 - 25 сентября 2004.

3. Конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.

4. Международная конференция «The 10th EuroPVM/MPI conference», Venice, Italy. September 29 - October 2,2003.

5. Международная конференция «Computer science and Information technologies», Yerevan. September 22 - 26,2003.

1 http://www.ispras.ru/groups/ctt/parjava.html

6. Международная конференция «Вычислительная механика и современные прикладные программные системы», Владимир, 30 июня - 5 июля 2003.

7. Международная конференция «Parallel and Distributed Processing Techniques and Applications», Las Vegas. June 23 - 26,2003.

8. Международный семинар «Russian - Indian Intern. Workshop on НРС», Москва, 16 - 20 июня 2003.

9. Международная конференция «Parallel Computational Fluid Dynamics», Москва, 13 - 15 мая 2003.

10. Конференция «Современные проблемы фундаментальных и прикладных наук», Москва - Долгопрудный, 23 - 30 ноября 2001. Объем и структура диссертации. Работа состоит из шести разделов,

списка литературы и четырех приложений. Общий объем диссертации 145 страниц, в том числе 30 иллюстраций и 5 таблиц. Список источников и литературы содержит 73 наименования.

Краткое содержание работы

Во введении (раздел 1) обсуждается цель диссертационной работы, обосновывается ее актуальность. Формулируются основные результаты работы. Рассматриваются возможности практического применения предложенной в работе методики оценки динамических характеристик, а также программных средств, поддерживающих эту методику. Перечисляются опубликованные печатные работы по теме диссертации.

Раздел 2 содержит обзор работ, имеющих непосредственное отношение к теме диссертации. В обзоре рассматриваются существующие программные средства, поддерживающие разработку программ, параллельных по данным.

Средства поддержки разработки параллельных программ разделены на следующие три типа: (1) среды разработки, выявляющие характеристики параллельной программы во время ее выполнения на целевом вычислительном кластере, (2) интерпретаторы параллельных программ, выполняющиеся на инструментальном кластере (как правило, менее мощном, чем целевой) и прогнозирующие время их работы, и (3) среды разработки, обеспечивающие оценку динамических характеристик параллельной программы с помощью инструментальных программ, работающих на инструментальном компьютере.

Из систем первого типа наиболее известны коммерческая система Vampir, разработанная в компании Pallas GmbH (Германия), и свободно распространяемая система V-Ray, разработанная в Научно-исследовательском вычислительном центре МГУ им. М.В. Ломоносова (НИВЦ МГУ). Примером системы второго типа может служить распределенный интерпретатор параллельных программ MPI-Sim. Среди

систем третьего типа можно выделить среду AIMS, разработанную в NASA, и систему DVM, разработанную в Институте прикладной математики им. М.В. Келдыша РАН.

В разделе 3 описывается модель параллельной программы, предлагается метод интерпретации модели. Рассматривается моделирование коммуникационных функций MPI с помощью базовых операций обмена. Отдельно рассмотрены особенности интерпретации для случая, когда строится прогноз времени работы параллельной программы. Выводятся вероятностные и мажорантные оценки погрешности прогнозирования времени работы. В главе введены понятия редукции вершины модели и корректности выполнения редукции, определены и обоснованы условия корректности редукции.

В разделе 3.1 подробно описывается модель параллельной Java-программы, строящаяся по ее абстрактному синтаксическому дереву (АСД). Моделью метода (функции) f ( ) класса с параллельной Java-программы называется пара M = <S, Т>, где S - список описаний локальных переменных и формальных параметров моделируемой функции (метода), Т - модель тела функции (метода). Модель тела функции получается из АСД этого метода (функции) с помощью следующих преобразований :

1. По каждому поддереву АСД, соответствующему объявлению локальных переменных функции (метода), строится последовательность описаний этих переменных, которая присоединяется к S, после чего указанное поддерево удаляется из АСД.

2. Удаляются листья АСД, являющиеся токенами (ключевые слова, открывающие и закрывающие скобки и т.п.).

3. Вершины АСД, представляющие управляющие структуры, заменяются внутренними вершинами модели.

4. Поддеревья АСД, соответствующие выражениям и вызовам функций (методов и коммуникационных), заменяются базовыми блоками.

5. Удаляются поддеревья АСД, соответствующие блокам catch операторов try.

Полученное после этих преобразований дерево содержит внутренние вершины, соответствующие следующим операторам исходной программы: {}, if, if-else, do, for, while, switch, листьями дерева являются базовые блоки, определяемые ниже.

Каждая внутренняя вершина F описывается кортежем V= <id, в, Е, /, О, С, R, А>, где id - идентификатор внутренней вершины (он используется для ссылок на вершину V),6 - тип вершины, Е - управляющее выражение, / - список входных переменных, О - список выходных переменных, С -список внешних управляющих переменных, т.е. переменных, принадлежащих спискам I управляющих выражений внутренних вершин,

не являющихся потомками вершины V, R - список непосредственных потомков вершины V, А- список атрибутов вершины V.

Определено согласно перечню операторов языка Java шесть видов внутренних вершин, присутствующих в модели тела метода.

Будем называть базовым блоком семерку B=<id, г, Р, I, О, С, А>, где id - идентификатор базового блока (используется для ссылок на блок В), т- тип базового блока, Р - последовательность инструкций байт-кода, I-список входных переменных, О - список выходных переменных, С - список управляющих переменных, т.е. переменных, входящих во множество 1 какого-либо управляющего выражения или участвующих в вычислении фактических параметров коммуникационных функций, А - список атрибутов базового блока. Определены базовые блоки следующих типов г : вычислительный блок (cb), вызов пользовательской функции (ufe), вызов внешней функции (efe), вызов коммуникационной функции (efe), редуцированный блок (rb). Атрибуты, входящие в список А, характеризуют динамические свойства программы (такие, как время ее выполнения, объем требуемой памяти, степень локальности данных и др.).

Моделью класса с параллельной Java-программы будем называть список именованных пар <S, Т>, где первая пара имеет имя с._ и содержит пустой элемент Т, а остальные пары последовательности описывают методы этого класса.

Список S первой пары включает: переменные объекта, объявленные в классе (общедоступные, приватные и защищенные переменные объекта класса с), статические переменные класса с, общедоступные статические переменные других классов пакета, в который входит класс с и которые используются в классе с, общедоступные статические переменные классов других пакетов, которые используются в классе с.

Моделью параллельной Java-прогроммы будем называть множество моделей всех классов этой программы.

Методика моделирования коммуникационных функций MPI описывается в разделе 3.2. Вводятся следующие базовые операции обмена.

In it - выделение ресурсов под используемые в коммуникации служебные структуры данных и инициализация последних.

Free - освобождение ресурсов.

Pa ck (п, type) - преобразования, выполняемые MPI над массивом данных типа type, общей размерности и байт. Имеется в виду два преобразования: (1) преобразование представления данных, упомянутое в стандарте, - перевод чисел с плавающей точкой в машинно-независимый формат или перекодировка данных типа MPI_CHAR (маршалинг данных), (2) преобразование Java-объектов в массив байт (сериализация).

Unpa ck (п, type) - действие, обратное операции Pa ck.

В JDK (Java Development Kit), начиная с версии 1.4, включен пакет java.nio, содержащий класс java.nio.Buffer, методы которого обеспечивают буферизацию Java-массивов примитивных типов, организуя доступ к буферу через указатель типа void* языка С. Наследуясь от этого класса, можно обеспечить доступ к массиву примитивного типа языка Java как к массиву языка С. Передачу массива через буфер можно организовать как простое переписывание буфера из памяти одного вычислительного узла в память другого. Поскольку форматы примитивных типов данных в языке Java жестко стандартизированы и при передаче массивов примитивного типа ни маршалинга, ни сериализации не требуется, можно обойтись без операций Раек и Unpack.

Post (п) - отправка буфера памяти длиной п байт другому процессу: буфер передается в абстрактный канал, после чего MPI перестает контролировать процесс отправки. Обращение MPI к абстрактному каналу включает все действия, использующие ресурсы центрального процессора или приводящие к его простою при передаче рассматриваемого буфера. На практике возможны различные сценарии взаимодействия центрального процессора с каналом, например, непосредственная запись центральным процессором данных по специальному адресу в памяти, или, в случае «интеллектуальных» сетевых адаптеров, спецификация расположения данных по их начальному адресу в памяти и размеру буфера.

Get (п) - прием сообщения длиной л байт.

PostSM(serv_msg) - отправка другому процессу служебного сообщения. Данная операция сводится к операции Post с фиксированной длиной сообщения.

GetSM(serv_msç) - прием служебного сообщения.

Process (serv_msg) - обработка служебного сообщения. Сообщение может быть как самостоятельным, так и являться служебным заголовком пользовательского сообщения.

Сору(п) - копирование буфера размерности и байт в памяти вычислительного узла.

MakeThread-создание нити выполнения в программе.

Wait (событие) - ожидание события. Под событием понимается прибытие на вычислительный узел служебного сообщения. Операция Wait состоит из простоя центрального процессора до момента прихода служебного сообщения, его приема (GetSM) и обработки (Process).

Для обозначения длительности операции будем в дальнейшем использовать Time(op), где ор - рассматриваемая операция.

Рассмотрим, как выполняется моделирование функции MPI_COMM_SSEND.

Блокирующая синхронная посылка (MPI COMM SSEND) гарантирует прохождение «рандеву» процессами, участвующими в коммуникации. В

<s

стандарте MPI дается следующее руководство для реализации MPI_COMM_SSEND. Отправитель посылает запрос на посылку принимающему процессу. Принимающий процесс сохраняет запрос в служебных структурах данных. Когда начинает выполняться подходящий под условия данной коммуникации прием данных (совпадение номера процесса и тега), принимающий процесс посылает отправляющему сообщение, разрешающее коммуникацию, после чего процесс-отправитель посылает данные. До приема «разрешающего» служебного сообщения процесс-отправитель находится в ожидании. После посылки сообщения функция MPI COMM SSEND заканчивает работу. Таким образом, работа функции MPI_COMM_SSEND описывается следующим образом: finit; PostSM (запрос); [Pack(n, type) ] ;

Wait (разрешение) ; Post(n) ; Free ; ) Ргодгат , где п - размер сообщения, type - тип пересылаемых данных. Операция Раек заключена в квадратные скобки в силу того, что в реализации MPI среды Par Java операция Pack не выполняется благодаря использованию возможностей пакета java.nio.

Другие коммуникационные функции моделируются аналогично. В работе рассмотрены все коммуникационные функции MPI 1.1.

Раздел 3.3 посвящен правилам интерпретации модели параллельной программы. Цель интерпретации - вычисление атрибутов, входящих в список А, для каждой интерпретируемой единицы - базового блока, внутренней вершины, метода (функции).

Интерпретация модели параллельной Java-прогроммы состоит в интерпретации модели метода main () одного из классов, входящих в состав программы. Имя этого класса указывается пользователем. При этом пользователь может задать значения параметров метода main ( ).

Интерпретация модели функции (метода) состоит в интерпретации ее корня - как правило, это интерпретация внутренней вершины типа {}.

Интерпретация внутренней вершины v состоит в интерпретации ее потомков согласно семантике представляемого вершиной v оператора и вычислении атрибутов вершины v (способ вычисления зависит от конкретного атрибута) по атрибутам потомков.

Интерпретация базового блока типа «вычислительный блок» состоит в выполнении подмножества инструкций из списка Р, необходимого для определения его атрибутов и значений переменных из списка С. Значения атрибутов либо предоставляется пользователем заранее, либо вычисляются во время интерпретации.

Интерпретация базового блока типа «вызов пользовательской функции» с. f ( ) состоит в интерпретации выражений из списка Р, определяющих значения фактических параметров, последующей интерпретации корневого узла элемента Т модели с. £ для вычисленных

значений фактических параметров и присвоении значений атрибутов этого корневого узла атрибутам данного базового блока.

Интерпретация базового блока типа «вызов внешней (библиотечной) функции» с. f () зависит от доступности этой функции (библиотеки). Если байт-код класса, содержащего соответствующую функцию (метод), доступен (может бьггь загружен) во время интерпретации, то интерпретируются выражения, определяющие значения фактических параметров, и выполняется соответствующая функция (метод) для вычисленных значений фактических параметров. Если байт-код соответствующего класса недоступен, то перед интерпретацией блок должен быть редуцирован.

Интерпретация базового блока типа «вызов коммуникационной функции» заключается в определении атрибутов базового блока согласно выбранной модели коммуникаций.

Интерпретация редуцированного блока не выполняется, поскольку блок уже был проинтерпретирован.

Раздел 3.4 посвящен редукции и частичной интерпретации. Для определения частичной интерпретации введем операцию редукции. Операция редукции определена только для таких вершин модели, интерпретация которых закончена и, следовательно, атрибуты из списка А определены.

По определению, результатом редукции базового блока B-<id, г, Р, I, О, С, А> является базовый блок, построенный по следующим правилам: (1) id сохраняется, (2) г принимает значение гЬ («редуцированный блок»),

(3) Р заменяется пустой последовательностью (nil), (4) I, О и А сохраняются, (5) каждая переменная списка С объявляется константой, в списке С вхождение этой переменной заменяется оператором присваивания соответствующего значения.

Результатом редукции внутренней вершины V = <id, в, Е, I, О, С, R, А> является редуцированный базовый блок, построенный по следующим правилам: (1) значение id берется из первого элемента списка R, (2) г принимает значение гЬ, (3) Р заменяется пустой последовательностью,

(4) I, О, С и А сохраняются. Таким образом, в результате редукции получается базовый блок следующего вида: <id, rb, nil, I, О, С, А>. Редукция корневой вершины выполняется по тем же правилам, что и редукция внутренней вершины.

Будем считать, что редукция внутренней вершины v модели М = <S, Т> корректна, если интерпретация модели М' = <S, Т*>, в которой Т' получается из Т путем редукции вершины v, приводит к таким же оценкам атрибутов, что и интерпретация модели М= <S, Т>.

Будем считать, что вершина замкнута по коммуникациям, если при ее интерпретации не остается не принятых сообщений, и все операции приема завершаются.

В разделе формулируются и обосновываются достаточные условия корректности редукции (Утверждения 1 и 2).

Возможность редукции части вершин модели позволяет интерпретировать модель программы по частям, заменяя интерпретированные фрагменты редуцированными блоками. Описанный способ интерпретации будем называть частичной интерпретацией. В результате частичной интерпретации количество вершин модели сокращается, что позволяет сократить длительность текущего сеанса интерпретации, если редукция выполнялась внутри гнезда цикла, а также сократить длительность последующих сеансов интерпретации. При этом сохраняются оценки атрибутов как для программы в целом, так и для остальных единиц интерпретации, присутствующих в модели.

В разделе 3.5 конкретизируются правила интерпретации модели для случая, когда вычисляется оценка времени работы. Вводится атрибут Time, описывающий время работы вершины модели. Правила интерпретации внутренних вершин вводятся, опираясь на свойство аддитивности атрибута, т.е. Time( {а; b} j = Time (a) + Time(to). Вершины типа if-else и while интерпретируются следующим образом: Time(<id, if-else, E, I, О, С, (г,, Ы A>) =

Time(E) + (val(E)? Time(r,): Time(rJ) Time(<id, while, E, 1, О, C, (r), A>) = (Time(E) + (val(E)? Time(r): 0))'

Внутренние вершины других типов интерпретируются аналогично.

Если v - вызов пользовательской функции, Time(v) определяется путем интерпретации этой функции.

Если v - вычислительный базовый блок или вызов библиотечной функции, значение Time(v) определяется заранее.

Пользователь имеет возможность сообщить оценку времени вычислительного базового блока, удовлетворяющего необходимым условиям редукции, или вызова библиотечной функции. Для этого ему необходимо заменить соответствующую вершину редуцированным блоком и присвоить требуемое значение его атрибуту Time.

Поскольку точности системных часов (в языке Java она составляет lms), как правило, не хватает для определения длительности работы базового блока, в диссертации была предложена следующая методика. Вычислительный базовый блок выполняется во вспомогательном цикле (вне исходной программы) с достаточно большим количеством итераций; измерив время работы вспомогательного цикла и накладные расходы на

организацию цикла, вычисляем оценку среднего времени работы базового блока.

В разделе 3.6 описывается интерпретация коммуникационных функций.

При интерпретации параллельной программы каждый ее процесс представляется в виде логического процесса. Каждый логический процесс имеет свои модельные часы - отображение f(v) вершин v модели, интерпретирующейся в логическом процессе i (i - это номер процесса в рамках коммуникатора MPI_COMM_WORLD), на моменты времени -показания модельных часов. Начальные показания модельных часов всех логических процессов равны нулю. Показания модельных часов логического процесса обновляются после интерпретации в этом процессе каждого базового блока путем добавления значения атрибута Time базового блока к текущему значению модельного времени. Интерпретация работы коммуникационных функций использует показания модельных часов различных процессов для выбора сценария выполнения коммуникации и определения ее продолжительности. Во время интерпретации коммуникационной функции считаем, что интерпретатор параллельной программы определил логические процессы, участвующие в коммуникации, и показания модельных часов каждого процесса-участника доступны.

Показания модельных часов логического процесса i до и после интерпретации базового блока ЬЬ будем обозначать как Т'ь(ЬЬ) и ТЦЬЬ) соответственно. Для базовых блоков типа «вызов коммуникационной функции» определены показания модельных часов для каждой базовой коммуникационной операции ор: ТЦор) и T't(op).

При активизации системы поддержки времени выполнения MPI (RTS) ресурсы вычислительного узла начинают разделяться между двумя нитями выполнения - основной программы и системы поддержки. Такое разделение ресурсов приводит к замедлению работы каждой нити по сравнению с монопольным использованием вычислительного узла. Поэтому, если во время работы базового блока ЬЬ работала также и нить RTS, показания модельных часов будем обновлять по правилу

ТЦЬЬ) = ТЦЬЬ) + Time(bb)/(1 - 0), где 0 < f}< 1 - доля процессорного времени, выделяемого для нити RTS.

При моделировании функций MPI было использовано 9 базовых операций. Разделим эти операции на две группы: (1) операции, длительность работы которых зависит только от свойств вычислительного узла, (2) операции, длительность работы которых зависит только от свойств сети.

В первую группу входят также базовые операции, свойства которых определяются для каждой реализации MPI: In it, Free, Pack, Unpack,

Copy, MakeThread, Process. Время выполнения этих операций определяется заранее и хранится в служебной таблице. Поскольку операция Process сводится к выполнению фиксированного количества операций присваивания,

Time(Process (sezv_msg)) « Time(GetSM (serv_msg)). Поэтому значением Time(Process (serv_msg)) будем пренебрегать.

Вторая группа состоит из пяти операций Post, Get, PostSM, GetSM, из которых необходимо определить время выполнения операций Post и Get. Формулы, описывающие длительность операций Post и Get, основываются на модели LogGP и имеют следующий вид: Time(Post (п)) =b*n + dP(n), dP (0) = I Time(Get(n))=b*n + d^n), dG (0) = / W

Параметры b (пропускная способность) и / (латентность) берутся из характеристик коммуникационного оборудования. Значения функций накладных расходов dp(n) и do(n) определяются из таблицы, которая для каждой вычислительной системы строится с помощью бенчмарков. Показания модельных часов используются следующим образом:

(1) Точное определение времени ожидания. Для вычисления длительности операции Wait (событие) необходимо знать момент прихода сообщения на принимающий узел. Введем обозначение для этого момента времени - ТМ(сообщение). Момент прибытия сообщения определяется показаниями модельных часов на отправляющем узле по правилу

ТМ(сообщение) = T/,(Post (сообщение)) + dp(n), (4) где п - размер сообщения, ТьО - показания модельных часов в момент начала отправки сообщения, dP0 - функция накладных расходов передачи сообщения, взятая из (3).

(2) Выбор сценария приема сообщения. Функции приема сообщения RECV и IRECV могут выполняться по разным сценариям. Выбор сценария зависит от того, было ли предварительно буферизовано на принимающей стороне соответствующе сообщение. Факт предварительной буферизации сообщения устанавливается путем сравнения значения ТМ(сообщение) с показаниями модельных часов принимающего процесса. Подробности выбора сценариев рассмотрены в описаниях функций RECV и IRECV.

Рассмотрим вычисление времени работы функции MPI_COMM_S SEND.

Time(SSEND) = Time(Init) + Time(PostSM (запрос)) + Time(Pack (n, type)) + TimefWait (разрешение)) + Time(GetSM(разрешение)) + Time(Post (n)) + Time(Free). ТМ(запрос) = rfSSEND), + Time(Init) + dP(n).

ТМ(передача) = ffSSEND^ + Time(Init) + TimefPack (n, type)) +

Time("Wait (разрешение)) + Time(GetSM(разрешение)) + dp(n).

При интерпретации функции SSEND возникает необходимость определения длительности операции Wait (разрешение). Поскольку посылка запроса и ожидание ответа на него разделены операцией Ра ск, вообще говоря, ответ может прийти раньше, чем операция Раек закончится. То есть, если ТМ(разрешение) < Те(Раск(п)), то Time(Wait (разрешение)) = 0. Иначе Time(Wait (разрешение)) = ТМ(разрешение) - Те(Раск (п)).

В ходе интерпретации параллельной программы может потребоваться корректировать модельные часы какого-либо логического процесса на величину D в силу того, что выполнение предварительной буферизации сообщения учитывается только в момент начала выполнения функции приема. Корректировка показаний модельных часов никак не влияет на Time(v) в случае, когда v - вычислительный базовый блок, но если v -базовый блок типа «вызов коммуникационной функции», Time(v) может зависеть от Tb(v) и, следовательно, корректировка показаний модельных часов должна сопровождаться пересчетом значения Time(v) путем повторной интерпретации v.

Следует отметить, что помимо изменения значения Time(v), в результате корректировки показаний модельных часов могут измениться временные метки сообщений, которые были посланы при интерпретации вершины v. Изменение значения каждой временной метки может повлиять на длительность работы ответной коммуникации. Таким образом, корректировка модельных часов одного процесса может повлечь за собой корректировку и в других процессах параллельной программы.

В работе предложена методика выполнения коррекции, основанная на повторной интерпретации коммуникаций. Во время интерпретации параллельной программы ведется журнал, в котором фиксируется порядок выполнения коммуникаций. Каждая запись в журнале содержит следующую информацию: показания модельных часов в момент начала и конца коммуникации, код коммуникации (идентификатор функции MPI), номера других процессов, участвующих в коммуникации; в случае групповой коммуникации записывается номер главного процесса. С использованием журналов коммуникаций строится граф корректировки, позволяющий определить порядок выполнения повторной интерпретации. Вершины этого графа соответствуют вызовам коммуникационных функций, ребра описывают зависимость времени работы одного вызова функции от момента начала работы другого вызова.

Выполнять корректировки коммуникаций предлагается по следующему алгоритму.

(Шаг 1) В графе корректировки выбирается такая вершина v, что di(v) - О, do(v) * 0, где di(v) и do(v) - входная и выходная степени вершины v соответственно. Для такой вершины возможно выполнить корректировку времени ее работы. После чего вычисляется новое значение величины D по формуле D = тах(0, D + Time '(v) - Time(v)), где Time '(v) и Timefv) - новое и старое значения времени работы v соответственно. Новое значение D будет использоваться для корректировки времени работы коммуникационных функций, проинтерпретированных после интерпретации v в том же логическом процессе.

(Шаг 2) из графа удаляется вершина v и ребра, инцидентные этой вершине,

(Шаг 3) шаги 1 и 2 повторяются до тех пор, пока в графе не останется одна вершина.

(Шаг 4) для оставшейся вершины выполняется корректировка времени работы так, как это описано в шаге 2.

Корректность алгоритма доказывается в Утверждении 3.

В разделе 3.7 получены оценки абсолютной и относительной погрешностей измерения времени работы базового блока, проведенной по предложенной в разделе 3.5 методике. Аналогичные оценки получены и для всей программы.

Раздел 4 посвящен описанию программного обеспечения, поддерживающего разработанную методику прогнозирования времени работы параллельной программы в рамках среды ParJava.

Раздел 4.1 описывает общую схему получения прогноза (рис. 1, 2), иерархию интерфейсов и классов, реализующих модель параллельной программы, а также взаимодействие пользователя со средой при запуске и работе интерпретатора.

Раздел 4.2 описывает процесс построения статической модели класса по его исходному коду. Подробно рассматриваются классы, используемые в статической модели. Статические модели классов, дополненные оценками времени работы базовых блоков, компонуются в модель параллельной программы. Во время компоновки вызовы методов специализируются: вершина общего вида заменяется вершиной одного из четырех типов: пользовательский метод, библиотечный метод, коммуникационный метод MPI, служебный метод MPI. Применяемые правила преобразования вершин и процесс компоновки подробно описаны в разделе 4.3.

В разделе 4.4 описывается интерпретатор параллельных программ. Интерпретатор состоит из набора логических процессов, совокупности методов simulate, определенных в классах, реализующих вершины модели тела метода, службы синхронизации, подсистемы управления и коммуникационной модели. Подсистема управления интерпретатора следит за работой логических процессов и передает информацию об их выполнении пользователю. Подсистема состоит из монитора и набора наблюдателей. Монитор обеспечивает пользователя информацией о состоянии интерпретируемых логических процессов (рис. 2) и позволяет контролировать процесс интерпретации в системе (приостанавливать, возобновлять интерпретацию). Каждый из наблюдателей отслеживает интерпретацию логических процессов и при наступлении в параллельной программе интересующего пользователя состояния, например, при возникновении взаимоблокировки процессов, информирует об этом через монитор.

1

Рис. 2. Устройство интерпретатора.

Обработка исключительных состояний, возникающих во время интерпретации, описана в разделе 4.5.

В разделе 4.6 описывается порядок использования GUI среды ParJava при выполнении частичной интерпретации.

Разделы 4.7 - 4.12 посвящены рассмотрению технических особенностей сбора профилей параллельной программы, получению оценок времени работы базовых блоков.

■-интерпретатор-

^-Подсистема управления-^

Монитор

Логичесдей процеос ^оЯЛЕйы^

Очередь входящих сообщен^

1 3

Модель параллельной программы

В разделе 4.13 перечисляются ограничения текущей версии программного обеспечения.

В разделе 5 описываются модельные расчеты, проведенные для экспериментальной проверки разработанной методики прогнозирования времени работы параллельных программ. Точность прогнозирования времени выполнения оценивается на примере четырех модельных программ: (1) программа, вычисляющая перенос вещества при взрыве протонейтронной звезды, (2) программа решения линейного уравнения теплопроводности в прямоугольной области, (3) программа решения системы линейных алгебраических уравнений итерационным методом Якоби, (4) программа моделирования вычислений на сеточной области.

Представлено предсказанное время выполнения и действительное, полученное на кластерах ИСП РАН (использовались сети Myrinet и Ethernet) и НИВЦ МГУ (сеть SCI). Для построения моделей программ и их интерпретации использовался инструментальный компьютер с одним процессором Intel Pentium IV 2,66 GHz и 512 Mb оперативной памяти, оценка времени работы базовых блоков получалась на соответствующих целевых вычислительных системах согласно описанной методике.

При моделировании коммуникаций кластера ИСП РАН использовались следующие значения параметров: Time(Init) = Time(Free) = Time(Process) = Time(Pack) = Time(Unpack) = Time(MakeThread) = 0, к = 4, >3=0.5, b = 200 MB/sec и / = 30 usee для сети Myrinet, b - 10 MB/sec и / = 160 usee для сети Ethernet. В силу однородности кластера и эффективности реализации MPI операции Pack и Unpack при пересылках не выполняются. Накладные расходы уровня MPI (операции Init, Free, Process, MakeThread) учитывались в параметрах b и /.

Для описания SCI-кластера использовались аналогичные значения параметров, за исключением: b = 300 MB/sec, 1 = 4 usee (взяты пиковые значения характеристик сети заявленные производителем).

Для второй программы результаты предсказания времени работы представлены на рис. 3.

Предсказание также строилось для измеренной с помощью бенчмарка Ping-Pong пропускной способности сети Myrinet. Относительная погрешность предсказаний составила около 1%.

Для третьей программы результаты предсказания времени работы представлены на рис. 4. При моделировании использовались те же значения характеристик коммуникационный сетей, что и в предыдущих примерах, за исключением того, что прогнозирование времени работы в случае сети Ethernet делалось для b = 10 и 5 MB/sec (пропускная способность сети на уровне MPI составляет 6-8 MB/sec). Относительная

погрешность предсказания не превысила 8,5% для Ь = 10 МВ/яес и 6% для Ь~ 5 МВ/вес.

Для остальных программ были получены аналогичные результаты.

и

S 595 а

Î а

■ 580

565

550

2 4 6 8 10 12 14 16

количество процессоров

Рис. 3. Сравнение предсказанного и действительного времени работы программы «Теплоперенос». Сеть Myrinet. MPI: mpich-gm-1.2.5-10.

u 2500

i ю я

д 2000 2

1500

1000

500

0

2 4 6 8 10 12 14 16

количество процессоров

Рис. 4. Сравнение предсказанного и действительного времени работы программы «Якоби». Сеть Ethernet. MPI: lam-7.1.1.

В заключении (раздел 6) перечислены результаты работы и изложены планы развития и применения разработанной методики интерпретации модели параллельной программы.

-Действительное время работы программы

-»- - Предсказанное время для фактической

пропускной способности ■ -А- Предсказанное время для гиковой

пропускной способности Муппа_

-«—Действительное время работы

■ -А ■ Предсказание для Ь=1 OMbfe -•- -Предсказание для Ь-5МЬ/в

В диссертации исследована и разработана оригинальная методика построения моделей параллельных программ и получения оценок динамических атрибутов параллельных программ путем интерпретации их моделей. На основе предложенной методики разработаны и реализованы инструментальные программные средства, позволяющие на инструментальном компьютере оценивать время выполнения параллельной программы и границы интервала ее масштабируемости.

Разработанные инструментальные средства включены в состав среды Раг/ауа. Среда Раг1ауа и представленные инструментальные средства используются разработчиками библиотеки методов параллельного символьного решения задач линейной алгебры Ро1уСа1с и разработчиками генетических алгоритмов оптимизации адаптивной системы управления мобильного робота на параллельном вычислительном комплексе. Кроме того, среда Рап1ауа используется в учебном процессе базовой кафедры системного программирования ФУПМ МФТИ при ИСП РАН и кафедры системного программирования факультета ВМиК МГУ. Среда Раг1ауа внедрена на кластере ИСП РАН, а также в ГУ МСЦ и НИВЦ МГУ.

Дальнейшие исследования по рассматриваемой тематике связаны с применением разработанной методики для оценки других динамических параллельных программ, в частности для получения профиля используемой памяти в целях улучшения работы подсистемы контрольных точек среды Раг1ауа. Кроме того, разработанная методика позволяет вычислять динамические характеристики параллельных программ, реализованных на других языках программирования.

Основные результаты работы

1. Разработана модель программы, параллельной по данным, предложены алгоритмы ее построения и интерпретации. Показано, что интерпретация модели может выполняться на инструментальном компьютере с учетом параметров целевого кластера.

2. Введено понятие частичной интерпретации, позволяющее автономно интерпретировать фрагменты программы (процедуры, циклы, гнезда циклов и т.п.). Сформулированы и обоснованы условия, которым должны удовлетворять фрагменты программы, чтобы их частичная интерпретация была корректной.

3. Предложен метод прогнозирования времени выполнения параллельной программы или ее фрагмента, основанный на интерпретации ее модели. Получены оценки абсолютной и относительной погрешностей прогноза.

4. Разработан интерпретатор модели параллельной программы. Интерпретатор реализован и включен в среду разработки параллельных программ Раг.1ауа.

Работы автора по теме диссертации

1. В.А. Падарян. Оценка времени работы параллельной программы с помощью интерпретатора среды ParJava. / Препринт Института Системного Программирования РАН № 6. М.: ИСП РАН, 2005.

2. Victor Ivannikov, Serguei Gaissaxyan, Arutyun Avetisyan, Vartan Padaiyan and Hennadiy Leontyev. Dynamic Analysis and Trace Simulation for Data Parallel Programs in the ParJava Environment. M. Estrada, A. Gelbukh (Eds.) // Avances en la Ciencia de la Computacion, ENC'04, Colima, Mexico, 2004, pp. 481-488.

3. Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян, Катерина Долгова. Среда разработки параллельных Java-прогрэмм, использующих библиотеку MPI. // Труды всероссийской научной конференции «Научный сервис в сети Интернет». Новороссийск, 2025 сентября 2004, с. 177-179.

4. В.А. Падарян. Интерпретация иерархической модели в среде ParJava. // Тезисы конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.

5. Виктор Иванников, Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян. Применение среды ParJava для разработки параллельных программ. // Труды Института Системного Программирования, т. 5, 2004, с. 41-62.

6. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10 EuroPVM/MPI conference. LNCS 2840. Sept. 2003, Venice, pp. 491-494.

7. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Analyzing Dynamic Properties of Parallel Program in ParJava Environment. // Proc. of the conf. Computer science and Information technologies. Sept. 2003, Yerevan, pp. 19-23.

8. В.А. Падарян, Г.А. Леонтьев, B.B. Бабкова. Инструментальные средства повышения качества параллельных программ. // Тезисы докладов, XII Международная конференция по вычислительной механике и современным прикладным программным системам, июнь - июль 2003, Владимир, т. 2. с. 516-518.

9. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaiyan. Using symbolic execution of a parallel program to estimate its scalability. // Proc. of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications, PDPTA '03, June 23 - 26, 2003, Las Vegas, Nevada, USA, Vol. 4. CSREA Press, pp. 1741-1744.

10. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Estimating Scalability of a Parallel Program in ParJava Environment // Russian - Indian Intern. Workshop on HPC, June 2003, Moscow, pp. 29-30.

11. Victor Ivannikov, Serguei Gaissaiyan, Arutyun Avetisyan, Vartan Padaryan. Development of Scalable Parallel Programs in ParJava Environment. // Parallel CFD 2003, May 2003, Moscow, pp. 291 - 293.

12. А.И. Аветисян, C.C. Гайсарян, B.A. Падарян. Эффективный обмен данными на сетях JavaVM. // Тезисы докладов, XLIV Научная конференция МФТИ, Современные проблемы фундаментальных и прикладных наук, ч. VII. Ноябрь 2001, Москва - Долгопрудный, с. 29.

13. А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. Параллельное профаммирование с распределением по данным в системе ParJava. // Вычислительные методы и программирование. 2001 г., Москва, т. 2, № 1. с, 129-146.

14. А.И. Аветисян, В.А. Падарян. Библиотека интерфейсов и классов, расширяющих язык Java средствами разработки параллельных программ в модели SPMD. // Труды института системного программирования, 2001, Москва, т. 2, с. 49-64.

!

РНБ Русский фонд

2006-4 14657

X¿>

Заказ № 32. ОбьЫ Ifin.n. Тираж 100 экз.

Отпечатано в ООО « Петроруш» г. Москва, ул. Палиха-2а, тел 250-92-06 www.postator.ro

1. Введение.

2. Системы, поддерживающие разработку параллельных программ с использованием символьной интерпретации.

3. Модель параллельной программы и ее интерпретация.

3.1 Описание модели.

3.2 Моделирование коммуникационных функций.

3.3 Интерпретация модели.

Интерпретация базовых блоков.

3.4 Частичная интерпретация.

3.5 Оценка времени выполнения программы.

3.6 Интерпретация коммуникационных функций при оценке времени работы программы.

3.7 Точность оценки времени.

4. Описание программного обеспечения.

4.1 Работа среды ParJava при построении оценки времени выполнения параллельной программы.

4.2. Построение статических моделей классов.

4.3. Компоновка модели.

4.4. Интерпретатор параллельной программы.

4.5 Обработка исключительных ситуаций в интерпретаторе.

4.6. Редукция вершин модели.

4.7. Частотное профилирование параллельной программы.

4.8. Инструментирование исходного кода.

4.9. Сбор частотного профиля и трассы параллельной программы.

4.10. Коррекция.

4.11. Анализ контекста базовых блоков.

4.12. Получение оценок времени работы базовых блоков.

4.13. Ограничения реализации.

5. Результаты численных экспериментов.

Параллельные программы для вычислительных систем с распределенной памятью (кластеров, суперкомпьютеров) разрабатываются и отлаживаются с использованием целевой вычислительной системы, что сопряжено со значительными накладными расходами как по времени разработки, так и по используемым ресурсам.

Целью диссертационной работы является исследование и разработка методов оценки масштабируемости, производительности и других динамических характеристик программы, параллельной по данным, которые позволяют значительно сократить использование целевого вычислительного кластера, перенеся большую часть разработки на средство индивидуального пользования - инструментальный компьютер (рабочую станцию).

Актуальность. В настоящее время параллельные вычисления широко применяются для решения инженерных и научных задач. При организации параллельных вычислений необходимо знание динамических характеристик параллельной программы, получаемых с помощью частотных и временных профилей. На данный момент для получения профилей используется целевой вычислительный кластер, особенности доступа к которому существенно увеличивают длительность разработки, а следовательно, и ее стоимость. Поэтому важной задачей является разработка методик, позволяющих оценивать динамические характеристики разрабатываемой программы, минимально вовлекая целевой кластер.

В диссертации рассмотрена проблема предсказания поведения параллельной программы на целевом вычислительном кластере. В работе предложена и обоснована модель параллельной программы, и на ее основе спроектированы и реализованы программные средства, которые позволяют на инструментальной машине определять границы масштабируемости параллельной программы, прогнозировать время ее работы на любом заданном вычислительном кластере, получать профили, трассы и другие динамические характеристики, а также использовать их для нахождения ошибок в организации параллельных вычислений.

Прогноз строится в процессе моделирования работы параллельной программы с учетом параметров предполагаемого целевого вычислительного кластера. Знание динамических характеристик программы позволяет работать над ее улучшением, оставаясь на инструментальной машине. Предполагается, что оценки динамических характеристик строятся в диалоговом режиме, поскольку в случае неудовлетворительной производительности программы такой подход позволяет лучше понимать причины, ее вызвавшие.

Разработанная методика может применяться для качественного моделирования поведения программы на нескольких кластерах с разными параметрами, что позволяет выбрать кластер, который лучше всего удовлетворяет требованиям прикладного программиста. Следует отметить, что в этом случае оценки динамических характеристик ' будут достаточно грубыми. Поэтому после выбора кластера необходимо повторно

1 вычислить динамические характеристики, используя точное знание параметров кластера.

Анализируя существующие системы, поддерживающие разработку параллельных программ, среди них можно выделить три типа: (1) среды разработки, выявляющие характеристики параллельной программы во время ее выполнения на целевом вычислительном кластере, (2) интерпретаторы параллельных программ, выполняющиеся на инструментальном кластере (как правило, менее мощном, чем целевой) и прогнозирующие время их работы и (3) среды разработки, обеспечивающие оценку динамических характеристик параллельной программы с помощью инструментальных программ, работающих на инструментальном компьютере.

Однако существующие методы оценки динамических характеристик либо существенно ограничивают возможность варьирования параметров целевого кластера, ' либо не обеспечивают должной точности прогноза. Методика, предложенная в диссертации, оценивать динамические характеристики параллельной программы с требуемой точностью на инструментальном компьютере. Это позволяет осуществлять большую часть «доводки» параллельной программы без использования целевого кластера. Основные результаты. В диссертации получены следующие результаты, характеризующиеся научной новизной.

1. Разработана модель программы, параллельной по данным, предложены алгоритмы ее построения и интерпретации. Показано, что интерпретация модели может выполняться на инструментальном компьютере с учетом параметров целевого кластера.

2. Введено понятие частичной интерпретации, позволяющее автономно интерпретировать фрагменты программы (процедуры, циклы, гнезда циклов и т.п.). Сформулированы и обоснованы условия, которым должны удовлетворять фрагменты программы, для того чтобы их частичная интерпретация была корректной.

3. Предложен метод прогнозирования времени выполнения параллельной программы, « или ее фрагмента, основанный на интерпретации ее модели. Получены оценки абсолютной и относительной погрешностей прогноза.

4. Разработан интерпретатор модели параллельной программы. Интерпретатор реализован и включён в среду разработки параллельных программ ParJava. Практическая ценность работы. Все разработанные средства интегрированы в инструментальную среду ParJava (среда ParJava является интегрированной средой разработки переносимых параллельных программ для вычислительных систем с распределенной памятью). Предложенная методика прогнозирования времени работы параллельной программы и инструментальные средства, поддерживающие эту методику, могут быть адаптированы для определения других динамических характеристик. В частности, интерпретатор может использоваться для выявления ошибок организации параллельных вычислений, таких, например, как взаимоблокировка процессов параллельной программы, потеря данных при коммуникациях, узкие места и т.п.

Среда ParJava, разработанная в ИСП РАН, используется в учебном процессе кафедры системного программирования факультета ВМиК МГУ и кафедры системного программирования ФУПМ МФТИ. ParJava используется как средство разработки в проекте по созданию библиотеки методов параллельного символьного решения задач линейной алгебры PolyCalc (Тамбовский государственный университет). Проект ParJava поддержан грантами РФФИ и Минпромнауки.

Среда ParJava доступна по http://www.ispras.ru/groups/ctt/parjava.html. Апробация работы.

Основные результаты работы опубликованы в статьях [1] - [14]. Результаты работы обсуждались на следующих конференциях и семинарах:

1. Международная конференция «Avances en la Ciencia de la Computacion, ENC'04», Colima, Mexico. Septiembre 20 - 24, 2004.

2. Всероссийская научная конференция «Научный сервис в сети Интернет», Новороссийск, 20 - 25 сентября, 2004.

3. Конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.

4. Международная конференция «The 10th EuroPVM/MPI conference», Venice, Italy. September 29 - October 2, 2003;

5. Международная конференция «Computer science and Information technologies», Yerevan. September 22 - 26,2003;

6. Международная конференция «Вычислительная механика и современные прикладные программные системы», Владимир. 30 июня - 5 июля, 2003;

7. Международная конференция «Parallel and Distributed Processing Techniques and Applications», Las Vegas. June 23 - 26, 2003;

8. Международный семинар «Russian - Indian Intern. Workshop on НРС», Москва. 16 — 20 июня, 2003;

9. Международная конференция «Parallel Computational Fluid Dynamics», Москва. 13 — 15 мая, 2003;

10. Конференция «Современные проблемы фундаментальных и прикладных наук», Москва - Долгопрудный. 23 - 30 ноября, 2001.

Краткое содержание работы. В разделе 2 приводится обзор систем, поддерживающих разработку параллельных программ с использованием символьной интерпретации. В настоящее время в различных исследовательских центрах мира ведется ряд проектов, в которых изучаются возможности анализа производительности параллельных программ посредством их символьной интерпретации. Разработкой систем поддержки занимаются как учебные заведения, так и различные государственные и коммерческие учреждения и организации. В обзоре рассмотрены и сравнены между собой различные научно-исследовательские и коммерческие системы. Анализ этих систем позволил уточнить постановку задачи.

В разделе 3 рассматривается модель параллельной программы и способ ее интерпретации. Предлагается строить модель параллельной Java-программы на основе ее абстрактного синтаксического дерева (АСД). Вводится набор базовых коммуникационных операций, коммуникационные функции MPI рассмотрены как композиция базовых операций. Определяется интерпретация модели параллельной программы. Вводится понятие редукции вершины модели параллельной программы, а также понятие корректности редукции. Сформулированы и доказаны достаточные требования корректности редукции. Рассмотрены особенности интерпретации для того случая, когда вычисляется оценка времени работы параллельной программы. Предложена методика предварительной оценки времени работы базовых блоков Java-программы. Заканчивается раздел набором утверждений об абсолютной и относительной погрешностях прогноза времени работы параллельной программы, получаемого при ее интерпретации. Все утверждения сопровождаются доказательствами.

В разделе 4 описано программное обеспечение, позволяющее прогнозировать время выполнения программы, параллельной по данным. Подробно описываются внутреннее представление параллельной Java-программы и реализация интерпретатора. Особое внимание уделено процессу выявления динамических свойств программы, в состав которого входят инструментация исходного кода, сбор профилей и компенсация влияния инструментальных операторов.

В разделе 5 рассматриваются три модельные программы, на примере которых демонстрируется погрешность прогноза времени работы. Приводятся многочисленные графики и диаграммы.

Раздел 6 содержит выводы и направления дальнейших исследований.

В заключение рассмотрим наиболее важные выводы из диссертационной работы. В работе ставилась задача исследования и разработки таких методов оценки масштабируемости программ, параллельных по данным, которые позволяют значительно сократить использование целевого вычислительного кластера.

В работе предложена и обоснована модель параллельной программы, и на ее основе спроектированы и реализованы инструментальные средства, которые позволяют на инструментальном компьютере определять границы области масштабируемости параллельной программы, прогнозировать время ее работы на вычислительном кластере, а также использовать выявленные динамические характеристики для нахождения ошибок в организации параллельных вычислений. В работе введено понятие редукции частей модели, позволяющее выполнять интерпретацию отдельных элементов модели параллельной программы. Предложенная методика и инструментальные средства могут быть адаптированы для определения других динамических свойств параллельной программы без изменения требований к инструментальной машине. В работе получены следующие новые научные результаты:

1. Разработана модель программы, параллельной по данным, предложены алгоритмы ее построения и интерпретации. Показано, что интерпретация модели может выполняться на инструментальном компьютере с учетом параметров целевого кластера.

2. Введено понятие частичной интерпретации, позволяющее автономно интерпретировать фрагменты программы (процедуры, циклы, гнезда циклов и т.п.). Сформулированы и обоснованы условия, которым должны удовлетворять фрагменты программы, для того чтобы их частичная интерпретация была корректной.

3. Предложен метод прогнозирования времени выполнения параллельной программы, или ее фрагмента, основанный на интерпретации ее модели. Получены оценки абсолютной и относительной погрешностей прогноза.

4. Разработан интерпретатор модели параллельной программы. Интерпретатор реализован и включён в среду разработки параллельных программ ParJava.

Эти результаты легли в основу разработки и реализации инструментальных средств анализа параллельных программ. Предложенные инструментальные средства позволяют, в частности, выявить узкие места разрабатываемой программы, которые препятствуют ее масштабируемости. Интерпретатор параллельных программ и другие инструментальные средства позволяют перенести доводку прикладных параллельных программ с целевой параллельной вычислительной системы на инструментальную машину, что значительно сокращает сроки разработки и ее стоимость.

Все разработанные средства интегрированы в инструментальную среду ParJava. Среда ParJava, разработанная в ИСП РАН, используется в учебном процессе кафедры системного программирования факультета ВМиК МГУ и кафедры системного программирования ФПМЭ МФТИ.

Среда ParJava доступна по http://www.ispras.ru/groups/ctt/parjava.html.

В дальнейшем планируется снять существующие ограничения реализации. Последующие исследования будут связаны с развитием интегрированной среды ParJava.

В частности, будет разработана и реализована методика интерпретации параллельных программ, учитывающая особенности аппаратуры в случае, когда вычислительные узлы кластера - SMP-машины. Возможности методики прогнозирования времени работы будут распространенны и на программы, использующие интерфейс ОрепМР. Среда ParJava содержит подсистему сохранения и восстановления параллельных программ, основанную на протоколе создания контрольных точек. Интерпретация модели параллельной программы будет использоваться и для сбора профиля используемой памяти, что поможет оптимизировать расположение контрольных точек в программе.

1. В. А. Падарян. Оценка времени работы параллельной программы с помощью интерпретатора среды ParJava. / Препринт Института Системного Программирования РАН №6. М.: ИСП РАН, 2005.

2. В. А. Падарян. Интерпретация иерархической модели в среде ParJava. // Тезисы конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.

3. Виктор Иванников, Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян. Применение среды ParJava для разработки параллельных программ. // Труды Института Системного Программирования, т.5. 2004. с. 41-62.

4. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference. LNCS 2840. Sept. 2003, Venice, pp. 491-494.

5. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Analyzing Dynamic Properties of Parallel Program in ParJava Environment. // Proc. of the conf. Computer science and Information technologies. Sept. 2003, Yerevan, pp. 19-23.

6. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Estimating Scalability of a Parallel Program in ParJava Environment. // Russian Indian Intern. Workshop on HPC, June 2003, Moscow, pp 29-30.

7. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Development of Scalable Parallel Programs in ParJava Environment. // Parallel CFD 2003, May 2003, Moscow, pp. 291 -293.

8. А.И. Аветисян, C.C. Гайсарян, B.A. Падарян. Эффективный обмен данными на сетях JavaVM. // Тезисы докладов, XLIV Научная конференция МФТИ, Современные проблемы фундаментальных и прикладных наук, 4.VII. Ноябрь 2001, Москва -Долгопрудный, с. 29.

9. А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. Параллельное программирование с распределением по данным в системе ParJava. // Вычислительные методы и программирование. 2001 г., Москва, т. 2, №1. с. 129-146.

10. А.И. Аветисян, В.А. Падарян. Библиотека интерфейсов и классов, расширяющих язык Java средствами разработки параллельных программ в модели SPMD. // Труды института системного программирования, 2001, Москва, т.2, с. 49-64.

11. PGHPF Compiler User's Guide, http://www.pgroup.com/doc/pghpfug/hpfug.htm

12. Luiz DeRose and Daniel A. Reed. SvPablo: A Multi-Language Architecture-Independent Performance Analysis System. // Proceedings of the International Conference on Parallel Processing (ICPP'99), Fukushima, Japan, September 1999, pp. 311-318.

13. PGI CDK, Cluster Development Kit. Linux cluster development tools for 32-bit and 64-bit processor-based systems, http://www.pgroup.com/products/cdkindex.htm

14. D. Brown, S. Hackstadt, A. Malony, B. Mohr. Program Analysis Environments for Parallel Language Systems: The TAU Environment. // Proceedings of the 2nd Workshop on

15. Environments and Tools For Parallel Scientific Computing, Townsend, Tennessee, May 1994, pp. 162-171.

16. S. Shende, and A. D. Malony. Integration and Application of the TAU Performance System in Parallel Java Environments. // Proceedings of the Joint ACM Java Grande -ISCOPE 2001 Conference, June 2001, pp. 87-96.

17. Java Native Interface, http://java.sun.eom/j2se/l.4.2/docs/guide/jni/index.html

18. Java Virtual Machine Profiler Interface. http://java.sun.eom/j2se/l.4.2/docs/guide/jvmpi/index.html

19. В. В. Воеводин, Вл. В. Воеводин. Параллельные вычисления. / СПб: БВХ-Петербург, 2000.

20. K. Shanmugam, A. Malony, B. Mohr. Speedy: An Integrated Performance Extrapolation Tool for pC++ Programs. // Proceedings of the Joint Conference PERFORMANCE TOOLS'95 and MMB'95, 20th-22nd September, 1995, Heidelberg, Germany.

21. C.L. Mendes. Performance prediction by trace transformation. // Fifth Brazilian Symposium on Computer Architecture, Florianopolis, September 1993.

22. Jesus Labarta, Sergi Girona, Vincent Pillet, Toni Cortes, and Luis Gregoris. DiP: A Parallel Program Development Environment. // Proceedings of the Euro-Par'96, Vol. II, 1996, pp. 665-674.

23. W. E. Nagel, A. Arnold, M. Weber, H.-C. Hoppe, and K. Solchenbach. VAMPIR: Visualization and analysis of MPI resources. // Supercomputer, 12(1): 69—80, January 1996.

24. Николай Коновалов, Виктор Крюков. Параллельные программы для вычислительных кластеров и сетей. // Открытые системы, 2002, №3.

25. Н.А. Коновалов, В.А. Крюков, С.Н. Михайлов, А.А. Погребцов. Fortran DVM язык разработки мобильных параллельных программ. // Программирование 1995, №1.

26. Н.А. Коновалов, В.А. Крюков, Ю.Л. Сазанов. C-DVM язык разработки мобильных параллельных программ. // Программирование №1, 1999.

27. J. С. Yan, S. R. Sarukkai, and P. Mehra. Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs using the AIMS Toolkit. // Software Practice & Experience. April 1995. Vol. 25, No. 4, pp 429-461.

28. S. R. Sarukkai, J. C. Yan, and J. Gotwals. Normalized Performance Indices for Message Passing Parallel Programs. // Proceedings of the International Conference on Supercomputing ICS-94, Manchester, England, July 11-15, 1994. pages 323-332.

29. Sundeep Prakash and Rajive Bagrodia. MPI-Sim: Using Parallel Simulation to Evaluate MPI Programs. // Proceedings of the Winter Simulation Conference, 1998, pp. 467-474.

30. Thomas Phan and Rajive Bagrodia. Optimistic Simulation of Parallel Message-Passing Applications. // Proceedings of the fifteenth workshop on Parallel and distributed simulation, 2001, pp. 173-181.

31. Mendel Rosenblum, Edouard Bugnion, Scott Devine, and Stephen Alan Herrod. Using the SimOS Machine Simulator to Study Complex Computer Systems. // Modeling and Computer Simulation, vol. 7, №1, 1997, pp. 78-103.

32. Sundeep Prakash, Ewa Deelman, and Rajive Bagrodia. Asynchronous Parallel Simulation of Parallel Programs. // IEEE Transaction on Software Engineering, May 2000, Vol. 26, No. 5, pp. 385-400.

33. J. Misra. Distributed Discrete-Event Simulation. // ACM Computing Surveys, Vol. 18, Issue 1, March 1986, pp. 39-65.

34. K.M. Chandy and R. Sherman. The conditional event approach to distributed simulation. // Proceedings of the SCS Multiconference on Distributed Simulation, Tampa, FL, March 1989, pp. 95-99.

35. Adve, V. S., R. Bagrodia, E. Deelman, T. Phan and R. Sakellariou. // Compiler-Supported Simulation of Highly Scalable Parallel Applications. // Proceedings of the IEEE/ACM SC99 Conference, November 13-18, 1999, Portland, Oregon, USA, pp. 1-20.

36. Vikram Adve and John Mellor-Crummey. Using Integer Sets for Data-Parallel Program Analysis and Optimization. // Proceedings of the SIGPLAN'98 Conference on Programming Language Design and Implementation (PLDI), Montreal, CA, June 1998, pp. 186-198.