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

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

□030В7'83Э

Тапкннов Батр Юрьевич

СТРУКТУРНО-ПРЕДИКАТИВНАЯ СИСТЕМА ПОСТРОЕНИЯ ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ ПРОГРАММ, ОРИЕНТИРОВАННОГО НА ОПТИМИЗАЦИЮ И РАСПАРАЛЛЕЛИВАНИЕ

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

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

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

003067839

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

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

Крицкий Сергей Петрович

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

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

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

Ведущая организация — Южно-Российский государственный

технический университет (Новочеркасский политехнический институт), г Новочеркасск

Защита состоится « ^ » 2007 г в //СО час на заседании

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

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

Автореферат разослан « зи января 2007 г

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

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

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

Муратова Г В

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

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

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

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

• постфиксная нотация;

• трехадресный код,

• синтаксическое дерево,

• другие граф-модели

Внутренние представления в современных компиляторах, как правило, реализуются в виде таких структур, как списки и деревья В некоторых системах оптимизации и распараллеливания программ, таких как Polaris1, SUIF/SUIF22, ОРС3, внутреннее представление программ реализовано в виде иерархии классов на объектно-ориентированном языке Основное преимущество представления в таком виде - это простота проектирования, модифицируемость и расширяемость

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

1 Система разработана в Иллинойском университете под руководством D Padua.

2 Система разработана в Стэндфордском университете под руководством М Lam

3 Открытая распараллеливающая система разрабатывается в Ростовском государственном университете под руководством Б Я Штейнберга

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

В 1980 году Ф Перейрой и Д Уорреном были описаны грамматики DCG5 (Definite Clause Grammars), относящиеся к классу логических грамматик Сейчас эти грамматики неизменно включаются во все развитые системы программирования на языке Пролог Эти грамматики в отличие от атрибутных грамматик, не требуют задания строгого порядка выполнения семантических правил Однако построение семантической структуры программы с помощью DCG, как и в атрибутных грамматиках, нужно описывать в процедурном виде (на языке Пролог)

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

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

4 Knuth D Е Semantics of Context-Free Languages // Mathematical Systems Theory 1968 2 N2 P 127-146

5 Pereira F , Warren D Definite Clause Grammars for Language Analysis - a Survey of Formalism and Comparison with Augment Transition Networks // Artificial Intelligence 1980 V 13 P 231-278

6 Крицкий С П Предикативные грамматики и аксиоматическое определение языков программирования и переводов // Компьютерное моделирование Вычислительные технологии Ростов-на-Дону ЦВВР, 2003 С 67-90

Для достижения поставленной цели решаются следующие задачи

1 Создание программной реализации СП-грамматик, представления структурного графа и алгоритма унификации вершин структурного графа и термов

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

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

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

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

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

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

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

Апробация результатов работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции "Научный сервис в сети Интернет технологии параллельного программирования", г Новороссийск, 2006 г, на научно-методической конференции "Современные информационные технологии в образовании Южный федеральный округ", г Ростов-на-Дону, 2006 г, на научных семинарах кафедр ИВЭ и АДМ мехмата РГУ, на научно-исследовательском семинаре ЮГИНФО РГУ, 2006 г

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавторстве Из них 3 статьи в российском рецензируемом журнале, 1 статья в сборнике трудов аспирантов РГУ и 2 в тезисах докладов всероссийской и региональной конференций

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений Основной текст работы (без приложений) занимает 111 страниц, и включает 11 рисунков и 22 таблицы Список литературы содержит 98 наименований

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

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

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

Первый раздел данной главы, посвящен подходам к распараллеливанию программ Рассматриваются 3 основных подхода: «ручное», автоматическое и полуавтоматическое распараллеливание

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

Во втором разделе первой главы приводится обзор различных технологий параллельного программирования Рассматриваются расширения традиционных языков Фортран и Си, такие как HPF (High Performance Fortran), Fortran-DVM, C-DVM, mpC, а также коммуникационные библиотеки и интерфейсы параллельного программирования MPI, OpenMP, PVM

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

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

При обзоре средств автоматического распараллеливания программ упоминаются такие системы, как PEPS, семейство препроцессоров-векторизаторов КАР, VAST/Parallel Данные системы в значительной степени могут облегчить и ускорить разработку параллельных программ, однако получить с их помощью эффективно работающие параллельные программы не всегда удается

