Компонентный подход к построению оптимизирующих компиляторов

В п. 4.5 рассмотрены алгоритмические основы глобального планирования и планирования цикловых регионов с использованием аппаратной поддержки для архитектур с явно выраженным параллелизмом. Разработана технология глобального планирования как для ациклических регионов программы, так и с учетом движения операций по обратным дугам циклов программы. Основными продвижениями в этой области следует признать многоуровневую пошаговую схему глобального планирования операций с возможностью отката и применения оптимизирующих преобразований на каждом шаге алгоритма.

Также следует отметить (п. 4.5.3) разработку методологии планирования цикла методом наложения итераций с использованием вращающихся регистров.

Эти методы позволили повысить на десятки (а в случае планирования циклов методом наложения итераций на сотни) процентов эффективность использования аппаратных ресурсов архитектуры «Эльбрус-3М» с явно выраженной параллельностью на уровне команд по сравнению с кодом, полученным без использования данных методов.

В главе 5 представлены продукты на основе блочной технологии построения оптимизирующих компиляторов, определена номенклатура блоков для каждого из продуктов, приведены данные об эффективности этих продуктов. Технологические и алгоритмические основы, предлагаемые в данной диссертации, были применены для создания трёх продуктов - анализатора программ, автоматического распараллеливателя и полномасштабного оптимизирующего компилятора.

Автоматический распараллеливатель (АР), представляемый в данной работе, реализован на базе двух технологий компиляции - технологической цепочки GCC и компонентной технологии оптимизирующей трансляции (КТОТ). Коллекция компиляторов GСС позволяет транслировать приложения со всех популярных языков программирования, таких как С, С++, Fortran, в код наиболее известных целевых платформ, таких как x86, Power Cell, Sparc и т.п. Компонентная технология оптимизирующей трансляции содержит в себе методы статического анализа программ, оптимизирующие преобразования и алгоритмы распараллеливания. Технология портирования, на базе которой реализована библиотека компонент, позволяет использовать все компоненты совместно с любой технологической компиляторной цепочкой, в том числе и с GCC.

Таким образом, используя технологию GCC для трансляции программ с языков высокого уровня в языки целевых архитектур, и технологию КТОТ для статического анализа программ, выявления параллельности и оптимизаций программ, был реализован АР.

Ключевым элементом АР является статический анализатор программ, реализованный на базе аналитических компонент КТОТ. Аналитическая часть библиотеки содержит реализацию современных алгоритмов потокового анализа, анализа данных, межпроцедурного анализа, анализа цикловых зависимостей и пр. Алгоритмы, реализованные в этой библиотеке, были опробованы в промышленных компиляторах и доказали свою высокую эффективность. В анализатор были включены следующие аналитические компоненты КТОТ:

Ш анализ потока данных методом нумераций значений

Ш анализ потока управления

Ш анализ переменных в цикле (распознавание инвариантов, индуктивностей, рекурентностей)

Ш анализ цикловых зависимостей

Ш анализ зависимостей на ациклических участках

Ш межпроцедурный анализ потока данных - чувствительный/нечувствительный к потоку управления/вызывающему контексту

Ш межпроцедурный распространитель (констант, выравниваний, диапазонов, указателей)

Ш межпроцедурный анализ методом нумерации значений

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

Для увеличения количества параллельных циклов и усиления эффекта от распараллеливания были использованы некоторые блоки оптимизаций: оптимизация по слиянию циклов (fusion), оптимизация по сведению индуктивных переменных к одной, технология дублирования циклов, переименование переменных, скаляризация для расширения аналитических возможностей распараллеливателя и другие.

Результаты экспериментов

В работе приведены результаты сравнения производительности базовых компиляторов для платформ x86, IA64 и PowerPC компаний Intel и IBM с производительностью для этих платформ, полученной с помощью АР. Замеры проводились для подмножества задач из пакетов Spec2006 и NAS Parallel Benchmarks

Ощутимый прирост производительности от применения АР зафиксирован как на задачах пакета Spec2006, так и на задачах NPB. В среднем, автоматический распараллеливатель (utlcc) дает больший прирост производительности по отношению к исходному уровню gcc, чем функциональность автоматического распараллеливания базовых компиляторов компаний Intel и IBM (reference) по отношению к их исходному уровню (без распараллеливания).

Ниже (рис. 11 и 12) приведены сравнительные характеристики АР (utlcc) и автоматического распараллеливания от базовых компиляторов компаний Intel и IBM (reference). Для получения сравниваемых значений время исполнения задачи, скомпилированной без распараллеливания, делится на время исполнения распараллеленной версии. Затем эти отношений усреднялись по каждому из пакетов (по 6 задачам из каждого). Результат выражается в процентах. В скобках указано количество ядер на аппаратных системах, для которых производилось сравнение (<архитектура> (х<количество ядер>)).

