Открытая распараллеливающая система

Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление

РАСПАРАЛЛЕЛИВАЮЩИЕ ПРЕОБРАЗОВАНИЯ ПРОГРАММ

Преобразования программ используются в оптимизирующих и распараллеливающих компиляторах и препроцессорах либо при ручной оптимизации кода. Целью преобразований является изменение качества программы: либо повышение быстродействия, либо уменьшение объема требуемой памяти, либо получение исходного текста на другом языке программирования (для последующего использования в какой-то программной среде).

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

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

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

Фрагменты преобразуемых программ будем записывать, используя, как правило, синтаксис языка ФОРТРАН. Но многие из преобразований без труда могут быть перенесены на программы языков ПАСКАЛЬ и С.

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

Использование программы OPSDemo / Преобразования программ / Графовые представления / Корректность преобразований / Информационная зависимость / Внутреннее представление
ОРС 2001-2006


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

Унификация оператора присваивания.

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

Канонизация сводится к формированию вместо одного оператора множественного присваивания эквивалентной последовательности операторов одинарного присваивания.

Пример 1.2.1:

a=b=c => b=c

a=b

Данное преобразование замедляет последовательное исполнение программы, так как один оператор выполняется быстрее последовательности операторов, то есть не всегда целесообразно. Но оно позволяет проводить анализ информационных зависимостей.

Так же реализовано разделение множественного присваивания, находящегося в аргументах оператора.

Пример 1.2.2:

1) for ( i=1;i <10; i=j=i+1) { …. } => for( i=1; i<10; i=i+1)

{ … ; j=i+1 }

2) for ( i=j=1;i <10; i=i+1) { …. } => j =1;

for( i=1; i<10; i=i+1) { … }

3)

j=a

if ( i=j=a) => if (i=a)

{ .. } { .. }

else else

{ .. } { .. }


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление

КОРРЕКТНОСТЬ ПРЕОБРАЗОВАНИЙ

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

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

В программе от оператора 1 к оператору 2 передается управление, если при некоторых входных данных в некоторый момент исполнения программы после оператора 1 следует оператор 2.

Управляющий граф программы – это граф, вершинами которого являются исполнимые операторы программы, а дуги – передачи управления.

Используются понятия ВХОД и ВЫХОД фрагмента программы. Под этими терминами понимаются передачи управления. При конкатенации операторов управление передается от предыдущего оператора к последующему. Условный оператор и оператор цикла имеют по две передачи управления.

Пример 1.

GOTO 999

999 X = 1

Пример 2. У фрагмента, состоящего из одного оператора 999 два входа:

IF BOOLEXPR THEN

A = 1

999 X = 1

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

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

Иногда будет использоваться понятие линейного участка программы. Это такой фрагмент, который состоит только из операторов присваивания и пустых операторов, который имеет единственный вход и единственный выход. Управляющий граф линейного участка – простой путь («линия»).

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

Пример 3.

1 GOTO 2

2 X = 1

3 Y = 2

4 Z = 3

В этом примере все операторы информационно независимы. Управление передается от каждого предыдущего оператора к последующему. Но операторы 3 и 4 можно менять местами, а операторы 1 и 2 – нельзя. Заметим, что перестановка операторов 1 и 2 приводит к программе синтаксически и семантически корректной, но не эквивалентной исходной. По этой причине иногда приходиться оговаривать, какие именно операторы входят в рассматриваемый фрагмент.

Поскольку преобразования в ОРС выполняются во внутреннем представлении, которое имеет структуру дерева, некоторые условия корректности выполняются автоматически.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление

Преобразования циклов

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

Канонизация циклов
Развертка цикла
Расщепление цикла
Расщепление вершин (Введение временных массивов)
Растягивание скаляров (Замена переменной массивом)
Слияние циклов
Перестановка заголовков циклов
Разрыв итераций и гнездование цикла
Переименование скалярных переменных
Канонизация условного оператора
Канонизация оператора присваивания
Подстановка вперед


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

Раскрутка и развертка циклов

РАЗВЕРТКА ЦИКЛА.

Развертка цикла кратности h заменяет цикл

DO 999 I = 1, N

999 ТЕЛОЦИКЛА(I)

следующим фрагментом программы

DO 888 I = 1, N, h

ТЕЛОЦИКЛА(I)

ТЕЛОЦИКЛА(I+1)

........................

888 ТЕЛОЦИКЛА(I+h-1)

N2 = N mod h //остаток от деления числа N на h.

DO 777 I = N-N2+1, N

777 ТЕЛОЦИКЛА(I)

Если N константа и делится нацело на h, то второй цикл и стоящий перед ним оператор присваивания можно опустить.

Если N константа и не делится нацело на h, то ко второму циклу полученного фрагмента программы можно применить раскрутку цикла (о раскрутке речь пойдет далее).

Метка последнего оператора тела цикла должна остаться только у оператора последней копии тела цикла. Если ТЕЛОЦИКЛА(I) содержит помеченные операторы, то в копиях тела цикла метки должны вводиться новые (вместе со ссылками на эти метки). Ввиду этого требования удобно, чтобы последним оператором тела цикла был CONTINUE и, чтобы не было без необходимости помеченных операторов.

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

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

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

РАСКРУТКА ЦИКЛА.

Раскрутка цикла заменяет цикл

DO 999 I=1,N

999 ТЕЛОЦИКЛА(I)

на следующий фрагмент программы

ТЕЛОЦИКЛА(1)

ТЕЛОЦИКЛА(2)

........................

ТЕЛОЦИКЛА(N)

I = N

Границы цикла должны быть константами (в частности, значение N в данном цикле должно быть известно на этапе трансляции).

Если ТЕЛОЦИКЛА(I) содержит помеченные операторы, на которые указывают goto, то в копиях тела цикла метки должны вводиться новые. В упрощенном варианте раскрутку можно применять лишь для циклов, в теле которых не содержаться помеченные операторы, на которые указывают goto.

Счетчику цикла следует присвоить значение последней итерации.

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

Для реализации раскрутки цикла можно сначала сделать развертку кратности N, а затем удалить заголовок цикла.

Теорема. Раскрутка цикла всегда является эквивалентным преобразованием.

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление

ИНФОРМАЦИОННАЯ ЗАВИСИМОСТЬ В ПРОГРАММЕ

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

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

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

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

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

Пример 2.

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).

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

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

Пример 3.

DO I=1,N

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

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

Пример 4.

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 нельзя определить. В этом случае в графе информационной зависимости должны быть проведены обе дуги между этими двумя вхождениями.

Пример 5.

DO 333 I=1,N

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

c v1 v2

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

v1 - v2

v2 - v1

Пример 6. В следующем цикле дуга графа информационных связей ведет от первого вхождения 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)

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

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

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

Приведение выражений к стандартному виду
Подстановка вперед


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

КАНОНИЗАЦИЯ ЦИКЛОВ

Данное преобразование заменяет всякий цикл равносильным, у которого левая граница счетчика цикла равна 1 и шаг цикла тоже равен 1. Иногда используется термин «нормализация» (do-loop normalization) Это преобразование применимо к любому оператору цикла

DO 99 I=L, N, h

99 ТЕЛОЦИКЛА(I)

и заменяет его оператором цикла

DO 99 J=1, (N-L+1)//h

99 ТЕЛОЦИКЛА(h*(J-1)+L)

Здесь // означает операцию целочисленного деления. Таким образом, канонический вид цикла - это цикл, у которого левая граница и шаг цикла равны 1. К описанным требованиям канонического вида цикла можно добавить еще одно: последний оператор тела цикла должен быть CONTINUE.

Алгоритм выполнения канонизации состоит в следующем:

1) сгенерировать новую переменную (обозначим ее J) для имени нового счетчика цикла.

2) Всюду в теле цикла заменить старый счетчик цикла I на выражение (h*(J-1)+L). Для выполнения этого преобразования можно использовать подстановку вперед.

3) В заголовке цикла левая граница заменяется числом 1, а правая - (N-L+1)//h.

4) Если последний оператор тела исходного цикла не CONTINUE, то надо этот оператор (CONTINUE ) приписать в конце цикла со сгенерированной новой меткой и эту же метку указать в заголовке цикла.

Теорема. Всякий цикл языка ФОРТРАН может быть приведен к каноническому виду и это преобразование эквивалентно.

Доказательство этой теоремы конструктивно и сводится к применению описанного выше алгоритма приведения к каноническому виду.

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

2’) В теле цикла первым оператором поставить присваивание

I = (h*(J-1)+L).

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

Канонический вид цикла допускает вариации, в зависимости от дальнейших преобразований. Следует отметить, что для некоторых преобразований удобно иметь цикл, у которого начальное значение счетчика (левая граница) равно 0. Иногда перед циклом и после цикла добавляются пустые операторы, которые перехватывают передачи управления, ведущие на заголовок цикла и выходящие из цикла соответственно.

Унификация операторов циклов, подобных оператору DO языка Фортран.

К этому типу относятся оператор DO в Фортране, оператор FOR в Паскале и оператор For в языке С.

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

Каждый оператор цикла имеет следующий набор полей:

- имя счетчика цикла

- левая граница

- правая граница

- шаг

- метка последнего оператора тела цикла

- идентификатор следующего по тексту оператора

- признак того, что данный цикл является вложенным в гнездо циклов

- признак того, что данный цикл является объемлющим для гнезда циклов

- признак канонизирован цикл или нет.

- признак можно распараллелить данный цикл или нет

- идентификатор следующего по выполнению оператора.

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

Пример 1.3.1:

DO 99, I=L, N, h

99 ТЕЛОЦИКЛА(I)

заменяем на оператор

DO 99, J=1,(N-L+1)//h

99 ТЕЛОЦИКЛА(h*(J-1)+L)

Здесь // - целочисленное деление.

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

Пример 1.3.2:

for ( int i=1 ; i<10;i=i+h) {..} => for (int i = 1; i <= 10-h ; i=i+h)


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

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

ГРАФ ВЫЧИСЛЕНИЙ

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

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

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

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

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

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

Вхождения переменных

Пусть X – переменная в программе. Вхождением переменной X будем называть всякое появление этой переменной в тексте программы. Если вхождение v находится в операторе присваивания Stmt, то будем говорить, что вхождение v принадлежит оператору Stmt и писать «v Î Stmt».

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

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

