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

На правах рукописи

Шульженко Александр Михайлович

ИССЛЕДОВАНИЕ ИНФОРМАЦИОННЫХ ЗАВИСИМОСТЕЙ ПРОГРАММ ДЛЯ РАСПАРАЛЛЕЛИВАЮЩИХ ПРЕОБРАЗОВАНИЙ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

г. Ростов-на-Дону - 2006 г.

Работа выполнена на кафедре алгебры и дискретной математики механико-математического факультета. Ростовского государственного университета.

Научный руководитель - доктор технических наук,

доцент,

Штейнберг Борис Яковлевич

Официальные оппоненты - доктор технических наук,

профессор,

Белявский Григорий Исаакович

кандидат технических наук, доцент,

Лазарева Светлана Александровна

Ведущая организация - Институт системного программирования РАН

Защита состоится

"/¿Г"

июня 2006 г. в 11 час. на заседании диссертационного совета К212.208.04 Южно-Российского регионального центра информатизации при Ростовском государственном университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, корп. 2, ЮГИНФО РГУ.

С диссертацией можно ознакомиться в Зональной научной библиотеке РГУ по адресу г. Ростов-на-Дону, уч. Пушкинская, 148.

Автореферат разослан " мая 2006 г.

Ученый секретарь совета

кандидат физ.-мат. наук, доцент С^Ьыу^.— Муратова Галина Викторовна

ЛооС А

Общая характеристика работы

Актуальность темы

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

В последнее время принципы параллельных ЭВМ все больше использу-» ются в персональных компьютерах, которые становятся все доступнее. Так, на-

пример, процессоры Intel Pentium-4 и Itanium используют технологию Hyper Threading. В настоящее время в широкой продаже имеются персональные компьютеры на базе процессоров Intel Pentium D, Intel Pentium Extreme Edition, AMD Athlon 64 X2, которые имеют двуядерную архитектуру. В дальнейшем ожидается увеличение производительности персональных компьютеров за счет увеличения количества ядер, расположенных на одном кристалле.

Для того чтобы программа выполнялась на параллельном компьютере быстрее, чем на последовательном, она должна быть специальным образом написана. Процесс разработки эффективных программ для параллельных компьютеров довольно трудоёмкий. Он требует применения специальных параллельных языков, библиотек или распараллеливающих компиляторов. В настоящее время разработано и разрабатывается большое количество средств создания параллельных программ, например, Т-система (ИПС РАН, под руководством С.М. Абрамова), система программирования трС (ИСП РАН), среда ParJava (ИСП РАН), язык НОРМА (ИПМ им. М.В. Келдыша РАН), система DVM (ИПМ им. М.В. Келдыша РАН) и др. Однако, использование распараллеливающих компиляторов является наиболее удобным для пользователя т к. в этом случае пользователю достаточно подать последовательную программу на вход такому компилятору, чтобы получить параллельную.

Разработка распараллеливающих компиляторов — одна из задач автоматического распараллеливания. Для её решения необходима детальная информация о структуре последовательной программы, взаимодействии отдельных операций между собой и с памятью. Неотъемлемой частью получения этой информации является анализ информационных зависимостей программы. Одним из наиболее тонких представлений информационной зависимости является решетчатый граф (граф алгоритма). В нашей стране методы распараллеливания, основанные на анализе решетчатого графа, активно исследуются академиком РАН В.В. Воеводиным и его учениками. Работать с этим графом, используя традиционные методы хранения, такие как матрица смежностей или список дуг, сложно из-за его больших размеров: число вершин решетчатого графа сопоставимо с числом исполняемых операций в программе. В.В. Воеводин предложил хранить этот граф в виде конечного числа аффинных отображений, описываю-

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург ^ ОЭ 200(£акт m

щих дуги графа, а также разработал алгоритм, позволяющий вычислять эти отображения. На основе данного алгоритма, под руководством чл.-корр. РАН Вл. В. Воеводина (НИВЦ МГУ), реализована исследовательская система V-Ray, предназначенная для выявления параллелизма в последовательных ФОРТРАН программах. Из других исследователей, внесших значительный вклад в теорию решетчатых графов, следует отметить П. Фотрье (P. Feautrier, Франция), который разработал алгоритм построения решетчатого графа в виде квазиаффинного дерева решений. До появления указанных алгоритмов построения решетчатого графа, применимых к широкому классу программ, этот граф использовался лишь в частных случаях, например, в методе гиперплоскостей Лампорта и методе параллелепипедов В.А. Вальковского.

Технологии, основанные ка развертке решетчатого графа, исследуются и используются для оптимизации/распараллеливания В. Пухом (W.Pugh), M. Лэм (M.Lam), А. Дарте (A. Darte), H.A. Лиходедом, A.B. Фроловым, A.C. Антоновым и многими другими. Несмотря на то, что теория решетчатых графов уже довольно давно разрабатывается, она не часто используется в распараллеливающих компиляторах и системах. Автору известно только четыре распараллеливающие системы, в которых используются решетчатые графы (или развертки решетчатого графа): V-Ray, PIPS, SUIF, LooPo, которые являются исследовательскими. Возможно, редкое использование теории решетчатых графов на практике связано со сложностью методов их использования и построения. Кроме этого, еще не достаточно разработаны оптимизирующие и распараллеливающие преобразования программ, которые могут быть реализованы только с помощью решетчатых графов.

Цель работы

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

Из сформулированной цели вытекают следующие задачи:

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

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

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

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

Методы исследований.

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

Научная новизна.

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

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

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

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

5. Выявлена связь между минимальными решетчатыми графами и носителями информационной зависимости по значению (dataflow, value-based dependence). Для решетчатых графов, описывающих потоковую зависимость, эта связь указывалась в одной из работ П. Фотрье. Однако в ней

б

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

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

Практическая значимость.

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

Часть исследований диссертации поддерживалась грантами:

• ФЦП «Интеграция» 2002-2006 гг., гос. контракт - Б0024/2148, «Разработка комплекса программных средств для высокопроизводительных вычислений».

• Грант Союзного Российско-Беларусского государства (шифр «ТРИАДА»), 2005 г.

Апробация работы и публикации.

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

• Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция/ Дивноморское, 22-27 сентября 2003 г.

• Научно-методическая конференция «Современные информационные технологии в образовании: Южный федеральный округ», Ростов-на-Дону, 12-15 мая 2004 г.

• Всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 21-25 июня 2004 г.

• XIII Международная конференция «Математика. Экономика. Образование.», г. Новороссийск, 29 мая - 5 июня 2005 г.

• Всероссийская научная конференция «Научный сервис в сети Интернет: технологии распределенных вычислений», г. Новороссийск, 19-24 сентября 2005 г.

По результатам выполненных исследований опубликовано 7 печатных работ, в том числе 3 в соавторстве. Из них 1 статья в российском журнале «Известия вузов. Северокавказский регион.», 1 статья в журнале Национальной Академии Наук Украины «Искусственный интеглект», 3 статьи в сборниках трудов, и 2 в сборниках тезисов конференций.

Основные результаты, выносимые на защиту

1. Методы расщепления многомерных гнезд циклов.

2. Методы подстановки индексных переменных и экспансии массивов в многомерных циклах.

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

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

5. Описание связи между решетчатыми графами и носителями зависимости по значению.

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы из 111 наименований. Диссертация содержит 197 страниц текста, 3 приложения, 29 рисунков и 1 таблицу.

Содержание работы

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

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

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

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

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

В третьей части главы рассматриваются наиболее часто используемые методы построения рассматриваемых представлений информационной зависимости: неравенства Банержи и НОД тест, методы построения решетчатых графов В.В. Воеводина и П. Фотрье (Р. РеаШпег), Омега тест. Особое внимание уделяется методам построения решетчатых графов: рассматривается общий алгоритм построения. Вводится понятие альтернативного многогранника (система неравенств, используемая в алгоритме построения решетчатого графа). Предлагается способ нумерации альтернативных многогранников. Анализируя алгоритм построения и то, как участвуют в нем альтернативные многогранники, делается вывод о том, что каждой построенной функции, описывающей дуги решетчатого графа, можно поставить в соответствие единственный альтернативный многогранник (или его номер), который участвовал в ее построении.

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

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

2. Если граница цикла есть функция от счетчиков внешних циклов, то нужно использовать тесты Банержи специального вида. В противном случае, при использовании тестов Банержи нужно аппроксимировать все границы константами.

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

4. Неравенства Банержи и НОД тест разработаны для анализа зависимости между вхождениями одномерных массивов. Если наличие зависимости требуется проверить между вхождениями массивов размерности больше 1, то нужно применять дополнительные аппроксимации. Причем, результат может зависеть от применяемого типа аппроксимации. Хотя в некоторых случаях все виды аппроксимаций приводят к неправильному выводу.

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

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

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

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

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

2. при построении функции Р использовался альтернативный многогранник с номером к.

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

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

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

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

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

случай на примере.

for (i.=l; i<5; i + + ) for (з=1; j<5; 3++) for(k=l; k£5; k++) if U==j)

