Помощь студентам в учебе
Методы высокоуровневой оптимизации циклов
|
1 Введение 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
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
Актуальность темы. С момента появления вычислительной техники и по сегодняшний день скорость выполнения программ была и остается важной темой исследований. Один из наиболее эффективных методов увеличения скорости работы программ — использование оптимизирующих компиляторов. Увеличение мощности современных компьютеров приводит не только к ускорению выполнения программ, но и к появлению новых возможностей, в том числе и для оптимизирующих компиляторов. Кроме того, изменение архитектуры процессоров приводит к необходимости создания новых и переработки уже имеющихся методов автоматической оптимизации.
На форуме 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).
Оптимизация по профилированию — это многофазная схема оптимизации программ, состоящая из инструментирования программы, пробного прогона на характерном наборе данных и последующего использования полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, находить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наиболее агрессивные оптимизации.
Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы ([20], [13, §10.2]), и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.
Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, Steven Muchnick, позднее написал книгу [41], которая по праву считается одной из фундаментальных работ по компиляторам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается — за последние годы в нем появились такие важные трансформации, как программная конвейеризация и автоматическая параллелизация, а также многие другие.
Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([13, §10.2], [41, §14.1.2], [17, §6.2.3]) и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах.
Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках данной диссертационной работы, интересен как минимум по двум причинам.
На форуме 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).
Оптимизация по профилированию — это многофазная схема оптимизации программ, состоящая из инструментирования программы, пробного прогона на характерном наборе данных и последующего использования полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, находить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наиболее агрессивные оптимизации.
Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы ([20], [13, §10.2]), и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.
Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, Steven Muchnick, позднее написал книгу [41], которая по праву считается одной из фундаментальных работ по компиляторам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается — за последние годы в нем появились такие важные трансформации, как программная конвейеризация и автоматическая параллелизация, а также многие другие.
Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([13, §10.2], [41, §14.1.2], [17, §6.2.3]) и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах.
Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках данной диссертационной работы, интересен как минимум по двум причинам.
1. Разработаны новые алгоритмы идентификации и символьного анализа индуктивных переменных и выражений, а также управляющей переменной. На основе данных алгоритмов разработаны алгоритмы оптимизации: подстановка индуктивных переменных и снижение стоимости индуктивных выражений.
Новые алгоритмы позволяют:
• обрабатывать индуктивные переменные с несколькими присваиваниями;
• учитывать взаимосвязь между различными индуктивными переменными;
• анализировать и оптимизировать операторы преобразования типов, примененные к индуктивным переменным и выражениям;
• трансформировать операторы деления индуктивного выражения на константу.
2. Проведен детальный анализ проблем, возникающих в программах на языках Си и Си+—+, и связанных с нестандартными способами описания управляю¬щей переменной. Предложен механизм решения этих проблем с применением специализации кода. Рассмотрены следующие случаи и их комбинации:
• использование управляющей переменной, имеющей беззнаковый целый тип;
• использование оператора != вместо оператора < в условии завершения цикла;
• использование оператора постинкремента в условии завершения цикла;
• использование глобальной переменной (или оператора считывания из памяти) в качестве верхней границы цикла.
3. Разработан метод быстрого профилирования конкретных значений выражений, учитывающий взаимозависимость значений нескольких различных выражений. На основе этого метода разработан механизм специализации кода по профилю значений.
4. Показано, что исследованные методы оптимизации, использующие специализацию циклов, являются “агрессивными”, т. е. в некоторых случаях могут ухудшить производительность. Однако, проведенные эксперименты доказали, что использование адекватных тренировочных данных при многофазной схеме компиляции обеспечивает отсутствие отрицательного результата.
5. Все исследованные методы анализа и оптимизации циклов реализованы в оптимизирующем компиляторе для платформы SPARC, что является важным практическим результатом работы.
6. Все предложенные методы оптимизации являются универсальными, т. е. не привязаны к конкретной архитектуре, конкретному компилятору или набору тестовых задач.
7. Реализованные оптимизации позволяют существенно повысить производительность реальных программ. На программах тестового набора SPEC CPU2000 был получен прирост производительности до 12%.
Разработка и исследование в области высокоуровневых оптимизаций циклов осуществлялась (и продолжает осуществляться) в рамках проекта оптимизатора промежуточного представления iropt (см. приложение), проводимого совместно фирмами ЗАО “МЦСТ” и Sun Microsystems с 1992 года. Автором были разработаны и реализованы все оптимизации, предложенные в главах 1, 2 и 3.
Новые алгоритмы позволяют:
• обрабатывать индуктивные переменные с несколькими присваиваниями;
• учитывать взаимосвязь между различными индуктивными переменными;
• анализировать и оптимизировать операторы преобразования типов, примененные к индуктивным переменным и выражениям;
• трансформировать операторы деления индуктивного выражения на константу.
2. Проведен детальный анализ проблем, возникающих в программах на языках Си и Си+—+, и связанных с нестандартными способами описания управляю¬щей переменной. Предложен механизм решения этих проблем с применением специализации кода. Рассмотрены следующие случаи и их комбинации:
• использование управляющей переменной, имеющей беззнаковый целый тип;
• использование оператора != вместо оператора < в условии завершения цикла;
• использование оператора постинкремента в условии завершения цикла;
• использование глобальной переменной (или оператора считывания из памяти) в качестве верхней границы цикла.
3. Разработан метод быстрого профилирования конкретных значений выражений, учитывающий взаимозависимость значений нескольких различных выражений. На основе этого метода разработан механизм специализации кода по профилю значений.
4. Показано, что исследованные методы оптимизации, использующие специализацию циклов, являются “агрессивными”, т. е. в некоторых случаях могут ухудшить производительность. Однако, проведенные эксперименты доказали, что использование адекватных тренировочных данных при многофазной схеме компиляции обеспечивает отсутствие отрицательного результата.
5. Все исследованные методы анализа и оптимизации циклов реализованы в оптимизирующем компиляторе для платформы SPARC, что является важным практическим результатом работы.
6. Все предложенные методы оптимизации являются универсальными, т. е. не привязаны к конкретной архитектуре, конкретному компилятору или набору тестовых задач.
7. Реализованные оптимизации позволяют существенно повысить производительность реальных программ. На программах тестового набора SPEC CPU2000 был получен прирост производительности до 12%.
Разработка и исследование в области высокоуровневых оптимизаций циклов осуществлялась (и продолжает осуществляться) в рамках проекта оптимизатора промежуточного представления iropt (см. приложение), проводимого совместно фирмами ЗАО “МЦСТ” и Sun Microsystems с 1992 года. Автором были разработаны и реализованы все оптимизации, предложенные в главах 1, 2 и 3.