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

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

КУДРЯВЦЕВ Максим Владимирович

АВТОМАТИЗАЦИЯ ОТЛАДКИ ПАРАЛЛЕЛЬНЫХ

ПРОГРАММ

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

сетей

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

АВТОРЕФЕРАТ

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

Москва - 2006

[ обязательный

бесплатный

ЭКЗЕМПЛЯР

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

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

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

Крюков Виктор Алексеевич.

Официальные оппоненты:

доктор физико-математических наук, член-корр. РАН

Воеводин Владимир Валентинович,

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

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

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

Институт математического моделирования РАН.

Защита диссертации состоится 22 декабря 2006 г. в 11 часов на заседании диссертационного совета Д 50Ï .001.44 в Московском государственном университете им. MB. Ломоносова по адресу: 119992, ГСП-2, г. Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-оЙ учебный корпус, факультет ВМиК, ауд. 685.

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

С текстом автореферата можно ознакомиться иа портале ВМиК МГУ им. М.В.Ломоносова http://cs.msu.su в разделе «Наука» - «Работа диссертационных Советов» - «Д 501.001.44».

Автореферат разослан « 22 » ноября 2006 г. Ученый секретарь

диссертационного совета профессор

Трифонов H Л.

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

Объект исследования п актуальность темы

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

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

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

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

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

Оба этих метода отладки параллельных программ были в середине 90-х годов XX столетия предложены и реализованы в ВУМ-системе, показав высокую эффективность при отладке приложений с незначительным объемом данных и вычислений. В сравнительном отладчике системы Е>УМ впервые реализовано полностью автоматическое определение контролируемых точек и сравниваемых в них переменных. Чем больше контролируемых точек, тем выше точность локализации ошибки. Полный контроль во всех точках программы позволяет обнаружить первые проявления ошибок, но требует при

этом неприемлемое количество ресурсов, которое невозможно

БИБЛИОТЕКА

С.-ЛетсрСург

ОЭ 2В0Т5»гг

е!

отладке научно-технических приложений, требующих

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

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

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

Цель работы

Целью данной диссертационной работы является разработка методов, способных автоматизировать отладку научно-технических приложений, требующих высокопроизводительных вычислений в моделях параллельного программирования с глобальным адресным пространством (ОрепМР, НРР,

тгм).

Научная новизна

Все основные результаты диссертации являются новыми и состоят в следующем:

1. Разработаны новые методы автоматического обнаружения некорректного выполнения параллельных программ, написанных в моделях параллельного программирования с глобальным адресным пространством (ОрепМР, НРР, БУМ). Эти методы, базирующиеся на динамическом контроле выполнения каждого оператора программы посредством его сопоставления со спецификациями параллелизма или с поведением эталонной программы, способны существенно упростить и ускорить отладку параллельных программ.

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

3. Разработанные методы и алгоритмы автоматического обнаружения некорректного выполнения параллельных программ реализованы в | отладчике БУМ-программ.

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

1NAS parallel benchmarks scpemi 2,3. Набор из пяти параллельных ядер и трек модельных приложений, имитирующих вычисления и характеристики перемещения данных больших приложений «шрогазоднышики, подробная информация доступно по ссылке http^ww.nns.nttsa.gov/Software/NPBA

Практическая ценность работы

Предложенные автором методы н алгоритмы предназначены для отладки программ, написанных в моделях параллельного программирования с глобальным адресным пространством OpenMP, HPF н DVM. Однако в некоторых случаях эти методы могут быть применены и для отладки последовательных программ, а так же MPI-программ.

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

Новый отладчик реализован на языке Си и протестирован на демонстрационных программах, входящих в состав системы DVM, Фортран-DVM версиях программ пакета NPB и реальных задачах на ОС Windows и Linux.

Отладчик находится в опытной эксплуатации на ряде крупнейших вычислительных систем России: кластерах МВС-15000ВМ, MBC-6000IM Межведомственного Суперкомпьккгерного Центра РАН, кластере ANT НЙВЦ МГУ, кластере RSC4 Института прикладной математики им. М.В. Келдыша РАН, а так же ЭВМ Regatta и кластере факультета ВМиК МГУ им. М.В. Ломоносова и доступен в исходных кодах. С помощью нового отладчика найдены ошибки в ряде реальных приложений.

Разработанный отладчик так же планируется использовать на практических занятиях факультета ВМиК МГУ в годовом спецкурсе по параллельному программированию кафедр Автоматизации систем вычислительных комплексов и Системного программирования.

Апробация работы и публикации

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

1. Научная конференция «Тихоновские чтения», факультет ВМиК МГУ вм. М. В. Ломоносова, Москва, октябрь 2006 г.

2. Всероссийская научная конференция «Научный сервис в сети Интернет: технологии параллельного программирования», Новороссийск, сентябрь 2006 г.

3. Объединенный научно-исследовательский семинар кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ им. М. В, Ломоносова, Москва, июнь 2006 г.

4. X Байкальская Всероссийская конференция «Информационные и математические технологии в науке, технике и образовании», Северобайкальск, июль 2005 г.

5. Научная конференция «Ломоносовские Чтения», факультет ВМиК МГУ им. М. В. Ломоносова, Москва, апрель 2005 г.

6. Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2005», факультет ВМяК МГУ им. М. В. Ломоносова, Москва, апрель 2005 г.

7. Конференция «Технологии Microsoft в теории и практике программирования», факультет ВМиК МГУ им.М. В. Ломоносова, Москва, ноябрь 2004 г.

8. Образовательный семинар Зимней Школы Intel, Нижний Новгород, февраль 2004 г.

Объем и структура работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы (54 наименования) и приложения. Общий объем работы составляет 96 страниц, работа содержит 2 иллюстрации и 10 таблиц.

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

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

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

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

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

В п. 1.2 приводится обзор стратегий автоматизированной отладки последовательных программ, рассмотрены применения этих стратегий для

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

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

В п. 1.4 подробно рассмотрен подход сравнительной отладки. Обычно сравнительная отладка параллельной программы производится с помощью сравнения промежуточных результатов её выполнения с результатами эталонной последовательной программы. В качестве эталонной программы так же может использоваться и параллельная программа. Детально описаны различия в степени автоматизации существующих инструментов. Впервые в DVM-отладчике было реализовано полностью автоматическое составление множества контролируемых точек и перечня проверяемых в них переменных (однако этим можно было пользоваться только для отладки простых программ с небольшим объемом данных). Позже в NASA было разработано три инструмента сравнительной отладки, но автоматизация в этих инструментах реализована по-другому. Работа первого инструмента основана на вычислении и сравнении контрольных сумм тех массивов, значения которых могли

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

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

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

Во второй главе представлен метод граничных итераций и двойных тел циклов, который направлен на существенное сокращение ресурсов, требуемых для сравнительной отладки и динамического анализа корректности и применим не только для программ, написанных в моделях с глобальным адресным пространством (OpenMP, HPF, DVM). В частности, он может быть применен для динамического контроля и сравнительной отладки последовательных программ, для сравнительной отладки MPI-программ. В его основу положены две простые и новые идеи.

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

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

В п. 2.1 приводится описание метода, в п. 2.2 - его реализация, а в п. 23 ~ результаты экспериментов и выводы.

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

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

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

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

«грани»

«уголки»

Рис. 1.

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

1. сокращение объема обрабатываемой информации;

2. сокращение времени выполнения программ;

3. потерн по покрытию операторов отлаживаемой про1рвммы;

4. потери по диапазону обнаруживаемых ошибок;

5. вероятность пропуска ошибки;

6. потери по точности определения отладчиком места ошибки (точности локализации);

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

Оценки вероятности пропуска и точности локализации ошибок сильно зависят от многих параметров - от программы и совершенных в ней ошибок, выбранных ширины и типа границ. Для адекватной практической оценки необходим представительный набор параллельных программ с типичными ошибками. Такого набора на сегодняшний день не существует. Вероятность пропуска и потери по точности локализации ошибок при использовании метода граничных итераций имеются как в случае динамического анализа корректности, так и при сравнительной отладке. Точность локализации ошибки при сравнительной отладке зависит от того, насколько быстро её проявление отразится на граничных итерациях. Метод интегральных характеристик, представленный в третьей главе, позволяет исключить пропуск ошибок и повысить точность их локализации при сравнительной отладке.

В п. 2,1.2 предложено два вида отладочной инструментации для метода граничных итераций: с одним телом цикла и с двумя телами циклов. Рассмотрим упрощенные примеры инструментации для одномерного цикла (рисунок 2). В инструментированные программы добавлены глобальная переменная логического типа сош! и функция Ьаз_Ыоск8, возвращающая значения логического типа. Эта функция производит разбиение множества итераций цикла на граничные я внутренние подмножества и возвращает значении «истина» столько раз, на сколько подмножеств был разбит исходный цикл. В приведенном примере эта функция задает значения новым границам цикла - переменным Ы и Й.1 и переменной сопЛ, значение которой истинно на граничных подмножествах и ложно - на внутренних. В инструментации первого вида каждый вызов отладчика окружается условным оператором. В инструментации второго вида вместо одного тела цикла генерируется два: одно тело цикла - с вызовами отладчика, другое - без.

£ог Х:яЬ Ъ> й <1о (

<тело цикла беэ вызовов отлад«ика>

}

без отладочной инструментации

while {baa blocks{...)) do if fcondj ~

for I: =1,1 to SI do t «гало цикла a

вцдовакг омтадтека>

)