A[B[i+1]]=C[2*i-2]+A[i+2];

v1 v2 v3 v4 v5 v6 v7

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

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

Рассмотрим гнездо из n вложенных друг в друга циклов. Занумеруем операторы циклов в этом гнезде в соответствии с порядком вложенности, начиная с самого внешнего цикла. Обозначим счетчик i-го цикла – Ii. Будем писать v[I'1, I'2, … I'n] (или v[I'], где I=(I'1, I'2, … I'n)) чтобы сослаться на вхождение v при значениях счетчиков циклов I1=I'1, I2=I'2, … In=I'n.

Определение. Множество значений, которые может принимать счетчик циклов I=(I1, I2, …, In) в указанном гнезде, называется пространством итераций данного гнезда. Для программ из линейного класса пространство итераций может быть описано как все целые точки, содержащиеся в некотором выпуклом многограннике. Этот многогранник называется линейным пространством итераций.

Информационная зависимость

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

Пример 3. В следующем фрагменте программы

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

v

u
x[i]= x[i-1]+y[i];

имеется зависимость вхождения v от u т.к., например, к ячейке памяти x(5) обращается сначала вхождение u на итерации 5, а затем вхождение v на итерации 6.

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

Определение. Пусть вхождение v зависит от вхождения u. В зависимости от типов вхождений (генератор, использование) различают четыре типа зависимости:

1. если u является генератором, а v – использованием, то зависимость такого типа называется истинной (true dependence) или потоковой зависимостью (flow dependence);

2. если u является использованием, а v – генератором, то зависимость такого типа называется антизависимостью (antidependence);

3. если u и v являются генераторами, то зависимость такого типа называется выходной зависимостью (output dependence) или зависимостью по выходу;

4. если u и v являются генераторами, то зависимость такого типа называется входной зависимостью (input dependence) или зависимостью по входу.

Пусть два вхождения u и v имеют d общих циклов.

Определение. Вхождение u зависит от вхождения v с носителем k (1£k£d), если существуют такие итерации I=(I1, I2, …, In1) и J=(J1, J2, …, Jn2), что:

1. v[J] зависит от u[I];

2. Ii = J i, для всех 1£i£k-1,

3. Ik < J k.

Определение. ([1, с. 100]) Зависимость вхождения u от вхождения v называется циклически независимой (loop independent dependence), если существуют такие итерации I=(I1, I2, …, In1) и J=(J1, J2, …, Jn2), что:

1. v[J] зависит от u[I];

2. Ii = J i, для всех 1£i£d.

В противном случае, такая зависимость называется циклически порожденной (loop carried dependence).

Граф информационных зависимостей

Граф информационных зависимостей – ориентированный помеченный граф. Вершины графа – вхождения переменных. Если вхождение v зависит от вхождения u, то в графе существует дуга, направленная от u к v. Обычно, с каждой дугой графа связывается некоторая дополнительная информация о зависимых вхождениях, такая как носитель (глубина) зависимости, вектор направления зависимости, вектор расстояния зависимости и др.

Построение графа информационных зависимостей

Для построения графа информационных зависимостей, необходимо:

1. выделить фрагмент программы, для которого нужно построить граф;

2. на вкладке «Graphs», в поле список выбрать «Dependence»;

3. нажать на кнопку «Build Graph».

При этом граф будет построен с помощью неравенств Банержи и НОД [1] теста, которые используются для тестирования информационной зависимости между парами вхождений. Этому режиму построения соответствует режим «None (Banerjee, GCD)» группы «Refine».

С помощью группы «Refine» можно выбрать альтернативный режим построения графа:

  • «Elem Lattices», в этом режиме для тестирования информационной зависимости между парами вхождений используется элементарный снизу решетчатый граф [2];
  • «Below Lattice», в этом режиме при построении графа зависимостей используются минимальные снизу решетчатые графы [2]; в этом режиме, в частности, устраняются ложные потоковые и выходные зависимости [3];
  • «Value Lattice», в этом режиме при построении графа используется абстракция зависимости по значению [3] (для построения также используются минимальные решетчатые графы).

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

Фрагмент программы должен принадлежать линейному классу программ [2]. Также, для достижения максимальной точности, программа не должна содержать внешние переменные [2] и условные операторы.

Литература.

1. Аллен Р., Кеннеди К. Автоматическая трансляция Фортран-программ в векторную форму. Векторизация программ: теория, методы, реализация. Сб. статей. Москва: Мир. 1991. С.77 ‑ 140.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург «БХВ-Петербург» 2002.

3. Pugh W., Wonnacott D. Going beyond integer programming with Omega test to eliminate false data dependences.// Technical Report CS-TR-2993, Dept. of Computer Science, University of Maryland, Collage Park, December 1992. An earlier version of this paper appeared at the SIGPLAN PLDI’92 conference.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

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

Определение элементарного (снизу) решетчатого графа

Рассмотрим гнездо из n вложенных друг в друга циклов. Занумеруем операторы циклов в этом гнезде в соответствии с порядком вложенности, начиная с самого внешнего цикла. Обозначим счетчик i-го цикла – Ii. Будем писать v[I'1, I'2, … I'n] (или v[I'], где I=(I'1, I'2, … I'n)) чтобы сослаться на вхождение v при значениях счетчиков циклов I1=I'1, I2=I'2, … In=I'n.

Определение. Множество значений, которые может принимать счетчик циклов I=(I1, I2, …, In) в указанном гнезде, называется пространством итераций данного гнезда.

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

· вершины графа – объединение множеств V1 и V2;

· дуга направлена из вершины I ÎV1 в вершину J ÎV2, если выполнено:

а) u[I] и v[J] обращаются к одной ячейке памяти;

б) запись u[I] выполняется раньше, чем чтение v[J];

г) не существует такой записи u[K], которая происходит после записи u[I], но перед чтением v[J], которая перезаписывает значение, записанное u[I].

Решетчатый граф обладает следующим свойством: в каждую вершину входит не более одной дуги. Пусть H – множество вершин решетчатого графа, в которые входят дуги (HÌV2). Тогда решетчатый граф может быть описан функцией F, определенной на множестве H, которая вершине J ÎH ставит в соответствие начальную вершину I ÎV1 единственной дуги входящей в J. В общем случае, функция F является кусочной. Поэтому функцию F представляют в виде набора функций Fk (k=1..s), которые определены на подмножествах Hk (k=1..s) пространства итераций V2.

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

· функции имеют вид I=A*J+b, где А – числовая матрица, b – вектор;

· функции заданы на всех целых точках некоторых выпуклых линейных многогранников;

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

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

Фрагмент программы должен принадлежать линейному классу программ [1]. Также программа не должна содержать внешние переменные [1] и условные операторы.

Литература.

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург «БХВ-Петербург» 2002.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

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

Граф операций

Обозначим через OP – множество операций (чтения данных, записи данных, арифметические операции) некоторого фрагмента программы. Обозначим через OP(S) – множество операций (чтения данных, записи данных, арифметические операции) некоторого оператора S.

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

Определение 1: Опорным пространством операции будем называть пространство итераций цикла, которому принадлежит оператор, который содержит эту операцию.

Обозначим через PI(o) опорное пространство операции o.

Определение 2: Графом оператора S будем называть ориентированный граф, множество вершин которого представляют собой множество
V = { (o, I), o Î OP(S), I Î PI(o) }, а дуги соединяют такие вершины (x, I ) и
(y, I ), что результат операции x, выполненной на итерации I, является аргументом операции y, выполняемой на итерации I.

Пример 1

Do 10 k=1,P

10 C[1,2] = C[1,2]+A[1,k]*B[k,2]

Граф единственного оператора в этом цикле изображен на рисунке 1.

Рис. 1

Рассмотрим пару операторов S1 и S2 (необязательно различных) и пару вхождений u Î S1 и v Î S2, из которых v – генератор, u – использование и они связаны истинной зависимостью. Построим граф являющийся объединением графов операторов S1 и S2. Обозначим его G.

В вершины, соответствующие генератору v, входит только одна дуга. Обозначим через x операцию, результат которой записывается в генератор v, а значит, дуги, которые входят в вершины соответствующие v, имеют вид:
(x,I )–>(v,I ).

Из вершин, соответствующих использованию u, выходит только одна дуга. Обозначим через y операцию, которая получает в качестве аргумента результат чтения данного использованием u. Дуги, которые выходят из вершин, соответствующих u, имеют вид: (u,I )–>(y,I ).

Рассмотрим элементарный решетчатый граф для вхождений u и v. Для всех итераций I и J, для которых существует дуга I –>J в этом графе, построим дугу в графе G: (x,I )–>(y,J ). Множество всех таких дуг для всех пар вхождений, связанных истинной зависимостью в этом фрагменте программы, обозначим D.

Для всех итераций I и J, для которых существует дуга I –>J в элементарном решетчатом графе для вхождений u и v, множество дуг в графе G, имеющих вид: (u,I )–>(y,J ) обозначим F, а вершины являющиеся их началами E.

Определение 3: Графом операций фрагмента программы будем называть ориентированный граф, являющийся объединением всех графов операторов входящих в этот фрагмент программы, с добавлением множества дуг D, удалением дуг F и их начальных вершин E.

Пример 2

Do 10 i=1,N

Do 10 k=1,P

Do 10 j=1,M

10 C[i,j] = C[i,j]+A[i,k]*B[k,j]

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

Заметим, что в случае тесного гнезда циклов, множество V совпадает с множеством OP ´ PI ввиду того, что пространства итераций всех операторов в тесном гнезде циклов совпадают.

Рис. 2

Свернутый граф операций

Определение 4: Свернутым графом операций будем называть ориентированный граф, вершины которого представляют собой множество OP – операций цикла, а дуги соединяют такие вершины x и y, что результат операции x, хотя бы на одной итерации цикла, является аргументом операции y, на некоторой итерации цикла. Каждой дуге u = (x, y) поставлена в соответствие функция Fu, которая задает элементарный решетчатый граф, построенный для пары вхождений соответствующих паре операций x и y.

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

Используя информацию, которую дает свернутый граф операций, можно построить расписание для таких архитектур как VLIW и потоков данных. Тем самым, свернутый граф операций дает возможность расширить класс программ, для которых эффективно строится расписание, но ни в коем случае не становиться заменой для РГА.

