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

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

.

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

В последнее время принципы параллельных ЭВМ все больше используются в персональных компьютерах, которые становятся все доступнее. Так, например, процессоры 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 г., г. Новороссийск, с. 106 108.

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 12 785 (#55 984), 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.137 178.

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