Компонентный подход к построению оптимизирующих компиляторов (27.09.2010)

Автор: Дроздов Александр Юльевич

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

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

Предмет исследования

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

Алгоритмические основы функционирования блоков оптимизирующих компиляторов:

методы статического анализа программ;

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

методы многопоточного распараллеливания программ на основе технологии OpenMP;

методы группирования оптимизаций для ускорения работы компилятора и для получения более эффективного машинного кода;

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

Методология разбиения оптимизирующего компилятора на блоки различного уровня абстракции;

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

Методология портирования блоков оптимизирующей компиляции в контексте существующих инфраструктур оптимизирующей компиляции (GCC, phoenix, ACE, open64, pathscale, …);

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

Методы исследования заимствованы из областей системного программирования, методологии компиляции, теории графов, теории абстрактной интерпретации, теории Диофантовых уравнений и неравенств, математической логики. Эффективность предложенных методов оценивалась путем вычисления значений ключевых параметров (время работы компилятора, производительность результирующего кода и т.п.), и сравнения значений этих параметров, со значениями, полученными с помощью традиционных подходов. Для проведения замеров использовался инструментальный комплекс в составе оптимизирующего компилятора и потактной модели архитектуры «Эльбрус-3М» и автоматический распараллеливатель, работающий в составе компиляторной технологии GCC (www.gnu.org). Замеры производились на пакетах задач Spec92, Spec95 и Spec2006.

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

Научной новизной в диссертации обладают:

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

разработка быстрого алгоритма построения формы статического единственного присваивания;

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

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

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

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

разработка единого метода решения задач межпроцедурного анализа потока данных, в том числе задачи межпроцедурной нумерации значений (Value Numbering);

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

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

разработка новых методов построения компонент оптимизирующей компиляции:

разработка методологии реализации блоков оптимизирующей компиляции, позволяющей распараллеливать работу компилятора;

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

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

Практическая ценность результатов работы состоит в том, что предложенные в работе алгоритмические и методологические основы построения оптимизирующих компиляторов использовались в процессе реализации оптимизирующего компилятора для архитектуры «Эльбрус-3М» и для добавления в технологию GCC ранее не существовавшей там функциональности (векторизатор, распараллеливатель на уровне потоков, анализатор программ).

Апробация

Результаты работы докладывались на Всероссийской научно-практической конференции «Перспективы развития высокопроизводительных вычислительных архитектур: история, современность и будущее отечественного компьютеростроения», приуроченной к 60-летию ИТМиВТ им. С.А. Лебедева РАН в 2008 году.

Практические результаты работы докладывались на международном форуме «Салон инноваций и инвестиций — 2008», который проходил в Москве, ВВЦ, в 2008 году. Проект «Разработчик оптимизирующих компиляторов» был удостоен золотой медали VIII Московского международного салона инноваций и инвестиций.

Результаты работы докладывались на IХ Санкт-Петербургской Международной конференции «Региональная информатика–2004 (РИ–2004)» в 2004 г., на Международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, 2004 г.), XXI Научно-технической конференции войсковой части 03425 (Москва, в/ч 03425, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО “МЦСТ” (2003-2005 гг.), Института микропроцессорных вычислительных систем РАН (2004-2005 гг.), Института точной механики и вычислительной техники им. С.А. Лебедева РАН (2007-2008 гг.), Института системного программирования РАН (2008), ОАО «Научно-исследовательский центр электронной вычислительной техники» (НИЦЭВТ) (2008) и НИВЦ МГУ им. Ломоносова (2009, 2010).

Публикации

По теме диссертации опубликованы 36 печатных работ. Из них 14 в изданиях, рекомендованных ВАК.

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

Диссертация состоит из пяти глав и заключения. Диссертация содержит 307 страниц, 124 рисунка, 23 таблицы. Список литературы насчитывает 160 наименований.

Краткое содержание работы


загрузка...