X(i, 3, k) = X(i, 3, k-1) // Stmt 1

Потоковая зависимость X(i,j, k-l) от X(i,j, к) описывается решетчатым графом G, который изображен на рисунке 1. Дуги решетчатого графа G могут быть точно описаны функцией F\(i,j, к) = (0*г +j,j, к-1) с областью определения 1<й5, 1<У<5, 2<к<5, i=j. Дуги этого же графа G могут быть точно описаны функцией Fi(i,j, к) = (i,j, к-\) с областью опрел,еления 1 <i<5, 1<у'<5, 2<к<5, i=j. Если применить известный метод к функции F?, то будет сделан вывод о том, что итерации самого внешнего цикла можно исполнять одновременно. Если применить известный метод к функции Fj, то будет сделан ошибочный вывод о том, что итерации самого внешнего цикла исполнять одновременно нельзя.

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

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

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

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

for (х=1; к=5; х++)

for(j=l; j<=5; (i)

a[i] [j]=a[j] [i]+b[i] [3];

Выполним расщепление гнезца циклов (1) по разбиению {Nu N2} его пространства итераций (рис. 2).

—/V,

--N2

I 2 3 4 5 / Рис. 2. Решетчатый граф г отоковой зависимости в гнезде (1). Разбиение итерационного пространства исходного гнезда по множествам {N\, N2)

Разработанные в диссертации методы позволяют расщепить исходное гнездо циклов (1) в двух видах. В виде последовательности тесных циклов:

for(i=l; i<=5; i++) // no Nj

for(3=1; з<=5; 3++)

a[1][j]=a [ 3 ] [1]+b[1] [] ] ; (2)

for (i=2; K=5; 1++) // no N2

for (3=1; j<= (i-1) ; j++) a[i] [j]=a[j] [i]+b[i] [3];

В виде структуры произвольно вложенных циклов:

for (i=l; K=N; i++) (

for (3 = 1; j<=(i-l); // no N2

a [i] [ j ] —a [ j ] [i]+b[i] [j];

for (j=i; j<=5; j++) II no N1

a[i] [j]=a[j] [i]+b[i] [j];

}

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

Расщепление многомерных циклов необходимо для выполнения таких преобразований, как подстановка индексных переменных и экспансия массивов. Однако, данное преобразование и само по себе может являться распараллеливающим. Например, по решетчатому графу потоковой зависимости e[/][i] от £>[г][/] (рис. 2), видно, что данная зависимость запрещает одновременное исполнение итераций внешнего цикла гнезда (1). После расщепления в виде последовательности тесных гнезд, итерации всех циклов фрагмента программы (2) можно выполнять одновременно.

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

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

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

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

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

Продемонстрируем работу подстановки на примере.

£ог(к=0; к<=(Н+М); к++)

с[к]=0;

«1

¿ог (1=0; К=М; 1++) (3)

¡ог (¿=0; ¿<=Н; }++)

