Использование многоуровневого внутреннего представления в автоматическом распараллеливании программ для многопроцессорных ЭВМ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Лазарева, Светлана Александровна

• Лазарева, Светлана Александровна
• кандидат технических наук
• 2000

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

Оглавление

Введение

I Распараллеливание программ для многопроцессорных ЭВМ

1.1 Архитектура современных ЭВМ

1.1.1 Параллелизм в рамках одного процессора

1.1.1.1 Конвейерные вычисления

1.1.1.2 Конвейеры с перекрытиями

1.1.1.3 ШБС - процессоры

1.1.1.4 , УЫXV - архитектура

1.1.2 • Параллелизм на множестве процессоров или данных

1.1.2.1 Массивно-параллельные ЭВМ с распределенной памятью

1.1.2.2 Параллельные компьютеры с общей памятью

1.1.2.3 Векторно-конвейерные ЭВМ

1.1.2.4 Многопроцессорные ЭВМ с архитектурой комбинированного типа

1.2 Различные подходы к распараллеливанию программ

1.2.1 «Ручное» распараллеливание

1.2.2 Автоматическое распараллеливание

1.2.2.1 Распараллеливание на уровне операторов и команд

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

1.2.2.2.1 Методы Лемпорта для векторизации циклов

1.2.2.2.2 Методы Вальковского

1.2.2.2.3 Метод линейного преобразования

1.2.2.2.4 Метод В.В. Воеводина

1.2.2.2.5 Методы оптимизации циклов, основанные на анализе вектора направлений зависимостей по данным

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

1.2.2.3 Крупноблочное распараллеливание

1.2.3 Полуавтоматическое распараллеливание

1.3 Различные варианты представления программ для автоматического распараллеливания

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

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

1.3.3 Идеографы

1.3.4 88А-формы

1.3.5 Сеть программных зависимостей

1.3.6 ОБА-форма

1.3.7 Граф потока зависимостей

1.3.8 Иерархический граф заданий

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

I.3.10 Общие требования к внутреннему представлению программ

II Многоуровневое представление программ

П.1 Основные понятия теории графов

П.2 Управляющий граф программы

Н.2.1 Вершины управляющего графа

II.2.2 Дуги управляющего графа 51 II.2.3 Алгоритм построения управляющего графа на основе синтаксического анализа программы 52 П.2.4 Исполнимость управляющего графа 56 II.2.5 Неизбыточность управляющего графа как основного представления программы

П.З Расширенная информация о вхождениях переменных в различные операторы

11.3.1 Построение расширенной информации на основе анализа управляющего графа 58 П.4 Граф зависимостей по данным

П.4.1 Зависимость по данным. Теоретические аспекты

11.4.1.1 Типы зависимостей по данным

11.4.1.2 Порядок выполнения операторов

11.4.1.3 Косвенная зависимость по данным

11.4.1.4 Вектор направления зависимостей по данным

11.4.1.5 Вычисление отношений зависимости по данным

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

11.4.1.7 Неравенства Банержи '

11.4.1.8 Точный алгоритм нахождения зависимостей для одного цикла

11.4.2 Зависимость по данным. Реализация 78 П.4.2.1 Вершины графа зависимостей по данным 78 11.4.2.2 Дуги графа зависимостей по данным 78 П.4.2.3 Вектор направления зависимости по данным для гнезда циклов 80 И.4.2.4 Алгоритм построения графа зависимостей по данным на основе управляющего графа и расширенной информации о вхождениях

III Использование многоуровневого представления программ для распараллеливающих и оптимизирующих преобразований

Ш.1 Глобальные преобразования Программ

III. 1.1 Подстановка идентификаторов переменных

III. 1.2 Распространение констант

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

Ш.2.1 Канонизация циклов

Ш.2.2 Разбиение циклов

Ш.2.3 Слияние циклов

Ш.З Вспомогательные оптимизирующие преобразования

III.3.1 Введение новой переменной

Ш.3.2 Приведение подобных в арифметических выражениях

Ш.З.З Удаление оператора

III.3.4 Вставка оператора

III.4 Удобство внутреннего представления для реализации преобразований программ

IV Использование многоуровневого представления и библиотеки преобразований для создания распараллеливателей

IV.1 Распараллеливающий компилятор на Супер-ЭВМ со структурной реализацией вычислений