elao

for I;eil to RI do t <дздло здиюта бед

шзовов о№палчяка>

}_

инструментация «с двумя телами цикла»

Рис 2.

В п. 2,1.3 и 2,1.4 приведены алгоритмы построения множеств итераций для отладки программ на «гранях» и «уголках» многомерных циклов соответственно. Эти алгоритмы реализованы автором в DVM-отладчнке. Вычислительная сложность реализованных алгоритмов составляет 0(г(2г+1)) для границ типа «грани» и 0(^2^-1)) доя границ типа «уголки», где г -размерность цикла.

В п. 24.5 представлен алгоритм построения множеств итераций цикла отлаживаемого запуска по результатам эталонного. Его вычислительная сложность составляет 0(p(log2p+r)), где г - размерность цикла, р - количество подмножеств итераций эталонной трассы для текущего цикла (р = 2х*1-I для границ типа «уголки» и р = 2г+1 для границ типа «грани»).

trhilo {haa_block3 (...)) do

for 1:=Ы to Rl do <

if fcondj

<вызов отладчика> <опара®оры>

i£ (aoad)

<выэов отлаичика> <операюры>

}

инструментам^ «с одним телом цикла»

В п. 2.2 описаны детали реализации метода граничных итераций и двойных тел циклов в отладчике системы 1)УМ. В качестве инструмента для реализации предложенных возможностей был выбран БУМ-отладчик, поскольку в нем уже были реализованы сравнительная отладка и динамический анализ корректности, для которых компиляторы обеспечивают необходимую шструментацню исходного кода. В п. 2.2.1 коротко рассмотрена модель параллелизма ЭУМ, в п. 2.2.2 описаны основные возможности ДОЛЫ-отладчика, методика отладки ОУМ-программ. В п. 2.2.3 приведен разработанный автором функциональный интерфейс для шструментации программ с одним и с двумя телами циклов, приведены примеры инструментации параллельных и последовательных циклов Фортран-ПУМ программ. В п. 2.2.4 представлены основные особенности программной реализации метода, описана семантика введенных функций и параметров отладчика. Дня метода граничных итераций и двойных теп циклов в новом ПУМ-отладчике реализована возможность использования многопроцессорной трассы в качестве эталонной. В п. 2.2.5 приведены изменения формата трассы. В п. 2.2,6 описана реализация оценки покрытия операторов программы. Покрытием операторов программы будем называть множество тех её строк, в которых производились операции чтения или записи в память с вызовами отладчика (эти вызовы выполняются доя всех переменных, в операторах присваивания и условных операторах исходной программы). Сравнение покрытий осуществляется отдельным инструментом, разработанным автором.