с[±+3]=с[] +а [ х]*Ъ [3 1;

«2 у

Подставим правую часть оператора с[£]=0 вместо вхождения у. Для этого построим решетчатый граф, описывающий потоковую зависимость по значению вхождения V от вхождений и\, «2. Этот граф изображен на рисунке 3. По данному решетчатому графу видно, что вхождение V использует значения, записанные генератором г/1, только на множествах итераций Еги|.„ Нги1„. Поэтому, для выполнения подстановки расщепим двумерное гнездо циклов данного примера в соответствии с разбиением его пространства итераций {#'„| #2„| „, Н„2у}. После этого заменим вхождение V правой частью оператора с[&]=0 в гнездах циклов, пространства итераций которых есть множества #2„ь-

Рис. 3. Решетчатый граф, описывающий потоковую зависимость по значению использования V от генераторов и1, «2, для М=Ы=3

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

for(k=0; k<=(N+M); k++) с[k]=0;

for (i=0; i<=0; i++) // цикл пой'й,,

for(]=0; ]<=N; j++)

c[-+j]=0+a[i]*b[]b'

for (i=l; K=M; i++) // цикл no H2uilV

for (]=N; j<=N; j++)

c[i+]]-0+a[i]*b[]]; forti=l; i<=M; i++) // цикл no Hu2,v

for (]=0; з<= (N-l); ]++)

c[i+3l=cti+j]+a[i]*b[j] ;

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

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

Экспансия массивов (Array Expansion) является обобщением растягивания скаляров, которое используется для устранения анти- и выходных зависимостей. Это преобразование, применимое к индексным переменным в любых программах из линейного класса, было впервые разработано П. Фотрье. Однако

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

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

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

Если во фрагменте программы (3) выполнить экспансию массива для генератора «2, то получим следующий фрагмент программы:

for(k=0; k<=(N+M); k++) с[k]=0;

for (i=0; i<=0; i++) // цикл по Hlui,»

for(j=0; j<=N; j++)

cc[i] ) =c [l+j ) +a [lj *b [] ] ;

for i<=M; x+ + ) // цикл по H2Ll,„

for(j=N; j<=N; j++)

cc[i] [] ] =c [i+] ] +a [l] *b [] ] ;

for (i=l; i<=M; i++) // цикл по Hu2,v

for(j=0; j<=(N-l); j++)

cc[i] [])=cc[i-l] [j+l]+a[i] *Ь[э] ;

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

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

1. построение графа информационных зависимостей для фрагмента программы на основе неравенств Банержи и НОД теста;

2. построение элементарных и простых снизу решетчатых графов;

3. построение графа информационных зависимостей на основе решетчатых графов;

4. разметка циклов РаЮо по решетчатым графам;

5. расщепление многомерных гнезд циклов в виде последовательности тесных гнезд;

6 подстановка индексных переменных, на основе расщепления в виде последовательности тесных гнезд циклов;

7. экспансия массивов, на основе расщепления в виде последовательности тесных гнезд циклов.

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

■с?Data,ai| i з*а <з t

Docuntert {

' p x

1

¿fOJ - HO]

For l - 2; {l <- 7|, 1 - (i ♦ 1| (

l[l] - Mi)

for j - 0. <j < (l - X)). ] • {

r[l] - Ulli - («Ii. j]

}

t

- (J * 1)

ifjm

Jaljsl

JF

'jü

Г empörten

Файл Праге Форият Вия спрайта

ы

Ol

рункйня: -1

V =+0*1+1'1+0

Область определения функции" -1*1+0*1<--2 +1*1+0*5<=7 +0*1-1*1<»-2 -1*1+Г*3<=-2 +0*1+1*3<-6

Область, в которую дуги не входят* -1»1+0*]<—2 +1*1+0*к=7 +0*1-1*^<«0 -1*1+1*3<--2 +0*1+1*]<«1

BülUGra^i

rränsftymations GretHe Г

/

к г

/а р

г

Графааьв лраастввяения программ Ршаатчатый граф

Примеры лрограм * рватопегаютсв в окне слева Греф может бить построен е деух режимах

Рис. 5. Элементарный решетчатый граф в ОРС.

В заключении приводится краткое описание полученных результатов, и

подводятся итоги проделанной автором работы.

Список основных опубликованных работ:

1. Шульженко A.M. Автоматическое определение циклов ParDo в программе //Приложение к журналу «Известия вузов. Северокавказский регион. Естественные науки», 2005, № 11, С. 77-88.

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

3. Шульженко A.M. Решетчатый граф и использующие его преобразования программ в Открытой распараллеливающей системе //Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», Новороссийск, 19-24 сентября 2005, С. 82-85.

4. Шульженко A.M. Расщепление многомерных циклов для эффективного распараллеливания //Труды всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 21-25 июня 2004, С. 186-194.

5. Шульженко A.M. Преимущества определения информационных зависимостей в программе с помощью решетчатых графов //XIII Международная конференция «Математика. Экономика. Образование». III международный симпозиум "Ряды Фурье и их приложения" Тезисы докладов. Ростов н/Д, изд-во ООО «ЦВВР», 2005. С. 137

6. Штейнберг Б.Я., Бутов А.Э., Науменко CA., Петренко В.В., Черданцев Д.Н., Штейнберг Р.Б., Шульженко A.M. Полуавтоматическое распараллеливание на основе ОРС /<Труды всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 21-25 июня 2004, С. 186-194.

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

В совместных работах личный вклад автора заключается в исследованиях и

разработках, связанных с графом информационных связей и решетчатыми графами.

/

Шульженко Александр Михайлович

ИССЛЕДОВАНИЕ ИНФОРМАЦИОННЫХ ЗАВИСИМОСТЕЙ ПРОГРАММ ДЛЯ РАСПАРАЛЛЕЛИВАЮЩИХ ПРЕОБРАЗОВАНИЙ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Подписано в печать "4" мая 2006 г.

Формат 60х 84 1/16 Бумага офсетная.

Печать оперативная. Усл. п.л. 1,0. Тираж 100 экз. Заказ 29-7

ООО "Мини Тайп"

344010, г. Ростов-на-Дону, пр. Ворошиловский, 87/65

ilOOGfí

ТтзГ

f11123

Введение

1 Информационная зависимость в программе. Основные способы ее определения и представления