В ОРС свернутый граф операций находится в стадии разработки. Его основная информационная компонента – решетчатый граф – уже реализован.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Граф информационных зависимостей
Решетчатый граф
Граф вычислений
Граф операций


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление

Использование программы OPS Demo

Функциональные части программы

  • Левая панель
    • Инструмент для выделения фрагментов исходного кода
  • Правая панель
    • Вкладка «Библиотека преобразований» (Transformations)
    • Вкладка «Графы» (Graphs)
  • Панель инструментов

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

    • - открыть менеджер примеров.
    • * - разобрать текущий открытый документ во внутреннее представление
    • - вызов справки по программе
  • Служебная панель
    • Окно активной подсказки (Tips)
    • Окно сообщений системы (Log)

Использование программы

Предлагается пример построения решетчатого графа:

  • Выбираем интересующую нас функциональную часть программы (вкладки справа в основном окне программы). Например, граф “Lattice” (“Решетчатый”):

  • Нажмите кнопку [image] (менеджер примеров) на панели инструментов:

  • В появившемся окне выберите один из предлагаемых для данного случая примеров (“l.c”) и нажмите кнопку “Load”:

  • Открывшийся в виде текста пример теперь нужно преобразовать во внутреннее представление. Для этого нажмите кнопку Transform:

    • Теперь пример разобран во внутреннее представление и имеется возможность выделять мышью участки программы. Выделим левой кнопкой вхождение-источник, а правой – вхождение-назначение:

    • И нажмите кнопку “Build Graph”:

В окна справа вы видите построенный решетчатый граф для данного примера.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

Унификация условных операторов.

Унификация условных операторов подразумевает переход к одному виду условного оператора, эквивалентному блочному IF - THEN - ELSE.

Пример 1.4.1:

If (i<10) then a=7 => if (i<10) then {a=7;} else {;} ;

Пример 1.4.2:

Арифметический оператор IF из Фортрана заменяется следующим оператором

If ( выражение ) M1, M2, M3 => if (выражение <0) then { goto M1}

else if ( - выражение < 0 ) then {goto M3}

else {goto M2};


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

Перестановка циклов

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

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

Пример 1.

Приведенное выше преобразование позволяет заменить цикл:

do 1 I1 = L1, U1

do 1 I2 = L2(I1), U2(I1)

…

А(P1(I1, I2), P2(I1, I2)) = . . . (*)

u

. . . = А(Q1(I1, I2), Q2(I1, I2))

v

…

1 continue

на фрагмент программы :

do 1 I2 = L2, U2

do 1 I1 = L1(I2), U1(I2)

…

А(P1(I1, I2), P2(I1, I2)) = . . . (**)

u

. . . = А(Q1(I1, I2), Q2(I1, I2))

v

…

1 continue

Li и Ui (i=1,2) – соответственно нижняя и верхняя границы изменения счётчиков циклов. L1 и U1 – константы. L2 , U2 и Pj , Qj (j=1,2) – целочисленные линейные функции от счетчика внешнего цикла (возможно константы).

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

называемого графа направления зависимости.

Направление зависимости.

Определение вектора направления зависимости.

Введём обозначение: I=(I1, I2, … In).

Предположим, что вхождения u и v находятся в гнезде из n‑циклов со счетчиками циклов I1, I2, … In соответственно, и предположим, что v зависит от u. Следовательно, существуют такие итерации I и J (I£J), что u[I] и v[J] обращаются к одной ячейке памяти. Между этими итерациями существует отношение :

W = (w1, w2,…, wn), где wi Î {<, =, >}. Т.е. если I W J, то имеют место следующие отношения: Ii wi Ji, для всех i из [1,n]N (1). Обычно, для зависимых вхождений имеется несколько пар итераций Ik и Jk, на которых u[Ik], v[Jk] обращаются к одной ячейке памяти. Пусть между парами итераций Ik и Jk существует отношение Wk.

Определение. Объединением отношений Wk ( Wk = (wk,1, wk,2,…, wk,n) ) по k называется отношение Y = (È{wk,1}, È{wk,2},…, È{wk,n}), где È - объединение по k.

Дополним множество {<, =, >} элементами: {£} -- эквивалентен {<, =}, {³} -- эквивалентен {>, =}, {¹} -- эквивалентен {<, >}, {*} -- эквивалентен {<, =, >}.

Пример. Пусть W1 = (<, >, =), W2 = (=, <, <), W3 = (<, >, >) тогда ÈWi = {{<, =, <}, {>, <, >}, {=, <, >}}={£ , ¹ , *} (повторяющиеся элементы в каждом подмножестве были отброшены).

Определение. Вектор направления зависимости (или просто вектор направления) есть объединение отношений Wk по всем парам итераций I k и J k, на которых u[I k] и v[J k] обращаются к одной ячейке памяти.

Обозначим вектор направления зависимости через Y = (y1, y2,… yn) и будем писать u d(y1,… yn ) v или u dΨ v (где yi Î {<, =, >, ³, £, ¹, *}).

Замечание. Если имеет место отношение u d(y1,… yn )v, то между любыми парами итераций I и J, такими что u[I] и v[J] обращаются к одной ячейке памяти, существует отношение Y : IYJ т.е. Ii yi Ji, для всех i из [1,n]N .

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

Пример 2.

do 7 i=0,10

do 7 j=0,10

A(2*i+3*j+21) = …

u

. . . = A(19*i+2*j+3)

v

7 CONTINUE

В данном примере имеется потоковая информационная зависимость. Например, на итерации I=(0,0) вхождение u, а на итерации J=(0,9) вхождение v обращаются к элементу A(21). Отношение между элементами I, J равно (=,<). Далее, на итерации I=(0,1) вхождение u, а на итерации J=(1,1) вхождение v обращаются к элементу A(24). Отношение между элементами I, J равно (<,=). Т. к. вектор направления зависимости равен объединению всех таких отношений, то здесь он, как минимум, равен (£,£).

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

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

циклов, а в каких нет.

критерий перестановки циклов.

Пусть имеется гнездо из двух циклов следующего вида:

do 1 I1 = L1, U1

do 1 I2 = L2(I1), U2(I1)

…

А(P1(I1, I2), P2(I1, I2)) = . . .

u

. . . = А(Q1(I1, I2), Q2(I1, I2))

v

…

1 continue

Li и Ui (i=1,2) – соответственно нижняя и верхняя границы изменения счётчиков циклов. L1 и U1 – константы. L2, U2 и Pj и Qj (j=1,2) – целочисленные линейные функции от счетчика внешнего цикла (возможно константы).

u и v – вхождение индексной переменной A.

Класс программ, для которых все функции Li, Ui, Pj, Qj являются линейными от счётчиков циклов, называется линейным. Все дальнейшие построения проводятся для такого класса программ.

Критерий: Заголовки циклов можно переставить тогда и только тогда, когда в графе направлений зависимости нет зависимостей любого вида имеющих вектор направления зависимости Y = (y1, y2) такой, что {<} Ì y1 и {>} Ì y2 .

Перестановка заголовков циклов есть преобразование пространства итераций гнезда циклов (изменение обхода пространства итераций). Зависимость между вхождениями, имеющая такой вектор направления зависимости Y = (y1, y2), что

{<} Ì y1 и {>} Ì y2, препятствует преобразованию. Пусть зависимость между вхождениями u и v препятствует преобразованию.

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

Пример 3. Рассмотрим гнездо циклов:

do 7 i=0,3

do 7 j=0,3

A(i+j) = i+j

u

7 CONTINUE

Несмотря на то, что вектор направления зависимости (в данном случае у нас выходная зависимость) равен {<, >}, перестановка заголовков гнезда циклов приводит к эквивалентной программе. Однако мы полагаем, что перестановка циклов недопустима т.к. существует программа, с идентичным вхождением u и с такой же зависимостью , перестановка циклов в которой ведет к неэквивалентной программе

Целесообразность

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

Перестановку циклов целесообразно выполнять, если:

1. Длина внешнего цикла больше длины внутреннего.

2. Если при двумерной конвейеризации исходного цикла конвейеры следует запускать

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

Пример 4.

DO i = 2, N

DO j = 2, M
X(i,j) = X(i-1,j)+A(i,j)

3.

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

Пример 5.

DO i = 2, 1000

DO j = 2, 100

X(i,j) = X(i-1,j)+X(i,j-1)


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление

Новое внутреннее представление открытой распараллеливающей системы

Оглавление

1. Введение. 3

1.1. Старое внутреннее представление ОРС.. 5

2. Структура нового внутреннего представления ОРС.. 7

2.1. Дерево типов данных. 9

2.2. Дерево идентификаторов. 14

2.3. Дерево выражений. 18

2.4. Дерево операторов. 20

2.5. Итераторы и ссылки. 23

2.6. Пометки узлов. 24

2.7. Средства проверки и отладки. 25

3. Представление свойств языков программирования во внутреннем представлении. 27

4. Графы ОРС и библиотека преобразований программ, их взаимодействие с внутренним представлением 29

5. Визуализация внутреннего представления. 31

6. Обзор внутренних представлений аналогичных систем.. 34

6.1. Polaris. 34

6.2. SUIF. 35

7. Заключение. 37

8. Литература. 38

1. Введение

В данной работе представлена основа программной реализации Открытой распараллеливающей системы – новое внутреннее представление.

Открытая распараллеливающая система (ОРС) – проект, разрабатываемый на кафедре Алгебры и дискретной математики группой студентов и аспирантов. Она предназначена для автоматического распараллеливания программ с процедурных языков программирования (Фортран, Паскаль, Си) на параллельные компьютеры, ориентированные на математические вычисления [1].

Внутреннее представление (ВП) – это структура данных для хранения информации о программе, а также алгоритмы, облегчающие выполнение преобразований программ [2]. Новое ВП ОРС удовлетворяет следующим требованиям.

· Является универсальной структурой данных для хранения программ процедурных языков (рассматривались Си, Фортран и Паскаль).

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

· Эта модель также предоставляет базис для построения и анализа информационных зависимостей в программе.

· Предусматривает расширяемость для подключения компиляторов переднего плана с новых языков программирования к ОРС.

· Предоставляет возможность для генерации машинного кода из внутреннего представления.

