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

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

Романенко Алексей Анатольевич

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

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2004

Работа выполнена в Новосибирском государственном университете

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

профессор

Малышкин Виктор Эммануилович

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

♦ доктор технических наук, профессор

Хабаров Валерий Иванович

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

Скопин Игорь Николаевич

Ведущая организация: Нижегородский государственный

университет им. Н.И. Лобачевского

Защита состоится 19 мая 2004 г., в 1600 на заседании диссертационного совета Д 212.173.06 при Новосибирском государственном техническом университете по адресу: 630092, г. Новосибирск, пр. К.Маркса, 20.

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

Автореферат разослан ($ апреля 2004 г.

Ученый секретарь

диссертационного совета Д 212.173.06

Чубич В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

На вычислительных комплексах МВС-1000/М складывается ситуация, когда растет количество пользователей и возрастает количество разрабатываемых программ. Из средств, предоставляемых пользователю для отладки, есть инструменты и библиотеки для разработки как последовательных программ, так и параллельных, при этом, если для разработки первых пользователю также предоставляются и средства отладки (GDB, strace), то пользователь, который занимается разработкой ПП, вынужден отлаживать свои программы с помощью вставления в код программы вызовов функций вывода информации на экран, что очень не эффективно, либо переходить на другие вычислительные комплексы, где есть соответствующие средства.

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

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

Научная новизна. Отладка ПП представляет собой более сложную

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

исполнения ПП состоит из множества последовательных процессов,

которые взаимодействуют между собой. Помимо программ процессов

появляется еще один объект, который—требует отлааки—г система

1 .^„национальная!

БИБЛИОТЕКА 1

3 I

С.Пт» ОЭ Я»

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

1. Минимально влиять на поведение программы. В противном случае

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

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

Эта функция является базовой и реализована в большинстве отладчиков.

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

4. Иметь возможность разбивать программу на логические блоки. Это позволит более детально изучать поведение программы на определенных участках. Эта возможность реализована в отладчиках Vampire, AIMS и отсутствует в Jumpshot, Paradyn.

5. Иметь возможность автоматически сравнить два варианта исполнения программы. Автоматическое сравнение позволит отслеживать, например, ошибки соревнования.

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

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

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

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

Практическая значимость. Практическая значимость работы заключаются в следующем:

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

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

Основные положения и результаты, выносимые на защиту.

1. Поведенческие ошибки в параллельной программе.

2. Методы обнаружения поведенческих ошибок.

3. Подходы к описанию частичного поведения.

4. Технические требования, предъявляемые к отладчику ПП ориентированному на отладку поведения ПП.

5. Архитектура отладчика.

6. Отладчик GEPARD, ориентированный на отладку программ для мультикомпьютеров.

Апробация работы. Результаты проведенных исследований обсуждались и получили признание на Всероссийских и Международных конференциях, школах-семинарах: VIII Всероссийская научно-методическая конференция «Телематика-2001» (Санкт-Петербург, 2001), IX Всероссийская научно-методическая конференция «Телематика-2002» (Санкт-Петербург, 2002), X Всероссийская научно-методическая конференция «Телематика-2003» (Санкт-Петербург, 2003), II научно-практический семинар «Высокопроизводительные параллельные вычисления на кластерах» (Нижний Новгород, 2002), II школа-семинар «Распределенные и кластерные вычисления» (Красноярск, 2002), Seventh International Conference on Parallel Computing Technologies «PaCT-2003» (Нижний Новгород, 2003).

Основные результаты автора опубликованы в работах, список которых указан в конце автореферата.

Акты внедрения результатов работы прилагаются. Копии актов внедрения помещены в приложение 4 текста диссертации.

Публикации. По теме диссертации опубликовано 7 печатных работ, список которых указан в конце автореферата.

Выполнение работы проводилось в соответствии с планами исследований по проекту «Методы и технологии распараллеливания алгоритмов и параллельная реализация численного моделирования на многопроцессорных системах» по Программе № 17.3 фундаментальных исследований РАН «Параллельные вычисления на многопроцессорных вычислительных системах» и междисциплинарному интеграционному проекту СО РАН № 148 «Самоорганизация, катализ и процессы химической эволюции в гравитационно и термодинамически неустойчивых системах, моделирующих ранние этапы формирования Земли».

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и четырех приложений. Работа написана на 112 листах и содержит 16 рисунков и одну таблицу. Список литературы содержит 49 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 «Методы и средства отладки параллельных программ. Анализ и классификация возможных ошибок» - теоретическая часть работы. В ней рассматриваются возможные ошибки в ПП, методы их обнаружения. Обсуждаются подходы к отладке ПП, рассматриваются различные типы отладчиков и их применение для отладки поведения ПП. Формулируются требования к отладчику ПП.

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

Выявлены следующие типы поведенческих ошибок:

• дедлоки;

• ошибки соревнования;

• ошибки коммуникаций;

• неоднородность загрузки вычислительного комплекса;

• не использование всех вычислительных ресурсов. Ошибки на уровне среды выполнения (последние два пункта) названы слабыми ошибками. Подобные ошибки не приводят к некорректному результату. Они оказывают влияние на эффективность решения задачи, что также является критичным.

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

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

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

Для обнаружения ошибок соревнования предлагается использовать следующие методы:

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

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

3. Если имеется два протокола выполнения программы (правильного и неправильного), можно произвести их сравнить и тем самым локализовать ошибку.

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

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

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

• Попытаться исполнить программу как один процесс, и провести последовательную отладку.

• Исполнить программу, запустив два, или четыре процесса на одном узле и проверить правильность передачи сообщений между процессами.

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

• Исполнить программу на реальных данных.

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

Под отладкой поведения понимается проверка соответствия между:

• количеством операций передач сообщений и количеством парных им операций приемов сообщений;

• объемом передаваемых данных и объемом принимаемых данных;

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

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

отладчика), т.е. влияние инструментов отладки должно быть минимальным. Рассматривается три подхода к построению отладчиков:

