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

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

Содержание
ведение.

I. Анализ .методов планирования дли архитекту р с явной параллельностью.

1.1. Лнаан архитектур с явной параллельностью

1.2. Сгатичсское планирование операции

1.2.1. Зависимости по управлению и поданным

1.2.2. Контекст алгоритмов статического планирования

1.2.3. Место статического планирования в схеме оптимизирующей трансляции

1.3. Методы статического планировании.

1.3.1. Планирование но спискуКЗ.2. Планирование трассы

1.3.3. Суперблок и Гиперблок

1.3.4. Планирование по дереву доминирования
1.3.5. Конвейеризация циклов
1.3.6.1 ланироваиие с учетом задержек между линейными участками
1.3.7. Планирование техникой просачивания
1.3.8. Планирование волнового фронта
1.4. Проблемы и недостатки существующих .методов.
1.5. Постановка задачи.
1.6. Нмкоды.
2. Глобальное планирование в рамках ациклического региона
2.1. Общее описание алгоритма набора гниерблоков
2.1.1. Описание схемы отката
2.1.2. Оценка эффективности одного шага алгоритма
2.1.3. Алгоритм набора гниерблоков
2.1.4. Стратегии набора
2.1.5. Экспериментальные результат ы
2.2. Граф авнсимосте.
2.2.1. Алгоритм построения зависимостей
2.2.2. Коррекция зависимостей на каждом шаге алгоритма
2.2.3. Минимизация графа зависимостей
2.2.4. Результаты тестирования
2.3. Переход к предикатному представлению ivi.
2.3.1. Посзроснпе предикатов для архитектуры ЭдьбруеЗМ
2.3.2. Построение предикатов для архшектурм Ii
2.4. Непольшване спекулятивного режима
2.4.1. Спекулятивность но управлению без построения компенсирующего кола
2.4.2. Спекулятивное ь по управлению и поданным с построением
компенсирующем о кода 2.4.3. Использование спекулятивного режима на папе планировании
2.5. Оптимизации, включенные и схему планировании.
2.6. Коррекция аналитических структур данных
2.6.1. Коррекция рафа управления
2.6.2. Коррекция глобального графа потока данных
2.6.3. Коррекция информации о зависимостях по управлению
2.7. Экспериментальные результаты.
2.8. Выводы.
3. Глобальное планирование за пределами ациклических регионов
3.1. Общее описание алгоритма глобального планирования
3.2. Граф зависимостей
3.2.1. Алгоритм построения зависимостей
3.2.2. Коррекция зависимостей при переносе операций
3.2.3. Результаты тестирования
3.3. Информация о времени жизни объекчов
3.4. Построение предиката операции
3.5. Оптимизации, включенные в схему планирования.
3.6. Коррекция аналитических структур данных
3.6.1. Коррекция графа управления
3.6.2. Коррекция глобального графа потока данных
3.6.3. Коррекция информации о зависимостях по управлению
3.6.4. Коррекция результатов индексного анализа
3.7. Алгоритм глобального планирования
3.8. Экспериментальные результаты.
3.9. Выводы.
Заключение.
Список литературы


Компьютеры в учебном процессе. Хч 5. С. -. Дроздов Л. К). Новиков С. П., Шилов В. Информационные технологии. Хч 2. С. -. Дроздов Л. К). Новиков С. В. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии. Хч 3. С. -. Боханко A. C., Новиков С. В., Шлыков С. Л. I (екоторыс вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе. Хч 8. С. -. Новиков С. В. Развитие методов глобального планирования программ, используемых в современных оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом на уровне команд // Тезисы докладов Международной молодежной научной конференции «XXXI Гагаринские чтения». Т. 4. М.: МА ГИ. Дроиов АЛО. Новиков С. В. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция “Региональная Информагика-“. Тезисы докладов. СПб. СИНИ РАН, . Дроиов АЛО. Новиков С. В. Методы совместною планирования путей программы, предлагаемые для использования в современных оптимизирующих компиляторах // Сборник тезисов докладов XXI научно-технической конференции войсковой части 5. М.: в/ч 5, . Боханко А. С., Дроздов A. IO. Новиков С. В., Шлыков С. Л. Распределение регистров методом раскраски графа несовместимости для VLIW-apx«rreктур // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАИ. Выпуск N8,. С. -. Дроздов А. К). Новиков С. В., Боханко А. С., Галатии А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН. Выпуск N8, . С. -. Дроздов А. К). Новиков С. В., Боханко А. С., Галазнн А. Б. Dof-Use граф и методы его использования в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. Nfc . С. 3-. Диссертация состоит из введения, трех глав п заключения. Диссертация содержит 7 страниц. Список литературы пасшимиасг наименований. Глава 1 содержит краткое описание основных черт ЕРЮархитекгур. Глава 2 посвящена вопросам статического планирования ациклических областей программы. В мой главе предлагается алгоритм набора пшерблоков. Далее в этой главе рассматривается техника работы с зависимостями во время набора гиперблоков, рассмотрен механизм их коррекции. Затем описаны подходы к построению предикатов для операций во время планирования для двух актуальных ЕРЮ-архнгектур - Эльбрус-ЗМ и 1А-. Далее рассматриваются методы оптимизаций с использованием поддержки спекулятивного исполнения операций, а также интеграция оптимизирующих преобразований в алгоритм планирования. Также в этой главе рассмотрены методы коррекции аналитических структур данных во время ациклического планирования, таких как управляющий граф. В заключительной части этой главы приводятся результаты экспериментов, доказывающих эффективность п редложенн о го I г одхода. В Главе 3 рассматриваются вопросы глобального планирования произвольных областей программы. В начале дается общее описание алгоритма, и указываются новые черты, вносимые в планирование при данном подходе. Далее рассмотрен вопрос глобализации подходов к построению зависимостей и предикатов при переходе от ациклических областей процедуры к области всей процедуры. Затем рассматривается важный для глобального планирования вопрос сохранения информации о времени жизни объектов на этапе планирования. Рассмотрены методы коррекции этой информации и области ее использования. Так же, как и в случае ациклического планирования, в этой главе описаны предлагаемые оптимизации, интегрированные в алгоритм планирования, и рассмотрены методы коррекции аналитических структур данных во время планирования. Дано подробное описание алгоритма глобального планирования. Результаты экспериментов по замерам эффективности алгоритма циклового глобального планирования приведены в заключительной части этой главы. В Заключении приводятся основные результаты диссертационной работы.