IV.1.1 Реализованные преобразования программы 108 IV. 1.2 Автоматическое размещение данных и генерация кода 111 IV. 1.3 Резюме

IV.2 Автоматическое распараллеливание циклов для выполнения на суперкомпьютере nCUBE 2S

IV.2.1 Архитектура суперкомпьютера nCUBE и пакет MPI

IV.2.2 Распараллеливающие преобразования для циклов с одномерными массивами

IV.2.2.1 Преобразование циклов с организацией межпроцессорной пересылки элементов

IV.2.2.2 Преобразование циклов без межпроцессорных пересылок данных

IV.2.3 Распараллеливающие преобразования для циклов с двумерными массивами

IV.2.3.1 Распределение данных и вычислений по процессорам

IV.2.3.2 Результаты распараллеливания процесса умножения матриц "

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

Важность и актуальность темы исследований. Эффективное программирование для параллельных ЭВМ - процесс довольно трудоёмкий. Он требует применения специальных параллельных языков, библиотек или компиляторов, способных строить для последовательных языков программирования программы в кодах параллельных ЭВМ. Разработка таких компиляторов -одна из задач автоматического распараллеливания. Для её решения необходима детальная информация о структуре алгоритма, взаимодействии отдельных операций, как между собой, так и с общей памятью. Традиционно для хранения и преобразования такой информации используется внутреннее или промежуточное представление. Выбор представления программы оказывает сильнейшее влияние на вид, асимптотическую сложность и реализацию оптимизирующих и распараллеливающих преобразований [26]. Последние несколько лет очень активно ведутся исследования в области разработки представлений программ. В качестве моделей программ используются операторные схемы, информационные графы, идеографы и т.д. Но почти все предложенные подходы обладают одним недостатком - некомпактностью. Это обстоятельство делает представления мало пригодными для использования. В то время как ещё в 1960 году Р. Карпом был введён управляющий граф программы (УГП) - первая теоретико-графовая модель. Компактного представления в виде УГП зачастую достаточно для анализа свойств программы, для описания и применения оптимизирующих преобразований. Однако, для исследования информационных отношений в распараллеливаемом алгоритме управляющего графа программы не достаточно. На этих двух наблюдениях был основан предложенный в работе подход - создание многоуровневого внутреннего представления с компактным базовым уровнем - УГП. С помощью УГП для исследования структуры исходного алгоритма на микроуровне может быть построена расширенная информация о вхождениях переменных и граф зависимостей по данным (ГЗД) - следующие уровни детализации внутреннего представления.

Частично работа выполнялась по заказу НИИ МВС ТРТУ (г. Таганрог). На базе предложенного внутреннего представления был создан экспериментальный вариант распараллеливающего компилятора для суперкомпьютера с архитектурой перестраиваемого конвейера (называемого так же суперкомпьютером со структурной реализацией вычислений [35]).

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

Методика проведения исследований. Для организации внутреннего представления использовалась теория графов.

Исследованы различные варианты промежуточного представления. Сделан вывод о целесообразности создания многоуровневого представления.

В основе построения внутреннего представления лежат методы трансляции. Изучены различные варианты грамматик для описания синтаксиса входного языка [24, 34]. Для преобразования исходной программы в УГП был выбран класс предикативных грамматик и система построения трансляторов Предлог [44] для такого класса грамматик.

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

У. Банержи, М. Вольфа. Разработан алгоритм построения детализированного ГЗД (вершины - вхождения переменных) с предварительным анализом зависимостей на символьном уровне.

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

Научная новизна и практическая значимость. Разработано и апробировано новое внутреннее представление программ, удобное для решения задач автоматического распараллеливания. С одной стороны, это представление обладает свойствами таких известных представлений, как [40, 25, 39] - компактностью, исполнимостью, лёгкой модифицируемостью. С другой стороны это внутреннее представление содержит информацию о зависимости по данным, поддерживает динамическую модель хранения данных, удобную для быстрого сбора и изменения информации.

Предложен алгоритм и разработаны предикативные грамматики [125], преобразующие программы во внутреннее представление. Предложена разметка УГП, позволяющая сократить его размеры за счёт удаления дуг, выходящих из вершин-преобразователей. Предложен алгоритм, синтезирующий создание графа зависимостей по данным на основе символьного анализа и алгоритма Банержи.