В п. 2.3 приведены результаты экспериментов и выводы относительно эффективности метода граничных итераций и двойных тел циклов. Сначала было произведено сравнение вариантов инструментации на Фортран-ОУМ версиях программ пакета МРВ класса А, на границах типа «уголки» ширины 1 на 16 процессорах. Имя класса определяет размеры основных массивов в приложениях ЫРВ. Среднее время выполнения приложений пакета без отладки на 16 процессорах ЭВМ МВС-15000ВМ МСЦ РАН составляет 14,8 секунд , на одном процессоре - 120,7 секунд. Выбор класса А обусловлен желанием сравнить предложенные методы с существующими. На задачах бблыпих размеров такое сравнение было бы невозможно. Сравнение вариантов инструментации проводилось на трех ЭВМ МСЦ РАН: МВС-15000ВМ, МВС-1000М и МВС-60001М при выключенном отладчике (его функции вызывались, но ничего не выполняли).

При обычной отладочной инструментации вызовы отладчика производятся при каждой операции чтения или записи в переменную. Эта инструментация очень сильно замедляет выполнение программы, в среднем, в 50 и более раз. Программа, инструментированная с двойными телами и границей «уголки» ширины 1 практически не замедляется по сравнению с программой без отладочной инструментации, её замедление составляет в среднем 2-3%. Инструментация с двойными телами заметно эффективнее инструментации с одним телом, в среднем от 1,6 до 4 раз, в зависимости от ЭВМ. Такое различие

