Введение 3 1 Трансформации индуктивных переменных 13
1.1 Трансформации циклов 14
1.1.1 Автоматическая параллелизация 14
1.1.2 Распознавание циклов-идиом 15
1.1.3 Перестановка циклов 15
1.1.4 Снижение стоимости индуктивных выражений 16
1.1.5 Развертка циклов 17
1.2 Индуктивные переменные и выражения 18
1.2.1 Преобразование типов индуктивных переменных 21
1.2.2 Деление индуктивного выражения на константу 21
1.3 Символьное представление индуктивных выражений 22
1.3.1 С-функция 22
1.3.2 Каноническая форма С-функции 25
1.3.3 Линейные С-функции 27
1.4 Подстановка индуктивных переменных 27
1.4.1 Подстановка точек модификации 27
1.4.2 Вычисление количества итераций цикла 28
1.4.3 Подстановка индуктивных переменных 30
1.5 Снижение стоимости 30
1.6 Другие реализации алгоритмов 33
1.6.1 Идентификация индуктивных переменных 34
1.6.2 Снижение стоимости индуктивных выражений 34
1.6.3 Подстановка индуктивных переменных 35
1.7 Результаты 36
-1-

1.8 Выводы 38
2 Нормализация структуры управляющей переменной цикла 40
2.1 Использование беззнакового типа 44
2.2 Использование оператора != в условии цикла 46
2.3 Использование оператора постинкремента 49
2.4 Использование глобальной переменной в качестве верхней границы . 52
2.5 Порядок нормализации циклов 55
2.6 Ограничения применения специализации кода 57
2.7 Результаты 58
2.8 Выводы 61
3 Профилирование значений выражений для специализации кода 63
3.1 Специализация кода по конкретным значениям инвариантов 65
3.2 Профилирование значений выражений 68
3.2.1 Инструментирование программы 68
3.2.2 Использование результатов инструментирования 72
3.3 Результаты 73
3.4 Выводы 76
Заключение 78 Приложение. Внутренняя структура компилятора фирмы Sun 80 Список литературы 83 Список примеров 89 Список иллюстраций 91 Список таблиц 91
-2-


Купить

