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

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

Жегуло Ольга Анатольевна

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

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

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

ООЗ159213

Ростов-ни-До ну - 2007

003159213

Работа выполнена на кафедре информатики ¡г вычислительного эксперимента факультета математики, механики и компьютерных наук Южного федерального университета.

Научный руководитель:

кандидат технических наук, доцент Бу катов Александр Алексеевич

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

Бабенко Людмила Климентьевна

кандидат технических наук, доцент Крицкий Сергей Петрович

Ведущая организация:

НИИ иы числительных, информационных и управляющих систем Южно-Российского государственного технического университета (Новочеркасского политехнического института)

Защита состоится октября 2007 г, в [ ["" часов на заседании

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

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

Автореферат разослан « »__2007 г.

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

диссертационного совета,

кандидат физико-математических наук,

доцент -тТ1** Муратова Галина Викторовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

' Букатов А А Разработка средств непроцедурной реализации распараллеливающих преобразований программ // Труды Всероссийской научной конференции "Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов", Абрау-Дюрсо, 1998, с 109-116

достаточно простого расширения и удовлетворяет всем требованиям к системе прото-типирования распараллеливающих компиляторов

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

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

Цель и задачи диссертационной работы

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

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

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

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

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

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

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

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

2 Разработано представление на дополненном языке представительного набора преобразований распараллеливания и оптимизации программ на подмножестве языка Фортран по классическим методам Аллена, Кеннеди, Падуа и Вольфа, а также некоторых (перестановка и слияние циклов, параллельное исполнение цикла типа РагБО согласно подходу академика В В Воеводина) неклассических рас-

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

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

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

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

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

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

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

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

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

Использование результатов работы

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

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

Апробация результатов работы

Основные результаты по теме диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах Всероссийская школа-семинар "Современные проблемы математического моделирования", Новороссийск, 1997, Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000, Первая и Вторая Всероссийские научно-технические конференции "Методы и средства обработки информации", Москва, 2003, 2005, Всероссийская научная конференция "Научный сервис в сети Интернет технологии распределенных вычислений", Новороссийск, 2005, II, V, IV и VII международные научно-технические конференции "Интеллектуальные и многопроцессорные системы", 2001,2003, 2004,2006 Публикации

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

Диссертация состоит из введения, четырех глав, заключения и приложения, имеются 3 рисунка Полный объем диссертации - 111 страниц, библиографический список содержит 123 наименования работ отечественных и зарубежных авторов В приложении приведена грамматика языка нелокальных схемных трансформаций и 2 акта об использовании результатов работы

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Основными классами современных параллельных архитектур являются машины с общей и распределенной памятью Наиболее дешевым и потому распространенным вариантом распределенных систем являются кластеры Многие современные параллельные системы представляют собой гибридные архитектуры Распространенными классами параллельных систем являются массивно-параллельные компьютеры (МРР), симметричные мультипроцессорные системы (SMP) системы с неоднородным доступом к памяти (NUMA), параллельные векторные системы (PVP) Большинство компьютеров из списка Тор 500 являются системами с распределенной памятью или гибридами этой архитектуры, например, векторно-параллельные

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

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

♦ Традиционные последовательные языки, расширенные директивами компилятора, новыми конструкциями, дополнительными служебными функциями, специальными переменными окружения (OpenMP, DVM, шрС, параллельные расширения Фортрана - HPF, Vienna Fortran и другие) Параллельные расширения языков существуют для самых разных классов параллельных архитектур

♦ Использование библиотек параллельных методов, чаще всего для распределенных архитектур (Aztec, LAPACK, PBLAS, ScaLAPACK и другие)

♦ Системы программирования на основе передачи сообщений Наиболее распространена технология MPI для распределенных машин

♦ Специальные языки параллельного программирования (Occam, МС#, Т-система, НОРМА, Adl, Erlang, Linda, Sisal, ZPL и другие)

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

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

В этой области было выполнено множество работ как в бывшем СССР и России, так и за рубежом Среди исследователей можно отметить Л Лемпорта, У Банержи, Р Алена, К Кеннеди, Д Кука, Д Падуа, M Вольфа, В Е Котова, В А Вальковского, В В и Вл В Воеводиных и многих других Для некоторых суперкомпьютеров, в частности, векторных и конвейерных, были созданы коммерческие распараллеливающие компиляторы Существует несколько весьма эффективных исследовательских инструментальных систем распараллеливания Тем не менее, на тему распараллеливания ежегодно продолжают появляться десятки работ Отчасти это обусловлено постоянным появлением новых параллельных архитектур

Методы распараллеливания можно классифицировать по способу выполнения, уровню распараллеливания, методу выявления параллельного кода

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

Практика показала, что ручное распараллеливание не только значительно более трудоемко, чем автоматическое, но бывает даже менее эффективным

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

Распараллеливание на уровне операторов и команд выполняют для конвейерных архитектур, а также для УЬШ-машин, для этих архитектур существуют эффективные распараллеливатели В стадии исследований находится Опфытая система распараллеливания, ориентированная, в частности, на макроконвейерный суперкомпьютер с программируемой архитектурой, создаваемый в НИИ МВС, Таганрог

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

Основой распараллеливания является анализ зависимостей по данным Методом выявления параллелизма на основе анализа индексных выражений были предложены Л Лемпортом, В А Вапьковским

Очень популярной для анализа возможности распараллеливания является идея различных графов зависимостей по данным (ГЗД) Теория зависимостей по данным сформировалась в работах Д Кука, У Банержи, М Вольфа, Р Аллена и К Кеннеди Дугами ГЗД являются 4 типа зависимостей истинная (потоковая), по входу, по выходу и антизависимость, а вершинами — операторы, в европейской и японской школах в качестве вершин рассматривают отдельные вхождения переменных Направления зависимостей отражают разницу между номерами итераций, порождающих зависимость в цикле На основе ГЗД и его вариантов было выполнено множество работ по векторизации программ, использовался данный граф и для предварительной оптимизации

Более удобный анализ зависимостей по управлению совместно с зависимостями по данным можно выполнять по графу программных зависимостей Дж Ферранте, К Отгенштейна и Д Уоррена

Академик В В Воеводин создал методику распараллеливания на основе анализа решетчатого графа, идея которого была предложена А П Ершовым Решетчатый граф содержит информационные связи 4 типов и строится на основе анализа индексных выражений Возможность параллельного исполнения определятся путем анализа разверток — функционалов, построенных по коэффициентам решетчатого графа

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

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

Распараллеливание на уровне процедур и заданий стало особенно актуально при распространении машин с распределенной памятью Анализом межпроцедурных за-

висимостей занимались и в 80-е годы, но в настоящее время несколько систем распараллеливания обладают такой возможностью

Следует отметить направление распараллеливания путем замены устойчивых шаблонов (идиом) программ на обращения к библиотекам или параллельные варианты распознанных алгоритмов Более общее направление параллельного программирования на основе шаблонов, так называемый скелетный параллелизм, занимается также генерацией параллельных программ и проектированием проблемно-ориентированных параллельных языков программирования высокого уровня на основе шаблонов программирования

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

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

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

Зарубежные исследования преобразований программ также начались с оптимизации и трансляции В конце 60-х гг было заложено направление синтеза программ, иначе называвшееся трансформационным программированием, к началу 80-х в этой области было получено много результатов В начале 20-го века к области трансформаций программ за рубежом стали причислять многие другие научные направления, от компиляции и суперкомпиляции до реинжениринга программного обеспечения Одним из приложений трансформаций является автоматическое распараллеливание программ

Введем основные понятия из области трансформаций программ (Заметим, что в этой области отсутствует устоявшаяся терминология )

Трансформация программы — это действие по преобразованию одной программы в другую Более строго, трансформация (преобразование) программы — это частичное отображение одного формального описания программы в другое Формальное описание алгоритма или отношения, которые реализуют данное отображение программ, называют правилом трансформации (иногда также трансформацией программы) Языки исходной и целевой программ могут различаться или быть одинаковыми Для трансформации может быть сформулировано предикатное контекстное условие (условие применимости), которое ограничивает область действия отображения программами определенного класса

Трансформации программ (правила трансформаций) подразделяются на процедурные и непроцедурные Процедурное описание преобразования представляет собой алгоритм (программу) получения результата, непроцедурное описание— пару схем заменяемого и заменяющего фрагментов (схемное правило) Под схемой понимают некую модель программы Чаще всего схема записана на специальном языке трансформаций программ Мы используем определение схемы как исходного текста про-

граммы, параметризованного по некоторым вложенным синтаксическим компонентам

Преобразование программ согласно правилам трансформации обеспечивается трансформационными системами (системами трансформаций программ, СТП) Обычно трансформационными называют системы, чьей единственной функцией является преобразование программ, за системами со многими функциями оставляют традиционные названия компилятора, CASE-системы

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

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

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

Большинство средств распараллеливания использует преобразования программ в алгоритмической, процедурной форме К ним относится и система V-ray Вл В Воеводина

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

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

Распараллеливающая СТП МТ1 (университет гДельфта) использует правила на параметризованном языке С Они наглядны, но строго локальны и не могут включать процедурных частей Условия применимости правил включают условия на графе зависимостей некоторого вида

Непроцедурные распараллеливающие преобразования, заданные на абстрактном дереве программы, используют системы распараллеливания PARAMAT и ее наследница SPARAMAT К Кесслер выявил 150 содержательных шаблонов программирования, ставших основой для правил трансформации Образцами в правилах служат па-

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

Некоторые универсальные ТС и средства преобразования текстов используют интересные с точки зрения нашей задачи решения

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

То же самое относится и к регулярным выражениям как средству преобразования произвольных текстов Регулярные выражения очень похожи на шаблоны на уровне синтаксиса, предоставляют сходные синтаксические средства (например, идентификатор, число, нечто идущее после указанной конструкции, именование найденных фрагментов и т д) Но в них нет дополнительной семантической разметки Например, нельзя найти условный оператор общего вида или оператор вообще, объект определенного типа

Распространенный и применяемый для задания трансформаций во множестве областей непроцедурный язык Stratego задает преобразования на уровне абстрактного дерева программы Преобразования могут быть нелокальными, как и в системе РА-RAMAT, но слишком громоздки

Чисто синтаксические языки разметки (XML, XSLT) во-первых, задают только локальные преобразования, во-вторых, не учитывают семантику

Преобразования рассредоточенных в тексте программы, но объединенных по смыслу фрагментов выполняют в аспектно-ориентированном подходе к программированию (АОП) В АОП связанные по смыслу части программы, рассредоточенные в ее тексте, объединяются в аспект, который преобразуется в процессе построения программы или ее сопровождении

АОП активно развивается и успешно применяется при создании реальных, в том числе коммерческих программных систем

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

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

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

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

правило = 'rule' имя-правила ['(' список-параметров-правила ')']''

[ 'var' описание-переменных-правила',' ]

составной-входной-образец

'&&' [ условие-применимости ]

'=>' составной-выходной-образец

'end'

Составной образец представляет собой упорядоченный набор простых образцов, связанных общими параметрами либо семантическими отношениями

Простой образец может быть схемным и процедурным Схемный входной образец включает идентифицирующее выражение и схему программной конструкции схемный-образец = '<' идентифицирующее-выражение '>' схема Схема программной конструкции — это параметризованный по некоторым вложенным синтаксическим компонентам текст программной конструкции Параметрами схемы могут быть только законченные синтаксические конструкции (а не произвольные строки, как, например, в регулярных выражениях) Входные и выходные параметры схемного правила описываются после его заголовка Для каждого параметра должны быть указаны его имя и синтаксический тип

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

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

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

С помощью операций beforeO и after0 можно задать положение идентифицируемой конструкции до или соответственно после аргумента этих операций идентифицирующее-выражение = синтакс-тип [' ' псевдоним-конструкции] |

[синтакс-тип] ( псевдоним-конструкции | '$'имя-параметра ) { ' 'отношение} [ ' ' псевдоним-конструкции] |

[синтакс-тип] ( 'before' | 'after' ) '(' ( псевдоним-конструкции | '$'имя-параметра ) {' 'отношение}')' [' ' псевдоним-конструкции]

Процедурный образец— это функция на языке реализации трансформационной системы, результатом которой является множество синтаксических конструкций

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

Условие применимости— логическое выражение, которое включает кванторы всеобщности и предикаты, зависящие от входных параметров правила Компоненты условия применимости соединены логическими операциями & ("и"), or ("или"), not ("нет") В состав условия также входят операции сравнения и проверки на равенство, операции присваивания и арифметические вычисления Условие применимости включает вычисление выходных параметров правила с помощью предикатов, арифметических выражений и функций

Применение правила происходит следующим образом

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

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

2 Проверка условия применимости При этом по входному образцу, в частности, значениям входных параметров, вычисляются значения выходных параметров правила

3 Подстановка вместо найденной многосвязной структуры другой многосвязной структуры, полученной из составного выходного образца путем подстановки входных и выходных параметров правила___

Составной входной образец правила Схема программы

^^гаСоДО^даение первого из несодо^тавленных простых образцов, * ; Неконкретизированные входные параметры этого образца получают значения

Подстановка всех найденньк входных параметров во Iвеё^едуюпдаё несопоставленные простые образцы

" 'I * " " "

Значения всех входных параметров

X

Йровещаусловия применимости. Попутцов: вычисление выходных параметров правила

I

ЩастщойМ]вхр|щых и выходных параметров в,каждый из простых образцов в составе со-^ - - - ставного, выходного образца "

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

Преобразованная программа

Рис 1 Порядок применения правила

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

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

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

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

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

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

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

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

схема-конструкции = $ all параметр-образца in множество $ схемы-конструкций

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

схема-конструкции = <идентифицирующее-выражение> схемы-конструкций

4 Можно указать повторение любого числа (ноль или более) синтаксических конструкций заданного типа, вид которых не важен, и схема потому опускается

схема-конструкции > '{' синтакс-тип '}'

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

rule имя-правила (параметры-правила)

[var описание переменных правила,]

простой-образец1

&& часть 1-условия-применимости

простой-образец2

&& часть2-условия-применимости

простой-образецИ && частьЫ-условия-применимости => составной-выходной-образец end

6 Добавлена возможность удаления фрагмента кода путем указания пустого выходного образца

7 Введена инструкция условной вставки синтаксической конструкции $ if логическое-выражение $ выходная-схема-конструкции

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

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

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

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

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

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

В качестве языка входной программвг выступает ограниченное подмножество Фортрана 77, выходной— Фортран с параллельными конструкциями Во входном языке отсутствуют подпрограммы и функции, COMMON-блоки, операторы ввода/вывода

Приведем примеры правил трансформации

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

<labei> — метка,

<var> — переменная,

<num_expr> — числовое выражение,

<assign> — оператор присваивания,

<1оор> — оператор цикла,

<stmt_seq> — последовательность операторов,

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

nested(L, Nest) — цикл L является вложенным в гнездо циклов Nest level(L, Nest, М) — цикл L является циклом вложенности М в гнезде циклов Nest no_jumps(L) — нет переходов (goto разных видов) извне внутрь цикла L, а также в теле цикла, передач управления на следующую итерацию и аварийных выходов из цикла

substmt(Sl, S2) — оператор S1 содержится в операторе S2 Это возвратный предикат, то есть при каждом следующем вызове выдает новое возможное значение своего первого параметра, пока все его значения не будут исчерпаны

stmt_type(Sl, Name) — оператор SI является оператором типа Name (например,

do)

dep(Sl, S2, Type, Dir)— между операторами SI и S2 существует зависимость по данным типа Туре с вектором направления Dir Данный предикат задан на графе зависимостей по данным

full_reachable_c(Sl, S2) — S2 достижим по управлению из S1 по любому из путей на управляющем графе, ведущих из S1 в S2

unchanged_between(v, SI, S2)— переменная v не изменяется на участке программы на всех путях передачи управления от оператора S1 до оператора S2

hnear(expr, id, a, b) — выражение expr линейно относительно переменной id с коэффициентами а и b

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

Предполагается, что циклы уже нормализованы, т е их счетчики целые и нижние границы равны 1

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

Исходный фрагмент

mc = n - 1 SI

do 1 i=l, 3

x(mc) = y(i) + z(2*i) $stsl

inc = mc - -1 S2

Конкретизация параметров

$i = i $Ub = 3 $sts2 = [] $id = mc

$mc_expr = mc - 1 Sexprl = n - 1 $b = -1

Выходной параметр $id_v = -1 *(3) + n - 1

Преобразованный фрагмент

do 1 1=1,3 x(—1 * (l - 1) + (n - 1)) = y(i) + z(2*i) 1 continue mc = n— 4

Рис 2 Пример применения правила

rule induct 1 var <label> label, <stmt_seq> stsl, sts2, <var> l, id,

<num_expr> Ub, mc_expr, <loop L> ( do Slabel $i=l to $Ub

$stsl

<assign S2> $id=$inc_expr $sts2

continue )| <before(L) Sl> ($id =$exprl)

&& full_reachable_c(Sl, loop) & linear(mc_expr, $id, 1, $b) & un-changed_between($id, SI, S2) & no_jumps(L) & $id_v = $b*($Ub) + (Sexprl) =>(<S1>()I do $label Si =1 to $Ub apply (($id => $b*($i-l) + (Sexprl)), Sstsl) apply (($id => $b*$i + (Sexprl)), $sts2) Slabel continue )

$ if dep(S2, $id, flow) $ $id = $id_v end

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

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

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

Параллелизация для цикла однократной вложенности Один из способов использования мультипроцессорности состоит в том, что разные итерации цикла назначают разным процессорам Такое исполнение цикла называется параллельным (кон-куррентным) В различных параллельных расширениях Фортрана независимое исполнение итераций цикла обозначается разными директивами, мы оставим часто употребимое в литературе обозначение doall

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

В данном варианте преобразования мы рассматриваем цикл, который не входит в гнездо циклов Параплелизацию для гнезда циклов мы рассмотрим ниже, так как ГЗД вложенных циклов отличается от ГЗД цикла однократной вложенности

Исходный фрагмент Преобразованный фрагмент

do 1 i=l, n doall 1 i=l, п

S1 a(i) = ад + a(i) a(i) = f[i) + a(i)

1 continue 1 continue

dep(Sl,Sl,flow,'=') — между SI и SI существует потоковая зависимость с направлением (=), что не препятствует одновременному выполнению итераций цикла)

Рис 3 Пример применения правила

rule parallelize 1

var <label> label, <var> l,

<num_expr> Ub, <stmt_seq> body, <loop L> ( do $label $i=l, $Ub $body

Slabel continue)

&& not nested(loop) & not enclosed(loop) & all SI, substmt(Sl, $body), S2, substmt(S2, Sbody), dep(Sl, S2,_,'=') & nojumpsto(Slabel) => doall Slabel i=l, $Ub Sbody

Slabel continue

end

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

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

В рамках данной работы выполнена макетная реализация МСТП в Пролог-системе Eclipse При построении внутренних представлений программы частично используется (после портирования их автором) код модулей на Anty Prolog, реализованных С А Лазаревой

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

Язык сценариев является суженным подмножеством языка С++, к которому добавлены операции над множествами Он включает операторы циклов, условные операторы, описания переменных базовых типов, а также типа "множество", операторы применения правил трансформации и вызовы служебных процедур (например, построения графа зависимостей по данным)

Оператор apply_опсе3 означает применение правила к первой сопоставимой конструкции внутри программы или программной конструкции-аргумента, apply — применение правила до исчерпания возможности (или не будет достигнуто заданное предельное количество проходов), apply_set — асинхронное применение независимого подмножества правил до исчерпания

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

3 Букатов А А, Коваль В В Методы реализации трансформационной машины в многоцелевой системе преобразований программ // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственйого интеллекта, 2003, № 3, Донецк Наука 1 освта, С 6-14

распараллеливающие преобразования удобнее выполнять в режиме советчика или в полностью управляемом пользователем режиме

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

Для проверки условий применимости преобразований вычисляется граф зависимостей по данным

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

Порядок работы с макетом системы распараллеливания

1) Считывание грамматики входного языка и языка правил

