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

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

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

Глава 1. Использование параллельности на уровне операций для

получения эффективного кода

1.1. Архитектурная поддержка параллельности на уровне операций

1.1.1. Широкое командное слово, статическое планирование операций

1.1.2. Предикатный и спекулятивный режим исполнения операций.

1.1.3. Аппаратные ресурсы архитектур с явно выраженной параллельностью.

1.1.4. Краткое описание архитектуры Эл ьбрусЗМ

1.2. Задачи оптимизирующего компилятора для архитектуры с явно

выраженной параллельностью.

1.2.1. Промежуточное представление программы и отображение параллельности.
1.2.2. Разбиение программы на участки и граф управления
ЛР 1.2.3. Методы анализа и оптимизирующие преобразования программы
1.2.4. Генерация кода из промежуточного представления
1.3. Постановка задачи.
1.4. Выводы
Глава 2. Предикатное промежуточное представление как
совокупность расширенных скалярных участков.
2.1. Переход к предикатному представлению ivi
2.1.1. Преобразование зависимостей по управлению к предикатным зависимостям, использование свойства спекулятивности для оптимизации предикатных зависимостей
2.1.2. Базовый регион предикатного промежуточного представления расширенный скалярный участок РСУ.
2.2. Алгоритм построения РСУ.
2.2.1. Построение полных условий относительно точки входа в РСУ
2.2.2. Применение базовых преобразований контекстных операций
на границах линейных участков.
2.2.3. Установление необходимых зависимостей по памяти, управляющих зависимостей и перевод операций с побочным
4Ц эффектом в предикатную форму.
2.2.4. Сложность алгоритма.
2.3. Оптимальное использование совместного спекулятивного исполнения операций из нескольких альтернатив условных предложений
2.3.1. Использование профиля программы, взаимодействие с построением гиперблоков.
2.3.2. Усложнение предикатного преобразования.
2.4. Результаты, полученные на тестовых пакетах 8РЕСЫ и
2.4.1. Наборы тестовых программ
2.4.2. Экспериментальные результаты
2.5. Выводы
Глава 3. Использование стратегии критического пути в
оптимизациях на основе предикатного представления программы.
3.1. Разметка операций временем раннего н позднего запуска и
критический путь участка.
3.2. Оптимизирующие преобразования для предикатного представления программы, направленные на сокращение критического пути участка.
3.2.1. Исключение условия с критического пути.
3.2.2. Удаление с критических путей потенциально зависимых последовательностей запись в память считывание из памяти
путем вставления динамического сравнения адресов
3.2.3. Балансировка критических путей РСУ, зависящих от условия.
3.3. Результаты, полученные на тестовых пакетах 8РЕСш2 и
вРЕСдп 5.
3.4. Вывод
Заключение.
Литература


В соответствии с этим определяются границы выделяемых в графе управления регионов, которые будут служить входными регионами для алгоритма построения предикатного представления программы, т. Алгоритм построения совокупности расширенных скалярных участков выполняется по двухпроходной схеме обхода каждого выделенного региона в графе управления процедуры. Этот алгоритм приведен в работе в обобщенном виде. Затем подробно обсуждаются его важнейшие составные части построение полных условий относительно точки входа в РСУ, оптимизирующие преобразования контекстных операций на границах линейных участков, а также перевод операций с побочным эффектом в предикатную форму и установление необходимых управляющих зависимостей. Для предикатного преобразования программы рассматриваются проблемы, связанные с оптимальным использованием совместного спекулятивного исполнения операций из нескольких альтернатив условных предложений избыточная спекулятивность. Описан подход, применяемый в инструментальном оптимизирующем компиляторе, для уменьшения избыточной спекулятивности. На основе этого интерфейса происходит учет профильной информации при предикатном преобразовании программы и делается предварительная оценка и балансировка различных путей управления в выделяемом первоначальном регионе графа управления. В конце главы приводятся экспериментальные данные по замерам производительности на целочисленных задачах из тестовых пакетов БРЕСШ и 5РСш. Дана методика проведения замеров на потактной модели архитектуры ЭльбрусЗМ. Приведенные результаты показывают эффективность перевода программы в предикатное представление и использование его для оптимизирующих преобразований. Основным результатом, представляемым в этой главе, следует считать то, что в инструментальном оптимизирующем компиляторе платформы ЭльбрусЗМ была создана необходимая инфраструктура в виде функционального компонента, позволяющая эффективно использовать в процессе компиляции и переводить в результирующий код аппаратные свойства, присущие архитектурам типа ЕРЮ. В Главе 3 представлены оптимизирующие методы для предикатного представления программы, использующие сокращение критического пути расширенного скалярного участка как основной критерий применения оптимизации. Это соответствует принятой в компиляторе стратегии оптимизации ациклических регионов программы с недостаточной степенью параллелизма в них. Критический путь РСУ определяется по разметке графа зависимостей рассматриваемого участка временами самого раннего и самого позднего начала запуска операции. В главе приведены определения этих времен, а также критического пути участка. Также даны алгоритмы разметки каждой операции участка данными временами. РСУ, зависящих от условия всталпение переходов для оптимизации критических путей, зависящих от предиката. Данные методы представляют пример направленных преобразований для конкретных типов зависимостей, определяющих критический путь участка. Они могут бьгть достаточно легко адаптированы для любой архитектурной платформы с явно выраженной параллельностью, поддерживающей предикатный и спекулятивный режим исполнения операций. Также для этих оптимизирующих преобразований проведено сравнение с подобными им методами для предикатного представления программы описанными в зарубежных статьях. Дана экспериментальная оценка применения рассмотренных оптимизирующих методов, а также оценка работы всей фазы оптимизации критических путей и работы фазы в комплексе с цикловыми оптимизирующими преобразованиями. Эти оценки проводятся на основании сравнения рассматриваемых вариантов оптимизации транслируемой программы с базовым уровнем оптимизации по времени исполнения в тактах на тех же тестовых задачах, которые были представлены в главе 2. В Заключении перечисляются основные результаты диссертационной работы. Делаются выводы об эффективности разработанных алгоритмов. Даются рекомендации по применению алгоритмов предикатного преобразования и алгоритмов фазы оптимизации критических путей в промышленном оптимизирующем компиляторе. В Приложении представлено обобщенное описание алгоритмов оптимизирующих методов сокращения критического пути, рассмотренных в главе 3.