1.1 Информационная зависимость и некоторые ее представления

1.1.1 Модель рассматриваемых программ: линейный класс

1.1.2 Вхождения переменных, итерационное пространство

1.1.3 Информационная зависимость по памяти (memory-based)

1.1.4 Информационная зависимость по значению (value-based, data-flow)

1.1.5 Сравнение представлений информационной зависимости

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

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

1.2.2 Решетчатый граф

1.2.2.1 Опорные пространства. Порядок исполнения операторов

1.2.2.2 Максимальные и минимальные решетчатые графы

1.2.2.3 Простые и элементарные решетчатые графы

1.2.2.4 Хранение решетчатых графов

1.2.3 Развертка решетчатого графа (таймирование, schedule)

1.3 Основные способы нахо/каения информационных зависимостей

1.3.1 Неравенства Банержи и НОД тест

1.3.2 Методы построения решетчатых графов В. В. Воеводина и П. Фотрье (P. Feautrier)

1.3.3 Омега Тест

1.3.4 Сравнение методов нахождения информационных зависимостей

1.3.4.1 Неравенства Банержи и точные методы

1.3.4.2 Метод В. В. Воеводина, метод П. Фотрье и Омега тест

2 Анализ и преобразования программ, основанные на решетчатом графе

2.1 Автоматическое распознавание ParDo циклов в программе

2.1.1 Определение ParDo цикла по решетчатому графу

2.1.2 Распознавание ParDo циклов по решетчатому графу. Связь между минимальными решетчатыми графами и носителями зависимости по значению

2.1.3 Определение ParDo циклов и их связь с ParDo циклами по решетчатому графу

2.1.4 Алгоритм распознавания ParDo циклов в программе

2.1.5 Циклы ParDo и внешние переменные

2.1.6 Сравнение с другими методами распознавания ParDo циклов

2.2 Расщепление многомерных гнезд циклов

2.2.1 Примеры рассматриваемых видов расщеплений

2.2.2 Построение расщепления в виде последовательности тесных гнезд циклов

2.2.2.1 Проверка существования дуги решетчатого графа между вершинами из заданных выпуклых множеств

2.2.2.2 Использование расщепления для непосредственного распараллеливания

2.2.3 Построение расщепления в виде структуры произвольно вложенных циклов 116 2.2.3.1 Использование расщепления для непосредственного распараллеливания: общий случай

2.2.4 Сравнение различных видов расщеплений 130 2.3 Подстановка переменных н экспансия массивов

2.3.1 Подстановка переменных

2.3.2 Экспансия массивов

3 Программная реализация построения графовых моделей информационных зависимостей и преобразований программ, их использующих

3.1 Анализ информационных зависимостей в ОРС

3.1.1 Построение расширенной информации о вхождениях

3.1.2 Реализация графа информационных зависимостей на основе неравенств Банержи

3.1.3 Реализация решетчатых графов. Выбор способа построения

3.1.3.1 Тестирование правильности построения решетчатого графа

3.1.3.2 Экспериментальные данные о времени построения решетчатых графов

3.1.4 Реализация построения графа информационных зависимостей на основе решетчатых графов

3.1.5 Реализация разметки ParDo циклов в программе

3.2 Преобразования программ, основанные на решетчатом графе, в ОРС

3.2.1 Реализация расщепления гнезда циклов. Выбор метода генерации границ циклов

3.2.2 Подстановка переменных и экспансия массивов

Актуальность темы.

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

В последнее время принципы параллельных ЭВМ все больше используются в персональных компьютерах, которые становятся все доступнее. Так, например, процессоры Intel Pentium-4 и Itanium используют технологию Hyper Threading. В настоящее время в продаже имеются персональные компьютеры на базе процессоров Intel Pentium D [101], Intel Pentium Extreme Edition [102], AMD Athlon 64 X2 [100], которые имеют двуядерную архитектуру. В дальнейшем ожидается увеличение производительности персональных компьютеров за счет увеличения количества ядер, расположенных на одном кристалле.

Для того чтобы программа выполнялась на параллельном компьютере быстрее, чем на последовательном, она должна быть специальным образом написана. Даже на компьютере с процессором Intel Pentium-4, можно найти и запустить одну последовательную программу, непрерывно выполняющую некоторые вычисления, при работе которой будет задействовано чуть более чем 50% мощности процессора (см. Приложение А.).

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

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

В ИПС РАН (г. Переславль-Залесский) под руководством С.М. Абрамова [1, 2] разработана Т-система, являющаяся средством автоматического динамического распараллеливания вычислений. Пользователь пишет программы на специально разработанном языке Т-системы Т++ (который является расширением языка С++), указывая потенциальные параллельные фрагменты кода с помощью, так называемых, Т-функций. Т-система освобождает программиста от решения задачи равномерного распределения нагрузки между доступными вычислительными ресурсами. Это особенно важно в случаях использования гетерогенных и/или меняющихся со временем параллельных вычислительных систем, а также в случаях, когда, анализируя тест программы трудно определить, как можно сбалансировать работу вычислительных узлов даже однородных суперЭВМ. Т-система также избавляет программиста от таких проблем как, организация явных обменов данными и синхронизации. Программы, реализуемые в Т-системе, пишутся в функциональном стиле.

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

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

В ИПМ им. М. В. Келдыша РАН разработан язык НОРМА [9, 10, 30], являющийся языком сверхвысокого уровня для параллельного программирования задач вычислительного характера (в частности, задач математической физики). Этот язык позволяет пользователю писать программы в терминах математических формул, значительно упрощая его работу. Сделаны компиляторы с языка НОРМА в Fortran 77 для последовательных компьютеров и распараллеливающие компиляторы в Fortran PVM, Fortran MPI и другие разновидности Fortran, специально ориентированные на конкретные архитектуры параллельных ЭВМ.

В работах [7, 32] говориться о DVM-системе, позволяющей разрабатывать параллельные программы для кластеров. В этой системе языки Fortran 77 и С снабжены дополнительными командами. Эти команды не воспринимаются стандартными компиляторами для последовательных ПК, но с их помощью DVM-компилятор генерирует параллельный код.