может быть вызвано разными архитектурами процессоров или особенностями оптимизации компиляторов на этих ЭВМ.

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

В результате последующих экспериментов на границах ширины 1-2 типов "грани" и "уголки" на 16 процессорах ЭВМ МВС-15000ВМ метод граничных итераций и двойных тел циклов продемонстрировал следующие результаты:

• сокращение размеров трасс в сотни - сотни тысяч раз;

в сокращение времен выполнения программ при генерации трасс и динамическом анализе корректности в десятки - тысячи раз;

• сохранение покрытия операторов отлаживаемой программы - 99,4 -99,8%.

Однако данный метод имеет следующие недостатки:

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

• при динамическом анализе корректности необходимо учитывать возможность ложных диагностик об ошибках «чтение неинициализированных данных» или вообще отменить поиск этих ошибок.

В этих экспериментах трассы не накапливались, производилась их генерация в оперативной памяти и оценка размера. Эксперименты с реальным накоплением трасс и со сравнением приведены в п. 3.3.

В третьей главе представлен метод интегральных характеристик массивов и его модификация - комбинированный метод

В п. 3.1 приводится описание метода интегральных характеристик. Этот метод применим только к сравнительной отладке. Его идея заключается в следующем: предлагается сравнивать не элементы массивов, в порядке доступа к ним на итерациях цикла, а только интегральные характеристики этих массивов (например, подсчитанные по какому-либо алгоритму контрольные суммы) по завершении циклов в которых к этим массивам был доступ. Однако такое сокращение сравниваемой информации приводит к потере точности локализации ошибки - неизвестно, какой именно оператор внутри цикла привел к расхождению интегральных характеристик. Для точного указания ошибочного оператора автор модифицировал методику сравнительной отладки следующим образом:

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

2. Далее, при повторном выполнении обеих программ производится подробная сравнительная отладка, но только ва интервале, определяемом динамическими точками, полученными на предыдущем шаге. За пределами этого интервала сравнение данных вообще не производится.

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

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

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

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

В п. 3,2 представлены подробности реализации метода интегральных характеристик массивов в отладчике системы ВУМ. В п. 3.2.1 описана дисциплина нумерации параллельных конструкций БУМ-программ -

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

В п. 3.3 приведены результаты экспериментов с программами пакета NPB с разными вариантами накопления трасс и сравнения с эталонными трассами. Программы были скомпилированы с двумя телами циклов, накопление трасс (с сохранением во внешнюю память) осуществлялось на 16 процессорах ЭВМ МВС-15000ВМ на граничных итерациях типа «уголки» ширины 1. Запуски со сравнением с эталонной 16-ти процессорной трассой производились на одном процессоре. Контрольные суммы вычислялись по завершении параллельных циклов для тех распределенных массивов, к которым был доступ на запись внутри цикла. Рассмотрены запуски программ без отладочной инструментации, с накоплением трассы чтений/записей переменных, с накоплением трассы контрольных сумм, а так же с накоплением трассы чтений/записей переменных и контрольных сумм (комбинированный метод).

Накопление трассы и сравнение поведения программы с эталонной трассой при трассировке контрольных сумм производится медленнее (на 2-4%), чем накопление трассы и сравнение поведения программы с эталонной трассой в случае трассировки чтений/записей переменных. Причина этого замедления заключается в накладных расходах на межпроцессорные обмены при вычислении контрольных сумм. Максимальное замедление при накоплении трассы по сравнению со временем работы неинструментированной программы составило 53%. Максимальный размер трасс составил примерно 160 мегабайт. Максимальное замедление при сравнении однопроцессорного выполнения программы с данными трассы составило 49% от времени выполнения неинструментированной про!раммы.

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

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

