Содержание к диссертации
Введение 5
Глава 1. Современное сосюяние исследований в обласіи оптимизации и
распараллеливания программ 11
1.1. Различные подходы к распараллеливанию проірамм 11
1.11. «Ручное» распараллеливание 11
-
Автоматическое распараллеливание 13
-
Полуавтоматическое распараллеливание 16
1.2. Технологии параллельної о программирования 16
1 2.1. Яшки параллельного программирования 16
1 2.2 Коммуникационные бибтиоіеки и ишерфейсы параллельного
программирования 19
1.2.3. Средсіва авюмаїического распараллеливания проірамм 21
1 2.4. Средсіва создания и проектирования параллельных программ 22
1 2 5 Специализированные параллельные библиотеки 25
1.3 Различные вариант внуїреннего представления программ 26
1 3 1. Управляющий граф 28
13 2 1 раф зависимости по данным 29
1 3 3 Граф программных зависимости 30
134 Граф вы зовов процедур 31
1.3.5. Решетчатый граф 32
1 3.6 Граф вычислений программы 33
1 3 7 Иерархический граф заданий 34
1.4 Выводы ... . 35
Глава 2 Сірукіурньїе предикативные грамматики и струкіурньїй іраф 37
2 1. Формализмы для описания семантики языков программирования и
построения семантической сірукіурьі программ 37
2 1 1 Атрибутные грамматики 37
212 DC-грамматики и DCG-нотация 40
2.1.3. Сгрукіурньїе предикативные ірамматики 44
2 2. Реализация струкіурньїх предикативных граммаїик 50
-
Предсіавчение структурною ірафа 51
-
Реализация аліоритма унификации вершин структурного графа и іермов 52
-
Преобразование правил струкіурнои предикативной грамматики в
правила Пролога 57
2.2 4. Среде і ва работы со струкіурньїм ірафом 60
2.3. Выводы 62
І лава 3. Использование структурною ірафа для оптимизации и
распараллеливания программ 63
3.1.1 Іромежуючное представление проіраммьі 63
-
Структура промежуточною предсіавления 64
-
Элементарные преобразования 69
3.2. Построение информационных структур 69
3.2.1 Управляющий граф 70
3.2 2.1 раф зависимости по данным 74
3 2 3 Граф вызовов процедур 78
3 3. Преобразования программ 79
3 3 1. Проіяі ивание констант 79
3 3 2 Удаление "мертвого" кода 80
3 3.3. Удаление недости/ісимоїо кода 83
3 3 4. Упрощение арифмеїических выражений 84
3 3 5. Канонизация цикла 86
3.3 6 Разрезание цикла. 87
3.3.7 Слияние циклов . 89
3 3.8 Развертка цикла 91
3 4 Результат и выводы 93
Глава 4 Структурно-предикативная система построения внутреннего
представления проірамм 94
4.1. Возможности сисіемьі 94
4.2 Структура сиеіемьі 94
-
Рабоїасо сіруктурно-нредикаїивной сисіемой 97
-
Сопоставление с друї ими системами 99
-
Выводы 100
Заключение 101
Литература 103
Приложение А. Описание подмножесів языков Си, Фортран и Паскаль.... 112
Элементы языка Си 112
Элементы языка Паскаль 112
Элемеьпы яшка Фортран 113
Приложение В. Реализация алгоритмов на Прологе 115
Введение к работе
Актуальность темы. Развитие вычисли іельньїх сисіем, появление новых аипараіньїх платформ и процессоров обуславливай^ необходимость разработки новых компиляторов Разработка эффекшвного компилятора - это ірудоемкий и досіаіочно длительный процесс.
Одним из ответе і венных этапов разработки компиляюра являемся проектирование внутреннею представления программ для исходного языка. От внуїреннего предсіавления будут зависеть важные свойства компиляюра, такие как переносимость на друї ие платформы, модифицируемость, скорость работы, качесіво кода и т д.
Сущееівуеі ботьшое количество моделей для представления программ, как чисю іеоретических, іак и широко применяемых на пракіике: постфиксная ноіация; грехадресный код; синтаксическое дерево, другие граф-модели
Внуїренние представления в современных компиляторах, как правило, реализуются в виде таких струкіур, как списки и деревья. В некоторых системах оптимизации и распаратлеливаиия нроірамм, таких как Polaris [9J, SUIF/SUIF2 [47], ОРС [96], внутреннее представление программ реализовано в виде иерархии классов на объектно-ориентированном языке. Основное преимущество представления в таком виде - ло просюта проектирования, модифицируемоеіь и расширяемость.
За преобразование исходной программы во внутреннее представление отвечаеі анализирующая часть компиляюра или парсер Разрабоїка парсера с нуля является очень трудоемкой задачей и может занять мною времени. Поэтому, чтобы ускорить и облегчить процесс ею разработки, как правило, используются специальные инсіруменіьі, так называемые іенераторьі компиляторов (Lex/YACC [52], Пех/Bison [9]). Но даже при использовании гене- раюров компиляторов за разрабоїчиком парсера осіается решение основной задачи - описание сишаксиса и семаніики исходною языка с помощью некоторого формализма.
Сегодня для решения этой задачи чаще всего используются аїрибутньїе грамматики [73], которые позвочяют описьіваїь синіаксис и семантику языка блаїодаря наличию аїрибутов, связанных с каждым ірамматическим символом, и семантических правил, вычисляющих эти атрибут. В атрибутной грамматике обязаіельно должен бьпь задан правильный порядок выполнения семаніических правил, связанных с узлами дерева разбора. Установление эюю порядка являеіся неіривиальной задачей, решение коюрой требуеі оі программист дополнительных временных заіраї и оівлекаетої реіиения основной задачи. Кроме того, при использовании аїрибутной граммаїики построение внутреннего представления программы, отличною от дерева разбора, нужно описывать в процедурном виде.
В 1980 году Ф. Перейрой и Д. Уорреном были описаны ірамматики DCG [35] (Definite Clause Grammars), о і носящиеся к классу логических грамматик Сейчас эш грамматики неизменно включаются во все развитые системы программирования на языке Пролої Оіи ірамматики в оіличие от атрибужых грамматик, не требуюі задания строгого порядка выполнения семантических правил Однако построение семашической структуры программы с помощью DCG, как и в атрибушых ірамматиках, нужно описывать в процедурном виде (на языке Пролог)
В 2003 году С II. Крицкий описал струкіурньїе предикативные ірамматики [76] (СП-грамматики), основанные на понятии структурною ірафа программы и расширяющие DCG процедурой унификации вершин структурного графа и термов Эти грамматики обладаю і всеми возможностями DCG и при этом позволяют описывать построение семантической сірукіурьі программы и работу с ней в непроцедурном виде Однако эти грамматики не нашли широкого применения из-за отсутствия и\ реаіизации, разрабоїка которой предсіавляется акіуаіьной задачей развития сисіем посіроения компиляторов.
Цель рабо і ы и задачи исследования. Целью данной диссертационной работы является реализация струкіурньїх предикаїивньїх грамматик и их использование для построения внутреннею представления программ, ориентированною на их ошимизацию и распараллеливание.
Для достижения иосіавленной цели решаются следующие задачи:
Создание программной реализации СП-ірамматик, представления структурною графа и алгоритма унификации вершин структурного графа и термов.
Применение СП-грамма і икдтя определения и посіроения внуїреннего представления программ, написанных на процедурных языках, в виде структурною ірафа.
Реализация с помощью среде і в работы со сірукгурньїм ірафом алгоритмов построения информационных сіруктур, используемых при оп-іимизации и распаралтеливании, а также набора ошимизирующих и распараллеливающих преобразований.
Разработка экспериментальной струкіурно-предикативной системы для построения внутреннего предеіавления проірамм, ориешированного на их оптимизацию и распаратлеливание.
Методы исследований. В диссертационной рабоїе использовались методы іеории трансляции и преобразовании ироірамм, элемешы іеории графов При реализации программною обеспечения использовались принципы логического программирования
Достоверность и обоснованность резулыаюв. Полученные результаты прошли проверку в ходе практического использования разработанного программного комплекса для проведения многочисленных экспериментов с исходными текстами тестовых и реальных проірамм.
Научная новизна. Иредюжены методы и алюри і мы автоматического построения структурного ірафа и преобразования правил СІ l-ірамматики в правила Пролога. Предчожен способ использования унификации вершин структурною графа и термов для построения, анализа и преобразования внуїреннего предеіавтения программ
Практическая ценность. В чоде исследовательской работы была разработана жсперименіальная сисіема дня пос і роения внуїреннего представления программ, которое ориентировано на их ошимизацию и распараллеливание. Эта система может быть использована для обучения, исследований и экспериментов в области преобразований программ.
Проіраммно реатизованные СІІ-ірамматики моїут бьпь использованы в качестве инструмент при разработке ошимизирующих и распараллеливающих компиляторов.
Апробация результант работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции "Научный сервис в сети Иніернет: технолоіии параллельного программирования", г Новороссийск, 2006 г., на научно-методической конференции "Современные информационные іехнологии в образовании: Южный федеральный окруї", і Ростов-на-Дону, 2006г., на научных семинарах кафедр ИВЭ и АДМ мехмаїа РГУ, на научно-исследоваїельском семинаре ЮГИНФО РГ У, 2006 г.
Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавюрстве Из них 3 статьи в российском рецензируемом журнале, 1 стаїья в сборнике трудов аспиранюв РГУ и 2 в іезисах докладов всероссийской и реї иональной конференций.
В совместных работах [77, 78] личный вклад авюра заключается в исследованиях и разработках, связанных с реализацией сіруктурньїх предикативных грамматик, представления струкіурноіо графа, алюригма унификации и экспериментальной сисчемы
Объем и содержание работы. Диссеріация состоит из введения, четырех глав, заключения, списка лиіераіурьі и приложений.
Во введении обоснована актуальность проводимых исследований, сформулирована цель диссертационной работы, показана новизна и практическая значимость резулыатов, указаны положения, выносимые ил защиту, и краї ко аннотировано содержание глав
Первая і „шва посвящена обзору современного состояния исследований в области оптимизации и расиарач іеливания ироірамм. Рассмаїривают-ся 3 основных подхода к распараллеливанию программ: «ручное», автоматическое и полуавтомаїическое распараллеливание. Приводится обзор различных технолоіий параллельною программирования. Рассмаїриваются расширения ірадициоиньїх последовательных языков, коммуникационные библиотеки и ишерфейсы параллельного проіраммирования, специализированные параллельные библиотеки, среде і ва автоматическою распараллеливания программ и средства создания и проекіирования параллельных программ. Приводится обзор и анализ различных вариантов внуїреннего представления программ.
Вторая їлава диссертации посвящена подробному описанию формализма СП-граммаїик, их использованию для посіроения семантической структуры программы, а іак же реализации эшх ірамматик. Приводятся определения атрибутом грамматики, іраммаїики DCG, с і рук і урной предикативной грамматики и струкіурною графа, описьнзаеіся алгориш унификации вершин структурною графа и термов І Іроизводится сравнение описания семантической сіруктурьі программ с помощью атрибутых и СП-грамма-гик, коюрое показывает преимущество непроцедурною описания с помощью СП-грамматик Описывается проіраммная реализация СП-грамматик.
Третья глава посвящена использованию сірукіурного графа в качестве промежуточного предеывления программ, ориешированною на их оптимизацию и распараллеливание Описьіваеіся разработанное единообразное внутреннее представтение проірамм дія подмножеспз языков Си, Паскаль и Фортран Приводятся алюритмы построения информационных структур, часто используемых при ошимизации и распараллеливании программ: унравпяющего ірафа, графа зависимостей поданным и графа вызовов процедур. Описывается реализация известных преобразований программ, протягивание консташ, удаление «мертвого» кода, удаление недостижимого кода, упрощение выражений, канонизация цикла, разрезание цикла, слияние цикла и развертка цикла.
В четвертой і.іаве описывается разрабоїанная структурно-предикативная система - проіраммньїи комплекс, основанный на реализации СТІ-граммагик.
В заключении формулирую і ся основные результаты рабо і ы.
В приложении А приводиіся описание подмножеств языков Си, Паскаль и Фортран, для коюрых были разработаны СІ І-ірамматики.
В приложении В приводятся реализации описанных в рабоїе алгоритмов на языке Пролог.