Первоначальное внутреннее представление ОРС было разработано несколько лет назад [3]. Был написан специальный генератор компиляторов, разбирающий программы с Фортрана, Паскаля и Си. К сожалению, в той работе основной акцент был сделан на разбор языков, а адаптация внутреннего представления для реализации преобразований и анализа информационных зависимостей в программе выполнялась на поздних стадиях реализации проекта. Поэтому, старое внутреннее представление предоставляет недостаточные средства для реализации преобразований.

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

При реализации проекта были выполнены следующие работы:

· Спроектировано новое универсальное внутреннее представление программ и реализовано в виде классов на языке С++.

· Проведены работы по интеграции внутреннего представления и нового компилятора переднего плана с языка Си, основанного на инструменте ANTLR [5].

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

· Реализованы отладочные средства и средства проверки целостности структуры внутреннего представления во время работы программы.

· Разработан инструмент для визуализации и дополнительных преобразований фрагментов программ во внутреннем представлении.

Программная часть проекта написана на языке С++. При проектировании использовались «паттерны проектирования» [10], приемы современного проектирования на С++ [11] и приемы классического объектно-ориентированного анализа [12]. Программная реализация ОРС на момент написания этой работы составляет ~91000 строк, из них кода сторонних библиотек (ANTLR, Advanced WTL Controls) ~29000. Внутреннее представление ~9000 строк.

1.1. Старое внутреннее представление ОРС

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

Основным требованием к старому внутреннему представлению ОРС была быстрая реализация, позволяющая начать разработку преобразований. Среди недостатков старого внутреннего представления следует отметить:

1. Отсутствие поддержки пользовательских типов данных, а также структур в языках программирования (struct в Си и record в Паскале). Не существовало понятия «дерево типов».

2. Недостаточное сведение общих свойств языков в общий базис.

3. Отсутствие адекватного механизма пометок узлов внутреннего представления.

4. Недостаточное использование статической типизации языка С++ для поддержки целостности, синтаксической и семантической корректности программы.

Вначале необходимо отметить, что при создании генератора компиляторов и как следствия – старого внутреннего представления, была решена сложная задача, спроектировано представление, хранящее программы на языках Си, Паскаль и Фортран. Это позволило начать реализовывать преобразования. На старом внутреннем представлении было реализовано девять распараллеливающих преобразований [2], в том числе два – «Введение временных массивов» и «Растягивание скаляров» автором. Появившийся в результате выполнения этой работы опыт позволил обнаружить приведенные выше недостатки старого ВП, и прийти к пониманию, каким должно быть новое ВП.

Остановимся на выделенных недостатках подробнее. Старое внутреннее представление содержало существенное ограничение на входные языки – отсутствие возможности описать пользовательские типы данных. Это ограничение, например, не позволяло разработать конвертеры в программу с MPI-инструкциями.

В старом внутреннем представлении не была закончена работа по сведению сходных конструкций языков в общий базис. Так, например, в старом ВП имеется оператор FortranDO, который может быть сведен к оператору FOR таких языков как Си и Паскаль.

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

Старое внутреннее представление недостаточно использовало возможности языка С++ по статическому контролю типов данных. Так например, все циклы в старом ВП были представлены как объекты класса OPERATOR и целочисленное поле указывало какой именно оператор представляет данный объект.

2. Структура нового внутреннего представления ОРС

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

За основу для конструирования внутреннего представления взят паттерн «Composite». Основная идея заключается в следующем. Записывается базовый класс[1] для всех типов узлов, встречающихся в дереве. Этот класс может содержать общие для всех типов узлов свойства и методы. Например, если узлы дерева представляют идентификаторы в программе, то в базовый класс удобно поместить строковое представление (имя) идентификатора, потому что каждый узел характеризуется таким именем. Такой базовый класс называется компонентом.

Следом за базовым классом определяются классы, представляющие узлы дерева. Эти классы связаны с базовым отношением наследования. Классы, представляющие узлы дерева, могут ссылаться на другие узлы дерева (как, например, в двусвязном списке одно звено ссылается на левого и правого соседа). Узлы, которые не имеют ссылок на другие узлы, как обычно, будем называть листьями.

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

Прежде чем переходить к рассмотрению деревьев, следует упомянуть о способе конструирования узлов. Для этой цели применяется паттерн «Factory» [10]. Поскольку язык С++ не содержит сборщик мусора, программист вынужден самостоятельно следить за освобождением памяти. При проектировании ВП было принято два важных решения:

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

2. Узел при удалении ответственен за освобождение памяти всех своих поддеревьев.

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

Теперь о стратегии освобождения памяти. На ранних этапах разработки нового ВП рассматривалась идея организации ссылок между узлами через «умные указатели» (Smart Pointers) [11]. Однако при практическом применении оказалось, что в данной ситуации использование таких указателей неэффективно. Во-первых, они создают перерасход памяти, во-вторых, при освобождении памяти могут возникать циклические ссылки между объектами, которые очень трудно отслеживать, а ошибки, связанные с их невнимательным применением крайне трудно находить. Таким образом, было принято решение использовать простую и четкую стратегию освобождения узлов – каждый узел отвечает за удаление своих поддеревьев.

2.1. Дерево типов данных

Дерево типов используется как для представления простых типов данных (целый, символьный), так и для представления составных (массивы, структуры, перечисления). Используется одна и та же система классов для всех языков, хранящихся во внутреннем представлении.

На Рисунок 1. Схема наследования классов типов представлена диаграмма классов для дерева типов:

Рисунок 1. Схема наследования классов типов

Класс IRObject является корнем иерархии для большинства классов внутреннего представления. Основная его роль – хранить пометки узлов. Таким образом, каждый класс, который наследуется от IRObject, может содержать пометки.

Абстрактный класс TypeData является компонентом – корнем иерархии классов дерева типов. Он содержит чисто виртуальный метод[2] clone(). Этот метод создает и возвращает свою копию и копию всех своих поддеревьев («глубокую копию»). Операцию clone() можно определить рекурсивно: для узла-листа clone() создает копию этого узла. Для узла-композиции clone() проходит по всем ссылкам из этого узла, вызывая для них clone(), таким образом, получая копию всех поддеревьев, затем создает копию самого узла и «прицепляет» вновь созданные поддеревья.

Теперь рассмотрим последовательно все узлы, наследованные от TypeData. Самый простой из них – TypeSimple. Этот узел представляет элементарные типы данных в языке программирования (целый, символьный, с плавающей запятой).

Внутри класса TypeSimple объявляется перечисление (enum), в котором перечислены все элементарные типы. Внутри класса имеется поле типа этого перечисления, которое и хранит информацию, какой конкретный элементарный тип представляет этот узел. Имеются методы для получения и установки типа узла: getType() и setType().

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

Следующий рассматриваемый узел – TypePtr. Этот узел используется для представления типа «указатель на тип». Этот класс имеет поле, в котором хранится ссылка на поддерево, представляющее тип (называемый базовым), на который указывает этот узел. Имеются методы для получения и установки базового типа – getBaseType() и setBaseType(). При установке нового базового типа, дерево, соответствующее старому базовому типу автоматически удаляется.

Например, запись типа в программе на Си «int *» будет выглядеть следующим образом:

Рисунок 2. Представление «int *»

А для типа «int**» следующим образом:

Рисунок 3. Представление «int **»

Следующий узел – TypeSubProc. Этот узел представляет тип «подпрограмма». Класс хранит информацию об аргументах подпрограммы, о типе возвращаемого значения, а также о модификаторах, которые использовались при объявлении подпрограммы (например, cdecl, inline). Для представления аргументов используется класс SubProcParams.

Класс SubProcParams представляет собой список аргументов подпрограммы. Каждый аргумент является экземпляром класса SubProcParam, поэтому для каждого аргумента хранится имя и информация о типе. Класс SubProcParams предоставляет методы для добавления, удаления и итерирования по списку аргументов.

Тип возвращаемого значения подпрограммы хранится точно так же, как базовый тип для узла-указателя на тип. Имеются методы для получения и установки типа возвращаемого значения getRetValueType() и setRetValueType().

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

Следующий узел дерева типов – TypeArray. Этот класс предназначен для хранения информации о типах – массивах. Многомерные массивы также представляются этим узлом. В отличие от Си, где многомерные массивы представляются композицией одномерных, во внутреннем представлении ОРС, массивы представляются единым узлом, содержащим информацию обо всех измерениях, потому что этот способ хранения удобнее для многих распараллеливающих преобразований. Для каждого измерения известна нижняя и верхняя граница индекса (позволяет хранить полную информацию о массивах в Паскале). Для этого внутри класса массива определена структура Limits, которая имеет два поля: low и high.

Пример определения массива. Пусть имеется следующий фрагмент программы на Паскале:

type

T = array[0..1][1..8] of int;

Во внутреннем представлении эта запись будет выглядеть следующим образом:

Рисунок 4. Представление массива

Класс TypeArray содержит все необходимые методы для работы с массивом. Для установки и получения базового типа массива: getBaseType() и setBaseType(). Для получения количества измерений массива – getDimsCount(). Для получения информации о каждом измерении, перегружен оператор [], который по номеру измерения возвращает ссылку на структуру Limits, соответствующую данному измерению.

Класс TypeStruct хранит информацию о структуре (struct) или объединении (union). Этот класс является контейнером для элементов структуры. Каждый элемент структуры описывается классом NameType. Этот класс будет рассмотрен позже в главе «Дерево идентификаторов», здесь же следует сказать, что этот класс содержит имя и информацию о типе элемента.

Класс TypeStruct предоставляет методы для добавления, вставки, удаления и итерирования по элементам структуры. Булевое поле m_bIsUnion внутри класса указывает, является ли это описание описанием структуры или объединения.

Последний узел дерева типов – TypeNamed. Этот класс используется для представления именованных типов. Т.е. типов, которые определены в некотором месте программы и ссылка на них необходима в другом месте. Например, пусть имеется следующий фрагмент программы на Паскале:

type

T = integer;

TPtr = ^T;

Класс TypeNamed имеет внутри два поля. Первое указывает на область видимости, в которой расположен именованный тип, а второе – имя этого типа.

Во внутреннем представлении эта запись будет выглядеть следующим образом:

Рисунок 5. Представление ссылки на именованный тип

