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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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