• мониторинг - анализ данных после завершения программы,

• интерактивная отладка - анализ данных во время выполнения; программы,

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

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

В конце главы формулируются основные требования, предъявляемые к отладчику ПП:

• достоверность - требование к любому типу отладчика,

• обеспечение информационного контекста - сопоставление участкам бинарного кода строк исходного кода программы,

• ориентация на отладку поведения ПП,

• необходимость обнаружения всех рассмотренных типов ошибок,

• минимальное влияние на поведение отлаживаемой программы

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

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

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

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

подсистемы визуализации и анализа. Отладчик относится к классу систем мониторинга и выполнение поставленных требований определяется качеством реализации его компонентов. Архитектура отладчика позволяет легко использовать его на других кластерных и SMP системах. Так, отладчик использовался и тестировался на кластере Новосибирского государственного университета.

Рис. 1. Структура отладчика GEPARD

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

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

смещение времени в процессах относительно какого-то момента в прошлом (запуск программы), - ограничение, накладываемое

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

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

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

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

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

первый подход. Все операторы языка отладки записываются в виде: /*GPRD <инструкция> */ Например, чтобы указать, что процессы могут передавать сообщения только последующему и предыдущему процессу в некоторой линейке процессов, в исходный код необходимо добавить строчку:

/*GPRD SCOMSET $i SEND ($i-l, $i+l) */ Спецификация поведения требует задания множества событий и задания множества протоколов. В качестве событий можно выбрать начало/окончание выполнения оператора языка программирования: Однако таких событий может быть много, и разобраться со множеством всех протоколов будет очень сложно, если не невозможно. Предлагается в качестве событий выбрать такие важные для отладки события как вызовы коммуникационных процедур (все MPI-функции) и разрешить пользователю самому определять события.

На языке отладки пользовательское событие А может быть определено как

/*GPRD EVENT "А" */ или, если необходимо отличать событие А на разных итерациях цикла, как

/*GPRD EVENT "A_%d" i */

На основе выбранного алфавита ожидаемая последовательность событий может быть описана в следующем виде:

/*GPRD STATES 1 "$1 А, В, (C, D), ($1, F)" */

Здесь говорится, что возможными протоколами процесса с идентификатором 1 являются те, которые описываются ориентированным графом, представленным на рисунке 2. Одним из возможных протоколов является следующий: А, В, С, А, В, D, F

Рис. 2. Граф, описывающий протоколы исполнения процесса

