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

Аннотация
Важным этапом процесса создания любого программного продукта является его отладка. При чем данный этап по количеству затраченных на него средств зачастую сопоставим со всеми остальными стадиями разработки программного продукта. Особенно сильно возрастает трудоемкость отладки в случае, если программа была написана с использованием параллельных вычислений. Данная работа посвящена автоматическому нахождению наиболее распространенных ошибок, возникающих при использовании OpenMP конструкций в Fortran-программах. В ходе работы были разработаны и реализованы алгоритмы нахождения таких ошибок, а также проведено сравнение полученного инструмента с существующими аналогами.
Оглавление
1 Введение
1.1 Технология OpenMP
1.2 Ошибки, возникающие при использовании OpenMP
1.3 Отладка параллельных программ
1.4 Цель работы
2 Постановка задачи
3 Обзор существующих отладчиков
3.1 Сравнение отладчиков
3.2 Выводы
4 Динамический контроль корректности
4.1 Схема работы отладчика
4.2 Построение дерева контекстов
4.3 Обнаружение ошибок общей памяти
4.3.1 Представление критических областей
4.3.2 Описание алгоритма
4.4 Расширенное дерево контекстов
4.5 Обнаружение ошибок инициализации
5 Практическая реализация
5.1 Интерфейс отладчика
5.2 Объединение алгоритмов
5.3 Оптимизация отладчика
5.4 Результаты тестирования
Литература
Введение
Технология OpenMP
Стандарт OpenMP[1] создавался для упрощения разработки параллельных программ для вычислительных систем с общей памятью, а так же для распараллеливания уже существующих последовательных программ. Стандартом определены специальные комментарии (команды препроцессору для C/C++) – директивы компилятору, непосредственно управляющие параллелизмом программы, вспомогательные функции, позволяющие создавать алгоритмы, ориентированные на параллельное выполнение, и переменные окружения, управляющие процессом выполнения параллельных областей.
Программа, использующая директивы OpenMP, состоит из последовательных и параллельных участков. В начале ее выполнения создается одна нить, которая существует на протяжении всей программы. Когда какая-либо нить доходит до параллельного участка, то порождаются дополнительные нити, выполняющие вместе с ней этот участок. Группой нитей называется множество нитей, созданных при входе в данную параллельную область, включая породившую их нить, называемую главной. Нить, достигшая конца параллельной области, дожидается всю группу. Когда все нити одной группы дойдут до конца параллельного участка, все нити кроме главной освобождаются, а главная нить продолжает выполнение программы. На рисунке 1 показан пример создания и освобождения нитей в параллельных областях в случае наличия вложенных параллельных участков.
Рисунок 1: Пример выполнения параллельного участка
В OpenMP память подразделяется на 2 вида: общая память и локальная память.
Общая память доступна нескольким нитям одновременно. Однако, для работы с ней необходимо использовать синхронизирующие конструкции, которые позволяют избежать недетерминизма.
Локальная память доступна только одной нити.
Ошибки, возникающие при использовании OpenMP--PAGE_BREAK--
В 2004-2005 годах в University of Kassel(Германия) проводилось исследование, целью которого было выявление наиболее часто совершаемых ошибок, обусловленных некорректным использованием функций и директив OpenMP, и приводящих к неверному выполнению программы. Эксперимент проводился на студентах этого университета, которые должны были написать некоторую программу с использованием OpenMP версии 2.5 или более ранней. Большинство испытуемых ранее не имели опыта работы с OpenMP, что позволило выявить ошибки, допускаемые начинающими программистами. В результате были обнаружены следующие ошибки [3]:
Незащищенный доступ к общим переменным.
Данная ошибка возникает, когда несколько нитей работают с общей памятью без какой-либо синхронизации. В этом случае возможны следующие ситуации:
— все нити только читают переменную, тогда ошибки нет, т.к. значение переменной в любой момент времени остается неизменным.
— все нити только пишут в переменную. Поскольку они это делают одновременно, то нельзя определить, какое значение получит переменная после выполнения всех операций записи. И значение данной переменной будет при каждом запуске программы различным.
— часть нитей читают переменную, а часть пишут в нее. Здесь помимо эффекта предыдущего случая, наблюдается аналогичная неопределенность. Когда какая-либо нить пытается прочитать значение переменной, то неизвестно, какое именно значение будет получено.
Использование механизма замков без директивы flush.
Этот пункт является ошибкой только для ранних версий OpenMP(до версии 2.5).
При работе с общими переменными предполагается, что каждая нить работает с копией этой переменной, расположенной в кэше соответствующего процессора. Директива flush обновляет во всех нитях значения общих переменных, т.е. все нити будут видеть последние изменения. Поэтому, если использовать замки без директивы flush, то возможна ситуация, когда одна нить замок поставит, а другая не увидит никаких изменений, и будет считать, что ресурс свободен, и его можно захватить. В результате будет некорректная ситуация, когда сразу несколько нитей установили один и тот же замок. Начиная с версий OpenMP 2.5, директива flush входит в состав функций для работы с замками.
Чтение общих переменных без директивы flush.
Ситуация аналогичная предыдущему случаю. Если не использовать директиву flush перед чтением переменной, то нить может не получить последнее обновленное значение переменной. Вообще, в последних версиях OpenMP flush неявно включена во многие директивы, в особенности в синхронизационные, что позволяет избежать во многих случаях данной ошибки.
Использование переменных как приватных, хотя таковыми они не являются.
Эта ошибка вызвана тем, что программист забыл указать, что переменная является приватной. Во время выполнения программы, данную ошибку невозможно отличить от ошибки, описанной в первом пункте.
Использование предложения ordered без конструкции ordered.
Предполагается, что если в директиве распараллеливания цикла указано условие ordered, то внутри этого цикла должна располагаться область, помеченная как ordered. Это означает, что указанная область должна быть выполнена в том же порядке (по итерациям цикла), что и в последовательной программе. Отсутствие такой области в теле цикла, при наличии условия ordered считается ошибкой.
Переменная распараллеливаемого цикла объявлена как общая.
Такая переменная не может быть общей, т.к. у каждой нити она должна принимать свое значение. Многие компиляторы просто игнорируют указания сделать общей управляющую переменную цикла.
Отсутствие слова for в директиве parallel for
Итогом этой ошибки будет не разделение цикла между нитями, а каждая нить будет выполнять его целиком, что может привести к ошибке общей переменной.
Изменение числа нитей в параллельной области программы.
В OpenMP можно изменять число нитей, на которые программа будет поделена, только в последовательном участке программы.
Снятие замка нитью, которая его не устанавливала.
Замок может быть снят только нитью, установившей его.
Изменение переменной распараллеленного цикла внутри него.
Изменение управляющей переменной может привести к непредсказуемым результатам, т.к. будет нарушено распределение итераций цикла между нитями.
Из перечисленных ошибок наиболее частыми и трудно отслеживаемыми являются ошибки 1 и 4. Но поскольку отличить их друг от друга во время выполнения программы в большинстве случаев невозможно, то следует их объединить в одну группу. Назовем ее ошибками общей переменной.
Приведенный список ошибок не является полным и поэтому следует сказать еще о паре ошибок, которые могут возникнуть в OpenMP-программе:
Ошибка инициализации. Суть этой ошибки заключается в том, что в программе может возникнуть ситуация, когда происходит чтение переменной, которой еще не присвоили начальное значение. Технология OpenMP только увеличивает число возможных причин этой ошибки. Дело в том, что приватные переменные могут быть определены по-разному. Обычная приватная переменная (private) при входе в область, где она, таким образом, определена, не имеет начального значения. Однако, если сделать ее firstprivate, то кроме того, что она становится приватной, так ей еще будет присвоено значение, которое переменная имела до данной области. В OpenMP существуют разные параметры директив, которые аналогичным образом определяют передачу значений от исходных приватным переменным и от приватных исходным переменным. Поэтому, если программист неправильно задал тип приватной переменной, то, скорее всего, проявится именно эта ошибка.
Ошибка взаимной блокировки (deadlock). Это классическая ошибка, которая возникает, когда несколько нитей сначала захватывают в собственное пользование некоторые ресурсы, а затем пытаются захватить ресурсы, захваченные другими нитями. В результате все нити блокируются и программа виснет. Простейшим примером взаимной блокировки в OpenMP является случай, когда в одной критической секции находится другая, но с таким же именем. В этом случае нить, когда дойдет до второй критической секции, заблокирует сама себя. Этот вид ошибок искать не очень сложно, т.к. найти место зависания программы обычно не составляет особого труда.
Отладка параллельных программ
Процесс отладки параллельных программ можно условно поделить на традиционную и автоматическую.
В традиционном подходе отлаживаемая программа запускается под управлением отладчика, который в любой момент может приостановить выполнение программы и выдать ее текущее состояние. Таким образом, пользователь может просматривать содержимое переменных и текущее положение в исходном коде, выполняя программу по шагам или расставляя контрольные точки. И на основании полученной информации, пользователь может определить причину некорректной работы программы. Следует заметить, что обычно при таком подходе параллельная работа моделируется программно, так как при достижении контрольной точки любой нитью все остальные нити так же должны остановиться, причем они могут находиться в это время в любом месте программы. Таким образом, при нескольких запусках, когда одна нить будет доходить до контрольной точки, то параллельные ей нити могут останавливаться каждый раз в разных местах, а следовательно значения переменных тоже будут разными, что в значительной степени увеличивает сложность обнаружения ошибок.
Одним из видов автоматической отладки является динамический контроль корректности. Автоматическая отладка позволяет только определить корректность самой программы, а не правильность работы реализованного в ней алгоритма. Т.е. автоматически будут найдены участки кода, которые создают ситуации несоответствующие стандарту языка или используемой технологии. Работа динамического контроля корректности заключается в слежении за состоянием отлаживаемой программы во время ее выполнения и обнаружении некорректных ситуаций.
Цель работы
Цель дипломной работы – разработать и реализовать алгоритм динамического контроля корректности использования директив OpenMP в программах, написанных на языке Fortran. И минимизировать количество потребляемых ресурсов при работе отладчика.
Постановка задачи
Задача инструмента, проводящего динамический контроль корректности OpenMP программы, состоит в том, чтобы находить в отлаживаемой программе некорректное использование директив, которое может привести к неправильному результату ее работы. Тем самым такой инструмент должен упростить и ускорить весь процесс отладки, благодаря нахождению самых распространенных и трудно обнаруживаемых ошибок. Из перечисленного во введении списка ошибок таковыми являются два вида: ошибки общей памяти и ошибки инициализации.
Ошибки общей памяти возникают, когда несколько нитей одновременно и независимо друг от друга работают с одной и той же областью памяти, причем хотя бы одна из нитей модифицирует содержимое этой области.
Ошибки инициализации возникают при чтении переменной, которой не присвоено никакое начальное значение. Если проблема обусловлена использованием директив OpenMP, то трудоемкость ее нахождения традиционным методом отладки сравнима с нахождением ошибки общей памяти. Кроме того, данный вид ошибки может не проявляться на одной машине, но приводить к неправильным результатам работы программы на других, в зависимости от использованных компиляторов и библиотек OpenMP.
Таким образом, требуется разработать и реализовать алгоритмы нахождения ошибок общей памяти и ошибок инициализации в OpenMP программах, написанных на языке Fortran 77.
Обзор существующих отладчиков
На данный момент существуют несколько коммерческих инструментов, осуществляющих динамический контроль корректности OpenMP программы. Рассмотрим отладчики Intel Thread Checker[5] и Sun Thread Analyzer[4]. Оба инструмента способны находить ошибки общей памяти и взаимной блокировки в программах, использующих не только OpenMP, но и другие разновидности параллелизма с общей памятью, например, нити POSIX.    продолжение
--PAGE_BREAK--
Intel Thread Checker имеет два режима работы: зависимый от числа нитей и независимый.
Для работы в первом отлаживаемую программу можно не перекомпилировать, если она компилировалась с включением отладочной информации. В этом режиме запуск программы должен осуществляться под управлением отладчика. Для обнаружения ошибок общей памяти необходимо запускать программу на более чем одной нити, при этом в случае нахождения ошибки будет выдано только положение в исходном коде, а имя переменной, с которой связана эта ошибка, останется неизвестным.
Независимый от числа нитей режим работы включается добавлением при компиляции программы с помощью компилятора Intel опции –tcheck. При этом в отлаживаемой программе должны отсутствовать вызовы функций работы с числом нитей, таких как omp_set_num_threads(), omp_get_num_threads(), omp_get_max_threads(), omp_get_thread_num(), и omp_get_num_procs(). В этом режиме программа должна быть запущена на одной нити. В процессе работы параллелизм будет смоделирован и, не смотря на то, что реально при работе программы ошибки не произошли, они будут найдены, как потенциальные. Так же этот режим позволяет получить более подробную информацию об ошибке.
Sun Thread Analyzer требует, чтобы программа была скомпилирована с ключом -xinstrument=datarace. Так же должна быть включена отладочная информация для того, чтобы отладчик мог выдать диагностику с привязкой к исходному коду. Для обнаружения ошибок, запуск программы должен быть произведен на нескольких нитях.
Сравнение отладчиков
Сравнение приведенных отладчиков было проведено в Center for Computing and Communication RWTH Aachen University в Германии[2]. Intel Thread Checker и Sun Thread Analyzer запускались на нескольких программах с разными параметрами, для определения достоинств и недостатков этих инструментов. Наибольший интерес представляют полученные результаты замеров производительности отлаживаемых программ под управлением данных инструментов и без них, а так же количество потребляемой памяти. Отладчики тестировались на 3 примерах:
Jacobi. Приближенное решение двумерного уравнения Пуассона методом Якоби.
SMXV. Умножение матрицы на вектор в случае, когда в матрице имеется большое количество нулевых элементов.
AIC. Вычисление интеграла адаптивным методом.
В Таблице 1 приведены параметры производительности и потребляемой памяти (в мегабайтах) при работе программы. При этом инструменты тестировались на разных машинах с использованием разных компиляторов:
Intel – запуск программы, скомпилированной компилятором Intel, без отладчика на 2 нитях.
Intel Thread Checker – запуск программы на 2 нитях под управлением этого инструмента в зависимом от числа нитей режиме, т.к. алгоритмы SMXV и AIC используют функции для работы с числом нитей.
Sun – выполнение программы на 2 нитях без режима отладки, с использованием компилятора фирмы Sun.
Sun Thread Analyzer – отладка программы на 2 нитях с помощью Sun Thread Analyzer.
Таблица 1: Характеристики выполнения программ


