В приведенном ранее описании алгоритмов показаны основные идеи, позволяющие обнаруживать искомые ошибки. На основе этих идей были реализованы алгоритмы в виде библиотеки функций динамического отладчика. А так же были проведены работы по модификации алгоритмов для увеличения производительности отладчика.

Отладчик разрабатывался на основе стандарта OpenMP версии 2.5 [1].

В качестве языка программирования для реализации отладчика был выбран язык C++. Благодаря своей выразительной мощности, высокой скорости работы и удобству использования этот язык подошел как нельзя лучше для поставленной задачи. К тому же не малую роль играет его совместимость с языком Fortran, на котором написаны отлаживаемые программы, непосредственно из которых вызываются функции отладчика.

Одно из важнейших условий для работы отладчика является правильное использование его интерфейсных функций, которые должны быть вызваны из отлаживаемой программы. За размещение этих вызовов отвечает специальная программа - инструментатор.

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

Реализованный отладчик для корректной работы требует осуществления следующей инструментации:

· В начале программы должна быть вызвана функция инициализации отладчика DBG_Init, до вызова каких-либо других его функций.

· должны быть вызваны функции, определяющие границы областей PARALLEL, SINGLE, CRITICAL, DO, SECTIONS, ORDERED. Дополнительно при входе в область PARALLEL должна быть вызвана функция DBG_ParallelEvent.

· после директивы BARRIER - вызов функции DBG_Barrier

· любое обращение к переменным или массивам должно быть обозначено вызовом соответствующей функции.

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

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

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

· определение threadprivate-переменных и common-блоков должно быть передано отладчику.

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

Струкутура Context в алгоритме обнаружения ошибок инициализации содержит поля, обобщающие аналогичные поля структуры в другом алгоритме. Но она содержит не все необходимые другому алгоритму поля. Поэтому объединенная структура Context включает в себя следующее:

· номер соответствующей контексту нити

· идентификатор критической области

· множество структур VarInfo, которые можно получить по адресу или имени, указанному в качестве ключа.

· объект, определяющий тип любой переменной в данном контексте.

Структура VarInfo вне зависимости от типа переменной содержит поле init и имя переменной. Однако, во время выполнения программы в структуры VarInfo может добавляться информация о чтении и записи, необходимая для нахождения ошибок общей памяти.

Правила работы отладчика состоят из объединенных правил двух алгоритмов.

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

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

Ключевым моментом в оптимизации отладчика было устранение критических секций в обработчиках чтения и записи переменных. Для этого была исключена какая-либо модификация родительских и расположенных выше по дереву вершин. Для выполнения данного ограничения, пришлось произвести следующие изменения в алгоритмах:

· При обращении к переменным каждая нить для обнаружения ошибок общей памяти должна записывать изменения только в свой контекст. Так же поле init может быть изменено только в своем контексте.

· В каждом месте, где располагается явная или неявная директива barrier, главная нить группы собирает накопленную информацию каждой нитью во всех вершинах потомках родительской вершины, т.е. в соседних вершинах. После чего происходит анализ собранных данных на предмет наличия ошибок общей памяти и сохраняет собранную информацию в родительский контекст, предварительно заменяя в этих данных номера соседних нитей на свой. Данные в текущих контекстах нитей группы обнуляются. Для ошибок инициализации производится сбор информации о полях init со всех соседних контекстах данной группы. Если для общей переменной находится хоть одно поле init со значением true, то это значение устанавливается во всех соседних контекстах, а так же в родительском контексте.

Сохранение всех обращений к переменным каждой нитью требуют больших затрат памяти, поэтому реализованный отладчик хранит в списках ReadList и WriteList только первый оператор, обратившийся к переменной в данном контексте. В результате достигается значительная экономия памяти, но для каждой параллельной области обнаруживается только первая пара операторов, создающих ошибку общей памяти при работе с этой переменной.

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

Таким образом, при первом же обращении к одному элементу массива будет выделена память для данных сразу по всем элементам. Этот метод в некоторых случаях увеличивает затраты по памяти, зато сокращает время работы программы. Хотя в случаях, когда нить в промежутке между синхронизациями обходит массив целиком, то расход памяти при такой организации меньше за счет того, что имя массива общее для всех элементов.

Для нахождения ошибок общей памяти, отладчику требуется, чтобы существовало, по крайней мере, две нити в параллельной области. Поэтому тестирование проводилось на многопроцессорной системе с общей памятью IBM eServer pSeries 690 (Regatta). Для отладки была взята программа Jacobi, находящая приближенное решение уравнения Пуассона методом Якоби в двумерном случае.

Jacobi_org - программа без инструментации

Jacobi_dbg - программа с вызовом функций отладчика

Таблица 2: время выполнения программ

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

Диагностика программы 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: Время выполнения программ в секундах.

Заключение

В рамках проделанной работы были разработаны алгоритмы нахождения ошибок, описанных в постановке задачи, а также на их основе создан отладчик, осуществляющий динамический контроль корректности OpenMP-программ, написанных на языке Fortran 77.

Общий объем исходного кода разработанного отладчика составил около 4000 строк.

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

Для применения отладчика для реальных производственных программ, которые невозможно отлаживать на модельных исходных данных, требуется реализовать методы выборочного контроля, позволяющие кардинально сократить накладные расходы, сохранив высокую вероятность обнаружения ошибок и их точную локализацию.