Для хранения во внутреннем представлении программы динамического анализатора информации о возможной зависимости из файла "posDepsInfo.txt" был создан специальный класс NeedLoopDep. Также был создан класс-хранилище объектов класса NeedLoopDep - NeedLoopDepStrg. Класс NeedLoopDepStrg содержит метод установки атрибута «флаг проверки» для объектов класса CCycleInfo (во внутреннем представлении динамического анализатора этот класс хранит информацию о цикле программы) и метод присваивания начального значения атрибуту «счетчик необходимости» для объектов класса CArrayInfo (во внутреннем представлении динамического анализатора этот класс хранит информацию о переменной программы). GlobalNeedLoopDeps - глобальный объект класса NeedLoopDepStrg, инициализируется информацией из файла "posDepsInfo.txt" при старте динамического анализа, и используется впоследствии для установки атрибута «флаг проверки» для объектов класса CCycleInfo, определения необходимых для анализа переменных для этого объекта, установки начального значения атрибута «счетчик необходимости» у объектов класса CArrayInfo.

Незначительные изменения коснулись методов заполнения базы данных САПФОР, комментариев, работы и числа параметров методов для некоторых классов из внутреннего представления динамического анализатора и т.д.

5.4 Программа сравнения баз данных

Программа сравнения баз данных реализована в среде разработки Microsoft Visual C++ 2008 Express Edition на языке программирования C++ и использует статическую библиотеку представления базы данных САПФОР.

Итак, пусть мы имеем программу program и два разных анализатора, соответствующие требованиям системы автоматизированного распараллеливания САПФОР, anlsr1 и anlsr2. В результате работы анализатора anlsr1(anlsr2) над программой program получаем базу данных САПФОР db1(db2).

Программа сравнения баз данных получает на вход две базы данных САПФОР одной программы db1 и db2, а на выходе:

1. Базу данных САПФОР answerDB, полученную из db1 путем корректирования возможных зависимостей информацией о реальных зависимостях базы данных САПФОР db2 по алгоритму описанному в пункте 4.4, если программа сравнения баз данных запущенна с флагом «-setTime», то в answerDB также фиксируются времена работы итераций циклов и программных единиц из db2.

2. Текстовый файл «compareDBs.txt» с описанием несоответствий между одинаковыми сущностями db1 и db2 и с описанием недостающих сущностей в db1(db2), которые присутствуют в db2(db1).

Любое несоответствие между одинаковыми сущностями двух баз данных описывается следующим образом:

Тип несоответствия < DataBase - первая база данных; описание сущности в первой базе данных >

< DataBase - вторая база данных; описание сущности во второй базе данных >

Например:

Routine name nonequivalence in < DataBase - my_test.db; FileID = 1; FileName = my_test.fdv; RoutineID - 1; RoutineName - jac; LineStart - 1; ParamsNumber - 0; >

< DataBase - my_test.fdv.db; FileID = 0; FileName = my_test.fdv; RoutineID - 0; RoutineName - program; LineStart - 1; ParamsNumber - 0; >

В примере отражено, что имена двух эквивалентных программных единиц (расположенных в одном файле, начинающихся с одного номера строки, имеющих одно и то же число параметров) в базах данных my_test.db и my_test.fdv.db одной программы отличаются.

Любое отсутствие сущности в базе данных описывается следующим образом:

Тип отсутствия < DataBase - база данных, в которой отсутствует сущность; описание места отсутствия сущности >

< DataBase - база данных, в которой наличествует сущность; описание сущности >

Например:

Variable absent in < DataBase - my_test.fdv.db; FileID - 0; FileName - my_test.fdv; RoutineID - 0; RoutineName - program; LineStart - 1; ParamsNumber - 0; >

< DataBase - my_test.db; FileID - 1; FileName - my_test.fdv; RoutineID - 1; RoutineName - jac; LineStart - 1; ParamsNumber - 0; VarID = 1; VarName = i; VarType = integer; VarDimentions = 0; >

В примере отражено, что в базе данных my_test.fdv.db нет описания переменной i целого типа нулевой размерности в программной единице program.

В таблице 1 описаны реализованные на данный момент типы несоответствий и отсутствий.

Таблица 1

Тестирование гибридного анализа проводилось на программах, использующих косвенную индексацию, сложные выражения, работу с данными, полученными в результате выполнения программы. Реализованные для гибридного анализа программы запускались на персональном компьютере (двуядерный процессор с частотой 2,21 ГГц, 1 Гб оперативной памяти) под управлением операционной системы Windows XP Service Pack 3.

Для демонстрации результатов рассмотрим ряд фрагментов программ на языке Fortran:

Фрагмент программы JACK (Рисунок 9):

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

Фрагмент программы с косвенной индексацией (Рисунок 10):

Для второго цикла доступ к элементу массива B осуществляется через элемент массива A. При статическом анализе мы не имеем никакой информации о значениях, хранящихся в переменных, следовательно, статический анализатор фиксирует возможную зависимость по переменной B для второго цикла. Частичный динамический анализ утверждает эту зависимость.

Фрагмент программы, в котором параметр цикла вводится пользователем во время ее выполнения:

Статические методы анализа не могут оценить параметр N, следовательно, фиксируется возможная зависимость. При частичном динамическом анализе проведем два теста:

1. введем N из диапазона 1 <= N <= 40

2. введем N > 40

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

Результаты тестирования гибридного анализа отражены в Таблице 2:

Таблица 2

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

Для реализации гибридного анализа понадобилось:

1. Разработать и реализовать алгоритм сбора информации в базе данных САПФОР о возможных зависимостях по данным между итерациями циклов.

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

3. Разработать и реализовать алгоритм коррекции одной базы данных САПФОР с использованием информации из другой.

Полученные программные реализации протестированы на реальных примерах и в будущем могут быть включены в качестве анализатора в систему автоматизации распараллеливания САПФОР. Общий объем разработанного программного кода превышает 7000 строк на языке Си++.