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

 

Программа сравнения баз данных реализована в среде разработки 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

Тип несоответствия или отсутствия	Описание типа
File absent in	файл отсутствует в
Common block absent in	общий блок отсутствует в
Routine absent in	программная единица отсутствует в
Routine name nonequivalence in	имена программных единиц не эквивалентны в
File contained routine absent in	название файла содержащего программную единицу отсутствует в
Variable type difference in	типы переменных не эквивалентны в
Variable attribut absent in	атрибуты переменных не эквивалентны в
Variable absent in	описание переменной отсутствует в
Routine parameters number nonequivalence in	число параметров программных единиц не совпадает в
Routine parameter in position absent	описание параметра в определенной позиции отсутствует
Routine parameter in position nonequivalence in	описания параметров в позиции не идентичны в
Common block definition nonequivalence in	описания общего блока не идентичны в
Common block definition absent in	описание общего блока отсутствует в
Loop absent	информация о цикле отсутствует в базе данных
Loop dependence absent in	зависимость в цикле отсутствует
Loop dependence absent nonequivalence in	зависимости по переменной в цикле не эквивалентны в
Loop iteration time nonequivalence in	итераторы цикла не совпадает в
Loop tightly inner nonequivalence in	флаг тесной вложенности у циклов различен в
Operator variable access nonequivalence in	доступы к переменной в операторе разнятся в
Operator variable access absent in	доступ к переменной отсутствует в
Operator call absent in	вызовы функции отсутствует в
Operator input/output mode absent in	идентификатор ввода/вывода отсутствует в

 

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

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

Обзор результатов

 

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

Примеры:	База данных статического анализа		База данных частичного динамического анализа	Модифицированная база данных
	Число возможных зависимостей	Число реальных зависимостей	Число утвержденных зависимостей	Число возможных зависимостей	Число реальных зависимостей
JACK	1	16	1	0	17
Косвенная индексация	1	0	1	0	1
Ввод параметра цикла	1	0	0	1	0
			1	0	1

 

Заключение

 

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

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

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

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

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

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