Для обоснования применимости алгоритмов, используемых при построении внутреннего представления, были проведены статистические исследования [80, 81] (независимо от [21]).

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

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

Апробация работы. Материалы диссертации доложены на Всесоюзном научно-техническом семинаре "Разработка системного и прикладного программного обеспечения МВК ПС-2000/2100, ПС-3000/3100 (Калинин, 1990), на научной конференции "Смешанные вычисления и преобразования программ" (Новосибирск, 1990), на VI и VIII Всероссийской Школе-семинаре "Современные проблемы математического моделирования" (Новороссийск, 1995 и 1999). Помимо этого-материалы диссертации одобрены Всероссийской научной конференцией "Фундаментальные и прикладные аспекты pä3-работки больших распределенных программных комплексов" (Новороссийск, 21-26.09.98.), VII Всероссийской Школой-семинаром "Современные проблемы математического' моделирования" (Новороссийск, 8-13.09.97.), Всероссийским симпозиумом "Математическое моделирование и компьютерные технологии" (Кисловодск, 24-26.04.97), Международными конференциями "Advanced mathematics, computation & applications" (Новосибирск, 20-24.06.95.) и "Environmental Mathematical Modeling and Numerical Analysis" (Ростов-на-Дону, 24-31.05.1999).

Публикации. По теме диссертации опубликовано 9 работ. Одна статья опубликована в центральной печати [50]. В сборниках трудов конференций и симпозиумов опубликованы 3 доклада [49, 51, 81], 5 работ опубликованы в сборниках тезисов [1, 12, 80, 112, 121].

Работа [1] выполнена совместно с Адигеевым М. Г., Дубровым Д. В., Штейнбергом Б. Я. Постановка задачи в [1] принадлежит Б .Я. Штейнбергу, реализация и описание предложенных в работе результатов в равной степени принадлежит всем соавторам.

Работа [12] выполнена в соавторстве с Букатовым А. А. и Жегуло О. А. Постановка задачи в [12] принадлежит Букатову А. А. Автору принадлежит проверка формулировок контекстных условий распараллеливающих преобразований и обсуждение результатов.

Работы [52 и 51] выполнены совместно с Н. Н. Ячменёвой. Автору принадлежит в них постановка задачи, описание внутреннего представления и общее руководство.

Объём и структура диссертации. Основной текст диссертации изложен на 147 страницах машинописного текста и содержит 27 рисунков (в том числе с примерами программ), 4 таблицы, и библиографию, насчитывающую 138 наименований литературных источников.

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

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

Во второй главе описывается предлагаемое многоуровневое представление программ. В начале главы даются основные понятия теории графов, используемые в следующих разделах. В разделах П.2.1 и П.2.2 описывается управляющий граф программы, в разделе П.2.3 предлагается алгоритм его построения на основе синтаксического анализа программы. В следующих двух разделах показывается компактность и исполнимость УГП. Раздел II.3 и его подразделы описывают следующий уровень многоуровневого представления программ - расширенную информацию о вхождении переменных (ВП) и алгоритм построения ВП по УГП. Раздел П.4 посвящен графу зависимостей по данным и содержит теоретические аспекты зависимости по данным, и описание их реализации. В частности разделы П.4.2.1-П.4.2.4 вводят определение и дают описание способа хранения во внутреннем представлении вершин и дуг графа зависимостей по данным, вектора направления зависимости по данным для гнезда циклов, алгоритм построения ГЗД на основе ВП и УГП.

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

Четвёртая глава содержит два примера использования внутреннего представления и преобразований - распараллеливающий компилятор для суперЭВМ со структурной реализацией вычислений и автоматический распаралле-ливатель циклов для выполнения на суперкомпьютере пСЦВЕ 28. При описании разработок уделяется внимание вопросам размещения кода и данных, организации коммутаций. Для суперкомпьютера пСИВЁ 28 (в разделах 1У.2.2.2 и 1У.2.3.2) приведены диаграммы времени работы исходных и распараллеленных программ на различном наборе процессоров.

В Приложении А приводится описание операторов языка программирования Фортран и соответствующее им представление в УГП.

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

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

2. На основе предложенного многоуровневого представления программ разработан набор оптимизирующих и распараллеливающих преобразований.

3. На базе многоуровневого представления программ и библиотеки преобра-. зований реализованы экспериментальные версии распараллеливателей для суперкомпьютера пСЦВЕ 28 и супер-ЭВМ со структурной реализацией вычислений.

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

I РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ МНОГОПРОЦЕССОРНЫХ ЭВМ

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

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

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

ЗАКЛЮЧЕНИЕ

Диссертационная работа посвящена построению многоуровневого представления программ и его использованию в процессе автоматического распараллеливания для многопроцессорных ЭВМ. Исследованы различные варианты промежуточного представления. Сделан вывод о целесообразности создания многоуровневого представления. В работе описаны теория и программная реализация построения многоуровневого представления. Это представление отличается от известных тем, что в него введена расширенная информация о вхождениях переменных. Помимо этого, управляющий граф отличается от описанных в литературе. А именно, введена специальная разметка графа, увеличивающая его компактность за счёт удаления дуг, начинающихся в вершинах-преобразователях. Что касается отличий ГЗД - вершинами предложенного ГЗД являются вхождения, а не операторы. В сравнении с описанными в литературе ГЗД, предложенный в работе граф зависимостей по данным содержит зависимости по входам, если это необходимо для решения задачи размещения данных. Вцелом предложенное представление отвечает требованиям, предъявляемым к представлениям программ.

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

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

132 переработан. С учётом его модификации был разработан алгоритм построения детализированного ГЗД (вершины - вхождения переменных) с предварительным анализом зависимостей на символьном уровне.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Лазарева, Светлана Александровна, 2000 год

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

2. Антонов A.C., Воеводин Вл.В. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных супер-ЭВМ//Программирование. 1996. №.4. С.37-51.

3. Бабенко JT.K., Каляев A.B., Николаев И.А. ЦОС для решения уравнений в частных производных// Изв. СКНЦ ВШ "Техн. науки". 1980. №.3. С.37-40.

4. Бабенко JI.K., Матвеева JI.K., Николаев И.А., Омаров О.М. Организация ВК на базе МВС для автоматизации физического эксперимента// Известия СКНЦВШ "Техн. науки". 1986. №.2. С.30-35.

5. Бабичев A.B., Лебедев В.Г. Распараллеливание программных циклов// Программирование. 1983. N5. С.52-63.

6. Брич 3. С., Капилевич Д. В., Котик С. Ю., Цагельский В. И. Фортран ЕС ЭВМ. М: Финансы и статистика. 1985. 287 с.

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

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

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

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

11. Вальковский В.А., Лебедев В.Г. Векторизаторы циклов// АиТ. 1989. №.8. С.3-23.

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

13. Воеводин Вл. В. Теория и практика исследования параллелизма последовательных программ//Программирование. 1992. №.3. С.38-54.

14. Высокоскоростные вычисления Под. ред. Я. Ковалика, пер. с английского. Москва: Радио и связь. 1988. 432 с.

15. Глушкова В.Н., Ильичёва O.A. Автоматизация синтаксического и контекстного анализа в СПТ// Кибернетика. 1985. №.4. С.26-28.

16. Евстигнеев В. А., Кожевникова Г. П. Топологические меры сложности программ. Новосибирск. 1989. (Препринт АН СССР. Ин-т точной механики и выч. техники. Новосиб. фил.; №23). 30 с.

17. Евстигнеев В. А. О некоторых формах промежуточного представления программ// Конструирование и оптимизация программ. Сб. статей. Новосибирск: НГУ. 1995. Стр. 60-68.

18. Евстигнеев В. А. Применение теории графов в программировании. Москва: Наука. 1985.

19. Евстигнеев В.А., Спрогис C.B. Векторизация программ. Векторизация программ: теория, методы, реализация. Сб. статей. Москва: Мир. 1991. С.246-271.

20. Евстигнеев В. А., Спрогис С. В. Векторизация программ: анализ зависимостей. Новосибирск: Препр. АН СССР. Ин-т точной механики и выч. техники. Новосиб. филиал. 1989. № 21.

21. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука. 1990. 384 с.

22. Ершов А. П. Введение в теоретическое программирование. Беседы о ме-. тоде. Москва: Наука. 1977.

23. Задыхайло И.Б., Ефимкин К.Н. Содержательные обозначения и языки нового поколения// Информационные технологии и вычислительные системы. 1996. №.2. С.46-58.