В помощь разработчикам эффективных параллельных программ создаются различные средства [6, 15, 28, 29, 31].

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

Разработка распараллеливающих компиляторов - одна из задач автоматического распараллеливания. Для её решения необходима детальная информация о структуре последовательной программы, взаимодействии отдельных операций между собой и с памятью. Неотъемлемой частью получения этой информации является, так называемый, анализ информационных зависимостей программы. Такой анализ позволяет определять операции, итерации (циклов) и операторы в последовательной программе, которые могут быть исполнены независимо (одновременно, параллельно). Существует множество представлений информационных зависимостей, которые различаются по степени информативности. Одним из наиболее тонких представлений информационной зависимости является решетчатый граф (граф алгоритма [22]). В нашей стране методы распараллеливания, основанные на анализе решетчатого графа, активно исследуются академиком РАН В.В. Воеводиным и его учениками. Работать с этим графом, используя традиционные методы хранения, такие как матрица смежности или список дуг, сложно из-за его больших размеров: число вершин решетчатого графа сопоставимо с числом исполняемых операций в программе. В.В. Воеводин предложил хранить этот граф в виде конечного числа аффинных отображений, описывающих дуги графа [25], а также разработал алгоритм, позволяющий вычислять эти отображения. На основе данного алгоритма, под руководством чл.-корр. РАН Вл. В. Воеводина (НИВЦ МГУ), реализована исследовательская система V-Ray [105], предназначенная для выявления параллелизма в последовательных ФОРТРАН программах. Из других исследователей, внесших значительный вклад в теорию решетчатых графов, следует отметить П. Фотрье (P. Feautrier, Франция), который разработал алгоритм построения решетчатого графа в виде квазиаффинного дерева решений [70, 71]. До появления указанных алгоритмов построения решетчатого графа, применимых к широкому классу программ, этот граф использовался лишь в частных случаях, например, в методе гиперплоскостей Лампорта [78] и методах параллелепипедов и пирамид В.А. Вальковского [19, 20].

В целях дополнения системы V-Ray А.В. Фроловым (ИВМ РАН) разрабатывается система МАКРОГРАФ [42]. Эта система предоставляет информацию о параллелизме программы. Кроме этого, используя технологию решетчатых графов, система МАКРОГРАФ дает пользователю информацию о распределении массивов программы, при котором затраты на межпроцессорные пересылки данных будут минимальны [41]. Планировалось ([42]), что в эту систему будут встроены методы межпроцедурного анализа, также основанные на решетчатом графе, разработанные А. С. Антоновым [11] (НИВЦ МГУ). А. С. Антонов также занимается исследованием канонического описания решетчатого графа и его использования для определения таких свойств программ, как оценка вычислительной сложности фрагмента или оценка объема входных и выходных данных [12].

Технологии, основанные на развертке решетчатого графа (см. п. 1.2.3), исследуются и используются для оптимизации/распараллеливания В. Пухом (W.Pugh), М. Лэм (M.Lam), А. Дарте (A. Darte), Н.А. Лиходедом и многими другими. Несмотря на то, что теория решетчатых графов уже довольно давно разрабатывается, она не часто используется в распараллеливающих компиляторах и системах. Например, из распараллеливающих систем [3, 87, 98, 103, 105, 106, 108, 109, 111] только в четырех используются решетчатые графы (или развертки решетчатого графа): V-Ray [105], PIPS [98], SUIF [106] (начиная с версии SUIF2 в экспериментальных целях [107]), LooPo [111], которые являются исследовательскими. Отметим, что многие из указанных распараллеливающих систем, в том числе и коммерческие, используют Омега тест для точного построения графа информационных зависимостей, например, Para Wise [110, с. 42], Promis [103]. Возможно, редкое использование теории решетчатых графов на практике связано со сложностью методов их построения и использования. Кроме этого, еще не достаточно разработаны оптимизирующие и распараллеливающие преобразования программ, которые могут быть реализованы только с помощью решетчатых графов.

Цель работы.

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

Из сформулированной цели вытекают следующие задачи:

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

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

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

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

Методы исследований.

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

Научная новизна.

1. Разработаны новые методы расщепления многомерных циклов. Эти методы отличаются от известных тем, что по заданному разбиению пространства итераций, они позволяют расщеплять как тесные, так и нетесные многомерные циклы. Кроме того, полученные алгоритмы конкретизированы до возможности использования при автоматическом распараллеливании, в отличие от [47]. Они применимы к большему классу программ, чем методы [47]. При выполнении разработанных методов расщепления в тела результирующих циклов не добавляются условные операторы, в отличие от [69, 71].

2. Разработаны новые методы подстановки индексных переменных и экспансии массивов в многомерных циклах. Эти методы являются обобщением подстановки скалярных переменных и растягивания скаляров на случай переменных-массивов, расположенных в гнездах циклов. В некоторых частных случаях действие преобразования экспансия массивов совпадает с переименованием скалярных или индексных переменных [47]. Полученный в данной работе метод экспансии массивов отличается от известного метода [69, 71] тем, что в результате его работы условные операторы в тела результирующих циклов не добавляются.

3. Разработан новый метод определения циклов, итерации которых можно исполнять одновременно. Этот метод позволяет находить более широкий класс циклов, итерации которых можно исполнять одновременно, чем известные методы [8, 21, 95]. Кроме того, если в данном методе использовать алгоритм построения решетчатых графов [21, параграф 6.5-6.6], то будет получен более быстрый, для циклов размерности больше 1, и простой в реализации способ определения параллелизма программы, чем [21, параграф 6.7].

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

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

Практическая значимость.

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

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

Личный вклад. Постановка задачи о разработке алгоритмов подстановки и переименования индексных переменных, а также об их реализации, принадлежит научному руководителю. Все теоретические результаты диссертации получены автором лично. Программная реализация графа информационных зависимостей, решетчатых графов, расщепления многомерных циклов, подстановки индексных переменных, экспансии массивов, метода определения ParDo циклов по решетчатым графам также выполнены автором лично. Однако эти реализации были бы невозможны без труда группы разработчиков ОРС, и, особенно, Черданцева Д.Н., Петренко В.В., Макошенко Д.В., которые реализовали внутреннее представление ОРС и богатый набор функций для работы с ним. Моры-лев Р.И. визуализировал граф информационных зависимостей в ОРС, а Гу-фан К.Ю. визуализировал решетчатый граф и метод определения ParDo циклов в ОРС.