Jacobi
SMXV
AIC


MByte
MFLOP/s
MByte
MFLOP/s
MByte
время
Intel
5
621
40
929
4
5,0 сек
Intel Thread Checker
115
0,9
1832
3,5
30
9,5 сек
Sun
5
600
50
550
2
8,4 сек
Sun Thread Analyzer
125
1,1
2020
0,8
17
8,5 сек
Из приведенной таблицы видно, что замедление во время отладки программы может достигать сотен раз, в то время как потребление памяти так же увеличивается в десятки раз.
К тому же при проведении данного тестирования было замечено, что Intel Thread Checker работал на 4-х нитях с такой же производительностью, что и на 2-х.
Выводы
Рассмотренные инструменты отладки, а именно IntelThreadCheckerи SunThreadAnalyzer, с успехом могут быть использованы для отладки небольших программ. Однако, из-за значительного увеличения объема потребляемых ресурсов во время отладки они становятся не применимыми для задач, работающих с большими объемами данных и производящими длительные вычисления. Для таких приложений требуется подбирать специальные входные данные, чтобы минимизировать потребляемые ресурсы. В некоторых случаях такой метод может быть не применим, например, когда объем требуемой памяти не сильно зависит от входных данных, или если программа получает на вход данные непосредственно от другого приложения.
Динамический контроль корректности
Схема работы отладчика
В этой главе описана схема работы отладчика, реализующего динамический контроль корректности OpenMPпрограммы.
Изначально имеется исходный код Fortranпрограммы со вставленными директивами OpenMP. Отладчик скомпилирован в объектный файл, и имеет интерфейс в виде набора функций, которые должны быть вызваны в процессе работы отлаживаемой программы, при наступлении соответствующих событий, например, при обращении к памяти. При помощи специальной программы – инструментатора, в исходный код вставляются вызовы интерфейсных функций отладчика. Далее полученный код должен быть скомпилирован вместе с объектным файлом отладчика в выполняемую программу, которую можно запускать на вычислительной системе с общей памятью. В результате работы этой программы будет выдана информация об обнаруженных ошибках. На рисунке 2 представлена описанная схема.
Рисунок 2: Общая схема работы отладчика.
Следует отметить, что при данной схеме работы будут найдены ошибки только в тех участках кода, для которых в процессе выполнения программы были выполнены вызовы функций отладчика. Из этого следует, что для исследования всего кода на наличие ошибок необходимо соответствующим образом подобрать входные данные. Но в любом случае недостижимый код проверен не будет из-за того, что вставленные функции отладчика также будут недостижимы.
Благодаря такой схеме можно проверить на наличие ошибок не только всю программу целиком, но и отдельно некоторые ее участки. Это может быть полезно, если программа требует значительное количество ресурсов, и при этом ошибка локализована в некоторой ее части. Тогда можно вставить вызовы функций отладчика только в данный участок программы, а также в места, содержащие необходимую информацию для работы алгоритма, такие как начало программы, описание переменных, массивов и т.д.
Построение дерева контекстов
Поскольку во время выполнения существуют несколько параллельно работающих нитей, которые объединены в группы, соответствующие параллельным областям, которые могут быть вложенными, то для анализа текущего состояния программы удобно построить дерево, отображающее взаимосвязь нитей в данный момент. Теперь необходимо решить, что будет находиться в вершинах этого дерева.
В постановке задачи требуется находить два вида ошибок: общей памяти и инициализации, а, следовательно, основным объектом исследований являются переменные и массивы, а точнее обращение к памяти. Но, так как чтение и запись в память связано с переменными и массивами, то можно объединить данные об этих операциях и информацию о переменной в одну структуру, которую назовем VarInfo. И теперь такая структура становится основным объектом, с которым будет работать отладчик.
В этом разделе описывается идея алгоритмов, и поэтому в их описании лучше всего работать с обобщенными объектами. Это позволит упростить сами алгоритмы, оставив неизменной их основной принцип работы. Поэтому для общности можно считать, что массивы состоят из набора переменных, соответствующих каждому элементу массива, и имеющих имена, составленные из имени самого массива и индекса, соответствующего элемента. Таким образом, дальше речь пойдет только о работе с переменными.    продолжение
--PAGE_BREAK--
Определим некоторую структуру, которая будет содержать данные о текущем состоянии нити, и назовем ее контекстом (Context). Для каждой нити в каждый момент времени доступен некоторый набор переменных, к которым они могут обращаться, при этом у разных нитей эти наборы обычно разные, т.к. они могут обладать приватными переменными и находиться в разных частях программы. Пусть текущий контекст нити содержит структуры данных, описывающие каждую переменную, (VarInfo) к которой было обращение с момента существования этого контекста. Структура VarInfo может быть взята из текущего контекста нити по некоторому ключу, например, по адресу соответствующей переменной. Конкретные ключи будут приведены далее при описании алгоритмов обнаружения ошибок, так же как будет уточнено содержимое самой структуры Context.
Теперь для полноты описания состояния всей программы следует поместить в вершины приведенного выше дерева, описывающего связи между нитями, структуры описывающие состояния самих нитей, а именно структуры Context. Такое дерево назовем деревом контекстов.
Правила построения дерева контекстов выглядят следующим образом:
В начале выполнения программы существует только одна нить, а следовательно дерево контекстов должно состоять из одной корневой вершины, соответствующей данной нити.
При входе в параллельную область создается группа параллельных нитей, которая включает породившую остальные нити (главную нить). В этом случае в дереве контекстов к вершине, соответствующей главной нити до этой параллельной области, добавляются вершины-потомки, соответствующие каждой нити из созданной группы.
При выходе из параллельной области группа параллельных нитей освобождается, за исключением главной нити, которая продолжает работу. В этом случае в дереве удаляются все вершины, соответствующие каждой нити из удаляемой группы, и их родительская вершина становится текущей для главной нити.
При вызове проинструментированной функции, т.е. функции содержащей обращения к отладчику, к вершине данной нити добавляется вершина-потомок, которая становится текущей для этой нити.
При выходе из функции текущая вершина нити удаляется, и текущей становится ее родительская вершина.
На рисунке 3 показан пример дерева контекстов. В вершинах этого дерева указан уникальный номер нитей, который в отличие от номеров OpenMP у любых двух нитей будет различным.
Рисунок 3: Пример дерева контекстов
Построенное дерево будет использоваться при дальнейшем описании алгоритмов, поэтому для удобства описания определим некоторые понятия, которые могут встретиться. Контекст или структура Context соответствует вершине дерева. Текущим контекстом для данной нити называется листовая вершина дерева, которая соответствует этой нити. Для каждой нити существует только один текущий контекст. Родительской вершиной называется вершина, к которой присоединена данная, и расположенная непосредственно над данной вершиной.
Обнаружение ошибок общей памяти
Ошибки общей памяти возникают, когда несколько нитей одновременно и независимо работают с одной областью памяти, причем хотя бы одна нить производит запись в эту область. Под независимостью в терминах OpenMP понимается отсутствие каких-либо конструкций синхронизации нитей, позволяющее в каждый момент времени обращаться к памяти только одной из них.
В OpenMP имеются следующие конструкции синхронизации:
Критические секции.
Атомарные операторы. Данную конструкцию можно заменить на критическую секцию с уникальным именем.
Барьерная синхронизация.
Последовательное выполнение блока в цикле (ordered).
Механизм замков.
Представление критических областей
Под критической областью (секцией) понимается участок программы заключенный в некоторую OpenMP-конструкцию, которая не допускает выполнение данного кода одновременно несколькими нитями. Причем данные области могут быть как статическими (critical, ordered, atomic), так и динамическими (механизм замков).
Для удобства работы будем считать, что границы областей определяются динамически, т.е. начало области определяется при входе в нее, а конец – при выходе.
При определении критических секций (critical) может быть указано некоторое имя. В этом случае критические области с разными именами могут выполняться параллельно, а с одинаковыми именами будут обозначать одну и ту же критическую область. Стандарт OpenMP позволяет определить критические области несколькими способами, но для обобщения достаточно определить имена критических областей для каждого случая:
каждая область, помеченная как ordered, получает уникальное имя
каждая директива atomic получает уникальное имя
имя критической секции (critical) указано в директиве
для каждой переменной замков заводится свое уникальное имя
Иногда возникают ситуации, когда критические области с разными именами являются вложенными. В этом случае их пересечение не может выполняться параллельно ни с одной из областей входящих в их число. Тогда для определения вхождения некоторого участка кода во множество критических областей, нужно ввести понятие идентификатора критической области.
Идентификатором критической области для данного кода называется множество имен критических областей, покрывающих этот участок. Далее определим сравнение этих идентификаторов. Два идентификатора критических областей равны, если пересечение их множеств имен критических областей не пусто, т.е. найдется такая критическая область, имя которой входит в оба идентификатора. И, соответственно идентификаторы не равны, если пересечение их множеств пусто.
Исходя из определения, следует, что любые два оператора могут выполняться параллельно, если их идентификаторы критической области не равны.
Описание алгоритма
Для обнаружения ошибки общей памяти необходимо для каждой общей переменной сохранять данные, об обращениях к ней. Пусть необходимо находить все операторы программы, которые конфликтуют между собой за доступ к переменной. Тогда для их определения достаточно поместить следующую информацию в структуру, описывающую общие переменные (VarInfo):
список обращений к переменной на запись (WriteList). Каждый элемент данного списка включает в себя следующую информацию:
номер нити, обратившейся к переменной
идентификатор критической секции
ссылка на описание места в исходном коде, из которого было произведено обращение к переменной
список обращений к переменной на чтение (ReadList). Список состоит из таких же элементов, что и WriteList.
имя переменной.
адрес переменной.
Структура VarInfo соответствующая некоторой общей переменной может быть получена из текущего контекста нити по адресу этой переменной, указанному в качестве ключа поиска.
Структура Context из дерева контекстов должна содержать следующие данные:
множество структур VarInfo для общих переменных. При создании контекста это множество должно быть пустым. Любая структура может быть выбрана из этого множества по адресу соответствующей ей переменной. Если при обращении по ключу такой структуры не обнаруживается, то она создается для переменной, отвечающей этому адресу.
идентификатор нити, для которой данный контекст является текущим. Этот идентификатор не меняется на протяжении всего времени существования данного контекста.
идентификатор критической области (critical_id).
список имен переменных, являющихся общими для данного контекста. На самом деле это не совсем список, а некоторый объект, который должен определять тип переменной для данного контекста, т.е. описана ли переменная как общая или нет. В OpenMP существует правило умолчания, которое определяет класс переменной, если последняя не была явно указана в директиве OpenMP. Поэтому, чтобы не включать имена всех общих переменных по умолчанию в данный список, можно заменить его таким объектом-определителем типа. Причем для корневого контекста все переменные считаются приватными, а для контекста, созданного при вызове функции, переменные, соответствующие параметрам этой функции, являются общими, а все остальные приватными.
Теперь можно описать сам алгоритм. Он состоит из следующих правил:
Дерево контекстов строится в соответствии с приведенными ранее правилами.
Пусть context – это контекст текущей нити; parent– контекст, являющийся родительским для context в дереве. При обращении к переменной определяется ее тип в контексте context. Если переменная общая, то в контексте parent по ее адресу выбирается структура VarInfo. И в зависимости от типа обращения к переменной в список WriteList или ReadList добавляется элемент, содержащий: номер нити (thread_id), хранящийся в context, текущий идентификатор критической области (critical_id), ссылку на положение в исходном коде этого обращения к переменной. Далее происходит исследование структуры VarInfo на предмет конфликта новой записи с добавленными ранее. При чтении переменной производится перебор всех записей из списка WriteList с номерами нитей, отличными от thread_id. Ошибка будет найдена, если найдется запись, в которой идентификатор критической области не равен critical_id. При записи в переменную производится перебор не только по списку WriteList, но и по списку ReadList. После окончания проверки на наличие ошибок, определяется тип переменной уже в контексте parent и, если она является общей, то данное правило повторяется снова, только в качестве context берется parent, а в качестве parent выступает родительский контекст нового context. При этом critical_id остается тем же самым. Таким образом, происходит подъем по дереву контекстов до тех пор, пока не найдется вершина, в которой данная переменная не является общей. На рисунке 4 приведена схема, соответствующая данному правилу.    продолжение
--PAGE_BREAK--
Рисунок 4: схема работы алгоритма при обращении к переменной
при входе в критическую область в текущем контексте поле critical_id модифицируется, добавлением имени текущей области.
при выходе из критической области в текущем контексте из поля critical_id исключается имя этой области.
при любой (явной или неявной) барьерной синхронизации требуется для каждой нити данной параллельной области сбросить информацию обо всех переменных в текущем контексте. Т.е. во всех вершинах, расположенных под вершиной, описывающей параллельную область, необходимо перебрать все структуры VarInfo и очисть их списки ReadList и WriteList. В качестве альтернативы, можно просто удалить все эти структуры VarInfo.
Идея алгоритма состоит в том, что параллельная область разделена синхронизирующими барьерами на последовательно расположенные участки. Предполагается, что операторы, расположенные внутри одного участка могут выполняться параллельно, а операторы, расположенные в разных участках всегда выполняются в разное время. Следовательно, можно хранить информацию только для текущего участка. Это работает, когда в программе существует только один уровень параллелизма, а в случае вложенного параллелизма на помощь приходит дерево контекстов, которое позволяет хранить данные о текущих участках всех параллельных областей.
Расширенное дерево контекстов
Расширенное дерево контекстов отличается от описанного ранее дерева контекстов тем, что при его построении используются дополнительные правила:
при входе нити в любую из областей SINGLE, DO или SECTIONS к вершине, отвечающей данной нити, добавляется вершина-потомок, и она становится текущей для нити.
при выходе из любой из областей SINGLE, DO или SECTIONS текущая вершина нити удаляется и текущей становится ее родительская вершина.
При создании любой вершины в структуру Context, содержащуюся в ней, добавляется информация, позволяющая определить тип переменной в данном контексте по ее имени. Причем, для директив SINGLE, DO или SECTIONS, если не указан тип переменной, и она не является THREADPRIVATE, то она считается типа SHARED. В контекстах, соответствующих вызовам функций, имеется информация о связи фактических и формальных параметров. Для фактических параметров функции, которым соответствуют переменные, а не выражения, тип определяется как SHARED.
Обнаружение ошибок инициализации
Ошибки инициализации возникают при чтении переменной, которой предварительно не присвоили какое-либо значение. Причиной может быть ошибка в реализации алгоритма или же некорректное использование директив OpenMP.
При использовании директив OpenMP переменная может потерять свое значение в следующих случаях:
Переменная объявлена как PRIVATE, тогда она теряет свое значение при входе в эту конструкцию и при выходе из нее.
FIRSTPRIVATE переменная теряет свое значение при выходе из параллельной конструкции.
LASTPRIVATE переменная не имеет начального значения.
THREADPRIVATE переменные могут иметь неопределенное значение, если они не были проинициализированы или не указаны в директиве COPYIN.
Для обнаружения ошибок этого вида достаточно отслеживать обращения к переменным и иметь построенное расширенное дерево контекстов.
Структура VarInfo для работы описываемого алгоритма должна содержать поле init, определяющее, присвоено ли переменной какое-либо значение, а так же имя этой переменной.
Структура Context должна содержать следующие данные:
множество структур VarInfo для переменных. При создании контекста это множество пусто. Любая структура может быть выбрана из этого множества по адресу или по имени соответствующей ей переменной. Причем структура, получаемая по адресу и по имени для одной переменной, должна быть одна и та же.
объект, позволяющий определить тип переменной, указанный в директиве OpenMP.
Далее описан набор правил, позволяющий обнаружить ошибку инициализации:
Если переменная определена как THREADPRIVATE, то работать с ней приходится иначе, чем с остальными. Для таких переменных каждая нить должна иметь отдельный контекст (назовем его thread_context), не входящий в дерево контекстов. Из этого контекста структуры VarInfo могут быть получены по адресу THREADPRIVATE-переменной. При определении такой переменной для нее заводится в контексте thread_context своя структура VarInfo, поле init которой изначально имеет значение false. При обращении к переменной структура VarInfo так же берется из контекста thread_context. Если переменная появляется в директиве COPYIN, то все нити этой группы копируют себе значение поля init из контекста thread_context главной нити. В случае, появления THREADPRIVATE-переменной в директиве COPYPRIVATE, то значение поля init передается всем нитям группы.
При чтении переменной в текущем контексте данной нити ищется структура VarInfo по адресу переменной. Если такая структура не найдена, то она добавляется и в зависимости от варианта устанавливается ее поле init (обозначим его new_init):
переменная определена как SHARED, тогда по адресу ищется структура VarInfo в родительском для данного контексте. Если такой не найдено, то она создается по такому же принципу. А затем полю new_init присваивается значение init, полученной структуры.
переменная определена как FIRSTPRIVATE или REDUCTION. Этот случай аналогичен предыдущему, за тем исключением, что поиск ведется не по адресу, а по имени переменной.
переменная определена как PRIVATE или LASTPRIVATE. В этом случае записывается new_init = false.
Если поле init = false, то выдается ошибка.
На рисунке 5 приведена схема, описывающая данный пункт правил.
Рисунок 5: схема работы алгоритма при обращении к переменной
При записи переменной в текущем контексте данной нити ищется структура VarInfo по адресу. Если такая структура не найдена, то она добавляется. Поле init найденной структуры получает значение true. Если переменная типа SHARED, то данный пункт повторяется для родительского контекста.
При освобождении контекста для переменных типа LASTPRIVATE переносятся значения полей init в родительский контекст. Для COPYPRIVATE переменных находится ближайшая вверх по дереву вершина, соответствующая параллельной области, и значения полей init из удаляемого контекста переносятся в структуры VarInfo, полученные по именам этих переменных, во всех непосредственных потомках найденной вершины.
Приведенные правила основаны на отображении модели переноса значений переменных в OpenMP на дерево контекстов. В результате структуры VarInfo адекватно описывают соответствующие им переменные, т.е. поля init согласованы с реальными значениями переменных. Что позволяет определить по полю init, имеет переменная значение или нет.
Практическая реализация
В приведенном ранее описании алгоритмов показаны основные идеи, позволяющие обнаруживать искомые ошибки. На основе этих идей были реализованы алгоритмы в виде библиотеки функций динамического отладчика. А так же были проведены работы по модификации алгоритмов для увеличения производительности отладчика.
Отладчик разрабатывался на основе стандарта OpenMP версии 2.5 [1].
В качестве языка программирования для реализации отладчика был выбран язык C++. Благодаря своей выразительной мощности, высокой скорости работы и удобству использования этот язык подошел как нельзя лучше для поставленной задачи. К тому же не малую роль играет его совместимость с языком Fortran, на котором написаны отлаживаемые программы, непосредственно из которых вызываются функции отладчика.
Интерфейс отладчика
Одно из важнейших условий для работы отладчика является правильное использование его интерфейсных функций, которые должны быть вызваны из отлаживаемой программы. За размещение этих вызовов отвечает специальная программа – инструментатор.
В самом начале программы вся статическая информация передается отладчику, который преобразует ее во внутренне представление, и возвращает ссылку на нее, которая будет использоваться для передачи отладчику описания соответствующего объекта при последующих вызовах интерфейсных функций.
Реализованный отладчик для корректной работы требует осуществления следующей инструментации:
В начале программы должна быть вызвана функция инициализации отладчика DBG_Init, до вызова каких-либо других его функций.
должны быть вызваны функции, определяющие границы областей PARALLEL, SINGLE, CRITICAL, DO, SECTIONS, ORDERED. Дополнительно при входе в область PARALLEL должна быть вызвана функция DBG_ParallelEvent.    продолжение
--PAGE_BREAK--
после директивы BARRIER – вызов функции DBG_Barrier
любое обращение к переменным или массивам должно быть обозначено вызовом соответствующей функции.
до того как будет произведено обращение к массиву, информация о нем должна быть передана отладчику. Это необходимо, чтобы определить его размер.
начало и конец вызова любой функции, не принадлежащей интерфейсу отладчика, должны быть отмечены соответствующими обращениями к нему. Так же требуется передача информации об актуальных параметрах.
Тело проинструментированной функции должно содержать в начале и конце соответствующие обращения к отладчику. Формальные параметры должны быть выделены среди остальных переменных.
определение threadprivate-переменных и common-блоков должно быть передано отладчику.
Объединение алгоритмов
Приведенные алгоритмы поиска ошибок общей памяти и ошибок инициализации разрабатывались таким образом, чтобы они имели общую основу, которая бы позволила сократить накладные расходы при работе отладчика. Такой основой является расширенное дерево контекстов, т.к. при поиске ошибок общей памяти без ущерба для алгоритма можно использовать именно его.
Струкутура Context в алгоритме обнаружения ошибок инициализации содержит поля, обобщающие аналогичные поля структуры в другом алгоритме. Но она содержит не все необходимые другому алгоритму поля. Поэтому объединенная структура Context включает в себя следующее:
номер соответствующей контексту нити
идентификатор критической области
множество структур VarInfo, которые можно получить по адресу или имени, указанному в качестве ключа.
объект, определяющий тип любой переменной в данном контексте.
Структура VarInfo вне зависимости от типа переменной содержит поле init и имя переменной. Однако, во время выполнения программы в структуры VarInfo может добавляться информация о чтении и записи, необходимая для нахождения ошибок общей памяти.
Правила работы отладчика состоят из объединенных правил двух алгоритмов.
В отладчике используется одно дерево контекстов для всех нитей, и каждая нить может его модифицировать, причем в соответствии с алгоритмами нить может обратиться к любой вершине, расположенной вверх по дереву относительно текущей вершины. Поэтому, чтобы исключить возможность появления ошибки общей памяти в самом отладчике, необходимо обращения к дереву заключать в критические секции. Но описанные алгоритмы подразумевают работу с деревом при каждом обращении к переменным, что приводит к появлению очень большого числа критических секций, а, следовательно, огромных накладных расходов. Это подтвердилось при тестировании, реализованного таким образом отладчика, когда во время отладки программа замедлилась в сотни тысяч раз по сравнению с не инструментированной программой.
Тестирование показало, что для достижения приемлемой скорости работы отладчика необходимо избавиться от любых конструкций синхронизации в местах, отличных от мест синхронизации в отлаживаемой программе. Поэтому дальнейшие работы были направлены на модификацию алгоритмов с целью увеличения скорости работы программы.
Оптимизация отладчика
Ключевым моментом в оптимизации отладчика было устранение критических секций в обработчиках чтения и записи переменных. Для этого была исключена какая-либо модификация родительских и расположенных выше по дереву вершин. Для выполнения данного ограничения, пришлось произвести следующие изменения в алгоритмах:
При обращении к переменным каждая нить для обнаружения ошибок общей памяти должна записывать изменения только в свой контекст. Так же поле init может быть изменено только в своем контексте.
В каждом месте, где располагается явная или неявная директива barrier, главная нить группы собирает накопленную информацию каждой нитью во всех вершинах потомках родительской вершины, т.е. в соседних вершинах. После чего происходит анализ собранных данных на предмет наличия ошибок общей памяти и сохраняет собранную информацию в родительский контекст, предварительно заменяя в этих данных номера соседних нитей на свой. Данные в текущих контекстах нитей группы обнуляются. Для ошибок инициализации производится сбор информации о полях init со всех соседних контекстах данной группы. Если для общей переменной находится хоть одно поле init со значением true, то это значение устанавливается во всех соседних контекстах, а так же в родительском контексте.
Сохранение всех обращений к переменным каждой нитью требуют больших затрат памяти, поэтому реализованный отладчик хранит в списках ReadList и WriteList только первый оператор, обратившийся к переменной в данном контексте. В результате достигается значительная экономия памяти, но для каждой параллельной области обнаруживается только первая пара операторов, создающих ошибку общей памяти при работе с этой переменной.
В целях увеличения производительности массивы представлены не в виде набора переменных, а как единое целое. Структура, описывающая массив содержит имя массива, его длину и набор структур, состоящих из тех же полей, что и VarInfo, за исключением поля имени переменной. Причем количество структур в наборе равно длине массива.
Таким образом, при первом же обращении к одному элементу массива будет выделена память для данных сразу по всем элементам. Этот метод в некоторых случаях увеличивает затраты по памяти, зато сокращает время работы программы. Хотя в случаях, когда нить в промежутке между синхронизациями обходит массив целиком, то расход памяти при такой организации меньше за счет того, что имя массива общее для всех элементов.
Результаты тестирования
Для нахождения ошибок общей памяти, отладчику требуется, чтобы существовало, по крайней мере, две нити в параллельной области. Поэтому тестирование проводилось на многопроцессорной системе с общей памятью IBM eServer pSeries 690 (Regatta). Для отладки была взята программа Jacobi, находящая приближенное решение уравнения Пуассона методом Якоби в двумерном случае.
Jacobi_org – программа без инструментации
Jacobi_dbg – программа с вызовом функций отладчика
Таблица 2: время выполнения программ
программа
2 нити
4 нити
8 нитей
Jacobi_org
5.748
2.958
1.496
Jacobi_dbg
5294
2794
2351
Следует отметить, что отладчик обладает не полной функциональностью, т.е. не были реализованы некоторые части алгоритмов, такие как обработка common-блоков, работа с threadprivate-переменными, а также обработка директивы ORDERED и механизма замков. Все же, полученное время выполнения программы близко к окончательному, так как добавление обработки этих случаев не должно сильно повлиять на производительность.
Из таблицы видно, что при отладке программа замедляется примерно в 900 раз при работе на 2-х и 4-х нитях. Это, несомненно, сильное замедление, однако, имеются возможности существенного снижения накладных расходов, за счет сокращения обрабатываемой информации.
Для демонстрации работы реализованного отладчика и сравнения его с Intel Thread Checker`ом была взята та же самая программа Jacobi. Запуск производился на одной и той же машине, обеспечивающей выполнение программы на 2 нитях.
Ниже приведен листинг корректной программы Jacobi. Обозначим его как Jacobi_correct.
PROGRAM JAC
PARAMETER (L=100)
REAL A(L,L), EPS, MAXEPS, B(L,L)
external omp_get_wtime;
double precision omp_get_wtime;
DOUBLE PRECISION sTime,eTime,dTime,st,et,dt;
INTEGER ITMAX
sTime = omp_get_wtime();
ITMAX=1000
!$OMP PARALLEL
!$OMP DO
DO 1 J = 1, L
DO 1 I = 1, L
A(I, J) = 0.
IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THEN
B(I, J) = 0.
ELSE
B(I, J) = ( 1. + I + J )
ENDIF
1 CONTINUE
!$OMP END PARALLEL     продолжение
--PAGE_BREAK--
st = omp_get_wtime();
DO 2 IT = 1, ITMAX
EPS = 0.
!$OMP PARALLEL DEFAULT (SHARED) PRIVATE (I,J) REDUCTION (MAX:EPS)
!$OMP DO
DO 21 J = 2, L-1
DO 21 I = 2, L-1
EPS = MAX ( EPS, ABS( B( I, J) — A( I, J)))
A(I, J) = B(I, J)
21 CONTINUE
!$OMP DO
DO 22 J = 2, L-1
DO 22 I = 2, L-1
B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+
* A( I, J+1 )) / 4
22 CONTINUE
!$OMP END PARALLEL
et = omp_get_wtime();
dt = et — st;
st = et;
PRINT 200, IT, EPS, dt
200 FORMAT('IT = ',I4, ' EPS = ', E14.7,' time = ',F14.6)
2 CONTINUE
eTime = omp_get_wtime();
dTime = eTime-sTime;
print *, 'time = ', dTime
C 3 OPEN (3, FILE='JAC.DAT', FORM='FORMATTED', STATUS='UNKNOWN')
C WRITE (3,*) B
C CLOSE (3)
END
Далее описана измененная часть программы Jacobi, в которую были внесены ошибки для демонстрации работы отладчиков. ОбозначимданныйварианткакJacobi_error.
init = 0
!$OMP PARALLEL DEFAULT (SHARED) PRIVATE (I,J,i_test)
C REDUCTION (MAX:EPS)
!$OMP DO
DO 21 J = 2, L-1
DO 21 I = 2, L-1
EPS = MAX ( EPS, ABS( B( I, J) — A( I, J)))
A(I, J) = B(I, J)
B(J,I)=A(J,I)
21 CONTINUE
i_test = init
!$OMP DO PRIVATE(init)
DO22 J = 2, L-1
DO22 I = 2, L-1
B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+
* A( I, J+1 )) / 4
i_test = init
22 CONTINUE
!$OMP END PARALLEL
При запуске программы Jacobi_correct оба отладчика ничего не нашли.
Для программы Jacobi_error отладчик Inte Thread Checker (ITC) выдал диагностику, описанную в таблице 3.
Таблица 3: диагностика программы Jacobi_error отладчиком Intel Thread Checker
Short description
description
count
Write -> Read data-race
Memory read at «Jacobi_err.F90»:37 conflicts with a prior memory write at «Jacobi_err.F90»:37 (flow dependence)
4686295
Write -> Write data-race
Memory write at «Jacobi_err.F90»:37 conflicts with a prior memory write at «Jacobi_err.F90»:37 (output dependence)
5727667
Read -> Write data-race
Memory write at «Jacobi_err.F90»:37 conflicts with a prior memory read at «Jacobi_err.F90»:37 (anti dependence)
1041372
Write -> Read data-race
Memory read at «Jacobi_err.F90»:37 conflicts with a prior memory write at «Jacobi_err.F90»:39 (flow dependence)
2400402
Write -> Read data-race
Memory read at «Jacobi_err.F90»:38 conflicts with a prior memory write at «Jacobi_err.F90»:39 (flow dependence)
2400717
Write -> Read data-race
Memory read at «Jacobi_err.F90»:39 conflicts with a prior memory write at «Jacobi_err.F90»:38 (flow dependence)
2401245
Read -> Write data-race
Memory write at «Jacobi_err.F90»:39 conflicts with a prior memory read at «Jacobi_err.F90»:38 (anti dependence)
2401283
Read -> Write data-race
Memory write at «Jacobi_err.F90»:39 conflicts with a prior memory read at «Jacobi_err.F90»:37 (anti dependence)
315
Read -> Write data-race
Memory write at «Jacobi_err.F90»:38 conflicts with a prior memory read at «Jacobi_err.F90»:39 (anti dependence)
321
Диагностика программы Jacobi_error, выданная реализованным мной отладчиком (debugger), выглядит следующим образом.
(Jacobi_err.fdv:37 — Jacobi_err.fdv:37):variable eps — shared error(write-read)
(Jacobi_err.fdv:37 — Jacobi_err.fdv:37):variable eps — shared error(write-write)
(Jacobi_err.fdv:39 — Jacobi_err.fdv:37):array b — shared error(write-read)
(Jacobi_err.fdv:38 — Jacobi_err.fdv:39):array a — shared error(write-read)
Jacobi_err.fdv:49: variable init — init error
В таблице 4 приведены времена выполнения описанных программ для обоих инструментов (ITC, debugger), включая контрольный запуск программы без отладки (original).
Таблица 4: Время выполнения программ в секундах.


original
debugger
ITC
Jacobi_correct
0,66
183
193
Jacobi_error
0,87
322
438
Заключение
В рамках проделанной работы были разработаны алгоритмы нахождения ошибок, описанных в постановке задачи, а также на их основе создан отладчик, осуществляющий динамический контроль корректности OpenMP-программ, написанных на языке Fortran77.
Общий объем исходного кода разработанного отладчика составил около 4000 строк.
Было проведено тестирование, которое позволило оценить замедление скорости работы программы под управлением отладчика, а так же увеличение объема потребляемой памяти. Дополнительно реализованный отладчик был сравнен с существующим отладчиком IntelThreadChecker.
Для применения отладчика для реальных производственных программ, которые невозможно отлаживать на модельных исходных данных, требуется реализовать методы выборочного контроля, позволяющие кардинально сократить накладные расходы, сохранив высокую вероятность обнаружения ошибок и их точную локализацию.
Литература
OpenMP Application Program Interface Version 2.5 May 2005 [PDF](http://www.openmp.org/mp-documents/spec25.pdf)
Christian Terboven.Comparing Intel Thread Checker and Sun Thread Analyzer. 2007. [PDF](http://www.fz-juelich.de/nic-series/volume38/terboven.pdf)
M. Suess, C. Leopold. Common mistakes in OpenMP and how to avoid them. 2006. [PDF](http://www.michaelsuess.net/publications/suess_leopold_common_mistakes_06.pdf)
Sun Studio 12: Thread Analyzer User'sGuide. 2007 [HTML,PDF](http://docs.sun.com/app/docs/doc/820-0619)
Intel Thread Checker 3.1 – Documentation. [PDF](http://software.intel.com/en-us/articles/intel-thread-checker-documentation/)