24. Ильичёва O.A. Инициальная семантика логических спецификаций с отрицанием// Кибернетика и системный анализ. 1992. №.4. С.13-19.

25. Ильичёва O.A. Определение языков программирования для систем построения трансляторов. Обзор. Прикладная информатика. Сб. статей. Москва: ФиС. 1987. №1. С.87-110.

26. Каляев A.B., Николаев И.А., Макаревич О.Б., Бабенко JI.K. Супер-ЭВМ с программируемой архитектурой. ЭВТ. Сб. статей. Москва: Радио и связь. 1988. вып. 2. С.36-48.

27. Карп Р. Заметка о приложении теории графов к программированию для цифровых вычислительных машин// Кибернетический сборник. 1962. в.4. С.123-134.

28. Касьянов В.Н. Методы оптимизации программ. Новосибирск: НГУ. 1984.92 с.

29. Касьянов В. Н. Оптимизирующие преобразования программ. Моск-ва:Наука. 1988. 240 с.

30. Касьянов В. Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ. Исследования по прикладной теории графов. Новосибирск: . 1986. С.9-26.

31. Касьянов В. Н., Трахтенброт М.Б. Анализ структур программ в глобальной оптимизации// Всесоюзн. симпозиум по методам реализации новых алгоритмических языков. Сб. трудов. Новосибирск. 1975. часть 2. С.143-159.

32. Коновалов H.A., Крюков В.А., Погребцов A.A. Сазанов Ю.Л. C-DVM -язык разработки мобильных параллельных программ. Москва: Препринт ИПМ им. М.В.Келдыша РАН. 1997. №86. 30 с.

33. Крицкий С.П. Логико-грамматические средства спецификации и реализации языков программирования// Канд. дисс. Ростов-на-Дону, 1990. 125 с.

34. Крицкий С.П. Логические средства проектирования языкового интерфейса// Тезисы докладов конференции "Диалог "Человек-ЭВМ". Часть 2. Свердловск. 1989. С.30-32.

35. Крицкий С.П. Предикативные грамматики в интеллектуальных систе-мах//Всесоюзн. научно-практич. семинар "Интеллектуальное программное обеспечение ЭВМ". 13-19 мая 1990. Тезисы докладов. 4.1. Ростов-на-Дону-Терскол, 1990. С. 56-57.

36. Крукиер Л.А., Гипский Н.В. ППП "ЭКОМОД". Вычислительные технологии. Сб. статей. Новосибирск: ИВТ СО РАН. 1995. т.4. N 10. С. 111-130.

37. Лазарева С. А. Многоуровневое представление программ и его использование в автоматическом распараллеливании// Математическое моделирование. 1997. т.9. №.2. С.31-33.

38. Лазарева С.А., Ячменёва H.H. Автоматическое распараллеливание циклов с двумерными массивами для выполнения на суперкомпьютерах сраспределённой памятью (на примере умножения матриц)// Математическое моделирование (принята к публикации). 8 с.

39. Логический подход к искусственному интеллекту: от классической логики к логическому программированию. Москва:Мир. 1990. с.432.

40. Макаллистер Дж. Искусственный интеллект и Пролог на микроЭВМ. Москва: Машиностроение. 1990. Пер. с англ. под ред. М.В. Сергиевского. 240 с.

41. Макаревич О.Б., Бабенко Л.К. и др. Супер ЭВМ с программируемой архитектурой// Электронная вычислительная техника. М.: Радио и связь. 1988. Вып.2. С. 161-171

42. Малпас Дж. Реляционный язык Пролог и его применение. Москва: Наука. 1990. Пер. с англ. под ред. В.Н. Соболева. 464 с.

43. Немнюгин С.A. Turbo Pascal. СпБ: ПИТЕР. 1999. 496 с.

44. Николаев И.А., Бабенко Л.К., Макаревич О.Б. Архитектура МВС на базе ЕС ЭВМ и СП, ориентированного на решение задач мат. физики// Высокопроизводительные вычисления. Сборник тезисов II всесоюзного совещания. Батуми. 1984. С.65-66.

45. Николаев И.А., Бабенко Л.К., Макаревич О.Б. Базовая ВС на основе потоковой машины для решения задач ВЭ// Перспективы развития ВС. Материалы II всесоюзного семинара. Рига. 1985. С.36-37.

