Содержание к диссертации
Введение
1. Технология повышения производительности компиляторов 14
1.1 Тестовая база 15
1.2 Анализ производительности 16
1.2.1 Требования к поиску неоптимальностей и системе приоритетов 17
1.2.2 Причины неоптимальностей 17
1.2.3 Подходы к выявлению неоптимальностей 20
1.2.4 Структурная модель анализа 22
1.2.5 Классификация предложений и порядок поиска неоптимальностей 24
1.2.6 Анализ производительности на отдельной задаче 26
1.2.7 Оценки и предсказания 28
1.2.7.1 Оценка эффекта от реализации выработанных предложений 29
1.2.7.2 Предсказание пиковой производительности на задаче 30
1.2.8 Система приоритетов предложений 30
1.3 Контроль деградаций 31
1.3.1 Общая постановка задачи (модель) 32
1.3.2 Виды деградаций 33
1.3.3 Подходы к контролю деградаций 33
1.3.4 Частота замеров показателей производительности 34
1.4 Реализация технологии повышения производительности 36
1.4.1 Реализация процесса анализа производительности 38
1.4.2 Реализация процесса контроля деградаций 41
1.5 Результаты 44
1.6 Выводы 47
2 Система контроля деградаций 49
2.1 Метрические характеристики производительности 49
2.2 Метрики деградаций 51
2.3 Требования к выбору значений порога деградации 57
2.4 Методы оценки эффекта модификаций на производительность 57
2.4.1 Оперативная оценка общего времени выполнения 58
2.4.2 Альтернативные подходы к обеспечению оперативности методов оценки 62
2.4.2.1 Метод оценки по времени выполнения наиболее значимых фрагментов 62
2.4.2.2 Метод оценки по фактам применения оптимизаций 75
2.5 Реализация системы контроля деградаций 78
2.5.1 Основные положения методики контроля (проектные решения) 78
2.5.2 Стратегия контроля 79
2.5.3 Реализация методов оперативной оценки 80
2.5.4 Структура системы контроля деградаций 87
2.6 Результаты 89
2.7 Выводы 90
3 Исследования оптимизационных возможностей компиляторов .93
3.1 Требования к тестовому комплекту 94
3.2 Подходы к тестированию оптимизаций 97
3.3 Особенности реализации системы тестирования ОСТеТ 100
3.3.1 Специфика окружения 101
3.3.2 Метод тестирования и критерий полноты 101
3.3.3 Спецификация метода тестирования 105
3.3.4 Пример проектирования спецификации для оптимизации Loop
Fusion 107
3.3.5 Принципы построения тестов 109
3.3.6 Структура тестов 122
3.4 Результаты 125
3.5 Выводы 127
Заключение 129
Список литературы
- Требования к поиску неоптимальностей и системе приоритетов
- Анализ производительности на отдельной задаче
- Требования к выбору значений порога деградации
- Особенности реализации системы тестирования ОСТеТ
Введение к работе
Актуальность темы. При промышленной разработке систем информационных технологий к эффективности1 конечного продукта традиционно предъявляются высокие требования. Не исключением являются и компиляторы. Как отмечается в [RHD98], эффективность компиляторов имеет две составляющие. Одна из них характеризует этап компиляции и затрагивает такие его аспекты как, например, скорость компиляции и объем выделяемой в процессе компиляции динамической памяти. Другая же относится к качеству генерируемого компилятором кода и определяется временем его выполнения и/или его размером. Такое разделение выбрано неслучайно - время компиляции и затрачиваемая при этом память важны для разработчиков приложений, в то время как быстродействие и компактность кода представляют интерес с точки зрения их конечного пользователя.
Если говорить об эффективности периода компиляции, то требуемый уровень последней должен достигаться, в основном, за счет выбора соответствующих ограничений на сложность реализуемых в компиляторе алгоритмов и следования участниками процесса разработки установленным правилам производственной дисциплины. Что же касается вопросов эффективности целевого кода, то компилятор должен быть наделен достаточно мощными средствами оптимизации, позволяющими строить код с заданными характеристиками.
Для минимизации времени выполнения оттранслированного кода компилятор может применять к исходной программе целый ряд оптимизирующих преобразований, переводящих ее из одного эквивалентного состояния в другое с тем, чтобы в идеале получить для этой программы самый быстрый целевой код, который только возможен. Таким образом, чтобы добиться требуемого уровня быстродействия, разработчики компилятора должны постоянно работать над качеством его оптимизационных возможностей. Такого рода деятельность мы будем называть повышением производительности1 компилятора.
Повышение производительности должно осуществляться за счет расширения набора оптимизирующих преобразований, которые компилятор поддерживает, и устранения
1 Одно из определений понятия эффективности можно найти, например, в [ББКЛММ81]: программный продукт обладает свойством эффективности, если он выполняет требуемые функции без излишних затрат ресурсов, где ресурсы понимаются в широком смысле.
Здесь и далее производительность компилятора понимается с позиции быстродействия создаваемого им кода.
дефектов в реализованных ранее компонентах. Для эффективного развития компилятора в этом направлении наряду с деятельностью по устранению дефектов и реализации новых преобразований необходимо проведение комплекса мероприятий аналитического характера по выявлению неоптимальностеи в целевом коде транслируемых с использованием этого компилятора программ.
Кроме того, как показывает практика [RHD98], [БВГНТ04], при разработке компилятора приемлемого уровня быстродействия целевого кода можно добиться лишь в результате непрерывного контроля текущего состояния производительности. Действительно, любые модификации исходного кода компилятора, будь то исправление ошибок или расширение функциональности, являются потенциальными источниками деградации достигнутых показателей быстродействия.
Наконец, как для проведения анализа кода на предмет неэффективности, так и для осуществления контроля производительности, требуется некоторое представительное множество программ. Так что формирование этого множества является еще одной проблемой, которую необходимо решить для достижения желаемого результата.
Таким образом, для повышения производительности компилятора, помимо непосредственного внесения изменений в его код, чрезвычайно важной оказывается деятельность по поддержке этого процесса, под которой мы будем понимать совокупность мероприятий аналитического и технологического характера, направленных на выработку предложений по развитию компилятора и призванных обеспечить контроль этого развития.
Проблема разработки высокопроизводительных оптимизирующих компиляторов становится еще более актуальной в свете современных тенденций развития вычислительной техники. Традиционные суперскаляры, реализующие динамический подход к распараллеливанию вычислений, практически достигли предельного уровня аппаратной сложности и не могут масштабироваться до бесконечности для поддержания темпов роста производительности, к которым привыкло современное общество [LeVa03]. Одним из путей к преодолению данного ограничения является перенос основных интеллектуальных функций аппаратуры на уровень программного обеспечения. Этот подход лежит в основе так называемых архитектур с явно выраженным параллелизмом на уровне команд (Explicitly Parallel Instruction Computing, EPIC).
Производительность архитектур с явно выраженным параллелизмом (далее, для краткости, ЕРІС-архитектур) сильно зависит от возможностей компилятора
оптимальным образом распределять аппаратные ресурсы статически [ACMS98]. Учитывая тот факт, что величина значения тактовой частоты и параллелизм уровня команд являются антагонистичными свойствами [АНКВОО], коммерческий успех архитектуры в целом определяется качеством оптимизационных возможностей компилятора, что наглядно демонстрируется на примере архитектуры Itanium / Itanium 2. Действительно, на начальном этапе отсутствие приемлемого компилятора являлось серьезным сдерживающим фактором продвижения данной архитектуры на рынок.
Отличительной чертой компиляторов для ЕРІС-архитектур является их предельная сложность, что обусловлено потребностью в использовании по максимуму потенциала широкого командного слова и прочих предоставляемых архитектурой аппаратных механизмов, призванных обеспечить эффективную поддержку внутреннего программного параллелизма. Прежде всего, в компиляторе должно быть реализовано значительное число оптимизирующих преобразований, обладающих в своей совокупности достаточным богатством выразительных средств для отображения внутреннего программного параллелизма на возможности целевой архитектуры. Далее, применимость каждого из преобразований в таком компиляторе контролируется сложной системой эвристик. Наконец, повышенные требования предъявляются к аналитическим компонентам, т.к. слишком грубый анализ может свести на нет тот потенциал, который содержится в транслируемых программах.
Данные особенности ЕРІС-компиляторов (здесь и далее, компиляторов для ЕРІС-архитектур) накладывают на процесс разработки значительный отпечаток. Во-первых, поскольку архитектура предоставляет множество резервов, следует ожидать выявления значительного числа дефектов компилятора на протяжении всего цикла его разработки. Так что разработка характеризуется высокой интенсивностью внесения изменений в архив проекта и высоким риском возникновения деградаций. Во-вторых, в каждый момент времени разработчики стоят перед проблемой, какие преобразования наиболее эффективно реализовать в компиляторе в первую очередь, чтобы в максимально короткие сроки добиться приемлемого уровня производительности. Здесь выбор может быть как в пользу традиционных оптимизаций, так и в пользу специфичных для ЕРІС-архитектур, и, часто, уникальных преобразований. В-третьих, несмотря на то, что ЕРІС-компиляторы используют множество традиционных преобразований, для архитектур с явно выраженным параллелизмом на уровне команд, контексты применимости таких преобразований могут быть существенно расширены.
Особый интерес представляет случай разработки компиляторов для архитектур, которые только готовятся к выходу на рынок. Поскольку новая архитектура должна выходить на рынок вместе с компилятором, большая часть времени разработки последнего приходится на период, когда реальной машины еще не существует.
Диссертационная работа посвящена проблеме обеспечения поддержки процесса повышения производительности компиляторов для архитектур с явным параллелизмом на уровне команд в условиях одновременной разработки компилятора и архитектуры. Технологическим и методологическим аспектам разработки высокопроизводительных компиляторов вообще, и вопросам обеспечения поддержки процесса повышения производительности в частности, посвящено незначительное количество публикаций. В основном, внимание уделяется конечному результату - архитектурной производительности. Это также определяет актуальность проведенного в рамках диссертационной работы исследования.
Цель исследования. Конечной целью настоящей работы являлась разработка технологии повышения производительности промышленных компиляторов для новых архитектур с явно выраженным параллелизмом на уровне команды и ее реализация в виде комплекса средств, обеспечивающих поддержку данного процесса. В соответствии с этой целью были определены следующие задачи:
исследовать специфику проблемы повышения производительности компиляторов в рассматриваемых условиях (частые обновления архива проекта, много оптимизаций, исполнение на программной модели процессора и т.д.);
разработать комплексный подход к проблеме повышения производительности компиляторов, затрагивающий все значимые аспекты технологического цикла данного процесса и пригодный к использованию в условиях разработки EPIC-компилятора для новой архитектуры;
реализовать предложенный подход в виде комплекса программных средств и технологий.
Предмет исследования составляют методологические и технологические аспекты обеспечения поддержки процесса повышения производительности промышленных компиляторов:
технология повышения производительности компиляторов;
методы выявления наиболее приоритетных направлений развития компилятора;
методы контроля состояния производительности компилятора на протяжении
технологического цикла разработки.
Методы исследования заимствованы из областей системного программирования, проектирования, технологии компиляции, аттестационного тестирования, системного анализа, математической статистики, теории алгоритмов. Эффективность предложенных решений оценивалась в рамках процесса разработки оптимизирующего компилятора для архитектуры «Эльбрус 2000». Показателем эффективности являлась динамика изменения показателей производительности компилятора на задачах из пакета SPEC [SPEC].
Научная новизна
Научная новизна работы может быть представлена следующими тезисами:
Разработана технология повышения производительности, учитывающая особенности процесса разработки компиляторов для архитектур, предоставляющих значительные резервы для явного отображения на них внутреннего программного параллелизма.
Предложены стратегия поиска неоптимальностей компилятора и методика их упорядочивания, позволяющие эффективно выбирать направления развития компилятора в условиях существования множества альтернатив, обеспечивая при этом стабильный рост показателей производительности.
Предложен и реализован механизм оперативного контроля деградаций, основанный на двух оригинальных методах оценки эффекта модификаций на производительность, который позволяет обнаруживать и предотвращать случаи регресса показателей производительности компилятора за приемлемое время даже при использовании программной модели процессора.
Разработан набор алгоритмов, обеспечивающих построение тестовых примеров, требуемых для осуществления оперативного контроля в рамках предложенной методики.
Сформулированы требования к комплекту для исследования оптимизаций и разработана методика тестирования оптимизаций в рамках следования критерию полного тестирования на уровне покрытия контекстов применимости.
Предложен метод формального описания тестовых ситуаций, обеспечивающий следование критерию полноты.
Для архитектур с явной параллельностью на уровне команды разработаны
принципы построения тестов, обеспечивающие наблюдаемое проявление
эффекта от применения компилятором заданной оптимизации.
Практическая ценность результатов диссертации состоит в том, что все предложенные в работе методы и технологии были использованы для обеспечения поддержки процесса повышения производительности оптимизирующего компилятора для архитектуры «Эльбрус 2000» [Diefendorf99], [Кузьминский99], [BabayanOO], разработанной в ЗАО МЦСТ. В частности, на основе исследований, выполненных по теме диссертации, были достигнуты следующие практические результаты:
Разработана автоматизированная система оперативного контроля деградаций.
Построено множество тестовых примеров, необходимое для осуществления оперативного контроля.
Для задач из пакетов SPEC92 и SPEC95 выделено множество наиболее значимых случаев применения оптимизаций, используемое для нужд оперативного контроля.
Спроектирован и реализован тестовый комплект, предназначенный для исследования оптимизаций.
Множество тестовых примеров, построенное для осуществления оперативного контроля, было также использовано в качестве основы для проведения базовых настроек компилятора для архитектуры «Эльбрус 2000» при его портировании на архитектуру Itanium 2 [ItaniumRM].
Результаты работы
В процессе работы были получены следующие результаты:
Исследована проблема повышения производительности компиляторов.
Предложена структурная схема организации процесса повышения производительности.
Разработана методика поиска неоптимальностей, определяющая выбор наиболее приоритетных направлений развития в условиях, когда архитектура предоставляет компилятору большие возможности по оптимизации.
Предложена система приоритетов, позволяющая эффективно упорядочивать интенсивный поток сообщений о неоптимальностях.
Сформулированы требования к контролю вносимых изменений и предложены методы их достижения.
Сформулированы требования к комплекту для исследования оптимизаций, и разработана методология его построения.
Осуществлено практическое воплощение предложенных идей в виде комплекса программных средств и технологий.
Публикации
По теме диссертации опубликовано 10 печатных работ:
Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной, М.И. Нейман-заде, Е.Ю. Чернова. Методика анализа производительности компиляторов для архитектур с явной параллельностью //Компьютеры в учебном процессе, N11, с. 23-38, 2005.
Ю.В. Баскаков. Об организации контроля деградаций показателей производительности компилятора на этапе разработки // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 25-33, 2005.
Е.Ю. Архангельская, Ю.В. Баскаков, Н.Н. Серебряная, Л.Г. Тарасенко. Принципы построения тестов для исследования оптимизационных возможностей компиляторов для архитектур с явной параллельностью // Высокопроизводительные вычислительные системы п. микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 9-24, 2005.
Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной. Оценка влияния модификаций компилятора на быстродействие целевого кода // Информационные технологии и вычислительные системы, N3, с. 111-119, 2005.
Ю.В. Баскаков. Об одном подходе к организации оперативного контроля деградаций показателей производительности компилятора на множестве приложений // 1-я Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Москва, 2005. Сборник трудов, с. 355-364.
Е.Ю. Архангельская, Ю.В. Баскаков, А.В. Грабежной, Н.Н. Серебряная, Л.Г. Тарасенко. ОСТеТ: система для исследования оптимизационных возможностей компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N7, с. 3-11, 2004.
Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной, М.И. Нейман-заде, Л.Г. Тарасенко. Поддержка процесса повышения производительности компиляторов // Информационные технологии и вычислительные системы, N3, с. 78-92, 2004.
Ю.В. Баскаков, А.В. Грабежной, А.А. Лаврешников, Р.Ю. Рогов , Л.Г. Тарасенко, Е.Ю. Чернова. Вопросы организации системы обеспечения качества оптимизирующих компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N6, с. 77-85, 2004.
Ю.В. Баскаков. Поддержка процесса повышения производительности // IX Санкт-Петербургская международная конференция «Региональная информатика - 2004», Санкт-Петербург, 2004.
Ю.В. Баскаков Об одном методе оперативного контроля эффективности целевого кода при разработке оптимизирующего компилятора // Научно-техническая конференция «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003.
Апробация
Результаты, полученные в работе, изложены в ряде печатных публикаций, докладывались на научных конференциях и семинарах, в частности:
на научно-технической конференции «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003;
на IX Санкт-Петербургской международной конференции «Региональная информатика - 2004», Санкт-Петербург, 2004;
на 1-ой Международной научно-практической конференции «Современные информационные технологии и ИТ-образование», Москва, 2005 г;
на научно-технических семинарах ЗАО МЦСТ и ИМВС РАН.
Структура и объем работы
Диссертация состоит из введения, трех глав, заключения и одного приложения. Список источников насчитывает 69 наименований. Объем диссертации составляет 149 страниц текста. Диссертация содержит 7 таблиц и 43 рисунка.
Краткое содержание работы
Требования к поиску неоптимальностей и системе приоритетов
Среди основных причин построения компилятором неоптимального кода можно выделить следующие: неполнота системы условий применимости оптимизации; несовершенство аналитических компонент компилятора; ошибки в сборе аналитической информации; излишние агрессивность или консерватизм оптимизации; отсутствие ряда статистически значимых оптимизирующих преобразований; неоптимальный выбор последовательности преобразований; неоптимальности алгоритмов планирования кода на параллельные аппаратные ресурсы; неполное использование возможностей целевой платформы.
Остановимся на упомянутых выше причинах с точки зрения их внешнего проявления. Несрабатывание реализованной оптимизации в контексте применимости К моменту проведения некоторого поддерживаемого компилятором оптимизирующего преобразования может сложиться контекст, допускающий применение этой оптимизации. Однако преобразование может и не быть произведено даже при очевидной выгоде. Это может происходить из-за того, что:
компилятор не распознает текущий контекст в качестве контекста срабатывания, т.е. имеет место неполнота системы условий применимости (например, преобразование Dead Code Elimination [Muchnick97], которое не считает операции записи в локальный массив «мертвыми» операциями);
в результате анализа принимается неправильное решение о свойствах объектов или отношениях, в которых эти объекты состоят (наличие или отсутствие зависимостей, принадлежность одному классу эквивалентности и т. д.), т. е. имеют место ошибки при сборе аналитической информации (например, преобразование Memory Access Widening [ДрРо04] может не срабатывать из-за того, что некорректно работает анализ, распознающий выравнивание адресов обращений в память); анализ может также не учитывать специфичных свойств языка программирования;
анализ не может дать определенный ответ на поставленный вопрос, т. е. имеет место несовершенство алгоритмов или ограниченность возможностей анализа (например, индексный анализ может быть ограничен только на линейные выражения);
функция оценки эффективности сильно затрублена, либо не учитывает важных метрических характеристик эффективности; в этом случае стоит говорить об излишнем консерватизме эвристик применения оптимизации (например, преобразование Loop Interchange [BGS94], изменяющее порядок следования циклов в плотном гнезде, в качестве критерия применимости может учитывать только случай, когда число итераций внутреннего цикла меньше числа итераций внешнего, и не применяться, если эти значения равны, не учитывая таким образом возможного выигрыша от увеличения локальности данных);
происходит неправильный отказ от применения в условиях ограничений, влияющих на допустимое количество срабатываний оптимизации (например, если оптимизация является агрессивной по отношению к росту кода, то на этот показатель может быть наложено ограничение, так что из нескольких контекстов применимости приходится выбирать, где же выгоднее применить преобразование);
Неэффективное срабатывание оптимизации
В ряде случаев, даже если это допускает контекст срабатывания, применение оптимизирующего преобразования может приводить к нежелательным потерям производительности. То есть может потребоваться запрещать производить преобразование в определенных ситуациях, удовлетворяющих условию применимости. Здесь явно проявляются проблемы в оценке эффективности преобразования -оптимизация излишне агрессивна, - либо имеют место ошибки сбора или использования аналитической информации.
Также стоит отметить, что к этому классу недочетов относятся не только неэффективные срабатывания как таковые, но и срабатывания с неэффективно выбранным параметром. Скажем, преобразование Loop Unrolling [BGS94], приводящее в некой ситуации к потерям, все же может иметь смысл, но при раскрутке на иное количество итераций.
Преобразование не поддерживается
Ряд полезных преобразований, которые могли бы дать эффект на статистически значимом наборе анализируемых задач, компилятором могут не поддерживаться. Например, компилятором могут не использоваться те или иные возможности архитектуры или системы команд. При внесении предложений по реализации новых преобразований должна оцениваться их важность.
Испорченный контекст применимости преобразования
Правильная последовательность применения преобразований также значит очень много для достижения максимального эффекта от оптимизаций. Так, одни оптимизации могут расширять или даже создавать контекст применимости для последующих. Напротив, предшественник может благоприятный контекст разрушать (например, Loop Unrolling может разрушить контекст Loop Fusion [BGS94]). Так что неправильно выстроенная линейка оптимизаций может приводить к серьезным потерям.
Анализ производительности на отдельной задаче
Выбор фрагментов для анализа. Прежде всего, необходимо выбрать набор фрагментов для последующего анализа. Достаточно ограничить список рассматриваемых процедур теми, которые составляют верхушку профиля исполнения задачи. Анализ будет наиболее эффективным, если на выбранные процедуры приходится подавляющая часть (80-90%) времени работы задачи. В каждой из процедур необходимо выделить набор фрагментов, определяющих основное время работы процедуры. Здесь основным критерием является прозрачность для анализа (небольшой размер фрагмента) и его замкнутость относительно управления (одна точка входа).
Исследование фрагментов. Для каждого из фрагментов желательно найти такое его преобразование, которое бы обеспечивало на этом фрагменте максимум производительности. При поиске оптимального преобразования должны быть учтены как специфика фрагмента, так и все ограничения и доступные ресурсы целевой архитектуры.
Для каждого фрагмента Ф, в зависимости от его типа, устанавливается порядок действий по поиску его оптимального преобразования:
1. Ф - многоитерационный самый влоэюепный цикл с простым управлением; (а) Если отсутствует межитерационная рекуррентность (или она не критична), то оптимизация должна быть направлена на уменьшение числа операций в цикле и максимальное использование возможностей архитектуры, таких как, например, потенциал широкой команды, аппаратная поддержка конвейеризации циклов, комбинированные операции, упреждающее чтения элементов массива, операции над упакованными целыми и вещественными числами и т. д. Здесь могут оказаться полезными Loop Unrolling, Overlap [ДрСт04], Code Vectorization [LaAmOO], а также ряд других платформозависимых оптимизаций. При этом должны учитываться ресурсные ограничения (например, размер и свойства кэшпамяти, количество доступных регистров, размер широкой команды). Так что к упомянутым выше оптимизациям могут добавиться еще и методы для борьбы с ограничениями: Prefetch - для оптимизации работы с кэш-памятью, Loop Distribution [BGS94] - при нехватке регистров и т. д.
1 Если наличие рекуррентности в цикле мешает эффективному использованию всех предоставляемых архитектурой возможностей, то поиск оптимального преобразования должен быть направлен на уменьшение длины рекуррентности {Lazy Code Motion [KRS92], Expression Balancing [Muchnick97] и др.), или на ослабление ее роли. Последнее подразумевает возможность использования свободных устройств операциями, пришедшими извне, что требует анализа всего содержащего цикл региона или гнезда циклов (3);
2. Ф - многоитерационный цикл со сложным управлением (возможно, содержит вложенные малоитерационные циклы); Необходимо обратить внимание на использование всех резервов упрощения управления (Loop Nesting [VoMa93], Loop Unswitching [BGS94], Loop Splitting [BGS94], Procedure Mining и т.д.) Если это удалось, то дальше действовать согласно (1), иначе - выделить наиболее важные ациклические области и разбираться с ними по отдельности (4);
3. Ф - гнездо циклов с простым управлением (или регион, содержащий несколько однотипных циклов);
Необходимо проанализировать применимость гнездовых оптимизаций (Loop Fusion, Unroll-and-Jam [СаКе94], Loop Interchange и т. д.) с целью привести по возможности все внутренние циклы к виду (1а)
4. Ф - ациклический участок, содержащий малоитерационные циклы; Если таким участком является вся процедура, то полезно исследовать возможность inline-подстановки (процедура небольшая) или частичной inline-подстановки (можно отделить наиболее вероятную часть потока управления). В общем случае, объектом исследования является набор небольшого числа наиболее вероятных траекторий потока управления, такой, что суммарная вероятность пучка выбранных траекторий вносит основной вклад в весь поток управления ( 80%), и ставится задача исследовать возможность минимизации критических путей, отвечающих этим траекториям.
После того, как найден способ оптимизации фрагмента, необходимо произвести его разложение в цепочку оптимизаций, которые уже реализованы (или могут быть реализованы) в компиляторе. Во время этого процесса возможна значительная корректировка найденного преобразования. Также возможная цепочка оптимизаций может не быть единственной.
Выработка предложений. Если код, полученный компилятором, проигрывает в сравнении с результатом теоретического исследования, то, последовательно проверяя на рассматриваемом фрагменте работу оптимизаций из построенной цепочки, находится неэффективно отработавшая (как вариант - отсутствующая) оптимизация и оформляется предложение с указанием на эту неэффективность и методами ее устранения.
Оценки и предсказания
Следует особо выделить еще одно направление деятельности, которое является чрезвычайно актуальным для эффективного ведения разработки компилятора. А именно, в ходе анализа должен производиться целый ряд количественных оценок и экспертных предсказаний.
Во-первых, для каждого предложения, относящегося к задачам из представительного множества, целесообразно оценивать ожидаемый эффект от его реализации. Такого рода оценки могут учитываться при выборе приоритетов для предложений, а также являются индикатором значимости для контроля деградаций. К тому же на их основе может быть посчитана суммарная выгода от предложений, находящихся на стадии реализации.
Во-вторых, имеет смысл предсказывать значение пиковой производительности компилятора на представительном множестве программ. Знание предельного показателя производительности является важным психологическим фактором и стимулом к дальнейшему улучшению компилятора. Оно позволяет судить, на какой стадии в текущий момент находится разработка и к чему нужно стремиться. Также, прогноз на пиковую производительность может учитываться при планировании дальнейших работ по развитию компилятора.
Оценка эффекта от реализации выработанных предложений
Необходимо различать локальный и глобальный эффекты. Под локальным эффектом от реализации предложения понимается ожидаемый эффект от применения элементарного преобразования, составляющего его основу, в том контексте и для той задачи, для которых это предложение было сформулировано. Глобальный же эффект определяется распространенностью данного контекста среди задач из представительного множества. В то время как массовость предложения не всегда является очевидной, эффект от преобразования в заданном контексте может быть спрогнозирован достаточно точно.
Существуют два основных метода оценки эффекта от применения некоторого преобразования в заданном контексте: теоретический прогноз и эксперимент.
При теоретическом прогнозе, оценка локального эффекта от реализации предложения производится исходя из оптимистического взгляда на работу компилятора, в котором данное предложение поддерживается. Например, в предположении идеального планирования может быть предсказана длина итерации конвейеризованного цикла, из которого, согласно предложению, удалены некоторые операции.
Требования к выбору значений порога деградации
Принятие решения о допустимости модификации осуществляется на основании вычисленных значений используемых метрик деградации. Поскольку деградация может носить легальный характер, должен существовать определенный допуск є на значения каждой из метрик, который будем в дальнейшем называть порогом деградации. Кроме того, этот порог должен позволять отфильтровывать шумы, связанные с погрешностью измерений, что особенно важно при использовании временных метрических характеристик производительности.
Для относительных метрик деградации, критерием приемлемости модификации является, таким образом, неравенство вида: (1-уСО-100 , где р - метрика, а є - порог деградации, заданный в процентах.
В случае абсолютных метрик соотношение имеет вид р е, где є задается как абсолютная величина.
Значение порога может различаться в зависимости от типа относительных метрик. Так, для метрик, оценивающих массовость проявления эффекта модификаций на производительность (например, для метрики среднего геометрического), порог деградаций целесообразно делать поменьше, в то время как для метрик, контролирующих выбросы, - побольше.
Выбор величины порога как для абсолютных так и для относительных метрик должен определяться теми издержками, которые имеют место при ложной тревоге (когда модификация признается недопустимой, таковой не являясь), а также трудозатратами на выявление и устранение причин деградации в противном случае.
Методы оценки эффекта модификаций на производительность
Оценка эффекта модификаций на производительность должна обладать свойством достоверности. В идеале она должна основываться на результатах реальных замеров быстродействия, проводимых на всем множестве программ 2, которые может воспринять на вход компилятор. Однако, в силу потенциальной бесконечности такого множества, область оценки должна быть ограничена на некоторый достаточно представительный класс задач (Q . Как правило, в этот класс входят задачи, используемые для анализа производительности [RHD98], [БГВНТ04].
Стоит отметить, что даже при таких ограничениях получение полной картины о состоянии производительности может потребовать часы или даже сутки (особенно в условиях, когда вместо реального процессора используются программные модели, существенно замедляющие скорость выполнения, а пользовательские характеристики компилятора, такие как время компиляции, еще далеки от промышленных требований), т. к. в представительный класс обычно попадают достаточно большие и ресурсоемкие задачи. Так что в процессе разработки, когда действуют временные ограничения и требуется оперативность принятия решений, методы оценки эффекта модификаций по общему времени выполнения программ могут оказаться практически неосуществимыми.
Оперативная оценка общего времени выполнения
С целью обеспечения более быстрого выявления деградаций на больших прикладных задачах, могут применяться методы оценки общего времени выполнения транслированных программ, отличные от его непосредственного замера. К таким методам можно отнести: ? метод статического предсказания; ? метод масштабирования результатов.
Наряду с тем, что данные методы позволяют значительно сократить время на установление факта наличия или отсутствия деградации компилятора на некотором приложении, они также сохраняют возможность получать достаточно достоверную картину о реальном быстродействии задачи с тем, чтобы проводить сравнение с эталонными оценками быстродействия. Рассмотрим данные методы более подробно.
Метод статического предсказания
В основе данного метода лежит техника предсказания производительности на этапе компиляции (см., например, [Cascaval99], [LMW99], [TVVA03]). Помимо идеального числа тактов, т.е. времени выполнения программы в предположении отсутствия затрат на переходы и доступ в память, оценка общего времени выполнения f может также учитывать издержки, связанные с организацией памяти и с неправильно предсказанными переходами. Формула (2.1) устанавливает связь между оценками: Т = Тideal + Тщет + ТЪг (2.1)
Как отмечается в [TVVA03], оценка идеального числа тактов для программы Р может быть представлена формулой: fideal= хгоо-ад, beB(P) где B(P) является разбиением программы Р на фрагменты, а Tib) и w(b) представляют для некоторого фрагмента Ъ оценки идеального числа тактов и веса соответственно. В качестве фрагментов обычно рассматривают линейные участки [Cascaval99], [TVVA03].
В зависимости от целевой архитектуры и требований к достоверности, для получения оценки идеального числа тактов для фрагмента b могут использоваться различные модели. Так в [Cascaval99] описана простейшая модель, когда время выполнения фрагмента определяется как сумма времен операций его составляющих. Там же говорится и о более сложных моделях, учитывающих возможность одновременного выполнения операций и основанных на использовании графа зависимостей. В [TVVA03] для оценки длины фрагмента в тактах предлагается пользоваться результатами предварительного планирования.
Информация о весе фрагмента может являться как результатом статического предсказания, так и основываться на экспериментальных данных, полученных в ходе профилирования. Однако, если в случае оценки времени выполнения фрагмента можно ставить вопрос о какой-то прогнозируемой точности, то его вес, даже при использовании профильной информации, является менее предсказуемой величиной. Действительно, профилирование линейных участков исходной программы и переходов между ними, поддерживаемое большинством компиляторов, позволяет иметь адекватную картину о весах лишь до того момента, когда начинают работать оптимизации, которые вносят недетерминизм в распределение потока управления.
Особенности реализации системы тестирования ОСТеТ
В качестве основного метода тестирования оптимизаций в системе ОСТеТ был выбран двухрежимный подход, реализующий сравнение неоптимизированной {базовой) и идеальной {эталонной) кодировок (см. рис.3.1). Данное решение было обусловлено потребностью в наблюдении за эффектом от применения оптимизирующих преобразований с целью обеспечения возможности исследования пространства оптимизаций для ЕРІС-архитектур.
При вынесении вердикта производится вычисление отношения времен выполнения результатов компиляции базовой и эталонной кодировок, которое затем проходит через серию проверок. Если полученное отношение больше 1 + 5",, где fj 0 - некоторое пороговое значение, то оптимизация считается неприменившейся и для теста выдается вердикт FAIL. При значении близком к 1, тест считается завершившимся успешно. Если же отношение получилось меньше чем 1 - є2, где є2 0, то выдается промежуточный вердикт CHECK, который должен быть в дальнейшем разрешен в пользу одного из окончательных вердиктов: PASS или NOT_APPLICABLE.
Первый случай имеет место, когда преобразование применилось, но эталонная кодировка оказалась недостаточно эффективной (возможно, она требует модификации). Во втором случае, предлагаемое в качестве эталона преобразование для рассматриваемой архитектуры приводит к ухудшению показателей производительности, а, значит, неприменимо.
При тестировании компилятора для архитектуры «Эльбрус 2000» пороговые значения для всех оптимизаций были выбраны равными є1= є2 = 0.05. Во многом это обуславливалось тем, что исполнение тестов осуществлялось на программной модели процессора, так что погрешности измерения, свойственные реальному окружению, были исключены.
Стоит отметить, что выбранная схема двухрежимного подхода подразумевает заметную разницу в производительности двух вариантов теста в тех случаях, когда преобразования не произошло. Для оптимизаций, меняющих структуру управления (например, Loop Fusion, Loop Unswitching [BGS94], Lazy Evaluation [Muchnick97]), как правило, может быть создано такое окружение, что независимо от изменения параметров контекста применимости, любое единичное срабатывание оптимизации дает многократный эффект . Это окружение формируется путем соответствующего выбора операций на линейных участках.
Однако, для ряда оптимизаций, которые структуру управления не меняют, и особенно для тех, задача которых состоит в сокращении числа операций (например, Redundant Load Elimination, Dead Code Elimination [Muchnick97]), заметная разница между производительностью базового и эталонного вариантов не может быть обеспечена во всех контекстах их применимости, даже если в эталонном варианте кроме рассматриваемого преобразования проделывать и другие, пользующиеся его результатами.
В некоторых случаях заметная разница между базовой и эталонной кодировками для таких оптимизаций может быть достигнута путем их многократного применения. При этом, эффект достигается в результате повышения удельного веса11 операций, затрагиваемых оптимизацией. Наиболее безопасным способом реализации подобной технологии является создание нескольких одинаковых контекстов применимости. Если это не дает должного эффекта, то можно попытаться выстроить цепочку зависимых друг от друга срабатываний оптимизации, возможно, добавив при этом контексты применимости, не относящиеся к цели данного теста.
Упомянутые выше подходы проиллюстрированы на рис.3.2 для оптимизации Loop Invariant Code Motion [BGS94], работа которой проверяется для случая выноса инвариантных операций из внешнего цикла гнезда. Эффект от применения данного преобразования будет заметным, если время выполнения внутреннего цикла сравнимо со временем выполнения выносимых операций. На рис.3.2а, с целью повышения удельного веса затрагиваемых оптимизацией объектов, вместо одной инвариантной операции деления во внешний цикл помещено три операции, реализующие одинаковый контекст. Так что для архитектур, в которых деление представляется цепочкой вычислений (например, Itanium 2 [ItaniumRM]), время выполнения данного гнезда после выноса инвариантов существенно уменьшится. На рис.3.2б представлен менее платформозависимый вариант, т.к. вес выносимого инвариантного выражения inv2/(inv2/(inv2/invl)) определяется лишь временем выполнения одной операции деления и числом таких операций в цепочке.