Spec2006

Рис. 11 Интегральные результаты по производительности (Spec2006)

NAS Parallel Benchmarks

Рис. 12 Интегральные результаты по производительности (NAS)

Как видно из приведенных на рис.11 и рис.12 диаграмм, авто-распараллеливатель, созданный на основе компонентного подхода, распараллеливает более эффективно, чем авто-распараллеливатели базовых компиляторов компаний Intel и IBM.

Компилятор общего назначения для архитектуры «Эльбрус-3М» позволил вычислительному комплексу, построенному на базе этой архитектуры, реализовать заложенный в него потенциал и достичь требований производительности, которые поставил перед разработчиками заказчик и которые были подтверждены государственными испытаниями вычислительного комплекса «Эльбрус-3М» в 2007 году.

В Заключении диссертации приводятся основные результаты диссертационной работы. Делаются выводы об эффективности разработанных технологий и алгоритмов. Указываются пути дальнейшего развития технологий оптимизирующей компиляции.

Выводы по результатам диссертации

В представленной диссертационной работе рассматриваются алгоритмические и технологические основы построения оптимизирующих компиляторов для современных архитектур. В работе показано, что методы анализа и оптимизации имеют решающее значение для получения высокопроизводительного кода для современных архитектур, включая архитектуры с явной параллельностью на уровне команд и многоядерные архитектуры. В данной работе исследованы проблемы, связанные с решением задач построения оптимизирующих компиляторов. Особое внимание было уделено созданию блочной технологии построения оптимизирующих компиляторов, развитию методов анализа программ, развитию методов планирования программ и развитию методов построения готовых продуктов.

В процессе исследований и в ходе решения поставленных задач автором были получены следующие результаты, выносимые на защиту:

1. Разработаны или существенно улучшены алгоритмические основы компонент оптимизирующих компиляторов:

1.1. Статический анализ программ

§ Предложен алгоритм группового (для множества переменных) построения формы статического единственного присваивания, позволяющий существенно ускорить построение формы единственного статического присваивания.

§ Предложена новая структура данных (дерево значений), позволяющая объединить в единое целое информацию о потоке данных и доминировании, и показано, как на ее основе применяется широкий класс преобразований потока данных.

§ Предложен оригинальный алгоритм перевода программы в предикатную форму, основанный на использовании предикатной формы статического единственного присваивания. Это позволило существенно уменьшить накладные расходы при проведении этого преобразования.

§ Предложен алгоритм, расширяющий применимость анализа предикатов для программ, в который поток управления переведен в поток данных с использованием предикатных операций. Этот метод позволяет включить в рассмотрение поток данных, входящих в регион через -узлы.

§ Показано, как на основе расширенного анализа предикатов можно улучшить эффективность многих преобразований на предикатном коде, и предложены новые преобразования, основанные на использовании результатов такого анализа.

§ Предложен оригинальный интерфейс решателя систем диофантовых уравнений и неравенств, позволивший снять многие ограничения на применимость анализа зависимостей в циклах.

§ Введено понятие минимального вектора расстояния зависимости и предложен метод его вычисления.

§ Предложен механизм сохранения информации о длинах измерений многомерных массивов, позволяющий проводить анализ зависимостей в циклах после всех преобразований на графе управления практически без потерь в точности получаемых результатов.

§ Разработана реализация решателя систем диофантовых неравенств на основе симплекс-метода. Показано, что симплекс-метод имеет преимущество перед методом Фурье по скорости работы на задачах, работающих с многомерными массивами.

§ Предложен единый подход к решению задачи межпроцедурного анализа потока данных на основе механизма частичных трансферных функций, позволяющий существенно расширить область применения анализа с высокой степенью детализации результатов.

§ Показано, как с помощью предложенного подхода решаются задачи межпроцедурного распространения указателей, констант, выравниваний объектов, диапазонов значений переменных.

§ Предложен алгоритм решения задачи межпроцедурной нумерации значений.

1.2. Глобальное планирование программ

§ Разработан обобщенный алгоритм планирования ациклических и произвольных областей программы, интегрированный с преобразованиями потока данных и управления и с возможностью оценки эффективности каждого шага планирования;

§ Разработана методология возврата к предыдущему состоянию на каждом шаге планирования, позволяющая оценивать качество планирования и отменять результат планирования в случае, если текущий шаг планирования ухудшил ситуацию;

§ Разработан алгоритм планирования циклов методом наложения итераций с использованием аппаратных “вращающихся” регистров. В алгоритм заложена возможность точной оценки эффективности планирования цикла, которая позволяет оптимально принимать решение об использовании механизма аппаратных “вращающихся” регистров.