46. Николаев И.А., Крукиер Л.А. Проект ППП РАСЕРАСК// Однородные вычислительные среды и систолические структуры. Сборник тезисов докладов 1-ой Всесоюзной конференции. Львов. 17-20 апреля 1990. Львов: ИППМиМ. 1990. т.З. С. 158-163.

47. Николаев И.А., Крукиер Л.А., Муратова Г.В., Тихонов А.Н. ППП РАСЕРАСК для решения эллиптических краевых задач на современных ЭВМ. Вычислительные технологии. Сб. статей. Новосибирск: Ин-т выч. техн. СО РАН. 1993. т.2, N 6. С.220-231.

48. Николаев И.А., Фомина Н.И., Бабенко Л.К. Параллельная система программирования МВС// Изв. ВУЗов СССР. Приборостроение. 1986. №.2. С.43-44.

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

50. Пакулев В. В. Сложность анализа параллельных структур произвольных фортрановских циклов. Москва: ОВМ АН СССР. 1989. Препринт №225. 20 с.

51. ПЛ/1 ВК ЭВМ. Руководство программиста версия транслятора 4.6. март, 1987. 92 с.

52. Поттосин И. В. К обоснованию алгоритмов оптимизации программ// Программирование. 1979. №.2.

53. Поттосин И. В. О контекстных условиях объединения и расчленения циклов. Сб. Языки и системы программирования. Новосибирск: препринт ВЦ СО РАН. 1979.

54. Поттосин И.В. Оптимизирующие преобразования и их последовательность. Системное программирование. Новосибирск: . 1973. часть 2. С.128-137.

55. Поттосин И.В., Юргинова О.В Обоснование преобразования чистки циклов//Программирование. 1980. №.5. С.3-16.

56. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. Москва: Энергоатомиздат. 1983.312 с.

57. Проблемы системного и теоретического программирования Сборник научных трудов. Новосибирск: НГУ. 1984. 172 с.

58. Сб. статей. Векторизация программ: теория, методы, реализация. Москва: "Мир". 1991.272 с.

59. Симонович И.В., Крукиер JI.A. Модульный анализ алгоритмов решения сеточных уравнений и требования к языкам программирования. Вычислительные системы и алгоритмы. Ростов-на-Дону: РГУ. 1983. С.74-86.

60. Симонович И.В., Крукиер JI.A. Модульный анализ итерационных алгоритмов для решения сеточных уравнений на многопроцессорных вычислительных комплексах// Спецпроцессоры параллельного действия. Тезисы докладов Всесоюзного семинара. Рига: РПИ. 1981.

61. Страуструп Бьерн. Язык программирования С++ (3 издание). СпБ: Невский Диалект. 1999. 991 с.

62. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. Москва: Наука. 1987.

63. Французов Ю. А. Обзор методов распараллеливания кода и программной конвейеризации//Программирование. 1992. №.3. С. 16-37.

64. Хожайнова (Лазарева) С. А. Статистические данные о распараллеливае-мости программ//Смешанные вычисления и преобразования программ. Сборник трудов конференции. Новосибирск. 27-29 ноября 1990 г., Новосибирск: ВЦ СО РАН, 1991, С.237-242.

65. Штейнберг Б. Я. Бесконфликтные размещения массивов при параллельных вычислениях// Кибернетика и системный анализ. 1999. №1, с. 166-178.

66. Штейнберг Б. Я. Оптимальные параллельные переразмещения двумерных массивов//Программирование. №6. 1993. С.81-88.

67. Штейнберг Б. Я. Преобразования программ и граф информационных связей. Ростов-на-Дону: УПЛ РГУ. 1997. 23 с.

68. Штейнберг Б.Я. Распараллеливание рекуррентных циклов с условными операторами// Автоматика и телемеханика. 1995. №.6. С. 176-184.

69. Штейнберг Б. Я. Распараллеливающие и оптимизирующие преобразования программных циклов. Ростов-на-Дону: УПЛ РГУ. 1997. 23 с.

70. Языки и параллельные ЭВМ. Москва: Наука. 1990. серия Алгоритмы и алгоритмические языки. 93 с.

71. Abu-Sufah W., Kuck D.J., Lawrie D.H. On the performance enhancement of paging systems through program analysis and transformations// IEEE Trans. Comput. 1981. Vol.C-30. No.5. P.341-356.