В заключение второй части первой главы приводится обзор средств создания и проектирования параллельных программ Рассматриваются отечественные проекты Открытая распараллеливающая система (ОРС), системы V-Ray, ПРОГРЕСС, ТРАНСФОРМ, а также зарубежные системы Parafrase, Polaris, SUIF/SUIF2, PTOOL и другие Хотя большинство из рассмотренных систем являются исследовательскими, в них используются более сложные методы исследования и преобразования программ, чем те, которые традиционно включаются в компиляторы или системы автоматического распараллеливания. Основной недостаток большинства из рассмотренных систем - это ограниченные возможности расширения Во-первых, многие системы для построения внутреннего представления программ используют внешние программы или библиотеки (ANTLR, Sage++, Bison, YACC, компиляторы Portland Group Inc ) с готовыми грамматиками языков, что ставит их в зависимость от сторонних разработчиков Во-вторых, внутреннее представление программ во многих системах ориентировано на конкретный язык, что может вызывать большие трудности при добавлении новых языков В-третьих, отсутствует поддержка динамически подключаемых библиотек (модулей), вследствие чего для внесения изменений или добавления новых возможностей требуется перекомпиляция всей системы

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

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

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

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

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

Определение: Структурным графом называется конечный ориентированный упорядоченный граф, удовлетворяющий следующим условиям

1 Каждая вершина графа помечена либо объектом первичного сорта (ОПС), либо конструктором, либо переменной, сорт метки считается сортом вершины, две вершины не могут помечаться одной переменной

2 Дуги графа соответствуют аргументам конструкторов, те выходят только из вершин, помеченных и-местным конструктором, где и > О, если тип конструктора/ 5Ь —> в, то из вершины /выходит п дуг и /-ая дуга входит в вершину V, сорта я, (вершины уь не обязательно различны) В этом случае вершину / можно обозначать /(VI, Л)

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

Унификация вершин структурного графа и термов (обозначается бинарным оператором =@=) используется в правилах СП-грамматики для построения семантической структуры программы и навигации по ней

Таблица 1

Алгоритм унификации вершин структурного графа и термов

Вершина графа Подтерм Результат

1 •Д>1, .V») Л'ь А) Переход к последовательной унификации вершин V) и термов и т д При этом найденные на каждом шаге подстановки применяются ко всему терму

2 Объект первичного сорта или 0-местный конструктор Тот же объект или конструктор Унификация вершины успешно завершена

3 Вершина Та же вершина

4 Вершина V сорта не являющаяся переменной Переменная X сорта у Все вхождения Хзаменяются на V, в графе вершины X и V отождествляются При отождествлении вершин в графе они отождествляются и в терме

5 Переменная X сортам Вершина V того же сорта

б Переменная X сортам Переменная У сорта 5 Отождествление (переименование) всех вхождений этих переменных В графе это может привести к отождествлению вершин X и У

7 Переменная X сорта 5 Терм Гсорта х, не являющийся вершиной или переменной (X может входить в Т) Вершины дерева терма Т и графа, помеченные ранее переменной X, отождествляются с корнем дерева терма Т Отождествляются и другие вершины полученного графа, помеченные одной переменной Остальные вершины дерева, не являвшиеся вершинами графа, становятся новыми вершинами графа.

8 В остальных случаях унификация невозможна

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

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

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

Таблица 2

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

Правила грамматики (продукции) Семантические правила

Е->Е\ + Т Enptr = mknode('+\ Е\ nptr, Tnptr)

Е-*ЕХ-Т Е nptr - mknode('-', El nptr, Tnptr)

£->Г Enptr = Tnptr

Г-»(£) T nptr = E nptr

Г—id Tnptr = mkleaflvi, id entry)

Т—* num Tnptr = mkleafltmm, num val)

В результате синтаксического анализа по данной грамматике арифметического выражения а - 4 + с будет построена семантическая структура этого выражения (рис 1)

к записи для а

Рис. 1. Семантическая структура выражения а — 4 + с

В следующей СП-грамматике, в отличие от описанной выше атрибутной грамматики, для построения семантической структуры арифметических выражений семантические правила не используются Структурный граф строится с помощью процедуры унификации вершин и термов 1: ехрг(ЛЕ) —> term(El),terms(El,Е). 2: term(AId) —> [id(Id)]. 3: term(ЛЫ) —> [num(N)].

4: term ГЕ) —> "(", expr(Е) , ")".

5: terms(ЛЕ1,ЛЕ)—> "+",term(Е2),terms(plus(El,E2),E). 6: terms(ЛЕ1,ЛЕ)—>"-",term(E2),terms(minus(El,E2),E). 7: terms(ЛЕ,ЛЕ) —> "".

В таблице 3 описывается пошаговый анализ по СП-грамматике и построение семантической структуры выражения а — 4 + с

Таблица 3

Пошаговое построение семантической структуры выражения

№ Вызов правила Действия и результат Структурный граф

1 1- ехрг(Е)

2 2. term(El) %Действия El =6= а ^Результат %Е1 = R0 ®а

3 6 terms (Ro,E) %Действия Е1 =6= Во %Результат %Е1 = R0 ®-

4 3- term(E2) %Действия: Е2 =8= 4 %Результат: %Е2 = Ri