В главе 3 «Проект GEPARD» рассматривается реализация подсистем отладчика GEPARD.

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

Отладчиком поддерживаются два языка программирования С и Fortran.

Параллельная программа

Рис. 3. Подсистема контроля выполнения. По одному монитору на каждый процесс ПП

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

Подсистема визуализации и анализа имеет графический (Рис. 4.) и текстовый (Рис. 5.) интерфейсы. Графический интерфейс реализован на

кросс платформенной библиотеке QT и сейчас он (графический интерфейс) существует под ОС Linux и Windows. Ядро подсистемы анализа написано на языке программирования C++ и никак не привязано к системе визуализации и поэтому легко может быть реализовано для других операционных систем и платформ.

Рис. 4. Графический интерфейс подсистемы визуализации и анализа

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

mephisto> gprd_ta -s ./res/puasson.grd Number of sent messages is not equal

to the number of received one (2 to 1) Number of sent messages is not equal

to the number of received one (3 to 2) Send/Reciev table. "GPRD_MAIN_SECT" section I 0 1 1| 2| 3|

0| 0/ 0Ц466/ 7321 0/ 0| 0/ 01 II 732/14661 0/ 011522/ 7611 0/ 0|

2| 0/ 01 760/15221 0/ 0Ц524/ 7621

31 0/ 01 0/ 01 761/15241 0/ 01_

Рис. 5 Пример работы подсистемы визуализации и анализа. Текстовый

режим

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

В конце главы предлагается несколько стратегий развития отладчика GEPARD и кратко описывается его применение.

Отладчик GEPARD неоднократно использовался для анализа поведения ПП в ИВМиМГ и применялся при работе над проектом разработки параллельной программы поиска послеаварийных режимов, выполняемом для Российской энергетической компании.

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

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

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

В приложение 2 описаны все параметры командной строки препроцессора отладчика и текстового варианта подсистемы анализа.

В приложение 3 приведено несколько программ с различными ошибками и дан способ их локализации с помощью отладчика GEPARD. Приложение 4 - копии актов внедрения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

1. Исследованы и проведен анализ моделей вычислений, программы и среды выполнения. На основе анализа выявлены и классифицированы поведенческие ошибки ПП.

2. Предложены методы обнаружения поведенческих ошибок.

3. Сформулированы технические требования, предъявляемые к отладчику ПП ориентированному на отладку поведения ПП.

4. С точки зрения выдвинутых требований проведено исследование существующих отладчиков ПП.

5. Проведен анализ сформулированных технических требований, и предложены способы их реализации. Разработана архитектура отладчика.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Локтев К.А., Мигинский Д.С., Нифонтов В.И., Романенко А.А. Исследование и применение кластерных технологий. Проблемы устойчивости. //Материалы научно-методической конференции "ТЕЛЕМАТИКА-2001". - Санкт-Петербург: Изд-во Санкт-Петербургского государственного университета точной механики и оптики, 2001.с. 162.

2. Малышкин В.Э., Романенко А.А. Отладка и мониторинг параллельных программ. //Материалы научно-методической конференции "ТЕЛЕМАТИКА-2002". - Санкт-Петербург: Изд-во Санкт-Петербургского государственного университета точной механики и оптики, 2002. с. 152-153.

3. Малышкин В.Э., Романенко А.А. Базисные функции отладчика параллельных программ GEPARD и их реализация для МВС-1000/М. Материалы второго научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерах». - Нижний Новгород: Изд-во Нижегородского государственного университета, 2002. с. 248-255.

4. Малышкин В.Э., Романенко А.А. Отладчик параллельных программ. //Материалы второй школы-семинара «Распределенные и кластерные вычисления». - Красноярск: Изд-во ИВМ СО РАН, 2002. с. 155-165.

5. Малышкин В.Э., Романенко А.А. Отладчик параллельных программ для мультикомпьютера. //Автометрия. № 3, т. 39, Изд-во СО РАН Новосибирск, 2003. с. 109-114.

6. Малышкин В.Э., Романенко А.А. Отладчик параллельных программ, для многопроцессорных вычислительных систем. //Материалы научно-методической конференции "ТЕЛЕМАТИКА-2003". - Санкт-Петербург: Изд-во Санкт-Петербургского государственного университета точной механики и оптики, 2003, с. 259-262.

