Спекулятивные оптимизации программ для архитектур с явно выраженным параллелизмом команд

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

Оглавление
Введение .

Глава 1. Методы спекулятивного выполнения и оптимизации.

1.1. Используемая терминология.

1.1.1 Анализ потока управления и потока данных

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

1.2. Спекулятивное выполнение команд

1.2.1 Аппаратные механизмы поддержки спекулятивного выполнения.

1.2.2 Спекулятивное выполнение, контролируемое компилятором

1.2.3 Спекулятивное выполнение в I Ii.

1.3. Алгоритмы вероятностного анализа потока данных и управления

1.3.1 Анализ потока управления.
1.3.2 Алгоритмы анализа указателей.
1.3.3 Алгоритмы анализа зависимостей по данным между массивами.
1.3.4 Вероятностные алгоритмы анализа потока данных
1.4. Примеры статических спекулятивных оптимизаций
1.4.1 Существующие подходы к планированию команд.
1.4.2 Использование спекулятивных перемещений при планировании команд
1.4.3 Спекулятивное удаление частичной избыточности
1.4.4 Спекулятивное расширение представления с единственным
присваиванием .
Глава 2. Построение алгоритмов спекулятивных оптимизаций.
2.1. Преобразование консервативной оптимизации в спекулятивную
2.1.1 Понятие спекулятивной оптимизации
2.1.2 Схема выполнения спекулятивной оптимизации.
2.2. Пример построения спекулятивной оптимизации
2.3. Построение оптимизаций, выполняющих спекулятивные перемещения
2.3.1 Спекулятивные перемещения инструкций программы.
2.3.2 Вероятностные алгоритмы построения зависимостей по данным и по
управлению
2.3.2.1 .Зависимости по управлению
2.3.2.2.Зависимости по данным.
Использование профилирования
Эвристики
2.3.3 Построение легальных и выгодных спекулятивных преобразований
2.4. Построение кода восстановления
Глава 3. Реализация спекулятивного перемещения в планировании команд
3.1. Общее устройство компилятора вСС
3.1.1 Планировщик команд компилятора вСС
3.2. Реализация спекулятивного выполнения в планировщике команд компилятора
вСС .
3.2.1 Расширение и инициализация структур данных
3.2.2 Помещение спекулятивных инструкций в список планирования.
3.2.3 Использование оценок выгодности спекулятивных инструкций
3.2.4 Выдача спекулятивных инструкций.
3.2.5 Машиннозависимая поддержка спекулятивного выполнения.
3.2.6 Экспериментальные результаты
3.3. Селективное планирование команд.
3.3.1 Основные процедуры селективного планирования
3.3.2 Вычисление множества доступных инструкций.
3.3.3 Перемещение запланированной инструкции
3.4. Реализация спекулятивного выполнения в селективном планировщике команд
3.4.1 Анализ зависимостей для спекулятивного выполнения.
3.4.2 Выполнение спекулятивного преобразования
3.4.3 Описание спекулятивных команд для Ше Капшп.
3.4.4 Экспериментальные результаты
Заключение.
Список литературы


Разработанное спекулятивное планирование команд было одобрено сообществом разработчиков компилятора GCC для включения в основную ветвь разработки. Данная оптимизация является частью GCC е марта года и включена в официальный релиз компилятора, начиная с версии 4. Части разработанных механизмов поддержки спекулятивного выполнения используются при реализации нового алгоритма планирования команд для компилятора GCC в рамках проекта, выполняемого Институтом системного программирования РАН для компании Hewlett-Packard. Апробация работы. Научно-исследовательском семинаре по автоматизации программирования иод руководством проф. М.Р. Семинаре GREPS по исследованию компиляторных технологий с помощью пакета GCC в сентябре года. Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации составляет 3 страницы. Диссертация содержит 6 таблиц и рисунка. Список литературы насчитывает наименование. Краткое содержание работы. Диссертация состоит из введения, трех глав и заключения. В главе 1 приводится обзор работ, имеющих отношение к теме диссертации. В начале главы вводятся понятия и термины, используемые далее в тексте диссертации. Описываются механизмы полностью аппаратной поддержки спекулятивною выполнения в традиционных архитектурах с использованием буфера переупорядочивания и отложенных исключений. Рассматриваются теоретические модели спекулятивного выполнения команд, контролируемого компилятором, и необходимая для каждой модели поддержка аппаратуры. Приводится устройство спекулятивных команд в архитектуре Itanium. Вводится понятие вероятностного анализа, описываются алгоритмы вероятностного анализа потока данных и потока управления. Излагаются примеры статических алгоритмов спекулятивных оптимизаций - использование спекулятивных перемещений команд при планировании команд, спекулятивные оптимизации удаления частичной избыточности, а также спекулятивное расширение представления с единственным присваиванием (ЗЗА-представления). В главе 2 приводятся основные результаты диссертации. Приводятся формулировки понятия спекулятивной оптимизации, спекулятивного преобразования и перемещения команд, вероятностного анализа потока данных, приводятся примеры спекулятивных оптимизаций. Описывается схема построения оптимизации, выполняющей спекулятивные перемещения команд. Приводятся алгоритмы нахождения зависимостей по данным и по управлению, обосновывается сходимость алгоритма построения зависимостей по данным, использующего вероятности выполнения отдельных путей в графе потока управления. Приводится и обосновывается оценка выгоды отдельного спекулятивного перемещения по известным вероятностям зависимостей по данным и по управлению. Описываются алгоритмы построения кода восстановления для данного спекулятивного перемещения, в том числе обосновывается алгоритм построения кода восстановления минимальной стоимости. В главе 3 описывается разработанная для компилятора GCC инфраструктура, позволяющая реализовать спекулятивные перемещения команд. Кратко описывается внутреннее устройство компилятора GCC. Описывается реализация поддержки спекулятивного планирования команд в существующем планировщике GCC. Описывается реализация оценок выгоды спекулятивного перемещения. Приводятся и обсуждаются результаты экспериментов с планировщиком GCC на платформе Itanium 2 и наборе тестов SPEC CPU . Далее описывается алгоритм селективного планирования команд и конвейеризации циклов, дорабатываемый для компилятора GCC в Институте системного программирования РАН, Описываются реализация спекулятивных перемещений для этого алгоритма. Приводятся и обсуждаются результаты экспериментов с модифицированной конвейеризацией циклов, поддерживающей спекулятивное выполнение, на платформе Itanium 2. В заключении формулируются результаты диссертационной работы и приводятся направления дальнейших исследований. Планируется расширить инфраструктуру профилирования компилятора GCC для возможности профилирования путей в графе потока выполнения и зависимостей по данным, а также использовать ее для построения машинно-независимых спекулятивных оптимизаций в GCC.