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

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

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

Пример 31. В следующем операторе присваивания

A(I+B(J+2))=D(I-1,B(I))+3*A(1)-I+5

1 2 3 4     5 6 7 8    9 10

десять вхождений переменных (их номера проставлены снизу) – и только первое является генератором.

Конец примера.

Пример 32. В следующем выражении языка С

A = B++

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

       Конец примера.

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

Пример 33.

DO 99 I=1,100

 99 A(I)=D(I,I-1)+A(I-1)

В операторе с меткой 99 вхождения переменной A информационно зависимы, поскольку оба обращаются к ячейке памяти A(10): вхождение A(I) на десятой итерации, а A(I-1) - на одиннадцатой итерации цикла.

Конец примера.

Граф информационных связей – это ориентированный граф, вершины которого соответствуют вхождениям, а дуга соединяет пару вершин (v,u), если выполняется одно из следующих условий:

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

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

Генератор будем обозначать – out (output), а использование – in (input). Дуги графа информационных связей бывают трех типов в зависимости от инцидентных им вершин: out-in – истинная зависимость (true dependence), in-out – антизависимость (antidependence), out-out – выходная зависимость (output dependence) [20, с.95].

Если информационная зависимость связывает два использования, то мы будем говорить об in-in зависимости.

Пример 34.

DO 333 J=2, N

DO 333 I=2, N

A(I-2,J)=X(2*I-1)

c   v1      v2

X(2*I)=X(2*I+3)+A(I,J-1)

c  v3    v4       v5

X(2*I+1)=A(J,I-1)

c  v6        v7

333 X(2*I+2)=A(I+K,J)+A(I-2,J)

     v8            v9       v10

Выпишем список всех нетривиальных дуг графа информационных связей этого цикла:

(v1;v7), (v1;v9), (v1;v10), (v4;v6), (v5;v1), (v6;v2), (v7;v1), (v8;v3), (v9;v1)

Если до выполнения программы неизвестно, какое значение примет K к началу выполнения цикла, то и характер зависимости между вхождениями v1 и v9 нельзя определить. В этом случае в графе информационных связей должны быть проведены обе дуги между этими двумя вхождениями.

Пример 35. В следующем цикле дуга графа информационных связей ведет от первого вхождения A(I) ко второму, но не наоборот. А вхождения переменной X соединяются двумя дугами в обе стороны: дугой антизависимости, поскольку на каждой итерации сначала X используется в первом операторе тела цикла, а потом перезаписывается; дугой истинной зависимости, поскольку на каждой итерации, начиная со второй, используется значение X, полученное на предыдущей итерации.

     DO 99 I = 1, N

     A(I) = B+X

     X = A(I)

99 CONTINUE

Информационная зависимость между вхождениями называется циклически независимой (loop independent dependence), если эти вхождения обращаются к одной и той же ячейке памяти на одной и той же итерации цикла. Иначе зависимость называется циклически порожденной (loop carried dependence) [20, с.96].

В предыдущем примере дуга зависимости между вхождениями A(I) циклически независима, дуга зависимости между вхождениями X, ведущая сверху вниз, тоже циклически независима, а дуга, ведущая снизу вверх – циклически зависима. 

Пусть v1 и v2 – два вхождения массива X в тело цикла со счетчиком I, связанные информационной зависимостью. Информационную зависимость между v1 и v2 будем называть РЕГУЛЯРНОЙ относительно этого цикла, если разность индексных выражений вхождений v1 и v2 не зависит от счетчика цикла I.

При конвейеризации используется граф вычислений. Граф вычислений – это помеченный граф. Вершинами этого графа являются операции программы, метка – тип операции. Дуга соединяет операцию a с операцией b, если результат операции a используется операцией b. 

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

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

Очевидно, если графы вычислений двух программ изоморфны, как помеченные графы, то рассматриваемые программы эквивалентны.

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

Пример 36.

DO 99 I=1,N

99 X(2*I)=X(2*I+k)

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

       Конец примера.

Пример 37.

DO 333 I=1,N

333 A(I+2)=A(N-I)

c v1 v2

Для данного цикла список дуг графа имеет вид:

v1 – v2

v2 – v1

Конец примера.

Пример 38. В следующем цикле дуга графа информационных связей ведет от первого вхождения A(I) ко второму, но не наоборот. Вхождения переменной X соединяются двумя дугами в обе стороны: дуга антизависимости, поскольку на каждой итерации сначала X используется в первом операторе тела цикла, а потом перезаписывается; дуга истинной зависимости, поскольку на каждой итерации, начиная со второй, используется значение X, полученное на предыдущей итерации.

     DO 99 I = 1,N

     A(I) = B+X

     X = A(I)

99 CONTINUE

       Конец примера.

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

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

Скалярные переменные, которые не меняют своего значения в рассматриваемом фрагменте программы, называются внешними (по отношению к данному фрагменту).

6.1.3  Базовые понятия о преобразованиях программ

Преобразование программы – это замена одной программы другой программой.

       Преобразование фрагмента программы – это замена одного фрагмента другим фрагментом.

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

       Преобразование фрагментов будем называть эквивалентным, если соответствующее ему преобразование программ всегда эквивалентно. Аналогично, преобразование фрагментов будем называть корректным, если соответствующее ему преобразование программ всегда корректно.

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

       Далее под преобразованиями программ будем понимать преобразования фрагментов.

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