72. Aho A. V., Sethi R., Ullman J. D. Compilers: Principles, Techniques and Tools. Addison-Wesley: Reading a. o. 1986.

73. Allen J.R., Baumgartner D., Kennedy K., Porterfield A. PTOOL: a semiautomatic parallel programming assistant// Int. Conf. on Parallel Processing. Proc. 1986. Washington, D.C.: IEEE Сотр. Soc. Press. 1986. P. 164-170.

74. Allen J. R., Kennedy K. Automatic Loop Interchange// Proc of ACM SIG-РЬА>Г84. Symposium on Compiler Construction. Montreal, Canada. June 1984. SIGPLAN NOTICES 19. Vol.6. P.233-246.

75. Alpern B ., Wegman M. N., Zadek F. K. Detecting equality of values in programs// Conf. Ree. Fifteenth ACM Symp. on Principles of Progr. Lang. Jan. 1988. New-York: ACM. P. 1-11.

76. Alpern B., Wegman M. N., Zadek F. K. Global value numbers and redundant computations// Conf. Ree. Fifteenth ACM Symp. on Principles of Progr. Lang. Jan. 1988. New-York: ACM. P.12-21.

77. Baneijee 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.

78. Burke M., Cytron R. Interprocedural Dependence Analysis and Parallelization // SIGPLAN Notices. 1986. Vol.21 (7). No.7. P.162-175. "

79. Butler R. and Lusk E. Monitors, Messages, and Clusters: The P4 Parallel Programming System// Parallel Computing. 1994. No.20. P.547-564.

80. Calkin R., Hempel R., Hoppe H. and Wypior P. Portable Programming with the PARMACS Message-Passing Library// Parallel Computing. Special issueon massage-passing interfaces. 1994. No.20. P.615-632.

81. Cohagen W.L. Vector optimization for the ASC// The Seventh Annual Princeton Conference on Information Sciences and Systems. Proc,. Dept. of Electrical Engineering, Princeton, N.J. 1973. P. 169-174.

82. Cowell W. R., Thompson C. P. Transforming Fortran DO Loops to Improve Performance on Vector Architectures// ACM Transactions on Mathematical Software. 1986. Vol.12. No.4. P.324-353.

83. Cytron R. Doacross: Beyond Vectorization for Multiprocessors // Proc. of International Conf. Parallel Process. 19-22 Aug, 1986. P.836-844.

84. Cytron R. and e. a. Efficiently computing static single assignment form and the control dependence graph// ACM TOPLAS. 1991. Vol.13. No.4. P.451-490.

85. Dongarra J. J.,'Duff I. S., Sorencen D. C., van der Vorst H. A. Numerical Linear Algebra for High-Performance Computers. Philadelphia: SIAM. 1998. 342 p.

86. Eijkhout V., Vassilevski P. Positive definiteness aspects of vectorizable pre-conditioners// Parallel Computing. 1989. Vol.10. No.l. P.93-100.

87. Express User's Guide, version 3.2.5., Monrovia, CA: Parasoft Corporation . 1992. .

88. Ferrante J., Ottenstein K. J., Warren J. D. The Program Dependence Graph and Its Use in Optimization// ACM Transactions on Programming Languages• and Systems. 1987. Vol.9. No.3.P.319-349.

89. Gary J., Fosdick.L. An optimizing precompiler for finite-difference computations on a vector computer// Parallel Computing. 1989. Vol.10. No.l. P.51-64.

90. Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R. and Sunderam V. PVM: A Users" Guide and Tutorial for Networked Parallel Computing. : MIT Press. 1994. Существует электронная версия книги. URL ftp— ://www.netlib.org/pvm3/book/pvm-book.ps.

91. Girkar M., Polychronopoulos C. D. The HTG: An intermediate representation for program based on control and data dependencies. Urbana-Champaign: Univ. of Illinois. May 1991. CSRD Rep. 1046.

92. Griffin H. Elementary Theory of Numbers. New York: McGraw-Hill. 1954.

93. Kirch A. M. Elementary Number Theory. New York: Intext. 1974.

94. Kuck D. The structure of computers and computation. New York, NY: John Wiley and Sons, Inc. 1978. Vol. 1.

95. Kuck D. J., Kuhn R.H.,. Padua D.A., Leasure В., Wolfe M. Dependence graphs and compiler optimizations// 8th ACM Symp. on Principles of Progr. Lang. Proc. Williamsburg, Va. Jan. 26-28. 1981. P.207-218.

