Исследование и реализация непроцедурных преобразований программ для построения расширяемой системы распараллеливания тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Жегуло, Ольга Анатольевна

• Жегуло, Ольга Анатольевна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Жегуло, Ольга Анатольевна

Введение

I Распараллеливание и технологии трансформирования программ

1.1 Технологии параллельного программирования и средства распараллеливания для современных параллельных ЭВМ

1.1.1 Основные классы параллельных архитектур и технологий параллельного программирования

1.1.2 Методы и средства распараллеливания программ

1.2 Трансформационный подход к программированию и его применение в распараллеливании

II Язык схемных трансформаций многокомпонентных программных структур

11.1 Базовый язык схемных трансформаций многокомпонентных программных структур 27 II. 1.1 Синтаксис

II. 1.2 Порядок применения правила

11.2 Развитие языка схемных трансформаций многокомпонентных программных структур

11.3 Методика написания нелокальных схемных правил трансформации ill Реализация на языке нелокальных схемных трансформаций распараллеливающих и оптимизирующих преобразований

111.1 Определения зависимостей по данным и управлению, используемых для проверки условий применимости

III.1.1 Граф зависимостей по управлению

111.1.2 Граф зависимостей по данным

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

111.2 Базовые предикаты и функции в условиях применимости правил 48 III.2.1 Базовые предикаты, заданные на семантическом дереве программы и графе зависимостей по управлению

Ш.2.2 Базовые предикаты, заданные на графе зависимостей по данным

III.2.3 Базовые предикаты, заданные на решетчатом графе

111.3 Типы параметров правил с образцами на параметризованном Фортране

111.4 Набор классических преобразований распараллеливания и оптимизации

111.4.1 Сценарий применения классических преобразований распараллеливания и оптимизации

111.4.2 Протягивание констант

111.4.3 Нормализация циклов

111.4.4 Удаление индуктивных переменных. Случай

111.4.5 Удаление индуктивных переменных. Случай 2 58 Ш.4.6 Удаление индуктивных переменных. Случай 3 60 III.4.7 Удаление охватывающих переменных

111.4.8 Слияние циклов (классический подход)

111.4.9 Перестановка двух циклов

111.4.10 Коллапс циклов

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

111.4.12 Редукция скалярного произведения векторов

111.4.13 Параллелизация для цикла однократной вложенности

111.4.14 Параллелизация для гнезда вложенных циклов

III.5 Правила распараллеливания согласно подходу В.В. Воеводина

111.5.1 Перестановка циклов для гнезда любой вложенности

111.5.2 Слияние циклов (подход В.В. Воеводина)

111.5.3 Параллельное исполнение цикла ParDO

IV Макет многоцелевой системы трансформаций программ

IV.1 Возможности макета МСТП 77 IV.2 Язык сценариев 78 IV.3 Внутренние механизмы и структура макета МСТП

IV.3.1 Структура макета МСТП и порядок работы с ним

IV.3.2 Внутреннее представление правил и сценариев

IV.3.3 Механизмы работы трансформационной машины

IV.3.3.1 Порядок обхода дерева программы 86 IV.3.3.2 Алгоритм унификации дерева составного входного образца и дерева программы

Введение диссертации (часть автореферата) на тему «Исследование и реализация непроцедурных преобразований программ для построения расширяемой системы распараллеливания»

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

Со времени постановки проблемы распараллеливания в 60-х гг. прошлого века ею занимались множество исследователей, отечественных и зарубежных. Были получены эффективные инструменты распараллеливания для векторных и некоторых других архитектур [20, 27, 28, 50, 57, 61]. Однако постоянно появляются новые суперкомпьютеры, в основном с распределенной памятью, и для них приходится создавать методы распараллеливания [22]. Разрабатываемые методы распараллеливания программ требуют предварительных экспериментов по их эффективности и применимости к реальным программам. Распараллеливающий компилятор является длительной в разработке и трудно поддающейся модификации программной системой, и потому существует потребность в быстром прототипировании новых методик распараллеливания последовательных программ.

