Введение
Система программирования PascalABC.NET - это реализация языка Object Pascal, сочетающая простоту языка Паскаль и огромные возможно¬сти платформы .NET. Система активно развивается и активно использует¬ся для обучения студентов и школьников основам программирования.
В апреле 2011 года вышла версия PascalABC.NET 1.7. Основным но¬вовведением стало реализация директив OpenMP, что позволило парал¬лельно выполнять циклы и секции. Директивы OpenMP являются простым механизмом для преобразования последовательной программы в парал-лельную, доступным для понимания начинающих программистов. Но де¬ло в том, что не всегда применение этих директив приводит к эквивалент¬ной программе. Результаты работы программы при последовательном и параллельном выполнении могут отличаться. Распараллеливанию могут мешать различные информационные зависимости, которые порождаются вхождениями переменных. Была поставлена задача: реализовать элементы автоматического распараллеливания в компиляторе PascalABC.NET, кото¬рые позволяют анализировать информационные зависимости внутри гнез¬да циклов и применять различные преобразования с целью получения эк¬вивалентной параллельной программы.
При анализе программы с целью оптимизации (распараллеливания) удобно рассматривать данные об информационных зависимостях этой про¬граммы в виде графов. Существуют как более грубые способы описания зависимостей программы, например, граф информационных зависимостей, так и более тонкие, например, решетчатый граф и развертка решетчатого графа. В этой работе в качестве модели информационной зависимости был использован решетчатый граф. Решетчатый граф - одна из наиболее тон¬ких моделей информационной зависимости. Решетчатый граф в частности позволяет для любой операции в правой части оператора присваивания указать итерацию и генератор, выход которого является аргументом данной операции.
Решетчатый граф строится для линейного класса программ[1, c. 18]. Многие программы могут быть приведены к линейному классу с помощью различных преобразований [3, параграф 8.1]. Например, если в про-грамме встречается произведение внешних переменных, то это произ¬ведение можно заменить новой внешней переменной. Если у некоторого оператора цикла шаг не равен +1, то с помощью канонизации циклов [33, 49] можно получить программу, в которой этот цикл имеет шаг +1. Со¬гласно статистике [3, с. 341], с помощью различных приемов, можно привести к линейному классу 90-95% текста практически используе¬мых программ. Рассмотрение программ, не принадлежащих линейному классу, выходит за рамки данной работы.
В рамках этой работы автором реализовано построение решетчатых графов для гнезд распараллеливаемых циклов в компиляторе Pas- calABC.NET. Эти графы строится на этапе синтактико-семантического преобразования для каждого из циклов, помеченных директивой OpenMP. На основе решетчатых графов определяются ParDO циклы, и, если распа¬раллеливаемый цикл не принадлежит к их числу, выдается предупрежде¬ние, что существуют циклически порожденные зависимости, мешающие распараллеливанию. Кроме того, на основе решетчатых графов автором было реализовано унимодулярное распараллеливающее преобразование двумерных гнезд циклов для компилятора PascalABC.NET.
Работа состоит из 10 глав. В главах 1 и 2 описывается общая про¬блематика задачи. Глава 3 рассказывает об информационной зависимости в программе и модели рассматриваемых программ. В главе 4 подробно рассматриваются различные решетчатые графы, а так алгоритм построения элементарного решетчатого графа. Глава 5 описывает построение расши¬ренной информации о вхождениях переменных. Глава 6 описывает под¬ключение целочисленной библиотеки параметрического программирова¬ния PipLib к компилятору PascalABC.NET. Глава 7 посвящена программ¬ной реализации построения решетчатых графов. Автоматическое распо¬знавание ParDo циклов по решетчатому графу описано в главе 8. В этой же главе рассказывается о программной реализации этого распознавания. Глава 9 посвящена преобразованию циклов с помощью унимодулярных матриц и его реализации в компиляторе PascalABC.NET. Глава 10 описы¬вает реализацию распараллеливания двумерных гнезд тесно вложенных циклов с помощью унимодулярного преобразования
Постановка задачи
Была поставлена задача, включающая в себя следующее:
• построение расширенной информации о вхождениях переменных в теле распараллеливаемого цикла;
• формирование входных данных для библиотеки параметрического программирования PipLib;
• подключение библиотеки PipLib к компилятору PascalABC.NET;
• построение решетчатых графов для фрагмента программы с помо¬щью библиотеки PipLib для компилятора PascalABC.NET;
• определение ParDo циклов по решетчатым графам для фрагмента программы;
• распараллеливание гнезд из двух тесно вложенных циклов с помо¬щью унимодулярного преобразования.
1 Информационная зависимость в программе
Определение. Вхождением переменной будем называть всякое появ¬ление переменной в тексте программы вместе с тем местом в программе, в котором эта переменная появилась [1].
Не умаляя общности, все переменные, кроме счетчиков циклов, можно считать индексными. Всякому вхождению при конкретном значе¬нии индексного выражения соответствует обращение к некоторой ячейке памяти.
Если при этом обращении меняется состояние ячейки (вхождение в левую часть оператора присваивания, которое не входит в индексное вы¬ражение другого вхождения), то такое вхождение называется генерато¬ром. Остальные вхождения называются использованиями.
Пример 1. В следующем операторе присваивания
A[ B[ i + 1] ]:=C[ 2*i - 2 ] + A [ i + 2 ];
v1 v2 v3 v4
четыре вхождения v1, v2, v3, v4 и только вхождение v1 является генера¬тором.
Конец примера 1.
Определение. Два вхождения информационно-зависимы, если об¬ращаются к одной и той же ячейке памяти при некоторых допустимых значениях индексных выражений.
Информационные зависимости делятся на 4 типа:
1) выходная зависимость, если оба вхождения являются генератора¬ми:
2) потоковая или истинная зависимость, если первое вхождение яв¬ляется генератором, а второе вхождение - использованием:
X:=...
. :=X
3) анти зависимость, если первое вхождение является использовани¬ем, а второе вхождение - генератором:
... :=X X:=...
4) входная зависимость, если оба вхождения являются использова¬ния:
... :=X ... :=X Пример 2.
A := B + C; v1 v2 v3 B := A + C; v4 v5 v6 B := 2; v7
В данном программном сегменте имеются следующие отношения за¬висимости:
1) потоковая зависимость использования v5 от генератора v1;
2) анти зависимость генератора v4 от использования v2;
3) выходная зависимость генератора v7 от генератора v4
4) входная зависимость использования v6 от использования v3 Конец примера 2.
Об информационных зависимостях можно прочитать, например, в [8].
3.1 Классификация зависимостей внутри цикла
Определение.([4]) Зависимость называется циклически порождён¬ной, если оба вхождения обращаются к общей ячейке памяти на разных итерациях цикла.
Определение.([4]) Зависимость называется циклически независи¬мой, если оба вхождения обращаются к одной и той же ячейке памяти на одной и той же итерации цикла.
Пример 3.
for var i:=0 to n do begin
A[i]:= X[i]; u1 u2
X[i+1]:= A[i]-A[i-1]; u3 u4 u5
end;
Зависимость, которую порождают вхождения u1 и u4, - циклически неза¬висимая. Зависимости, которые образуют вхождения u2 и u3, u1 и u5 - циклически порожденные.
Конец примера 3.
Условие распараллеливания цикла:
Допускаются только циклически независимые зависимости.
3.2 Модель рассматриваемых программ
Построение решетчатых графов и многие преобразования, на них ос¬нованные, возможны в рамках линейного класса [3, с. 340]. ]. Для полноты изложения опишем этот класс. Это класс программ, включающий в себя следующие элементы языка:
• скалярные и индексные переменные;
• операторы присваивания, правая часть которых является ариф¬метическим выражением;
• все повторяющиеся операции описываются только с помощью циклов for языка программирования Pascal; структура вложенности циклов может быть произвольной; шаги изменения параметров циклов всегда рав¬ны +1(в случае языка программирования Pascal это всегда так); если у цик¬ла нижняя граница больше верхней, то цикл не выполняется;
• условные и безусловные операторы перехода, передающие управление «вниз» по тексту; не допускается использование побочных вы¬ходов из циклов;
• все индексные выражения переменных, границы изменения пара¬метров циклов и условия передачи управления задаются аффинными фор¬мами от совокупности параметров циклов и внешних переменных про¬граммы; все коэффициенты при переменных в этих формах являются це-лыми числами;
• внешние переменные программы всегда целочисленные. Программы, принадлежащие этому классу, называются линейными.
Определение. Внешние переменные фрагмента программы - пе¬ременные, значения которых в этом фрагменте не изменяются и не мо¬гут быть определены на момент компиляции программы.
Пример 4. Следующий фрагмент принадлежит линейному классу про¬грамм:
for var i:=0 to N do begin
a[N-i+1] := 2*b[3*i]; end;
Конец примера 4.
Пример 5. Следующий фрагмент не принадлежит линейному классу про¬грамм:
for var i := 0 to N do
for var j := 0 to a[i] do begin
a[i + 2 * j] := b[i * j];
end;
Конец примера 5
по следующим причинам:
1. условие окончания работы второго цикла не аффинное;
2. индексное выражение массива b относительно счетчиков циклов
не является аффинным.
В частности, следует отметить, что программы нахождения макси¬мального элемента массива или сортировки не принадлежат линейному классу. Многие оптимизируемые (требующие больших объемов вычисле¬ний) участки программ классических численных методов принадлежат линейному классу или сводятся к таким. Не относятся к линейному клас¬су программы для метода конечных элементов, поскольку матрицы в этих случаях разреженные и работа с ними предполагает косвенную адреса- цию.[4]
В защиту линейного класса программ заметим, что большинство оп¬тимизирующих/распараллеливающих преобразований программ, как пра¬вило, носят локальный, а не глобальный характер. А это означает, что тре-бования линейности предъявляются не ко всей программе, а только к оптимизируемому фрагменту.
Последний аргумент в пользу исследований линейного класса программ состоит в том, что традиционный граф информационных связей, который основан на неравенствах Банерджи или Омега-тесте, строится тоже только для линейного класса. [4]
2 Решетчатый граф, как модель информационной за¬висимости в гнездах циклов
При анализе программы с целью оптимизации (распараллеливания) удобно рассматривать данные об информационных зависимостях этой про¬граммы в виде графов. Существуют как более грубые способы описания зависимостей программы, например, граф информационных зависимостей, так и более тонкие, например, решетчатый граф и развертка решетчатого графа. В этом параграфе будут рассмотрены решетчатые графы.
Решетчатый граф - одна из наиболее тонких моделей информацион¬ной зависимости. Решетчатый граф в частности позволяет для любой опе¬рации в правой части оператора присваивания указать итерацию и генера¬тор, выход которого является аргументом данной операции. Описание решетчатых графов в этом параграфе большей частью основано на [1,3,4].
2.1 Опорные пространства
Рассмотрим некоторый фрагмент программы из линейного класса. Занумеруем операторы циклов в этом фрагменте сверху вниз по тексту программы. Обозначим счетчик i-го цикла - /.
Определение. ([1]) Множество всех вложенных друг в друга циклов, в теле каждого из которых содержится некоторый оператор Stmt, назы¬вают опорным гнездом циклов для оператора Stmt и для всех вхождений, которые этот оператор содержит.
Определение. Множество значений вектора счетчиков циклов опорного гнезда, при которых исполняется оператор Stmt, будем называть опорным пространством для данного оператора и всех вхождений пере¬менных, которые он содержит.
Далее будем считать, что в каждой строке программы находится только один оператор. Занумеруем все операторы присваивания фрагмента программы сверху вниз по тексту программы и обозначим их через , Stmt2, ..., Stmtm
Обозначим опорное пространство оператора через .
Определение. ([1]) Пространством итераций фрагмента програм¬мы назовем совокупность опорных пространств Vj для /=1, 2, ..., т.
Пример 6. Рассмотрим гнездо циклов:
for var i1 := L1 to U1 do
for var i2 := L2 to U2 do
for var in := Ln to Un do loopbody(i1,i2,...,in);
Пространство итераций этого многомерного цикла (11) - это множество всех таких целочисленных векторов:
{( ) ] Границы L j, Uj изменения счетчиков циклов / могут линейно зависеть от счетчиков объемлющих циклов. В этом случае пространство итераций многомерного цикла является целочисленным многогранником в n-мерном пространстве.
Конец примера 6.
Определение. Пусть имеются векторы ( ) , и
(J i'J2> ■ ■ ■ Jn2). Пусть m — m i п(щ,п2). Тогда:
1. если существует k £ [ 1 ,m], что /1 — /2 — J, /к-1 —Jk-1, /k<Jk, то будем говорить, что вектор / лексикографически меньше вектора J. Будем обозначать этот факт I < J ;
2. если и для любого [ ] , то будем говорить, что вектор лексикографически равен вектору и обозначать ; [1]
Пример 7.
Пусть / — ( 1 , 2 , 3 , 8 , 5 ) и J— ( 1 , 2 , 3 , 4 , 5 ). Вектор J будет лексикографи¬чески меньше вектора , поскольку при совпадающих первых трех коор¬динатах, третья координата вектора строго меньше, третьей координаты вектора /. Значения всех последующих координат уже не важны.
Конец примера 7.
При последовательном выполнении гнезда циклов, точки про¬странства итераций просматриваются в лексикографическом порядке - это вытекает из семантики оператора цикла языка программирования Pascal.
2.2 Максимальные и минимальные решетчатые графы
Определение. ([1]) Множество вершин максимального решетчатого графа - все точки пространства итераций фрагмента программы. Дуга направляется из вершины / £ V j в вершину J £ Vj, если / < J, и существуют такие вхождения и , что [ ] и [ ] обращаются к од¬
ной и той же ячейке памяти. При этом говорят, что вхождение и определя¬ет начало дуги, а вхождение v - конец дуги.
В зависимости от того, чем являются вхождения и и v (генератором или использованием), различают максимальные решетчатые графы потоковой, выходной, анти - и входной зависимости.
Определение минимальных решетчатых графов дадим конструк¬тивно ([1]).
Возьмем максимальный решетчатый граф зависимости типа Т. Для каж¬дой вершины s этого графа выполним:
1. разобьем множество дуг, входящих в вершину s на группы: к одной группе отнесем дуги, конец которых определялся одним и тем же вхожде¬нием;
2. в каждой группе выберем одну дугу, у которой начальная вершина лек¬сикографически ближе всего к вершине s; остальные дуги удалим.
Полученный граф называется минимальным снизу решетчатым графом зависимости типа Т.
Для зависимостей по выходу и по входу минимальные снизу и сверху решетчатые графы совпадают [3, с. 347]. В общем случае для анти- и пото¬ковой зависимости минимальные сверху и снизу решетчатые графы разли¬чаются [3, с. 347].
Пример 8. Рассмотрим следующий фрагмент программы:
for var i := 1 to 10 do begin
y[i] := x[i + 1]; u1
z[i] := x[i]; u2
x[i] := 5; u3 end;
В этом цикле имеется анти зависимость вхождения u3 от вхож¬дений u1, и2.Других анти зависимостей нет. Часть минимального сни¬зу решетчатого графа анти зависимости для данного цикла изображена на рисунке 1.а, минимального сверху решетчатого графа анти зависимо¬сти изображена на рисунке 1. б.
Рис.1. Решетчатые графы анти зависимости а) минимальный снизу и б) минимальный сверху.
Из приведенного примера видно, что эти графы не совпадают.
Конец примера 8.
В компиляторе PascalABC.NET автором реализовано построение ми¬нимальных сверху и минимальных снизу решетчатых графов.
2.3 Элементарные и полные решетчатые графы. Способы хранения
Определение решетчатого графа истинной зависимости пере-
менной.([4])Пусть задан фрагмент программы и некоторая переменная (м.б. индексная) X. Множество вершин решетчатого графа истинной зави¬симости переменной - это пространство итераций заданного фрагмента. Две точки пространства итераций I и J соединяются дугой, если
1. в графе информационных связей существует дуга истинной зави¬симости (u1, v1), решетчатый граф которой содержит дугу (I,J);
2. для любой другой дуги (u2, v1) истинной зависимости графа ин¬формационных связей, решетчатый граф которой содержит некоторую дугу (I2,J) , входящую в вершину J, точка пространства итераций I2 лек-сикографически меньше I, либо I2 = I, но вхождение и2 в тексте про¬граммы встречается всегда раньше вхождения u.
Аналогично определяются решетчатые графы переменной для ан- ти зависимости, выходной зависимости и входной зависимости.
Определение (полного) решетчатого графа фрагмента про¬граммы.^]) Решетчатый граф фрагмента программы - это граф, верши¬нами которого являются все точки пространства итераций, а множество дуг является объединением множеств дуг решетчатых графов всех пере-менных данного фрагмента.
Из определения решетчатого графа вытекает следующее свойство:
• в каждую вершину элементарного решетчатого графа входит не более одной дуги.
Из этого свойства вытекает возможность хранения решетчатого графа в виде отображения подмножества пространства итераций в про¬странство итераций: концу дуги решетчатого графа сопоставляется начало этой дуги.
Традиционные способы хранения графов в виде матрицы смежно¬стей или списка дуг не приемлемы для решетчатых графов. Действи¬тельно, для гнезд циклов реальных долго считаемых программ количе¬ство дуг решетчатого графа может быть так велико, что прочтение всех дуг может потребовать время, сравнимое со временем последовательного выполнения исходной программы, и распараллеливание, основанное на та¬ком графе, потеряет смысл.
Функция, описывающая решетчатый граф, может занимать объем, не зависящий от размерностей циклов, описывающих пространство ите¬раций. Эта функция является кусочно-квазилинейной. «Квази-линейная» - это значит, что кроме линейных операций над счетчиками циклов эта функция допускает взятие целой части числа или условные операторы. Во многих практически важных случаях эта функция оказывается кусочно- линейной[4, с. 83].
4.4 Построение решетчатого графа
Все минимальные решетчатые графы строятся на основе элемен¬тарных решетчатых графов. Поэтому здесь будет детально рассмотрен процесс построения элементарного решетчатого графа. Для упрощения изложения будем считать, что рассматриваемые фрагменты программ не содержат внешних переменных. Материал этого параграфа в значительной степени опирается на работы [1,c.68],[3, с.363].
Пусть вхождение и содержится в гнезде из n циклов, пространство итераций которого . Вхождение v - в гнезде из m циклов, пространство итераций которого . Пусть оператор, содержащий вхождение u находит¬ся раньше по тексту программы, чем оператор, содержащий вхождение v. Обозначим через P(I) вектор, координатами которого являются индексы вхождения и, через Q(J) - вектор индексов вхождения v.
Рассмотрим задачу построения элементарного решетчатого графа [1, с. 69], описывающего зависимость вхождения v от вхождения и. Зафик¬сируем некоторую вершину . Чтобы из вершины выходила ду¬га в вершину , необходимо выполнение условий:
Р(/) — Q (J) , (1)
/evu Jev2, (2)
(3)
Система (1) при условиях (2), (3) может иметь неединственное реше¬ние. На множестве всевозможных решений I из (1), (2), (3) нужно найти то решение /0, которое является лексикографически максимальным (lex.max). Такое решение
/0 — I ex .max/ (4)
является единственным.
Для того чтобы решить указанную задачу, сначала нужно свести условия (1),(2), (3) к совокупности систем линейных неравенств. Условия ( ) ( ) и , сводятся к системе линейных неравенств
как обычно в линейном программировании. Равенство ( ) ( ) за¬меняется на два линейных неравенства:
( ) ( )
- Р(/) > -Q (J)
Условия , в случае цикла задаются его границами в виде ли¬
нейных неравенств.
Рассмотрим подробно, как сводится к совокупности систем линейных не¬равенств условие / < 1 ех J. Пусть два указанных вхождения и и v имеют d общих циклов. Системы неравенств, к которым сводится условие / <iexJ, называются альтернативными многогранниками [3, с. 365]. Пер¬вая...
Система программирования PascalABC.NET - это реализация языка Object Pascal, сочетающая простоту языка Паскаль и огромные возможно¬сти платформы .NET. Система активно развивается и активно использует¬ся для обучения студентов и школьников основам программирования.
В апреле 2011 года вышла версия PascalABC.NET 1.7. Основным но¬вовведением стало реализация директив OpenMP, что позволило парал¬лельно выполнять циклы и секции. Директивы OpenMP являются простым механизмом для преобразования последовательной программы в парал-лельную, доступным для понимания начинающих программистов. Но де¬ло в том, что не всегда применение этих директив приводит к эквивалент¬ной программе. Результаты работы программы при последовательном и параллельном выполнении могут отличаться. Распараллеливанию могут мешать различные информационные зависимости, которые порождаются вхождениями переменных. Была поставлена задача: реализовать элементы автоматического распараллеливания в компиляторе PascalABC.NET, кото¬рые позволяют анализировать информационные зависимости внутри гнез¬да циклов и применять различные преобразования с целью получения эк¬вивалентной параллельной программы.
При анализе программы с целью оптимизации (распараллеливания) удобно рассматривать данные об информационных зависимостях этой про¬граммы в виде графов. Существуют как более грубые способы описания зависимостей программы, например, граф информационных зависимостей, так и более тонкие, например, решетчатый граф и развертка решетчатого графа. В этой работе в качестве модели информационной зависимости был использован решетчатый граф. Решетчатый граф - одна из наиболее тон¬ких моделей информационной зависимости. Решетчатый граф в частности позволяет для любой операции в правой части оператора присваивания указать итерацию и генератор, выход которого является аргументом данной операции.
Решетчатый граф строится для линейного класса программ[1, c. 18]. Многие программы могут быть приведены к линейному классу с помощью различных преобразований [3, параграф 8.1]. Например, если в про-грамме встречается произведение внешних переменных, то это произ¬ведение можно заменить новой внешней переменной. Если у некоторого оператора цикла шаг не равен +1, то с помощью канонизации циклов [33, 49] можно получить программу, в которой этот цикл имеет шаг +1. Со¬гласно статистике [3, с. 341], с помощью различных приемов, можно привести к линейному классу 90-95% текста практически используе¬мых программ. Рассмотрение программ, не принадлежащих линейному классу, выходит за рамки данной работы.
В рамках этой работы автором реализовано построение решетчатых графов для гнезд распараллеливаемых циклов в компиляторе Pas- calABC.NET. Эти графы строится на этапе синтактико-семантического преобразования для каждого из циклов, помеченных директивой OpenMP. На основе решетчатых графов определяются ParDO циклы, и, если распа¬раллеливаемый цикл не принадлежит к их числу, выдается предупрежде¬ние, что существуют циклически порожденные зависимости, мешающие распараллеливанию. Кроме того, на основе решетчатых графов автором было реализовано унимодулярное распараллеливающее преобразование двумерных гнезд циклов для компилятора PascalABC.NET.
Работа состоит из 10 глав. В главах 1 и 2 описывается общая про¬блематика задачи. Глава 3 рассказывает об информационной зависимости в программе и модели рассматриваемых программ. В главе 4 подробно рассматриваются различные решетчатые графы, а так алгоритм построения элементарного решетчатого графа. Глава 5 описывает построение расши¬ренной информации о вхождениях переменных. Глава 6 описывает под¬ключение целочисленной библиотеки параметрического программирова¬ния PipLib к компилятору PascalABC.NET. Глава 7 посвящена программ¬ной реализации построения решетчатых графов. Автоматическое распо¬знавание ParDo циклов по решетчатому графу описано в главе 8. В этой же главе рассказывается о программной реализации этого распознавания. Глава 9 посвящена преобразованию циклов с помощью унимодулярных матриц и его реализации в компиляторе PascalABC.NET. Глава 10 описы¬вает реализацию распараллеливания двумерных гнезд тесно вложенных циклов с помощью унимодулярного преобразования
Постановка задачи
Была поставлена задача, включающая в себя следующее:
• построение расширенной информации о вхождениях переменных в теле распараллеливаемого цикла;
• формирование входных данных для библиотеки параметрического программирования PipLib;
• подключение библиотеки PipLib к компилятору PascalABC.NET;
• построение решетчатых графов для фрагмента программы с помо¬щью библиотеки PipLib для компилятора PascalABC.NET;
• определение ParDo циклов по решетчатым графам для фрагмента программы;
• распараллеливание гнезд из двух тесно вложенных циклов с помо¬щью унимодулярного преобразования.
1 Информационная зависимость в программе
Определение. Вхождением переменной будем называть всякое появ¬ление переменной в тексте программы вместе с тем местом в программе, в котором эта переменная появилась [1].
Не умаляя общности, все переменные, кроме счетчиков циклов, можно считать индексными. Всякому вхождению при конкретном значе¬нии индексного выражения соответствует обращение к некоторой ячейке памяти.
Если при этом обращении меняется состояние ячейки (вхождение в левую часть оператора присваивания, которое не входит в индексное вы¬ражение другого вхождения), то такое вхождение называется генерато¬ром. Остальные вхождения называются использованиями.
Пример 1. В следующем операторе присваивания
A[ B[ i + 1] ]:=C[ 2*i - 2 ] + A [ i + 2 ];
v1 v2 v3 v4
четыре вхождения v1, v2, v3, v4 и только вхождение v1 является генера¬тором.
Конец примера 1.
Определение. Два вхождения информационно-зависимы, если об¬ращаются к одной и той же ячейке памяти при некоторых допустимых значениях индексных выражений.
Информационные зависимости делятся на 4 типа:
1) выходная зависимость, если оба вхождения являются генератора¬ми:
2) потоковая или истинная зависимость, если первое вхождение яв¬ляется генератором, а второе вхождение - использованием:
X:=...
. :=X
3) анти зависимость, если первое вхождение является использовани¬ем, а второе вхождение - генератором:
... :=X X:=...
4) входная зависимость, если оба вхождения являются использова¬ния:
... :=X ... :=X Пример 2.
A := B + C; v1 v2 v3 B := A + C; v4 v5 v6 B := 2; v7
В данном программном сегменте имеются следующие отношения за¬висимости:
1) потоковая зависимость использования v5 от генератора v1;
2) анти зависимость генератора v4 от использования v2;
3) выходная зависимость генератора v7 от генератора v4
4) входная зависимость использования v6 от использования v3 Конец примера 2.
Об информационных зависимостях можно прочитать, например, в [8].
3.1 Классификация зависимостей внутри цикла
Определение.([4]) Зависимость называется циклически порождён¬ной, если оба вхождения обращаются к общей ячейке памяти на разных итерациях цикла.
Определение.([4]) Зависимость называется циклически независи¬мой, если оба вхождения обращаются к одной и той же ячейке памяти на одной и той же итерации цикла.
Пример 3.
for var i:=0 to n do begin
A[i]:= X[i]; u1 u2
X[i+1]:= A[i]-A[i-1]; u3 u4 u5
end;
Зависимость, которую порождают вхождения u1 и u4, - циклически неза¬висимая. Зависимости, которые образуют вхождения u2 и u3, u1 и u5 - циклически порожденные.
Конец примера 3.
Условие распараллеливания цикла:
Допускаются только циклически независимые зависимости.
3.2 Модель рассматриваемых программ
Построение решетчатых графов и многие преобразования, на них ос¬нованные, возможны в рамках линейного класса [3, с. 340]. ]. Для полноты изложения опишем этот класс. Это класс программ, включающий в себя следующие элементы языка:
• скалярные и индексные переменные;
• операторы присваивания, правая часть которых является ариф¬метическим выражением;
• все повторяющиеся операции описываются только с помощью циклов for языка программирования Pascal; структура вложенности циклов может быть произвольной; шаги изменения параметров циклов всегда рав¬ны +1(в случае языка программирования Pascal это всегда так); если у цик¬ла нижняя граница больше верхней, то цикл не выполняется;
• условные и безусловные операторы перехода, передающие управление «вниз» по тексту; не допускается использование побочных вы¬ходов из циклов;
• все индексные выражения переменных, границы изменения пара¬метров циклов и условия передачи управления задаются аффинными фор¬мами от совокупности параметров циклов и внешних переменных про¬граммы; все коэффициенты при переменных в этих формах являются це-лыми числами;
• внешние переменные программы всегда целочисленные. Программы, принадлежащие этому классу, называются линейными.
Определение. Внешние переменные фрагмента программы - пе¬ременные, значения которых в этом фрагменте не изменяются и не мо¬гут быть определены на момент компиляции программы.
Пример 4. Следующий фрагмент принадлежит линейному классу про¬грамм:
for var i:=0 to N do begin
a[N-i+1] := 2*b[3*i]; end;
Конец примера 4.
Пример 5. Следующий фрагмент не принадлежит линейному классу про¬грамм:
for var i := 0 to N do
for var j := 0 to a[i] do begin
a[i + 2 * j] := b[i * j];
end;
Конец примера 5
по следующим причинам:
1. условие окончания работы второго цикла не аффинное;
2. индексное выражение массива b относительно счетчиков циклов
не является аффинным.
В частности, следует отметить, что программы нахождения макси¬мального элемента массива или сортировки не принадлежат линейному классу. Многие оптимизируемые (требующие больших объемов вычисле¬ний) участки программ классических численных методов принадлежат линейному классу или сводятся к таким. Не относятся к линейному клас¬су программы для метода конечных элементов, поскольку матрицы в этих случаях разреженные и работа с ними предполагает косвенную адреса- цию.[4]
В защиту линейного класса программ заметим, что большинство оп¬тимизирующих/распараллеливающих преобразований программ, как пра¬вило, носят локальный, а не глобальный характер. А это означает, что тре-бования линейности предъявляются не ко всей программе, а только к оптимизируемому фрагменту.
Последний аргумент в пользу исследований линейного класса программ состоит в том, что традиционный граф информационных связей, который основан на неравенствах Банерджи или Омега-тесте, строится тоже только для линейного класса. [4]
2 Решетчатый граф, как модель информационной за¬висимости в гнездах циклов
При анализе программы с целью оптимизации (распараллеливания) удобно рассматривать данные об информационных зависимостях этой про¬граммы в виде графов. Существуют как более грубые способы описания зависимостей программы, например, граф информационных зависимостей, так и более тонкие, например, решетчатый граф и развертка решетчатого графа. В этом параграфе будут рассмотрены решетчатые графы.
Решетчатый граф - одна из наиболее тонких моделей информацион¬ной зависимости. Решетчатый граф в частности позволяет для любой опе¬рации в правой части оператора присваивания указать итерацию и генера¬тор, выход которого является аргументом данной операции. Описание решетчатых графов в этом параграфе большей частью основано на [1,3,4].
2.1 Опорные пространства
Рассмотрим некоторый фрагмент программы из линейного класса. Занумеруем операторы циклов в этом фрагменте сверху вниз по тексту программы. Обозначим счетчик i-го цикла - /.
Определение. ([1]) Множество всех вложенных друг в друга циклов, в теле каждого из которых содержится некоторый оператор Stmt, назы¬вают опорным гнездом циклов для оператора Stmt и для всех вхождений, которые этот оператор содержит.
Определение. Множество значений вектора счетчиков циклов опорного гнезда, при которых исполняется оператор Stmt, будем называть опорным пространством для данного оператора и всех вхождений пере¬менных, которые он содержит.
Далее будем считать, что в каждой строке программы находится только один оператор. Занумеруем все операторы присваивания фрагмента программы сверху вниз по тексту программы и обозначим их через , Stmt2, ..., Stmtm
Обозначим опорное пространство оператора через .
Определение. ([1]) Пространством итераций фрагмента програм¬мы назовем совокупность опорных пространств Vj для /=1, 2, ..., т.
Пример 6. Рассмотрим гнездо циклов:
for var i1 := L1 to U1 do
for var i2 := L2 to U2 do
for var in := Ln to Un do loopbody(i1,i2,...,in);
Пространство итераций этого многомерного цикла (11) - это множество всех таких целочисленных векторов:
{( ) ] Границы L j, Uj изменения счетчиков циклов / могут линейно зависеть от счетчиков объемлющих циклов. В этом случае пространство итераций многомерного цикла является целочисленным многогранником в n-мерном пространстве.
Конец примера 6.
Определение. Пусть имеются векторы ( ) , и
(J i'J2> ■ ■ ■ Jn2). Пусть m — m i п(щ,п2). Тогда:
1. если существует k £ [ 1 ,m], что /1 — /2 — J, /к-1 —Jk-1, /k<Jk, то будем говорить, что вектор / лексикографически меньше вектора J. Будем обозначать этот факт I < J ;
2. если и для любого [ ] , то будем говорить, что вектор лексикографически равен вектору и обозначать ; [1]
Пример 7.
Пусть / — ( 1 , 2 , 3 , 8 , 5 ) и J— ( 1 , 2 , 3 , 4 , 5 ). Вектор J будет лексикографи¬чески меньше вектора , поскольку при совпадающих первых трех коор¬динатах, третья координата вектора строго меньше, третьей координаты вектора /. Значения всех последующих координат уже не важны.
Конец примера 7.
При последовательном выполнении гнезда циклов, точки про¬странства итераций просматриваются в лексикографическом порядке - это вытекает из семантики оператора цикла языка программирования Pascal.
2.2 Максимальные и минимальные решетчатые графы
Определение. ([1]) Множество вершин максимального решетчатого графа - все точки пространства итераций фрагмента программы. Дуга направляется из вершины / £ V j в вершину J £ Vj, если / < J, и существуют такие вхождения и , что [ ] и [ ] обращаются к од¬
ной и той же ячейке памяти. При этом говорят, что вхождение и определя¬ет начало дуги, а вхождение v - конец дуги.
В зависимости от того, чем являются вхождения и и v (генератором или использованием), различают максимальные решетчатые графы потоковой, выходной, анти - и входной зависимости.
Определение минимальных решетчатых графов дадим конструк¬тивно ([1]).
Возьмем максимальный решетчатый граф зависимости типа Т. Для каж¬дой вершины s этого графа выполним:
1. разобьем множество дуг, входящих в вершину s на группы: к одной группе отнесем дуги, конец которых определялся одним и тем же вхожде¬нием;
2. в каждой группе выберем одну дугу, у которой начальная вершина лек¬сикографически ближе всего к вершине s; остальные дуги удалим.
Полученный граф называется минимальным снизу решетчатым графом зависимости типа Т.
Для зависимостей по выходу и по входу минимальные снизу и сверху решетчатые графы совпадают [3, с. 347]. В общем случае для анти- и пото¬ковой зависимости минимальные сверху и снизу решетчатые графы разли¬чаются [3, с. 347].
Пример 8. Рассмотрим следующий фрагмент программы:
for var i := 1 to 10 do begin
y[i] := x[i + 1]; u1
z[i] := x[i]; u2
x[i] := 5; u3 end;
В этом цикле имеется анти зависимость вхождения u3 от вхож¬дений u1, и2.Других анти зависимостей нет. Часть минимального сни¬зу решетчатого графа анти зависимости для данного цикла изображена на рисунке 1.а, минимального сверху решетчатого графа анти зависимо¬сти изображена на рисунке 1. б.
Рис.1. Решетчатые графы анти зависимости а) минимальный снизу и б) минимальный сверху.
Из приведенного примера видно, что эти графы не совпадают.
Конец примера 8.
В компиляторе PascalABC.NET автором реализовано построение ми¬нимальных сверху и минимальных снизу решетчатых графов.
2.3 Элементарные и полные решетчатые графы. Способы хранения
Определение решетчатого графа истинной зависимости пере-
менной.([4])Пусть задан фрагмент программы и некоторая переменная (м.б. индексная) X. Множество вершин решетчатого графа истинной зави¬симости переменной - это пространство итераций заданного фрагмента. Две точки пространства итераций I и J соединяются дугой, если
1. в графе информационных связей существует дуга истинной зави¬симости (u1, v1), решетчатый граф которой содержит дугу (I,J);
2. для любой другой дуги (u2, v1) истинной зависимости графа ин¬формационных связей, решетчатый граф которой содержит некоторую дугу (I2,J) , входящую в вершину J, точка пространства итераций I2 лек-сикографически меньше I, либо I2 = I, но вхождение и2 в тексте про¬граммы встречается всегда раньше вхождения u.
Аналогично определяются решетчатые графы переменной для ан- ти зависимости, выходной зависимости и входной зависимости.
Определение (полного) решетчатого графа фрагмента про¬граммы.^]) Решетчатый граф фрагмента программы - это граф, верши¬нами которого являются все точки пространства итераций, а множество дуг является объединением множеств дуг решетчатых графов всех пере-менных данного фрагмента.
Из определения решетчатого графа вытекает следующее свойство:
• в каждую вершину элементарного решетчатого графа входит не более одной дуги.
Из этого свойства вытекает возможность хранения решетчатого графа в виде отображения подмножества пространства итераций в про¬странство итераций: концу дуги решетчатого графа сопоставляется начало этой дуги.
Традиционные способы хранения графов в виде матрицы смежно¬стей или списка дуг не приемлемы для решетчатых графов. Действи¬тельно, для гнезд циклов реальных долго считаемых программ количе¬ство дуг решетчатого графа может быть так велико, что прочтение всех дуг может потребовать время, сравнимое со временем последовательного выполнения исходной программы, и распараллеливание, основанное на та¬ком графе, потеряет смысл.
Функция, описывающая решетчатый граф, может занимать объем, не зависящий от размерностей циклов, описывающих пространство ите¬раций. Эта функция является кусочно-квазилинейной. «Квази-линейная» - это значит, что кроме линейных операций над счетчиками циклов эта функция допускает взятие целой части числа или условные операторы. Во многих практически важных случаях эта функция оказывается кусочно- линейной[4, с. 83].
4.4 Построение решетчатого графа
Все минимальные решетчатые графы строятся на основе элемен¬тарных решетчатых графов. Поэтому здесь будет детально рассмотрен процесс построения элементарного решетчатого графа. Для упрощения изложения будем считать, что рассматриваемые фрагменты программ не содержат внешних переменных. Материал этого параграфа в значительной степени опирается на работы [1,c.68],[3, с.363].
Пусть вхождение и содержится в гнезде из n циклов, пространство итераций которого . Вхождение v - в гнезде из m циклов, пространство итераций которого . Пусть оператор, содержащий вхождение u находит¬ся раньше по тексту программы, чем оператор, содержащий вхождение v. Обозначим через P(I) вектор, координатами которого являются индексы вхождения и, через Q(J) - вектор индексов вхождения v.
Рассмотрим задачу построения элементарного решетчатого графа [1, с. 69], описывающего зависимость вхождения v от вхождения и. Зафик¬сируем некоторую вершину . Чтобы из вершины выходила ду¬га в вершину , необходимо выполнение условий:
Р(/) — Q (J) , (1)
/evu Jev2, (2)
(3)
Система (1) при условиях (2), (3) может иметь неединственное реше¬ние. На множестве всевозможных решений I из (1), (2), (3) нужно найти то решение /0, которое является лексикографически максимальным (lex.max). Такое решение
/0 — I ex .max/ (4)
является единственным.
Для того чтобы решить указанную задачу, сначала нужно свести условия (1),(2), (3) к совокупности систем линейных неравенств. Условия ( ) ( ) и , сводятся к системе линейных неравенств
как обычно в линейном программировании. Равенство ( ) ( ) за¬меняется на два линейных неравенства:
( ) ( )
- Р(/) > -Q (J)
Условия , в случае цикла задаются его границами в виде ли¬
нейных неравенств.
Рассмотрим подробно, как сводится к совокупности систем линейных не¬равенств условие / < 1 ех J. Пусть два указанных вхождения и и v имеют d общих циклов. Системы неравенств, к которым сводится условие / <iexJ, называются альтернативными многогранниками [3, с. 365]. Пер¬вая...
Показать текст полностью