1.2. Разработаны методы группирования оптимизаций, позволяющие повысить эффективность применения оптимизаций при одновременном уменьшении времени компиляции.

2. Разработана методология блочного построения оптимизирующих компиляторов, позволяющая переиспользовать исходные коды в процессе разработки оптимизирующих компиляторов, что позволило уменьшить время разработки программ в области оптимизирующих компиляторов. Предложена необходимая для создания компилятора общего назначения номенклатура блоков оптимизирующей компиляции.

3. Разработана методология реализации блоков оптимизирующей компиляции с использованием объектно-ориентированного подхода к проектированию и реализации программ, которая также включает в себя параллельную реализацию работы блоков, что позволяет уменьшать время работы компилятора, за счет чего можно включать в него алгоритмически более сложные алгоритмы, что ведет к ускорению выполнения производимого компилятором кода.

4. Разработана методология портирования блоков оптимизирующей компиляции в состав любой существующей технологической цепочки. Это позволяет, использую блочную технологию, достраивать и улучшать любой оптимизирующий компилятор без необходимости его полного редизайна. Технология была успешно использована в процессе портирования автоматического распараллеливания в контекст GCC.

5. На примере автоматического распараллеливателя программ показана эффективность применения разработанных технологических и алгоритмических основ построения оптимизирующих компиляторов.

Все представленные в диссертационной работе алгоритмы и методы, реализованы в составе оптимизирующего компилятора с языков высокого уровня С, С++, F77 для архитектуры «Эльбрус-3М» и составляют основу оптимизирующей части этого компилятора. На основе предложенной блочной технологии построения оптимизирующих компиляторов были созданы анализатор программ и автоматический распараллеливатель программ для архитектур x86 (Intel, AMD), Itanium (Intel), Power PC, Power Cell. Автоматические распараллеливатели были построены на основе совместного использования компонентной технологии построения оптимизирующих компиляторов и технологии GCC.

Список работ, опубликованных по теме диссертации

1. Дроздов А.Ю. Компонентный подход к построению оптимизирующих компиляторов. // Программирование. 2009. № 5, с. 70-80.

2. Дроздов А.Ю., Особенности и перспективы Универсальной технологии оптимизирующей компиляции. // Сборник научных трудов ИТМиВТ им. С.А. Лебедева РАН, Выпуск №1, Материалы Всероссийской конференции «Перспективы развития высокопроизводительных архитектур. История, современность и будущее отечественного компьютеростроения», 2008, С. 62-74.

3. А.Ю. Дроздов, С.В. Новиков. Авто-распараллеливатель программ, реализованный на основе компонентной технологии построения оптимизирующих компиляторов. // Программирование. 2009. № 6, с. 1-24.

4. Дроздов А. Ю., Кирнасов А.Е. Анализ предикатных выражений и его использование в оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом // Информационные технологии, № 7, 2005 г., с. 40-45.

5. Дроздов А.Ю., Новиков С.В. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии, № 3, 2005 г.

6. Дроздов А.Ю, Владиславлев В.Е. Межпроцедурный анализ указателей // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 2-13.

7. Дроздов А. Ю., Сыркин А. Г. Методы контекстного межпроцедурного распространения свойств значений переменных программы // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 14-18.

8. Дроздов А. Ю., Тютюник О. М., Шилов В.В. Эффективная реализация графа потока зависимостей // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 19-23.

9. Дроздов А. Ю., Новиков С. В., Шилов В.В. Эффективный алгоритм преобразования потока управления в поток данных // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 23-31.

10. Дроздов А.Ю, Боханко А.С. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании // Информационные технологии, № 12, 2004 г.

11. Дроздов А. Ю., Корнев Р.М., Боханко А.С. Индексный анализ зависимостей по данным // Информационные технологии и вычислительные системы, № 3, 2004г., с. 27-37.

12. Дроздов А. Ю., Степаненков А. М. Управляемые пакеты оптимизаций // Информационные технологии и вычислительные системы, № 3, 2004г., с. 93-101.

13. Дроздов А. Ю., Степаненков А. М. Технология оптимизации циклов для архитектур с аппаратной поддержкой конвейеризации циклов // Информационные технологии и вычислительные системы, № 3, 2004г., с. 52-62.

14. Волконский В.Ю., Дроздов А.Ю., Ровинский Е.В. Метод использования мелкоформатных векторных операций в оптимизирующем компиляторе // Информационные технологии и вычислительные системы, № 3, 2004г.. с. 63-77.

15. Дроздов А. Ю., Кан А.В. Анализ межпроцедурная нумерация значений. // Компьютеры в учебном процессе, № 6, 2005 г.

16. Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б., Def-Use граф и методы его использования в современных оптимизирующих компиляторах. // Компьютеры в учебном процессе. № 12. 2005. C. 3-14.

17. Дроздов А.Ю., Новиков С.В. Исследование методов преобразования программы в предикатную форму для архитектур с явно выраженной параллельностью. // Компьютеры в учебном процессе, № 5, 2005 г.

18. Дроздов А.Ю., Перекатов В.И., Шлыков С.Л. Задача планирования операций по кластерам для архитектур с разделением исполнительных устройств на кластеры // Компьютеры в учебном процессе, № 3, 2005 г.

19. Дроздов А.Ю., Кирнасов А.Е., Перекатов В.И. Использование результатов анализа предикатных выражений для эффективного применения оптимизирующих преобразований программ // Компьютеры в учебном процессе, № 3, 2005 г.

20. Дроздов А.Ю., Степаненков А.М. Методы комбинирования алгоритмов анализа и оптимизаций в современных оптимизирующих компиляторах // Компьютеры в учебном процессе, № 11, 2004 г.

21. Дроздов А.Ю., Степаненков А.М. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10, 2004 г.

22. Дроздов А.Ю., Ровинский Е.В. Технология использования векторных операций для получения оптимального кода // Компьютеры в учебном процессе, № 9, 2004 г.

23. Боханко А.С., Дроздов А.Ю., Корнев Р.М. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004 г.

24. Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б., Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ. // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005.

25. Боханко А. С., Дроздов А. Ю., Новиков С. В., Шлыков С. Л., Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур. // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005.

26. Дроздов А.Ю., Новиков С.В. Улучшение алгоритмов построения формы статического единственного присваивания // IХ Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

27. Дроздов А.Ю., Владиславлев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IХ Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

28. Боханко А.С., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IХ Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

29. Боханко А.С., Дроздов А.Ю. Оптимизация «Расширенное удаление излишних операций чтения из памяти» // В трудах Международной молодежной научной конференции «XXX Гагаринские чтения», Москва, 2004.

30. Б. А. Бабаян А. К. Ким, Ю. Х. Сахин, А. Ю. Дроздов и др. ИМВС РАН Научно-технический отчет по НИР «Поисковые исследования и разработка архитектурных и логических принципов построения универсальных вычислительных систем «Эльбрус-4» с производительностью пентафлопового диапазона». Разработка принципов построения однокристального мультипроцессора. Глава 3: Исследование зависимостей по данным и управлению в алгоритмах задач. Москва 2003г.

31. Б. А. Бабаян, А. К. Ким, Ю. Х. Сахин, А. Ю. Дроздов и др. Российская академия наук. Институт микропроцессорных вычислительных систем (ИМВС). Отчет о научно-исследовательской работе. Программа фундаментальных научных исследований ОИТВС РАН "Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий". Направление № 2 "Высокопараллельная, масштабируемая кластерная архитектура, приспосабливаемая под конкретные приложения". Раздел 9: Особенности генерации кода для архитектур с разделением исполнительных устройств на кластеры. Москва 2003.

32. Дроздов А.Ю., Степаненков А.М. Методы глобального планирования программ, предлагаемые для использования в современных оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом. "Сборник тезисов XXI научно-технической конфренции войсковой части 03425" Москва, в/ч 03425, 2003г.

33. Дроздов А.Ю., Новиков С.В. Методы совместного планирования путей программы, предлагаемые для использования в современных оптимизирующих компилятора. "Сборник тезисов XXI научно-технической конфренции войсковой части 03425" Москва, в/ч 03425, 2003г.

34. Дроздов А.Ю. Методы анализа программ, предлагаемые для использования в современных оптимизирующих компиляторах. "Сборник тезисов XXI научно-технической конференции войсковой части 03425", Москва, в/ч 03425, 2003г.

35. A. Drozdov, I. Moukhin, A. Kasinsky, S. Okunev, A. Ostanevich, Y. Rumyantsev, A. Sushentsov, V. Tikhonov, V. Volkonski, K. Yaremenko. The optimizing compiler for the Elbrus-3 supercomputer // In Proceedings of the "International Congress on Computer Systems and Applied Mathematics (CSAM'93 )", Abstracts. St. Petersburg, July 19-23, 1993. P. 127-128.

36. В. Ю. Волконский, А. Ю. Дроздов, А. И. Касинский, И. А. Мухин, С. К. Окунев, А. Ю. Останевич, А. Л. Сушенцов и др. Оптимизирующая транслирующая система для МВК "Эльбрус-3" // В трудах международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях”, Тезисы. Алма-Ата, сентябрь 1991 г. С. 70.

Размещено на Allbest.ru