7. Malyshkin V.E., Romanenko A.A., GEPARD - GEneral PARallel Debugger for MVS-1000/M. // In Proceedings of the International conference on Parallel Computing Technologies, Springer Verlag, Lecture Notes in Computer Science series, vol. 2763, 2003, pp. 519-523

Подписано в печать 13.04.04 Уч.изл. л. 1 Офсетная печать. Формат 60x80 1/16 Заказ № 2 04 Тираж 100 экз.

Лицензия ЛР № 021285 от 6 мая 1998 г.

Издательский центр НГУ; 630090, Новосибирск-90, ул. Пирогова, 2

1-8173

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ И СРЕДСТВА ОТЛАДКИ

ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. АНАЛИЗ И КЛАССИФИКАЦИЯ ВОЗМОЖНЫХ ОШИБОК.

1.1. Параллельные вычисления.

1.1.1. Модель.

1.1.2. Анализ ошибок на уровне модели вычислений.

1.2. Поведение параллельной программы.

1.3. Параллельная программа.

1.3.1. Модель.

1.3.2. Реализация модели передачи сообщений.

1.3.3. Анализ ошибок, обусловленных моделью программы.

1.4. Среда выполнения параллельной программы.

1.4.1. Модель.

1.4.2. Реализация.

1.4.3. Анализ ошибок обусловленных средой выполнения.

1.5. Классификация ошибок.

1.6. Методы поиска ошибок в параллельных программах.

1.6.1. Обнаружение дедлоков.

1.6.2. Обнаружение ошибок соревнования.

1.6.3. Обнаружение ошибок в коммуникациях.

1.6.4. Обнаружение несбалансированности загрузки.

1.6.5. Метод отладки параллельных программ.

1.7. Требования к организации отладки параллельных программ.

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

1.8.1. Влияние средств отладки на выполнение программы.

1.8.2. Классиф икацпя инструментов отладки.

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

1.9.1. Total View.

1.9.2. Jumpshot.

1.9.3. AIMS.

1.9.4. Vampire.

1.9.5. Paradyn.

Выводы.

ГЛАВА 2. ОСНОВНЫЕ ПРОЕКТНЫЕ РЕШЕНИЯ И

АЛГОРИТМЫ РЕАЛИЗАЦИИ ОТЛАДЧИКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ GEPARD.

2.1. Многопроцессорная вычислительная система МВС-1000/М.

2.2. Кластер Новосибирского государственного университета.

2.3. Messages Passing Interface (MPI). Параллельная программа HAMPI.

2.4. Формулировка задачи.

2.5. Архитектура отладчика.

2.6. Обработка исходного кода.

2.7. Обеспечение информационного контекста.

2.8. Подсистема контроля выполнения.

2.9. Подсистема визуализации.

2.10. Синхронизация времени.

2.11. Описание поведения системы взаимодействующих процессов.

2.11.1. Выбор алфавита событий.

2.11.2. Определение множества всех протоколов.

2.11.3. Процесс отладки.

2.11.4. Отладка направления передачи данных.

Выводы. щ

ГЛАВА 3. ПРОЕКТ GEPARD.

3.1. Компоненты отладчика.

3.2. Язык отладки. Препроцессор.

3.3. Подсистема контроля выполнения.

3.4. Подсистема анализа собранной информации.

3.5. Анализ информации.

3.6. Использование и перспективы развития отладчика т GEPARD.

Выводы.

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

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

На вычислительном комплексе МВС-1000/М [1] складывается ситуация, когда растет количество пользователей и возрастает количество разрабатываемых программ. Из средств, предоставляемых пользователю для отладки, есть инструменты и библиотеки для разработки, как последовательных, так и параллельных программ. При этом если для разработки первых пользователю также предоставляются и средства отладки (GDB, strace), то пользователь, который занимается разработкой 1111, вынужден отлаживать свои программы с помощью вставления в код вызова функции вывода информации на экран, что очень не эффективно, либо переходить на другие вычислительные комплексы, где есть соответствующие средства.

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

Цель работы

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

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

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

Для отладки ПП необходимо:

1. Минимально влиять на поведение программы. В противном случае некоторые ошибки при отладке могут себя не проявлять;

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

