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

}

}

В этом примере оператор st2 может иметь контекст C(a) = (main f1 st1 proc f2 if1 st2). В случае наличия рекурсивной функции rfunc контекст мог бы быть таким: C(a) = (… rfunc st1 rfunc st1 rfunc …).

Цепочка векторов итераций (iteration vector chain) IVC(a) — это список номеров итераций для каждого узла-цикла контекста C(a). Если контекст не содержит циклов, то список не будет содержать ни одного элемента.

Цепочка векторов итераций относится к конкретному моменту выполнения программы, поэтому каждый оператор может иметь несколько разных IVC. Так, например, для оператора st2 может быть IVC(a) = (1, 4) или IVC(a) = (4, 1).

Виртуальная точка доступа a (virtual point) — это пара VP(a) = (C(a), IVC(a)).

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

Алгоритм нахождения прямых зависимостей.

Для каждой операции чтения ar:

Определить ячейку памяти, читаемую ar.

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

Найти контекст CL – длиннейший общий подпуть контекстов C(ar) и C(aw).

Найти контекст Cm – длиннейший контекст, являющийся подконтекстом контекста CL таким, что соответствующие цепочки IVC(ar) и IVC(aw) содержат одинаковые значения на отрезке, соответствующем контексту Cm.

Пусть r и w – векторы, образованные отрезками цепочек IVC(ar) и IVC(aw), не вошедшими в контекст Cm. Вычислить расстояние d = r – w, если dim(r)>0 и положить d=[] иначе.

Пусть f1 – самый «глубокий» цикл в контексте СL. Добавить зависимость между итерациями цикла f1 (и обрамляющих циклов) с расстоянием d.

Вместо п.6 можно записать зависимость между конкретными операторами в теле цикла. Пусть st1 и st2 – вершины C(ar) и C(aw), непосредственно следующие за CL. Добавить зависимость st1 от st2 с расстоянием d. Поскольку в данной работе рассматривается только распараллеливание циклов, в текущем анализаторе этого не делается.

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

3.3 Динамический анализ с использованием глобальных номеров итераций

Другой подход к динамическому анализу использует понятие глобальных номеров итераций (GIN – Global Iteration Number) [5]. Это означает, что все итерации всех циклов нумеруются по порядку. Например, в следующем примере

for (i=1; i<=3; i++)

for (j=1; j<=3; j++)

A[f1(i,j)]= ... A[f2(i,j)] ...;

глобальные номера итераций будут распределены следующим образом:

(1,–)

1

(1,1)

2

(1,2)

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