В области видимости содержатся два именованных типа: T и TPtr. Из схемы видно, что имя типа T связано с объектом класса TypeSimple, а ST_INT указывается что тип – целое число. TPtr является указателем (TypePtr), а тип на который он указывает – T. Чтобы сослаться на уже определенный тип и используется класс TypeNamed. Создается объект этого класса, «Имя» в нем содержит имя типа - «T», а «Область» в нем указывает на область видимости, в котором определен тип «T».

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

2.2. Дерево идентификаторов

Теперь рассмотрим дерево идентификаторов. Узлы этого дерева хранят информацию о поименованных сущностях в программе, таких как: переменные, типы данных, метки и подпрограммы.

На Рисунок 6. Схема наследования классов идентификаторовпредставлена диаграмма наследования классов идентификаторов:

Рисунок 6. Схема наследования классов идентификаторов

Базовым классом для всех классов-узлов является класс NameObject. Он содержит общее для всех, наследованных от него классов свойство – имя идентификатора. Имя представляется обычной текстовой строкой. Класс также содержит метод getName(), который позволяет получить имя идентификатора.

Рассмотрим класс NameVar, он хранит информацию о объявленной в программе переменной. В этом классе содержится тип переменной – объект обобщенного класса TypeData. Это позволяет представлять переменные любого типа. Также в классе содержится булев признак, является ли переменная константной (модификатор const в языке Си), а также является ли переменная аргументом функции. Следует пояснить, как представляются аргументы функции во внутреннем представлении.

Если речь идет не о переменной из глобальной области видимости (глобальной переменной), то переменная является либо локальной для некоторой подпрограммы, либо параметром этой подпрограммы. Параметры подпрограммы во многом схожи с локальными переменными, поэтому также представлены классом NameVar. Однако, в случае необходимости, метод isArgument() позволяет определить является ли объект класса NameVar локальной переменной или аргументом подпрограммы. Такая проверка используется, например, при выводе внутреннего представления в Си. Для локальных переменных необходимо генерировать их определение, в то время как информация о типах параметров записывается как типы аргументов подпрограммы.

Также при создании объекта класса NameVar имеется возможность указать его значение. Это необходимо для задания значения константных переменных в Си и типизированных переменных в Паскале.

Рассмотрим следующий класс дерева идентификаторов – NameType. Этот класс хранит информацию о поименованном типе данных: typedef в Си и раздел type в Паскале. В классе содержится объект обобщенного класса TypeData, что позволяет создавать именованные типы любой сложности в рамках дерева типов.

Следующий класс дерева идентификаторов – NameLabel. Этот класс содержит информацию о метках в программе: не используется явное определение в Си; label в Паскале. Он содержит указатель на оператор, который помечен этой меткой. Имеются методы getLabelStatement() и setLabelStatement() соответственно для получения и установки помеченного оператора.

Последний класс дерева идентификаторов – NameSubProc. Он представляет подпрограмму: функцию языка Си; procedure, function в Паскале. Класс содержит тип подпрограммы (указатель на TypeSubProc), а также опционально ссылку на тело подпрограммы (указатель на Block).

Необходимо заметить, что определение именованной подпрограммы может быть полным и неполным. Неполное определение – это «прототип функции» в языке Си и предварительное описание процедуры или функции в Паскале. Неполное определение, в отличие от полного, не содержит тело подпрограммы. Предполагается, что после неполного определения, в программе где-то далее встретится полное. Однако, поскольку фактический поиск тела подпрограммы может быть отложен до фазы работы линкера (редактора связей), поддержка неполных определений необходима во внутреннем представлении.

В классе NameSubProc имеется также важный метод syncNamespace(), который необходимо рассмотреть подробнее. Как было сказано ранее, локальные переменные и параметры подпрограммы представлены классом NameVar. Однако, NameSubProc содержит тип подпрограммы, который определяет типы и название аргументов подпрограммы. Фактически, информация о параметрах подпрограммы хранится в двух местах – в прототипе и в виде объектов NameVar. Эта двойственность является вынужденной и оправдана схожестью для преобразований программ локальных переменных и параметров подпрограмм. Метод syncNamespace() используется при создании объекта класса NameSubProc для полного (вместе с телом) описания подпрограммы. syncNamespace() необходимо вызвать после задания прототипа подпрограммы, чтобы в область видимости тела подпрограммы были добавлены объекты класса NameVar для представления параметров подпрограммы. Также этот метод необходимо вызывать после каждого изменения в прототипе, чтобы соответствующие изменения были отражены в объектах NameVar.

Наконец, следует рассмотреть класс Namespace. Он представляет «ярус» области видимости идентификаторов, и хранит обобщенный список NameObject-ов, т.е. идентификаторов, объявленных в текущей области видимости.

Один объект класса Namespace связывается с объектом класса Program и является глобальной областью видимости программы. Также с каждым блоком (Block) ассоциируется объект класса Namespace и представляет локальную область видимости блока. В классе Namespace имеются методы для поиска, рекурсивного поиска (вверх по дереву идентификаторов), итерирования, удаления и добавления объектов области видимости.

2.3. Дерево выражений

Базовым классом для дерева выражений является класс ExprNode. В нем определены абстрактные методы isLValue (проверка, является ли выражение l-value) и isEqual (проверка выражений на структурную эквивалентность). Диаграмма наследования классов дерева выражений приведена на Рисунок 7. Схема наследования классов выражений:

Рисунок 7. Схема наследования классов выражений

Из диаграммы видно, что классы ExprData, ExprImm, ExprNull и ExprOper являются непосредственными наследниками ExprNode. Рассмотрим назначение и структуру этих классов.

Класс ExprData представляет понятие вхождения переменной в выражение. Внутри он хранит NameReference, ссылку на идентификатор из области видимости. Класс реализует метод getData() для получения этого идентификатора.

Класс ExprImm представляет литерал, т.е. константу, записанную явно в коде программы. Для представления значения используется класс ImmValue, который способен хранить данное одного из следующих типов: int, double, char, string.

Класс ExprNull представляет понятие пустого выражения. Он используется при записи операторов в полном виде, например, если при конструировании оператора IF не задано условное выражение, объект класса ExprNull становится условным выражением этого оператора IF.

Класс ExprOper представляет операцию в выражении. Внутри класса определено перечисление (enum) со всеми возможными операциями:

// Unary

OT_UNPLUS, // Unary +

OT_UNMINUS, // Unary -

OT_UNPOSTPP, // Unary postfix ++

OT_UNPREFPP, // Unary prefix ++

OT_UNPOSTMM, // Unary postfix --

OT_UNPREFMM, // Unary prefix --

OT_SIZEOF, // sizeof() operator

OT_ADDR, // &

OT_UNREF, // *

// Binary

OT_PLUS, // +

OT_MINUS, // -

OT_MUL, // *

OT_DIV, // /

OT_MOD, // %

// Assign

OT_ASSIGN, // =

OT_PLUS_ASSIGN, // +=

OT_MINUS_ASSIGN, // -=

OT_MUL_ASSIGN, // *=

OT_DIV_ASSIGN, // /=

OT_MOD_ASSIGN, // %=

OT_LSHIFT_ASSIGN, // <<=

OT_RSHIFT_ASSIGN, // >>=

OT_BAND_ASSIGN, // &=

OT_BOR_ASSIGN, // |=

OT_BXOR_ASSIGN, // ^=

// Equality

OT_LESS, // <

OT_GREATER, // >

OT_LESSEQ, // <=

OT_GREATEREQ, // >=

OT_EQ, // ==

OT_NOTEQ, // !=

OT_LSHIFT, // <<

OT_RSHIFT, // >>

// Logical

OT_LNOT, // !

OT_LAND, // &&

OT_LOR, // ||

// Bitwise

OT_BNOT, // ~

OT_BAND, // &

OT_BOR, // |

OT_BXOR, // ^

// Special

OT_CALL, // ()

OT_ARRAY, // []

OT_STRUCT, // .

OT_PTRSTRUCT, // ->

// Special case

OT_POW // pow(a, b) (at C language)

Класс реализует обобщенные методы для создания операций, установки аргументов операций. Однако, зачастую удобнее работать с операцией в соответствии с ее принадлежностью к одному из шести классов операций: обращение к массиву, присваивание, унарную и бинарную арифметические операции, вызов подпрограммы, обращение к элементу структуры. Для каждой операции из приведенного выше перечисления известно, к какому из шести классов операций она относится. Поэтому удобнее воспользоваться одним из соответствующих, унаследованных от ExprOper классов: ExprArray, ExprAssign, ExprUnary, ExprBinary, ExprCall или ExprStruct. Эти классы также имеют методы для получения и установки аргументов, но выполняют соответствующие проверки. Например, соотносят операцию и количество ее аргументов.

2.4. Дерево операторов

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

Диаграмма наследования классов дерева операторов представлена на Рисунок 8. Схема наследования классов операторов.

Рисунок 8. Схема наследования классов операторов

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

Теперь последовательно рассмотрим другие классы, непосредственно наследованные от Statement.

Классы StmtBreak и StmtContinue представляют соответственно операторы break и continue языка Си.

StmtEmpty – пустой оператор.

StmtExpr – оператор-выражение. В этом операторе хранится указатель на узел дерева выражения. Обычно этот класс служит адаптером для операции присваивания (ExprAssign).

StmtGoto – оператор безусловного перехода, goto. Содержит ссылку на объект в дереве идентификаторов, на метку, на которую осуществляется переход.

StmtReturn – оператор return в языке Си, также как и StmtExpr содержит ссылку на выражение.

Классы StmtBranch и StmtLoop имеют специальное назначение. Они являются базовыми соответственно для операторов ветвления и операторов цикла. Диаграммы наследования этих операторов приведены на Рисунок 9. Схема наследования классов операторов ветвления и Рисунок 10. Схема наследования классов циклов:

Рисунок 9. Схема наследования классов операторов ветвления

Рисунок 10. Схема наследования классов циклов

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

Классы StmtIf и StmtSwitch представляют соответственно операторы IF и SWITCH языка Си.

Классы StmtFor, StmtWhile, StmtDoWhile представляют соответственно операторы FOR, WHILE и DO..WHILE языка Си.

2.5. Итераторы и ссылки

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

