Управление преобразованиями программ с переменным набором трансформаций

• Автор: Князева, Маргарита Александровна
• Шифр специальности: 05.13.01, 05.13.11
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Владивосток
• Количество страниц: 349 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. ПРЕОБРАЗОВАНИЯ ПРОГРАММ. ОБЗОР ЛИТЕРАТУРЫ

1.1. Основные понятия и постановка проблемы преобразований программ .

1.2. Современное состояние теоретических исследований в области преобразований программ

1.2.1. Модели программ, ориентированные на трансформации программ

1.2.2. Классификация трансформаций

1.3. Современное состояние разработки блоков оптимизации в компиляторах.

1.3.1. Представления программ.

1.3.2. Представление трансформаций в реализациях трансформационных машин.

1.3.3. Потоковый анализ программ

1.4. Средства автоматизации построения оптимизирующих компиляторов .
1.5. Компьютерные эксперименты в области преобразований программ.
1.6. Выводы к первой главе.
ГЛАВА 2. КОНЦЕПЦИЯ ПРЕОБРАЗОВАТЕЛЯ ПРОГРАММ С ПЕРЕМЕННЫМ НАБОРОМ ТРАНСФОРМАЦИЙ.
2.1. Требования к преобразователю программ с переменным набором трансформаций
2.2. Архитектура преобразователя программ с переменным набором трансформаций
2.3. Выводы ко второй главе и постановки задач исследования
ГЛАВА 3. ОНТОЛОГИЯ МОДЕЛИ ОБЪЕКТА ПРЕОБРАЗОВАНИЙ
3.1. Постановка задачи моделирования объекта преобразований
3.2. Онтология МСГ
3.2.1. Определение МСН
3.2.2. Вспомогательные термины
3.2.3. Классы фрагментов программы, идентификаторы программы
3.2.4. Тины данных
3.2.5. Дуги управления
3.2.6. Атрибуты.
3.3. Проекции языков программирования высокого уровня на единое представление программ и единого представления программ на языки высокого уровня
3.4. Онтология расширенной МСП.
3.4.1. Онтология расширенной МСН для классических оптимизирующих
преобразований.
3.4.2. Онтология расширенной МСП для реструктурирующих преобразований
3.4.3. Онтология расширенной МСП для коммуникационных преобразований
3.5. Онтологические соглашения онтологии МСП и онтологии расширенной МСП.
3.6. Выводы к третьей главе.
ГЛАВА 4. ПРЕДСТАВЛЕНИЕ МЕТОДОВ ПОТОКОВОГО АНАЛИЗА ПРОГРАММ .
4.1. Постановка задачи представления методов потокового анализа программ
4.2. Абстрактный синтаксис языка описания методов потокового анализа программ и его операционная семантика.
4.3. База знаний о методах потокового анализа программ
4.4. Выводы к четвертой главе.
ГЛАВА 5. ПРЕДСТАВЛЕНИЕ ТРАНСФОРМАЦИЙ.
5.1. Постановка задачи представления трансформаций
5.2. Абстрактный синтаксис языка описания трансформаций
5.3. База знаний о трансформациях программ
5.4. Выводы к пятой главе.
ГЛАВА 6. МЕТОДЫ ИНТЕРПРЕТАЦИИ БАЗЫ ЗНАНИЙ О ТРАНСФОРМАЦИЯХ ПРОГРАММ.
6.1. Постановка задачи интерпретации базы знаний о трансформациях программ
6.2. Метод интерпретации стратегии преобразования.
6.3. Метод поиска участка экономии
6.4. Метод выполнения преобразования
6.5. Выводы к шестой главе
ГЛАВА 7. СПЕЦИАЛИЗИРОВАННЫЙ БАНК ЗНАНИЙ О ПРЕОБРАЗОВАНИЯХ ПРОГРАММ.
7.1. Постановка задачи разработки средств преобразования программ с переменным набором трансформаций
7.2. Требования к СБкЗПП.
7.3. Архитектура СБкЗПП
7.4. Методы реализации СБкЗПП
7.5. Выводы к седьмой главе.
ГЛАВА 8. ТЕХНОЛОГИЯ ИСПОЛЬЗОВАНИЯ МЕТОДОВ И СРЕДСТВ ПРЕОБРАЗОВАНИЯ ПРОГРАММ С ПЕРЕМЕННЫМ НАБОРОМ ТРАНСФОРМАЦИЙ И ЕЕ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ
8.1. Технология использования методов и средств преобразования программ с переменным набором трансформаций.
8.2. Экспериментальное исследование технологии использования методов и средств преобразования программ с переменным набором трансформаций.
8.2.1. Постановка задачи экспериментального исследования переменных
наборов трансформаций на МСП
8.2.1.1. Модель измерения временных характеристик МСП.
8.2.1.2. Модель измерения характеристик объема МСП
8.2.2. Постановка задачи экспериментального исследования переменных
наборов трансформаций па штатном компиляторе
8.3. Использование технологии для экспериментального исследования переменных наборов трансформаций.
8.4. Использования технологии для моделирования блоков оптимизации в компиляторах.
8.5. Использование технологии для обучения студентов.
8.5.1. Организация лабораторного практикума.
8.5.2. Проведение деловых игр на лабораторном практикуме
8.6. Выводы к восьмой главе
ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
ГЛОССАРИЙ
СПИСОК ЛИТЕРАТУРЫ


