Теперь можно описать сам алгоритм. Он состоит из следующих правил:
· Дерево контекстов строится в соответствии с приведенными ранее правилами.
· Пусть 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 приведена схема, описывающая данный пункт правил.
Рисунок 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.
Страницы: 1, 2, 3, 4, 5
