1.6 Цель работы

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

2. Постановка задачи

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

Зависимость по данным образуют любые два оператора программы, обращающиеся к одной ячейке памяти, если хотя бы один из них производит запись в эту ячейку [3]. Существует 3 вида зависимостей по данным. Пусть s1 и s2 - операторы в программе, обращающиеся к одной ячейке памяти, и s2 выполняется после s1. Операторы s1 и s2 могут быть одним и тем же оператором программы. В зависимости от порядка чтения и записи используемой ячейки зависимости подразделяются следующим образом:

прямая зависимость (true dependence) - s1 записывает значение в ячейку памяти, а s2 считывает,

обратная зависимость (anti dependence) - s1 считывает значение, а s2 записывает,

зависимость по выходу (output dependence) - оба оператора s1 и s2 производят запись в ячейку.

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

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

Пусть есть зависимость по данным между операторами s1 и s2 с соответствующими векторами итераций i1 и i2. Предполагается, что векторы i1 и i2 имеют одинаковую размерность, и соответствующие их элементы соответствуют одним и тем же циклам программы. Расстоянием или шагом зависимости назовем вектор d = i2 - i1.

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

2.2 Система автоматизации распараллеливания

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

инструментатор / преобразователь программы,

анализатор,

экспертные модули по распараллеливанию программы,

модуль-ассистент, позволяющий пользователю работать с системой.

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

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

2.3 Задача анализатора

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

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

3. Динамический анализ

3.1 Схема работы динамического анализатора

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

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

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

Далее рассматриваются два возможных алгоритма динамического анализа.

3.2 Динамический анализ с использованием дерева контекстов

Эта схема анализа описана в работе [4] и в несколько измененном виде приводится здесь.

Введем следующую терминологию.

Дерево контекстов (context tree) CV(p) программы p -- дерево, состоящее из вершин следующих типов: функция, цикл, оператор вызова функции или доступа к памяти, условный оператор, и другие типы операторов, присутствующие в языке. Между двумя вершинами есть ребро, если одна из них непосредственно вызывает другую. Корень дерева - функция main(), основное тело программы или другое аналогичное понятие из используемого языка программирования.

Контекст -- это путь от корня до любой вершины дерева контекстов.

Пусть вершина S(a) соответствует оператору доступа к памяти a. Контекст CV(a) оператора a -- путь от корня дерева контекстов к вершине S(a).

Контекст функции (цикла) -- путь от корня дерева контекстов к вершине, соответствующей этой функции (циклу).

Рассмотрим пример.

int A[10], B[10];

void main() {

for (int i=0; i<10; i++)/* f1 */

proc(i);/* st1 */

}

void proc(int i) {

for (int m=0; m<10; m++) {/* f2 */

if (i%2 == 0)/* if1 */

A[m] = ...;/* st2 */

else

... = A[m];/* st3 */

B[m] = ...;/* st4 */

}

}

В этом примере оператор 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)] ...;

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

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

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

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

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