Динамический контроль корректности OpenMP-программ - Дипломная работа

Стандарт OPENMP[1] создавался для упрощения разработки параллельных программ для вычислительных систем с общей памятью, а так же для распараллеливания уже существующих последовательных программ. Стандартом определены специальные комментарии (команды препроцессору для C/C ) - директивы компилятору, непосредственно управляющие параллелизмом программы, вспомогательные функции, позволяющие создавать алгоритмы, ориентированные на параллельное выполнение, и переменные окружения, управляющие процессом выполнения параллельных областей. В начале ее выполнения создается одна нить, которая существует на протяжении всей программы. Группой нитей называется множество нитей, созданных при входе в данную параллельную область, включая породившую их нить, называемую главной.В этом случае возможны следующие ситуации: - все нити только читают переменную, тогда ошибки нет, т.к. значение переменной в любой момент времени остается неизменным. Когда какая-либо нить пытается прочитать значение переменной, то неизвестно, какое именно значение будет получено. Директива flush обновляет во всех нитях значения общих переменных, т.е. все нити будут видеть последние изменения. Поэтому, если использовать замки без директивы flush, то возможна ситуация, когда одна нить замок поставит, а другая не увидит никаких изменений, и будет считать, что ресурс свободен, и его можно захватить. Во время выполнения программы, данную ошибку невозможно отличить от ошибки, описанной в первом пункте.В традиционном подходе отлаживаемая программа запускается под управлением отладчика, который в любой момент может приостановить выполнение программы и выдать ее текущее состояние. Таким образом, пользователь может просматривать содержимое переменных и текущее положение в исходном коде, выполняя программу по шагам или расставляя контрольные точки. И на основании полученной информации, пользователь может определить причину некорректной работы программы.Цель дипломной работы - разработать и реализовать алгоритм динамического контроля корректности использования директив OPENMP в программах, написанных на языке Fortran.Задача инструмента, проводящего динамический контроль корректности OPENMP программы, состоит в том, чтобы находить в отлаживаемой программе некорректное использование директив, которое может привести к неправильному результату ее работы. Ошибки общей памяти возникают, когда несколько нитей одновременно и независимо друг от друга работают с одной и той же областью памяти, причем хотя бы одна из нитей модифицирует содержимое этой области.На данный момент существуют несколько коммерческих инструментов, осуществляющих динамический контроль корректности OPENMP программы. Рассмотрим отладчики Intel Thread Checker[5] и Sun Thread Analyzer[4]. Оба инструмента способны находить ошибки общей памяти и взаимной блокировки в программах, использующих не только OPENMP, но и другие разновидности параллелизма с общей памятью, например, нити POSIX. Для обнаружения ошибок общей памяти необходимо запускать программу на более чем одной нити, при этом в случае нахождения ошибки будет выдано только положение в исходном коде, а имя переменной, с которой связана эта ошибка, останется неизвестным. При этом в отлаживаемой программе должны отсутствовать вызовы функций работы с числом нитей, таких как omp_set_num_threads(), omp_get_num_threads(), omp_get_max_threads(), omp_get_thread_num(), и omp_get_num_procs().Сравнение приведенных отладчиков было проведено в Center for Computing and Communication RWTH Aachen University в Германии[2]. Intel Thread Checker и Sun Thread Analyzer запускались на нескольких программах с разными параметрами, для определения достоинств и недостатков этих инструментов. Наибольший интерес представляют полученные результаты замеров производительности отлаживаемых программ под управлением данных инструментов и без них, а так же количество потребляемой памяти. При этом инструменты тестировались на разных машинах с использованием разных компиляторов: Intel - запуск программы, скомпилированной компилятором Intel, без отладчика на 2 нитях. Intel Thread Checker - запуск программы на 2 нитях под управлением этого инструмента в зависимом от числа нитей режиме, т.к. алгоритмы SMXV и AIC используют функции для работы с числом нитей.Рассмотренные инструменты отладки, а именно Intel Thread Checker и Sun Thread Analyzer, с успехом могут быть использованы для отладки небольших программ.В этой главе описана схема работы отладчика, реализующего динамический контроль корректности OPENMP программы. Изначально имеется исходный код Fortran программы со вставленными директивами OPENMP. Отладчик скомпилирован в объектный файл, и имеет интерфейс в виде набора функций, которые должны быть вызваны в процессе работы отлаживаемой программы, при наступлении соответствующих событий, например, при обращении к памяти. При помощи специальной программы - инструментатора, в исходный код вставляются вызовы интерфейсных функций отладчика.Поскольку во время выполнения существуют несколько па

Оглавление

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 Представление критических областей 18

4.3.2 Описание алгоритма 20

4.4 Расширенное дерево контекстов 23

4.5 Обнаружение ошибок инициализации 24

5 Практическая реализация 27

5.1 Интерфейс отладчика 27

5.2 Объединение алгоритмов 28

5.3 Оптимизация отладчика 30

5.4 Результаты тестирования 31

Литература 38

1

Рассмотренные инструменты отладки, а именно Intel Thread Checker и Sun Thread Analyzer, с успехом могут быть использованы для отладки небольших программ. Однако, изза значительного увеличения объема потребляемых ресурсов во время отладки они становятся не применимыми для задач, работающих с большими объемами данных и производящими длительные вычисления. Для таких приложений требуется подбирать специальные входные данные, чтобы минимизировать потребляемые ресурсы. В некоторых случаях такой метод может быть не применим, например, когда объем требуемой памяти не сильно зависит от входных данных, или если программа получает на вход данные непосредственно от другого приложения.

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