Содержание к диссертации
Введение
Глава 1. Обзор подходов к отладке параллельных программ 11
1.1 Традиционные подходы. Интерактивная отладка, отладочные печати 11
1.2 Стратегии автоматизированной отладки последовательных программ 15
Глава 2. Метод граничных итераций и двойных тел циклов 27
2.1 Описание метода 27
2.1.1 Использование граничных итераций 27
2.1.2 Инструментация с одним и с двумя телами циклов 30
2.1.3 Алгоритм построения множеств итераций для отладки программ на «гранях» многомерных циклов 31
2.1.4 Алгоритм построения множеств итераций для отладки программ на «уголках» многомерных циклов 34
2.1.5 Алгоритм построения множеств итераций отлаживаемого запуска по результатам эталонного 35
2.2 Реализация метода граничных итераций и двойных тел циклов в отладчике системы DVM 36
2.2.1 Модель параллелизма DVM 37
2.2.2 Основные возможности DVM-отладчика 38
2.2.3 Инструментация Фортран-DVM программ с одним и с двумя телами циклов 38
2.2.4 Особенности программной реализации метода 44
2.2.5 Изменения формата трассы 48
2.2.6 Реализация оценки покрытия операторов программы 50
2.3 Результаты экспериментов и выводы 51
Глава 3. Метод интегральных характеристик массивов. Комбинированный метод 58
3.1 Описание метода 58
3.2 Реализация метода в отладчике системы DVM 60
3.2.1 Нумерация параллельных конструкций 60
3.2.2 Реализация метода интегральных характеристик 66
Вычисление контрольных сумм 67
Запись/чтение трассы с контрольными суммами 69
Формат файла трассы 72
Сравнение контрольных сумм 73
Новые структуры данных и функции 74
3.3 Результаты экспериментов и выводы 76
Глава 4. Метод коррекции результатов редукционных операций 80
4.1 Описание метода 80
4.2 Реализация метода в отладчике системы DVM 81
4.3 Результаты экспериментов и выводы 83
Заключение 84
Литература
- Стратегии автоматизированной отладки последовательных программ
- Инструментация с одним и с двумя телами циклов
- Алгоритм построения множеств итераций отлаживаемого запуска по результатам эталонного
- Реализация метода интегральных характеристик
Введение к работе
Объект доследования н актуальность темы
С распространением многопроцессорных, многоядерных и кластерных технологий, разработка параллельных программ становится все более актуальной. Развитые инструменты отладки способны существенно облегчить и ускорить их разработку.
Параллельные алгоритмы и программы, как правило, сложнее последовательных. Параллельные программы и отлаживать сложнее. Кроме того, в них возможны н нетипичные для последовательных программ ошибки, вызываемые некорректной синхронизацией процессов или нитей и некорректным использованием средств, обеспечивающих параллелизм. Существенно усложняет отладку параллельных программ их недетерминированное поведение, поскольку оно затрудняет использование привычного приема постепенной локализации ошибок посредством многократных запусков программы иод управлением отладчика.
Ручные методы отладки, основанные на точках останова и отладочных печатях, неадекватны сложности многих реальных научно-технических приложений. Кроме того, ручные методы неприменимы для отладки приложений, полученных с помощью средств автоматизации распараллеливания.
Автоматизированные методы - сравнительная отладка и динамический анализ корректности - могли бы существенно облегчить и ускорить отладку параллельных программ. Динамический анализ эффективен для поиска неверных спецификаций параллелизма, реальных и потенциальных дедлоков, некорректного доступа к общим данным, ошибочных обращений и последовательностей обращений к библиотекам и прочих ошибок. Анализ некоторых ошибок, таких как необъявленная зависимость по данным, выход за границы массива, доступ к неинициализированным переменным требует отслеживания обращений к памяти и существенно замедляет выполнение программы, не позволяя тем самым обнаруживать эти ошибки в научно-технических приложениях, требующих высокопроизводительных вычислений.
Сравнительная отладка заключается в сравнении двух запусков программы - эталонного и отлаживаемого. Обнаруженные при этом различия используются для локализации ошибок.
Оба этих метода отладки параллельных программ были в середине 90-х годов XX столетия предложены и реализованы в DVM-системе, показав высокую эффективность при отладке приложений с незначительным объемом данных и вычислений. В сравнительном отладчике снстемы DVM впервые реализовано полностью автоматическое определение контролируемых точек и сравниваемых в них переменных. Чем больше контролируемых точек, тем выше точность локализации ошибки. Полный контроль во всех точках программы позволяет обнаружить первые проявления ошибок, но требует при
этом неприемлемое количество ресурсов, которое невозможно (одеелезнгйіррил Ь НЛЯ
С.-ЛетсрСург
ОЭ 280?айт{ :
отладке научно-технических приложений, требующих
высокопроизводительных вычислений. Кроме того, сравнительную отладку невозможно применять к приложениям с недетерминированным поведением
Для автоматизации отладки реальных научно-технических приложений можно было бы воспользоваться методами сравнительной отладки и анализа корректности, если бы удалось найти способы существенного сокращения (в сотни и тысячи раз) необходимых для этих методов ресурсов памяти и времени.
Диссертационная работа посвящена проблеме разработки методов автоматизированной отладки научно-технических приложений, требующих высокопроизводительных вычислений.
Цель работы
Целью данной диссертационной работы является разработка методов, способных автоматизировать отладку научно-технических приложений, требующих высокопроизводительных вычислений в моделях иараллельного программирования с глобальным адресным пространством (ОрепМР, HPF, DVM).
Научная новизна
Все основные результаты диссертации являются новыми и состоят в следующем:
Разработаны новые методы автоматического обнаружения некорректного выполнения параллельных программ, написанных в моделях параллельного программирования с глобальным адресным пространством (ОрепМР, HPF, DVM). Эти методы, базирующиеся на динамическом контроле выполнения каждого оператора программы посредством его сопоставления со спецификациями параллелизма или с поведением эталонной программы, способны существенно упростить и ускорить отладку параллельных программ.
Разработаны алгоритмы автоматического определения контролируемых точек выполнения программы, обеспечивающие существенное сокращение требуемых ресурсов времени и памяти и высокую точность обнаружения первых проявлений некорректного поведения параллельной программы.
Разработанные методы и алгоритмы автоматического обнаружения некорректного выполнения параллельных программ реализованы в і отладчике DVM-программ.
Проведено экспериментальное исследование эффективности созданного отладчика на представительном наборе параллельных программ, включающем пакет NPB1 и реальные приложения, подтвердившее высокую эффективность разработанных методов и алгоритмов.
1NAS parallel benchmarks версті 2,3. Набор из пяти параллельных ядер и трех модельных приложений, имитирующих вычисления и характеристики перемещения данных больших приложении гидрогазоднншикя, подробная информация доступно по ссылке http^
Практическая ценность работы
Предложенные автором методы н алгоритмы предназначены для отладки программ, написанных в моделях параллельного программирования с глобальным адресным пространством OpenMP, HPF н DVM. Однако в некоторых случаях эти методы могут быть применены и для отладки последовательных программ, а так же МРІ-программ.
Новый DVM-отладчик, включающий в себя предложенные и реализованные автором методы и алгоритмы, способен производить отладку таких приложений, отладка которых до этого была невозможна в силу очень больших требований алгоритмов предыдущей версии отладчика к ресурсам памяти и времени.
Новый отладчик реализован на языке Си и протестирован на демонстрационных программах, входящих в состав системы DVM, Фортран-DVM версиях программ пакета NPB и реальных задачах на ОС Windows и Linux.
Отладчик находится в опытной эксплуатации на ряде крупнейших вычислительных систем России: кластерах МВС-15000ВМ, MBC-6000IM Межведомственного Суперкомпьютерного Центра РАН, кластере АКТ НИВЦ МГУ, кластере RSC4 Института прикладной математики им. М.В. Келдыша РАН, а так же ЭВМ Regatta и кластере факультета ВМиК МГУ им. М,В. Ломоносова и доступен в исходных кодах. С помощью нового отладчика найдены ошибки в ряде реальных приложений.
Разработанный отладчик так же планируется использовать на практических занятиях факультета ВМиК МГУ в годовом спецкурсе по параллельному программированию кафедр Автоматизации систем вычислительных комплексов и Системного программирования.
Апробация работы н публикации
Результаты диссертации опубликованы в работах [1]-[5] и обсуждались на следующих конференциях и семинарах:
Научная конференция «Тихоновские чтения», факультет ВМиК МГУ им. М В. Ломоносова, Москва, октябрь 2006 г.
Всероссийская научная конференция «Научный сервис в сети Интернет: технологии параллельного программирования», Новороссийск, сентябрь 2006 г.
Объединенный научно-исследовательский семинар кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ им. М. В, Ломоносова, Москва, июнь 2006 г.
X Байкальская Всероссийская конференция «Информационные и математические технологии в науке, технике и образовании», Северобайкальск, июль 2005 г.
Научная конференция «Ломоносовские Чтения», факультет ВМиК МГУ им. М. В, Ломоносова, Москва, апрель 2005 г.
Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2005», факультет ВМиК МГУ им. М. В. Ломоносова, Москва, апрель 2005 г.
Конференция «Технологии Microsoft в теории и практике программирования», факультет ВМиК МГУ им. М. В. Ломоносова, Москва, ноябрь 2004 г.
Образовательный семинар Зимней Школы Intel, Нижний Новгород, февраль 2004 г.
Объем и структура работы
Стратегии автоматизированной отладки последовательных программ
Существует немало исследовательских инструментов, посвященных проблеме автоматизации отладки последовательных программ. В обзоре [52] выделяют следующие стратегии построения этих систем: верификация по отношению к формальным спецификациям; проверки на соответствие знаниям о языке программирования; фильтрация информации по отношению к проявлениям ошибок.
Первая стратегия основывается на том, что пользователь задает формальную спецификацию поведения программы, а инструмент отладки производит верификацию, используя, либо не используя при этом процессы выполнения программы. Формальные спецификации могут быть эффективны для отладки параллельных программ, однако это ручной труд и написание подробной формальной спецификации может быть сравнимо по трудозатратам с написанием самой программы. Кроме того, спецификации, как и отлаживаемая программа, могут содержать ошибки. На сегодняшний день задание формальных спецификаций с целью верификации не является нормой параллельного программирования. Однако существует инструмент LockLint [53], позволяющий в определенных случаях обнаруживать ошибки синхронизации в многонитевых программах, основываясь на статическом анализе программы и дополнительных спецификациях пользователя. Так же стратегия верификации по отношению к формальным спецификациям используется в сравнительной отладке параллельных и последовательных программ, при которой эталонная программа служит формальной спецификацией отлаживаемой.
Вторая стратегия заключается в том, что программа анализируется на предмет наличия в ней подозрительных с точки зрения языка программирования, либо типично ошибочных конструкций. В параллельных программах имеет смысл так же проверять корректность параллельных конструкций и обращений к библиотекам, обеспечивающим параллелизм. Применительно к параллельным программам эта стратегия используется методом динамического анализа корректности, который описан ниже.
Третья стратегия состоит в выделении в программе пользователя участков, которые могли повлиять на указанное пользователем проявление ошибки или наоборот, не могли повлиять. Известное применение этой стратегии - вычисление среза программы (program slices) [16] - таких частей её исходного кода, которые влияют на вычисление заданных значений. Эта стратегия используется в качестве вспомогательной в некоторых инструментах сравнительной отладки параллельных программ [22,24], о которых пойдет речь ниже, а так же методом дельта-отладки.
Дельта-отладка была предложена Андреасом Зеллером [45] в 1999 году. Это метод автоматизированной отладки программ, основанный на систематическом тестировании. Дельта-отладка разрабатывалась для определения минимального набора изменений в программе, приводящего к её некорректной работе (обычно АВОСТу). Пусть имеются две программы -первая работающая, а вторая получается из первой изменением некоторых её строк и не работает. Первое применение дельта-отладки [45] заключалось в формировании подмножеств измененных строк кода и переборе этих подмножеств с целью поиска минимального в определенном смысле набора строк, приводящего к некорректной работе программы (описание алгоритма дельта-отладки здесь не приводится из-за его большого размера). В статье [46] авторы применили подход дельта-отладки для формирования минимального теста. В этой статье рассмотрена программа, при компиляции которой компилятор GCC завершал свое выполнение АВОСТом. С помощью перебора подмножеств символов этой программы был определен тест минимальной длины, на котором компилятор завершался аварийно. В этой статье так же рассмотрен случай с минимизацией размера веб-страницы, приводящей к поломке браузера Mozilla при попытке печати. В статье [49] авторы впервые использовали подход дельта-отладки совместно с методом детерминированного воспроизведения для отладки многонитевых Java-программ. Идея состояла в том, чтобы, перебирая различия в планировании нитей запуска программы, дающего верный результат и запуска, дающего неверный результат, определить два плана переключения нитей, минимально различающихся друг от друга, таких, что на одном плане ошибка в программе проявляется, а на другом - нет. Новый комбинированный метод был использован для поиска ошибки в многонитевом тесте из набора SPEC JVM98, который осуществлял трассировку лучей для отображения трехмерной сцены. В последующих статьях этой исследовательской группы упоминаний об отладке параллельных программ не встречается. В статье [50] дельта-отладка применена для поиска минимальных различий в состояниях корректно и некорректно работающих программ на примере компилятора GCC. Различия в состояниях программ способны навести пользователя на мысль о причине ошибки, однако сама техника работы с состояниями программ недостаточно автоматизирована и имеет целый ряд реализационных ограничений.
Инструментация с одним и с двумя телами циклов
Граничными итерациями ширины к одномерного цикла являются к первых и к последних итераций этого цикла. Многомерными циклами будем считать только тесно вложенные одномерные циклы. Для многомерных циклов понятие границы можно ввести несколькими способами. Граничными итерациями типа «грань» ширины к многомерного цикла будем считать те итерации, которые являются граничными ширины к хотя бы для одного из одномерных циклов, входящих в состав заданного многомерного. Граничными итерациями типа «уголки» ширины к многомерного цикла будем считать те итерации, которые являются граничными ширины к для всех одномерных циклов, входящих в состав заданного многомерного. Параметр к и тип границ можно выбрать экспериментально, оценивая покрытие операторов программы на предварительных запусках и выбрав подходящее.
Разбиение на граничные и внутренние итерации должно производиться отладчиком. Чтобы избавиться от необходимости на каждой итерации проверять, является она граничной или нет (а такая проверка отнюдь не тривиальна, поскольку надо учитывать границы циклов на каждом процессоре для обеих конфигураций процессоров, на которых были запущены сравниваемые программы), нужно разбивать итерации на граничные и внутренние подмножества. Отладчик должен обеспечивать правильный порядок обхода этих подмножеств для обеспечения корректного выполнения многомерных параллельных циклов с допустимыми в них зависимостями по данным.
На рисунке 1 приведены примеры разбиения множества итераций двумерного цикла с прямоугольным индексным пространством на граничные (черный цвет) и внутренние (белый) подмножества. Внутренний одномерный цикл идет по столбцам, внешний - по строкам, обход столбцов производится слева-направо, строк - сверху-вниз. Цифрами обозначен порядок обхода подмножеств.
Для оценки эффективности предложенного метода граничных итераций и двойных тел циклов необходимо выбрать критерии. Такими критериями могут выступать: 1. сокращение объема обрабатываемой информации; 2. сокращение времени выполнения программ; 3. потери по покрытию операторов отлаживаемой программы; 4. потери по диапазону обнаруживаемых ошибок; 5. вероятность пропуска ошибки; 6. потери по точности определения отладчиком места ошибки (точности локализации);
Числовые характеристики по первым трем критериям приведены в разделе 2.3. По диапазону обнаруживаемых ошибок в случае сравнительной отладки потерь не возникает, поскольку сравнительная отладка обнаруживает только различия в поведении и данных сравниваемых программ, уменьшиться может только количество обнаруженных различий. Ошибка «доступ к неинициализированным данным» может быть обнаружена анализом корректности, но поскольку анализ производится только на граничных итерациях, то множество элементов массивов и переменных, инициализируемых на внутренних итерациях, останутся для отладчика неинициализированными и при доступе к ним будут выданы ошибки. Поэтому при анализе корректности только на граничных итерациях необходимо учитывать возможность ложных диагностик об ошибках «чтение неинициализированных данных» или вообще отменить поиск этих ошибок.
Оценки вероятности пропуска и точности локализации ошибок сильно зависят от многих параметров - от программы и совершенных в ней ошибок, выбранных ширины и типа границ. Для адекватной практической оценки необходим представительный набор параллельных программ с типичными ошибками. Такого набора на сегодняшний день не существует. Вероятность пропуска и потери по точности локализации ошибок при использовании метода граничных итераций имеются как в случае динамического анализа корректности, так и при сравнительной отладке. Точность локализации ошибки при сравнительной отладке зависит от того, насколько быстро её проявление отразится на граничных итерациях. Рассмотренный в третьей главе метод способен исключить пропуск ошибок и повысить точность их локализации при сравнительной отладке.
Алгоритм построения множеств итераций отлаживаемого запуска по результатам эталонного
Модель параллелизма DVM [36] разработана в 1993 году в Институте прикладной математики им. М.В. Келдыша РАН и положена в основу языков параллельного программирования Фортран- и Си-DVM. Аббревиатура DVM (Distributed Virtual Memory, Distributed Virtual Machine) отражает поддержку глобального адресного пространства на распределенных системах.
При разработке модели DVM авторы руководствовались следующими принципами [36]: данные и соответствующие вычисления по процессорам виртуальной параллельной машины распределяет программист; ответственность за соблюдение правила собственных вычислений возлагается на программиста; общие данные определяет программист (данные, вычисляемые на одних процессорах и используемые на других процессорах); точки в последовательной программе, в которых происходит обновление значений общих данных, задает программист.
На основе DVM-модели разработаны спецификации параллелизма для языков Фортран и Си. Эти спецификации могут быть проигнорированы стандартными компиляторами, делая возможным выполнение DVM-программ как обычных последовательных программ. После обработки специальными трансляторами DVM-программы преобразуются в программы на языках Фортран и Си с вызовами библиотеки Lib-DVM. Высокий уровень модели DVM позволяет производить основную работу по реализации распределения данных и вычислений библиотеке Lib-DVM, которая так же может осуществлять и динамическую настройку DVM-программ на их параметры (например, размеры массивов) и конфигурацию вычислительной системы.
Помимо трансляторов с языков Фортран- и Си-DVM, библиотеки Lib-DVM, частью которой является DVM-отладчик, в состав DVM-системы входят анализатор и предсказатель производительности.
Авторами DVM отладчика предложена следующая методика отладки DVM-программ [44]:
Этап 1. DVM-программа отлаживается как обычная последовательная программа с помощью стандартных инструментов отладки последовательных программ;
Этап 2. Производится динамический анализ корректности DVM-программы при её однопроцессорном выполнении;
Этап 3. Производится сравнительная отладка DVM-программы посредством сравнения промежуточных данных многопроцессорного запуска с данными однопроцессорного.
При сравнительной отладке DVM-программ производится сравнение данных выполнения отлаживаемой программы с данными эталонной трассы, собранной при последовательном выполнении. Помимо режимов сравнения и накопления трассы имеется режим, позволяющий определить предполагаемый размер трассы. Данные оценки размера трассы сохраняются в специальный конфигурационный файл, в котором так же хранится информация об основных конструкциях программы.
Предложенные автором два вида инструментации для метода граничных итераций (с одним и двумя телами циклов) реализованы в трансляторе Фортран-DVM.
Параллельные многомерные DVM-циклы и соответствующие им тесногнездовые циклы с прямоугольным индексным пространством в последовательной программе при инструментации и работе отладчика рассматриваются как многомерные циклы. Вложенные последовательные циклы инструментируются и выполняются как вложенные одномерные циклы.
Ниже приведен интерфейс на языке Си, разработанный автором для управления вызовами отладчика на разных итерациях циклов. Этот интерфейс не зависит от выбранного пользователем типа отладочной инструментации (с одним или двумя телами циклов). void dvtr_ (int VTR, int conv_mode) ;
Функция сохраняет во внутренних структурах DVM-отладчика передаваемый ей адрес переменной VTR, которая заведена в Фортран-программе с именем dbgvarOO. При помощи изменений значения этой переменной обеспечивается вызов функций отладчика на граничных итерациях и отсутствие таких вызовов на внутренних итерациях циклов. С помощью второго параметра передается режим, в котором транслировалась программа, 0 - последовательный (опция конвертера "-s"), 1 - в противном случае. long doplmb_(LoopRef LoopRefPtr, long No) Параметрами функции являются дескриптор параллельного цикла (LoopRefPtr) и номер конструкции (No). Функция производит разбиение множества итераций параллельного цикла на граничные и внутренние подмножества (подробнее см. раздел 2.2.3). Функция возвращает ненулевое значение столько раз, на сколько подмножеств разбивается первоначальное множество итераций. При необходимости продолжения выполнения цикла параметры цикла (значения начальных и конечных итераций) получают требуемые значения. Функция возвращает 0, когда выполнение цикла следует завершить.
Реализация метода интегральных характеристик
Режимы работы отладчика с вычислением контрольных сумм (накопление трассы и сравнение с эталонной трассой) реализованы с помощью отдельного уровня подробности, включение которого производится с помощью установки параметру TraceOptions.TraceLevel значения 4. Так же реализована возможность вычисления контрольных сумм вдобавок к накоплению трассы с другими уровнями подробности. Эта возможность полезна для использования совместно с методом граничных итераций, её включение осуществляется с помощью установки параметру TraceOptions.CalcChecksums значения 1 (по умолчанию 0).
Рассмотрение реализации уровня подробности контрольных сумм удобно произвести по следующему плану: 1. Сбор информации о читаемых и изменяемых элементах массивов и вычисление контрольных сумм этих массивов по окончании параллельных циклов и областей задач. 2. Запись/чтение трассы с контрольными суммами и конфигурационного файла.
Сравнение контрольных сумм, полученных в процессе выполнения программы с контрольными суммами, прочитанными из трассы. Вычисление контрольных сумм
К элементам массивов возможны следующие типы доступа: a) чтение; b) запись; c) чтение и запись.
Далее, под словами «доступ к массиву» будем понимать доступ к элементам этого массива.
Контрольные суммы вычисляются по завершении выполнения параллельных циклов и областей задач для тех массивов, к которым был доступ в этом цикле (или области задач), определяемый новым параметром TraceOptions.ChecksumMode. TraceOptions.ChecksumMode = 1 (по умолчанию). В этом случае контрольные суммы будут вычисляться для массивов, к которым производился доступ типа Ь) или с). TraceOptions.ChecksumMode = 2. Контрольные суммы будут вычисляться для массивов, к которым производился доступ любого из указанных типов. Контрольная сумма элементов массива вычисляется по следующей формуле: Checksum(Array)= У АгтУ - 0 где Nv...,Nn - размеры измерений массива Array, в пределах которых меняются индексные переменные /,,...,/„ соответственно. Деление на количество элементов необходимо для защиты от переполнения. Замечания:
1. Вычисление контрольных сумм может заметно замедлять выполнение параллельной программы в силу того, что один процессор (центральный) должен собрать значения локальных сумм, вычислить окончательную контрольную сумму и разослать её всем остальным процессорам (см. результаты экспериментов в п. 3.3).
2. Вычислять контрольные суммы удобно именно для параллельных конструкций (параллельных циклов и областей задач), поскольку имеется дисциплина их прохождения (любая параллельная конструкция единожды выполняется на всех процессорах текущей процессорной системы) и ограничение на вложенность (параллельные циклы могут быть вложены только в области задач, области задач не могут быть вложены ни друг в друга, ни в параллельные циклы). Для последовательных циклов контрольные суммы не вычисляются.
3. Пусть имеется параллельный цикл (или область задач), а в него (или в задачу области задач) вложены один или несколько последовательных циклов. В этом случае после параллельного цикла (или области задач) будут вычислены контрольные суммы для всех массивов, к которым был доступ непосредственно в параллельном цикле (соответственно, задаче области задач) и во вложенных последовательных циклах.
Введен параметр TraceOptions.ChecksumDisarrOnly, значение 1 которого указывает, что контрольные суммы нужно вычислять только для DVM-массивов. Для обычных размноженных по всем процессорам массивов контрольные суммы при этом не вычисляются.