В дереве операторов итераторы применяются для обхода блока (класс Block). Для этого используется шаблонный класс ListIter[3] (константная версия ConstListIter), который инстанцируется классом Statement. Итератор реализует стандартную логику двунаправленного последовательного прохода по контейнеру, реализует методы для сравнения итераторов на равенство, присваивания и проверки на конец последовательности (метод isValid() ).

Для доступа к дереву идентификаторов применяется две сущности: ссылки на идентификаторы в области видимости (NameReference) и итераторы по области видимости (NameIter). Класс NameReference внутри содержит указатель на некоторую конкретную область видимости и указатель на конкретный идентификатор в этой области видимости. Таким образом, он подходит для представления ссылки на идентификатор (например, из дерева выражений). Для удобства, объект этого класса дополнительно может находиться в состоянии Not Valid, т.е. не указывать ни на какой идентификатор. В класс определены вспомогательные методы для определения типа идентификатора:

NameKind getNameKind();

bool isVarName();

bool isTypeName();

bool isLabelName();

bool isSubProcName();

методы для получения объекта-идентификатора:

NameObject& getAsObject();

NameVar& getAsVar();

NameType& getAsType();

NameLabel& getAsLabel();

NameSubProc& getAsSubProc();

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

Класс NameIter – это итератор по идентификаторам области видимости, который позволяет ставить фильтр на тип идентификаторов, по которым может осуществляться проход. При создании экземпляра класса разработчик выбирает, хочет ли он этим итератором проходить все идентификаторы в заданной области видимости или только идентификаторы определенного типа (например, только переменные или только подпрограммы). Итератор реализует стандартную логику последовательного прохода по контейнеру. Реализует операции сравнения двух итераторов на равенство. Объект класса NameIter может быть инициализировать объектом класса NameReference, а также по объекту класса NameIter можно получить объект класса NameReference. Таким образом, объекты этих двух классов являются взаимозаменяемыми и разработчик должен выбирать тот класс, который больше подходит для его задач. Если ему необходимо сослаться на идентификатор, предпочтительней использовать NameReference, если осуществить проход по области видимости – NameIter.

2.6. Пометки узлов

Пометки узлов во внутреннем представлении позволяют ассоциировать информацию с узлом одного из четырех деревьев и хранить ее вместе с внутренним представлением. Причем, при реализации сериализации[4] внутреннего представления эта информация сохраняется.

Базовый механизм пометок узлов реализован в классе IRObject. Методы setNote(), getNote() и delNote() позволяют соответственно устанавливать, получать и удалять пометки узлов. Пометки идентифицируются по имени, т.е. все эти три метода одним из параметров принимают строку символов – имя пометки. Сама пометка представляется классом ImmValue (непосредственное значение). Этот класс позволяет хранить один из следующих типов данных: bool, int, double, char, string, указатель на IRObject*. Таким образом, пометки являются типизированными и допускают вложение друг в друга.

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

