Динамический контроль корректности OpenMP-программ (стр. 3 из 6)

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

4.2 Построение дерева контекстов

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

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

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

Определим некоторую структуру, которая будет содержать данные о текущем состоянии нити, и назовем ее контекстом (Context). Для каждой нити в каждый момент времени доступен некоторый набор переменных, к которым они могут обращаться, при этом у разных нитей эти наборы обычно разные, т.к. они могут обладать приватными переменными и находиться в разных частях программы. Пусть текущий контекст нити содержит структуры данных, описывающие каждую переменную, (VarInfo) к которой было обращение с момента существования этого контекста. Структура VarInfo может быть взята из текущего контекста нити по некоторому ключу, например, по адресу соответствующей переменной. Конкретные ключи будут приведены далее при описании алгоритмов обнаружения ошибок, так же как будет уточнено содержимое самой структуры Context.

Теперь для полноты описания состояния всей программы следует поместить в вершины приведенного выше дерева, описывающего связи между нитями, структуры описывающие состояния самих нитей, а именно структуры Context. Такое дерево назовем деревом контекстов.

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

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

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

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

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

· При выходе из функции текущая вершина нити удаляется, и текущей становится ее родительская вершина.

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

Рисунок 3: Пример дерева контекстов

Построенное дерево будет использоваться при дальнейшем описании алгоритмов, поэтому для удобства описания определим некоторые понятия, которые могут встретиться. Контекст или структура Context соответствует вершине дерева. Текущим контекстом для данной нити называется листовая вершина дерева, которая соответствует этой нити. Для каждой нити существует только один текущий контекст. Родительской вершиной называется вершина, к которой присоединена данная, и расположенная непосредственно над данной вершиной.

4.3 Обнаружение ошибок общей памяти

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

В OpenMP имеются следующие конструкции синхронизации:

· Критические секции.

· Атомарные операторы. Данную конструкцию можно заменить на критическую секцию с уникальным именем.

· Барьерная синхронизация.

· Последовательное выполнение блока в цикле (ordered).

· Механизм замков.

4.3.1 Представление критических областей

Под критической областью (секцией) понимается участок программы заключенный в некоторую OpenMP-конструкцию, которая не допускает выполнение данного кода одновременно несколькими нитями. Причем данные области могут быть как статическими (critical, ordered, atomic), так и динамическими (механизм замков).

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

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

· каждая область, помеченная как ordered, получает уникальное имя

· каждая директива atomic получает уникальное имя

· имя критической секции (critical) указано в директиве

· для каждой переменной замков заводится свое уникальное имя

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

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

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

4.3.2 Описание алгоритма

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

· список обращений к переменной на запись (WriteList). Каждый элемент данного списка включает в себя следующую информацию:

- номер нити, обратившейся к переменной

- идентификатор критической секции

- ссылка на описание места в исходном коде, из которого было произведено обращение к переменной

· список обращений к переменной на чтение (ReadList). Список состоит из таких же элементов, что и WriteList.

· имя переменной.

· адрес переменной.

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

Структура Context из дерева контекстов должна содержать следующие данные:

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

· идентификатор нити, для которой данный контекст является текущим. Этот идентификатор не меняется на протяжении всего времени существования данного контекста.

· идентификатор критической области (critical_id).

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