Далее приводится реальный случай нахождения ошибки с помощью сравнительной отладки на граничных итерациях в программе решения диффузионной нестационарной задачи на гексагональной сетке, использующей пакет «РЕАКТОР»2. Программа состоит из 70 Фортран-DVM файлов, суммарное количество строк 19029. С помощью нового DVM-отладчика была выявлена переменная, которая должна была иметь атрибут «SAVE», но не имела его. Компилятор Compaq устанавливал этой переменной атрибут «SAVE» по умолчанию, а компилятор ЮМ - нет.

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

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

1 BoposEoa A.B., Головное СЛ. Архив пакета прикладных программ «РЕАКТОР». Препринт Института

прикладкой «атематикк им. MJ3 .Келдыша РАН. №119. М., 2005

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

Автор реализовал в ОУМ-отладчике возможность замены вычисленных редукционных значений на значения эталонной трассы. Однако такая замена производится не всегда, а только в тек случаях, когда вычисленные значения отличаются от эталонных в пределах заданной пользователем точности. Предложенный метод назван методом коррекции результатов редукционных операций.

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

В п. 4.3 приведены результаты экспериментов и вывод относительно эффективности метода коррекции результатов редукционных операций. Эксперименты проводились с Фортран-0УМ программами пакета ЫРВ класса Б. Класс Э был взят для простоты, размеры массивов в нем меньше, чем в классе А. При сравнении 1-процессорных запусков с 2 и 4-процессорными без использования коррекции результатов редукционных операций во всех программах пакета были обнаружены многочисленные различия данных. При использовании коррекции результатов редукционных операций различий не обнаружено ни в одной программе, В случае запуска ошибочной программы с опцией коррекции редукционных результатов и сравнением данных на полное совпадение сразу было бы видно первое существенное различие (а не множество несущественных, вызванных недетерминиэмом).

Делается вывод, что метод коррекции результатов редукционных операций способен сделать возможной сравнительную отладку недетерминированных программ в моделях с глобальным адресным пространством (ОрепМР, ЮТ, ОУМ), недетерминированное поведение которых вызвано изменением порядка операций сложения или умножения при выполнении редукционных операций.

В заключении формулируются основные результаты работы.

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

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

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

3. Разработанные методы и алгоритмы автоматического обнаружения некорректного выполнения параллельных программ реализованы в отладчике DVM-ггрограмм.

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

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

1. Крюков В.А., Кудрявцев М.В. Автоматизация отладки параллельных программ // Вычислительные методы и программирование. Том 7, раздел 2. ht^://www.srcc.msiusu/ruaTi-metb. 2006.102-109.

2. Крюков В.А., Кудрявцев МЛЗ. Развитие средств отладки DVM-программ И Научный сервис в сети Интернет: технологии параллельного программирования. Труды Всероссийской научной конференции. М.: Изд-во МГУ, 2006.135-137.

3. Крюков В .А., Кудрявцев М. В. Отладка параллельных программ // Информационные и математические технологии в науке, технике и образовании. Труды X Байкальской Всероссийской конференции "Информационные и математические технологии в науке, технике и образовании". Часть I. Иркутск: ИСЭМ СО РАН. 2005. 210-214,

4. Кудрявцев МБ. Новые возможности DVM отладчика И Материалы международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2005" секция "Вычислительная математика и кибернетика". М,:МАКС Пресс. 2005.33-34.

5. Кудрявцев М.В., Крюков ВА Повышение эффективности отладки DVM-программ // Технологий Microsoft в теории и практике программирования: тезисы конференции студентов, аспирантов и молодых ученых. М.:МАКС Пресс. 2004. 24.

Напечатано с готового оригинал-макета

Издательство ООО "MAICC Пресс" Лвцетиая ИД N00510crr 03.12.99 г. Подписано к печати 21.11.2ÜÖ6 г. Формат 60x90 1/16, Уоллечл, 1,0. Твраж 70 экз. Заказ 819. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ ям. М.В. Ломоносова, 2-й учебныв корпус, 627 к.

Введение.

Актуальность темы.

Цель и задачи работы.

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

Практическая ценность работы.

Апробация работы.

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

Глава 1. Обзор подходов к отладке параллельных программ.

1.1 Традиционные подходы. Интерактивная отладка, отладочные печати.

1.2 Стратегии автоматизированной отладки последовательных программ.

Глава 2. Метод граничных итераций и двойных тел циклов.

2.1 Описание метода.

2.1.1 Использование граничных итераций.

2.1.2 Инструментация с одним и с двумя телами циклов.

2.1.3 Алгоритм построения множеств итераций для отладки программ на «гранях» многомерных циклов.