Текущая реализация компилятора переднего плана в ОРС поддерживает использование директив компилятора (#pragma), с помощью которых можно в тексте программы задать пометки узлов.

2.7. Средства проверки и отладки

В новом внутреннем представлении, как было сказано ранее, используется паттерн Factory для порождения узлов всех деревьев. Кроме рассмотренных ранее достоинств единообразия выделения и освобождения памяти, такой подход позволил также повысить надежность внутреннего представления. При реализации любого преобразования, всегда вызываются методы классов внутреннего представления. Эти методы содержат строгие проверки входных данных и некоторые эвристические проверки, которые предотвращают порождение неправильных конструкций. Следует заметить, что новое ВП, в отличие от старого, гораздо лучше использует статическую проверку типов С++, присущую этому языку строгую типизацию, поэтому многие ошибки, которые допускались при реализации работы со старым ВП, теперь выявляются на этапе компиляции. Так, например, узел дерева операторов – оператор FOR в новом ВП имеет строго четыре потомка, первые три из которых выражения, а четвертый – блок операторов. В то же время, в старом ВП оператор FOR представлялся обобщенным классом OPERATOR, и никаких проверок относительно потомков такого узла на этапе компиляции было произвести невозможно.

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

Кроме того, все узлы ВП поддерживают модель обхода по паттерну Visitor [10]. Реализация этого паттерна сделана по описанию Acyclic Visitor из [11] и, вообще говоря, может применяться не только в отладочных целях. Однако, на текущий момент не решены некоторые специфичные технические проблемы с обходом константных объектов внутреннего представления и применение этого механизма, например, в графах информационных зависимостей небезопасно. Для тестирования преобразований, автором была разработана программа IntegrityTest, в которой для сбора статистики по операторам и вхождениям переменных в программу использовался именно механизм паттерна Visitor. Простота кода программы IntegrityTest подтверждает удобство применения этого способа обхода узлов внутреннего представления.

3. Представление свойств языков программирования во внутреннем представлении

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

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

Большинство конструкций во внутреннем представлении перешли из языка Си. Например, цикл FOR Си и Паскаля (цикл DO Фортрана) во внутреннем представлении называется StmtFor и характеризуется узлом с четырьмя потомками: выражение инициализации (InitExpr), выражение условия (CondExpr), выражение инкремента (IncrExpr) и тела цикла (Body). Таким образом, например, цикл For Паскаля

for i := 1 to 10 do

...

может быть записан во внутреннем представлении:

InitExpr: i = 1

CondExpr: i <= 10

IncrExpr: ++i

Body: ...

В то же время определение массивов в языке Паскаль является более общим, чем в Си:

M : array[1..10, -5..5] of integer;

Поэтому узел дерева типов, хранящий массив во внутреннем представлении содержит информацию о верхних и нижних границах массива. Более того, в языке Си понятие многомерного массива вводится индуктивно, так, например, трехмерный массив представляется как массив двухмерных массивов, а двухмерный массив как массив массивов. Во внутреннем представлении ОРС многомерный массив – это один узел в дереве типов, которых хранит информацию о количестве измерений массива и границы индексов каждого.

Также важной характеристикой внутреннего представления является его исполнимость [15, с. 44]. Исполнимость ВП означает возможность исполнить программу, записанную во внутреннем представлении. При этом результаты такого исполнения должны быть идентичны результатам исполнения первоначальной программы при одинаковых наборах данных на входе обеих программ. Новое внутреннее представление ОРС, как и прежнее, является исполнимым.

Внутреннее представление проектировалось так, чтобы при преобразованиях программ сохранялась синтаксическая и семантическая целостность. Так операторы циклов и ветвления представлены в полном виде. Это означает, что при добавлении, например, оператора IF сразу создается выражение (пустое) для условия, а также пустые блоки для THEN и ELSE веток оператора. В частности, это решает проблему «кочующего ELSE». Таким образом, невозможна ситуация, когда оператор IF (в терминах языка Паскаль) имеет только ELSE, без THEN. Или когда в блоке имеется два ELSE, но только один IF.

4. Графы ОРС и библиотека преобразований программ, их взаимодействие с внутренним представлением

Графовые модели программ используются в оптимизирующих и распараллеливающих компиляторах давно. Так одной из первых теоретико-графовых моделей программ был управляющий граф, введенный в рассмотрение Р. Карпом в 1960 г. В Открытой распараллеливающей системе на момент написания этой работы реализованы пять графов: граф информационных связей Лампорта, решетчатый граф, граф вычислений, управляющий граф программы и граф вызовов подпрограмм.

Граф информационных связей Лампорта позволяет определять наличие зависимости между вхождениями переменных. Вершинами этого графа соответственно являются вхождения переменных, а дугами – зависимости между ними. Выделяется три типа зависимостей: истинная информационная зависимость, антизависимость, выходная зависимость [3].

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

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

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

Внутреннее представление ОРС не содержит в явном виде эти графы, вместо этого оно предоставляет сервис для их построения и осуществляет взаимодействие между графами и библиотекой преобразований. Так для графа Лампорта, решетчатого графа и графа вычислений для обозначения вхождений используется класс внутреннего представления ExprData. Для управляющего графа для обозначения операторов используется класс Statement, а для графа вызовов подпрограмм класс NameSubProc.

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

5. Визуализация внутреннего представления

Визуализация внутреннего представления может быть необходима в различных ситуациях. Например, это упрощает отладку и понимание структуры ВП (при обучении разработчиков). Однако, имеется важное прикладное применение визуализации ВП в Открытой распараллеливающей системе – работа с фрагментами программы. Инструмент для визуализации внутреннего представления в виде текста программы с возможностью выделения фрагментов, был реализован еще для старого внутреннего представления и нашел применение в обучающей программе на основе ОРС [4]. Поясним принцип работы этого инструмента на примере.

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

Рисунок 11. Инструмент для выделения фрагментов

И получает изображение решетчатого графа, построенного для двух выделенных вхождений переменных:

Рисунок 12. Решетчатый граф

Сложность реализации инструмента выделения фрагмента заключается в том, что необходимо проверить целостность фрагмента (например, что пользователь выделил именно вхождение, т.е. “a[i,j]”, а не “[i,j]”) и соотнести выделение с узлом во внутреннем представлении. Оказалось, что проще всего решить эти две проблемы, позволив пользователю выделять фрагменты на визуализированном внутреннем представлении программы.

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

6. Обзор внутренних представлений аналогичных систем

6.1. Polaris

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

Прежде всего, следует отметить, что внутреннее представление Polaris ориентировано только на один язык программирования – Фортран-77, это во многом определило его архитектуру. Представление содержит ряд специфичных для фортрана конструкций, таких как Data Blocks и Common Blocks. Это позволяет эффективно реализовывать преобразования программ. Однако, у этого представления имеются недостатки. Отсутствует такая важная для современных процедурных языков (Си, Паскаль, Java) конструкция, как блок операторов (список операторов с ассоциированной с ним областью видимости имен). Пометки в узлах ВП не предусмотрены. Вместо них разработчики предоставили стек временных объектов, ассоциированный со всей программой (единицей трансляции), поэтому разработчик программы не может ссылаться на определенный элемент программы (оператор, операцию, вхождение) неким стандартным образом.

Граф информационных зависимостей в системе Polaris неразрывно связан с внутренним представлением [7]. Это означает, что при выполнении преобразований приходится его постоянно перестраивать, чтобы поддерживать его информацию о зависимостях в актуальном состоянии. В ОРС граф информационных зависимостей строится до выполнения преобразований заново. Это особенно актуально, потому что ОРС на момент написания этой работы уже содержит пять графовых моделей: граф информационных связей, решетчатый граф, граф вычислений, граф вызова подпрограмм и управляющий граф. Синхронное перестроение всех этих графов заняло бы слишком много времени и усложнило бы реализацию преобразований внутреннего представления.

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

6.2. SUIF

Stanford University Intermediate Format (SUIF) – программная система для исследования распараллеливающих и оптимизирующих компиляторов [8]. Эта система также как и ОРС реализована на С++, в Интернете имеется документация на внутреннее представление [9] и исходный код.

Внутреннее представление SUIF рассчитано на языки Си и Фортран-77. Однако поддержка языка Фортран изначально в систему не закладывалась, программа с него конвертером f2c переводится в Си, а только потом во внутренний формат. Очевидно, что при таком подходе специфичная для программ на Фортране информация никак не отражается во внутреннем представлении.

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

Внутреннее представление ОРС имеет ряд схожих черт с внутренним форматом SUIF, например, основанный на паттерне «Composite» [10] способ представления программ и использование пометок узлов для передачи информации между отдельными частями компилятора.

7. Заключение

Дипломная работа посвящена новому внутреннему представлению Открытой распараллеливающей системы, его связи с графовыми моделями и преобразованиями программ. В работе показано, что разработанное внутреннее представление является универсальным, расширяемым, исполнимым и способно хранить программы процедурных языков программирования. Приведены доводы в пользу объектно-ориентированной модели внутреннего представления, приведено сравнение со старым внутренним представлением ОРС. Также приведено сравнение с внутренними представлениями наиболее известных распараллеливающих систем – Polaris и SUIF.

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

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

8. Литература

1. Штейнберг Б.Я. Открытая распараллеливающая система.// PACO’2001/ Труды международной конференции «Параллельные вычисления и задачи управления». М., 2-4 октября 2001 г., ИПУ РАН, с. 214-220.

2. Штейнберг Б.Я., Черданцев Д.Н., Науменко С.А., Бутов А.Э., Петренко В.В. Преобразование программ для Открытой распараллеливающей системе. // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, “Наука и Освита”, 2003, № 4 , с. 97-105.

3. Штейнберг Б.Я., Макошенко Д.В., Черданцев Д.Н., Шульженко А.М. Внутреннее представление в Открытой распараллеливающей системе. // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, “Наука и Освита”, 2003, № 4 , с. 89-97.

4. Штейнберг Б.Я., Черданцев Д.Н., Штейнберг Р.Б., Шульженко А.М., Бутов А.Э., Науменко С.А., Петренко В.В., Шилов М. В., Гуфан К.Ю., Тузаев А.В., Арутюнян О. Э., Морылёв Р.И. Обучающая распараллеливанию программа на основе ОРС. // Научно-методическая конференция «Современные информационные технологии в образовании: Южный Федеральный округ»/ 13-14 мая 2004 г., Ростов-на-Дону, Тезисы докладов, с. 248-250.

5. ANother Tool for Language Recognition. http://www.antlr.org/.

6. K. Faigin, J. Hoeflinger, D. Padua, P. Petersen, S. Weatherford. The Polaris Internal Representation.

7. Y. Paek, P. Petersen. A Data Dependence Graph in Polaris.

8. R. Wilson, R. French, Ch. Wilson, S. Amarasinghe, J. Anderson, S. Tjiang, S. Liao, C. Tseng, M. Hall, M. Lam, J. Hennessy. SUIF: An Infrastructure for Research on Parallelizing and Optimizing Compilers

9. G. Aigner, A. Diwan, D. Heine, M. Lam, D. Moorey, B. Murphy, C. Sapuntzakis. The SUIF Program Representation

10. Гамма Э., Хэлм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. – СПб: Питер, 2001. – 368 с.: ил.

11. Andrei Alexandrescu. Modern C++ Design: Generic Programming and Design Patterns Applied – Addison Wesley, 2001. – 352 p.

12. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя/ Пер. с англ. – М.: ДМК Пресс, 2001 – 432 с.: ил.

13. Страуструп Б. Язык программирования С++, 3-е изд. / Пер. с англ. – СПб.; М.: «Невский диалект» - «Издательство БИНОМ», 1999 г. – 991 с.: ил.

14. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд./ Пер. с англ. – М.: «Издательство БИНОМ», СПб.: «Невский диалект», 2000 – 560 с.: ил.

15. Лазарева С. А. Использование многоуровневого внутреннего представления в автоматическом распараллеливании программ для многопроцессорных ЭВМ, диссертация на соискание ученой степени кандидата технических наук, Ростовский госуниверситет, Ростов-на-Дону, 2000 г., 150 с.

16. Штейнберг Б.Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью . – Ростов н/Д: Изд-во Ростовского университета, 2004. – 192 с.: ил.

17. Штейнберг Р.Б. Вычисление задержек в стартах конвейеров для суперкомпьютеров со структурно-процедурной организацией вычислений. // Международная научно-техническая конференция «Интеллектуальные и многопроцессорные системы»/ 22-27 сентября, 2003, Дивноморское, Россия, Тезисы докладов, с. 43-47.

[1] Речь идет о классах объектно-ориентированного языка программирования, например, С++.

[2] Чисто виртуальный метод (pure virtual method) – виртуальный метод, который не имеет реализации. Если класс содержит хотя бы один чисто виртуальный метод, его называют абстрактным классом. Невозможно создать объект абстрактного класса. Такой класс служит для представления понятия «интерфейс».

[3] Класс ListIter используется также для обхода членов структур и параметров подпрограмм.

[4] Сериялизация – преобразование некоторой структуры данных в поток регулярной структуры. Например, в байтовый поток (бинарная сериализация) или XML-поток (текстовая сериализация).


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

РАСЩЕПЛЕНИЕ ЦИКЛА

Это преобразование заменяет цикл

DO I=1,N

ТЕЛОЦИКЛА(I)

на фрагмент программы

DO 99 I=1,M

99 ТЕЛОЦИКЛА(I)

DO 88 I=1,N-M

88 ТЕЛОЦИКЛА(I+M)

Это же преобразование может выглядеть и по-другому, как

замена цикла

DO 99 I=1,N

99 ТЕЛОЦИКЛА(I)

на фрагмент программы

DO 99 I=1,M

99 ТЕЛОЦИКЛА(I)

DO 88 I=M+1,N

88 ТЕЛОЦИКЛА(I)

(Здесь не выполнена канонизация второго цикла в результирующем фрагменте).

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

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

Расщепление описывается во многих работах.

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

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

СЛИЯНИЕ ЦИКЛОВ

Данное преобразование заменяет фрагмент программы, состоящий из двух подряд написанных циклов с одинаковыми заголовками, одним циклом (loop fusion).

Это преобразование является обратным к разбиению циклов.

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

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Информационная зависимость : Приведение выражений к стандартному виду Подстановка вперед

ПРИВЕДЕНИЕ ВЫРАЖЕНИЙ К СТАНДАРТНОМУ ВИДУ

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

1. Аргументы коммутативной бинарной операции должны следовать в алфавитном порядке. Например, P*Q а не Q*P.

2. Если в выражении некоторая одновременно и коммутативная и ассоциативная операция должна выполняться несколько раз подряд, то все аргументы должны быть отсортированы по алфавиту. Например, A+B-X (вычитание в этой записи следует понимать, как сложение с переменной с унарным минусом A+B+(-X)).

3. Сумма двух одинаковых выражений с (может быть разными) числовыми множителями заменяется таким выражением с множителем, который равен сумме исходных. 3*I-I => 2*I.

4. Можно выносить общий множитель-переменную, пользуясь законом дистрибутивности. Но при вызове такой процедуры следует указывать, какие множители следует выносить. Такая процедура может выполняться благополучно лишь тогда, когда исходное выражение линейно зависит от совокупности указанных переменных (если их несколько). Например, A*B+A*C+B*C => A*B+(A+B)*C, если выражение надо приводить относительно переменной C. Заметим, что в этом примере невозможно привести исходное выражение относительно переменных A и B одновременно, поскольку выражение нелинейно зависит от их совокупности. Если выносимый множитель является не константой, а переменной или подвыражением, то он пишется слева или справа в зависимости от алфавитного порядка с переменной, относительно которой множитель выносится.

5. При записи отношений будем использовать «<» вместо «>» и «£» вместо «³». (x+2)<0 вместо 0>(x+2).

6. Булевы выражения следует приводить к ДНФ (дизъюнктивной нормальной форме), в которой аргументы конъюнкций и дизъюнкций расположены в алфавитном порядке. При этом, выражение без отрицания должно записываться раньше такого же выражения с отрицанием. Например, Not(A) and B and Z or B and Y or not(B) and C.

7. Арифметические подвыражения над константами следует заменять их числовыми значениями. Например, числом –5 можно заменить выражение (3-4*2).

8. Унарный «-» можно выносить, как множитель, если это особо оговорено в параметрах процедуры.

Пример 1.

X(I)*2-2*X(I-1) = > 2*X(I)-2*X(I-1)

X(I)*A(I)-2*X(I) => (A(I)-2))* X(I)

X(I)*Y(I)-2*X(I) => X(I) *(Y(I)-2))

Для реализации пункта 4 требований к стандартному виду выражения может быть полезным предварительное раскрытие скобок по закону дистрибутивности.

Пример 2. 5*(X-Y)+(A+1)*(X+Y) => 5*X-5*Y+(A+1)*X+(A+1)*Y => (5+(A+1))*X +(-5+(A+1))*Y => (A+6)*X +(A-4)*Y

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Информационная зависимость : Приведение выражений к стандартному виду Подстановка вперед

ПОДСТАНОВКА ВПЕРЕД

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

Пусть для рассматриваемого фрагмента программы выполняются условия:

1. S1 - единственная точка входа фрагмента.

2. В графе информационных связей дуга (v1,v2) между вхождениями X(F1), выделенными в фрагменте (1), является единственной дугой этого фрагмента, входящей во вхождение v2 переменной X.

3. Нет дуг, входящих во вхождения индексного выражения F1 оператора Sm из вхождений данного фрагмента.

4. Нет дуг, выходящих из вхождений выражения expr(A,B,...) в генераторы операторов S1,..,S(m-1).

Тогда подстановка вперед является эквивалентным преобразованием.

Доказательство. После выполнения подстановки из фрагмента программы (1) получается фрагмент

