|
p align="left">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 Express Edition на языке программирования 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, который включает методы инициализации хранилищей информацией базы данных САПФОР,методы доступа к хранилищам представления, методы создания и заполнения новой базы данных, основываясь на информации, содержащейся в хранилищах представления. Стоит отметить, что, при инициализации хранилищей представления информацией базы данных САПФОР, проверяется ссылочная целостность базы данных САПФОР. Ссылочная целостность - это ограничение базы данных, гарантирующее, что ссылки между данными являются действительно правомерными и неповрежденными. Таким образом, если в базе данных САПФОР будет присутствовать некорректная информация, то в представление она не попадет. 5.2 Программа поиска возможных зависимостей
Программа поиска возможных зависимостей реализована в среде разработки Microsoft Visual C++ 2008 Express Edition на языке программирования C++ и использует статическую библиотеку представления базы данных САПФОР. На вход программа получает базу данных САПФОР, на выходе файл с информацией о возможных зависимостях по данным между витками цикла «posDepsInfo.txt». Файл «posDepsInfo.txt» представляет собой набор строк вида: название_файла ; номер_строки_программной_единицы ; номер_строки_начала_цикла ; имя_переменной ; тип_переменной ; размерность_переменной; Таким образом, каждая строчка файла точно определяет цикл и переменную, по которой предполагается возможная зависимость между итерациями данного цикла. 5.3 Изменения, внесенные в статическую библиотеку функций динамического анализа
Статическая библиотека функций динамического анализа была пересобрана в среде Microsoft Visual Studio 2005. В этой же среде велась работа по изменению и дополнению некоторых функций библиотеки. Основных дополнений два: 1. При наличии в каталоге исполняемого файла непустого текстового файла "posDepsInfo.txt" будет проводится частичный динамический анализ программы в соответствии с алгоритмом, описанным в пункте 4.3.2. Иначе, если файл "posDepsInfo.txt" отсутствует или пуст, то проводится полный динамический анализ программы. 2. В динамический анализ добавлен механизм измерения времени работы итераций цикла и программных единиц без учета времени работы вложенных циклов. Эта информация необходима для заполнения базы данных САПФОР и раньше игнорировалась. Для хранения во внутреннем представлении программы динамического анализатора информации о возможной зависимости из файла "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 |
Тип несоответствия или отсутствия | Описание типа | | 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 для сравнения хранилищ представлений. Сравнения хранилищ можно производить независимо друг от друга. 5.5 Обзор результатов
Тестирование гибридного анализа проводилось на программах, использующих косвенную индексацию, сложные выражения, работу с данными, полученными в результате выполнения программы. Реализованные для гибридного анализа программы запускались на персональном компьютере (двуядерный процессор с частотой 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 | | |
6 Заключение
В данной работе исследованы методы статического и динамического анализа зависимостей по данным для последовательных программ. Разработан и реализован алгоритм гибридного анализа, объединяющий достоинства обоих методов. Для реализации гибридного анализа понадобилось: 1. Разработать и реализовать алгоритм сбора информации в базе данных САПФОР о возможных зависимостях по данным между итерациями циклов. 2. Разработать алгоритм частичного динамического анализа последовательной программы и реализовать его на базе уже существующей библиотеки функций динамического анализа 3. Разработать и реализовать алгоритм коррекции одной базы данных САПФОР с использованием информации из другой. Полученные программные реализации протестированы на реальных примерах и в будущем могут быть включены в качестве анализатора в систему автоматизации распараллеливания САПФОР. Общий объем разработанного программного кода превышает 7000 строк на языке Си++.
Страницы: 1, 2, 3, 4
| 
