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

2

Рисунок 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):

o переменная определена как SHARED, тогда по адресу ищется структура VarInfo в родительском для данного контексте. Если такой не найдено, то она создается по такому же принципу. А затем полю new_init присваивается значение init, полученной структуры.

o переменная определена как FIRSTPRIVATE или REDUCTION. Этот случай аналогичен предыдущему, за тем исключением, что поиск ведется не по адресу, а по имени переменной.

o переменная определена как PRIVATE или LASTPRIVATE. В этом случае записывается new_init = false.

Если поле init = false, то выдается ошибка.

На рисунке 5 приведена схема, описывающая данный пункт правил.

2

Рисунок 5: схема работы алгоритма при обращении к переменной

· При записи переменной в текущем контексте данной нити ищется структура VarInfo по адресу. Если такая структура не найдена, то она добавляется. Поле init найденной структуры получает значение true. Если переменная типа SHARED, то данный пункт повторяется для родительского контекста.

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

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

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