Системы автоматического распараллеливания строятся на основе трансформаций программ, поэтапно применяемых к преобразуемой программе [43, 26]. Трансформации программ подразделяются на процедурные и непроцедурные (схемные) [26,43,98].

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

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

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

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

В работах А.А. Букатова [9, 10, 64] были предложены язык и организация многоцелевой системы трансформаций программ (МСТП), основанные на схемном описании нелокальных трансформаций программ и допускающие использование алгоритмических средств для выполнения нетривиальных вычислений над параметрами схем. МСТП ориентирована, в частности, на распараллеливание программ, обеспечивает средства достаточно простого расширения и удовлетворяет всем требованиям к системе прототипирования распараллеливающих компиляторов.

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

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

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

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

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

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

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

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

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

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

2. Разработано представление на разработанном языке представительного набора преобразований распараллеливания и оптимизации программ на подмножестве языка Фортран по классическим методам Аллена, Кеннеди, Паду а и Вольфа 4, 23, 24, 51], а также некоторых (перестановка и слияние циклов, параллельное исполнение цикла типа ParDO согласно подходу академика В.В. Воеводина [21, 22]) неклассических распараллеливающих преобразований программ. Для некоторых классических преобразований оптимизации сформулированы отсутствующие в других источниках условия, обеспечивающие семантическую корректность выходной программы.

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

4. Разработано внутреннее представление правил трансформаций программ, совместимое с абстрактным деревом преобразуемой программы [47], а также методы трансляции правил трансформации в их внутреннее представление.

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

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

1. Предложенные дополнения языка многокомпонентных схемных правил расширяют его возможности и перспективы его применения для задания различных преобразований программ.

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

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

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

Результаты работы использованы в НИР ЮГИНФО № 1.7.43 «Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» (выполненную в рамках раздела «Освоение и развитие сетевых технологий нового поколения» подпрограммы «Информационные технологии в системе информационного общества» научной отраслевой программы Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования»). Апробация результатов работы

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

Всероссийская школа-семинар "Современные проблемы математического моделирования", Новороссийск, 1997;

Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000;

Первая и Вторая Всероссийские научно-технические конференции "Методы и средства обработки информации", Москва, 2003, 2005;

Всероссийская научная конференция "Научный сервис в сети Интернет: технологии распределенных вычислений", Новороссийск, 2005;

II, IV, V и VII международные научно-технические конференции "Интеллектуальные и многопроцессорные системы", 2001, 2003, 2004,2006.

Публикации

По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей, включая 1 статью в журнале, рекомендованном ВАК РФ для публикации результатов докторских диссертаций, 5 тезисов докладов на конференциях и 4 публикации в материалах конференций.

В совместной работе [15] автору принадлежит заключение о возможности непроцедурного задания распараллеливающих преобразований программ на основе результатов экспериментов; в работах [41,42, 12] — разработка правил распараллеливающих трансформаций и использованные в определениях некоторых правил расширения языка нелокальных схемных трансформаций программ. В работе [13] — обзор актуальных близких проектов среди технологий распараллеливания и программирования. Объем и структура работы

Основной текст диссертации изложен на 88 страницах, имеются 3 рисунка.

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Жегуло, Ольга Анатольевна

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

Заключение

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

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

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

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

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

Таким образом, цель диссертационной работы достигнута.

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

Развитие экспериментальной системы распараллеливания предполагается в следующих направлениях: 1) добавление новых преобразований распараллеливания согласно разным методам и на основе изучения практики ручного распараллеливания, в том числе с заменой типовых действий вызовами параллельных библиотек, для различных классов задач и целевых архитектур; 2) встраивание в систему других языков программирования; 3) развитие средств визуализации и диалога с пользователем макета МСТП.