Гранты.

Часть исследований диссертации поддерживалась грантами:

ФЦП «Интеграция» 2002-2006 гг., гос. контракт - Б0024/2148, «Разработка комплекса программных средств для высокопроизводительных вычислений».

Грант Союзного Российско-Беларусского государства (шифр «ТРИАДА»), 2005 г.

Апробация работы.

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

• Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция/ Дивноморское, 22-27 сентября 2003 г.

• Научно-методическая конференция «Современные информационные технологии в образовании: Южный федеральный округ», Ростов-на-Дону, 12-15 мая 2004 г.

• Всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 21-25 июня 2004 г.

• XIII Международная конференция «Математика. Экономика. Образование», г. Новороссийск, 29 мая - 5 июня 2005 г.

• Всероссийская научная конференция «Научный сервис в сети Интернет: технологии распределенных вычислений», г. Новороссийск, 19-24 сентября 2005 г.

По основным результатам диссертационной работы был сделан доклад на семинаре Института системного программирования РАН, г. Москва, 14 апреля 2006 г.

По результатам выполненных исследований опубликовано 7 печатных работ ([50 - 56]), в том числе 3 в соавторстве. Из них 1 статья в российском журнале «Известия вузов. Северокавказский регион», 1 статья в журнале Национальной Академии Наук Украины «Искусственный интеллект», 3 статьи в сборниках трудов, и 2 в сборниках тезисов конференций.

Основные результаты, выносимые на защиту

1. Методы расщепления многомерных гнезд циклов.

2. Методы подстановки индексных переменных и экспансии массивов в многомерных циклах.

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

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

5. Описание связи между решетчатыми графами и носителями зависимости по значению.

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

Структура диссертации.

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

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

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

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

Автор диссертации выражает глубокую признательность своему научному руководителю, д.т.н., Штейнбергу Б.Я. за переданную школу и оказанную помощь.

Автор признателен к.ф.-м.н. Михалковичу С.С. (научный руководитель при получении степени Бакалавра) за приобретенный уровень программирования.

Автор благодарен Черданцеву Д.Н., Петренко В.В., Макошенко Д.В., Нис З.Я., Штейнбергу Р.Б., Шилову М.В., Морылеву Р.И., Гуфану К.Ю. и другим разработчикам ОРС, труд которых значительно повысил качество программных разработок автора и помог ему в исследованиях.

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

1. Абрамов СМ., Адамович А.И., Инюхин А.В,, Московский А.А., Роганов В.А., Шевчук Ю.В., Шевчук Е.В. Т-Система с открытой архитектурой. Тр. междунар. науч. конф. «Суперкомпыотерные системы и их применение» (SSA2004). -Минск, 2004, с. 18-23.

2. Абрамов СМ., Московский А.А., Роганов В.А., Шевчук Ю.В., Шевчук Е.В., Парамонов Н.Н., Чиж О.П. 2

3. Open TS: архитектура и реализация среды для динамического распараллеливания вычислений. Ргос. Научный сервис в сети Интернет: технологии распределенных вычислений Труды Всероссийской научной конференции, 19-24 сентября 2005 г. Новороссийск, Изд-воМГУ,М.,с.79-81.

4. Адигеев М.Г., Дубров Д.В., Лазарева СА., Штейнберг Б.Я. Экспериментальный распараллеливающий компилятор на Супер-ЭВМ со структурной организацией вычислений// Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов. Тезисы докладов всероссийской научной конференции. Новороссийск. 21-26.09.

5. Москва: МГУ, 1998. с.101-108.

6. Адуцкевич Е.В., Баханович СВ., Лиходед Н.А. Условия получения согласованного таймирования и распределения операций и данных между процессорами. Тр. междунар. науч. конф. «Суперкомпьютерные системы и их применение» (SSA2004). -Минск, 2004, с. 160-165.

7. Адуцкевич Е.В., Баханович СВ. Адаптация алгоритмов к реализации на системах с распределенной памятью. Пространственно-временная локализация и распределение данных. Тр. междунар. науч. конф. «Суперкомпыотерные системы и их применение» (SSA2004). Минск, 2004, с. 165-170.

8. Алексахин В.Ф., Ефимкин К.Н., Ильяков В.Н., Крюков В.А., Кулешова М.И., Сазанов Ю.Л. Средства отладки МР1-программ в DVM-системе.//

9. Алексахин В.Ф., Ильяков В.Н., Коновалов Н.А., Ковалева Н.В., Крюков В.А., Поддерюгина Н.В., Сазанов Ю.Л. Система автоматизации разработки параллельных программ для вычислительных кластеров и сетей (DVMсистема). Научный сервис в сети Интернет. Труды Всероссийской научной конференции, 23-28 сентября 2002, г. Новороссийск. М.: изд-во МГУ, с. 272-273.

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

11. Андрианов А.Н., Ефимкин К.Н., Задыхайло И.Б. Непроцедурный язык для решения задач математической физики.// Нрограммирование, №2, 1991, с. 80-94.

12. Андрианов А.Н. Использование языка НОРМА для решения вычислительных задач на нерегулярных сетках. Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов. Тезисы докладов всероссийской научной конференции. Новороссийск. 2126.09.

13. Москва: МГУ, 1998. с.120-122.

14. Антонов А.С., Воеводин Вл.В. Новый подход к построению методов межпроцедурного анализа программ Труды первой международной научнопрактической конференции по программированию УкрПРОГ-98, Киев, 1998 г.

15. Антонов А.С. Использование канонического описания графа алгоритма для определения свойств программ.// Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», 19-24 сентября 2005 г., г. Новороссийск, с. 100-102.

16. Букатов А.А., Жегуло О.А., Коваль В.В. Создание системы поддержки распараллеливания программ, основанной на непроцедурном описании распараллеливающих программ.// Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», 19-24 сентября 2005 г., г. Новороссийск, с. 69-71.