2.1.4 Алгоритм построения множеств итераций для отладки программ на «уголках» многомерных циклов.

2.1.5 Алгоритм построения множеств итераций отлаживаемого запуска по результатам эталонного.

2.2 Реализация метода граничных итераций и двойных тел циклов в отладчике системы DVM.

2.2.1 Модель параллелизма DVM.

2.2.2 Основные возможности DVM-отладчика.

2.2.3 Инструментация Фортран-DVM программ с одним и с двумя телами циклов.

2.2.4 Особенности программной реализации метода.

2.2.5 Изменения формата трассы.

2.2.6 Реализация оценки покрытия операторов программы.

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

Глава 3. Метод интегральных характеристик массивов. Комбинированный метод.

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

3.2 Реализация метода в отладчике системы DVM.

3.2.1 Нумерация параллельных конструкций.

3.2.2 Реализация метода интегральных характеристик.

Вычисление контрольных сумм.

Запись/чтение трассы с контрольными суммами.

Формат файла трассы.

Сравнение контрольных сумм.

Новые структуры данных и функции.

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

Глава 4. Метод коррекции результатов редукционных операций.

4.1 Описание метода.

4.2 Реализация метода в отладчике системы DVM.

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

Актуальность темы

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

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

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

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

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

Оба этих метода отладки параллельных программ были в середине 90-х годов XX столетия предложены и реализованы в DVM-системе [36], показав высокую эффективность при отладке приложений с незначительным объемом данных и вычислений. В сравнительном отладчике системы DVM впервые реализовано полностью автоматическое определение контролируемых точек и сравниваемых в них переменных. Чем больше таких точек, тем выше точность локализации ошибки. Полный контроль во всех точках программы позволяет обнаружить первые проявления ошибок, но требует при этом неприемлемое количество ресурсов, которое невозможно обеспечить при отладке научно-технических приложений, требующих высокопроизводительных вычислений. Кроме того, сравнительную отладку невозможно применять к приложениям с недетерминированным поведением.

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

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

Цель и задачи работы

Целью диссертационной работы является разработка методов, способных автоматизировать отладку научно-технических приложений, требующих высокопроизводительных вычислений в моделях параллельного программирования с глобальным адресным пространством (ОрепМР [7], HPF [5], DVM [6]). В соответствии с этой целью были определены следующие задачи:

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

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

3. Программно реализовать разработанные методы и алгоритмы в отладчике системы DVM [8].

4. Оценить эффективность предложенных методов и алгоритмов на представительном наборе параллельных программ.

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

В работе были достигнуты следующие основные результаты:

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

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

3. Разработанные методы и алгоритмы автоматического обнаружения некорректного выполнения параллельных программ реализованы в отладчике DVM-программ.

4. Проведено экспериментальное исследование эффективности созданного отладчика на представительном наборе параллельных программ, включающем пакет NPB [37] и реальные приложения, подтвердившее высокую эффективность разработанных методов и алгоритмов.

Перечисленные результаты обладают научной новизной.

Практическая ценность работы

Предложенные автором методы и алгоритмы могут быть использованы для отладки программ, написанных в моделях параллельного программирования с глобальным адресным пространством OpenMP, HPF и DVM. В некоторых случаях эти методы могут применяться и для отладки последовательных программ, а так же MPI-программ [3].

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

Новый отладчик реализован на языке Си и протестирован на демонстрационных программах, входящих в состав системы DVM, Фортран-DVM версиях программ пакета NPB и реальных задачах на ОС Windows и Linux.

Отладчик находится в опытной эксплуатации на ряде крупнейших вычислительных систем России: кластерах МВС-15000ВМ, MBC-6000IM Межведомственного Суперкомпьютерного Центра РАН, кластере ANT НИВЦ МГУ, кластере RSC4 Института прикладной математики им. М.В. Келдыша РАН, а так же ЭВМ Regatta и кластере факультета ВМиК МГУ им. М.В. Ломоносова и доступен в исходных кодах. С помощью нового отладчика найдены ошибки в ряде реальных приложений.

Разработанный отладчик так же планируется использовать на практических занятиях факультета ВМиК МГУ в годовом спецкурсе по параллельному программированию кафедр Автоматизации систем вычислительных комплексов и Системного программирования.

Апробация работы

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

1. Научная конференция «Тихоновские чтения», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Автоматизация отладки параллельных программ», октябрь 2006 г.

