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

Актуальность темы

При промышленной разработке систем информационных технологий к эффективности1 конечного продукта традиционно предъявляются высокие требования. Не исключением являются и компиляторы. Как отмечается в [RHD98], эффективность компиляторов имеет две составляющие. Одна из них характеризует этап компиляции и затрагивает такие его аспекты как, например, скорость компиляции и объем выделяемой в процессе компиляции динамической памяти. Другая же относится к качеству генерируемого компилятором кода и определяется временем его выполнения и/или его размером. Такое разделение выбрано неслучайно — время компиляции и затрачиваемая при этом память важны для разработчиков приложений, в то время как быстродействие и компактность кода представляют интерес с точки зрения их конечного пользователя.

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

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

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

1 Одно из определений понятия эффективности можно найти, например, в [ББКЛММ81]: программный продукт обладает свойством эффективности, если он выполняет требуемые функции без излишних затрат ресурсов, где ресурсы понимаются в широком смысле.

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

Кроме того, как показывает практика [RHD98], [БВГНТ04], при разработке компилятора приемлемого уровня быстродействия целевого кода можно добиться лишь в результате непрерывного контроля текущего состояния производительности. Действительно, любые модификации исходного кода компилятора, будь то исправление ошибок или расширение функциональности, являются потенциальными источниками деградации достигнутых показателей быстродействия.

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

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

Проблема разработки высокопроизводительных оптимизирующих компиляторов становится еще более актуальной в свете современных тенденций развития вычислительной техники. Традиционные суперскаляры, реализующие динамический подход к распараллеливанию вычислений, практически достигли предельного уровня аппаратной сложности и не могут масштабироваться до бесконечности для поддержания темпов роста производительности, к которым привыкло современное общество [LeVa03]. Одним из путей к преодолению данного ограничения является перенос основных интеллектуальных функций аппаратуры на уровень программного обеспечения. Этот подход лежит в основе так называемых архитектур с явно выраженным параллелизмом на уровне команд (Explicitly Parallel Instruction Computing, EPIC).

Производительность архитектур с явно выраженным параллелизмом (далее, для краткости, EPIC-архитектур) сильно зависит от возможностей компилятора оптимальным образом распределять аппаратные ресурсы статически [ACMS98]. Учитывая тот факт, что величина значения тактовой частоты и параллелизм уровня команд являются антагонистичными свойствами [АНКВОО], коммерческий успех архитектуры в целом определяется качеством оптимизационных возможностей компилятора, что наглядно демонстрируется на примере архитектуры Itanium / Itanium 2. Действительно, на начальном этапе отсутствие приемлемого компилятора являлось серьезным сдерживающим фактором продвижения данной архитектуры на рынок.

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

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

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

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

Цель исследования. Конечной целью настоящей работы являлась разработка технологии повышения производительности промышленных компиляторов для новых архитектур с явно выраженным параллелизмом на уровне команды и ее реализация в виде комплекса средств, обеспечивающих поддержку данного процесса. В соответствии с этой целью были определены следующие задачи: исследовать специфику проблемы повышения производительности компиляторов в рассматриваемых условиях (частые обновления архива проекта, много оптимизаций, исполнение на программной модели процессора и т. д.) — разработать комплексный подход к проблеме повышения производительности компиляторов, затрагивающий все значимые аспекты технологического цикла данного процесса и пригодный к использованию в условиях разработки EPIC-компилятора для новой архитектурыреализовать предложенный подход в виде комплекса программных средств и технологий.

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

Методы исследования заимствованы из областей системного программирования, проектирования, технологии компиляции, аттестационного тестирования, системного анализа, математической статистики, теории алгоритмов. Эффективность предложенных решений оценивалась в рамках процесса разработки оптимизирующего компилятора для архитектуры «Эльбрус 2000». Показателем эффективности являлась динамика изменения показателей производительности компилятора на задачах из пакета SPEC [SPEC].

Научная новизна.

Научная новизна работы может быть представлена следующими тезисами:

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

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

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

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

Сформулированы требования к комплекту для исследования оптимизаций и разработана методика тестирования оптимизаций в рамках следования критерию полного тестирования на уровне покрытия контекстов применимости.

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

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

Практическая ценность результатов диссертации состоит в том, что все предложенные в работе методы и технологии были использованы для обеспечения поддержки процесса повышения производительности оптимизирующего компилятора для архитектуры «Эльбрус 2000» [Diefendorf99], [Кузьминский99], [BabayanOO], разработанной в ЗАО МЦСТ. В частности, на основе исследований, выполненных по теме диссертации, были достигнуты следующие практические результаты:

Разработана автоматизированная система оперативного контроля деградаций.

Построено множество тестовых примеров, необходимое для осуществления оперативного контроля.

Для задач из пакетов SPEC92 и SPEC95 выделено множество наиболее значимых случаев применения оптимизаций, используемое для нужд оперативного контроля.

Спроектирован и реализован тестовый комплект, предназначенный для исследования оптимизаций.

Множество тестовых примеров, построенное для осуществления оперативного контроля, было также использовано в качестве основы для проведения базовых настроек компилятора для архитектуры «Эльбрус 2000» при его портировании на архитектуру Itanium 2 [ItaniumRM].

Результаты работы.

В процессе работы были получены следующие результаты:

Исследована проблема повышения производительности компиляторов.

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

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

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

Сформулированы требования к контролю вносимых изменений и предложены методы их достижения.

