Введение к работе
Актуальность темы. С момента появления вычислительной техники и по сегодняшний день скорость выполнения программ была и остается важной темой исследований. Один из наиболее эффективных методов ускорения работы программ — использование оптимизирующих компиляторов. Увеличение мощности современных компьютеров приводит не только к ускорению выполнения программ, но и к появлению новых возможностей, в том числе и для оптимизирующих компиляторов. Кроме того, изменение архитектуры процессоров определяет необходимость создания новых и переработки уже имеющихся методов автоматической оптимизации.
На форуме Intel для разработчиков (Intel Developer Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности. Среди них: а) программная конвейеризация (software pipelining), б) автопараллелизация (autoparallelization) и в) оптимизация по профилированию (profile guided optimization, PGO).
Программная конвейеризация — это такая трансформация циклов, которая позволяет наиболее эффективно использовать параллелизм уровня команд в большинстве современных микропроцессоров, в том числе, например, в Sun ULTRASparc IIICu или Intel Itanium.
Автопараллелизация — это семейство оптимизирующих трансформаций, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления (threads). Наиболее распространенное применение автопараллелизация — автоматическая параллелизация циклов. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур, в том числе и псевдо-мультипроцессорных (например, системы HyperThreading фирмы Intel).
Оптимизация по профилированию — это многофазная схема оптимизации программ, состоящая из инструментирования программы, пробного прогона на характерном наборе данных и последующего использова-
ния полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, находить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наиболее агрессивные оптимизации.
Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы, и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.
Цель диссертационного исследования — разработка новых и модификация имеющихся методов и алгоритмов оптимизации программ, связанных с программной конвейеризацией и автопараллелизацией, а также использующих профилирование. Исходя из поставленной цели, в диссертационной работе решаются следующие задачи:
разработка нового алгоритма снижения стоимости для индуктивных переменных, позволяющего в ряде случаев улучшить возможности последующей программной конвейеризации;
разработка нового алгоритма подстановки индуктивных переменных, увеличивающего возможности автопараллелизации;
анализ и частичное решение проблем, связанных с "нестандартными" управляющими переменными циклов в языках С и C++;
создание методов профилирования значений для последующей специализации кода.
Предмет исследования составляют различные аспекты разработки и реализации алгоритмов оптимизации программ:
эффективные алгоритмы идентификации, анализа и трансформации индуктивных переменных;
эффективные методы профилирования значений и выбора участков кода для специализации;
оценка конечной производительности оптимизированного кода.
Методы исследования заимствованы из областей системного программирования, технологии компиляции, символьной алгебры и теории графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени исполнения ряда тестовых программ, в первую очередь программ пакета SPEC CPU2000 (состоящего из двух частей: SPECint2000— 12 программ, использующих преимущественно целочисленную арифметику и SPECfp2000— 14 программ, активно использующих арифметику с плавающей точкой).
Научная новизна работы заключается в создании новых методов анализа и автоматической оптимизации программ, а именно:
в разработке методов идентификации и символьного анализа индуктивных переменных;
в описании и анализе различных разновидностей "нестандартных" управляющих переменных цикла и возможностей их трансформации;
в разработке быстрого метода профилирования значений с целью последующей оптимизации кода.
Практическая ценность работы. Разработанные алгоритмы были реализованы в рамках промышленного оптимизирующего компилятора фирмы Sun для платформы SPARC (поддерживает языки Си, Си++, Фортран 77, Фортран 90) и показали прирост производительности на ряде реальных программ. Большая часть разработанных алгоритмов имеет платформо- и языко-независимый характер, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.
Основные научные и практические результаты, выносимые на защиту
В диссертационной работе представлены следующие результаты:
1. Новые алгоритмы анализа и трансформации индуктивных пере
менных:
символьный анализ индуктивных переменных;
снижение стоимости индуктивных переменных и выражений;
подстановка индуктивных переменных.
Методы решения проблемы "нестандартных" управляющих переменных: применение специализации кода и интервального анализа для нормализации управляющих переменных.
Новые алгоритмы специализации кода, основанные на профилировании значений:
анализ возможных точек профилирования;
метод быстрого профилирования конкретных значений сразу нескольких переменных или выражений;
специализация кода по полученной статистике значений переменных и выражений.
Все разработанные алгоритмы реализованы автором в оптимизирующем компиляторе для платформы SPARC и успешно прошли этап опытной эксплуатации в фирме Sun и в ЗАО "МЦСТ", дав хорошие результаты и продемонстрировав высокую надежность методов. Часть алгоритмов включена в версию промышленного компилятора, поставляемую с мая 2003 года, другую часть планируется включить в следующую версию компилятора, готовящуюся к выпуску в середине 2005 года.
Апробация. Результаты работы докладывались на научных конференциях
Всероссийская научно-техническая конференция "Новые материалы и технологии", Москва 2002;
Научная конференция МФТИ, Москва-Долгопрудный 2002;
XXIX и XXX Международная молодежная научная конференция "Гагаринские чтения" (Москва 2003 и 2004);
а также на научных и технических семинарах ЗАО "МЦСТ" и ИМВС РАН и в электронном форуме по методам реализации компиляторов фирмы Sun.
Публикации. По теме диссертации опубликованы шесть работ.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и приложения. Диссертация содержит 91 страницу, в том числе 3 иллюстрации, 13 таблиц и 33 примера кода. Список литературы насчитывает 56 наименований.