Эта функция является базовой и реализована в большинстве отладчиков.

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

4. Иметь возможность разбивать программу на логические блоки. Это позволит более детально изучать поведение программы на определенных участках. Эта возможность реализована в отладчиках Vampire, AIMS и отсутствует в Jumpshot, Paradyn.

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

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

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

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

Научная и практическая значимость

Научная новизна и практическая значимость работы заключаются в следующем:

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

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

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

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

Выполнение работы проводилось в соответствии с планами исследований по проекту «Методы и технологии распараллеливания алгоритмов и параллельная реализация численного моделирования на многопроцессорных системах» по Программе № 17.3 фундаментальных исследований РАН «Параллельные вычисления на многопроцессорных вычислительных системах» и междисциплинарному интеграционному проекту СО РАН № 148 «Самоорганизация, катализ и процессы химической эволюции в гравитационно и термодинамически неустойчивых системах, моделирующих ранние этапы формирования Земли».

Выводы

Отладчик GEPARD состоит из трех основных компонентов: препроцессора, подсистемы контроля выполнения и анализа информации.

Отладчиком поддерживаются два языка программирования С и Fortran.

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

Система визуализации и анализа имеет графический и текстовый интерфейсы. Графический интерфейс реализован на кросс платформенной библиотеке QT и сейчас он (графический интерфейс) существует под ОС Linux и Windows. Ядро системы анализа не привязано к системе визуализации и поэтому легко может быть реализована версия для других операционных систем. Ядро системы анализа написано на языке программирования С++.

Предложено несколько стратегий развития отладчика GEPARD.

Заключение

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

Результатом выполненной работы является:

1. На основе анализа моделей вычислений, программы и среды выполнения, выявлены и классифицированы поведенческие ошибки ПЛ.

2. Предложены методы обнаружения поведенческих ошибок.

3. Сформулированы технические требования, предъявляемые к отладчику ПП ориентированному на отладку поведения 1111.

4. С точки зрения выдвинутых требований проведен сравнительный анализ существующих отладчиков 1111.

5. Проведен анализ сформулированных технических требований и предложены способы их реализации. Разработана архитектура отладчика.

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

1. Официальный сервер Сибирского Суперкомпьютерного Центра, www2.sscc.ru.

2. Малышкин В.Э. Параллельное программирование мультикомпьютеров. Ярославль. 1999

3. Методическое пособие по многопользовательским многооперационным системам, ermak.cs.nstu.ru/~mos/.

4. Хоар Ч. Взаимодействующие последовательные процессы. Мир. 1989.

5. Hwang, К., and Xu, Z., Scalable Parallel Computing Technology, Architecture, Programming, WCB McGraw-Hill, USA (1998)

6. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. Санкт-Петербург, БХВ-Петербург, 2002.

7. Message Passing Interface Forum. MPI: Message Passing Interface standard.

8. Gropp W., Lusk E., User's Guide for MPICH, a Portable Implementation of MPI Version 1.2.0. Argone National Lab. 1999

9. Burns G., Daoud R., Vaigl J. LAM: An Open Cluster Environment for MPI. Ohaio supercomputer center. 1998.

10. Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderman V. PVM: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing. MIT Press, 1994

11. MPI-2: Extensions on the Message-Passing Interface. www.mpi-forum.org/docs/.

12. Карпов Ю.Г. Анализ корректности параллельной программы разделения множеств. //Программирование. 1996. #5.

13. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт

14. Петербург, БХВ-Петербург, 2002.

15. Фридланд А .Я., Ханамирова Л.С., Фридланд И.А. Информатика. Толковый словарь основных терминов. М. Приор, 1998

16. Grabner S., Kranzlmuller D., Volkert J., A Debugging Strategy for Distributed Memory Machines, in: Proc. Icole'94, Workshop iiber Parallelverarbeitung, Lessach, Austria, pp. 114-123 (Oct. 1994)

17. McDowell Ch.E., Helmbold D.P., Debugging Concurrent Programs, ACM Computing Surveys, Vol. 21, No. 4, pp. 593-622 (December 1989).

18. Krawczyk H., Wiszniewski В., Analysis and Testing of Distributed Software Applications, in: Wilson, D.R., (Ed.), C3 Industrial Control, Computers, and Communication Series, Research Studies Press Ltd., Baldock, Hertfordshire, England (1998).

