Содержание к диссертации
Введение
2. Системы, поддерживающие разработку параллельных программ с использованием символьной интерпретации 10
3. Модель параллельной программы и ее интерпретация 31
3.1 Описание модели 31
3.2 Моделирование коммуникационных функций 34
3.3 Интерпретация модели 48
Интерпретация базовых блоков 51
3.4 Частичная интерпретация 52
3.5 Оценка времени выполнения программы 55
3.6 Интерпретация коммуникационных функций при оценке времени работы программы 57
3.7 Точность оценки времени , 70
4. Описание программного обеспечения , 77
4.1 Работа среды ParJava при построении оценки времени выполнения параллельной программы 77
4.2. Построение статических моделей классов 81
4.3. Компоновка модели 84
4.4. Интерпретатор параллельной программы 85
4.5 Обработка исключительных ситуаций в интерпретаторе 92
4.6. Редукция вершин модели 93
4.7. Частотное профилирование параллельной программы 94
4.8. Инструментирование исходного кода . 96
4.9. Сбор частотного профиля и трассы параллельной программы 97
4.10. Коррекция 98
4.11. Анализ контекста базовых блоков 105
4.12. Получение оценок времени работы базовых блоков 105
4.13. Ограничения реализации 107
5. Результаты численных экспериментов 109
6. Заключение 127
Литература
- Моделирование коммуникационных функций
- Оценка времени выполнения программы
- Построение статических моделей классов
- Сбор частотного профиля и трассы параллельной программы
Введение к работе
Параллельные программы для вычислительных систем с распределенной памятью (кластеров, суперкомпьютеров) разрабатываются и отлаживаются с использованием целевой вычислительной системы, что сопряжено со значительными накладными расходами как по времени разработки, так и по используемым ресурсам.
Целью диссертационной работы является исследование и разработка методов оценки масштабируемости, производительности и других динамических характеристик программы, параллельной по данным, которые позволяют значительно сократить использование целевого вычислительного кластера, перенеся большую часть разработки на средство индивидуального пользования - инструментальный компьютер (рабочую станцию).
Актуальность. В настоящее время параллельные вычисления широко применяются для решения инженерных и научных задач. При организации параллельных вычислений необходимо знание динамических характеристик параллельной программы, получаемых с помощью частотных и временных профилей. На данный момент для получения профилей используется целевой вычислительный кластер, особенности доступа к которому существенно увеличивают длительность разработки, а следовательно, и ее стоимость. Поэтому важной задачей является разработка методик, позволяющих оценивать динамические характеристики разрабатываемой программы, минимально вовлекая целевой кластер.
В диссертации рассмотрена проблема предсказания поведения параллельной программы на целевом вычислительном кластере. В работе предложена и обоснована модель параллельной программы, и на ее основе спроектированы и реализованы программные средства, которые позволяют на инструментальной машине определять границы масштабируемости параллельной программы, прогнозировать время ее работы на любом заданном вычислительном кластере, получать профили, трассы и другие динамические характеристики, а также использовать их для нахождения ошибок в организации параллельных вычислений.
Прогноз строится в процессе моделирования работы параллельной программы с учетом параметров предполагаемого целевого вычислительного кластера. Знание динамических характеристик программы позволяет работать над ее улучшением, оставаясь на инструментальной машине. Предполагается, что оценки динамических характеристик строятся в диалоговом режиме, поскольку в случае неудовлетворительной производительности программы такой подход позволяет лучше понимать причины, ее вызвавшие.
Разработанная методика может применяться для качественного моделирования поведения программы на нескольких кластерах с разными параметрами, что позволяет выбрать кластер, который лучше всего удовлетворяет требованиям прикладного программиста. Следует отметить, что в этом случае оценки динамических характеристик будут достаточно грубыми. Поэтому после выбора кластера необходимо повторно вычислить динамические характеристики, используя точное знание параметров кластера.
Анализируя существующие системы, поддерживающие разработку параллельных программ, среди них можно выделить три типа: (1) среды разработки, выявляющие характеристики параллельной программы во время ее выполнения па целевом вычислительном кластере, (2) интерпретаторы параллельных программ, выполняющиеся на инструментальном кластере {как правило, менее мощном, чем целевой) и прогнозирующие время их работы и (3) среды разработки, обеспечивающие оценку динамических характеристик параллельной программы с помощью инструментальных программ, работающих на инструментальном компьютере.
Однако существующие методы оценки динамических характеристик либо существенно ограничивают возможность варьирования параметров целевого кластера, либо не обеспечивают должной точности прогноза. Методика, предложенная в диссертации, оценивать динамические характеристики параллельной программы с требуемой точностью на инструментальном компьютере. Это позволяет осуществлять большую часть «доводки» параллельной программы без использования целевого кластера. Основные результаты. В диссертации получены следующие результаты, характеризующиеся научной новизной.
Разработана модель программы, параллельной по данным, предложены алгоритмы ее построения и интерпретации. Показано, что интерпретация модели может выполняться на инструментальном компьютере с учетом параметров целевого кластера.
Введено понятие частичной интерпретации, позволяющее автономно интерпретировать фрагменты программы (процедуры, циклы, гнезда циклов и т.п.). Сформулированы и обоснованы условия, которым должны удовлетворять фрагменты программы, для того чтобы их частичная интерпретация была корректной.
Предложен метод прогнозирования времени выполнения параллельной программы, или ее фрагмента, основанный на интерпретации ее модели. Получены оценки абсолютной и относительной погрешностей прогноза.
4. Разработан интерпретатор модели параллельной программы. Интерпретатор реализован и включён в среду разработки параллельных программ ParJava.
Практическая ценность работы. Все разработанные средства интегрированы в инструментальную среду ParJava (среда ParJava является интегрированной средой разработки переносимых параллельных, программ для вычислительных систем с распределенной памятью). Предложенная методика прогнозирования времени работы параллельной программы и инструментальные средства, поддерживающие эту методику, могут быть адаптированы для определения других динамических характеристик. В частности, интерпретатор может использоваться для выявления ошибок организации параллельных вычислений, таких, например, как взаимоблокировка процессов параллельной программы, потеря данных при коммуникациях, узкие места и т.п.
Среда ParJava, разработанная в ИСП РАН, используется в учебном процессе кафедры системного программирования факультета ВМиК МГУ и кафедрысистемного программирования ФУПМ МФТИ. ParJava используется как средство разработки в проекте по созданию библиотеки методов параллельного символьного решения задач линейной алгебры PolyCalc (Тамбовский государственный университет). Проект ParJava поддержан грантами РФФИ и Минпромнауки.
Среда ParJava доступна по .
Апробация работы.
Основные результаты работы опубликованы в статьях [1] - [14]. Результаты работы обсуждались на следующих конференциях и семинарах:
Международная конференция «Avances en la Ciencia de la Computacjon, ENC'04», Colima, Mexico. Septiembre 20 - 24, 2004.
Всероссийская научная конференция «Научный сервис в сети Интернет», Новороссийск, 20 - 25 сентября, 2004.
Конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 4-5 марта 2004 года.
Международная конференция «The 10th EuroPVM/MPl conference», Venice, Italy. September 29 - October 2,2003;
Международная конференция «Computer science and Information technologies», Yerevan. September 22-26, 2003;
Международная конференция «Вычислительная механика и современные прикладные программные системы», Владимир. 30 июня - 5 июля, 2003;
Международная конференция «Parallel and Distributed Processing Techniques and Applications», Las Vegas. June 23 - 26, 2003;
Международный семинар «Russian — Indian Intern. Workshop on HPC», Москва. 16 — 20 июня, 2003;
Международная конференция «Parallel Computational Fluid Dynamics», Москва. 13 — 15 мая, 2003;
Конференция «Современные проблемы фундаментальных и прикладных наук», Москва - Долгопрудный. 23 - 30 ноября, 2001.
Краткое содержание работы. В разделе 2 приводится обзор систем, поддерживающих разработку параллельных программ с использованием символьной интерпретации. В настоящее время в различных исследовательских центрах мира ведется ряд проектов, в которых изучаются возможности анализа производительности параллельных программ посредством их символьной интерпретации. Разработкой систем поддержки занимаются как учебные заведения, так и различные государственные и коммерческие учреждения и организации. В обзоре рассмотрены и сравнены между собой различные научно-исследовательские и коммерческие системы. Анализ этих систем позволил уточнить постановку задачи.
В разделе 3 рассматривается модель параллельной программы и способ ее интерпретации. Предлагается строить модель параллельной Java-программы на основе ее абстрактного синтаксического дерева (АСД). Вводится набор базовых коммуникационных операций, коммуникационные функции MPI рассмотрены как композиция базовых операций. Определяется интерпретация модели параллельной программы. Вводится понятие редукции вершины модели параллельной программы, а также понятие корректности редукции. Сформулированы и доказаны достаточные требования корректности редукции. Рассмотрены особенности интерпретации для того случая, когда вычисляется оценка времени работы параллельной программы. Предложена методика предварительной оценки времени работы базовых блоков Java-программы. Заканчивается раздел набором утверждений об абсолютной и относительной погрешностях прогноза времени работы параллельной программы, получаемого при ее интерпретации. Все утверждения сопровождаются доказательствами.
В разделе 4 описано программное обеспечение, позволяющее прогнозировать время выполнения программы, параллельной по данным. Подробно описываются внутреннее представление параллельной Java-программы и реализация интерпретатора. Особое внимание уделено процессу выявления динамических свойств программы, в состав которого входят инструментация исходного кода, сбор профилей и компенсация влияния инструментальных операторов.
В разделе 5 рассматриваются три модельные программы, на примере которых демонстрируется погрешность прогноза времени работы. Приводятся многочисленные графики и диаграммы.
Моделирование коммуникационных функций
Управляющее выражение представляет собой последовательность из одного или нескольких базовых блоков (в общем случае представляется внутренней вершиной типа { }). Значение Е будем в дальнейшем обозначать как val(E).
Значения атрибутов вершины Г вычисляются в результате ее интерпретации.
Определены следующие типы внутренних вершин модели: (1) последовательность (внутреннее представление оператора {}): id, [), nil, 1, О, С, (г i, г2, ...), А , (2) переключатель {внутреннее представление оператора switch): id, switch, Е, I, О, С, (г/, Г2, ...), А , (3) ветвление (внутреннее представление операторов if и if-else): id, if, Е, I, О, С, (г), А , id, if-else, Е, I, О, С, (п, rj), А соответственно, (4) цикл for. id, for, Е, I, О, С, (init, {body; update}), A , (5) цикл while: id, while, E, І, О, C, (body), A , (6) цикл do-while: id, do-while, E, І, О, C, (body), A .
В описаниях операторов цикла init обозначает выражение, вычисляющееся при инициализации, body обозначает тело цикла, update обозначает список выражений, выполняющихся в конце каждой итерации цикла.
Будем называть базовым блоком семерку B= id, г, Р, I, О, С, А , где id -идентификатор базового блока (он используется для ссылок на блок В), г— тип базового блока, Р — последовательность инструкций байт-кода, /— список входных переменных, О список выходных переменных, С - список управляющих переменных, т.е. переменных, входящих во множество / какого-либо управляющего выражения или участвующих в вычислении фактических параметров коммуникационных функций, А - список атрибутов базового блока. Определены базовые блоки следующих типов г. вычислительный блок (cb), вызов пользовательской функции (ufc), вызов внешней функции (efc), вызов коммуникационной функции (cfc), редуцированный блок (rb). Атрибуты, входящие в список А, характеризуют динамические свойства программы (такие, как время ее выполнения, объем требуемой памяти, степень локальности данных и др.).
Вычислительный базовый блок моделирует последовательность операторов-выражений, а также сложные выражения, входящие в состав управляющих операторов. Все инструкции, входящие в последовательность Р, выполняются в естественном порядке. Каждый элемент списков /, О и С представляет собой пару пате, id , где пате - имя переменной, id - идентификатор базового блока, содержащего определение переменной пате. Последним оператором последовательности Р может быть break id или continue id, где id - идентификатор вершины модели, выполнение которой надо прервать или повторить.
Замечание 1, Вычислительный базовый блок может состоять только из оператора break, continue или return.
Замечание 2. Операторы исходной программы break и continue, не использующие меток, переводятся соответственно в break id и continue id, где id — идентификатор внутренней вершины, в рамках которой производится завершение выполнения фрагмента программы (идентификатор вычисляется во время построения модели).
Определены три типа базовых блоков, моделирующих вызовы функций. В каждом из таких блоков последовательность Р содержит инструкции байт-кода, обеспечивающие вычисление фактических параметров (если в качестве таких параметров использованы выражения) и еще одной инструкции - вызова функции. Множество атрибутов А определяется обычным образом. Что касается множеств /, О и С, то их определение зависит от типа базового блока.
Для вызовов внешних (а также библиотечных) функций требуется, чтобы пользователь специфицировал их формальные параметры с помощью спецификаторов: in, out, inout. Семантика спецификаторов следующая: in - функция использует, но не изменяет соответствующий параметр, out в функции вычисляется значение параметра, inout - функция и использует, и вычисляет параметр. По определению /содержит все переменные, присутствующие в выражениях, соответствующих параметрам типов in и inout, О содержит все параметры типов out и inout. Множество С строится так же, как и для обычного базового блока.
Замечание. В семантически правильной программе фактические параметры, соответствующие формальным параметрам типов out и inout, должны быть I-значениями.
Поскольку исходный код пользовательских функций доступен, межпроцедурный анализ позволил бы автоматически присвоить спецификаторы in, out, inout их параметрам и построить множества I, О и С. Однако, в настоящей реализации принято ограничение, согласно которому требуется, чтобы параметры таких процедур тоже были специфицированы пользователем аналогично тому, как это делается для внешних функций.
Для коммуникационных функций спецификаторы параметров определяются согласно документации пакета передачи сообщений [47]. Редуцированный базовый блок моделирует поддерево модели. Список Р такого блока пуст. Атрибуты такого блока характеризуют свойства всего фрагмента программы, описываемого блоком. Редуцированные базовые блоки представляют результаты интерпретации соответствующего фрагмента программы, Значения их атрибутов вычисляются во время интерпретации поддерева, заменяемого данным блоком, а в некоторых случаях определяются заранее.
Моделью класса с параллельной Java-программы будем называть список именованных пар S, Т , в которой первая пара имеет имя с._ и содержит пустой элемент Г, а остальные пары последовательности описывают методы этого класса.
Список S первой пары включает: Переменные объекта, объявленные в классе (общедоступные, приватные и защищенные переменные объекта класса с); Статические переменные класса с; Общедоступные статические переменные других классов пакета, в который входит класс с и которые используются в классе с; Общедоступные статические переменные классов других пакетов, которые используются в классе с. Моделью параллельной Java-программы будем называть множество моделей всех классов этой программы.
Оценка времени выполнения программы
Поставим задачу прогноза (оценки) времени выполнения параллельной программы на определенном количестве вершин целевой вычислительной системы. Решение этой задачи можно получить путем интерпретации модели этой программы с целевым атрибутом Time. Как было указано выше, для этого необходимо на модели программы определить функцию вычисления этого атрибута Time(v), где v - вершина модели программы.
Для нетерминальных вершин модели программы атрибут Time по определению вычисляется по следующим правилам:
Time( id, {), nil, I, О, С, (п, г г, ...), А ) = Time(ri) + Time(r$ + ...+ Time(r„) Time( id, if, E, I, O, C, (r), A ) = Time(E) + (val(E)? Time(r): 0) Time( id, if-else, E, I, O. C, (n, n), A ) = Time(E) + (val(E)? Time(r,): Timefrz)) Time( id, switch, E, I, O, C, (rj, Г2, .... r„, г фиіі), A ) = Time(E) + Time(rvai(j) Time( id, while, E, J, O, C, (r), A ) = (Time(E) + (val(E)? Time(r): 0)) Time( id, do-while, E, I, O, C, (r), A ) = Time(r) + (Time(E) + (val(E)? Time(r): 0)) Time( id, for, E, I, О, C, (init, {r; update}), A ) = Time(init) + CTime(E) + (val(E)? Time(r) + Time(update): 0)) В случае последовательного выполнения операторов программы времена их работы складываются. При выполнении оператора if-alse время его работы складывается из времени вычисления селекторной переменной и времени работы одной из ветвей. Если else ветви нет, то при соответствующем значении селекторной переменой время работы оператора равно времени вычисления селекторной переменной. При выполнении оператора switch время его работы складывается из времени вычисления селекторной переменной и времени выполнения потомка rvai(E) (yal(E) определяет какой из потомков выполняется). Время выполнения оператора while состоит из времени вычисления селекторной переменной и времени последовательного выполнения потомков г и Е требуемое количество раз. Время выполнения оператора do-while подсчитывается аналогично while, отличаясь только наличием еще одною слагаемого - времени работы потомка г. Время работы оператора for представляется как сумма времен последовательного выполнения потомка init и оператора while, построенного по следующим правилам: управляющее выражение берется из оператора for, тело состоит из последовательно выполняющихся вершин г и update.
Как уже отмечалось, Time(v) в случае, когда v - вызов пользовательской функции, определяется путем интерпретации этой функции.
Значение функции Time(v), в случае, когда v - вычислительный базовый блок или вызов библиотечной функции, берется из временного профиля программы, полученного на целевой вычислительной системе.
Пользователь также имеет возможность сообщить оценку времени вычислительного базового блока, удовлетворяющего необходимым условиям редукции, или вызова библиотечной функции. Для этого ему необходимо заменить соответствующую вершину редуцированным блоком и присвоить требуемое значение времени его атрибуту Time,
Обычно при временном профилировании оценка времени выполнения участка кода (базового блока) получается как разность показаний системных часов в начале и конце этого участка кода. На большинстве платформ показания системных часов выражаются в миллисекундах. В среде Java единицей измерения времени также является миллисекунда. Поскольку на современных компьютерах время работы базового блока много меньше миллисекунды, временное профилирование программы требует применения специальной методики.
Для получения временного профиля программы необходимо выяснить время работы каждого базового блока. Для получения времени работы вычислительного базового блока применим следующий подход.
Запустим вычислительный базовый блок, время работы которого мы хотим измерить, в автономном цикле (цикл выполняется вне остальной части программы, временной профиль которой мы строим) с достаточно большим количеством итераций (ЛГ) и измерим время работы этого цикла (ТІ). Время работы цикла складывается из времени работы базового блока в цикле (тьь) и накладных расходов на организацию цикла (г 0). Таким образом, Tc = nb+T 0 = N(Tbb+Tj, (1) где Тьь и Т0 - среднее время работы базового блока, которое необходимо измерить, и среднее время накладных расходов на организацию цикла соответственно. Из формулы (1) следует, что tbb = (тс - N7g)/N. Следовательно, для вычисления Тьь необходимо помимо тс получить оценку Т0.
Для получения оценки tc выполняется цикл с пустым телом и количеством итераций Ш, где к - достаточно большое целое число, к подбирается таким образом, чтобы обеспечить достаточную точность оценки Тд. При выполнении пустого цикла измеряется время, т0 = ШТС, откуда NTB - тв /к. Окончательно получаем формулу для оценки Тьь: Tbb=(Tc0/k)/N, (2) где тс и т0 измеряемые значения, а к и N константы, подбираемые таким образом, чтобы обеспечить требуемую точность вычисления Т№.
Таким образом, для получения оценки среднего времени работы базового блока tbh необходимо измерить время работы вспомогательного цикла тс и время работы пустого цикла т0.
Поскольку длительность работы коммуникационной функции может зависеть от момента ее вызова, а также от момента вызова ответной коммуникационной функции, необходимо ввести понятие модельного времени. Следуя работе [36], будем считать, что интерпретация модели параллельной программы выполняется в п независимых логических процессах. Каждый логический процесс имеет свои модельные часы -отображение Iі (v) вершин v модели, интерпретирующейся в логическом процессе і (/-это номер процесса в рамках коммуникатора MPI_CQMM_W0RLD), на моменты времени -показания модельных часов. Начальные показания модельных часов всех логических процессов равны нулю. Показания модельных часов логического процесса обновляются после интерпретации в этом процессе каждого базового блока путем добавления значения атрибута Time базового блока к текущему значению модельного времени. Интерпретация работы коммуникационных функций использует показания модельных часов различных процессов для выбора сценария выполнения коммуникации и определения ее продолжительности. Во время интерпретации коммуникационной функции считаем, что интерпретатор параллельной программы определил логические процессы, участвующие в коммуникации, и доступны показания модельных часов каждого процесса-участника.
Построение статических моделей классов
Интерпретатор при своей работе использует различные параметры целевой системы: мощность вычислительных узлов, латентность и пропускную способность каналов передачи данных, длительность базовых операций MPI, перечисленных в разделе 3.2. Таким образом, располагая моделью программы и описанием целевой вычислительной системы, пользователь получает профиль требуемого уровня модели программы, используя только инструментальный компьютер.
Построение статических моделей классов
Лексический и синтаксический разбор исходного кода параллельной программы выполняется с привлечением пакета JTB [55], разработанного и реализованного в университете Purdue, который позволяет автоматически строить синтаксический анализатор произвольной грамматики и предоставляет набор классов, реализующих различные стратегии обхода АСД. По описанию грамматики языка Java версии 1.2 [56] получены следующие классы: синтаксический анализатор, набор классов, представляющих элементы языка Java, и набор шаблонных классов, реализующих обход вершин АСД. Полученные классы встроены в среду Par Java. Интерфейс Node, реализуемый во всех классах синтаксического дерева, был изменен - он стал расширением интерфейса II Form (см. рис. 7), который не содержит методов, но служит базовым классом для всех элементов внутреннего представления.
Полученное АСД служит основой для формирования объекта класса Filelnfo -контейнера моделей классов. Объект класса Filelnfo содержит: модели всех классов, описанных в соответствующем файле исходного кода, описание областей видимости классов, порожденных операторами import, и объектную ссылку на АСД, полученное при трансляции. Модель класса (класс С lass Descriptor) содержит строковое поле -имя класса, список описаний переменных - членов класса и список моделей методов. Переменная программы (класс Variable) описывается своим типом (класс DataType). Класс DataType используется для описания как базовых типов языка Java, так и произвольных классов. Модель метода (класс Method Descriptor) содержит следующую информацию о методе: имя, количество формальных параметров, тип возвращаемого значения, список описаний локальных переменных (список начинается с описания формальных параметров), модель тела метода. Модель метода строится объектом типа CFGBuilder, выполняющем обход АСД в глубину. Попав в тело метода, этот класс начинает строить модель тела функции. Элементы модели — объекты типа Vertex или его производных типов. Все типы элементов, встречающиеся во внутреннем представлении, показаны на рис. 7 в виде UML-диаграммы. Полное описание интерфейсов и классов представлено в Приложении 1.
После первичной группировки выражений в базовые блоки, в коде программы выявляются вызовы методов, которые затем оформляются в виде отдельных базовых блоков. На этом этапе описываются только общие свойства вызова метода - переменная, на которой метод вызван (если метод не статический), имя метода, список фактических параметров. Построенный таким образом объект типа Filelnf о сериализуется и записывается на диск в виде файла с расширением . ast и может быть в дальнейшем использован инструментальными средствами среды Par Java. \— Q -
Внутренние вершины модели тела метода (экземпляры классов, производных от класса innerVertex) содержат объектные ссылки на своих потомков согласно тому, как это было описано в разделе 3.1.
Базовые блоки типа «вычислительный блок» содержат дескриптор вспомогательного статического метода, в который помещен байт-код этого базового блока. Если у базового блока более одного последователя, то в нем определено поле, являющееся ссылкой на управляющую переменную (возможно временную), позволяющую выбрать следующий блок.
Каждый базовый блок вне зависимости от своего типа содержит набор объектных ссылок на поддеревья исходного АСД. Если тип базового блока «вычислительный блок», то каждая объектная ссылка указывает на выражение, вычисляемое в базовом блоке. Если базовый блок описывает вызов метода, то объектная ссылка указывает на выражение, представляющее собой вызов метода. Эта информация используется лри восстановлении исходного кода по модели программы по требованию пользователя.
Лексемы (листовые вершины) исходного АСД содержат поля, описывающие позиции их начала и конца в исходном коде. Позиция - пара чисел: (номер строки, номер столбца). Эта информация используется при восстановлении исходного кода из промежуточного представления по требованию пользователя.
Исходный код программы восстанавливается по ее АСД следующим образом. АСД передается экземпляру класса Printer, который интерпретирует вершины АСД, вычисляя атрибут Text, исходный код, который породил вершины (сохраненный в объекте системного класса String).
Для листовой вершины исходного АСД атрибут Text определяется как ее значение (значение лексемы). Во внутренних вершинах АСД атрибут Text строится как конкатенация атрибутов Text потомков.
После того, как все файлы, содержащие код программы, переведены во внутреннее представление, строится модель всей программы. Модель представляет собой совокупность моделей методов, взятых из статических моделей файлов. Компоновщик выполняет следующие действия.
(1) Строятся служебные таблицы, позволяющие осуществлять быстрый доступ к переменным и методам классов программы.
(2) Вызовы методов в моделях тел методов специализируются и переводятся в блоки четырех типов:
Пользовательские методы. Базовый блок дополняется полем, содержащим объектную ссылку на модель соответствующего метода.
Вызовы библиотечных (внешних) методов. Вызовы таких методов не моделируются, а непосредственно выполняются. На этапе создания модели объект типа MethodBlock заменяется объектом производного типа LibraryMethodBlock (см. рис. 7).
Коммуникационные методы. Коммуникационные методы характеризуются следующими параметрами: процесс-источник, процесс-приемник, количество единиц пересылаемых данных, длина единицы данных в байтах, идентификатор сообщения - тэг.
Служебные методы MPI. В служебный тип методов MPI выделены методы MPl_Rank и MPI_Size. Их моделирование заключается в возвращении значения служебной переменной из контекста программы,
(3) Строится служебная таблица библиотечных (внешних) методов (функций). Проверяется доступность байт-кода перечисленных методов.
(4) Из набора файлов с оценками времени выполнения базовых блоков данные переносятся в соответствующие базовые блоки (при этом используется файл тар, отображающий номера инструментальных программ на базовые блоки программы).
Сбор частотного профиля и трассы параллельной программы
Интерпретатор при своей работе использует различные параметры целевой системы: мощность вычислительных узлов, латентность и пропускную способность каналов передачи данных, длительность базовых операций MPI, перечисленных в разделе 3.2. Таким образом, располагая моделью программы и описанием целевой вычислительной системы, пользователь получает профиль требуемого уровня модели программы, используя только инструментальный компьютер.
Построение статических моделей классов
Лексический и синтаксический разбор исходного кода параллельной программы выполняется с привлечением пакета JTB [55], разработанного и реализованного в университете Purdue, который позволяет автоматически строить синтаксический анализатор произвольной грамматики и предоставляет набор классов, реализующих различные стратегии обхода АСД. По описанию грамматики языка Java версии 1.2 [56] получены следующие классы: синтаксический анализатор, набор классов, представляющих элементы языка Java, и набор шаблонных классов, реализующих обход вершин АСД. Полученные классы встроены в среду Par Java. Интерфейс Node, реализуемый во всех классах синтаксического дерева, был изменен - он стал расширением интерфейса II Form (см. рис. 7), который не содержит методов, но служит базовым классом для всех элементов внутреннего представления.
Полученное АСД служит основой для формирования объекта класса Filelnfo -контейнера моделей классов. Объект класса Filelnfo содержит: модели всех классов, описанных в соответствующем файле исходного кода, описание областей видимости классов, порожденных операторами import, и объектную ссылку на АСД, полученное при трансляции. Модель класса (класс С lass Descriptor) содержит строковое поле -имя класса, список описаний переменных - членов класса и список моделей методов. Переменная программы (класс Variable) описывается своим типом (класс DataType). Класс DataType используется для описания как базовых типов языка Java, так и произвольных классов. Модель метода (класс Method Descriptor) содержит следующую информацию о методе: имя, количество формальных параметров, тип возвращаемого значения, список описаний локальных переменных (список начинается с описания формальных параметров), модель тела метода. Модель метода строится объектом типа CFGBuilder, выполняющем обход АСД в глубину. Попав в тело метода, этот класс начинает строить модель тела функции. Элементы модели — объекты типа Vertex или его производных типов. Все типы элементов, встречающиеся во внутреннем представлении, показаны на рис. 7 в виде UML-диаграммы. Полное описание интерфейсов и классов представлено в Приложении 1.
После первичной группировки выражений в базовые блоки, в коде программы выявляются вызовы методов, которые затем оформляются в виде отдельных базовых блоков. На этом этапе описываются только общие свойства вызова метода - переменная, на которой метод вызван (если метод не статический), имя метода, список фактических параметров.
Построенный таким образом объект типа Filelnf о сериализуется и записывается на диск в виде файла с расширением . ast и может быть в дальнейшем использован инструментальными средствами среды Par Java. \— Q -
Внутренние вершины модели тела метода (экземпляры классов, производных от класса innerVertex) содержат объектные ссылки на своих потомков согласно тому, как это было описано в разделе 3.1.
Базовые блоки типа «вычислительный блок» содержат дескриптор вспомогательного статического метода, в который помещен байт-код этого базового блока. Если у базового блока более одного последователя, то в нем определено поле, являющееся ссылкой на управляющую переменную (возможно временную), позволяющую выбрать следующий блок.
Каждый базовый блок вне зависимости от своего типа содержит набор объектных ссылок на поддеревья исходного АСД. Если тип базового блока «вычислительный блок», то каждая объектная ссылка указывает на выражение, вычисляемое в базовом блоке. Если базовый блок описывает вызов метода, то объектная ссылка указывает на выражение, представляющее собой вызов метода. Эта информация используется лри восстановлении исходного кода по модели программы по требованию пользователя.
Лексемы (листовые вершины) исходного АСД содержат поля, описывающие позиции их начала и конца в исходном коде. Позиция - пара чисел: (номер строки, номер столбца). Эта информация используется при восстановлении исходного кода из промежуточного представления по требованию пользователя.
Исходный код программы восстанавливается по ее АСД следующим образом. АСД передается экземпляру класса Printer, который интерпретирует вершины АСД, вычисляя атрибут Text, исходный код, который породил вершины (сохраненный в объекте системного класса String).
Для листовой вершины исходного АСД атрибут Text определяется как ее значение (значение лексемы). Во внутренних вершинах АСД атрибут Text строится как конкатенация атрибутов Text потомков.
