Дипломная работа: Динамический контроль корректности 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. Поэтому, чтобы не включать имена всех общих переменных по умолчанию в данный список, можно заменить его таким объектом-определителем типа. Причем для корневого контекста все переменные считаются приватными, а для контекста, созданного при вызове функции, переменные, соответствующие параметрам этой функции, являются общими, а все остальные приватными.

Теперь можно описать сам алгоритм. Он состоит из следующих правил:

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