Список литературы диссертационного исследования кандидат технических наук Жегуло, Ольга Анатольевна, 2007 год

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

2. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". 4.1. Термины для описания объекта оптимизации // НТИ. Сер. 2. — 2002. — №12. — С.23-28.

3. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". 4.2. Термины для описания процесса оптимизации // НТИ. Сер. 2.— 2003.— № 1, —С.22-29.

4. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". Ч.З. Примеры описания некоторых оптимизирующих преобразований // НТИ. Сер. 2. — 2003. — № 2. — С.27-34.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М., Мир, 1978. —Т.2, гл.11 «Оптимизация кода».

6. Букатов А.А. Разработка средств построения систем преобразования исходных текстов программ // Информационные технологии. — № 2. —1999. —С.22-25.

7. Букатов А.А. Методы и средства эффективного построения и использования региональных научно-образовательных сетей. — Ростов-на-Дону, изд-во ООО «ЦВВР», 2004. — 212 с.

8. Букатов А.А., Лазарева С.А., Жегуло О.А. Непроцедурное описание распараллеливающих преобразований программ // Тезисы докладов VII Всероссийской школы-семинара "Современные проблемы математического моделирования". — Ростов-на-Дону, 1997. — С.27-29.

9. Вальковский В.А. Параллельное выполнение циклов. Метод параллелепипедов // Кибернетика. — 1982. — № 2. — С.51-62.

10. Вальковский В.А. Параллельное выполнение циклов. Метод пирамид // Кибернетика. — 1983. — № 5. — С.51-55.

11. Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. — Москва: Радио и связь, 1989. — 176 с.

12. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Элементы параллельного программирования.— Москва: Радио и связь, 1983.— 239 с.

13. Ватанабе Т., Катияма X., Ивая А. Супер ЭВМ фирмы NEC: семейство SX // СуперЭВМ. Аппаратная и программная организация. — М.: Радио и связь, 1991. — С.184-200.

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

15. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.— СПб.: БХВ-Петербург, 2002. — 608 с.

16. Вольф М. Перестановка циклов. В сб. Векторизация программ, С.48-65.

17. Вольф М. Векторная оптимизация в сравнении с векторизацией. В сб. Векторизация программ, С.183-191.

18. Горелик A.M. Современный Фортран для компьютеров традиционной архитектуры и для параллельных вычислительных систем (аналитическийобзор). Препринт, ИПМ им. М.В.Келдыша РАН, Москва, 2003.— http://www.keldysh.ru/papers/2003/prep29/prep200329.html

19. Евстигнеев В.А., Касьянов В.Н. Оптимизирующие преобразования в распараллеливающих компиляторах // Программирование.— 1996.— №6. — С. 12-26.

20. Евстигнеев В.А., Мирзуитова И.Л. Анализ циклов: выбор кандидатов на распараллеливание. Препринт № 58, Сибирское отделение Института систем информатики им. А.П. Ершова, Новосибирск, 1999 // http://www.iis.nsk.su/preprints/pdf/058.pdf.

21. Евстигнеев В.А., Спрогис С.В. Векторизация программ (обзор) // В сб. Векторизация программ, С.246-267.

22. Ершов А.П. Введение в теоретическое программирование (беседы о методе) — М.: «Наука», 1977.

23. Ершов А.П. Трансформационная машина: тема и вариации // В сборнике Проблемы теоретического и системного программирования. Сборник научных трудов. — НГУ. — 1982. — С.5-24.

24. Ершов А.П. О сущности трансляции // Программирование.— 1977.— №5. — С.21-39.

25. Жегуло О.А. Непроцедурное представление преобразований программ в системе поддержки распараллеливания // В сб. "Компьютерное моделирование. Вычислительные технологии". — Ростов-на-Дону: изд-во ООО "ЦВВР", 2003. — С.27-40.

26. Жегуло О.А. Создание экспериментальной системы поддержки распараллеливания программ на основе макета многоцелевой системы трансформаций программ // Известия вузов. Северо-Кавказский регион. Технические науки. — 2006. — Приложение № 10. — С.5-13.

27. Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука. Гл. ред. Физ.-мат. лит., 1988. — 336 с.

28. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — 1104 с.

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

30. Котов В.Е. Введение в теорию схем программ. — Новосибирск: «Наука», 1978. —256 с.

31. Кристиансен Т., Торкингтон Н. Perl: библиотека программиста. — СПб: Изд-во «Питер», 2000. — 736 с.

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

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

34. Миура К. СуперЭВМ фирмы Fujitsu: векторная система FACOM // СуперЭВМ. Аппаратная и программная организация. — М.: Радио и связь, 1991. —С. 166-183.

35. Падуа Д., Вольф М. Оптимизация в компиляторах для суперкомпьютеров. В сб. Векторизация программ, С.7-47.

36. Поттосин И.В. Российские исследования по языкам программирования и трансляции // Мир ПК. — 2003. — № 12.

37. Стандарт языка Фортран. Reference number of document: ISO/IEC FCD 1539-1:2004(E).

38. Ферранте Дж., Оттенштейн К., Уоррен Дж. Граф программных зависимостей и его применение в оптимизации. // В сб. Векторизация программ. — С.141-182.

39. Фуксман А.Л. Технологические аспекты создания сложных программных систем. — М.: Финансы и статистика", 1979. — 184 с.

40. Хаммер К. Паскаль-компилятор для векторного процессора // В сб. Векторизация программ. — С. 192-201.

41. Черняев А.П. Программные системы векторизации и распараллеливания Фортран-программ для некоторых векторно-конвейерных ЭВМ (обзор) // Программирование. — 1991. — № 2. — С.53-68.

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

43. Шульженко А. М. Исследование информационных зависимостей программ для распараллеливающих преобразований. Диссертация на соискание степени к.т.н. — Ростов-на-Дону, 2006.

44. Allen F., Burke M., Charles Ph. a.o. An overview of the PTRAN analysis system for multiprocessing // Journal of Parallel and Distributed Computing, 1988, V. 5, № 5 — pp. 617-640.

45. Blume W., Eigenmann R. Performance analysis of parallelizing compilers on the Perfect Benchmarks programs // IEEE Transactions on Parallel and Distributed Systems, 1992, Vol. 3, № 6. — pp. 643-656.

46. Blume W., Doallo R., Eigenmann R. a. o. Parallel programming with Polaris // Computer. 1992, Vol.29, № 12. — pp. 78-82.

47. Boekhold M., Karkowski I., Corporaal H. Transforming and Parallelizing ANSI С Programs Using Pattern Recognition.

48. Callahan D., Cooper K., Hood R.T. a.o. Parallel programming support in ParaScope // Lecter Notes of Computer Science, 1987, Vol. 297.— pp. 91-105.

49. Callahan D., Cooper K., Hood R.T. a.o. ParaScope: a parallel programming environment // The International Journal of Supercomputer Applications, 1988, Vol. 2, № 4. — pp.84-99.

50. Carle A., Cooper K.D., Hood R.T. a.o. A practical environment for scientific programming//Computer. 1987,Nov. — pp. 75-89.

51. Coleman H.B. The vectorizing compiler for the Unisys ISP // Proceedings Of International Conference on Parallel Processing, Aug. 17-21, 1987.— University Park, PA, 1987. — pp. 567-576.

52. Collard J.-F., Feautrier P. Automatic Generation of Data Parallel Code // Proceedings of the Fourth International Workshop on Compilers for Parallel Computers. Delft, The Netherlands, Dec. 1993, pp. 321-332.

53. Creusillet В., Irigoin F. Interprocedural analyses of Fortran programs. — Ecole des Mines de Paris: Tech. Rep., 1997.

54. Dodson D.S., Metzger R.C., Smith P.E. Optimize supercomputer code with vectorizing compilers // Electronic Design. — 1988. — Vol. 36, № 5. — pp. 79-84.

