Система автоматизации распараллеливания гибридный анализ (стр. 5 из 7)
1. При регистрации новой переменной устанавливаем атрибут «счетчик необходимости» этой переменной в ноль.
2. При регистрации нового цикла, устанавливается «флаг проверки» этого цикла положительным, если цикл содержит возможные зависимости по переменным, в противном случае - отрицательным. Заполняем список необходимых для анализа переменных данного цикла, переменными, по которым существует возможная зависимость в данном цикле.
3. При входе в цикл, если «флаг проверки» цикла истинен, то у каждой переменной из списка необходимых для анализа переменных этого цикла «счетчик необходимости» увеличивается на единицу
4. При выходе из цикла, если «флаг проверки» цикла истинен, то у каждой переменной из списка необходимых для анализа переменных этого цикла «счетчик необходимости» уменьшается на единицу.
5. При доступе к переменной (чтение или запись), если доступ происходит в цикле с утвердительным «флагом проверки» к переменной с положительным «счетчиком необходимости», то фиксируем его, в противном случае – нет.
При данном алгоритме, мы будем проводить анализ зависимостей по интересующим нас переменным в интересующих нас циклах и программных единицах.
4.4 Коррекция информации в базе данных САПФОР
Итак, пусть мы имеем программу program и два разных анализатора, соответствующие требованиям системы автоматизированного распараллеливания САПФОР, anlsr1 и anlsr2. В результате работы анализатора anlsr1(anlsr2) над программой program, получаем базу данных САПФОР db1(db2). Необходимо определить, какие из возможных зависимостей по переменным между итерациями циклов db1 являются реальными в db2, заменить возможные зависимости по переменным между итерациями циклов из db1 соответствующими реальными зависимостями из db2.
Для решения поставленной задачи воспользуемся представлением базы данных САПФОР, описанным в пункте 4.1.
Для упрощения повествования далее:
1. цикл – структура представления базы данных САПФОР, содержащая информацию о цикле
2. переменная – структура представления базы данных САПФОР, содержащая информацию о переменной
3. зависимость – структура представления базы данных САПФОР, содержащая информацию о сложностях распараллеливания программы, за исключением возможных зависимостей по переменным между итерациями цикла
4. возможная зависимость – структура представления базы данных САПФОР, содержащая информацию о возможной зависимости по переменной между итерациями цикла
Путь loop1 (loop2) – цикл, fileName1 (fileName2) - название файла, содержащего цикл loop1( loop2), lineNumber1 (lineNumber2) - номер строки цикла loop1 (loop2) в файле. Тогдацикл loop1 эквивалентен loop2, если fileName1 = fileName2 и lineNumber1 = lineNumber2.
Путь var1 (var2) – переменная, fileName1 (fileName2) - названиефайла, содержащегопрограммнуюединицу, вкоторойописанапеременная var1( var2), lineNumber1 (lineNumber2) - номерстрокиначалаэтойпрограммнойединицывфайле, name1(name2) – имяпеременной var1(var2), type1(type2) – типпеременной var1(var2), dims1(dims2) – размерностьпеременной var1(var2). Тогдапеременная var1 эквивалентна var2, если fileName1 = fileName2, lineNumber1 = lineNumber2, name1 = name2, type1 = type2 и dims1 = dims2 .
Далее, пустьrepres1(repres2) – представление db1(db2), loopsLst1(loopsLst2) – списокциклов, соответствующихпрограммнымединицам repres1(repres2), тогда:
1. Если loopsLst1 пуст, то завершаем вычисления, иначе для каждого цикла loop1из loopsLst1 ищем эквивалентный цикл loop2 из loopsLst2
2. Пусть posDepsLst1 – список возможных зависимостей из loop1, depsLst1(depsLst2) – список зависимостей из loop1(loop2)
3. Для каждой возможной зависимости dep1 по переменной var1 из списка posDepsLst1 ищем список реальных зависимостей tmpDepLst по переменной var2, эквивалентной var1, из списка depsLst2.
4. Если tmpDepLst не пуст, то дополняем список depsLst1 зависимостями из списка tmpDepLst и удаляем dep1 из posDepsLst1, иначе идем на пятый шаг.
5. Устанавливаем loopLst1(loopLst2) как список дочерних циклов цикла loop1(loop2), идем на шаг 1.
4.5 Общая схема работы гибридного анализа
Введем обозначения:
База данных статического анализатора – база данных системы САПФОР, полученная в результате анализа текста программы статическим анализатором.
База данных динамического анализатора – база данных системы САПФОР, полученная в результате динамического анализа выполнения программы, запущенной на определенных входных данных.
Общая схема работы гибридного анализа (Рисунок 8):
1. Текст исходной программы подается на вход статическому анализатору. На выходе получаем базу данных статического анализатора.
2. База данных статического анализатора подается на вход программе поиска возможных зависимостей. Программа поиска возможных зависимостей строит внутреннее представление базы данных статического анализатора на основе функций статической библиотеки организации представления базы данных, затем выделяет из представления информацию о возможных зависимостях по переменным между итерациями циклов и, наконец, выводит собранную информацию в файл «Файл возможных зависимостей».
3. Текст исходной программы подается на вход инструментатору. Инструментатор вставляет в текст программы вызовы функций динамического анализатора. Проинструментированная программа подаётся на вход стандартному компилятору Fortran. Скомпилированная программа линкуется со статической библиотекой динамического анализатора, и на выходе получается исполняемая программа с вызовами динамического анализатора. Полученная исполнительная программа запускается на некотором входном наборе данных. В ходе выполнения программы осуществляется её частичный динамический анализ с учетом информации из файла возможных зависимостей (при отсутствии файла или отсутствии информации внутри файла предполагается полный динамический анализ программы). Полученная при анализе информация об исходной программе помещается в базу данных динамического анализатора.
4. Базы данных статического и динамического анализаторов подаются на вход программе сравнения баз данных. Программа строит внутренние представления обоих баз данных на основе функций из библиотеки организации представления базы данных, далее, руководствуясь полезной информацией, записанной в базе данных динамического анализатора, корректирует внутреннее представление базы данных статического анализатора. На выходе программы сравнения баз данных получаем базу данных, сформированную на основе скорректированного внутреннего представления базы данных статического анализатора.
5 Описание практической части
В ходе практических работ были реализованы:
1. статическая библиотека функций организации и дальнейшей обработки представления базы данных САПФОР
2. программа поиска информации о возможных зависимостях по переменным между итерациями циклов из представления базы данных САПФОР
3. программа сравнения двух представлений баз данных САПФОР одной программы, с последующей коррекцией первого представления за счет полезной информации второго представления
также была доработана статическая библиотека функций динамического анализа возможностью проведения частичного анализа. Рассмотрим подробнее каждый из перечисленных элементов.
5.1 Статическая библиотека представления базы данных САПФОР
Статическая библиотека представления базы данных САПФОР реализована в среде разработки Microsoft Visual C++ 2008 ExpressEdition на языке программирования C++. Она содержит:
1. набор классов, каждый из которых описывает сущность базы данных САПФОР и включает методы доступа к информации этих сущностей и коррекции этой информации.
a. класс FileInfo описывает структуру, содержащую информацию о файле, изложенную в пункте 4.1.
b. класс RoutineInfoописывает структуру, содержащую информацию о программной единице, изложенную в пункте 4.1.
c. класс ArrayInfoописывает структуру, содержащую информацию о переменной, изложенную в пункте 4.1.
d. класс Monomописывает структуру, содержащую информацию об одночлене линейного выражения, изложенную в пункте 4.1.
e. класс Expressionописывает структуру, содержащую информацию о выражении, изложенную в пункте 4.1.
f. класс VariableAccesописывает структуру, содержащую информацию о доступе к переменной, изложенную в пункте 4.1.
g. класс CommonBlockInfo описывает структуру, содержащую информацию об общем блоке, изложенную в пункте 4.1.
h. класс ComBlockDefописывает структуру, содержащую информацию о конкретном описании общего блока, изложенную в пункте 4.1.
i. класс Dependence описывает структуру, содержащую информацию о сложности распараллеливания, изложенную в пункте 4.1.
j. класс LoopInfoописывает структуру, содержащую информацию о цикле, изложенную в пункте 4.1.
k. класс OperatorInfoописывает структуру, содержащую информацию об операторе, изложенную в пункте 4.1.
l. класс Branchописывает структуру, содержащую информацию о переходе на другой оператор, изложенную в пункте 4.1.
m. класс Callописывает структуру, содержащую информацию о вызове функции, изложенную в пункте 4.1.
2. Набор классов, каждый из которых описывает хранилище представления базы данных САПФОР и включает методы добавления и удаления элементов хранилища, доступа к элементам хранилища.
a. Класс FilesStorage описывает хранилище информации о файлах программы
b. Класс CommonBlocksStorage описывает хранилище информации об общих блоках программы
c. Класс RoutinesStorage описывает хранилище информации о программных единицах программы
d. Класс LoopsStorage описывает хранилище информации о циклах программы
3. Оновной класс InternalRepresentation, который включает методы инициализации хранилищей информацией базы данных САПФОР,методы доступа к хранилищам представления, методы создания и заполнения новой базы данных, основываясь на информации, содержащейся в хранилищах представления.
Стоит отметить, что, при инициализации хранилищей представления информацией базы данных САПФОР, проверяется ссылочная целостность базы данных САПФОР. Ссылочная целостность – это ограничение базы данных, гарантирующее, что ссылки между данными являются действительно правомерными и неповрежденными. Таким образом, если в базе данных САПФОР будет присутствовать некорректная информация, то в представление она не попадет.