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

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

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

· при входе в критическую область в текущем контексте поле critical_id модифицируется, добавлением имени текущей области.

· при выходе из критической области в текущем контексте из поля critical_id исключается имя этой области.

· при любой (явной или неявной) барьерной синхронизации требуется для каждой нити данной параллельной области сбросить информацию обо всех переменных в текущем контексте. Т.е. во всех вершинах, расположенных под вершиной, описывающей параллельную область, необходимо перебрать все структуры VarInfo и очисть их списки ReadList и WriteList. В качестве альтернативы, можно просто удалить все эти структуры VarInfo.

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