Загрузка...
Учебная работа. Дипломная работа: Динамический контроль корректности OpenMP-программ
Принципиальным шагом процесса сотворения хоть какого программного продукта является его отладка. При чем данный шаг по количеству затраченных на него средств часто сравним со всеми остальными стадиями разработки программного продукта. В особенности очень растет трудозатратность отладки в случае, если программка была написана с внедрением параллельных вычислений. Данная работа посвящена автоматическому нахождению более всераспространенных ошибок, возникающих при использовании OpenMP конструкций в Fortran-программах. В процессе работы были разработаны и реализованы методы нахождения таковых ошибок, также проведено сопоставление приобретенного инструмента с существующими аналогами.
Оглавление
1 Введение. 3
1.1 разработка OpenMP. 3
1.2 Ошибки, возникающие при использовании OpenMP. 4
1.3 Отладка параллельных программ. 8
1.4 Цель работы.. 9
2 Постановка задачки. 10
3 Обзор имеющихся отладчиков. 11
3.1 Сопоставление отладчиков. 12
3.2 Выводы.. 13
4 Динамический контроль правильности. 14
4.1 Схема работы отладчика. 14
4.2 Построение дерева контекстов. 15
4.3 Обнаружение ошибок общей памяти. 18
4.3.1 интерфейс отладчика. 27
5.2 Объединение алгоритмов. 28
5.3 Оптимизация отладчика. 30
5.4 Результаты тестирования. 31
Литература. 38
1 Введение
1.1 разработка OpenMP
Эталон OpenMP[1] создавался для упрощения разработки параллельных программ для вычислительных систем с общей памятью, а так же для распараллеливания уже имеющихся поочередных программ. Эталоном определены особые комменты (команды препроцессору для C/C++) – директивы компилятору, конкретно управляющие параллелизмом программки, вспомогательные функции, дозволяющие создавать методы, направленные на параллельное выполнение, и переменные окружения, управляющие действием выполнения параллельных областей.
программка, использующая директивы OpenMP, состоит из поочередных и параллельных участков. Сначала ее выполнения создается одна нить, которая существует в протяжении всей программки. Когда какая-либо нить доходит до параллельного участка, то порождаются доп нити, выполняющие вкупе с ней этот участок. Группой нитей именуется огромное количество нитей, сделанных при входе в данную параллельную область, включая породившую их нить, именуемую главной. Нить, достигшая конца параллельной области, дожидается всю группу. Когда все нити одной группы дойдут до конца параллельного участка, все нити не считая главной освобождаются, а основная нить продолжает выполнение программки. На рисунке 1 показан пример сотворения и освобождения нитей в параллельных областях в случае наличия вложенных параллельных участков.
Набросок 1: Пример выполнения параллельного участка
В OpenMP память разделяется на 2 вида: общая память и локальная память.
Общая память доступна нескольким нитям сразу. Но, для работы с ней нужно употреблять синхронизирующие конструкции, которые разрешают избежать недетерминизма.
локальная память доступна лишь одной нити.
1.2 Ошибки, возникающие при использовании OpenMP
В 2004-2005 годах в University of Kassel(Германия) проводилось исследование, целью которого было выявление более нередко совершаемых ошибок, обусловленных неправильным внедрением функций и директив OpenMP, и приводящих к неправильному выполнению программки. работы с OpenMP, что позволило выявить ошибки, допускаемые начинающими программерами. В итоге были обнаружены последующие ошибки [3]:
1)
Незащищенный доступ к общим переменным.
Данная ошибка возникает, когда несколько нитей работают с общей памятью без какой-нибудь синхронизации. В этом случае вероятны последующие ситуации:
— все нити лишь читают переменную, тогда ошибки нет, т.к.
— все нити лишь пишут в переменную. Так как они это делают сразу, то недозволено найти, какое значение получит переменная опосля выполнения всех операций записи. И
— часть нитей читают переменную, а часть пишут в нее. тут кроме эффекта предшествующего варианта, наблюдается подобная неопределенность. Когда какая-либо нить пробует прочесть
2)
Внедрение механизма замков без директивы
flush
.
Этот пункт является ошибкой лишь для ранешних версий OpenMP(до версии 2.5).
При работе с общими переменными предполагается, что любая нить работает с копией данной переменной, расположенной в кэше соответственного микропроцессора. Директива flush обновляет во всех нитях значения общих переменных, т.е. все нити будут созидать крайние конфигурации. Потому, если употреблять замки без директивы flush, то вероятна ситуация, когда одна нить замок поставит, а иная не увидит никаких конфигураций, и будет считать, что ресурс волен, и его можно захватить. В итоге будет неправильная ситуация, когда сходу несколько нитей установили один и этот же замок. Начиная с версий OpenMP 2.5, директива flush заходит в состав функций для работы с замками.
3)
Чтение общих переменных без директивы
flush
.
Ситуация подобная предшествующему случаю. Если не употреблять директиву flush перед чтением переменной, то нить может не получить крайнее освеженное
4)
Внедрение переменных как приватных, хотя такими они не являются.
Эта ошибка вызвана тем, что программер запамятовал указать, что переменная является приватной. Во время выполнения программки, данную ошибку нереально отличить от ошибки, описанной в первом пт.
5)
Внедрение предложения
ordered
без конструкции
ordered
.
Предполагается, что если в директиве распараллеливания цикла обозначено условие ordered, то снутри этого цикла обязана размещаться область, помеченная как ordered. Это значит, что обозначенная область обязана быть выполнена в том же порядке (по итерациям цикла), что и в поочередной программке. Отсутствие таковой области в теле цикла, при наличии условия ordered считается ошибкой.
6)
Переменная распараллеливаемого цикла объявлена как общая.
Таковая переменная не быть может общей, т.к. у каждой нити она обязана принимать свое
7)
Отсутствие слова
for
в директиве parallel for
Итогом данной ошибки будет не разделение цикла меж нитями, а любая нить будет делать его полностью, что может привести к ошибке общей переменной.
8)
Изменение числа нитей в параллельной области программки.
В OpenMP можно изменять число нитей, на которые программка будет поделена, лишь в поочередном участке программки.
9)
Снятие замка нитью, которая его не устанавливала.
Замок быть может снят лишь нитью, установившей его.
10)
Изменение переменной распараллеленного цикла снутри него.
Изменение управляющей переменной может привести к непредсказуемым результатам, т.к. будет нарушено распределение итераций цикла меж нитями.
Из перечисленных ошибок более частыми и тяжело отслеживаемыми являются ошибки 1 и 4. Но так как отличить их друг от друга во время выполнения программки почти всегда нереально, то следует их соединить в одну группу. Назовем ее ошибками общей переменной.
Приведенный перечень ошибок не является полным и потому следует сказать еще о паре ошибок, которые могут появиться в OpenMP-программе:
· Ошибка инициализации
. Сущность данной ошибки состоит в том, что в программке может появиться ситуация, когда происходит чтение переменной, которой еще не присвоили изначальное значения. Но, если создать ее firstprivate, то не считая того, что она становится приватной, так ей еще будет присвоено области. В OpenMP есть различные характеристики директив, которые аналогичным образом определяют передачу значений от начальных приватным переменным и от приватных начальным переменным. Потому, если программер некорректно задал тип приватной переменной, то, быстрее всего, проявится конкретно эта ошибка.
· Ошибка обоюдной блокировки (
deadlock
)
. Это традиционная ошибка, которая возникает, когда несколько нитей поначалу захватывают в собственное использование некие ресурсы, а потом пробуют захватить ресурсы, оккупированные иными нитями. В итоге все нити блокируются и программка виснет. Простым примером обоюдной блокировки в OpenMP является вариант, когда в одной критичной секции находится иная, но с таковым же именованием. В этом случае нить, когда дойдет до 2-ой критичной секции, перекроет сама себя. Этот вид ошибок находить не весьма трудно, т.к. отыскать пространство зависания программки обычно не составляет особенного труда.
1.3 Отладка параллельных программ
процесс отладки параллельных программ можно условно поделить на классическую и автоматическую.
В классическом подходе отлаживаемая программка запускается под управлением отладчика, который в хоть какой момент может остановить выполнение программки и выдать ее текущее состояние. Таковым образом, юзер может просматривать содержимое переменных и текущее положение в начальном коде, выполняя программку по шагам либо расставляя контрольные точки. И на основании приобретенной инфы, юзер может найти причину неправильной работы программки. Следует увидеть, что обычно при таком подходе параллельная работа моделируется программно, потому что при достижении контрольной точки хоть какой нитью все другие нити так же должны тормознуть, при этом они могут находиться в это время в любом месте программки. Таковым образом, при нескольких пусках, когда одна нить будет доходить до контрольной точки, то параллельные ей нити могут останавливаться всякий раз в различных местах, а как следует значения переменных тоже будут различными, что в значимой степени наращивает сложность обнаружения ошибок.
Одним из видов автоматической отладки является динамический контроль правильности. Автоматическая отладка дозволяет лишь найти правильность самой программки, а не корректность работы реализованного в ней метода. Т.е. автоматом будут найдены участки кода, которые делают ситуации несоответствующие эталону языка либо применяемой технологии. Работа динамического контроля правильности заключается в слежении за состоянием отлаживаемой программки во время ее выполнения и обнаружении неправильных ситуаций.
1.4 Цель работы
Цель дипломной работы – создать и воплотить метод динамического контроля правильности использования директив OpenMP в программках, написанных на языке Fortran. И минимизировать количество потребляемых ресурсов при работе отладчика.
2 Постановка задачки
Задачка инструмента, проводящего динамический контроль правильности OpenMP программки, заключается в том, чтоб отыскивать в отлаживаемой программке неточное внедрение директив, которое может привести к неверному результату ее работы. Тем таковой инструмент должен упростить и убыстрить весь процесс отладки, благодаря нахождению самых всераспространенных и тяжело обнаруживаемых ошибок. Из перечисленного во внедрении перечня ошибок такими являются два вида: ошибки общей памяти и ошибки инициализации.
Ошибки общей памяти появляются, когда несколько нитей сразу и независимо друг от друга работают с одной и той же областью памяти, при этом хотя бы одна из нитей видоизменит содержимое данной области.
Ошибки инициализации появляются при чтении переменной, которой не присвоено никакое изначальное одной машине, но приводить к неверным результатам работы программки на остальных, зависимо от использованных компиляторов и библиотек OpenMP.
Таковым образом, требуется создать и воплотить методы нахождения ошибок общей памяти и ошибок инициализации в OpenMP программках, написанных на языке Fortran 77.
3 Обзор имеющихся отладчиков
На данный момент есть несколько коммерческих инструментов, осуществляющих динамический контроль правильности OpenMP программки. Разглядим отладчики Intel Thread Checker[5] и Sun Thread Analyzer[4]. Оба инструмента способны отыскивать ошибки общей памяти и обоюдной блокировки в программках, использующих не только лишь OpenMP, да и остальные разновидности параллелизма с общей памятью, к примеру, нити POSIX.
Intel Thread Checker имеет два режима работы: зависимый от числа нитей и независящий.
Для работы в первом отлаживаемую программку можно не перекомпилировать, если она компилировалась с включением отладочной инфы. В этом режиме пуск программки должен осуществляться под управлением отладчика. Для обнаружения ошибок общей памяти нужно запускать программку на наиболее чем одной нити, при всем этом в случае нахождения ошибки будет выдано лишь положение в начальном коде, а имя переменной, с которой связана эта ошибка, остается неведомым.
Независящий от числа нитей режим работы врубается добавлением при компиляции программки при помощи компилятора Intel функции –tcheck. При всем этом в отлаживаемой программке должны отсутствовать вызовы функций работы с числом нитей, таковых как omp_set_num_threads(), omp_get_num_threads(), omp_get_max_threads(), omp_get_thread_num(), и omp_get_num_procs(). В этом режиме программка обязана быть запущена на одной нити. В процессе работы параллелизм будет смоделирован и, не глядя на то, что реально при работе программки ошибки не произошли, они будут найдены, как потенциальные. Так же этот режим дозволяет получить наиболее подробную информацию о ошибке.
Sun Thread Analyzer просит, чтоб программка была скомпилирована с ключом -xinstrument=datarace. Так же обязана быть включена отладочная информация для того, чтоб отладчик мог выдать диагностику с привязкой к начальному коду. Для обнаружения ошибок, пуск программки должен быть произведен на нескольких нитях.
3.1 Сопоставление отладчиков
Сопоставление приведенных отладчиков было проведено в Center for Computing and Communication RWTH Aachen University в Германии[2]. Intel Thread Checker и Sun Thread Analyzer запускались на нескольких программках с различными параметрами, для определения плюсов и недочетов этих инструментов. Больший Энтузиазм представляют приобретенные результаты замеров производительности отлаживаемых программ под управлением данных инструментов и без их, а так же количество потребляемой памяти. Отладчики тестировались на 3 примерах:
— Jacobi. Приближенное решение двумерного уравнения Пуассона способом Якоби.
— SMXV. Умножение матрицы на вектор в случае, когда в матрице имеется огромное количество нулевых частей.
— AIC. Вычисление интеграла адаптивным способом.
В Таблице 1 приведены характеристики производительности и потребляемой памяти (в мб) при работе программки. При всем этом инструменты тестировались на различных машинках с внедрением различных компиляторов:
Intel – пуск программки, скомпилированной компилятором Intel, без отладчика на 2 нитях.
Intel Thread Checker – пуск программки на 2 нитях под управлением этого инструмента в зависимом от числа нитей режиме, т.к. методы SMXV и AIC употребляют функции для работы с числом нитей.
Sun – выполнение программки на 2 нитях без режима отладки, с внедрением компилятора конторы Sun.
Sun Thread Analyzer – отладка программки на 2 нитях при помощи Sun Thread Analyzer.
Таблица 1: свойства выполнения программ
Jacobi
SMXV
AIC
MByte
MFLOP/s
MByte
MFLOP/s
MByte
время
Intel
5
621
40
929
4
5,0 сек
Intel Thread Checker
115
0,9
1832
3,5
30
9,5 сек
Sun
5
600
50
550
2
8,4 сек
Sun Thread Analyzer
125
1,1
2020
0,8
17
8,5 сек
Из приведенной таблицы видно, что замедление во время отладки программки может достигать сотен раз, в то время как потребление памяти так же возрастает в 10-ки раз.
К тому же при проведении данного тестирования было увидено, что Intel Thread Checker работал на 4-х нитях с таковой же производительностью, что и на 2-х.
3.2 Выводы
Рассмотренные инструменты отладки, а конкретно Intel Thread Checker и Sun Thread Analyzer, с фуррором могут быть применены для отладки маленьких программ. Но, из-за значимого роста размера потребляемых ресурсов во время отладки они стают не применимыми для задач, работающих с большенными размерами данных и производящими долгие вычисления. Для таковых приложений требуется подбирать особые входные данные, чтоб минимизировать потребляемые ресурсы. В неких вариантах таковой способ быть может не применим, к примеру, когда размер требуемой памяти не очень зависит от входных данных, либо если программка получает на вход данные конкретно от другого приложения.
4 Динамический контроль правильности
4.1 Схема работы отладчика
В данной главе описана схема работы отладчика, реализующего динамический контроль правильности OpenMP программки.
Вначале имеется начальный код Fortran программки со вставленными директивами OpenMP. Отладчик скомпилирован в объектный файл, и имеет интерфейс в виде набора функций, которые должны быть вызваны в процессе работы отлаживаемой программки, при пришествии соответственных событий, к примеру, при воззвании к памяти. С помощью специальной программки – инструментатора, в начальный код вставляются вызовы интерфейсных функций отладчика. Дальше приобретенный код должен быть скомпилирован вкупе с объектным файлом отладчика в выполняемую программку, которую можно запускать на вычислительной системе с общей памятью. В итоге работы данной программки будет выдана информация о найденных ошибках. На рисунке 2 представлена описанная схема.
Набросок 2: Общая схема работы отладчика.
Необходимо подчеркнуть, что при данной схеме работы будут найдены ошибки лишь в тех участках кода, для которых в процессе выполнения программки были выполнены вызовы функций отладчика. Из этого следует, что для исследования всего кода на наличие ошибок нужно подходящим образом подобрать входные данные. Но в любом случае недосягаемый код проверен не будет из-за того, что вставленные функции отладчика также будут недосягаемы.
Благодаря таковой схеме можно проверить на наличие ошибок не только лишь всю программку полностью, да и раздельно некие ее участки. Это быть может полезно, если программка просит существенное количество ресурсов, и при всем этом ошибка локализована в некой ее части. Тогда можно вставить вызовы функций отладчика лишь в данный участок программки, также в места, содержащие нужную информацию для работы метода, такие как начало программки, описание переменных, массивов и т.д.
4.2 Построение дерева контекстов
Так как во время выполнения есть несколько параллельно работающих нитей, которые объединены в группы, надлежащие параллельным областям, которые могут быть вложенными, то для анализа текущего состояния программки комфортно выстроить дерево, отображающее связь нитей в данный момент. Сейчас нужно решить, что будет находиться в верхушках этого дерева.
В постановке задачки требуется отыскивать два вида ошибок: общей памяти и инициализации, а, как следует, главным объектом исследовательских работ являются переменные и массивы, а поточнее воззвание к памяти. Но, потому что чтение и запись в память соединено с переменными и массивами, то можно соединить данные о этих операциях и информацию о переменной в одну структуру, которую назовем VarInfo
. И сейчас таковая структура становится главным объектом, с которым будет работать отладчик.
В этом разделе описывается мысль алгоритмов, и потому в их описании лучше всего работать с обобщенными объектами. Это дозволит упростить сами методы, оставив постоянной их главный принцип работы. Потому для общности можно считать, что массивы состоят из набора переменных, соответственных любому элементу массива, и имеющих имена, составленные из имени самого массива и индекса, соответственного элемента. Таковым образом, далее пойдет речь лишь о работе с переменными.
Определим некую структуру, которая будет содержать данные о текущем состоянии нити, и назовем ее контекстом
(Context
). Для каждой нити в любой момент времени доступен некий набор переменных, к которым они могут обращаться, при всем этом у различных нитей эти наборы обычно различные, т.к. они могут владеть приватными переменными и находиться в различных частях программки. Пусть текущий контекст нити содержит структуры данных, описывающие каждую переменную, (VarInfo) к которой было воззвание с момента существования этого контекста. структура VarInfo быть может взята из текущего контекста нити по некому ключу, к примеру, по адресу соответственной переменной. Определенные ключи будут приведены дальше при описании алгоритмов обнаружения ошибок, так же как будет уточнено содержимое самой структуры Context.
Сейчас для полноты описания состояния всей программки следует поместить в верхушки приведенного выше дерева, описывающего связи меж нитями, структуры описывающие состояния самих нитей, а конкретно структуры Context. Такое дерево назовем деревом контекстов
.
Правила построения дерева контекстов смотрятся последующим образом:
· Сначала выполнения программки существует лишь одна нить, а как следует дерево контекстов обязано состоять из одной корневой верхушки, соответственной данной нити.
· При входе в параллельную область создается группа параллельных нитей, которая включает породившую другие нити (главную нить). В этом случае в дереве контекстов к верхушке, соответственной главной нити до данной параллельной области, добавляются вершины-потомки, надлежащие каждой нити из сделанной группы.
· При выходе из параллельной области группа параллельных нитей освобождается, кроме главной нити, которая продолжает работу. В этом случае в дереве удаляются все верхушки, надлежащие каждой нити из удаляемой группы, и их родительская верхушка становится текущей для главной нити.
· При вызове проинструментированной функции, т.е. функции содержащей воззвания к отладчику, к верхушке данной нити добавляется вершина-потомок, которая становится текущей для данной нити.
· При выходе из функции текущая верхушка нити удаляется, и текущей становится ее родительская верхушка.
На рисунке 3 показан пример дерева контекстов. В верхушках этого дерева указан неповторимый номер нитей, который в отличие от номеров OpenMP у всех 2-ух нитей будет разным.
Набросок 3: Пример дерева контекстов
Построенное дерево будет употребляться при предстоящем описании алгоритмов, потому для удобства описания определим некие понятия, которые могут повстречаться. Контекст
либо структура Context
соответствует верхушке дерева. Текущим контекстом
для данной нити именуется листовая верхушка дерева, которая соответствует данной нити. Для каждой нити существует лишь один текущий контекст. Родительской верхушкой
именуется верхушка, к которой присоединена данная, и расположенная конкретно над данной верхушкой.
4.3 Обнаружение ошибок общей памяти
Ошибки общей памяти появляются, когда несколько нитей сразу и независимо работают с одной областью памяти, при этом хотя бы одна нить производит запись в эту область. Под независимостью в определениях OpenMP понимается отсутствие каких-то конструкций синхронизации нитей, позволяющее в любой момент времени обращаться к памяти лишь одной из их.
В OpenMP имеются последующие конструкции синхронизации:
· Критичные секции.
· Атомарные операторы. Данную систему можно поменять на критичную секцию с неповторимым именованием.
· Барьерная синхронизация.
· Последовательное выполнение блока в цикле (ordered).
· Механизм замков.
4.3.1 сразу несколькими нитями. При этом данные области могут быть как статическими (critical, ordered, atomic), так и динамическими (механизм замков).
Для удобства работы будем считать, что границы областей определяются динамически, т.е. начало области определяется при входе в нее, а конец – при выходе.
При определении критичных секций (critical) быть может обозначено некое имя. В этом случае критичные области с различными именами могут производиться параллельно, а с схожими именами будут обозначать одну и ту же критичную область. Эталон OpenMP дозволяет найти критичные области несколькими методами, но для обобщения довольно найти имена критичных областей для всякого варианта:
· любая область, помеченная как ordered, получает неповторимое имя
· любая директива atomic получает неповторимое имя
· имя критичной секции (critical) обозначено в директиве
· для каждой переменной замков заводится свое неповторимое имя
Время от времени появляются ситуации, когда критичные области с различными именами являются вложенными. В этом случае их пересечение не может производиться параллельно ни с одной из областей входящих в их число. Тогда для определения вхождения некого участка кода во огромное количество критичных областей, необходимо ввести понятие идентификатора критичной области.
Идентификатором критичной области
для данного кода именуется огромное количество имен критичных областей, покрывающих этот участок. Дальше определим сопоставление этих идентификаторов. Два идентификатора критичных областей равны
, если пересечение их множеств имен критичных областей не пусто, т.е. найдется таковая критичная область, имя которой заходит в оба идентификатора. И, соответственно идентификаторы не равны
, если пересечение их множеств пусто.
Исходя из определения, следует, что любые два оператора могут производиться параллельно, если их идентификаторы критичной области не равны.
4.3.2 Описание метода
Для обнаружения ошибки общей памяти нужно для каждой общей переменной сохранять данные, о воззваниях к ней. Пусть нужно отыскивать все операторы программки, которые конфликтуют меж собой за доступ к переменной. Тогда для их определения довольно поместить последующую информацию в структуру, описывающую общие переменные (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.
Мысль метода заключается в том, что параллельная область разбита синхронизирующими барьерами на поочередно расположенные участки. Предполагается, что операторы, расположенные снутри 1-го участка могут производиться параллельно, а операторы, расположенные в различных участках постоянно производятся в различное время. Как следует, можно хранить информацию лишь для текущего участка. Это работает, когда в программке существует лишь один уровень параллелизма, а в случае вложенного параллелизма на помощь приходит дерево контекстов, которое дозволяет хранить данные о текущих участках всех параллельных областей.
4.4 Расширенное дерево контекстов
Расширенное дерево контекстов различается от описанного ранее дерева контекстов тем, что при его построении употребляются доп правила:
· при входе нити в всякую из областей SINGLE, DO либо SECTIONS к верхушке, отвечающей данной нити, добавляется вершина-потомок, и она становится текущей для нити.
· при выходе из хоть какой из областей SINGLE, DO либо SECTIONS текущая верхушка нити удаляется и текущей становится ее родительская верхушка.
При разработке хоть какой верхушки в структуру Context, содержащуюся в ней, добавляется информация, позволяющая найти тип переменной в данном контексте по ее имени. При этом, для директив SINGLE, DO либо SECTIONS, если не указан тип переменной, и она не является THREADPRIVATE, то она считается типа SHARED. В контекстах, соответственных вызовам функций, имеется информация о связи фактических и формальных характеристик. Для фактических характеристик функции, которым соответствуют переменные, а не выражения, тип определяется как SHARED.
4.5 Обнаружение ошибок инициализации
Ошибки инициализации появляются при чтении переменной, которой за ранее не присвоили какое-либо
При использовании директив OpenMP переменная может утратить свое
· Переменная объявлена как PRIVATE, тогда она теряет свое
· FIRSTPRIVATE переменная теряет свое
· LASTPRIVATE переменная не имеет исходного значения.
· THREADPRIVATE переменные могут иметь неопределенное
Для обнаружения ошибок этого вида довольно выслеживать воззвания к переменным и иметь построенное расширенное дерево контекстов.
структура VarInfo для работы описываемого метода обязана содержать поле init
, определяющее, присвоено ли переменной какое-либо
структура Context обязана содержать последующие данные:
· огромное количество структур VarInfo для переменных. При разработке контекста это огромное количество пусто. Неважно какая структура быть может выбрана из этого огромного количества по адресу либо по имени соответственной ей переменной. При этом структура, получаемая по адресу и по имени для одной переменной, обязана быть одна и та же.
· объект, позволяющий найти тип переменной, обозначенный в директиве OpenMP.
Дальше описан набор правил, позволяющий найти ошибку инициализации:
· Если переменная определена как THREADPRIVATE, то работать с ней приходится по другому, чем с остальными. Для таковых переменных любая нить обязана иметь отдельный контекст (назовем его thread
_
context
), не входящий в дерево контекстов. Из этого контекста структуры VarInfo могут быть получены по адресу THREADPRIVATE-переменной. При определении таковой переменной для нее заводится в контексте thread_context своя структура VarInfo, поле init которой вначале имеет случае, возникновения THREADPRIVATE-переменной в директиве COPYPRIVATE, то
· При чтении переменной в текущем контексте данной нити ищется структура VarInfo по адресу переменной. Если таковая структура не найдена, то она добавляется и зависимо от варианта устанавливается ее поле init (обозначим его new
_
init
):
o переменная определена как SHARED, тогда по адресу ищется структура VarInfo в родительском для данного контексте. Если таковой не найдено, то она создается по такому же принципу. А потом полю new_init присваивается
o переменная определена как FIRSTPRIVATE либо REDUCTION. Этот вариант аналогичен предшествующему, за тем исключением, что поиск ведется не по адресу, а по имени переменной.
o переменная определена как PRIVATE либо LASTPRIVATE. В этом случае записывается new_init = false.
Если поле init = false, то выдается ошибка.
На рисунке 5 приведена схема, описывающая данный пункт правил.
Набросок 5: схема работы метода при воззвании к переменной
· При записи переменной в текущем контексте данной нити ищется структура VarInfo по адресу. Если таковая структура не найдена, то она добавляется. Поле init отысканной структуры получает
· При освобождении контекста для переменных типа LASTPRIVATE переносятся значения полей init в родительский контекст. Для COPYPRIVATE переменных находится наиблежайшая ввысь по дереву верхушка, соответственная параллельной области, и значения полей init из удаляемого контекста переносятся в структуры VarInfo, приобретенные по именам этих переменных, во всех конкретных потомках отысканной верхушки.
Приведенные правила основаны на отображении модели переноса значений переменных в OpenMP на дерево контекстов. В итоге структуры VarInfo правильно обрисовывают надлежащие им переменные, т.е. поля init согласованы с настоящими значениями переменных. Что дозволяет найти по полю init, имеет переменная
5 Практическая реализация
В приведенном ранее описании алгоритмов показаны главные идеи, дозволяющие обнаруживать разыскиваемые ошибки. На базе этих мыслях были реализованы методы в виде библиотеки функций динамического отладчика. А так же были проведены работы по модификации алгоритмов для роста производительности отладчика.
Отладчик разрабатывался на базе эталона OpenMP версии 2.5 [1].
В качестве языка программирования для реализации отладчика был избран язык C++. Благодаря собственной выразительной мощности, высочайшей скорости работы и удобству использования этот язык подошел как недозволено лучше для поставленной задачки. К тому же не малую роль играет его сопоставимость с языком Fortran, на котором написаны отлаживаемые программки, конкретно из которых вызываются функции отладчика.
5.1 интерфейс отладчика
Одно из важных критерий для работы отладчика является правильное внедрение его интерфейсных функций, которые должны быть вызваны из отлаживаемой программки. За размещение этих вызовов отвечает особая программка – инструментатор.
В самом начале программки вся статическая информация передается отладчику, который конвертирует ее во внутренне работы просит воплощения последующей инструментации:
· Сначала программки обязана быть вызвана функция инициализации отладчика DBG_Init, до вызова каких-то остальных его функций.
· должны быть вызваны функции, определяющие границы областей PARALLEL, SINGLE, CRITICAL, DO, SECTIONS, ORDERED. Добавочно при входе в область PARALLEL обязана быть вызвана функция DBG_ParallelEvent.
· опосля директивы BARRIER – вызов функции DBG_Barrier
· хоть какое воззвание к переменным либо массивам обязано быть обозначено вызовом соответственной функции.
· до того как будет произведено воззвание к массиву, информация о нем обязана быть передана отладчику. Это нужно, чтоб найти его размер.
· начало и конец вызова хоть какой функции, не принадлежащей интерфейсу отладчика, должны быть отмечены надлежащими воззваниями к нему. Так же требуется передача инфы о животрепещущих параметрах.
· тело проинструментированной функции обязано содержать сначала и конце надлежащие воззвания к отладчику. Формальные характеристики должны быть выделены посреди других переменных.
· определение threadprivate-переменных и common-блоков обязано быть передано отладчику.
5.2 Объединение алгоритмов
Приведенные методы поиска ошибок общей памяти и ошибок инициализации разрабатывались таковым образом, чтоб они имели общую базу, которая бы дозволила уменьшить затратные расходы при работе отладчика. Таковой основой является расширенное дерево контекстов, т.к. при поиске ошибок общей памяти без вреда для метода можно употреблять конкретно его.
Струкутура Context в методе обнаружения ошибок инициализации содержит поля, обобщающие подобные поля структуры в другом методе. Но она содержит не все нужные другому методу поля. Потому объединенная структура Context содержит в себе последующее:
· номер соответственной контексту нити
· идентификатор критичной области
· огромное количество структур VarInfo, которые можно получить по адресу либо имени, обозначенному в качестве ключа.
· объект, определяющий тип хоть какой переменной в данном контексте.
структура VarInfo вне зависимости от типа переменной содержит поле init и имя переменной. Но, во время выполнения программки в структуры VarInfo может добавляться информация о чтении и записи, нужная для нахождения ошибок общей памяти.
Правила работы отладчика состоят из объединенных правил 2-ух алгоритмов.
В отладчике употребляется одно дерево контекстов для всех нитей, и любая нить может его видоизменять, при этом в согласовании с методами нить может обратиться к хоть какой верхушке, расположенной ввысь по дереву относительно текущей верхушки. Потому, чтоб исключить возможность возникновения ошибки общей памяти в самом отладчике, нужно воззвания к дереву заключать в критичные секции. Но описанные методы предполагают работу с деревом при любом воззвании к переменным, что приводит к возникновению весьма огромного числа критичных секций, а, как следует, больших затратных расходов. Это подтвердилось при тестировании, реализованного таковым образом отладчика, когда во время отладки программка замедлилась в сотки тыщ раз по сопоставлению с не инструментированной программкой.
Тестирование показало, что для заслуги применимой скорости работы отладчика нужно избавиться от всех конструкций синхронизации в местах, хороших от мест синхронизации в отлаживаемой программке. Потому последующие работы были ориентированы на модификацию алгоритмов с целью роста скорости работы программки.
5.3 Оптимизация отладчика
Главным моментом в оптимизации отладчика было устранение критичных секций в обработчиках чтения и записи переменных. Для этого была исключена какая-либо модификация родительских и расположенных выше по дереву вершин. Для выполнения данного ограничения, пришлось произвести последующие конфигурации в методах:
· При воззвании к переменным любая нить для обнаружения ошибок общей памяти обязана записывать конфигурации лишь в собственный контекст. Так же поле init быть может изменено лишь в собственном контексте.
· В любом месте, где размещается очевидная либо неявная директива barrier, основная нить группы собирает скопленную информацию каждой нитью во всех верхушках потомках родительской верхушки, т.е. в примыкающих верхушках. Опосля чего же происходит анализ собранных данных на предмет наличия ошибок общей памяти и сохраняет собранную информацию в родительский контекст, за ранее заменяя в этих данных номера примыкающих нитей на собственный. Данные в текущих контекстах нитей группы обнуляются. Для ошибок инициализации делается сбор инфы о полях init со всех примыкающих контекстах данной группы. Если для общей переменной находится хоть одно поле init со значением true, то это
Сохранение всех воззваний к переменным каждой нитью требуют огромных издержек памяти, потому реализованный отладчик хранит в перечнях ReadList и WriteList лишь 1-ый оператор, обратившийся к переменной в данном контексте. В итоге достигается значимая экономия памяти, но для каждой параллельной области находится лишь 1-ая пара операторов, создающих ошибку общей памяти при работе с данной переменной.
В целях роста производительности массивы представлены не в виде набора переменных, как единое целое. структура, описывающая массив содержит имя массива, его длину и набор структур, состоящих из тех же полей, что и VarInfo, кроме поля имени переменной. При этом количество структур в наборе равно длине массива.
Таковым образом, при первом же воззвании к одному элементу массива будет выделена память для данных сходу по всем элементам. Этот способ в неких вариантах наращивает Издержки по памяти, зато уменьшает время работы программки. Хотя в вариантах, когда нить в промежутке меж синхронизациями обходит массив полностью, то расход памяти при таковой организации меньше за счет того, что имя массива общее для всех частей.
5.4 Результаты тестирования
Для нахождения ошибок общей памяти, отладчику требуется, чтоб было, по последней мере, две нити в параллельной области. Потому тестирование проводилось на многопроцессорной системе с общей памятью IBM eServer pSeries 690 (Regatta). Для отладки была взята программка Jacobi, находящая приближенное решение уравнения Пуассона способом Якоби в двумерном случае.
Jacobi_org – программка без инструментации
Jacobi_dbg – программка с вызовом функций отладчика
Таблица 2: время выполнения программ
программка
2 нити
4 нити
8 нитей
Jacobi_org
5.748
2.958
1.496
Jacobi_dbg
5294
2794
2351
Необходимо подчеркнуть, что отладчик владеет не полной функциональностью, т.е. не были реализованы некие части алгоритмов, такие как обработка common-блоков, работа с threadprivate-переменными, также обработка директивы ORDERED и механизма замков. Все таки, приобретенное время выполнения программки близко к окончательному, потому что добавление обработки этих случаев не обязано очень воздействовать на производительность.
Из таблицы видно, что при отладке программка замедляется приблизительно в 900 раз при работе на 2-х и 4-х нитях. Это, непременно, мощное замедление, но, имеются способности существенного понижения затратных расходов, за счет сокращения обрабатываемой инфы.
Для демонстрации работы реализованного отладчика и сопоставления его с Intel Thread Checker`ом была взята та же самая программка Jacobi. Пуск выполнялся на одной и той же машине, обеспечивающей выполнение программки на 2 нитях.
Ниже приведен листинг корректной программки Jacobi. Обозначим его как Jacobi_correct.
1: PROGRAM
JAC
2: PARAMETER
(L=100)
3: REAL
A(L,L), EPS, MAXEPS, B(L,L)
4: external
omp_get_wtime;
5: double precision
omp_get_wtime;
6: DOUBLE PRECISION
sTime,eTime,dTime,st,et,dt;
7: INTEGER
ITMAX
8:
9: sTime = omp_get_wtime();
10:
11: ITMAX=1000
12:
13: !$OMP PARALLEL
14: !$OMP DO
15: DO
1 J = 1, L
16: DO
1 I = 1, L
17: A(I, J) = 0.
18: IF
(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THEN
19: B(I, J) = 0.
20: ELSE
21: B(I, J) = ( 1. + I + J )
22: ENDIF
23: 1 CONTINUE
24: !$OMP END PARALLEL
25:
26: st = omp_get_wtime();
27: DO
2 IT = 1, ITMAX
28: EPS = 0.
29: !$OMP PARALLEL DEFAULT (SHARED) PRIVATE (I,J) REDUCTION (MAX:EPS)
30: !$OMP DO
31: DO
21 J = 2, L-1
32: DO
21 I = 2, L-1
33: EPS = MAX ( EPS, ABS( B( I, J) — A( I, J)))
34: A(I, J) = B(I, J)
35: 21 CONTINUE
36: !$OMP DO
37: DO
22 J = 2, L-1
38: DO
22 I = 2, L-1
39: B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+
40: * A( I, J+1 )) / 4
41: 22 CONTINUE
42: !$OMP END PARALLEL
43:
44: et = omp_get_wtime();
45: dt = et — st;
46: st = et;
47: PRINT
200, IT, EPS, dt
48: 200 FORMAT
(‘IT = ‘,I4, ‘ EPS = ‘, E14.7,’ time = ‘,F14.6)
49: 2 CONTINUE
50:
51: eTime = omp_get_wtime();
52: dTime = eTime-sTime;
53: print
*, ‘time = ‘, dTime
54:
55: C 3 OPEN (3, FILE=’JAC.DAT’, FORM=’FORMATTED’, STATUS=’UNKNOWN’)
56: C WRITE (3,*) B
57: C CLOSE (3)
58: END
59:
Дальше описана модифицированная часть программки Jacobi, в которую были внесены ошибки для демонстрации работы отладчиков. Обозначим данный вариант как Jacobi_error.
30: init = 0
31:
32: !$OMP PARALLEL DEFAULT (SHARED) PRIVATE (I,J,i_test
)
33: C REDUCTION (MAX:EPS)
34: !$OMP DO
35: DO
21 J = 2, L-1
36: DO
21 I = 2, L-1
37: EPS = MAX ( EPS, ABS( B( I, J) — A( I, J)))
38: A(I, J) = B(I, J)
39: B(J,I)=A(J,I)
40: 21 CONTINUE
41:
42: i_test = init
43:
44: !$OMP DO PRIVATE(init)
45: DO
22 J = 2, L-1
46: DO
22 I = 2, L-1
47: B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+
48: * A( I, J+1 )) / 4
49: i_test = init
50: 22 CONTINUE
51: !$OMP END PARALLEL
При запуске программки Jacobi_correct оба отладчика ничего не отыскали.
Для программки Jacobi_error отладчик Inte Thread Checker (ITC) выдал диагностику, описанную в таблице 3.
Таблица 3: другими словами заключения о сути заболевания и состоянии пациента»>диагностика
программки Jacobi_error отладчиком Intel Thread Checker
Short description
description
count
Write -> Read data-race
Memory read at «Jacobi_err.F90»:37 conflicts with a prior memory write at «Jacobi_err.F90»:37 (flow dependence)
4686295
Write -> Write data-race
Memory write at «Jacobi_err.F90»:37 conflicts with a prior memory write at «Jacobi_err.F90»:37 (output dependence)
5727667
Read -> Write data-race
Memory write at «Jacobi_err.F90»:37 conflicts with a prior memory read at «Jacobi_err.F90»:37 (anti dependence)
1041372
Write -> Read data-race
Memory read at «Jacobi_err.F90»:37 conflicts with a prior memory write at «Jacobi_err.F90»:39 (flow dependence)
2400402
Write -> Read data-race
Memory read at «Jacobi_err.F90»:38 conflicts with a prior memory write at «Jacobi_err.F90»:39 (flow dependence)
2400717
Write -> Read data-race
Memory read at «Jacobi_err.F90»:39 conflicts with a prior memory write at «Jacobi_err.F90»:38 (flow dependence)
2401245
Read -> Write data-race
Memory write at «Jacobi_err.F90»:39 conflicts with a prior memory read at «Jacobi_err.F90»:38 (anti dependence)
2401283
Read -> Write data-race
Memory write at «Jacobi_err.F90»:39 conflicts with a prior memory read at «Jacobi_err.F90»:37 (anti dependence)
315
Read -> Write data-race
Memory write at «Jacobi_err.F90»:38 conflicts with a prior memory read at «Jacobi_err.F90»:39 (anti dependence)
321
смерти) программки Jacobi_error, выданная реализованным мной отладчиком (debugger), смотрится последующим образом.
(Jacobi_err.fdv:37 — Jacobi_err.fdv:37):variable eps — shared error(write-read)
(Jacobi_err.fdv:37 — Jacobi_err.fdv:37):variable eps — shared error(write-write)
(Jacobi_err.fdv:39 — Jacobi_err.fdv:37):array b — shared error(write-read)
(Jacobi_err.fdv:38 — Jacobi_err.fdv:39):array a — shared error(write-read)
Jacobi_err.fdv:49: variable init — init error
В таблице 4 приведены времена выполнения обрисованных программ для обоих инструментов (ITC, debugger), включая контрольный пуск программки без отладки (original).
Таблица 4: время выполнения программ в секундах.
original
debugger
ITC
Jacobi_correct
0,66
183
193
Jacobi_error
0,87
322
438
Заключение
В рамках проделанной работы были разработаны методы нахождения ошибок, обрисованных в постановке задачки, также на их базе сотворен отладчик, осуществляющий динамический контроль правильности OpenMP-программ, написанных на языке Fortran 77.
Общий размер начального кода разработанного отладчика составил около 4000 строк.
Было проведено тестирование, которое позволило оценить замедление скорости работы программки под управлением отладчика, а так же повышение размера потребляемой памяти. Добавочно реализованный отладчик был сравнен с имеющимся отладчиком Intel Thread Checker.
Для внедрения отладчика для настоящих производственных программ, которые нереально отлаживать на модельных начальных данных, требуется воплотить способы выборочного контроля, дозволяющие абсолютно уменьшить затратные расходы, сохранив высшую возможность обнаружения ошибок и их точную локализацию.
Литература
1. OpenMP Application Program Interface Version 2.5 May 2005 [PDF](HTTP://www.openmp.org/mp-documents/spec25.pdf)
2. Christian Terboven. Comparing Intel Thread Checker and Sun Thread Analyzer. 2007. [PDF](HTTP://www.fz-juelich.de/nic-series/volume38/terboven.pdf)
3. M. Suess, C. Leopold. Common mistakes in OpenMP and how to avoid them. 2006. [PDF](HTTP://www.michaelsuess.net/publications/suess_leopold_common_mistakes_06.pdf)
4. Sun Studio 12: Thread Analyzer User‘sGuide. 2007 [HTML,PDF](http://docs.sun.com/app/docs/doc/820-0619)
5. Intel Thread Checker 3.1 – Documentation. [PDF](HTTP://software.intel.com/en-us/articles/intel-thread-checker-documentation/)
]]>