2. Всероссийская научная конференция «Научный сервис в сети Интернет: технологии параллельного программирования». Доклад «Развитие средств отладки DVM-программ», Новороссийск, сентябрь 2006 г.

3. Объединенный научно-исследовательский семинар кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ им. М.В. Ломоносова. Доклад «Автоматизация отладки параллельных программ», Москва, июнь 2006 г.

4. X Байкальская Всероссийская конференция «Информационные и математические технологии в науке, технике и образовании». Доклад «Отладка параллельных программ», Северобайкальск, июль 2005 г.

5. Научная конференция «Ломоносовские Чтения», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Сравнительная отладка параллельных программ», Москва, апрель 2005 г.

6. Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2005», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Новые возможности DVM отладчика», Москва, апрель 2005 г.

7. Конференция «Технологии Microsoft в теории и практике программирования», факультет ВМиК МГУ им. М.В. Ломоносова. Москва, ноябрь 2004 г.

8. Образовательный семинар Зимней Школы Intel. Доклад «Сравнительная отладка DVM-программ», Нижний Новгород, февраль 2004 г.

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

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

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

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

В заключении перечисляются основные результаты работы.

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

Заключение

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

В работе были достигнуты следующие основные результаты:

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

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

3. Разработанные методы и алгоритмы автоматического обнаружения некорректного выполнения параллельных программ реализованы в отладчике DVM-программ.

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

1. Single UN1. Specification V3. http://www.unix.org/singleunixspecification/

2. MSDN: Processes and Threads. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/base/processesandthreads.asp

3. Message-Passing Interface Forum, http://www.mpi-forum.org

4. Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderam V. PVM 3 User's Guide and Reference Manual // Cambridge, MA, USA:MIT Press, 1994.

5. High Performance Fortran Forum, http://www.hipersoft.rice.edu/hpff/

6. Коновалов H.A., Крюков B.A., Михайлов C.H., Погребцов JI.A. Fortran-DVM язык разработки мобильных параллельных программ//Программирование. 1995. № 1.49-54.

7. OpenMP Consortium, http://www.openmp.org

8. Крюков В.А., Удовиченко Р.В. Отладка DVM- программ // Программирование. 2001. № 3. 19-29.9. pdbx.http://publib.boulder.ibm.com/infocenter/clresctr/vxrx/topic/com.ibm. cluster.pe.doc/pe42/am 103 00223 .html

9. Prism. http://docs.sun.com/app/docs?q=prism

10. Total View, http://www.etnus.com

11. Francioni J. Pancake C.M. High Performance Debugging Standards Effort // Scientific Programming. Amsterdam: IOS Press. Vol. 8. 2000. 95-108.http://web.engr.oregonstate.edu/~pancake/papers/HPDebugForum.pdf

12. Guard Parallel Relative Debugger. http://sourceforge.net/projects/guardsoft/

13. DejaVu project home page. http://researchweb.watson.ibm.com/dejavu/

14. Trace-Driven Debugging of Message Passing Programs. http://ipdps.cc.gatech.edu/1998/papers/166.pdf

15. Tip F. A survey of program slicing techniques. http://domino.research.ibm.com/comm/researchpeople.nsf/pages/tip. jpll995.html

16. Abramson D.A., Sosic R. Relative Debugging using Multiple Program Versions // Intensional Programming I. Sydney: World Scientific. 1995.http://www.csse.monash.edu.au/%7Edavida/papers/islip.pdf

17. Manne F., Andersen S.O. Automating the Debugging of Large Numerical Codes // Modern Software Tools for Scientific Computing. Birkhauser Verlag. 1997. Chapter 16. http://www.ii.uib.no/~fredrikni/fredrik/papers/debug.ps

18. ZPL. http://www.cs.washington.edu/research/zpl/home/index.html

19. Крюков B.A., Удовиченко P.B. Отладка DVM-программ. Препринт ИПМ им. М.В.Келдыша РАН. №56. М., 1999.

20. Hood R., Jost G. Support for Debugging Automatically Parallelized Programs // Proceedings of AADEBUG'2000. Munich. 2000. http://arxiv.org/ftp/cs/papers/0012/0012006.pdf

21. Computer Aided Parallelization Tools (CAPTools). http://www.parallelsp.com/