Исторически первой теоретикографовой формой представления программ был управляющий граф программы . Развитие параллельных архитектур и различных подходов к распараллеливанию программ привело к формальному теоретикографововому определению зависимостей, данному Д. Ферранте, К. Оттенштейном и Д. Уорреном в работе 3. В процессе анализа потока данных происходит исполнение каждой программы в параллель над всеми значениями из некоторой символической и сильно упрощенной версии области ее реальных данных . При создании современных компиляторов, с большим количеством элементарных преобразований, возникают проблемы их структурирования и организации их взаимодействия. Очень важно чтобы процесс компиляции укладывался в допустимое время. Разрабатывая конкурентноспособный оптимизирующий компилятор, необходимо предусмотреть и возможность его развития. В работе рассматривается способ организации преобразований в виде управляемых пакетов оптимизаций, позволяющий эффективно решать вышеперечисленные проблемы. Дается общий подход к решению проблемы организации оптимизаций, не зависящий от их внутренней структуры и приводятся примеры конкретных реализаций управляемых пакетов оптимизаций в рамках промышленного компилятора, разработанного для архитектуры Эльбрус 0 9. Комбинирование различных методов анализа потока данных и оптимизаций рассматривается в работе 2. В настоящее разрабатываются системы, ориентированные на построение блоков оптимизации для конкретных внутренних представлений. Система и iix являются генераторами блоков оптимизации. Разрабатываются подходы к оптимизации кода, в которых используется схема динамической профилировки, позволяющая обойти недостатки однократной профилировки на машине разработчика. Примером такой системы является система V 2. Система V разрабатывалась для поддержки нескольких языков высокого уровня. Каждый компилятор с языка высокого уровня преобразует его в набор инструкций V и может содержать специфичные для языка оптимизации инструкции. Набор инструкций V представляет некоторую виртуальную архитектуру, содержащую ключевые операции современных процессоров, но не содержит машиннозависимых ограничений, таких как регистры или конвейеры. V предоставляет бесконечное число регистров, которые могут использоваться для сохранения значений примитивных типов. Большинство операций V представлено в трехадресном формате. Инструкции V являются полиморфными одна инструкция может оперировать различными типами аргументов. Это существенно уменьшает количество операций. V использует как основную форму представления кода. Программа находится в форме , если значение каждой переменной присваивается только один раз. Форма упрощает большинство оптимизаций потока данных, поскольку только одно присваивание может предшествовать использованию переменной и нахождение этого присваивания является тривиальной задачей. Каждая функция, возвращающая значение, создает новый регистр, содержащий это значение. Оптимизатор на стадии линковки оперирует над кодом V. Здесь проводятся все основные оптимизации. Использование типизированной информации и , полученной во время компиляции в V, облегчает выполнение многих оптимизаций. Оптимизатор содержит все основные скалярные и межпроцедурные оптимизации. Одним из ключевых моментов при разработке V являлась разработка новой стратегии для выполнения оптимизаций во время выполнения. Стратегия построена вокруг сбора информации во время выполнения для последующей перекомпиляции и оптимизации байткода V. Многие современные компиляторы разрабатываются по технологии , преследующей следующие цели разбить компилятор на законченные блоки предоставить разработчику возможность использовать внешние модули анализаторы, оптимизаторы, генераторы предоставить возможность работы с большим количеством целевых платформ добиться значительного увеличения жизненного цикла компилятора и отдельных его блоков. Примером компилятора, построенного по этой технологии, является промышленный компилятор 4. Современные компиляторы поддерживают большое количество платформ , I х, , ii, I, I , РАI, , I I, x.