В самом начале программы вся статическая информация передается отладчику, который преобразует ее во внутренне представление, и возвращает ссылку на нее, которая будет использоваться для передачи отладчику описания соответствующего объекта при последующих вызовах интерфейсных функций.
Реализованный отладчик для корректной работы требует осуществления следующей инструментации:
· В начале программы должна быть вызвана функция инициализации отладчика 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: время выполнения программ
| программа | 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 оба отладчика ничего не нашли.