22. Matthews G., Hood R., Jin H., Johnson S., Ierotheou C. Automatic Relative Debugging of OpenMP Programs. NAS Technical Report NAS-03-014. 2003.http://www.nas.nasa.gov/News/Techreports/2003/PDF/nas-03-014.pdf

23. Jin H., Frumkin M., Yan J. Code Parallelization with CAPO A User Manual. NAS Technical Report NAS-01-008. 2001. http://www.nas.nasa.gov/News/Techreports/2001/PDF/nas-01-008.pdf

24. GDB: The GNU Project Debugger, http://www.gnu.org/software/gdb/

25. The Dyninst API. http://www.dyninst.org/

26. Hood R. The p2d2 Project: Building a Portable Distributed Debugger // Proc. of the ACM SIGMETRICS Symposium on Parallel and Distributed Tools. Philadelphia. 1996. 127-136. http://doi.acm.org/10.1145/238020.238058

27. Vetter J.S., de Supinski B.R. Dynamic Software Testing of MPI Applications with Umpire // Proc. SC2000: High Performance Networking and Computing Conf. 2000.http://www.llnl.gov/CASC/people/vetter/pubs/scOO-umpire-vetter.pdf

28. MPI-CHECK. http://andrew.ait.iastate.edu/HPC/MPI-CHECK.htm

29. Marmot, http://www.hlrs.de/organization/amt/projects/marmot/

30. Intel Thread Checker. http://www.intel.com/cd/software/products/asmo-na/eng/threading/286406.htm

31. Система DVM. www.keldysh.ru/dvm

32. NAS parallel benchmarks. http://www.nas.nasa.gov/Software/NPB/

33. Крюков B.A., Кудрявцев М.В. Автоматизация отладки параллельных программ // Вычислительные методы и программирование. Том 7, раздел 2. http://www.srcc.msu.su/num-meth. 2006. 102-109.

34. Крюков В.А., Кудрявцев М.В. Развитие средств отладки DVM-программ // Научный сервис в сети Интернет: технологии параллельного программирования. Труды Всероссийской научной конференции. М.: Изд-во МГУ. 2006. 135-137.

35. Кудрявцев М.В. Новые возможности DVM отладчика // Материалы международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2005" секция "Вычислительная математика и кибернетика". М.:МАКС Пресс. 2005. 33-34.

36. Кудрявцев М.В., Крюков В.А. Повышение эффективности отладки DVM-программ // Технологии Microsoft в теории и практике программирования: тезисы конференции студентов, аспирантов и молодых ученых. М.:МАКС Пресс. 2004.24.

37. Воронков А.В., Головков СЛ. Архив пакета прикладных программ «РЕАКТОР». Препринт Института прикладной математики им. М.В.Келдыша РАН. №119. М., 2005.

38. Удовиченко Р. В. Отладка DVM-программ. Дис. канд. физ.-мат. наук. М., 2000.

39. Zeller A. Yesterday, my program worked. Today, it does not. Why? // Proc. ESEC/FSE 99. Toulouse. France. September 1999. Vol. 1687 of LNCS. 253-267. http://www.st.cs.uni-sb.de/papers/tr-99-01/

40. Hildebrandt R., Zeller A. Simplifying Failure-Inducing Input // Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis. ACM Press. 2000. 135-145. http://doi.acm.org/10.1145/347324.348938

41. Alpern В. и др. The Jalapeno virtual machine // IBM systems journal, Vol 39. No 1.2000.http://www.research.ibm.com/journal/sj/391/alpern.pdf

42. Alpern В., Choi J.-D., Ngo Т., Sridharan M., Vlissides J. A Perturbation-Free Replay Platform for Cross-Optimized Multithreaded Applications // IBM Research Report 21864 http://www.research.ibm.com/dejavu/rc21864.pdf

43. Zeller A. Isolating cause-effect chains from computer programs // SIGSOFT Softw. Eng. Notes 27, 6 Nov. 2002. 1-10. http://doi.acm.org/10.1145/605466.605468

44. Ladebug debugger manual. ftp://ftp.compaq.com/pub/products/software/developer/ladebugdebu ggermanual.html

45. Сайт с документацией компании Sun. Workshop: Command-Line Utilities, http://docs.sun.com/app/docs/doc/802-5763/6i9ggirrf?q=LockLint#hic

46. Assure for Threads. Reference Manual. Version 4.0. KAI Software, A Division of Intel Americas, Inc. http://www.physics.ohio-state.edu/doco/KAI/assure40/docs/AssureTReference.pdf