· идентификатор выражения в базе данных

· текстовое представление выражения

· постфиксное представление выражения

· список структур, каждая из которых содержит информацию об одночлене выражения, если данное выражение можно представить в линейном виде, иначе список пуст.

e. Структура, содержащая информацию об одночлене линейного выражения, заключает в себе:

· идентификатор одночлена в базе данных

· коэффициент при одночлене

· информацию о переменной одночлена

4. Хранилище информации о циклах программы, состоит из множества структур, каждая из которых содержит информацию о цикле

a. Структура, содержащая информацию о цикле, заключает в себе:

· идентификатор цикла в базе данных

· тип цикла (цикл или программная единица)

· номер строки начала цикла

· суммарное время выполнения итерации цикла

· информацию о переменной - итераторе цикла

· структуры, содержащие информацию о выражениях начала, конца и шага итератора

· идентификатор программной единицы базы данных, содержащей цикл

· признак тесной вложенности

· список структур, содержащих информацию о дочерних циклах

· список структур, содержащих информацию об операторах внутри цикла

· структуру, содержащую информацию об операторе самого цикла

· список структур, содержащих информацию о зависимостях по данным в цикле

· список структур, содержащих информацию о возможных зависимостях по данным в цикле

b. Структура, содержащая информацию об операторе, заключает в себе:

· идентификатор оператора в базе данных

· номер строки оператора

· список структур, каждая из которых содержит информацию о переходе на другой оператор

· список структур, каждая из которых содержит информацию о доступе к переменной в операторе

· список структур, каждая из которых содержит информацию о вызове функции в операторе

· список особенностей ввода/вывода для оператора

c. Структура, содержащая информацию о зависимости для цикла, заключает в себе:

· тип зависимости

· информацию о переменной зависимости

· тип редукции (для редукционной зависимости)

d. Структура, содержащая информацию о переходе на другой оператор, заключает в себе:

· идентификатор цикла, в который происходит переход

· идентификатор оператора, на который происходит переход

· номер строки оператора, на который происходит переход

· вероятность перехода

e. Структура, содержащая информацию о вызове функции в операторе, заключает в себе:

· идентификатор вызова функции в базе данных

· информацию о программной единице, вызов которой происходит в операторе

· список информаций о параметрах программной единицы

· список доступов к памяти для параметров данного вызова программной единицы

· список структур, каждая из которых содержит информацию о выражениях для параметров данного вызова программной единицы

f. Структура, содержащая информацию о доступе к переменной в операторе, заключает в себе:

· идентификатор доступа к переменной в базе данных

· информацию о переменной, к которой осуществляется доступ

· тип доступа к переменной

· список структур, содержащих выражения для размерностей массива в момент доступа, для переменной массива

Общая схема организации представления базы данных отражена на Рисунке 6. Пунктирные стрелки указывают на возможное использование элементами одного хранилища информации элементов другого, сплошные - на связь хранилищей с интерфейсом представления базы данных. Через интерфейс осуществляется создание, удаление и корректировка элементов хранилищей.

ИИ

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

Основным свойством информации о зависимостях по данным, полученной в результате статического анализа текста программы, является безопасность. То есть, в спорных ситуациях, когда метод статического анализа не может доказать наличие или отсутствие зависимости, предполагается наличие зависимости. Именно для таких случаев в базе данных САПФОР введен способ фиксации возможных зависимостей по данным [10] (Тип зависимости VAR_DEP_POS в таблице depends базы данных говорит о возможном наличии зависимости по определенной переменной). Такая организация базы данных способствует проведению анализа программы сразу несколькими анализаторами, причем каждый следующий анализатор будет проводить анализ программы только для циклов, в которых обнаружена возможная зависимость по данным, и только для тех переменных, по которым возникла эта зависимость. Для проведения подобного анализа необходимо решить следующие проблемы:

1. Определить, какую информацию о цикле (о переменной) необходимо выделить из базы данных САПФОР, чтобы легко отличить в анализируемой программе данный цикл (переменную)

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

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

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

В 2008 году Остапенко Г.Ю. в рамках дипломной работы разработал алгоритм динамического анализа последовательных программ, написанных на языке FORTRAN, соответствующий требованиям системы автоматизированного распараллеливания САПФОР, и на основе этого алгоритма программно реализовал динамический анализатор [5]. Доработаем динамический анализатор возможностью проведения частичного анализа программы.

Общая схема работы динамического анализатора показана на Рисунке 7.

1. исходный текст программы поступает на вход инструментатору

2. инструментатор вставляет в текст программы вызовы функций динамического анализатора

3. проинструментированная программа подаётся на вход стандартному компилятору Fortran

4. скомпилированная программа линкуется со статической библиотекой динамического анализатора, и на выходе получается исполняемая программа с вызовами динамического анализатора

5. исполняемая программа запускается на входном наборе данных. В ходе выполнения программы осуществляется её анализ

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

В качестве инструментатора в динамическом анализаторе используется инструментатор Fortran DVM/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).

Для построения дерева циклов программы, необходимого базе данных САПФОР, программные единицы тоже рассматриваются как циклы с одной итерацией. Поэтому любая зависимость по данным между операторами программы всегда будет рассматриваться в контексте объемлющего цикла. В базе данных САПФОР предусмотрено пять типов сложностей распараллеливания: редукционная зависимость, зависимость по собственной переменной между итерациями цикла, зависимость, связанная с неплановым завершением цикла (например, с помощью оператора перехода на оператор программы, находящийся вне цикла), зависимость по переменной между итерациями цикла, потенциальная зависимость по переменной между итерациями цикла. Рассмотренный выше алгоритм позволяет обнаруживать только реально существующие зависимости по переменным между итерациями цикла.

Расширим структуру, содержащую информацию о переменной во внутреннем представлении программы динамического анализа, добавлением атрибута «счетчик необходимости» целого беззнакового типа. Данный атрибут будет отвечать за необходимость обработки обращения к переменной при проведении частичного динамического анализа программы.

Расширим структуру, содержащую информацию о цикле во внутреннем представлении программы динамического анализа, добавлением атрибута «флага проверки» булевого типа и списка структур-переменных, необходимых для анализа в данном цикле. «Флаг проверки» будет отвечать за необходимость обработки обращений к структуре-переменной из списка необходимых для анализа в данном цикле структур-переменных при проведении частичного динамического анализа программы.

Алгоритм частичного динамического анализа:

Для облегчения повествования под переменной будем понимать структуру, содержащую информацию о переменной во внутреннем представлении программы динамического анализатора, а под циклом - структуру, содержащую информацию о цикле во внутреннем представлении программы динамического анализатора (Программная единица также рассматривается как цикл)

1. При регистрации новой переменной устанавливаем атрибут «счетчик необходимости» этой переменной в ноль.

2. При регистрации нового цикла, устанавливается «флаг проверки» этого цикла положительным, если цикл содержит возможные зависимости по переменным, в противном случае - отрицательным. Заполняем список необходимых для анализа переменных данного цикла, переменными, по которым существует возможная зависимость в данном цикле.

3. При входе в цикл, если «флаг проверки» цикла истинен, то у каждой переменной из списка необходимых для анализа переменных этого цикла «счетчик необходимости» увеличивается на единицу

4. При выходе из цикла, если «флаг проверки» цикла истинен, то у каждой переменной из списка необходимых для анализа переменных этого цикла «счетчик необходимости» уменьшается на единицу.

Страницы: 1, 2, 3, 4