Сформулированы требования к комплекту для исследования оптимизаций, и разработана методология его построения.

Осуществлено практическое воплощение предложенных идей в виде комплекса программных средств и технологий.

Публикации.

По теме диссертации опубликовано 10 печатных работ:

1. Ю. В. Баскаков, В. Ю. Волконский, А. В. Грабежной, М.И. Нейман-заде, Е. Ю. Чернова. Методика анализа производительности компиляторов для архитектур с явной параллельностью // Компьютеры в учебном процессе, N11, с. 23−38, 2005.

2. Ю. В. Баскаков. Об организации контроля деградаций показателей производительности компилятора на этапе разработки // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 25−33, 2005.

3. Е. Ю. Архангельская, Ю. В. Баскаков, Н. Н. Серебряная, Л. Г. Тарасенко. Принципы построения тестов для исследования оптимизационных возможностей компиляторов для архитектур с явной параллельностью // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 9−24, 2005.

4. Ю. В. Баскаков, В. Ю. Волконский, А. В. Грабежной. Оценка влияния модификаций компилятора на быстродействие целевого кода // Информационные технологии и вычислительные системы, N3, с. 111−119, 2005.

5. Ю. В. Баскаков. Об одном подходе к организации оперативного контроля деградаций показателей производительности компилятора на множестве приложений // 1-я Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Москва, 2005. Сборник трудов, с. 355−364.

6. Е. Ю. Архангельская, Ю. В. Баскаков, А. В. Грабежной, Н. Н. Серебряная, Л. Г. Тарасенко. ОСТеТ: система для исследования оптимизационных возможностей компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N7, с. 3−11, 2004.

7. Ю. В. Баскаков, В. Ю. Волконский, А. В. Грабежной, М.И. Нейман-заде, Л. Г. Тарасенко. Поддержка процесса повышения производительности компиляторов // Информационные технологии и вычислительные системы, N3, с. 78−92, 2004.

8. Ю. В. Баскаков, А. В. Грабежной, А. А. Лаврешников, Р. Ю. Рогов, Л. Г. Тарасенко, Е. Ю. Чернова. Вопросы организации системы обеспечения качества оптимизирующих компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N6, с. 77−85, 2004.

9. Ю. В. Баскаков. Поддержка процесса повышения производительности // IX Санкт-Петербургская международная конференция «Региональная информатика — 2004», Санкт-Петербург, 2004.

10. Ю. В. Баскаков Об одном методе оперативного контроля эффективности целевого кода при разработке оптимизирующего компилятора // Научно-техническая конференция «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003.

Апробация.

Результаты, полученные в работе, изложены в ряде печатных публикаций, докладывались на научных конференциях и семинарах, в частности: на научно-технической конференции «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003; на IX Санкт-Петербургской международной конференции «Региональная информатика — 2004», Санкт-Петербург, 2004; на 1-ой Международной научно-практической конференции «Современные информационные технологии и ИТ-образование», Москва, 2005 гна научно-технических семинарах ЗАО МЦСТ и ИМВС РАН.

Структура и объем работы.

Диссертация состоит из введения, трех глав, заключения и одного приложения. Список источников насчитывает 69 наименований. Объем диссертации составляет 149 страниц текста. Диссертация содержит 7 таблиц и 43 рисунка.

3.5 Выводы.

В данной главе были затронуты проблемы тестирования оптимизирующих преобразований. В частности, рассмотрена система ОСТеТ, разработанная для исследования пространства оптимизаций в контексте архитектуры «Эльбрус 2000» и осуществляющая их тестирование посредством изоляции функциональности последних.

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

В данной главе предложены стратегия и принципы построения набора атрибутов, а также сформулирован критерий полноты тестирования в терминах элементов спецификации.

Кроме того, на примере архитектуры «Эльбрус 2000» проведено исследование возможностей по выявлению дефектов оптимизаций в случае использования двухрежимного подхода в контексте EPIC-архитектур. Для каждого класса оптимизаций подробно рассмотрены разработанные автором принципы построения тестов, обеспечивающие наблюдаемое проявление эффекта от применения заданного преобразования. Также предложена структура тестов и разработана политика их взаимодействия с тестовым окружением. Для поддержки реализации преобразований, результат работы которых зависит от профильной информации, разработан механизм достижения заданного распределения вероятностей прохождения путей программы.

Построенная в соответствии с разработанной автором методологией, система ОСТеТ, включающая тесты для 22 оптимизаций общим числом 1928 штук, была успешно применена не только для исследования оптимизационных возможностей компилятора для архитектуры «Эльбрус 2000», но и для тестирования промышленного компилятора фирмы Intel для архитектуры Itanium 2. В последнем случае было выявлено 898 фактов несрабатывания оптимизаций в благоприятных контекстах.

Что касается результатов использования системы ОСТеТ в рамках процесса повышения производительности компилятора для архитектуры «Эльбрус 2000», то было выявлено и устранено 192 различных случая неприменения оптимизаций в благоприятных контекстах, а также 105 случаев нарушения работоспособности программ. При этом, был обнаружен ряд ошибок взаимодействия оптимизаций. Для текущего состояния компилятора системой ОСТеТ зафиксировано 527 фактов несрабатывания оптимизаций.

Заключение

.

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

— существование множества альтернативных направлений для дальнейшего развития;

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

— высокая интенсивность внесения изменений в архив проекта;

— высокий риск возникновения деградацийведение работ при отсутствии готового процессора.

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

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

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

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

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