96. Kuhn R.H. Optimization and interconnection complexity for parallel processors, single-stage .networks and decision trees. Ph. D. thesis. Rep 801009 :Univ. of Illinois at Urbana-Champaign. 1980.

97. Lamport L. The coordinate method for the parallel execution of DO-loops. -S agamore computer conference on parallel processing, 1973.

98. Lamport L. The parallel execution of DO loops// Commun. ACM. 1974. Vol.17. No.2. P.83-93.

99. Lapkowski C. Symbolic Manipulation for Array Dependence Testing. Montreal: McGill University. 1995. ACAPS Project №621.1994.11. 16 p.

100. Lastovetsky A. mpC a Multi-Paradigm Programming Language for Massively Parallel Computers// ACM SIGPLAN Notices. 1996. Vol.31. No.2. P.13-20.

101. Lazareva S. A. The multy-level program representation and its use in automatic parallelization// Abstracts of EMMNA'99. The international Conference on Environmental Mathematical Modeling and Numerical Analysis. Rostov on Don, May 24-31, 1999, p. 27

102. Loveman D.B. Program improvement by source-to-source transformation// J. ACM. 1977. Vol.24. No.l. P.121-145.

103. Message Passing Interface Forum. MPI: A Message-Passing Interface Standard // Int. J. Supercomputer Applications. 1994. No.8. (3/4). Special issue on MPI. Существует электронная версия. URL ftp://www.netlib.org/mpi/mpi-report.ps.

104. Partch H., Steinbruggen R. Program transformation systems// ACM Computer Survey. 1983. Vol.15. No.3. P.199-236.

105. Pereira F., Warren D. Definite clause grammars for language analysis a survay of formalism and comparison with augment transition networks// Artificial intelligence. 1980. Vol.13. P.231-278.

106. Pingali K. Dependence flow graphs: An algebraical approach to program dependencies. Cornell Univ. Dept. Comp. Sci. Tech. Rep. 90-152. Sept. 1990.

107. Polychronopoulos C., Baneijee U. Processor allocation for horizontal and vertical parallelizm and related speedup bounds// IEEE Transactions on computers. 1987. Vol.C-36. No.4. P. 410-420.

108. Polychronopoulos C. D., Kuck D J., Padua D. A. Execution of parallel loops on parallel processor systems// Proc. of International Conf. Parallel Process. 19-22 Aug. 1986. P.519-527.

109. Ruppelt Th., Wirtz G. Automatic transformation of high-level object-oriented specifications into parallel programs// Parallel Computing. 1989. Vol.10 No.l.P. 15-28.

110. Scarborough R. G., Kolsky H. G. A vectorizing Fortran compiler// IBM J. Res. Develop. 1986. Vol.30. No.2. MARCH. P.163-171.

111. Skjellum A. and Leung A. Zipcode: a Portable Multicomputer Communication Library atop the Reactive Kernel. In D.W. Walker and Q.F. Stout editors// Fifth Distributed Memory Concurrent Computing Conference. Proceedings. IEEE Press. 1990. P.767-776.

112. Tomasulo R.M. An Efficient Algorithm for Exploding Multiple Arithmetic Units// IBM J. of Res. and Devel. 1967. Vol.11. No.l. P.25-33.

113. The Arity/Prolog Language reference manual. Concord, Massachusetts: Ar-ity Corporation. 1988. 320 p.

114. Wang S. S., Uht A. K. Program optimization with ideo graph// Intern. Conf. on Parallel Processing. Proc. 1989. C. 153-159.

115. Weiss S., Smith J.I. Instruction Issue Logic in Pipelined Supercomputers// IEEE Trans. Comput. 1984. Vol.C-33. No.l 1. P.1013-1122.147

116. Wolfe M., Baneijee U. Data Dependence and Its Application to Parallel Processing// International Journal of Parallel Programming. 1987. Vol.16. No.2. P. 137-178.

117. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MVS-100// Third International Conference PaCT-95. Parallel Computing Technologies: Springer 964. 1995. P.341-356.

118. Zima H. P., Bast H-J., Gerndt M., Hoppen P. J. Semi-Automatic paralleliza-tion of Fortran Programs// CONPAR,86. Conf. Proc. Aachen. 1986. Vol.237. P.287-264.