Введение
1. Двоичная трансляция и методы сокращения длины критического пути в графе зависимостей 12
1.1. Двоичная трансляция 12
1.2. Обзор основных особенностей epic архитектур 18
1.3. Обзор внутреннего представления в компиляторе
1.3.1. Внутреннее представление 21
1.3.2. Граф зависимостей 25
1.3.3. Особенности графа зависимостей в динамическом двоичном трансляторе 27
1.4. Ускорение результирующего кода за счёт сокращения длины критических путей 31
1.4.1. Ациклические области 31
1.4.1.1. Классические оптимизации с точки зрения сокращения длины критических путей 31
1.4.1.2. Специализированные преобразования для сокращении длины критических путей 34
1.4.2. Циклические области 35
1.4.2.1. Основные идеи конвейеризации циклов 36
1.4.2.2. Аппаратная поддержка конвейеризации циклов
1.5. Постановка задачи 38
1.6. Выводы 40
2. Сокращение длины критических путей в ациклических областях без построения новых операций 41
2.1. Методы разрыва зависимостей без построения новых операций 41
2.2. Обзор существующих методов минимизации высоты графа зависимостей
2.2.1. Переименование регистров 43
2.2.2. Использование частичных предикатов
2.3. Схема работы двоичного транслятора для архитектуры “эльбрус” 44
2.4. Минимизация высоты графа зависимостей без построения новых операций.
2.4.1. Переименование регистров 45
2.4.2. Спекулятивность по управлению 50
2.4.3. Частичные предикаты 51
2.4.4. Схема работы двоичного компилятора с учётом алгоритмов минимизации без построения новых операций
2.5. Экспериментальные результаты 61
2.6. Выводы 64
3. Сокращение длины критических путей в ациклических областях с построением новых операций 66
3.1. Методы разрыва зависимостей с помощью построения новых операций 66
3.2. Обзор существующих алгоритмов минимизации высоты графа зависимостей
3.2.1. Разрыв зависимостей и минимизация высоты графа зависимостей в суперблоках 75
3.2.2. Минимизация высоты графа зависимостей в процессе работы планировщика 76
3.2.3. Минимизация высоты графа зависимостей в гиперблоках 77
3.2.4. Минимизация высоты графа зависимостей с помощью решения задачи целочисленного линейного программирования 78
3.2.5. Проблемы и недостатки существующих методов минимизации высоты графа зависимостей 79
3.3. Общее описание алгоритма минимизации высоты графа зависимостей основанного на техниках разрыва с построением новых операций 83
3.3.1. Вводные замечания 83
3.3.2. Формализация задачи 85
3.3.3. Формальное описание алгоритма минимизации высоты графа зависимостей 86
3.3.4. Доказательство корректности алгоритма 91
3.3.5. Оптимальность алгоритма 91
3.3.6. Оценка сложности алгоритма
3.4. Избавление от излишней спекулятивности для операций чтения из памяти 96
3.5. Схема работы двоичного оптимизирующего транслятора с учётом алгоритмов минимизации высоты графа зависимостей 99
3.6. Экспериментальные результаты 100
3.7. Выводы 103
4. Сокращение длины критических путей в циклических областях 105
4.1. Обзор существующих алгоритмов конвейеризации циклов 105
4.1.1. Основные определения 105
4.1.2. Модульное планирование. 106
4.1.3. URCR, URPR, GURPR и GURPR 108
4.1.4. Enhanced Pipeline Scheduling 109
4.1.5. Другие алгоритмы конвейеризации 110
4.1.6. Проблемы и недостатки существующих методов конвейеризации циклов 111
4.2. РАСширенный граф зависимостей 112
4.2.1. Расширение графа зависимостей 112
4.3. Подсчёт минимального размера высоты цикла 114
4.3.1. Ограничения снизу на размер физической итерации цикла 114
4.3.2. Подсчёт ограничения по ресурсам 115
4.3.3. Подсчёт максимальной длины рекуррентности 116
4.4. Разметка времён раннего и позднего планирования на расширенном графе зависимостей 120
4.4.1. Времена раннего и позднего планирования на расширенном графе зависимостей 120
4.4.2. Алгоритм разметки времён планирования на расширенном графе зависимостей 121
4.4.3. Корректность и оптимальность алгоритма 126
4.5. Алгоритм конвейеризации циклов. 128
4.5.1. Описание алгоритма конвейеризации циклов 128
4.5.2. Разрыв зависимостей в процессе работы алгоритма конвейеризации циклов 130
4.5.3. Оценка сложности алгоритма конвейеризации
4.5.3.1. Оценка сложности алгоритма разметки времён планирования 131
4.5.3.2. Оценка сложности алгоритма конвейеризации циклов 135
4.6. Аппаратная поддержка обеспечения точного контекста при использовании вращающихся регистров 136
4.6.1. Обеспечение точного контекста 136
4.6.2. Взаимодействие схемы восстановления точного контекста с механизмом вращающихся регистров 137
4.7. Некоторые обобщения 139
4.7.1. Использование конвейеризации для циклов с несколькими обратными дугами 139
4.7.2. Использование конвейеризации для внешних циклов
4.8. Экспериментальные результаты 142
4.9. Выводы 144
Заключение. 145
Список литературы. 148
