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

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

2.1 Зависимость по данным

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

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

1. в первом случае операторы S₁ и S₂ не имеют общих переменных или элементов массивов. Следовательно, зависимостей по данным между операторами нет.

2. во втором случае оба оператора S₁ и S₂ считывают значение A. При этом запись в Aне осуществляется, следовательно, зависимостей по данным между операторами также нет.

3. в третьем случае оператор S₁ записывает значение в A, а S₂ считывает А. Говорят, что между операторами S₁ и S₂ существует прямая зависимость по A.

4. в четвертом случае оператор S₁ считывает значение из A, а S₂ записывает в A. Говорят, что между операторами S₁ и S₂ существует обратная зависимость по A.

5. в пятом случае оба оператора S₁ и S₂ записывают значения в A. Говорят, что между S₁ и S₂ существует зависимость по выходу по A.

Теперь рассмотрим следующую ситуацию (Рисунок 3)

Рисунок 3

Мы имеем d тесно вложенных циклов. Для оператора S_v , содержащегося в теле этих циклов, вектором итераций I назовем номера итераций объемлющих циклов I = (I₁ ,…,I_d ). Далее, пусть есть зависимость по данным между операторами S_v и S_w с векторами итераций I'и I''. Предполагается, что векторы I'и I'' имеют одинаковую размерность, и их соответствующие элементы относятся к одним и тем же циклам программы. Шагом зависимости назовем вектор D = I'- I''. Тогда, между витками цикла существует зависимость по данным, если операторы S_v и S_w выполняются на разных итерациях цикла, то есть D ≠ 0 [2].

Зависимость по данным между двумя операторами требует сохранения их порядка следования в программе. Следовательно, если найдена зависимость по данным между итерациями цикла, то все его итерации должны выполниться последовательно, а это значит, что цикл распараллеливанию не подлежит. Иначе обстоит дело с циклами, между итерациями которых зависимостей не обнаружено, витки таких циклов могут одновременно выполняться на разных процессорах, что позволит увеличить эффективность выполнения программы на многопроцессорных ЭВМ.

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

3 Обзор

В рамках обзора рассмотрим принципы организации статического и динамического анализа последовательных программ, достоинства и недостатки этих методов, а также пример организации гибридного анализа.

3.1 Статический анализ. Принципы организации

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

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

Мы имеем d тесно вложенных циклов, n-мерный массив X и две функции f и g из Z^d в Z, где Z – множество всех целых чисел.

Для определения наличия зависимости между операторами S_v и S_w по переменной X, необходимо найти решение следующей системы уравнений:

1. для оператора S_v вектор итераций Ī' = (I'₁ , I'₂ ,…,I'_d )

2. для оператора S_w вектор итераций Ī" = (I"₁ , I"₂ ,…,I"_d )

3. Ī' ≤ Ī"

4. f_i (Ī') = g_i (Ī") для всех (1 <= i <= n) и для определенных I'₁ , I'₂ ,…,I'_d , I"₁ , I"₂ ,…,I"_d , таких что L_i <=I'_i <=U_i и L_i <=I''_i <=U_i .

Если решения системы нет, то зависимость между операторами S_v и S_w по переменной X отсутствует. Если решить систему уравнений невозможно, то статический анализ не может точно доказать наличие или отсутствие зависимости между операторами и фиксирует возможную зависимость. Это предположение гарантирует генерацию корректной параллельной программы, но связано с потерей эффективности из-за недостаточного использования параллелизма, в случае, если реальной зависимости в программе нет.

3.2 Недостатки и преимущества статического анализа

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

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

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