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

(1,3)

4

(2,–)

5

(2,1)

6

(2,2)

7

(2,3)

8

(3,–)

9

(3,1)

10

(3,2)

11

(3,3)

12

Здесь в каждой клетке в первой строчке показаны значения индексов циклов (i,j), а во второй – соответствующий глобальный номер итерации. Запись (i,–) означает, что в момент начала итерации внешнего цикла внутренний цикл еще не активен.

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

Рассмотрим случай, когда некоторая ячейка массива A записывается на итерации (2, 2), а затем читается на итерации (2, 3). К моменту чтения состояние выполнения программы будет таким:

Цикл	Начало цикла	Текущая итерация	Буфер
i	1	5	1
j	6	8	7,6

Запись в ячейку массива имела GIN = 7. Это было на той же итерации внешнего цикла. Просмотрев буфер цикла по j, можно вычислить расстояние между записью и чтением, равное 1.

Теперь пусть запись производилась на итерации (1,1), а чтение на итерации (3,3). Состояние программы в момент чтения:

Цикл	Начало цикла	Текущая итерация	Буфер
i	1	9	5,1
j	10	12	11,10

Запись в массив (GIN = 2) произошла не в текущем цикле (2 < 10), а в объемлющем цикле (1 <= 2 <= 9). Просматривая буфер цикла по i в поисках итерации с GIN <= 2, мы определяем расстояние, равное 2.

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

3.4 Преимущества и недостатки динамического анализа

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

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