55. Feautrier P. Automatic Parallelization in the Polytope Model. In G.-R. Perrin and A. Darte, editors, The Data Parallel ProgrammingModel, volume 1132 of LNCS, pp.79-100. Springer-Verlag, 1996.

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

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

58. Feautrier P. Some efficient solution to the affine scheduling problem, part II, Multidimensional time. // International Journal of Parallel Programming, 21(6), Oct. 1992.

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

60. Guarna V.A., Jr., Gannon D., Jablonowski D. a.o. Faust: An integrated environment for parallel programming // IEEE Software.— July 1989.— pp. 20-26.

61. Hall M., Meller-Crummey J., Carle A., Rodriguez R. FIAT: A framework for interprocedural analysis and transformation // Lecture Notes of Computer Science, 1993, Vol. 768. — pp. 522-545

62. Hall M., Murphy В., Amarasinghe S. a.o. Interprocedural analysis for parallelization // Lecture Notes of Computer Science, 1996, Vol. 1033. — pp. 6180.

63. Hall M., Hiranandani S., Kennedy K., Tseng C.-W. Interprocedural compilation of Fortran D // Journal of Parallel and Distributed Computing, 1996, Vol. 38,№2. — pp 114-129.

64. Katayama H., Tsukagoshi M. Fortran and tuning utilities aiming at ease of use of a supercomputer // Fall Joint Comput. Conf., Dallas, Texas, May 2-6, 1986: Proc., 1986. —pp. 1034-1040.

65. Kessler C. W., Paul W.J. Automatic Parallelization by Pattern Matching // Proc. of 2nd Int. ACPC Conference, Gmunden, Austria, Oct. 1993, Springer LNCS, Vol. 734.

66. Kessler C. W. Symbolic array data flow analysis and pattern recognition in numerical codes.

67. Kessler C. W. Pattern-Driven Automatic Program Transformation and Parallelization // Proc. of 3rd EUROMICRO Workshop on Parallel and Distributed Processing, Jan. 1995.

68. Kessler C. W. The PARAMAT Project: Current Status and Plans for the Future // Proc. of AP'95 Workshop on Automatic Data Layout and Performance Prediction, Rice University, Houston, Apr. 1995.

69. Kessler C. W. On the applicability of program comrehension techniques to the automatic parallelization of sparse matrix computation // AP'97, Barcelona.

70. Kessler C. W. Applicability of automatic program comprehension to sparse matrix computations // CPC'98 workshop, June 1998, Linkoping, Sweden.

71. Kessler C.W., Smith C.H. The SPARAMAT Approach to Automatic Comprehension of Sparse Matrix Computations // Proc. IWPC'99 Int. Workshop on Program Comprehension, Pittsburgh, May 5-7, 1999. IEEE CS Press.

72. Kessler C.W., Seidl H., Smith C.H. The SPARAMAT Approach to Automatic Comprehension of Sparse Matrix Computations // Technical report 99-10, Dept. of Mathematics and Computer Science, University of Trier, 54286 Trier, Germany. March 1999.

73. Kiczales G., Lamping J., Mendhekar A., Maeda C., Lopes C.V., Loingtier J-M., Irwin J. Aspect-Oriented Programming // Proceedings of the European Conference on Object-Oriented Programming (ECOOP), Finland. Springer-Verlag LNCS 1241. June 1997.

74. Lamport L. The parallel execution of DO loops // Communications of ACM. — 1974. —Vol.17, № 2. — pp.83-93.

75. Lim A., Lam M. Maximizing parallelism and minimizing synchronization with affine partitions // Parallel Computing, 24:445-475,1998.

76. Lim A.W., Lam M.S. Cache optimizations with affine partitioning // Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, Virginia, 2001.

