Помощь студентам в учебе
Оптимизация объектного кода для процессорных архитектур с поддержкой параллелизма на уровне команд
|
1. Введение 5
2. Обзор методов оптимизации кода для процессоров с поддержкой
параллелизма на уровне команд 9
2.1. ILP-платформы 10
2.2. Критерии оптимизации кода 16
2.3. Круг проблем, связанных с оптимизацией кода для ILP-
процессоров 17
2.4. Области планирования 20
2.5. Усиление параллелизма в пределах областей планирования ....26
2.5.1. Преобразования циклов 27
2.5.2. Встраивание функций 30
2.5.3. Снятие зависимостей по данным 30
2.5.4. Соотношение программного и аппаратного параллелизма.36
2.6. Планирование команд 37
2.6.1. Алгоритмы планирования 37
2.6.2. Координация планирования и распределения регистров 41
2.6.3. Глобальное планирование 43
2.6.4. Аппаратная поддержка глобального планирования 45
2.6.5. Метод доминантного параллелизма при планировании в
древовидных областях 50
2.6.6. Планирование по прогнозу значений данных 51
2.7. Особенности генерации кода для ЦПОС 53
2.8. О роли языковых расширений 57
2.9. Сводка методов оптимизации для процессоров с поддержкой
параллелизма на уровне команд 58
3. Компилятор с оптимизирующим постпроцессором - детальное
описание 59
3.1. Характеристика процессора 1В577 60
3.2. Общие сведения о компиляторе для 1В577 61
3.3. Роль базового компилятора 63
3.4. Постпроцессирование 66
3.4.1. Примеры оптимизаций, выполняемых постпроцессором.... 67
3.4.2. Основные понятия 69
3.4.3. Последовательность обработки входного ассемблерного
файла 70
3.4.4. Аппаратная совместимость 71
3.4.5. Модель линейного участка и постановка задачи
планирования 72
3.4.6. Алгоритм планирования 82
3.4.7. Учет аппаратных задержек 90
3.4.8. Сокращение перебора 92
3.4.9. Подбор вариантов команд 107
3.4.10. Модификация команд 108
3.5. Настройка постпроцессора на архитектуру 1В577 109
3.5.1. Регистры 110
3.5.2. Классы регистров 112
• 3.5.4. Ресурсы 116
3.5.5. Свойства команд 120
3.5.6. Варианты
3.5.7. Псевдокоманды (модификаторы)
3.5.8. Динамические ресурсы 131
3.5.9. Реализация аппаратных ограничений при помощи
псевдорегистров 134
4. Оценки эффективности 135
4.1. Сравнение с другими методами планирования 135
4.1.1. Списочное планирование 135
4.1.2. Методы планирования на основе ЦЛП 139
4.1.3. Метод планирования с использованием дизъюнктивных
графов 140
4.2. Измерение эффективности кода для процессора 1В577 140
4.2.1. Цели и методика измерений 140
4.2.2. Результаты измерений 142
4.2.3. Конвейеризация и развертка циклов 143
4.2.4. Замена адресации со смещением на адресацию с
постинкрементацией адресного регистра 146
4.2.5. Перестановки обращений к памяти 148
4.2.6. Оценка эффективности оптимизаций 151
4.2.7. Распределение регистров 152
5. Заключение 155
6. Литература 157
2. Обзор методов оптимизации кода для процессоров с поддержкой
параллелизма на уровне команд 9
2.1. ILP-платформы 10
2.2. Критерии оптимизации кода 16
2.3. Круг проблем, связанных с оптимизацией кода для ILP-
процессоров 17
2.4. Области планирования 20
2.5. Усиление параллелизма в пределах областей планирования ....26
2.5.1. Преобразования циклов 27
2.5.2. Встраивание функций 30
2.5.3. Снятие зависимостей по данным 30
2.5.4. Соотношение программного и аппаратного параллелизма.36
2.6. Планирование команд 37
2.6.1. Алгоритмы планирования 37
2.6.2. Координация планирования и распределения регистров 41
2.6.3. Глобальное планирование 43
2.6.4. Аппаратная поддержка глобального планирования 45
2.6.5. Метод доминантного параллелизма при планировании в
древовидных областях 50
2.6.6. Планирование по прогнозу значений данных 51
2.7. Особенности генерации кода для ЦПОС 53
2.8. О роли языковых расширений 57
2.9. Сводка методов оптимизации для процессоров с поддержкой
параллелизма на уровне команд 58
3. Компилятор с оптимизирующим постпроцессором - детальное
описание 59
3.1. Характеристика процессора 1В577 60
3.2. Общие сведения о компиляторе для 1В577 61
3.3. Роль базового компилятора 63
3.4. Постпроцессирование 66
3.4.1. Примеры оптимизаций, выполняемых постпроцессором.... 67
3.4.2. Основные понятия 69
3.4.3. Последовательность обработки входного ассемблерного
файла 70
3.4.4. Аппаратная совместимость 71
3.4.5. Модель линейного участка и постановка задачи
планирования 72
3.4.6. Алгоритм планирования 82
3.4.7. Учет аппаратных задержек 90
3.4.8. Сокращение перебора 92
3.4.9. Подбор вариантов команд 107
3.4.10. Модификация команд 108
3.5. Настройка постпроцессора на архитектуру 1В577 109
3.5.1. Регистры 110
3.5.2. Классы регистров 112
• 3.5.4. Ресурсы 116
3.5.5. Свойства команд 120
3.5.6. Варианты
3.5.7. Псевдокоманды (модификаторы)
3.5.8. Динамические ресурсы 131
3.5.9. Реализация аппаратных ограничений при помощи
псевдорегистров 134
4. Оценки эффективности 135
4.1. Сравнение с другими методами планирования 135
4.1.1. Списочное планирование 135
4.1.2. Методы планирования на основе ЦЛП 139
4.1.3. Метод планирования с использованием дизъюнктивных
графов 140
4.2. Измерение эффективности кода для процессора 1В577 140
4.2.1. Цели и методика измерений 140
4.2.2. Результаты измерений 142
4.2.3. Конвейеризация и развертка циклов 143
4.2.4. Замена адресации со смещением на адресацию с
постинкрементацией адресного регистра 146
4.2.5. Перестановки обращений к памяти 148
4.2.6. Оценка эффективности оптимизаций 151
4.2.7. Распределение регистров 152
5. Заключение 155
6. Литература 157
Актуальность темы.
Поддержка параллелизма на уровне команд в (микро)процессорных архитектурах - одно из основных направлений повышения быстродействия компьютеров. Такие микропроцессоры используются как в гражданских областях, так и при создании перспективных образцов вооружения и военной техники, в том числе для систем обработки информации в радиолокаторах и гидроакустических комплексах. Примером отечественного микропроцессора с поддержкой параллелизма на уровне команд является 1В577 и модели на его основе.
С аппаратной точки зрения наиболее перспективными в данном классе архитектур признаются процессоры с длинным командным словом. Их быстрое развитие ставит сложные задачи перед разработчиками инструментальных средств программирования. Некачественный компилятор способен нивелировать преимущества, предоставляемые высокопроизводительной аппаратурой. Укажем, что компания Hewlett- Packard, параллельно с созданием архитектуры IA-64, выделяет миллионы долларов на развитие инструментальных средств.
Трудность генерации эффективного кода для микропроцессорных архитектур с длинным командным словом проистекает в первую очередь из того, что традиционные компиляторы генерируют последовательный код, уступающий по качеству оптимальному в 5-10 раз, в то время как для достижения максимальной эффективности кода необходимо объединять в длинные командные слова элементарные операции, относящиеся к разным операторам исходного языка и разным итерациям циклов.
Цели диссертационной работы.
Основными целями диссертационной работы являются:
- исследование методов оптимизации объектного кода для микропроцессорных архитектур с параллелизмом на уровне команд;
- разработка и реализация постпроцессора, выполняющего оптимизацию объектного кода для процессоров с длинным командным словом;
- разработка и реализация средств настройки оптимизирующего постпроцессора на различные целевые архитектуры;
Научная новизна.
Предложен алгоритм планирования потока команд для процессоров с длинным командным словом путем перебора планов выполнения по методу динамического программирования. Наиболее актуальная область применения разработанного алгоритма планирования - генерация объектного кода для цифровых процессоров обработки сигналов с длинным командным словом.
Предложены новые средства описания процессорных архитектур с длинным командным словом, делающие возможным выделение архитектурно-независимого ядра оптимизирующего постпроцессора.
Практическая ценность.
Публикации.
По теме диссертации опубликовано 5 печатных работ - [4], [5], [6], [7], [19].
Объем и структура работы.
Диссертация состоит из 4 глав, заключения и списка литературы.
Первая глава является введением.
Вторая глава представляет собой обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд. Особое внимание уделяется методам усиления программного параллелизма на уровне команд, а также методам планирования потока команд.
В третьей главе подробно рассматривается реализация компилятора для процессора 1В577 с оптимизирующим постпроцессором. В ней описана структура компилятора, рассмотрены оптимизации, реализованные в постпроцессоре, в частности, алгоритм планирования потока команд перебором планов выполнения по методу динамического программирования. Здесь же описаны средства настройки постпроцессора на целевую архитектуру и применение этих средств для настройки на архитектуру процессора 1В577.
В главе 4 дается сравнение реализованного алгоритма планирования с другими известными алгоритмами, а также приводятся результаты измерений эффективности кода, полученного с помощью постпроцессора. Полученный объектный код для различных тестовых задач сравнивается по времени выполнения с кодом, написанным вручную опытным программистом, а также с кодом других имеющихся компиляторов.
В заключении излагаются основные результаты диссертационной работы.
Поддержка параллелизма на уровне команд в (микро)процессорных архитектурах - одно из основных направлений повышения быстродействия компьютеров. Такие микропроцессоры используются как в гражданских областях, так и при создании перспективных образцов вооружения и военной техники, в том числе для систем обработки информации в радиолокаторах и гидроакустических комплексах. Примером отечественного микропроцессора с поддержкой параллелизма на уровне команд является 1В577 и модели на его основе.
С аппаратной точки зрения наиболее перспективными в данном классе архитектур признаются процессоры с длинным командным словом. Их быстрое развитие ставит сложные задачи перед разработчиками инструментальных средств программирования. Некачественный компилятор способен нивелировать преимущества, предоставляемые высокопроизводительной аппаратурой. Укажем, что компания Hewlett- Packard, параллельно с созданием архитектуры IA-64, выделяет миллионы долларов на развитие инструментальных средств.
Трудность генерации эффективного кода для микропроцессорных архитектур с длинным командным словом проистекает в первую очередь из того, что традиционные компиляторы генерируют последовательный код, уступающий по качеству оптимальному в 5-10 раз, в то время как для достижения максимальной эффективности кода необходимо объединять в длинные командные слова элементарные операции, относящиеся к разным операторам исходного языка и разным итерациям циклов.
Цели диссертационной работы.
Основными целями диссертационной работы являются:
- исследование методов оптимизации объектного кода для микропроцессорных архитектур с параллелизмом на уровне команд;
- разработка и реализация постпроцессора, выполняющего оптимизацию объектного кода для процессоров с длинным командным словом;
- разработка и реализация средств настройки оптимизирующего постпроцессора на различные целевые архитектуры;
Научная новизна.
Предложен алгоритм планирования потока команд для процессоров с длинным командным словом путем перебора планов выполнения по методу динамического программирования. Наиболее актуальная область применения разработанного алгоритма планирования - генерация объектного кода для цифровых процессоров обработки сигналов с длинным командным словом.
Предложены новые средства описания процессорных архитектур с длинным командным словом, делающие возможным выделение архитектурно-независимого ядра оптимизирующего постпроцессора.
Практическая ценность.
Публикации.
По теме диссертации опубликовано 5 печатных работ - [4], [5], [6], [7], [19].
Объем и структура работы.
Диссертация состоит из 4 глав, заключения и списка литературы.
Первая глава является введением.
Вторая глава представляет собой обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд. Особое внимание уделяется методам усиления программного параллелизма на уровне команд, а также методам планирования потока команд.
В третьей главе подробно рассматривается реализация компилятора для процессора 1В577 с оптимизирующим постпроцессором. В ней описана структура компилятора, рассмотрены оптимизации, реализованные в постпроцессоре, в частности, алгоритм планирования потока команд перебором планов выполнения по методу динамического программирования. Здесь же описаны средства настройки постпроцессора на целевую архитектуру и применение этих средств для настройки на архитектуру процессора 1В577.
В главе 4 дается сравнение реализованного алгоритма планирования с другими известными алгоритмами, а также приводятся результаты измерений эффективности кода, полученного с помощью постпроцессора. Полученный объектный код для различных тестовых задач сравнивается по времени выполнения с кодом, написанным вручную опытным программистом, а также с кодом других имеющихся компиляторов.
В заключении излагаются основные результаты диссертационной работы.
1. Проведен анализ существующих методов оптимизации объектного кода для процессорных архитектур с параллелизмом на уровне команд. Выделены основные классы таких методов.
2. Разработан алгоритм планирования потока команд для процессоров с длинным командным словом путем перебора планов выполнения по методу динамического программирования. В алгоритме предусмотрены оптимизации, направленные на сокращение перебора, которые позволяют обеспечить приемлемое время обработки входных программ.
3. Реализован постпроцессор, выполняющий планирование и другие оптимизации объектного кода. В постпроцессоре выделено универсальное, архитектурно-независимое ядро.
4. Разработаны и реализованы средства настройки оптимизирующего постпроцессора на различные целевые архитектуры. Выполнена настройка на отечественный микропроцессор 1В577.
5. Разработан оптимизирующий кросс-компилятор с языка Си для отечественных целевых ЭВМ на основе микропроцессора 1В577. Компилятор позволяет сочетать преимущества программирования на языке высокого уровня с качеством объектного кода, близким к ручному, что подтверждено полученными экспериментальными оценками.
процессорных архитектур с длинным командным словом.
2. Разработан алгоритм планирования потока команд для процессоров с длинным командным словом путем перебора планов выполнения по методу динамического программирования. В алгоритме предусмотрены оптимизации, направленные на сокращение перебора, которые позволяют обеспечить приемлемое время обработки входных программ.
3. Реализован постпроцессор, выполняющий планирование и другие оптимизации объектного кода. В постпроцессоре выделено универсальное, архитектурно-независимое ядро.
4. Разработаны и реализованы средства настройки оптимизирующего постпроцессора на различные целевые архитектуры. Выполнена настройка на отечественный микропроцессор 1В577.
5. Разработан оптимизирующий кросс-компилятор с языка Си для отечественных целевых ЭВМ на основе микропроцессора 1В577. Компилятор позволяет сочетать преимущества программирования на языке высокого уровня с качеством объектного кода, близким к ручному, что подтверждено полученными экспериментальными оценками.
процессорных архитектур с длинным командным словом.