5 5 terms (minus (R0/ Ri), E) %Действия: El =8= minus (R<>,Ri) %Результат %Е1 = R2 (ih) mmus х\ @" @4

6 2 term(E2) ^Действия: Е2 =8= с %Результат-%Е2 = R3 (ft) nunus ® с ®° ®4

7 7 terms (plus (R2,Rj), E) %Действия. Е1 =0= plus(Ra,R3) , Е =8= Е1 %Результат %Е1 = R< %Е = R4 ® plus minus Л^) с ®" ® 4

Второй раздел данной главы посвящен программной реализации СП-грамматик, состоящей из трех этапов

1 выбор представления структурного графа,

2 реализация алгоритма унификации вершин структурного графа и термов;

3 разработка способа преобразования правил СП-грамматики в правила Пролога

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

Таблица 4

Представление структурного графа

Вершина, помеченная представлена записью в БД, в которой хранится

переменной переменная

объектом первичного сорта константа (атом, число, строка)

конструктором Дуъ \ъ , у„) структура./^,, Я2,. , Я„) (Я, - ссылки)

конструктором [V,, У2, , У„] список [Л], Я2, ,Я„](Я,- ссылки)

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

Я —► V (Я — ссылка, V— метка вершины) или

Я0 ► —|► —► Як —» V (Я, - ссылки) в тех случаях, когда происходит отождествление вершин

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

Таблица 5 Представление структурного графа

Представление Тип

конструктор

конструктор

Я2-+А переменная

Я3~* V ОПС

Я4-*5 ОПС

Рис 2. Структурный граф

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

На рисунке 3 изображена ситуация, когда унифицируется несколько вершин структурного графа (А и В - вершины переменные, V — вершина любого типа) В результате унификации вершин

А =@=В В=@= V

структурный граф (рис 3, а) должен быть перестроен, как показано на рисунке 3, Ь

Рис. 3. Унификация нескольких вершин структурного графа

Для этого потребуется отыскать в графе все родительские вершины /и/ъ , /6 по отношению к вершинам А и Б, и заменить в них ссылки, так чтобы они ссылались на вершину V При большом количестве вершин в графе поиск родительских вершин может занять много времени Для ускорения поиска можно было бы для каждой вершины хранить обратные ссылки на родительские вершины Однако такой подход требует использования дополнительной памяти

Предлагается следующее решение этой проблемы Обозначим через Я, —* V/ — вершину-переменную, а через VJ —

вершину любого типа Для отождествления этих двух вершин запишем в запись по ссылке Я, ссылку Л, В результате отождествления из двух вершин получится одна, представленная в виде Я, —> —* V/ Чтобы получить метку такой вершины, представленной цепочкой ссылок, используется рекурсия Решение описанной выше ситуации изображено на рисунке 4 Еще одна сложность, с которой пришлось столкнуться при реализации алгоритма унификации, заключается в ситуации, когда нужно выполнить откат изменений в графе при неудачной унификации (в Прологе предусмотрен откат только для обычной унификации термов) Для решения данной проблемы был предложен следующий способ

после отождествления его вершин

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

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

Для преобразования СП-правил в правила Пролога необходимо

1. Заменить в заголовке правила параметры Г„ помеченные унарным оператором Л, новыми переменными X,

2 Добавить в заголовок правила параметры Л0 и Кг, где Я0 - ссылка на начало входной цепочки лексем, Яг — ссылка на начало оставшейся части цепочки лексем после разбора (аналогичный прием используется при преобразовании правил грамматики БСв в правила Пролога)

3 В начало правой части правила для каждого помеченного параметра Г, вставить предикат унификации X, =@= У, вершины X и терма У

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

Таблица 6

Преобразование правил СП-грамматики в правила Пролога

Правило СП-грамматики Правило Пролога