77. Lim A.W., Liao S.-W., Lam M.S. Blocking and array contraction across arbitrary nested loops using affine partitioning // Proceedings of the ACM SIGPLAN Simposium on Principles and Practice of Programming Languages, 2001.

78. Martino B. di, Iannello G., Zima H. An Automated Algorithmic Recognition Technique to Support Parallel Software Development // Proc. of Int. Workshop on Parallel and Distributed Software Engineering, Boston (USA), 17-18 May 1997, IEEE-CS press.

79. Martino B. Di, Kessler C. W. Program Comprehension Engines for Automatic Parallelization: A Comparative Study // Proc. of 1st Int. Workshop on Software Engineering for Parallel and Distributed Systems, Chapman&Hall, March 25-26,1996, Berlin, Germany.

80. Nguen Т., Gu J., Li Z. An interprocedural parallelizing compiler and its support for memory hierarchy research // Lecture Notes of Computer Science, 1995, Vol. 1033. —pp. 96-110.

81. Partch H., Steinbruggen R. Program transformation systems // ACM Computer Survey, 1983, v. 15, № 3, pp. 199-236.

82. Pinter S. S., Pinter R. Y., Program Optimization and Parallelization Using Idioms // ACM Trans, on Programming Languages and Systems, 1994, vol. 16, №3, pp. 305-327.

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

84. Scarborough R.G., Kolsky H.G. A vectorizing Fortran compiler // IBM J Res. Develop. — 1986. — Vol. 30, № 2. — pp. 163-171.

85. Smith K., Appelbe W.F. PAT — An interactive Fortran parallelizing assistant tool // Proc. 1988 Int. Conf. on Parallel Processing, University Park, Pa., Aug. 15-19,1988. —pp. 58-62.

86. Visser E. A Survey of Rewriting Strategies in Program Transformation Systems // Electronic Notes in Theoretical Computer Science 57 (2001).

87. Wilson R.P., French R.S., Wilson C.S. a.o. SUIF: An infrastructure for research on parallelizing and optimizing compilers // SIGPLAN Not.— 1994. — Vol. 29, № 12. — pp. 31-37.

88. Winter V. L. Proving the correctness of program transformationss. Ph.D. thesis.

89. Winter V. L. Do you trust your compiler? Applying formal methods to constructing high-assurance compilers.

90. Wolfe M., Banerjee U. Data dependence and its application to parallel programming // International Journal of Parallel Programming Vol. 6, No.2,1987.

91. Wonnacott D. Constraint-Based Array Dependence Analysis. Ph.D. thesis.

92. Многопроцессорные компьютеры // http://paralIel.ru/computers/

93. Определение трансформации программ // http://www.program-transformation.org/Transform/ProgramTransformation/

94. Открытая распараллеливающая система // http://ops.rsu.ru

95. Средства разработки параллельных программ // http://paralleltech/parallel.ru/tech/techdev/

96. Program Construction and Optimization Laboratory // http://transform.iis.nsk.su

97. Parafrase(-2)ParaWise 2.4 User Guide // http://www.parallelsp.com/downloads/parawise-2.4/parawise-user-guide-2.4-OOl.pdf

98. Skeletal Parallelism // http://homepages.inf.ed.ac.uk/mic/Skeletons/

99. Stratego/XT // http://www.stratego-language.org

100. The Omega Project: Frameworks and Algorithms for the Analysis and Transformation of Scientific Programs // http://www.cs.umd.edu/projects/omega/

101. The PIPS Workbench Project // http://www.cri.ensmp.fr/~pips/

102. The SUIF Group // http://suif.stanford.edu/

103. Top500 самых производительных суперкомпьютеров // http://parallel.ru/computers/top500.list29.html

104. XHTML™ 1.0 The Extensible HyperText Markup Language // http://www.w3 .org/TR/xhtml 1 /

105. Extensible Stylesheet Language (XSL) Version 1.1. W3C Recommendation 05 December 2006 // http://www.w3.org/TR/xsl/