Но наряду с существенными недостатками в статическом методе анализа присутствует важная положительная особенность:

1. Безопасность анализа. Если в результате статического анализа программы было выяснено отсутствие зависимостей по данным между операторами, то такой зависимости действительно нет.

Идея динамического анализа заключается в определении зависимостей по данным в программе на основании информации, собранной в результате ее выполнения на тестовых наборах начальных данных [6]. Схематически это выглядит так (Рисунок 5):

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

2. Полученная программа подается на вход стандартному компилятору

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

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

Рассмотрим организацию динамического анализа зависимостей по данным с использованием дерева контекстов [6].

Введем ряд определений:

Определение 1: Контекстное дерево CT(program) программы program - дерево с тремя типами вершин: процедура, цикл или доступ к памяти. Две вершины контекстного дерева связаны ребром, если они непосредственно вложены друг в друга или если одна из этих вершин вызывает другую. Корень контекстного дерева - процедура, с которой начинает свое выполнение программа. Сложные программные выражения делятся на ряд контекстных вершин, по одной на каждое обращение к памяти.

Определение 2: Контекстом CT(program) назовем путь от корня дерева контекстов до любой его вершины. Пусть S(a) - контекстная вершина обращения к переменной `a'. Тогда, контекст C(a) обращения к `a' - это путь от корня дерева контекстов до вершины S(a). Контекст процедуры(цикла) - контекст, заканчивающийся соответствующей этой процедуре(циклу) вершиной. Процедурная секция - наибольший подпуть контекста C, содержащий единственную процедурную вершину, с которой он и начинается.

Определение 3: Цепочка векторов итерации IVC(a) доступа к памяти «a» - список векторов итераций, соответствующих всем процедурным секциям в контексте C(a) на момент доступа `a'. Если процедурная секция не содержит ни одного цикла, то вектор итераций будет пустым вектором.

Определение 4

Виртуальная точка доступа к памяти «a» - пара VP(a) = (C(a), IVC(a)).

Для определения прямых зависимостей по памяти в программе используется следующий алгоритм:

Для каждой ячейки памяти мы храним виртуальные точки последнего чтения и последней записи. Тогда, при каждом доступе к ячейке памяти на чтение ar производим следующие действия:

1. определяем ячейку памяти m, к которой происходит доступ ar;

2. получаем виртуальную точку VP(aw) последней записи aw в ячейку памяти m;

3. получаем по точкам доступа VP(aw) и VP(ar) значения цепочек векторов итераций IVC(aw) и IVC(ar);

4. определяем контекст CL, являющийся наибольшим общим подпутём контекстов C(aw) и C(ar) в дереве контекстов CT(p);

5. находим контекст Cm, являющийся наибольшим процедурным подконтекстом или подконтекстом цикла контекста CL, такой, что все его процедурные секции, кроме последней, имеют одинаковые значения векторов итераций в IVC(aw) и IVC(ar);

6. получаем по значениям цепочек IVC(aw) и IVC(ar) вектора итераций w и r последней процедурной секции контекста Cm; если размерность вектора r больше нуля, то определяем расстояние зависимости d: d = r - w, в противном случае полагаем d пустым вектором;

7. пусть вершина st1 следует сразу после подконтекста Cm в контексте C(aw), а вершина st2 следует сразу после подконтекста Cm в контексте C(ar), тогда добавим новую зависимость с расстоянием d между операторами st1 и st2.

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

Динамический метод анализа зависимостей по данным обладает рядом преимуществ над статическим:

1. При динамическом анализе обращения к переменным определяются по доступам к соответствующим ячейкам памяти. Это позволяет преодолеть трудности статического анализа, связанные с обработкой входных данных или данных, полученных в результате выполнения программы.

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

3. Динамический анализ всегда дает полную картину зависимостей для данного конкретного запуска программы.

4. Динамический анализ никогда не укажет на зависимость по данным там, где ее на самом деле нет.

Но наряду со всеми достоинствами в динамическом методе анализа имеют место несколько существенных недостатков [2]:

1. Динамический анализ показывает только те зависимости, которые возникают на данном конкретном запуске программы. При выполнении программы на других входных данных зависимости могут измениться. Нужно очень точно подбирать покрытие тестов.

2. Время работы. Нам необходимо запустить программу на каждом тесте, а их может быть довольно много.

Гибридный анализ - комбинация использования статического и динамического метода анализа зависимостей по данным с целью получения наиболее полной информации для эффективного распараллеливания программы.

В результате работы статического анализатора мы получаем два вида информации:

1. Информация о наличии зависимостей по данным

2. Информация о предполагаемых зависимостях по данным

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

Динамический анализ полностью лишен проблем статического анализа. Обращения к переменным определяются по доступам к соответствующим ячейкам памяти, а сложные выражения просто вычисляются. Кроме того, существует возможность инструментации трассировочными функциями (функциями, собирающими информацию о ходе выполнения программы для дальнейшего анализа на поиск зависимостей по данным) не всей программы, а определенных ее фрагментов. В этом случае в качестве результатов будут получены только зависимости по данным между операторами, попавшими в инструментированную часть программы.

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

Отсюда, получаем алгоритм гибридного анализа зависимостей по данным:

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

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

3. Корректируем информацию о зависимостях статического анализа информацией, полученной в результате динамического анализа.

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

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

Таблицы содержат информацию о некоторых сущностях, введенных для описания программы, результатов анализа, параметров и результатов распараллеливания. К основным сущностям относятся: файлы, программные единицы, циклы, переменные, имена и описания COMMON-блоков, выражения, операторы, вызовы подпрограмм, обращения к элементам массивов и т.д. Зачастую, информация о некоторой сущности разбита между таблицами базы данных. Например, чтобы собрать информацию о переменной var, скажем, программную единицу, в которой объявлена переменная, тип, размерность и атрибуты переменной, необходимо ознакомится с содержимым трех таблиц базы данных. Этот факт достаточно неудобен для организации дополнения базы данных новыми элементами, сравнения двух одинаковых элементов разных баз данных, или сбора информации об определенной сущности базы данных. Именно поэтому было решено создать представление базы данных, для которого будут справедливы следующие утверждения:

1. Представление базы данных должно иметь интерфейс для хранения и обработки всей информации из базы данных.

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

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

1. Хранилище информации о файлах программы

2. Хранилище информации об общих блоках программы

3. Хранилище информации о программных единицах программы

4. Хранилище информации о циклах программы

Рассмотрим каждое хранилище более подробно:

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

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

· имя файла

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

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

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

· название общего блока

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

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

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

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

· название программной единицы

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

· номер строки, с которой начинается программная единица

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

· число параметров программной единицы

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

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

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

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

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

· имя переменной

· тип переменной

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

· размерность переменной

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

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

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

· идентификатор описания общего блока в базе данных

· информацию о переменных, входящих в это описание общего блока.

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