Также с помощью интерфейса осуществляется заполнение хранилищ информацией базы данных САПФОР и создание новой базы данных САПФОР по информации, содержащейся в хранилищах.
Основным свойством информации о зависимостях по данным, полученной в результате статического анализа текста программы, является безопасность. То есть, в спорных ситуациях, когда метод статического анализа не может доказать наличие или отсутствие зависимости, предполагается наличие зависимости. Именно для таких случаев в базе данных САПФОР введен способ фиксации возможных зависимостей по данным [10] (Тип зависимости VAR_DEP_POS в таблице depends базы данных говорит о возможном наличии зависимости по определенной переменной). Такая организация базы данных способствует проведению анализа программы сразу несколькими анализаторами, причем каждый следующий анализатор будет проводить анализ программы только для циклов, в которых обнаружена возможная зависимость по данным, и только для тех переменных, по которым возникла эта зависимость. Для проведения подобного анализа необходимо решить следующие проблемы:
1. Определить, какую информацию о цикле (о переменной) необходимо выделить из базы данных САПФОР, чтобы легко отличить в анализируемой программе данный цикл (переменную)
2. Разработать алгоритм частичного анализа программы, то есть, анализа зависимостей по интересующим нас переменным между витками интересующих нас циклов.
3. Разработать алгоритм сравнения двух баз данных САПФОР одной программы с последующим замещением неточной информации из первой базы данных на точную информацию из второй базы данных
Любой цикл программы однозначно определяется названием файла, содержащего цикл, и номером строки цикла в этом файле. А любая переменная программы однозначно определяется названием файла, содержащего программную единицу, в которой описана переменная, номером строки начала этой программной единицы в файле, а также именем, типом и размерностью переменной. Вся перечисленная информация содержится в базе данных САПФОР, следовательно, первая проблема сводится к получению необходимой информации из базы данных. Рассмотрим возможные решения второй и третьей проблемы в следующих пунктах.
В 2008 году Остапенко Г.Ю. в рамках дипломной работы разработал алгоритм динамического анализа последовательных программ, написанных на языке FORTRAN, соответствующий требованиям системы автоматизированного распараллеливания САПФОР, и на основе этого алгоритма программно реализовал динамический анализатор [5]. Доработаем динамический анализатор возможностью проведения частичного анализа программы.
Общая схема работы динамического анализатора показана на Рисунке 7.
1. исходный текст программы поступает на вход инструментатору
2. инструментатор вставляет в текст программы вызовы функций динамического анализатора
3. проинструментированная программа подаётся на вход стандартному компилятору Fortran
4. скомпилированная программа линкуется со статической библиотекой динамического анализатора, и на выходе получается исполняемая программа с вызовами динамического анализатора
5. исполняемая программа запускается на входном наборе данных. В ходе выполнения программы осуществляется её анализ
6. полученная при анализе информация об исходной программе помещается в базу данных системы САПФОР
В качестве инструментатора в динамическом анализаторе используется инструментатор FortranDVM/OpenMPпрограмм [8]. Этот инструментатор предоставляет для нужд динамического анализа информацию об объявлениях скалярных переменных и массивов, об обращениях к памяти переменных и массивов для чтения и записи, о начале, новой итерации и конце цикла, о местоположении цикла в программе и его параметрах, об объявлениях и вызовах функций и процедур, о формальных и фактических параметрах функций.
Обнаружение зависимостей по данным между итерациями циклов в динамическом анализаторе осуществляется по алгоритму, использующему дерево контекстов. Реализация этого алгоритма определила внутреннее представление программы - в виде дерева, которое хранится в памяти компьютера до конца анализа и отражает всю информацию о ходе выполнения программы.
Опишем указанный алгоритм:
Для каждой переменной (элемента массива) хранятся все её точки чтения и записи. При очередном доступе на чтение (на запись) выполняется следующий анализ:
1. определяем ячейку памяти, к которой происходит доступ на чтение ar (на запись aw1);
2. для каждой предшествующей записи в ячейку памяти aw(для каждого предшествующего чтения arи каждой предшествующей записи aw2) определяем виртуальную точу доступа VP(aw) (виртуальные точки доступа VP(ar) и VP(aw2));
3. находим контекст CL (контексты CLrи CLw) – длиннейший общий подпуть контекстов C(ar) и C(aw) (C(aw1) и C(ar), C(aw1) и C(aw2));
4. находим контекст Cm (контексты Cmrи Cmw) – длиннейший контекст, являющийся подконтекстом контекста CL (контекстов CLrи CLwсоответственно) таким, что соответствующие цепочки IVC(ar) и IVC(aw) (IVC(aw1) и IVC(ar), IVC(aw1) и IVC(aw2)) содержат одинаковые значения на отрезке, соответствующем контексту Cm (контекстам Cmrи Cmwсоответственно);
5. пусть rи w (w1, r, w2) – векторы, образованные отрезками цепочек IVC(ar) и IVC(aw) (IVC(aw1), IVC(ar), IVC(aw2) соответственно), не вошедшими в контекст Cm(Cmrи Cmw); вычислим расстояние зависимости как d = r – w (d1 = w1 – r, d2 = w1 – w2), если dim(r)>0 (dim(w1)>0) и положим d=[] (d1 = [] и d2 = []) иначе;
6. пусть f1 (frи fw) – самый «глубокий» цикл в контексте СL(CLrи CLw), добавим зависимость между итерациями цикла f1 с расстоянием d (между итерациями цикла frс расстоянием d1, и между итерациями цикла fw с расстоянием d2);
7. пусть st1 и st2 – вершины, соответствующие первому и второму доступу к памяти и непосредственно следующие за CL (CLrили CLw); добавить зависимость между операторами st1 и st2 с расстоянием d (d1 или d2).
Для построения дерева циклов программы, необходимого базе данных САПФОР, программные единицы тоже рассматриваются как циклы с одной итерацией. Поэтому любая зависимость по данным между операторами программы всегда будет рассматриваться в контексте объемлющего цикла. В базе данных САПФОР предусмотрено пять типов сложностей распараллеливания: редукционная зависимость, зависимость по собственной переменной между итерациями цикла, зависимость, связанная с неплановым завершением цикла (например, с помощью оператора перехода на оператор программы, находящийся вне цикла), зависимость по переменной между итерациями цикла, потенциальная зависимость по переменной между итерациями цикла. Рассмотренный выше алгоритм позволяет обнаруживать только реально существующие зависимости по переменным между итерациями цикла.
4.3.2 Алгоритм частичного динамического анализа
Расширим структуру, содержащую информацию о переменной во внутреннем представлении программы динамического анализа, добавлением атрибута «счетчик необходимости» целого беззнакового типа. Данный атрибут будет отвечать за необходимость обработки обращения к переменной при проведении частичного динамического анализа программы.
Расширим структуру, содержащую информацию о цикле во внутреннем представлении программы динамического анализа, добавлением атрибута «флага проверки» булевого типа и списка структур-переменных, необходимых для анализа в данном цикле. «Флаг проверки» будет отвечать за необходимость обработки обращений к структуре-переменной из списка необходимых для анализа в данном цикле структур-переменных при проведении частичного динамического анализа программы.
Алгоритм частичного динамического анализа:
Для облегчения повествования под переменной будем понимать структуру, содержащую информацию о переменной во внутреннем представлении программы динамического анализатора, а под циклом - структуру, содержащую информацию о цикле во внутреннем представлении программы динамического анализатора (Программная единица также рассматривается как цикл)