Актуальность темы. С момента появления вычислительной техники и по сегодняшний день скорость выполнения программ была и остается важной темой исследований. Один из наиболее эффективных методов увеличения скорости работы программ — использование оптимизирующих компиляторов. Увеличение мощности современных компьютеров приводит не только к ускорению выполнения программ, но и к появлению новых возможностей, в том числе и для оптимизирующих компиляторов. Кроме того, изменение архитектуры процессоров приводит к необходимости создания новых и переработки уже имеющихся методов автоматической оптимизации.
На форуме Intel для разработчиков (Intel Developer Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности при использовании компиляторов Intel [11]. Среди них:
1. программная конвейеризация (software pipelining) для архитектуры Itanium,
2. автопараллелизация (autoparallelization) и
3. оптимизация по профилированию (profile guided optimization, PGO).
Программная конвейеризация — это такая трансформация циклов, которая позволяет наиболее эффективно использовать параллелизм уровня команд в большинстве современных микропроцессоров, в том числе, например, в Sun ULTRASparc™ IIICu или Intel Itanium™.
Автопараллелизация — это семейство оптимизирующих трансформаций, позволяющих запускать последовательные независимые участки программы параллель¬но в нескольких потоках управления (threads). Наиболее распространенное применение автопараллелизации — автоматическая параллелизация циклов. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур, в том числе и псевдомультипроцессорных (например, системы HyperThreading фирмы Intel).
-3-

Оптимизация по профилированию — это многофазная схема оптимизации про¬грамм, состоящая из инструментирования программы, пробного прогона на характерном наборе данных и последующего использования полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, находить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наиболее агрессивные оптимизации.
Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы ([20], [13, §10.2]), и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.
Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, Steven Muchnick, позднее написал книгу [41], которая по праву считается одной из фундаментальных работ по компиляторам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается — за последние годы в нем появились такие важные трансформации, как программная конвейеризация и автоматическая параллелизация, а также многие другие.
Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([13, §10.2], [41, §14.1.2],
-4-

[17, §6.2.3]) и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах.
Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках данной диссертационной работы, интересен как минимум по двум причинам.
Во-первых, этот алгоритм разработан не только как теоретическое построение, но и внедрен в работающий компилятор с его заданной структурой представления программы, при этом за то же время выполняет существенно большее число трансформаций, чем предыдущий алгоритм, реализованный в компиляторе Sun.
Во-вторых, в основу данного алгоритма снижения стоимости положен такой механизм символьного анализа индуктивных переменных и индуктивных выражений, который применим для очень широкого класса оптимизаций и точного аналога которому автор не нашел в известной ему литературе.
После успешного внедрения в компилятор механизма символьного анализа индуктивных выражений было решено применить данный механизм для реализации еще одной оптимизирующей трансформации — подстановки индуктивных переменных. Данная оптимизация, необходимая в первую очередь для параллелизации циклов, достаточно изучена, однако ее прежняя реализация не позволяла охватить ряд важных случаев. Применение символьного анализа к индуктивным переменным позволило существенно расширить множество обрабатываемых случаев, сохранив прежнее время компиляции.
В процессе работы над алгоритмами трансформации индуктивных переменных и в ходе исследования результатов их работы было обнаружено большое количество таких циклов, которые нельзя было трансформировать из-за неправильной структуры управляющей переменной цикла. Зачастую неправильная структура управляющей переменной цикла являлась следствием применения некоторых конструкций языка Си (и Си+—+), например, использования глобальной переменной в качестве верхней границы цикла или оператора неравенства для проверки условия выхода из цикла. Вероятно, подобные проблемы хорошо известны многим разработчикам компиляторов, однако они очень мало освещены в литературе и не были практически решены в компиляторе Sun.
В диссертационной работе предлагается метод нормализации структуры цикла с использованием специализации кода, то есть при помощи дублирования цикла и вставки в код динамической проверки определенных условий. Реализация данного метода широко использует механизм символьного анализа индуктивных переменных, упомянутый выше.
Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. е. статистической информации, полученной в результате пробного запуска программы и позволяющей предсказать наиболее вероятные значения тех или иных переменных и выражений. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использования различной профильной информации (самыми распространенными типами такой информации следует назвать профиль переходов и профиль вызовов виртуальных функций). Однако профили значений выражений не нашли пока применения в большинстве компиляторов в силу крайне низкой скорости сбора статистики о значениях выражений. В большинстве работ по профилированию выражений упоминается замедление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод профилирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный “быстрый” метод позволяет собирать статистику несколько иного рода, чем ранее известные “медленные” методы. Это дает возможность не только собрать большую часть информации о значениях выражений, доступной при использовании других методов, но также получить информацию о взаимозависимости значений различных выражений.
Актуальность диссертационой работы обусловлена тем, что все исследованные методы оптимизации позволяют существенно повысить скорость выполнения про¬грамм.
-6-

Целью диссертационной работы является разработка новых и модификация имеющихся методов и алгоритмов оптимизации программ, связанных с программ¬ной конвейеризацией и автопараллелизацией, а также использующих профилирование. Исходя из поставленной цели, в диссертационной работе решаются следующие задачи:
• разработка нового алгоритма снижения стоимости для индуктивных переменных, позволяющего в ряде случаев улучшить возможности последующей программной конвейеризации;
• разработка нового алгоритма подстановки индуктивных переменных, увеличивающего возможности автопараллелизации;
• анализ и частичное решение проблем, связанных с “нестандартными” управляющими переменными циклов в языках С и C+—Н;
• создание методов профилирования значений для последующей специализации кода.
Предмет исследования составляют различные аспекты разработки и реализации алгоритмов оптимизации программ:
• разработка эффективных алгоритмов идентификации, анализа и трансформации индуктивных переменных;
• разработка эффективных методов профилирования значений и выбора участков кода для специализации;
• оценка конечной производительности оптимизированного кода.
Методы исследования заимствованы из областей системного программирования, технологии компиляции, символьной алгебры и теории графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени исполнения ряда тестовых программ, в первую очередь SPEC CPU2000, на двухпроцессорной рабочей станции SunBlade™ 1000.
-7-

Тестовый набор SPEC CPU2000 ([56]) — это международно признанный пакет тестов для оценки производительности вычислительных систем, состоящий из двух частей: набор программ, использующих преимущественно целочисленную арифметику (SPECint2000) и набор программ, использующих в основном арифметику с плавающей запятой (SPECfp2000). Пакет содержит в общей сложности 26 про¬грамм (12 в SPECint2000 и 14 в SPECfp2000), представляющих различные сферы применения языков программирования Си, СиН—Н, Фортран 77 и Фортран 90, таких как: архивация данных, компьютерная графика и распознавание образов, компиляция и интерпретация языков программирования, теория чисел, базы данных, искусственный интеллект (игра в шахматы), физика, химия, метеорология и др. Для каждой программы из тестового пакета имеется три набора входных данных: test — малый набор данных, используемый для проверки работоспособности теста, train — набор данных среднего размера, используемый для пробного запуска при многофазной схеме компиляции и ref — большой набор данных, используемый для измерения времени работы программы. Кроме пакета SPEC CPU2000, в процессе анализа и тестирования разработанных алгоритмов использовались тесты SPEC CPU95, bench++ и другие.

Купить