1 ВВЕДЕНИЕ
Данная работа посвящена проблеме
отладки параллельных программ,
создаваемых в рамках DVM-модели (Distributed Virtual
Machine, Distributed
Virtual
Memory),
разработанной в ИПМ им. М. В. Келдыша РАН. В
основу этой модели положена следующая
основная идея: параллельное выполнение
программы должно осуществляться в
соответствии с ее потенциальным
параллелизмом, явно описанным
пользователем с помощью специальных
указаний. Языки C-DVM и Fortran-DVM
являются расширениями стандартных языков Cи
и Fortran 77 в
соответствии с DVM-моделью. Параллельная
программа представляет собой обычную
последовательную программу, в которую
вставлены DVM-указания, определяющие ее
параллельное выполнение. С помощью таких
указаний программист должен задать
правила распределения
данных и вычислений между процессорами,
отметить те операторы программы,
выполнение которых может потребовать
доступа к удаленным данным, и т.п.
DVM-указания
прозрачны для стандартных компиляторов,
поэтому DVM-программа может быть
скомпилирована и выполнена как обычная
последовательная программа.
Специальные компиляторы переводят
программу на языке C-DVM или Fortran-DVM
в программу на стандартном языке (Си или Fortran
77), расширенную функциями библиотеки Lib-DVM (системы поддержки DVM-программ).
На распределенных системах эта программа
загружается на все процессоры, выделенные
для выполнения параллельной программы. Для
организации межпроцессорного
взаимодействия библиотека Lib-DVM
использует средства стандартных
коммуникационных библиотек (например, MPI
или PVM).
Подробное описание DVM-модели и языков C-DVM и
Fortran-DVM
можно найти в работах [1],
[2]
и [3].
Вычислительные программы для
последовательных ЭВМ традиционно
создавались на языках Фортран 77 и Си. Для
многопроцессорных ЭВМ с распределенной
памятью (IBM
SP2, Parsytec,
MBC-1000) и
сетей ЭВМ такие программы в настоящее
время, как правило, создаются на языках
Фортран 77 и Си, расширенных библиотеками
передачи сообщений (MPI[5],
PVM [6]).
Разработка таких параллельных программ
требует от прикладного программиста
гораздо больше усилий, чем разработка
последовательных программ, поскольку ему
требуется не только распределить данные и
вычисления между разными процессорами, но
и организовать взаимодействие процессоров
посредством обмена сообщениями.
Фактически, параллельная программа
представляет собой систему
взаимодействующих программ, каждая из
которых выполняется на своем процессоре.
Отладка таких программ еще более
осложняется их недетерминированным
поведением.
Для облегчения отладки
используются специальные параллельные
отладчики, которые позволяют
контролировать одновременное исполнение
нескольких процессов как на одной, так и на
разных машинах. Как правило, такие
отладчики предоставляют тот же набор
средств, что и последовательные отладчики:
приостановка программы в определенной
точке, просмотр и модификация значений
переменных, пошаговое исполнение и т.д.
Некоторые отладчики обеспечивают
накопление и автоматизированный анализ
трассировки обращений к функциям
коммуникационной библиотеки.
Существуют три других подхода,
которые избавляют программиста от
необходимости представлять свою программу
в виде системы процессов,
взаимодействующих посредством обмена
сообщениями.
Первый подход заключается в
автоматическом распараллеливании
программ, написанных на языке Фортран.
Для многопроцессорных ЭВМ с
общей памятью были созданы и успешно
используются распараллеливающие
компиляторы, которые позволяют
программисту сообщать некоторую
информацию о свойствах своей программы (например,
имеется ли в цикле зависимость по данным,
имеет ли процедура побочные эффекты, и т.п.),
которую не удается получить компилятору
при анализе программы.
Однако автоматическое
распараллеливание для распределенных
систем принципиально сложнее. В отличие от
многопроцессорных ЭВМ с общей памятью, на
которых распределять данные не требуется,
а распределение вычислений осуществляется,
как правило, посредством динамического
распределения между процессорами витков
каждого параллельного цикла (независимо от
распределения витков других циклов), на
системах с распределенной памятью
требуется произвести согласованное
распределение вычислений и данных.
Несогласованность распределения
вычислений и данных приведет, вероятнее
всего, к тому, что параллельная программа
будет выполняться гораздо медленнее
последовательной. Если, например, на
системе с общей памятью распараллелить
один цикл, занимающий 90 процентов времени
решения задачи, то можно рассчитывать на
почти десятикратное ускорение программы.
На системе с распределенной памятью
распараллеливание этого цикла без учета «интересов»
других циклов, скорее всего, вызовет не
ускорение, а замедление программы.
Для нахождения подходящего
варианта распределения данных и
вычислений требуется не только
осуществить тщательный анализ всей
программы, но и получить некоторую
дополнительную информацию, позволяющую
оценивать время выполнения отдельных ее
фрагментов (например, размеры динамических
массивов). Поэтому не удивительно, что
системы автоматического
распараллеливания для распределенных
систем не стали до сих пор инструментом
практического программирования.
Второй подход базируется на
использовании языков программирования с
параллелизмом по данным, самыми яркими
представителями которых являются HPF, Fortran D
и Vienna Fortran. При этом подходе на программиста
возлагается ответственность за
распределение данных между процессорами, а
представление программы в виде системы
процессов, взаимодействующих посредством
обмена сообщениями, осуществляет
компилятор автоматически. Однако, такого
перераспределения работы между
программистом и компилятором оказалось
недостаточно для создания эффективных
компиляторов и широкого внедрения этих
языков. Кроме того, при таком подходе
программист не имеет ясной модели
выполнения своей программы, что
существенно усложняет отладку ее
эффективности.
Третьим подходом является DVM-подход,
при котором пользователь должен точно
специфицировать не только распределение
данных, но и распределение вычислений, а
также может полностью управлять обменом
информации между процессорами. Такое
перераспределение работы между
программистом и компилятором позволило, с
одной стороны, значительно упростить
компилятор, а с другой стороны, обеспечить
высокую эффективность выполнения DVM-программ.
В результате, DVM-подход может
рассматриваться как реальная альтернатива
явному использованию коммуникационных
библиотек.
Анализ последних трех подходов,
базирующихся на использовании единой
программы с единым пространством имен и
единым адресном пространством, позволяет
утверждать, что с точки зрения отладки
программ они имеют много общего.
Во-первых, хотя параллельная
программа в момент выполнения
представляет собой систему
взаимодействующих процессов,
использование параллельных отладчиков,
созданных для отладки программ с передачей
сообщений, проблематично, поскольку эта
программа очень непохожа на исходную
программу. Программисту необходимо
предоставить средства отладки в терминах
исходной программы.
Во-вторых, задаваемая
программистом и используемая при
распараллеливании информация о свойствах
программы, которую невозможно извлечь на
стадии компиляции, может быть получена и
проверена при выполнении программы. Это
позволит автоматически выявлять целый ряд
ошибок, поиск которых традиционными
методами очень сложен.
В-третьих, способность одной и
той же программы выполняться и в
последовательном и в параллельном режиме,
позволяет использовать для ее отладки
метод автоматического сравнения
результатов выполнения в разных режимах,
что существенно упрощает поиск ошибок,
проявляющихся только при параллельном
выполнении программы.
Важным достоинством DVM-подхода
является то, что спецификации параллелизма
(DVM-указания) оформляются в виде
специальных комментариев и остаются «невидимыми»
для стандартных компиляторов.
Во-первых, это упрощает внедрение
новых параллельных языков, поскольку
программист знает, что его программа без
каких-либо изменений может выполняться в
последовательном режиме на любых ЭВМ.
Во-вторых, это позволило
предложить следующий метод поэтапной
отладки DVM-программ.
На первом этапе программа
отлаживается на рабочей станции как
последовательная программа, используя
обычные методы и средства отладки. На
втором этапе программа выполняется на той
же рабочей станции в специальном режиме
проверки DVM-указаний. На третьем этапе
программа может быть выполнена на
параллельной машине (или ее модели,
например MPI-машине в среде Windows95 или UNIX) в
специальном режиме, когда промежуточные
результаты параллельного выполнения
сравниваются с эталонными результатами (например,
результатами последовательного
выполнения).
Для осуществления двух последних
этапов в состав DVM-системы включен
специальный инструмент – динамический
отладчик.
Для уточнения функций
динамического отладчика проведем
классификацию возможных ошибок в DVM-программах.
Эти ошибки можно разбить на несколько
классов по степени их влияния на
работоспособность программы, по легкости
выявления и т.д. Мы ограничимся
рассмотрением только тех ошибок, которые
не проявляются при последовательном
выполнении DVM-программы.
В общем случае можно выделить
следующие четыре класса таких ошибок:
1.
Синтаксические ошибки в DVM-указаниях
(неправильная запись оператора, отсутствие
скобки и т.д.), а также нарушение
статической семантики.
2.
Неправильная
последовательность выполнения DVM-указаний
или неправильные параметры DVM-указаний.
3.
Неправильное выполнение
вычислений из-за некорректности DVM-указаний
и ошибок, не проявляющихся при
последовательном выполнении программы.
4.
Аварийное завершение
параллельного выполнения программы (авосты,
зацикливания, зависания) из-за ошибок, не
проявляющихся при последовательном
выполнении программы.
Синтаксические ошибки в
программе выявляются при компиляции.
Ошибки второго класса
обнаруживаются библиотекой Lib-DVM при
параллельном выполнении программы:
функции библиотеки проверяют корректность
порядка выполнения DVM-указаний и
передаваемых параметров.
Ошибки третьего класса
выявляются динамическим отладчиком:
·при
запуске DVM-программы на одном процессоре в
режиме динамического контроля;
·при
запуске DVM-программы на одном или
нескольких процессорах в режиме сравнения
результатов ее параллельного выполнения с
эталонными результатами, полученными при
ее последовательном выполнении.
Входящие в состав
динамического отладчика средства
накопления результатов параллельного
выполнения программы могут оказаться
полезными и для обнаружения ошибок
четвертого класса. Кроме того, для
обнаружения таких ошибок предназначен
механизм накопления системной трассировки
(трассировки вызовов функций системы
поддержки выполнения DVM-программ).
2
Методы проверки корректности DVM-программ
Для отладки
параллельной DVM-программы ее необходимо
скомпилировать в специальном отладочном
режиме, при котором компилятор вставляет в
программу обращения к функциям
динамического отладчика в следующих
точках:
·начало
последовательного или параллельного цикла;
·завершение
последовательного или параллельного цикла;
·начало
нового витка цикла;
·обращение
к переменной на чтение;
·перед
обращением к переменной на запись;
·после
обращения к переменной на запись.
Кроме того, обращения
к функциям динамического отладчика
производятся также и при выполнении многих
функций библиотеки Lib-DVM.
Для проверки
корректности DVM-программы используются
следующие два метода.
Первый метод – метод
динамического контроля DVM-указаний,
позволяет проверить корректность
распараллеливания программы с помощью DVM-указаний.
Он основан на анализе последовательности
вызовов функций Lib-DVM и обращений к
переменным во время выполнения программы в
режиме моделирования параллельных
вычислений на одном процессоре.
Второй метод – метод
сравнения результатов выполнения,
позволяет локализовать ошибки,
возникающие вследствие неправильного
преобразования компилятором
последовательного алгоритма в
параллельный (из-за неверной спецификации
параллелизма с помощью DVM-указаний), или
ошибки последовательного алгоритма,
проявляющейся только при его параллельном
выполнении. Путем сравнения двух
трассировок, накапливаемых во время
выполнения программы в последовательном и
параллельном режимах, можно определить
место в программе и момент, когда возникают
расхождения в результатах вычислений. При
этом, в отличие от первого метода, в
специальном режиме может быть
скомпилирована только часть программы.
Далее приводится
более подробное описание этих методов,
используемых алгоритмов и управляющих
параметров.
3
Метод динамического контроля DVM-указаний
Этот метод основан на
моделировании параллельного выполнения DVM-программы
во время ее последовательного выполнения
на одном процессоре. Это позволяет
накапливать и использовать любую
информацию, необходимую для контроля (при
реальном параллельном выполнении трудно
обеспечить оперативный доступ к
информации, накапливаемой на разных
процессорах).
Однако использование
моделирования параллельного выполнения
может существенно замедлить выполнение
программы и требует больших объемов
дополнительной памяти. Поэтому, этот метод
может применяться только для программы со
специально подобранными тестовыми данными.
Кроме того, предусмотрены средства
настройки алгоритмов отладчика,
позволяющие сократить объем требуемой
памяти или время выполнения.
3.1 Типы
выявляемых ошибок
Все переменные,
которые используются в DVM-программе при ее
параллельном выполнении, можно разбить на
следующие классы:
·Приватные
переменные. Каждая параллельная ветвь (группа
витков параллельного цикла, выполняющихся
на одном процессоре) имеет свою локальную
копию переменной и работает только с ней.
До входа в параллельную
конструкцию и после выхода из нее
переменная имеет неопределенное значение.
Использование таких переменных в каждом
витке цикла должно начинаться с их
инициализации.
·Неизменяемые
переменные. Модификация этих переменных
внутри параллельной конструкции является
ошибочной.
·Редукционные
переменные. Каждая параллельная ветвь
имеет свою локальную копию каждой такой
переменной. После завершения
параллельного цикла, в соответствии с
заданной редукционной операцией, система
поддержки DVM производит вычисление над
всеми частичными результатами,
накопленными на каждом процессоре в
локальных копиях переменной. Результат
рассылается на все процессоры и
записывается во все копии редукционной
переменной.
·Распределенный
массив. Элементы такого массива
отображаются на процессоры системы. Каждая
параллельная ветвь может читать и
модифицировать только элементы,
располагающиеся на текущем процессоре, а
также читать элементы теневых граней.
·Буфер
удаленного доступа. На каждом процессоре
буфер содержит некоторую секцию
распределенного массива, доступную только
на чтение.
Проверяя
корректность работы с переменными каждого
класса, динамический отладчик позволяет
обнаружить следующие ошибки:
·Необъявленная
зависимость параллельного цикла по данным.
·Чтение
неинициализированных переменных.
·Модификация
неизменяемых переменных.
·Использование
редукционных переменных до завершения
операции асинхронной редукции.
·Выход за
пределы распределенного массива.
·Необъявленный
доступ к нелокальным элементам
распределенного массива.
·Запись в
теневые грани распределенного массива.
·Чтение
теневых граней распределенного массива до
завершения операции их обновления.
Ниже описываются
алгоритмы контроля переменных разных
классов.
Контроль
инициализации переменных и элементов
массивов. Данный контроль
осуществляется для всех классов
переменных. Каждой переменной
соответствует флаг ее инициализации (массиву
соответствует массив флагов). Данный флаг
устанавливается при записи нового
значения в переменную или элемент массива.
При чтении переменной или элемента массива
проверяется состояние данного флага, и
если он не установлен, то диагностируется
ошибка использования
неинициализированных данных.
Контроль
приватных и неизменяемых переменных. Класс
обычной (не редукционной) размноженной
переменной определяется при первом
обращении к ней внутри параллельной
конструкции. Если это обращение на чтение,
то переменная считается неизменяемой. Если
же первое обращение произошло для записи в
переменную, то она считается приватной.
Флаг инициализации
приватной переменной устанавливается при
записи в нее нового значения и
сбрасывается при входе и при выходе из
параллельной конструкции. При чтении
переменной проверяется установка данного
флага.
При использовании
неизменяемых переменных проверяется тип
обращения к ним. При попытке модификации
таких переменных диагностируется ошибка.
Контроль
редукционных переменных. Редукционные
переменные регистрируются динамическим
отладчиком при входе в параллельный цикл.
Каждой редукционной переменной
соответствует флаг, который определяет
текущее состояние этой переменной.
Состояние переменной контролируется при
каждом обращении к ней. Если переменная
используется после выхода из параллельной
конструкции, но до запуска и завершения
асинхронной редукции, или после запуска
асинхронной редукции, но до ее завершения,
то диагностируется ошибка.
Контроль
доступа к элементам распределенного
массива. Каждому
элементу распределенного массива
соответствует структура, описывающая тип
использования данного элемента (чтение или
запись) и номер последнего витка, где
данное использование осуществлялось.
При вхождении в
параллельный цикл каждый элемент получает
статус, который соответствует отсутствию
обращений к этому элементу. Когда элемент
используется внутри параллельного цикла,
для него запоминается номер витка и тип
доступа. Если один и тот же элемент
модифицируется в одном витке и
используется в другом, то диагностируется
ошибка зависимости цикла по данным.
При обращении к
элементу распределенного массива внутри
параллельного цикла, для данного массива
вычисляется его локальная часть,
принадлежащая выполняющемуся витку.
Если локальная часть
не содержит используемого элемента, то
диагностируется либо ошибка обращения к
нелокальному элементу массива, либо ошибка
выхода за пределы массива. Если элемент
принадлежит теневым граням, то проверяется
наличие и завершенность операции
обновления теневых граней для данного
массива.
Всем теневым граням
распределенного массива соответствуют
следующие три состояния: обновление не
выполнялось, обновление началось и
обновление завершено. Программа может
обращаться к теневым элементам только на
чтение и только после завершения их
обновления.
Состояние «обновление не выполнялось»
устанавливается при модификации любого
экспортируемого элемента распределенного
массива. Это обеспечивает контроль
некорректного доступа к теневым элементам
до начала выполнения следующей операции
обновления теневых граней.
Контроль
использования буфера удаленного доступа.
Буфер удаленного доступа используется
для доступа к нелокальным элементам
распределенного массива на каждом
процессоре. Для буфера удаленного доступа
производятся аналогичные проверки, что и
для распределенных массивов за следующими
исключениями:
·Проверка
необъявленной зависимости по данным
осуществляется для распределенного
массива, для которого был создан буфер
распределенного доступа.
·Проверка
на инициализацию элементов производится
как для буфера удаленного доступа (инициализация
– копирование элементов из массива в буфер),
так и для распределенного массива, доступ к
которому данный буфер обеспечивает.
·Элементы
буфера удаленного доступа доступны только
на чтение.
3.2
Ограничения метода динамического
контроля
При включении
динамического контроля, каждое обращение к
переменной и на чтение и на запись проходит
целый ряд проверок. Кроме того, каждой
переменной пользовательской программы
соответствует структура динамического
отладчика, описывающая ее состояние. Это
заметно увеличивает время выполнения
программы и объем требуемой памяти.
Поэтому запуск в режиме динамического
контроля необходимо осуществлять на
специально подобранных данных, чтобы
избежать бесконечно долгого выполнения
программы или отказа из-за нехватки памяти.
Динамический
контроль не гарантирует стопроцентное
выявление всех возможных ошибок, связанных
с неверной спецификацией параллелизма. Так,
если часть процедур, используемых
программой, представлено в виде библиотеки
заранее откомпилированных модулей, то их
корректность невозможно проверить, т.к.
компиляторы C-DVM или Fortran-DVM не могут
вставить в них вызовы отладочных функций.
Аналогичная ситуация возникает при
использовании в параллельных программах
процедур, написанных на обычных
последовательных языках (включая
ассемблер). В обоих этих случаях имеется
еще одна проблема – невозможно определить,
используются ли параметры процедуры для
чтения или для модификации. Поэтому
динамический контроль может не
обнаруживать некоторые ошибки или,
наоборот, выдавать сообщения о
несуществующих ошибках. Для
предотвращения выдачи таких сообщений
имеется возможность при запуске программы
отключать те или иные виды проверок
динамического контроля.
Еще одно ограничение
динамического контроля связано с
проверкой корректности редукции. Данный
метод можно использовать только для
проверки корректности доступа к
редукционным переменным, но с его помощью
нельзя выявить некорректность задания
редукционной операции. Например, для
переменной может быть специфицирована
редукционная операция нахождения
максимума, а на самом деле в программе
вычисляется минимум. При выполнении такой
программы на разном числе процессоров
будут получаться разные результаты. Для
выявления такой некорректности необходимо
воспользоваться другим методом – методом
сравнения результатов выполнения
программы.
4
Метод сравнения результатов
выполнения
Динамический
контроль предназначен, в основном, для
проверки корректности DVM-указаний. Однако в
исходной (последовательной) программе
могут быть ошибки, которые не проявляются
при ее последовательном выполнении, но
приводят к неверному параллельному
выполнению. Кроме того, как было сказано
выше, метод динамического контроля имеет и
другие ограничения.
В данной главе
описывается другой метод проверки
корректности DVM-программ, который хотя и
уступает по точности локализации и
диагностики ошибок методу динамического
контроля, но зато свободен от его
ограничений. Этот метод основывается на
получении трассировки вычислений при
разных условиях выполнения программы и
сравнении полученных результатов. При
использовании этого метода программа
может выполняться в двух различных режимах
– режиме накопления трассировки и режиме
сравнения результатов вычислений.
При выполнении
программы в первом режиме ее результаты
вычислений (значения переменных)
накапливаются и записываются в файл. Если
выполнение программы производится на
нескольких процессорах, то для каждого
процессора создается свой файл
трассировки. Воспользовавшись таким
режимом при выполнении DVM-программы на
одном процессоре (последовательном или
параллельном), пользователь может получить
эталонную трассировку, которая будет затем
использоваться при запусках этой
программы на различных конфигурациях
многопроцессорной системы в режиме
сравнения результатов вычислений.
При запуске
программы во втором режиме ее результаты
вычислений сравниваются с теми, которые
содержатся в эталонной трассировке. При
этом учитывается, что значения некоторых
переменных (например, редукционных
переменных внутри параллельного цикла) при
разных условиях выполнения программы
могут различаться.
4.1
Накопление трассировки
В режиме накопления
трассировки в трассировочный файл
помещается следующие виды записей:
·Значение
переменной, используемой для чтения.
·Значение
модифицируемой переменной.
·Результат
вычисления редукции.
·Информация
о начале параллельного или
последовательного цикла.
·Информация
о начале нового витка цикла.
·Информация
о завершении параллельного или
последовательного цикла.
Каждая запись в файле
трассировки содержит ссылку на файл и
строку исходной программы.
Так как размер
трассировочного файла может достигать
очень больших размеров, то пользователю
предоставляются следующие возможности
сокращения объема трассировки.
Во-первых, программу
можно разбить на фрагменты и при ее
компиляции для каждого фрагмента указать,
в каких точках должны быть вставлены
обращения к отладчику
(обращения к любым переменным, модификация
любых переменных, обращения к
распределенным массивам, модификация
распределенных массивов).
Во-вторых, при
запуске программы с помощью специального
параметра можно задать один из следующих
возможных уровней подробности трассировки:
·Отсутствие
трассировки.
·Трассировка
только начала и конца цикла и начала
каждого его витка.
·Предыдущий
уровень, плюс трассировка модификаций
переменных и результатов вычисления
редукции.
·Полная
трассировка (включает трассировку всех
событий).
В-третьих, при
запуске программы с помощью специального
файла (файла описания циклов) можно задать
уровень подробности трассировки для
каждого ее цикла. Там же для каждого цикла
можно ограничить множество
трассируемых витков.
4.2
Сравнение с эталонной трассировкой
В режиме сравнения,
файл с эталонной трассировкой считывается
в память перед началом выполнения
программы. Затем, в ходе выполнения
программы, ее результаты вычислений
сравниваются с соответствующими записями
эталонной трассировки. При этом программа
в режиме сравнения может быть запущена как
на нескольких процессорах, так и на одном с
различными режимами вычисления редукции.
При сравнении
результатов вычислений учитываются
следующие особенности:
·Значения
редукционных переменных могут различаться
при параллельном и последовательном
выполнении цикла. Поэтому, в
трассировочном файле записи,
соответствующие обращениям к редукционным
переменным, помечаются специальным
образом и значения этих переменных внутри
параллельных циклов не контролируются.
Кроме того, при вычислении редукционного
максимума или минимума количество
срабатываний операторов обновления
редукционных переменных могут также
различаться при последовательном и
параллельном выполнении цикла. Данные
ситуации распознаются благодаря тому, что
помечаются не только редукционные
переменные, но и все операторы
присваивания.
·При
параллельном выполнении цикла порядок его
витков может изменяться, а часть витков
может вообще не выполняться на данном
процессоре. Для поиска витков в эталонной
трассировке используется специальная
таблица, которая формируется при чтении
трассировки из файла.
·При
параллельном выполнении последовательных
участков программы на каждом процессоре
пропускаются те операторы, которые
модифицируют нелокальные элементы
распределенного массива. Для
распознавания таких участков, в
трассировку помещаются специальные записи.
·Изменение
алгоритма вычисления редукционных
операций (например, изменение порядка
суммирования) приводит к некоторому
отличию результатов выполнения для
вещественных чисел. Поэтому сравнение
вещественных чисел должно производиться с
определенной точностью, заданной при
запуске в режиме накопления трассировки.
4.3
Контроль редукционных операций
Как было сказано выше,
значения редукционных переменных внутри
параллельных циклов не контролируются. При
выходе из цикла (в случае асинхронной
редукции – при завершении ожидания
выполнения редукции) производится
сравнение результата вычисления редукции
с тем, который содержится в эталонной
трассировке.
Для контроля
правильности спецификации редукционной
операции, вычисление редукционной
операции производится двумя различными
способами. Первый способ – это стандартный
метод вычисления редукции. Сначала на
каждом процессоре выполняются
отображенные на него витки параллельного
цикла, в которых в соответствии с заданным
программистом алгоритмом будет вычислен
частичный результат редукции. Конечный
результат редукционной операции
вычисляется библиотекой Lib-DVM путем
объединения всех частичных результатов в
соответствии с описанной программистом
редукционной операцией. Если программа
выполняется последовательно (или
параллельно, но на одном процессоре), то
редукционная операция целиком будет
вычислена в соответствии с заданным
программистом алгоритмом.
Второй способ
представляет собой эмуляцию выполнения
каждого витка параллельного цикла на своем
процессоре, осуществляемую следующим
образом. Перед началом выполнения
очередного витка значение редукционной
переменной сохраняется, а редукционной
переменной присваивается ее начальное
значение, т.е. то значение, которое она
имела перед началом выполнения цикла.
После выполнения витка над сохраненным
значением редукционной переменной и
полученным в редукционной переменной
частичным результатом выполняется
операция редукции в соответствии с
описанной программистом редукционной
операцией.
Для проверки
правильности задания редукционной
операции производится сравнение
результатов выполнения программы с
использованием двух описанных выше
способов вычисления редукции. Если
редукционная операция в программе задана
правильно, то при обоих способах
вычисления редукции получится одинаковый
результат. При неверном задании операции
редукции пользователь получит диагностику
о расхождении результатов выполнения
редукции.
5
Заключение
Вычислительные программы для
многопроцессорных ЭВМ с распределенной
памятью и сетей ЭВМ в настоящее время, как
правило, создаются на языках Фортран 77 и Си,
расширенных библиотеками передачи
сообщений (PVM, MPI). Разработка таких
параллельных программ требует от
прикладного программиста гораздо больше
усилий, чем разработка последовательных
программ, поскольку ему требуется не
только распределить данные и вычисления
между разными процессорами, но и
организовать взаимодействие процессоров
посредством обмена сообщениями.
Существуют другие подходы,
базирующиеся на автоматизированном
распараллеливании программ, которые
избавляют программиста от необходимости
представлять свою программу в виде системы
процессов, взаимодействующих посредством
обмена сообщениями.
Анализ этих подходов позволяет
утверждать, что с точки зрения отладки
программ они имеют много общего. Во-первых,
хотя параллельная программа в момент
выполнения и представляет собой систему
взаимодействующих процессов, однако
использование параллельных отладчиков,
созданных для отладки программ с передачей
сообщений, проблематично, поскольку эта
программа очень непохожа на исходную.
Программисту необходимо предоставить
средства отладки в терминах исходной
программы.
Во-вторых, задаваемая
программистом и используемая при
распараллеливании информация о свойствах
программы, которую невозможно извлечь на
стадии компиляции, может быть получена и
проверена при выполнении программы. Это
позволит автоматически выявлять целый ряд
ошибок, поиск которых традиционными
методами очень сложен.
В-третьих, способность одной и
той же программы выполняться и в
последовательном и в параллельном режиме,
позволяет использовать для ее отладки
метод автоматического сравнения
результатов выполнения в разных режимах,
что существенно упрощает поиск ошибок,
проявляющихся только при параллельном
выполнении программы.
Учитывая эти особенности
выполнения параллельных программ для
систем автоматизации распараллеливания, в
рамках DVM-системы предложен следующий
метод поэтапной отладки DVM-программ.
На первом этапе программа
отлаживается на рабочей станции как
последовательная программа, используя
обычные методы и средства отладки. На
втором этапе программа выполняется на той
же рабочей станции в специальном режиме
проверки DVM-указаний. На третьем этапе
программа может быть выполнена на
параллельной машине (или ее модели,
например MPI-машине в среде Windows95 или UNIX) в
специальном режиме, когда промежуточные
результаты параллельного выполнения
сравниваются с эталонными результатами (например,
результатами последовательного
выполнения).
Разработанный для DVM-системы
динамический отладчик осуществляет
последние два этапа отладки.
Динамический отладчик
использовался для проверки целого ряда
тестовых программ, а также для отладки
нескольких реальных приложений.
Опыт использования отладчика
показал, что его применение позволяет
выявить достаточно большой спектр часто
допускаемых ошибок и значительно ускоряет
процесс отладки программ.
В заключение, необходимо
подчеркнуть, что описанные методы отладки
DVM-программ и принципы построения
соответствующих инструментальных средств
могут быть использованы не только в
рамках DVM-подхода, но и применительно к
другим языкам с параллелизмом данных (таких,
как HPF2) и системам автоматического
распараллеливания программ для
распределенных систем.
список литературы
1.
Konovalov
N.A., Krukov V.A., Mihailov S.N. and Pogrebtsov A.A. Fortran-DVM language for
portable parallel programs development // Proceedings of Software For
Multiprocessors & Supercomputers: Theory, Practice, Experience (SMS-TPE
94),Inst. for System Programming RAS, Moscow, Sept. 1994.
2.
Коновалов Н.А., Крюков В.А.,
Михайлов С.Н., Погребцов А.А. FORTRAN
DVM – язык для разработки мобильных
параллельных программ // Программирование.–
1995.– № 1.– С. 49-54.
3.
Коновалов Н.А., Крюков В.А.,
Сазанов Ю.Л. C-DVM – язык разработки
мобильных параллельных программ //
Программирование.– 1999.– № 1.– С. 54-65.
4.
Abramson
D.A., Watson G. Relative Debugging for Parallel Systems // Proceedings of PCW
97, Caberra,
Australia,
Sept.
25-26, 1997.
5.
Walker
D.W. The design of a standard message-passing interface for distributed memory
concurrent computers // Parallel Computing. - 1994 - Vol. 20(4), pp. 657-673.
6.
Geist
A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderam V. PVM 3 User’s
Guide and Reference Manual // Technical
report, Oak Ridge National Laboratory ORNL/TM-12187 - 1993.
