Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание

• Автор: Тапкинов, Батр Юрьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ростов-на-Дону
• Количество страниц: 120 с.

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

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

1.1 1. Ручное распараллеливание

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

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

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

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

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

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

1 2.4. Среде 1ва создания и проектирования параллельных программ.
1 2 5 Специализированные параллельные библиотеки.
1.3 Различные вариант внуфеннего представления профамм.
1. Управляющий граф.
2 1 раф зависимости по данным.
1 3 3 Граф программных зависимостей
1 3 4 Граф вызовов процедур
1.3.5. Решетчатый граф
1 3.6 Граф вычислений программы
1 3 7 Иерархический граф заданий.
1.4 Выводы . . .
Глава 2 Сфукчурные предикативные грамматики и структурный граф.
2 1. Формализмы для описания семантики языков программирования и построения семантической арукчуры профамм .
2 1 1 Атрибутные грамматики .
2 1 2 ОСграмматики и ОСОнотация
2.1.3. С рук урные предикативные рамматики
2 2. Реализация структурных предикативных граммашк.
2.2.1.1 рсдеавение структурно о рафа
2.2.2. Реализация алюритма унификации вершин структурного графа и ермов.
2.2.3. Преобразование правил струкурнои предикативной грамматики правила Пролога
2.2 4. Среде на работы со струкурньм рафом.
2.3. Выводы
I лава 3. Использование структурно о рафа для оптимизации и
распараллеливания программ.
3.1.1 ромежу очное представление про раммы.
3.1.1. Структура промежуточною представления.
3.1.2. Элементарные гтреобра зования.
3.2. Построение информационных структур
3.2.1 Управляющий граф
3.2 2.1 раф зависимое ей по данным.
3 2 3 Граф вызовов процедур .
3 3. Преобразования программ.
3 3 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. Рабо а со сруктурнопредикаивной сисемой
4.4. Сопоставление с дру ими системами.
4.5. Выводы
Заключение.
Литература


Создание программной реализации СП-фамматик, представления структурною графа и алгоритма унификации вершин структурного графа и термов. Применение СП-грамматик для определения и построения внутреннего представления программ, написанных на процедурных языках, в виде структурною фафа. Реализация с помощью средеIв работы со структурным графом алго-ри(мов построения информационных сфуктур, используемых при оптимизации и распараллеливании, а также набора ошимизирующих и распараллеливающих преобразований. Разработка экспериментальной структурно-предикативной системы для построения внутреннего представления профлмм, ориентированного на их оптимизацию и распараллеливание. Методы исследований. Достоверность и обоснованность резулмаюв. Полученные результаты прошли проверку в ходе практического использования разработанного программного комплекса для проведения многочисленных зкенериментов с исходными текстами тестовых и реальных профлмм. Научная новизна. Пролога. Ир лктичсскаи ценность. В ходе исследовательской работы была разработана жеперимеиильная система для посмроения впуфеннего представления программ, которое ориентировано на их ошимитацию и распараллеливание. ЭIа система может быть использована для обучения, исследований и экспериментов в области преобразований программ. Профаммно реализованные СП-фамматики мо! Апробации результант работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции “Научный сервис в сети Ишернет: технолотии параллельного программирования”, г Новороссийск, г. Современные информационные технологии в образовании: Южный федеральный окрут”, I Ростов-на-Дону, г. ИВЭ и АДМ мехмат РГУ, на научно-исследовательском семинаре ЮГИНФО Р1 У, г. Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавюрстве Из них 3 статьи в российском рецензируемом журнале, 1 статя в сборнике трудов аспиратов РГУ и 2 в тезисах докладов всероссийской и ретионалыюй конференций. Объем и содержание работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Первая мака посвящена обзору современного состояния исследований в области оптимизации и распарам 1еливания профамм. Рассматриваются 3 основных подхода к распараллеливанию программ: «ручное», автоматическое и полуавтоматическое распараллеливание. Приводится обзор различных тсхноло1 ий параллельном программирования. Рассматриваются расширения традиционных последовательных языков, коммуникационные библиотеки и интерфейсы параллельного программирования, специализированные параллельные библиотеки, средства автоматическою распараллеливания программ и средства создания и проектирования параллельных программ. Приводится обзор и анализ различных вариантов внутреннего представления программ. Вторая 1лава диссертации посвящена подробному описанию формализма СП-граммашк, их использованию для построения семантической структуры программы, а так же реализации лих трамматик. Приводятся определения атрибутной грамматики, трамматики ОСС, структурной предикативной грамматики и структурною графа, описывается алгоритм унификации вершин структурною графа и термов Производится сравнение описания семантической структуры программ с помощью атрибутных и СП-грамма-гик, которое показывает преимущество непроцедурною описания с помощью СП-грамматик Описывается протраммная реализация С-грамматик. Описывается реализация известных преобразований программ, протягивание консташ, удаление «мертвого» кода, удаление недостижимого кода, упрощение выражений, канонизация цикла, разрезание цикла, слияние цикла и развертка цикла. В четвертой їлаве описывается разрабоїанная структурно-предикативная система - проіраммньїи комплекс, основанный на реализации СГ1-граммагик. В заключении формулирую і ся основные результаты рабо їм. В приложении А приводи і ся описание подмножеств языков Си, Паскаль и Фортран, для коюрых были разработаны СІ І-ірамматики. В приложении В приводятся реализации описанных в рабоїе алгоритмов на языке Пролог.