19. Steve McConnell, Code complete. Microsoft Press. 1993

20. Horward M., LeBlance D., Writing secure code, Microsoft Press. 2003.

21. Microsoft Solution Framework, www.microsoft.com/msf/.

22. Романюк С.Г. Оценка надежности программного обеспечения. //Открытые системы. 1994. #4

23. Петренко А., Бритвина Е., Трошев С., Монахов А., Петренко О. Тестирование на основе моделей. //Открытые системы. 2003. #9

24. Abramson D., Foster I., Michalakes J., Sosic R., Relative Debugging and its Application to the Development of Large Numerical Models //Proceedings of the 1995 АСМЯЕЕЕ Supercomputing Conference, Dec. 1995

25. Geist, G.A., Beguelin, A., Dongarra, J.J., Jiang, W., Manchek, R., Sunderam, V.S., PVM3 User's Guide and Reference Manual, Technical Report, Oak Ridge National Laboratory, Tennessee, MIT Press, Cambridge, MA, USA 1994.

26. Самофалов B.B., Коновалов A.B., Технология отладки программ длямашин с массовым параллелизмом //Вопросы атомной науки и техники, сер. Математическое моделирование физических процессов, вып. 4, 1996, стр. 52-56

27. Rosenberg, J.B., How Debuggers Work: Algorithms, Data Structures, and Architecture, 1996

28. Ландау Л.Д., Лифшиц Е.М. Теоретическая физика. Т.З. Квантовая механика. Нерелятивистская теория. М.: Физматлит, 2001

29. Hollingsworth J.K., Miller В.P. An adaptive cost model for parallel program instrumentation. Proceedings of EuroPar'96, 1996

30. Петренко A.K. Методы отладки и мониторинга параллельных программ (обзор). //Программирование. 1994. #3

31. Etnus, LLC, Parallel debugger TotalView, 2001

32. Hood R. The p2d2 Project: Building a Portable Distributed Debugger. 1996 www.nas.nasa.gov/Groups/Tools/Projects/P2D2.

33. Zaki, O., Lusk, E., Gropp, W., Swider, D., Toward Scalable Performance Visualization with Jumpshot, 2001

34. Yan, J.C., Sarukkai, S.R., Mehra, P., Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs using the AIMS Toolkit, 1995

35. Visualization and Analysis of Parallel Programs, www.pallas.com/e/products/vampir.

36. Баранов A.B., Лацис A.O., Храмцов М.Ю., Шарф С.В. Руководство системного программиста (администратора) системы управленияпрохождением задач МВС-1000/М (версия 2.01). www.j scc.ru/infonnat/1000MPrgGuide.zip.

37. Страница кластера Новосибирского государственного университета ccfit.nsu.ru/cluster.

38. Карпов В.Я. Алгоритмический язык Фортран. М.: Наука. 1976

39. Немнюгин С., Стесик О. Современный Фортран. Самоучитель. Санкт-Петербург, БХВ-Петербург, 2004

40. Kernighan, Brian W., Ritchie, Dennis M. The С Programming Language (Second Edition). Prentice-Hall; 1988

41. Kalev D. ANSI/ISO С++ Professional Programmer's Handbook. Macmillan Computer Publishing. 1999.

42. Burley J.C. GCC 3.2.3 G77 Manual. gcc.gnu.org/onlinedocs/gcc-3.2.3/g77/.

43. Menapace J., Kingdon J., MacKenzie D. The "stabs" debug format. 2000. www.sunsite.ualberta.ca/Documentation/Gnu/gdb-4.18/htmlchapter/.

44. Qt С++ GUI Application Development Toolkit, doc.trolltech.com.

45. Gale Т., Main I. And GTK team. GTK+ 2.0 Tutorial, www.gtk.org/tutorial/.

46. Eckel B. Thinking in Java, 2nd edition, Revision 12,2001

47. Корнеев В.Д. Параллельное программирование в MPI 2-е изд., Новосибирск, Издательство ИВМиМГ СО РАН, 2002

48. Srinivasan S., Advanced Perl Programming, O'Reilly & Associates, 1999, ISBN 1-56592-220-4