S1 X(F1) = expr(A,B,...)

................………………........ (2)

Sm ... = ...expr(A,B,...)...

Очевидно, что для эквивалентности фрагментов (1) и (2) достаточно, чтобы к моменту выполнения оператора Sm переменная X(F1) и выражение expr(A,B,...) принимали одинаковые значения. Предположим, что это неверно. Тогда к моменту выполнения оператора Sm либо X(F1), либо expr(A,B,...) поменяло свое значение.

Предположим, свое значение поменяло вхождение X(F1). Тогда, ввиду единственности входа у фрагмента, либо где-то в рассматриваемом фрагменте существует еще один генератор X(F1) , что противоречило бы условию 2 теоремы, либо изменило свое значение индексное выражение F1, но тогда из рассматриваемого фрагмента должны быть дуги в F1, что противоречило бы условию 3 теоремы.

Теперь предположим, что свое значение поменяло выражение expr(A,B,...). Тогда, где-то по пути от S1 до Sm свое значение поменяло какое-то вхождение этого выражения. Но это означает, что у операторов S2,..,S(m-1) есть генератор переменной из данного выражения, что противоречит условию 4 теоремы.

Полученные противоречия завершают доказательство теоремы.

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

Условия предыдущей теоремы не являются необходимыми. Действительно, если в операторе Sm вхождение X(F1) умножается на ноль, то никакие нарушения условий теоремы не препятствуют эквивалентности подстановки.

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

ПЕРЕИМЕНОВАНИЕ ПЕРЕМЕННЫХ

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

Будем говорить, что фрагмент программы обладаем свойством разложимости относительно оператора Operator, если этот фрагмент программы представим в виде

PartOfProg1

Operator

PartOfProg2

где каждый из фрагментов PartOfProg1 и PartOfProg2 имеет один вход и один выход.

Переименование безындексных переменных

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

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

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

Лемма 1. Пусть оператор

L Statement(A(I),A(J),...)

с меткой L включает использования A(I), A(J),... переменной A. Тогда этот оператор можно заменить фрагментом программы

L AA(I) = A(I)

AA(J)= A(J)

. . . . . . . . . . . . . . . . . . . . . . . . . . .

L1 Statement(AA(I),AA(J),...)

При этом, если исходный оператор был последним оператором тел каких-либо циклов, то в заголовках этих циклов следует метку L заменить на L1. (Метка L переносится к первому добавленному оператору присваивания на тот случай, если существуют переходы (goto) к оператору с этой меткой).

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

Лемма 2. Пусть в текст программы входит оператор присваивания

L A(I) = expr

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

L AA(I) = expr

L1 A(I) = AA(I)

Если исходный оператор был последним оператором тел каких-либо циклов, то в заголовках этих циклов следует метку L заменить на L1.

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

Теорема 6. Пусть имеется фрагмент программы

PartOfProg(A,B,...)

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

PartOfProg1

X=expr1

PartOfProg2

где PartOfProg1 - не содержит генераторов переменной X и каждый из фрагментов PartOfProg1 и PartOfProg2 имеет один вход и один выход. Тогда эквивалентным преобразованием является замена исходного фрагмента на фрагмент программы

AA=A

BB=B

...........................

PartOfProg(AA,BB,...)

A=AA

B=BB

........................

(здесь AA, BB,... - новые переменные).

Доказательство. Доказательство проведем в предположении одной безиндексной переменной A во фрагменте программы PartOfProg(A). Общий случай получается по индукции.

Рассмотрим случай существования генератора переменной A в исходном фрагменте. Представим фрагмент программы PartOfProg(A) в виде конкатенации фрагментов

PartOfProg1(A)

A=expr1

PartOfProg2(A)

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

AA=A

PartOfProg1(AA)

AA=expr

PartOfProg2(AA)

A=AA

. В части

AA=A

PartOfProg1(AA)

выполним подстановку вперед и получим

AA=A

PartOfProg1(A)

AA=expr

PartOfProg2(AA)

A=AA

Теперь можно удалить первый оператор присваивания этого фрагмента, получив ему эквивалентный

PartOfProg1(A)

AA=expr

PartOfProg2(AA)

A=AA

Новый фрагмент можно получить из фрагмента

PartOfProg1(A)

A=expr

PartOfProg2(A)

A=A

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


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

Разрыв итераций и гнездование цикла

  1. Разрыв итераций – это преобразование, которое заменяет цикл

for(i = 0; i < N; i = i + 1)

BODY(i);

следующим фрагментом программы

for(i = 0; i < (N / h); i = i + 1)

for(j = 0; j < h; j = j + 1)

BODY(h * i + j);

for(i = 0; i < (N – (N / h) * h); i = i + 1)

BODY((N / h) * h + i);

Гнездование циклов похоже на разрыв итераций и заменяет цикл

for(i = 0; i < N; i = i + 1)

BODY(i);

следующим фрагментом программы

for(j = 0; j < h; j = j + 1)

for(i = 0; i < (N / h); i = i + 1)

BODY(i + j * (N / h));

for(i = 0; i < (N – (N / h) * h); i = i + 1)

BODY((N / h) * h + i);

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

Эти преобразования не меняют порядок выполнения операций, а значит равносильны.

Есть ещё два подобных этим преобразования. Первое из них меняет цикл

for(i = 0; i < N; i = i + 1)

BODY(i);

на следующий фрагмент программы

for(i = 0; i < h; i = i + 1)

for(j = 0; j < (N / h); j = j + 1)

BODY(h * j + i);

for(i = 0; i < (N – (N / h) * h); i = i + 1)

BODY((N / h) * h + i);

а второе – на следующий

for(j = 0; j < (N / h); j = j + 1)

for(i = 0; i < h; i = i + 1)

BODY(j + i * (N / h));

for(i = 0; i < (N – (N / h) * h); i = i + 1)

BODY((N / h) * h + i);

Эти два преобразования равносильны не всегда.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

Подстановка вперед

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

Пример 3.2.1: Идентификаторы

x = a+5 0001

A: b= x+3 0002

For ( i = 1; i<10 ; i++) 0003

aa[i] = i+x; 0004

B: . . . . . . 0005

В приведенном примере можно произвести подстановку вперед, т.е. на участке программы от идентификатора «0002» до идентификатора «0005» все вхождения переменной «х» заменить на а+5. При этом получится программа эквивалентная исходной.

x = a+5

A: b = a+5+3

For ( i=1; i<10;i++)

aa[i] = i+a+5;

B: ……………….

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

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

В данной работе реализована подстановка вперед без проверки на эквивалентность. Преобразование проводится для безындексных переменных, а также ограничено для массивов. Ограничение состоит в том, что имя массива рассматривается вместе с индексами, т.е. a[i] и a[i+1] при таком рассмотрении - разные переменные.

Пример 3.2.2:

for ( i = 0 ; i<10 ; i++)

{

a[i] = 5*i+2;

a[i+1] = a[i] +12;

}

После подстановки a[i] в теле цикла имеем

for (i=0; i<10 ;i++)

{

a[i] = 5*i+2;

a[i+1] = 5*i+2+12;


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

РАСЩЕПЛЕНИЕ ВЕРШИН (Введение временных массивов)

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

Алгоритм.

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

Иначе,

1) вводим временный одномерный массив, длина которого равна длине преобразуемого цикла (вставляем в программу оператор описания массива.

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

3) вхождение, соответствующее начальной вершине рассматриваемой дуги антизависимости, заменяем левой частью нового оператора.


Использование программы OPSDemo

Преобразования программ

Графовые представления

Корректность преобразований

Информационная зависимость

Внутреннее представление
Преобразования программ : Канонизация циклов Развертка цикла Расщепление цикла Расщепление вершин (Введение временных массивов) Растягивание скаляров (Замена переменной массивом) Слияние циклов Перестановка заголовков циклов Разрыв итераций и гнездование цикла Переименование скалярных переменных Канонизация условного оператора Канонизация оператора присваивания Подстановка вперед

РАСТЯГИВАНИЕ СКАЛЯРОВ (Замена переменной массивом)

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

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

Алгоритм выполнения замены в цикле переменной на массив выглядит следующим образом.

Предположим, что тело цикла состоит только из операторов присваивания. Будем полагать, что счетчик цикла изменяется от 1 и с шагом 1.

Будем считать для определенности, что имя этого генератора A, а имя счетчика цикла - I.

1) Пусть в теле цикла существует генератор переменной A, не зависящей от счетчика цикла. Подбираем не использованное в данной программе имя для нового массива - предположим, что таким именем является AA. Заметим, что в теле цикла может быть несколько генераторов A. Тогда заменим все вхождения (использования) до первого генератора A на AA(I), а все вхождения A начиная с первого генератора - на AA(I+1). В начало программы следует вставить оператор описания массива AA. Перед заголовком цикла следует поставить оператор присваивания

AA(1)=A.

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

2) Если в теле цикла нет вхождения переменной A, как генератора, то после цикла следует вставить оператор

A=AA(I)

(в фортране после выполнения цикла значение счетчика сохраняется) или оператор

A=AA(N)

где N - последнее значение счетчика цикла.

В противоположном случае (если в теле цикла есть генератор переменной A) после цикла должен быть вставлен оператор

A=AA(I+1)

или

A=AA(N+1)

соответственно.

Теорема. Пусть в теле цикла есть только операторы присваивания. Тогда описанная выше процедура замены переменной массивом равносильна.

Доказательство. Воспользуемся методом математической индукции по количеству итераций цикла. Не умаляя общности, будем считать, что цикл приведен к каноническому виду и имеет N итераций. Если N=1, то справедливость утверждения теоремы проверяется очевидным образом. Заменим исходный и результирующий циклы их раскрутками (напомним, что раскрутка - всегда эквивалентное преобразование). Теперь следует доказать эквивалентность полученных линейных участков программ. Но, если переменная A не является генератором в теле цикла, один линейный участок получается из другого с помощью N переименований: для каждого значения переменной I=1,..,N переменная A заменяется переменной AA(I) на фрагменте участка, соответствующем I-ой итерации тела цикла. Если переменная A в теле цикла хотя бы в одном месте является генератором, один линейный участок получается из другого с помощью N+1 переименований переменной A на переменные AA(I) на фрагментах участков, заключенных между копиями первого генератора переменной A.