N ( f AYl( , aY2, ,AYm, ) —> N( ,Xlf ,X2, , Xm, , R0<RZ) .-

Xx Y1(

Xm =8= Ym,

[EilLJ , cmp( [ExILx] ,R0,Ri) ,

N x( ), Ni( ,RJ,R2),

Nlf . Rf.Rf+i) t

[Ej I L-j ] , cmp( [E31 L-,] , Rf+ir Rf+г)

N1+1 ( ) , N3. + 1 ( , Rf+2f Rf + з) r

{Tr}, Tr,

Nk( ) • Nt( ,RZ_1(RZ)

Здесь предикат cmp(i, R„ R,) считывает лексемы из входного потока, начиная с лексемы R„ и сравнивает их со списком терминальных символов L Если сравнение проходит успешно, то предикат возвращает R} - ссылку на следующую лексему для анализа

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

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

Для возможности дальнейшего расширения внутреннего представления введен обобщенный конструктор для представления операторов программы stmnt{Label, Parent, Block, Prev, Next, Name, Args)

Аргументы

Label — метка безусловного перехода на данный оператор

Parent — оператор-родитель, т е оператор, под непосредственным

управлением которого находится данный Block - блок операторов, в котором находится данный оператор Prev, Next - предыдущий и следующий операторы в блоке (по месту

расположения в тексте программы) Name — идентификатор оператора. Args - список аргументов

Пример 3. На рисунке 5 изображен структурный граф для фрагмента программы

Id = Exprl; L: if <Expr2)

Stmntl;

else

Stmnt2;

Для построения внутреннего представления программ и работы с ним используется процедура унификации вершин структурного графа и термов Например, создать представление оператора присваивания n = n + (k-l) можно следующим образом.

NewSt =@= stmnt(L,P,B,Sl,S2,let, [n, plus(n,minus(k,1))]) В результате унификации будет построено дерево терма (рис 6) stmnt ( ), а в переменную NewSt будет записана ссылка на корень этого дерева — вершину-конструктор stmnt

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

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

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

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

Вершинами в графе вызовов процедур являются программные единицы (главная программа, процедуры и функции), описанные в тексте программы

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

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

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

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

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

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

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

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

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

• ядро;

• дополнительные модули,

• интерфейс

Ядро системы написано на языке Пролог в системе логического программирования Ап1у/Рго1о§32 и включает в себя

• средства для работы со структурным графом,

• конвертер правил СП-грамматики в правила Пролога,

• предикаты для взаимодействия ядра с интерфейсом системы,

• вспомогательные предикаты

Дополнительные модули так же, как и ядро, реализованы на Прологе К ним относятся

• лексический анализатор;

• СП-грамматика исходного языка,

• средства анализа внутреннего представления,

• преобразования,

• средства визуализации внутреннего представления,

• генератор исходного кода,

• вспомогательные утилиты

Интерфейс системы (рис 7) реализован на Visual С++ в виде многооконного редактора, в котором можно создавать и редактировать тексты пользовательских программ и модулей системы (в том числе и СП-грамматик) Помимо текстов программ в главном окне могут отображаться

• подключенные модули системы,

• внутреннее представление программы,

• отладочная информация

Данная система является экспериментальной и, конечно, уступает по количеству преобразований, средствам анализа и визуализации таким системам, как SUIF/SUIF2, Polaris, ОРС, PIPS, V-Ray, которые разрабатываются уже на протяжении нескольких лет целыми группами разработчиков Однако у этой системы есть ряд возможностей, которые могут оказаться полезными как для обычных пользователей, так и для разработчиков компиляторов

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

Во-вторых, дополнительные модули, в которых содержится основной функционал системы, абсолютно открыты для пользователя Таким образом, система может легко расширяться пользователями путем добавления новых преобразований, средств анализа и визуализации, поддержки других языков программирования В других системах возможности расширения для пользователей либо вообще отсутствуют (V-Ray, PTOOL), либо ограничены отсутствием собственного парсера (SUIF/SUIF2, Cetus) или ориентированностью внутреннего представления программ на конкретный язык (Polaris, Parafrase)

В-третьих, управление модулями во время работы с системой происходит динамически То есть пользователь может подключать, отключать или изменять дополнительные модули, не компилируя их и не выходя из системы Это может быть полезным, например, при написании и отладке преобразований В системе SUIF/SUIF2 имеется аналогичная возможность динамического подключения модулей, однако, модули должны быть откомпилированы

В-четвертых, при работе с большими программами, анализ которых может занимать много времени, у пользователя есть возможность сохранения построенного внутреннего представления программы в файл Таким образом, пользователь может продолжить свою работу с момента сохранения или открыть файл с внутренним представлением программы в интерпретаторе Arity/Prolog32 для пошаговой отладки модулей системы, например, средств анализа и преобразований Из рассмотренных систем такой возможностью обладает только система SUIF/SUIF2

В приложении А приводится описание подмножеств языков Си,

Паскаль и Фортран, для которых были разработаны СП-грамматики

В приложении В приводятся реализации описанных в работе

алгоритмов на языке Пролог

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

1 Разработана программная реализация СП-грамматик, включающая в себя способ представления структурного графа, реализацию алгоритма унификации вершин структурного графа и термов, интерпретацию правил СП-грамматики

2 Разработаны СП-грамматики для подмножеств языков Си, Паскаль и Фортран, ориентированные на построение внутреннего представления программ в виде структурного графа

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

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

Основные публикации по теме диссертации

1 КрицкийСП, Тапкинов Б Ю Реализация оптимизирующих преобразований программ с помощью структурных предикативных грамматик // Приложение к журналу «Известия вузов СевероКавказский регион Естественные науки», 2006, № 1, С 3-13

2 Крщкий С П, Тапкинов Б Ю Система построения оптимизирующих и распараллеливающих компиляторов // Приложение к журналу «Известия вузов Северо-Кавказский регион Естественные науки», 2006, №9, С 24-28

3 Тапкинов Б Ю Преобразование правил структурной предикативной грамматики в правила ОС-грамматики // Труды аспирантов и соискателей Ростовского государственного университета, Ростов-на-Дону, 2005, т XI, С 28-30

4 Тапкинов Б Ю Внутреннее представление программы в Системе построения оптимизирующих и распараллеливающих компиляторов // Труды Всероссийской научной конференции «Научный сервис в сети Интернет технологии параллельного программирования», Новороссийск, 18-23 сентября 2006, С 88-91

5 Тапкинов Б Ю Обучающие аспекты системы построения оптимизирующих и распараллеливающих компиляторов // Тезисы научно-методической конференции "Современные информационные технологии в образовании Южный федеральный округ", Ростов-на-Дону, 20-21 апреля 2006, С 240-242

6 Тапкинов Б Ю Представление структурного графа и реализация алгоритма унификации его вершин и термов // Приложение к журналу «Известия вузов Северо-Кавказский регион Естественные науки», 2006, № 1,С 30-36

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

Подписано в печать 0,5.04, С*? Формат 60*84 '/1в Бумага офсетная Печать офсетная Объем^^физ печ л. Тираж^/ООэкз Заказ № 2.ЧЭ

ИПОРГПУ

344082, г Ростов-на-Дону, ул Большая Садовая, 33

Введение.

Глава 1. Современное соеюяние исследований в облаем и оптимизации и распараллеливания программ.

1.1. Различные подходы к распараллеливанию профамм.

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

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

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

1.2. Технологии параллельною программирования.

1 2.1. Яшки параллельного программирования.

1 2.2 Коммуникационные бибпиогеки и ишерфейсы параллельного программирования.

1.2.3. Среде 1ва автмажческого распараллеливания профамм.

1 2.4. Средсгва создания и проектирования параллельных программ.

1 2 5 Специализированные параллельные библиотеки.

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

13 1. Управляющий граф.

13 2 1 раф зависимости по данным.

1 3 3 Граф программных зависимоеIей.

1 3 4 Граф вызовов процедур.

1.3.5. Решетчатый граф

1 3.6 Граф вычислений программы.

1 3 7 Иерархический граф заданий.

1.4 Выводы

Глава 2 Сфук1урные предикативные грамматики и струк1урный фаф.

2 1. Формализмы для описания семантики языков программирования и построения семантической арук1уры ирофамм

2 1 1 Атрибутные грамматики

2 1 2 ОС-грамматики и ОСС-нотация.

2.1.3. Структурные предикативные фамматики.

2 2. Реализация струюурных предикативных граммашк.

2.2.1. 11редс1авчение структурною фафа.

2.2.2. Реализация алюритма унификации вершин структурного графа и 1ермов.

2.2.3. Преобразование правил струк1урнои предикативной грамматики в правила Пролога.

2.2 4. Средства работы со струк1урным фафом.

2.3. Выводы.

I лава 3. Использование структурною фафа для оптимизации и распараллеливания программ.

3.1.11ромежу1 очное представление профаммы.

3.1.1. Структура промежуточною предеывления.

3.1.2. Элементарные преобразования.

3.2. Построение информационных структур.

3.2.1 Управляющий граф

3.2 2.1 раф зависимоеIей по данным.

3 2 3 Граф вызовов процедур

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

3 3 1. Про 1Я1 ивание констант.

3 3 2 Удаление "мертвого" кода.

3 3.3. Удаление недостижимою кода.

3 3 4. Упрощение арифмежческих выражений.

3 3 5. Канонизация цикла

3.3 6 Разрезание цикла.

3.3.7 Слияние циклов

3 3.8 Развертка цикла

3 4 Результат и выводы

Глава 4 Структурно-предикативная система построения внутреннего представления профамм

4.1. Возможности сиаемы.

4.2 Структура сиаемы.

4.3. Рабош со сфуктурно-предикашвной сис1емой.

4.4. Сопоставление с дру1 ими системами.

4.5. Выводы.

Актуальность темы. Развитие вычисли ¡ельных сиаем, появление новых amiapaiHbix платформ и процессоров обуславливаю! необходимость разработки новых компиляторов Разработка эффекшвного компилятора - это фудоемкий и досшючно длительный процесс.

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

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

• постфиксная ношция;

• грехадресный код;

• синтаксическое дерево,

• другие граф-модели

Внуфенние представления в современных компиляторах, как правило, реализуются в виде таких струюур, как списки и деревья. В некоторых системах оптимизации и распаратлеливаиия ирофамм, таких как Polaris [9J, SUIF/SUIF2 [47], ОРС [96], внутреннее представление программ реализовано в виде иерархии классов на объектно-ориентированном языке. Основное преимущество представления в таком виде - ло просюта проектирования, модифицируемость и расширяемость.

За преобразование исходной программы во внутреннее представление отвечае1 анализирующая часть компиляюра или парсер Разрабо1ка парсера с нуля является очень трудоемкой задачей и может занять мною времени. Поэтому, чтобы ускорить и облегчить процесс ею разработки, как правило, используются специальные инсфуменш, так называемые юнераторы компиляторов (Lex/YACC [52], Пех/Bison [9]). Но даже при использовании гене5 раюров компиляторов за разрабсмчиком парсера остется решение основной задачи - описание сишаксиса и семаншки исходною языка с помощью некоторого формализма.

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

В 1980 году Ф. Перейрой и Д. Уорреном были описаны фамматики DCG [35] (Definite Clause Grammars), оiносящиеся к классу логических грамматик Сейчас эш грамматики неизменно включаются во все развитые системы программирования на языке Проло1 Oi и фамматики в смличие от атрибутных грамматик, не требуки задания строгого порядка выполнения семантических правил Однако построение семашической структуры программы с помощью DCG, как и в атрибушых фамматиках, нужно описывать в процедурном виде (на языке Пролог)

В 2003 году С II. Крицкий описал струк1урные предикативные фамматики [76] (СП-грамматики), основанные на понятии структурною графа программы и расширяющие DCG процедурой унификации вершин структурного графа и термов Эти грамматики обладаюi всеми возможностями DCG и при этом позволяют описывать построение семантической счруюуры программы и работу с ней в непроцедурном виде Однако эти грамматики не нашли широкого применения из-за отсутствия и\ реашзации, разрабоиа которой преде ывляется ак1уа1ьной задачей развития сиаем пое1роения компиляторов.

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

Для достижения нос явленной цели решаются следующие задачи:

1. Создание программной реализации СП-1 рамматик, представления структурною графа и алгоритма унификации вершин структурного графа и термов.

2. Применение СП-граммажк дпя определения и построения внуфеннего представления программ, написанных на процедурных языках, в виде структурною фафа.

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

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

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

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

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

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

Профаммно реагж зованные CII-iрамматики мо!ут бьпь использованы в качестве инструмент при разработке ошимитирующих и распараллеливающих компиляторов.

Апробация результант работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции "Научный сервис в сети Ишернет: техиолоти параллельного программирования", г Новороссийск, 2006 г., на научно-методической конференции "Современные информационные 1ехнологии в образовании: Южный федеральный oKpyi", i Ростов-на-Дону, 2006г., на научных семинарах кафедр ИВЭ и АДМ мехма1а РГУ, на научно-исследова1ельском семинаре ЮГИНФО PÍ У, 2006 г.

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавюрстве Из них 3 статьи в российском рецензируемом журнале, 1 ста!ья в сборнике трудов аспиратов РГУ и 2 в 1езисах докладов всероссийской и peí иональной конференций.

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

Объем и содержание работы. Диссерищия состоит из введения, четырех глав, заключения, списка ли1ера/уры и приложений.

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

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

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

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

В четвертой кшве описывается разрабо1анная структурно-предикативная система - про!раммныи комплекс, основанный на реализации СП-граммагик.

В заключении формулирую 1ся основные результаты рабош.

В приложении А приводи 1ся описание подмножеств языков Си, Паскаль и Фортран, для коюрых были разработаны С11-фамматики.

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

4.5. Выводы

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

Заключение

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

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

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

Разрабогана программная реализация СП-граммагик, включающая в себя способ представления струюурного графа, реализацию алгоритма унификации вершин структурного графа и термов, интерпретацию правил СП-грамматики Показано, чт о прог раммно реал и зованные Cl I-i рамматики moi ут быть использованы в качестве инструмента при разработке оптимизирующих и распараллеливающих компиляторов.

Разработаны СП-грамматики для подмножеств языков Си, Паскаль и Фортран, ориентированные на построение внутреннего представления программ в виде структурного графа

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

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

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

Итак, в ходе работы были получены следующие резулыаты:

1. Разработана профаммная реализация СП-грамма 1ик, включающая в себя способ представления структурного трафа, реализацию алгоритма унификации вершин аруктурного фафа и термов, интерпретацию правил CI 1-фаммагики.

2 Разработаны CII-фамматики для подмножеств языков Си, Паскаль и Фортран, ориентированные на построение внутреннего представления программ в виде аруктурного графа.

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

4. На основе реализации CII-фамматик и средств работы со структурным графом разработана экспериментальная сиаема для построения внутреннего представления программ, ориентированного на их оптимизацию и распараллеливание

1. Abramov S. М., Adamowitch A. 1., Nesterov I. A , Pimenov S. P., Shevchuk Yu V. Autotransformation of evaluation network as a basis for automatic dynamic parallelizing // NA1 UG'1993 Spring Meeting "Transputer: Reserch and Application", May 10-11, 1993.

2. Allen J. R., Kennedy K. Automatic Loop Interchange // Proc of ACM SIGPLAN'84. Symposium on Compiler Construction. Montreal, Canada. June 1984. SIGPLAN NOTICES 19. Vol.6. P.233-246.

3. Allen J.R., Baumgartner D., Kennedy К , Porterfield A. PTOOL: a semiautomatic parallel programming assistant // Int Conf. on Parallel Processing. Proc. 1986. Washington, D C. IFEE Сотр. Soc. Piess 1986. P. 164 170.

4. ANTLR (ANother Iool for Language Recognition) Reference Manual. httpV/www.antlr огц

5. Aztec. A Massively Parallel Iterative Solver Libraiy for Solving Sparse Linear Systems httpV/www cs.sandia gov/CRf/a/tecl html

6. Bacon D.F., Graham S.L. and Sharp O.J. Compiler Transformations for High Performance Computing Computer Science Division Iechnical Report UCB-CSD-93-781, U.C Berkeley, Oct 1993.

7. Banerjee U., Chen S. C., Kuck D., Towle R. 1 ime and Parallel Processor Bounds for Fortran-like I oops// IEEE Irans on Computers. 1979. C-28. No.9. P 660-670

8. Bison manual http //www gnu org/software/bison/manual/index.html

9. Blume W., Doallo R , Eigenmann R. a. o. Parallel programming with Polaris // Computer 1992 - Vol 29, N 12. - P. 78 - 82.

10. Brunei-J., Cheong H., Veidenbaum A., Yew P. C CIIIFF: a parallel simulation environment for parallel systems IJniv 111 CSRD Rep 1050, April 1991.

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

12. Calkin R., I lempel R., I loppe H. and Wypior P. Portable Programming with the PARMACS Message-Passing 1 ibrary // Parallel Computing. Special issue on massage-passing interfaces. 1994. No.20. P.615-632.

13. Callahan D., Cooper K., Hood R. T. a.o. Parallel programming support in ParaScope// Lect. Notes Comput. Sci. 1987. Vol.297. P.91 105.

14. Callahan D., Cooper K., Hood R T. a.o ParaScope: a parallel programming environment // The Int. J. of Supercomputer Appl. 1988. Vol.2, N4. P.84 99.

15. CreusiIIet B., Iiigoin F. Inteiprocedural analyses ofTortran programs. Kcole des Mines de Paris: lech. Rep , 1997.

16. Dongarra J. J., Duff 1. S., Sorencen D C., van der Vorst 11 A. Numerical Linear Algebra for High-Performance Computers. Philadelphia: SI AM. 1998. 342 P

17. ECLiPSe User Manuel. Release 4 2 London: Imperial College, 1999.

18. Eigenmann R., McClaughry P Practical tools for optimizing parallel programs. Univ. Ill CSRD Rep 1276, Jan. 1993.

19. Express User's Guide, version 3.2 5 , Monrovia, CA: Paiasoft Corporation . 1992

20. Ferrante J, Ottenstein K. J., Warien J. D. The Program Dependence Graph and Its Use in Optimization // ACM Transactions on Programming I anguages and Systems. 1987. Vol.9 No 3. P 319-349.

21. Geist A , Beguelin A , Dongana J, Jiang W., Manchek R. and Sunderarn V. PVM: A Users' Guide and Tutorial for Networked Parallel Computing. : MIT Press 1994

22. Gelernter D Parallel programming in I inda // Technical Report 359, Yale University Department ot Computer Science, Jan., 1985.

23. Girkar M., Polychronopouios C. D. I he HTG: An intermediate representation for progiam based on control and data dependencies IJrbana-Champaign: IJniv. of Illinois. May 1991 CSRD Rep 1046

24. Guarna V A., Jr., Gannon D., Jablonowski I), a.o. Faust An integrated environment for parallel programming // IEEE Software. July 1989. P.20 26.

25. Iigh Performance Fortran. http.//www.cipc rice edu/HPri7home.html

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

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

28. Lamport L. I he coordinate method for the parallel execution of DO-loops. -Sagamore computer confetence on parallel processing, 1973.

29. Lamport L The parallel execution of DO loops // Commun. ACM. 1974. V. 17, N2 P 83 -93.

30. Message Passing Interface I orum MPI: A Message-Passing Interface Standard // Int J Supeicomputer Applications. 1994. No.8. (3/4). Special issue on MPI.

31. Message Passing Interface (MPI) Foium Home Page, http://www.mpi-forum org

32. Padua D I he Delta program manipulation system. Preliminary design. Univ. Ill CSRD Rep 880, June 1989.

33. Pereira F , Warren D Definite Clause Grammars for I anguage Analysis a Survey of Formalism and Comparison with Augment Transition Networks // Artificial Intelligence. 1980. V 13 P. 231-278.

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

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

36. Polychronopoulos C., Banerjee (J Processor allocation for hoii/ontal and vertical parallelizm and related speedup bounds // IEEE Iransactions on computers.1987. Vol.C-36. No.4. P. 410-420.

37. 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, N 12 - P 31-37

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

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

40. Арапов Д. М., Калинов А. Я., Ласювенкий A. JI., Ледовских И. Н., По-сыпкин Н. А. Язык и система профаммирования для высокопроизводительных параллельных вычислений на неоднородных сетях // Программирование. 2000. N4. С. 55 80.

41. Ахо А.В, Сети Р., Ульман Д.Д. Компиляторы: принципы, технологии и инструменш.: Пер. с шил. М.: Издаюльский дом «Вильяме», 2001. -С. 500.

42. Ахо А В, Ульман ДД 1еория синтаксическою анализа, перевода и компиляции. 1.1. Синтаксический анализ. М.: Мир, 1978.

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

44. ЬукаювА А., Дацюк В Н, Же гул о А И. Программирование многопроцессорных вычислительных сис1ем. Ростов-на-Дону: ЦВВР, 2003. С. 191 -206

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

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

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

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

49. Воеводин В В, Воеводин Вл.В Параллельные вычисления. СПб.: БХВ-Петербург, 2003 с 436.

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

51. Евстигнеев В.А., Касьянов В.II. Инструмешальная сиаема для изучения преобразований программ // Интеллектуализация и качеаво программного обеспечения. Новосибирск- НСИ СО РАН, 1994. с. 90-99.

52. Евстигнеев В.А., Мирзуитова ИЛ. Анализ циклов выбор кандидатов на распараллеливание. Препринт ИСИ СО РАН. № 58. Новосибирск, 1999. -48 стр.

53. Евстигнеев В.А , Мирзуитова ИЛ. Иерархический граф заданий: свойства и алгоритм построения // Проблемы конструирования эффективных и надежных программ -Новосибирск: ИСИ СО РАН, 1995. С. 53 - 69.

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

55. Ершов А П. Современное состояние геории схем программ // Проблемы кибернетики. М : Наука, 1973. - Вып. 27. - С.87-110.

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

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

58. Касьянов В. Н. Оптимизирующие преобразования программ. Москва: Наука 1988 240 с71 .Касьянов В. H. Iеоретико-графовые задачи анализа управляющих графов транслируемых npoipaMM. Исследования по прикладной теории графов. Новосибирск:. 1986. С.9-26.

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

60. Кнут Д. Семаншка контекстно-свободных языков // Семантика языков программирования. М.: "Мир", 1980.-С. 137-161.

61. Колмогоров А.Н., Драгалин А Г. Матемашческая логика. М.: Изд-во МГУ, 2005.

62. Коновалов 11 А., Крюков В. А , 1 loi ребцов А А , Сазанов К). JL C-DVM -язык разрабо1ки мобильных параллельных профамм // Программирование. 1999. № 1. С. 20- 28.

63. Крицкий С.П. Предикативные фамматики и аксиомашческое определение языков программирования и переводов // Компьютерное моделирование Вычисли 1ельные технологии. Росюв-на-Дону: ЦВВР, 2003. С. 67 -90.

64. Крицкий С. II, Тапкинов Б 10 Реализация оптимизирующих преобразований программ с помощью структурных предикативных грамма!ик // Приложение к журналу «Извес1ия вузов. Северо-Кавказский регион. Естественные науки», 2006, № 1, С 3-13.

65. Крицкии С П., Тапкинов Ь 10. Сиаема посфоения оптимизирующих и распараллеливающих компиляторов // Приложение к журналу «Известия вузов Северо-Кавказский регион. L ci ее i венные науки», 2006, №9, С. 2428

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

67. ВО.Малинина Ю.В. Информационная система I РАСНФОРМ но преобразованиям про1рамм. // Проблемы конструирования эффективных и надежных профамм. Новосибирск, 1995 - С 128-136.

68. Мартышок В.В. Об анализе графа переходов для операторной схемы // Журн. вычисл. математики и мат. фи зики. 1965. - Т. 5, № 2. - С. 298-310.

69. Немнютин С. А., Слесик О. Л. Современный Фортран. Самоучитель. СПб.: БХВ-Петербур1, 2003. С. 353 365.

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

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

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

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

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

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

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

77. Тапкинов Б 10 Преобразование правил структурной предикативной грамматики в правила ОС-грамматики // Груды аспирантов и соискателей Ростовского государственного университета, Ростов-на-Дону, 2005, т. XI, С 28-30

78. IaiiKHHOB Б. 10. Представчение струк1урною графа и реализация алгоритма унификации ею вершин и 1ермов // Приложение к журналу «Известия вузов. Северо-Кавказский peí ион. Естеа венные науки», 2006, № 1, С 30-36.

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