Динамический контроль корректности OpenMP-программ

2

Аннотация

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

Оглавление

• 1 Введение 3
• 1.1 Технология OpenMP 3
• 1.2 Ошибки, возникающие при использовании OpenMP 4
• 1.3 Отладка параллельных программ 8
• 1.4 Цель работы 9
• 2 Постановка задачи 10
• 3 Обзор существующих отладчиков 11
• 3.1 Сравнение отладчиков 12
• 3.2 Выводы 13
• 4 Динамический контроль корректности 14
• 4.1 Схема работы отладчика 14
• 4.2 Построение дерева контекстов 15
• 4.3 Обнаружение ошибок общей памяти 18
• 4.3.1 Представление критических областей 18
• 4.3.2 Описание алгоритма 20
• 4.4 Расширенное дерево контекстов 23
• 4.5 Обнаружение ошибок инициализации 24
• 5 Практическая реализация 27
• 5.1 Интерфейс отладчика 27
• 5.2 Объединение алгоритмов 28
• 5.3 Оптимизация отладчика 30
• 5.4 Результаты тестирования 31
• Литература 38

В OpenMP память подразделяется на 2 вида: общая память и локальная память.

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

Локальная память доступна только одной нити.

В 2004-2005 годах в University of Kassel(Германия) проводилось исследование, целью которого было выявление наиболее часто совершаемых ошибок, обусловленных некорректным использованием функций и директив OpenMP, и приводящих к неверному выполнению программы. Эксперимент проводился на студентах этого университета, которые должны были написать некоторую программу с использованием OpenMP версии 2.5 или более ранней. Большинство испытуемых ранее не имели опыта работы с OpenMP, что позволило выявить ошибки, допускаемые начинающими программистами. В результате были обнаружены следующие ошибки [3]:

1) Незащищенный доступ к общим переменным.

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

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

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

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

2) Использование механизма замков без директивы flush.

Этот пункт является ошибкой только для ранних версий OpenMP(до версии 2.5).

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

3) Чтение общих переменных без директивы flush.

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

4) Использование переменных как приватных, хотя таковыми они не являются.

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

5) Использование предложения ordered без конструкции ordered.

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

6) Переменная распараллеливаемого цикла объявлена как общая.

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

7) Отсутствие слова for в директиве parallel for

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

8) Изменение числа нитей в параллельной области программы.

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

9) Снятие замка нитью, которая его не устанавливала.

Замок может быть снят только нитью, установившей его.

10) Изменение переменной распараллеленного цикла внутри него.

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

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

Приведенный список ошибок не является полным и поэтому следует сказать еще о паре ошибок, которые могут возникнуть в OpenMP-программе:

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

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

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

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

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

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

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

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

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

Страницы: 1, 2, 3, 4