17. Бурцев B.C. Выбор новой системы организации выполнения высокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ. В сб. трудов академика B.C. Бурцева "Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ". ИВВС РАН, М., 1997, с. 41-78.

18. Бурцев B.C. Новые принципы организации вычислительных процессов высокого параллелизма. Труды Первой Всероссийской научной конференции «Методы и средства обработки информации», 1-3 октября 2003, Москва, с. 17-32.

19. Бурцев B.C. Новые подходы к оценке качества вычислительных средств.// Интеллектуальные и многопроцессорные системы 1999/ Тезисы докладов Международной научной конференции. Таганрог: Изд-во ТРТУ, 1999, с. 921.

20. Вальковский В.А. Параллельное выполнение циклов. Метод параллелепипедов. Кибернетика. 1982, N 2. с. 51-62.

21. Вальковский В.А. Параллельное выполнение циклов. Метод пирамид. Кибернетика. 1983, N 5. с. 51-55.

22. Воеводин В. В. Математические модели и методы в параллельных процессах. Москва: Наука. 1986. 296 с.

23. Воеводин В. В. Информационная структура алгоритмов. М.: МГУ, 1997. 139 с.

24. Воеводин В. В. Математические основы параллельных вычислений. М.: МГУ, 1991.-345 с.

25. Воеводин В.В., Пакулев В.В. принт М 228, 1989.22 с.

26. Вольф М. Перестановка циклов. Векторизация программ: теория, методы, реализация. Сб. статей. Москва: Мир. 1991. 48 65.

27. Гайсарян С, Аветисян А.И., Падарян В.А., Леонтьев Г. Применение среды ParJava для разработки параллельных программ. Тр. междунар. науч. конф. «Суперкомпьютерные системы и их применение» (SSA2004). Минск, 2004. с. 99-104.

28. Гергель В.П., Сибирякова А. Программная система для изучения и исследования параллельных методов решения сложных вычислительных задач. Материалы второго Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах», 26-29 ноября, 2002 г, с. 82-88.

29. Громова В.В., Прохоров Д.А., Самофалов В.В. Комбинированный метод оптимизации параллельных программ для систем с общей памятью.// Труды Всероссийской научной конференции «Паучный сервис в сети Интернет: технологии распределенных вычислений», 19-24 сентября 2005 г., г. Новороссийск, с. 104-106.

30. Ефимкин К.Н. Язык НОРМА и методы его трансляции для параллельных вычислительных систем. Фундаментальные и прикладные аспекты разраОпределение дуг графа алгоритма. М.: Пре31. Москва: МГУ, 1998. с. 117-119.

32. Игумнов А.С., Открытая платформа отладки параллельных программ// Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М.: изд-во МГУ, с. 92-94.

33. Ильяков В.Н.. Коваленко И.В.. Крюков В.А. Анализ и предсказание эффективности выполнения DVM-программ на неоднородных сетях ЭВМ// Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М изд-во МГУ, с. 181-182.

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

35. Лиходед Н.А. Распределение операций и массивов данных между процессорами.// Нрограммирование, 2003, №3, с. 73-80.

36. Нетренко В. В. Внутреннее представление ОРС 3.// Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», 19-24 сентября 2005 г., г. Новороссийск, с. 106108.

37. Надуа Д., Вольф М. Оптимизация в компиляторах для суперкомпьюте-ров. Векторизация программ: теория, методы, реализация. Сб. статей. Москва: Мир. 1991. 7-47. 37. Сб. статей. Векторизация программ: теория, методы, реализация. Москва: "Мир". 1991.272 с.

38. Свами М., Тхуласираман К.. Графы, сети и алгоритмы. Москва: Мир. 1984. 455 с.

39. Торчигин В. Особенности отладки прикладных и системных задач на вычислительной системе с автоматическим распределением ресурсов// Интеллектуальные и многопроцессорные системы 2003/ Тезисы докладов Международной научной конференции. Таганрог: Изд-во ТРТУ, 2003, с. 55-57.

40. Фролов А.В. Оптимизация размещения массивов в Фортран-программах на многопроцессорных вычислительных системах Программирование, 1998, №3, с. 70-80.

41. Фролов А.В. Система МАКРОГРАФ и другие технологии ускорения исполнения ФОРТРАН-программ. Труды Первой Всероссийской научной конференции «Методы и средства обработки информации», 1-3 октября 2003, Москва, с.

42. Чумаченко Г. О. Технология отложенных токенов для преодоления ситуаций блокировки по переполнению буферов в суперпроцессоре нетрадиционной архитектуры. Труды Первой Всероссийской научной конференции «Методы и средства обработки информации», 1-3 октября 2003, Москва, с. 151-158.

43. Ширай А.Е. Виртуальная потоковая машина Труды Всероссийской научной конференции «Методы и средства обработки информации», 5-7 октября 2005, Москва.

44. Ширай А.Е. Системная поддержка вычислений в комплексе с автоматическим распределением ресурсов. Интеллектуальные и многопроцессорные системы 2003/ Тезисы докладов Международной научной конференции. Таганрог: Изд-во ТРТУ, 2003, с.54-55.

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

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

47. Штейнберг Б. Я. Распараллеливание программ для суперкомпьютеров с параллельной памятью и Открытая распараллеливающая система. Диссертация на соискание ученой степени доктора технических наук. РГУ, 2004.

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

49. Штейнберг Б.Я., Бутов А.Э., Науменко А., Петренко В.В., Черданцев Д.Н., Штейнберг Р.Б., Шульженко A.M. Полуавтоматическое распараллеливание на основе ОРС.// Труды всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики», 21-25 июня 2004, г. Ростов-на-Дону, с. 186-194.

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

51. Шульженко А. М. Преимущества определения информационных зависимостей в программе с помощью решетчатых графов XIII Международная

52. Шульженко А. М. Расщепление многомерных циклов для эффективного распараллеливания.// Труды всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики», 21-25 июня 2004, г. Ростов-на-Дону, с. 186-194.