2) Считывание сценариев

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

4) Анализ семантического дерева программы и построение графа зависимостей по данным

За), 4а) Считывание из файлов сохраненных во время предыдущего сеанса работы данных внутренних представлений программы, включая граф зависимостей по данным, внутренних представлений правил, а также перечня разрешенных правил для именованного набора фильтров

5) Запуск сценария преобразования входной программы

5а) Показ пользователю возможных вариантов преобразования и применение указанных им правил

6) Перевычисление внутренних представлений после каждого успешно выполненного преобразования или этапа сценария

7) Генерация текста выходной программы по ее семантическому дереву

В целом макет МСТП состоит из 1) машины трансформаций внутреннего представления программы, 2) набора правил распараллеливания, 3) модуля анализа зависимостей по данным, 4) модулей, создающих абстрактное внутреннее представление программы и правил и 5) модуля базовых предикатов проверки условий применимости преобразований, эти предикаты в основном специфичны для предметной области (связаны с зависимостями по данным и управлению) 6) переменных окружения, определяющих среду выполнения программы

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

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

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

Дерево программы состоит из деревьев операторов Структурой данных, реализующей дерево в макете МСТП, является дерево, хранимое как база вершин дерева Каждая вершина дерева представляет собой оператор программы и имеет вид терма орег(номер_строки_в_программе, метка, тип_оператора(атрибуты_оператора) В параметризованном семантическом дереве образца правила параметры этого правила могут занимать место любого поддерева или деревьев нескольких последовательно идущих операторов программы Параметры типа "идентификатор переменной", "константа" и "выражение" хранятся как подтермы, а типа "оператор" произвольного либо заданного типа и "последовательность операторов" — как термы структуры, подобной оператору программы

При поиске применимого правила трансформации дерево программы проходится в глубину, и для каждой вершины делается попытка унификации для всех правил, применимых на данном шаге сценария

Глубина рекурсивного спуска ограничена синтаксическими типами асинхронно применяемых правил не глубже самого "мелкого" синтаксического типа Например, если все правила преобразуют операторы, то на уровень тела цикла спускаться нужно, а на уровень выражений — нет

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

Алгоритм унификации параметризованного дерева составного входного образца и абстрактного семантического дерева программы Начало

Унификация(составной-входной-образец, поддеререво) Итерация по простым образцам

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

Унификация(простой-образец, поддерево) Итерация по списку операторов и идентифицированных конструкций Начало цикла

Если оператор имеет идентифицирующее выражение, проинтерпретировать выражение

Итерация цо цепочке отношений от самого вложенного аргумента

Начало цикла

Если аргумент — псевдоним, извлечь из памяти обозначаемую им конструкцию программы

Если отношение между конструкциями, найти по этой связи конструкцию программы

Если before/after, то Если идентифицирующее выражение всего простого образца, просмотр дерева вверх/вниз

Иначе проверить выполнимость отношения before/after для идентифицированной конструкции

Конец цикла

Если идентифицирующее выражение присваивает псевдоним идентифицированной конструкции программы, запомнить псевдоним и конструкцию Унификация(идентифицированная-конструкция, текущее поддерево) Конец цикла Конец цикла Конец

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

Параметр образца и поддерево, синтаксический тип параметра такой же или является обобщением типа поддерева (например, операторами являются присваивание и цикл) Успех, параметр = поддереву

Синтаксический тип поддерева образца одинаков с типом поддерева программы или является его обобщением Унификация всех пар поддеревьев

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

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

Полагаем пустое значение анонимного параметра Если унификация следующих операторов безуспешна, То добавляем к значению следующую конструкцию заданного типа Если такой конструкции нет, неуспех Конец алгоритма

После успешной проверки условия применимости получаем имя правила, список пар из вершин синтаксического дерева образца и вершин семантического дерева программы и список значений входных и выходных параметров (нетерминалов правила)

Рассмотрим пример распараллеливания с помощью набора преобразований распараллеливания и оптимизации по методике Аллена-Кеннеди

Преобразования выполняются автоматически по нижеследующему сценарию Будем считать, что построены абстрактные семантические деревья правил и программы В сценарии участвуют не только операторы применения правил трансформации, но и предикат cr_dep, который относится к сервисным функциям МСТП и выполняет построение графа зависимостей по данным void classic 0 { int 1,

apply set (normalizel, normalize2), /* нормализация (стандартизация) циклов */ apply_set (mductl, mduct2, mduct3), /* удаление индуктивных переменных */ apply wraparound, /* удаление охватывающих переменных */ apply_set(loop_fusion, loop distribution), /* слияние и разбиение циклов*/ apply interchange, /* перестановка циклов */ apply unfold, /* развертка циклов*/

for (i=l, i< MaxNest, 1++) apply parallelize(M), /* распараллеливание циклов разной вложенности, начиная с самых внешних и кончая самым глубоким уровнем вложенности в программе */ }

Для рассматриваемого примера фрагмента кода будут выполнены следующие преобразования

♦ Нормализация цикла

♦ Распознавание индуктивных переменных (2 прохода)

♦ Перестановка циклов

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

jj=0 doall 10 i_new_5=l,10

do 10j=l,10,2 do 10j_new_l=l,5

JJ=JJ + 1 xx(i_new_5, j_new_l,l)= x(i_new_5,2*j_new_l - 1,1)

n=0 xx(i_new_5, j_new_l,2)= x(i_new_5, 2*|_new_l - 1,2)

do 101=1,20,2 10 continue

H= li +1

XX(iljj,1)=X(IIJ,1) xx(ii,jj,2)= x(n,j,2) 10 continue

Рассмотрим подробнее наиболее интересный промежуточный шаг — параллели-зацию цикла для гнезда вложенности 2

Для исполнения разных итераций цикла разными процессорами итерации должны быть независимы

После перестановки циклов Граф зависгмо-

do 10 i_new_5=l,10 стей do 10j_new_J=l,5 SI зависит от S2 -Z^C1^®'^™^,x(i_nev^5,— i.fj j si noj new l при "x¥(Tn~e wJ5~j^ne w"f "x(i"new^5~2*JJri8w^l"-ЧJ"" "1 §2 J_new_l = 1, зави-confiriiie ..........................................симость не цикли-

ческая

Условие независимости итераций наружного цикла выполнено, в итоге получим следующий распараллеленный код doall 10 i_new_5=l,10 do 10j_new_l=l,5

xx(i_new_5,j_new_l,l)=x(i_new_5, 2*j_new_l -1,1) xx(i_new_5,j_new_l,2)=x(i_new_5,2*j_new_l -1,2) 10 continue

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

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

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

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

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

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

4 Модифицированный алгоритм унификации параметризованного дерева правила и семантического дерева программы

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2 Жегуло О А, Букатов А А Непроцедурное описание распараллеливающих преобразований программ в виде схематических трансформаций // Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения", г Черноголовка, 30 октября - 2 ноября 2000 г — М изд-во Московского университета, 2000 — С 147-150

3 Жегуло О А Представление знаний о методах распараллеливания в экспертной системе поддержки распараллеливания программ // Тезисы докладов международной конференции "Интеллектуальные и многопроцессорные системы", пос Дивноморское, 1-6 октября 2001 г —Таганрог изд-во ТРТУ, 2001 —С 176-178

4 Жегуло О А Представление знаний о методах распараллеливания в экспертной системе поддержки распараллеливания программ // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта — 2001 —№3 —Донецк Наука i освгга —С 323-330

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

6 Жегуло О А Методы настройки системы автоматического распараллеливания программ на параметры условий применения // Материалы Международной научно-технической конференции "Интеллектуальные и многопроцессорные системы", пос Дивноморское, Геленджик, Россия, 22-27 сентября 2003 г, т 2 — Таганрог изд-во ТРТУ, 2003 — С 68-70

7 Жегуло О А Методы настройки трансформационной системы автоматического распараллеливания программ на параметры условий применения // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта — 2003 — № 3 — Донецк Наука i освгга — С 88-94

8 Жегуло О А , Букатов А А Представление распараллеливающих преобразований программ в виде схемных правил трансформации // Труды Первой Всероссийской научной конференции, 1-3 октября 2003 г — М Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2003 — С 361-367

9 Жегуло О А Реализация экспериментальной системы распараллеливания на основе макета многоцелевой системы трансформаций программ // Материалы Международной научно-технической конференции "Искусственный интеллект Интеллектуальные и многопроцессорные системы", 20-25 сентября 2004г, т 1 —Таганрог изд-воТРТУ, 2004 —С 249-254

10 Жегуло О А Распараллеливание программ в экспериментальной системе, основанной на макете многоцелевой системы трансформаций программ // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта — 2004 — № 4 — Донецк Наука 1 освт — С 1-14

11 Букатов А А , Жегуло О А, Коваль В В Создание системы поддержки распараллеливания программ, основанной на непроцедурном описании распараллеливающих преобразований // Труды Всероссийской конференции "Научный сервис в сети Интернет технологии распределенных вычислений", Новороссийск — М изд-во МГУ, 2005 — С 69-71

12 Жегуло О А Экспериментальная система распараллеливания на основе макета многоцелевой системы трансформаций программ // Методы и средства обработки информации Труды второй Всероссийской научной конференции 5-7 октября

2005 г М Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2005 — С 246-251

13 Букатов А А, Жегуло О А Методики в основе построения расширяемой системы распараллеливания программ на основе непроцедурных трансформаций программ // Материалы Третьей Международной научной молодежной школы "Высокопроизводительные вычислительные системы", Крым — Таганрог изд-во ТРТУ, 2006 — С 239-243

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

2006 — Приложение № 10 — с 5-13

В совместной работе [1] автору принадлежит заключение о возможности непроцедурного задания распараллеливающих преобразований программ на основе результатов экспериментов, в работах [2], [8], [11] — разработка правил распараллеливающих трансформаций и использованные в определениях некоторых правил расширения языка нелокальных схемных трансформаций программ В работе [13] — обзор актуальных близких проектов среди технологий распараллеливания и программирования

Печать цифровая Бумага офсетная Гарнитура «Тайме» Формат 60x84/16 Объем 1,0 уч -изд -л Заказ № 374 Тираж 100 экз Отпечатано в КМЦ «КОПИЦЕНТР» 344006, г Ростов-на-Дону, ул Суворова, 19, тел 247-34-88

Введение

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) развитие средств визуализации и диалога с пользователем макета МСТП.

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/