53. Шульженко А. М. Решетчатый граф и использующие его преобразования программ в Открытой распараллеливающей системе.// Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», 19-24 сентября 2005 г., г. Новороссийск, с. 82-85.

54. Шульженко А. М. Автоматическое определение циклов ParDo в программе. Известия вузов. Северокавказский регион. Естественные науки. Приложение 1 Г05. с. 77-88.

55. Allen R., Kennedy К. Optimizing compilers for modem architectures. Morgan Kaufmann Publishers, An Imprint of Elsevier. 2002. 790 p.

56. Ancourt C, Irigoin F. Scanning polyhedra with DO loops. In ACM/SIGPLAN Symp. on Principles and Practice of Parallel Programming, pages 39—50, ACM, June 1991.

57. Banerjee U., Chen S. C, Kuck D., Towle R. Time and Parallel Processor Bounds for Fortran-like Loops// IEEE Trans, on Computers. 1979. C-28. No.9. P.660-670.

58. Calland P., Darte A., Robert Y., Vivien F. Plugging anti and output dependence removal techniques into loop parallelization algorithms.// Parallel Computing 23(1-2): 251-266 (1997).

59. Chamski Z. Fast and efficient generation of loop bounds. Proceedings of ParCo 93, Elsevier Science Publishers (North Holland).

60. Chamski Z. Nested Loop Sequences: Towards Efficient Loop Structures in Automatic Parallelization. HICSS 1994: Maui, Hawaii, USA Volume 2. P 14-22.

61. Collard J.-F., Feautrier P., Risset T. Construction of DO Loops from Systems of Affine Constraints. Research Report 93-15, Ecole Normale Superieure de Lyon, Lyon, France, May 1993.

62. Cytron R., Ferrante J. Whats in a name? Or the value of renaming for parallelism detection and storege allocation. IBM Res. Rep. RC 12785 (#55984), 1987.

63. Darte A., Vivien F. On the optimality of Allen and Kennedys algorithm for parallelism extraction in nested loops. Euro-Par 96 Parallel Processing, Second Int. Euro-Par Conf., Lyon, France, August 26-29, 1996, Proceedings, Volume I. P: 379-388.

64. Darte A., Vivien F. Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs. International Journal of Parallel Programming, 25(6):447-496, December 1997.

65. Darte A., Robert Y., Vivien F. Loop Parallelization Algorithms. Chapter in volume 1808 of LNCS on Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques, and Run Time Systems, Dharma P. Agrawal and Santosh Pande editors, pages 141-

67. Feautrier P. Array Expansion. //In ACM Int. Conf. on Supercomputing, St Malo, 1988.

68. Feautrier P. Parametric integer programming// Operationnelle/Operations Research, 22(3):243-268, September 1988.

69. Feautrier P. Dataflow analysis of scalar and array references// International Journal of Parallel Programming, 20(l):23-52, February 1991.

70. Feautrier P. Some efficient solution to the affine scheduling problem, part I, One Dimensional Time. //Int. J. of Parallel Programming, 21(5), Oct. 1992.

71. Feautrier P. Fine-grain scheduling under Resource Constraints// Proceedings of Languages and Compilers for Parallel Computing, 7th International Workshop, LCPC94, Ithaca, NY, USA, August 8-10, 1994.

72. Kalinov A., and Klimov S., Optimal mapping of a parallel application processes onto heterogeneous platform Proceedings of 19th International Parallel and Distributed Processing Symposium, Denver, USA, April 2005, IEEE CS, CD-ROM.

73. Kelly W., Pugh W. A framework for unifying reordering transformations.// Technical Report: CS-TR-2

74. University of Maryland at College Park, MD, USA. 1993.

75. Kuck D.J., Kuhn R.H., Leasure В., Wolfe M. Depedance graph and compiler optimizations. Proc. 8-th ACM Symp. On Principles of Progr. Lang. (Williamsburg, Va., Jan. 26-28), 1981, p. 207-218.

76. Maslov V. Delinearization: An Efficient Way to Break Multiloop Dependence Equations. Proceedings of the ACM SIGPLAN92 Conference on Programming Language Design and Implementation (PLDI), San Francisco, California, June 17-19, 1992. SIGPLAN Notices 27(7) (Julv 1992). 152-161.

77. Maydan D. E., Hennessy J. L., and Lam M. S.. Efficient and exact data dependence analysis. //In SIGPLAN 1991 Conference on Programming Language Design and Implementation, pages 1—14, ACM, Toronto, Canada, June 1991.

78. Maydan D. E., Hennessy J. L., and Lam M. S.. Effectiveness of data dependence analysis.// International Journal of Parallel Programming. Volume 23, Issue 1 (February 1995). Pages: 63-81

79. Padua D., Wolfe M. Advanced Compiler Optimizations for Supercomputers// Commun. ACM. 1986. Vol. 29. No. 12. P. 1184-1201.

80. Paek Y., Petersen P. A Data Dependence Graph in Polaris// Technical Report 1495, Univ. of Illinois at Urbana-Champaign, Center for Supercomputing Res. Dev., May 1996.

81. Petersen P., Padua D. Static and Dynamic Evaluation of Data Dependence Analysis Techniques. IEEE Trans, on Computers. 1996. Vol 7, No 11. P. 1121-1132.

82. Pugh W. The Omega test: a fast and practical integer programming algorithm for dependence analysis// Communications of ACM, 8:102-114, August 1992.

83. Pugh W. Definitions of Dependence Distance// Letters on Programming Languages and Systems, 1(3):261-265, September 1993.

84. 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 PLDr92 conference.

85. Pugh W., Wonnacott D. An Exact Method for Analysis of Value-based Array Data Dependences.// Technical Report CS-TR-3196, Dept. of Computer Science, University of Maryland, Collage Park, December 1993.

86. Wolfe M. The Definition of Dependence Distance. ACM Trans. Program. Lang. Syst. 16(4): 1114-1116(1994).

87. Wolfe M., Banerjee U. Data Dependence and Its Application to Parallel Processing// International Journal of Parallel Programming. 1987. Vol.16. No.2. P.137178.

89. Parallel Software Products Inc. (http://www.parallelsp.com/index.htm)