Компонентный подход к построению оптимизирующих компиляторов 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание ученой степени доктора технических наук Москва

Авторефераты по всем темам >> Авторефераты по техническим специальностям

На правах рукописи

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

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени

доктора технических наук

Москва Ц 2010

Работа выполнена в Институте Точной Механики и Вычислительной техники им. С.А. Лебедева

Официальные оппоненты:

доктор физико-математических наук,

чл.-корр. РАН

Воеводин Владимир Валентинович

доктор физико-математических наук

Галатенко Владимир Антонович

доктор физико-математических наук

Крюков Виктор Алексеевич

Ведущая организация

Учреждение Российской академии наук Вычислительный центр им.аА.аА.аДородницынаа РАН

Защита состоится 16 декабря 2010 г. в 15 ч. 00 мин. на заседании диссертационного совета Д.002.087.01 при Институте системного программирования РАН по адресу:

109004, Москва, ул. Александра Солженицына, д.25,

Институт системного программирования РАН, конференц-зал (комн. 110).

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН.

Автореферат разослан ___ 2010 г.

Ученый секретарь

диссертационного совета

кандидат физико-математических наук /Прохоров С.П./

Общая характеристика работы

Актуальность работы

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

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

Разработка каждого отдельного решения требует временных затрат в пределах десятков человеко-лет и значительных затрат по сопровождению этих решений. В качестве примеров можно привести оптимизирующие компиляторы компаний Intel, Sun Microsystems, Transmeta, Microsoft, IBM, HP, Elbrus, и др. Все эти компании создали свои собственные, не совместимые друг с другом коммерческие продукты с высоким уровнем внутренней сложности. Этот процесс продолжает нарастать, так как нужно соответствовать современной тенденции увеличения разнообразия аппаратных решений (Multi core, Many core, EPIC и т.д.).

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

Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая всё более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, её значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.

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

Динамическое распараллеливание вычислений наиболее распространено в современных микропроцессорах и продолжает обеспечивать некоторый рост производительности исполнения вычислительных задач. Но дальнейшее увеличение параллельности на уровне операций в архитектурах процессоров может быть ограничено квадратичным усложнением логики проверок в аппаратуре при планировании выполнения команд. Поэтому статический подход к реализации пооперационной параллельности в процессе компиляции сейчас активно развивается как альтернатива суперскалярным (с динамическим планированием вычислений) процессорам. Для обозначения такого рода архитектур во второй половине 90-х годов появился термин EPIC (Explicitly Parallel Instruction Computing) - архитектура с явно выраженной параллельностью на уровне команд.

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

Цель диссертационной работы

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

Исходя из вышеизложенного, для достижения поставленной цели в работе выполняются:

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

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

Для достижения поставленных целей особое внимание в данной работе уделено таким методам оптимизирующей компиляции как статический анализ программ, внутрипроцедурные трансформации программ, планирование и разбиение задачи на потоки. Применение этих методов позволяет добиваться полноценного использования таких архитектурных особенностей 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 наименований.

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

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

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

Структурные аспекты

В качестве языка реализации был выбран язык C++, как проверенный инструмент отображения абстракций объектно-ориентированного проектирования.

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

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

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

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

- использование единого стиля программирования;

- использование методов и практик объектно-ориентированного проектирования и программирования;

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

- использование средств внутренней верификации и отладки;

- использование средств визуализации внутренних структур данных;

- использование средств автоматической документации программ;

- глубокое тестирование программ.

На настоящий момент времени блоки оптимизирующей компиляции, реализованные на основе технологии, предложенной в данной работе, оттестированы в технологической цепочке компиляторов GCC. Компиляция с языков C, C++, FORTRAN оттестирована в контексте архитектуры x86. Сейчас есть возможность производить тестирование в контексте любой целевой архитектуры, поддержанной в технологической цепочке GCC - x86, Itanium, SPARC, MIPS, Power PC, Power Cell.

Параметризация окружения

Рис. 1 иллюстрирует основной подход к переносимости технологии в произвольные технологические цепочки.

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

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

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

Рис.1 Иерархия блоков и база данных программы

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

Реализация иерархии блоков оптимизирующей компиляции основана на применении объектно-ориентированного программирования (ООП) и выполнена на одном из самых распространенных языков ООП С++. Основная идея ООП состоит в том, что данные отделяются от алгоритмов. Это не совсем бесплатное свойство, так как ведет к увеличению времени компиляции. Известно, что чем более специализирована реализация, тем она быстрее, а здесь, наоборот, используется наиболее абстрактная форма представления программы.

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

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

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

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

Для того чтобы произвести абстрагирование, программу необходимо представить в понятиях настолько общих, что внутренняя структура реализации этого представления не будет никак сказываться на реализации блоков. Наиболее общий подход к хранению и манипуляции данных, позволяющий практически полностью абстрагировать конкретный способ хранения этих данных, представлен в использовании базы данных Oracle. Доступ к базе данных (заполнение, изменение, удаление) осуществляется при помощи интерфейса запросов (SQL) или при помощи функционального интерфейса (PL SQL), что и позволяет полностью скрыть реализацию базы от пользователя. Подобный подход применим и в случае с информацией о программе (информация о высокоуровневом языке, информация о семантике операций и информация о целевой архитектуре (machine model)). Задание всех входных параметров компиляции через такую базу данных позволяет полностью скрыть от пользователя детали используемого промежуточного представления программы и, таким образом, делает все блоки независимыми от технологической цепочки, в которой они будут использоваться.

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

Итак, мы имеем три разновидности информации о контексте, в котором работает оптимизатор: информация с языка высокого уровня (измерения массивов, символьная таблица), информация о семантике (представление семантики через небольшую расширяемую номенклатуру операций, с заданием порядка между ними), и информация о машинной модели (информация о правилах, по которым команды должны помещаться в исполняемый файл, а также вся информация об особенностях архитектуры, которую можно использовать в целях оптимизации). Таким образом, мы имеем полную гибкость в отношении контекста. Например, в случае двоичной компиляции в базе не будет ссылок из семантического представления в таблицу языковой информации, которая приходит из языков высокого уровня (С, С++, Fortran, Е), но будут ссылки в таблицу машинной модели и все методы оптимизации будут работать без каких-либо изменений. Это также относится к случаю, когда есть только семантика и языковая информация. В этом случае все методы будут делать только то, что можно сделать на основе этой информации без знания машинной модели.

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

Распараллеливание работы компилятора

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

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

Рис. 2. Распараллеливание

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

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

Методы портирования

Рис. 3 Способы портирования

Существует три сценария взаимодействия блоков оптимизирующей компиляции с системой трансляции пользователя (рис. 3, 4).

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

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

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

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

Рис. 4 Методика портирования

Семантическое представление

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

Операционное представление является списком операций. У операции может существовать входной контекст и выходной контекст. Входной и выходной контексты задаются списками аргументов и результатов. Аргументы могут быть литералами, объектами или ссылками на другие операции. Отображение связи между результатом одной операции и аргументом другой через объекты является более общей, чем представление этой связи в виде ссылки на операцию. Сама операция представляет собой набор атрибутов, определяющих семантическое действие над входным контекстом для получения выходного контекста. К такому операционному представлению может быть сведено практически любое известное промежуточное представление, начиная с синтаксических деревьев фронтендов (gcc, edg), заканчивая представлениями, наиболее приближенными к ассемблерам целевой архитектуры.

Рис. 5 Представление операции

Аналитическое представление

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

Для представления фрагментации программы на уровне аналитического представления вводится понятие области видимости. Области видимости имеют иерархическую организацию. Каждый объект программы принадлежит одной из областей видимости. Понятия модуля и процедуры семантического представления программы представляются областями видимости в аналитическом представлении программы.

Элементами аналитического промежуточного представления являются аналитические операции (рис. 6). Входным контекстом для аналитических операций являются объекты и литералы. Выходным контекстом могут быть только объекты.

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

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

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

Семантическая модель

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

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

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

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

На рис. 7 приведен пример семантической модели операции сложения с тремя аргументами.

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

Совместимость с GCC

Технология, представленная в работе, может применяться на платформах Windows, Linux или как кросс-платформенная. Исходный код транслируется с языков C, C++, Fortran компилятором GCC. С промежуточного представления высокого уровня СGIMPLEТ, используемого в gcc, семантика экспортируется в файл в формате базы данных программы, из которого она далее разворачивается в промежуточное представление оптимизирующих блоков. На этом промежуточном представлении применяются оптимизации, после чего модифицированная семантика экспортируется обратно в файл, из которого она далее возвращается обратно в компилятор GCC, разворачивается в нем в его промежуточное представление и далее транслируется в код целевой машины, например x86, SPARC, PowerPC (рис.8).

Рис. 8. Совместимость с GCC

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

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

Рис. 9. Иерархия блоков оптимизирующей компиляции

В п.4.3 рассмотрены алгоритмические основы построения анализатора программ.

Форма статического единственного присваивания (Static Single Assignment, SSA) является одной из самых распространенных форм представления потока данных программы и активно используется в большинстве современных оптимизирующих компиляторов. Для множества переменных сложность алгоритма имеет порядок O(E)*B, где B - количество переменных, для которых строится SSA-форма, E - количество дуг графа потока управления. Таким образом, количество переменных существенно влияет на скорость преобразования программы в SSA-форму. В работе предлагается метод, позволяющий уменьшать алгоритмическую сложность алгоритмов построения -функций, которые представляют собой вспомогательные элементы промежуточного представления и построение которых составляет основную алгоритмическую сложность перевода программы в статическую форму единственного присваивания. В новой оценке величина B заменяется на величину B/size(word), где size(word) - размер минимального элемента реализации пакета битовых векторов (в нашей реализации size(word)=32).

Предложена новая структура данных (дерево значений), позволяющая объединить в единое целое информацию о потоке данных и доминировании. Приведен алгоритм построения дерева значений. Алгоритм обладает алгоритмической сложностью O(M1+M2*N), где M1 - число операций и φ-узлов SSA-формы, M2 - число операций промежуточного представления программы, N - число линейных участков в управляющем графе. Результаты тестирования показали, что дерево значений имеет хорошие характеристики по объему занимаемой памяти и подходит для использования в промышленных компиляторах. Далее показывается, как использование дерева значений позволяет эффективно проводить ряд оптимизирующих преобразований программы, таких как глобальное распространение копий (Global Copy Propagation, далее GCP), удаление излишних чтений (Redundant Loads Elimination, далее RLE), удаление мертвого кода (Dead Code Elimination, далее DCE) и удаление излишних записей (Redundant Stores Elimination, далее RSE). Для этих оптимизаций использование дерева значений позволяет упростить их реализацию, увеличив при этом эффект от применения и регион применения как минимум некоторых из них.

В п.4.3.3.2 предлагается алгоритм перевода потока управления программы в поток данных, в основе которого лежит метод построения предикатов для ациклических регионов управляющего графа, обеспечивающий возможность распараллеливания условных операций, а также требующий меньшее количество дополнительных операций при вычислении предикатов. В основе метода лежит предикатная форма единственного присваивания представления потока данных программы (Gated Single Assignment, GSA). В работе описывается GSA-формa и приводится алгоритм ее построения. Показывается, как на основе GSA-формы можно построить предикатное выражение, которое описывает предикатный путь любого узла ациклического участка программы относительно произвольного предшественника этого узла из того же ациклического участка. В работе описываются способ реализации предикатных выражений, который был использован в оптимизирующем компиляторе проекта УЭльбрусФ, а также способ хеширования предикатных выражений, позволяющие избегать дублирования при их построении. Предложенный метод построения предикатов имеет ключевое значении для эффективной работы алгоритмов глобального планирования, рассматриваемых далее в данной работе.

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

Метод, расширяющий применимость этого вида анализа на случай произвольного региона, позволяет включить в рассмотрение поток данных, входящих в регион через φ-узлы. На рис. 10 представлен пример, в котором на основе анализа предикатов удаётся определить, что операция условной записи в переменную а (store a, v [p0]) доминирует над операцией use r0 [p4], которая использует результат операции чтения из переменной a (load a а r0), следовательно, оптимизация удаления избыточных чтений применима.

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

В п.4.3.4 рассматриваются вопросы, связанные с решением проблемы статического анализа зависимостей в цикле. Предложена методология проведения такого анализа от фазы нахождения гнезд циклов до запуска решателя систем диофантовых уравнений и неравенств. В работе удалось снять практически все ограничения на постановку задачи индексного анализа программ, что позволило существенно расширить область применения данного вида анализа и имело решающее значение при разработке автоматического распараллеливателя для многоядерных архитектур и для распараллеливания на уровне системы команд, особенно в циклах, где применима аппаратная поддержка наложения итераций. Был предложен оригинальный интерфейс решателя систем диофантовых уравнений и неравенств, позволивший снять многие ограничения на применимость анализа зависимостей в циклах. Введено понятие минимального вектора расстояния зависимости и предложен метод его вычисления. Предложен механизм сохранения информации о длинах измерений многомерных массивов, позволяющий проводить анализ зависимостей в циклах после всех преобразований на графе управления практически без потерь в точности получаемых результатов. Разработана реализация решателя систем диофантовых неравенств на основе Симплекс-метода. Показано, что симплекс-метод имеет преимущество перед методом Фурье по скорости работы на задачах, работающих с многомерными массивами.

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

Ключевыми параметрами в постановке задачи межпроцедурного анализа являются:

- множество объектов программы, для которых проводится анализ;

- степень детализации результатов анализа.

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

За основу решения данной проблемы в работе был взят известный подход, основанный на использовании частичных трансферных функций (ЧТФ) (Robert P.Wilson, Monika S.Lam. Efficient context-sensitive pointer analysis for C programs. In Proccedings of the ACM SIGPLANТ95 Conference on Programming Language and Implementation, pages 1-12, June 1995.).

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

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

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

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

В п.4.4 рассмотрена проблема последовательности применения оптимизаций и их группировки.

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

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

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

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

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

Автоматический распараллеливатель (АР), представляемый в данной работе, реализован на базе двух технологий компиляции - технологической цепочки GCC и компонентной технологии оптимизирующей трансляции (КТОТ). Коллекция компиляторов GСС позволяет транслировать приложения со всех популярных языков программирования, таких как С, С++, Fortran, в код наиболее известных целевых платформ, таких как x86, Power Cell, Sparc и т.п. Компонентная технология оптимизирующей трансляции содержит в себе методы статического анализа программ, оптимизирующие преобразования и алгоритмы распараллеливания. Технология портирования, на базе которой реализована библиотека компонент, позволяет использовать все компоненты совместно с любой технологической компиляторной цепочкой, в том числе и с GCC.

Таким образом, используя технологию GCC для трансляции программ с языков высокого уровня в языки целевых архитектур, и технологию КТОТ для статического анализа программ, выявления параллельности и оптимизаций программ, был реализован АР.

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

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

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

Результаты экспериментов

В работе приведены результаты сравнения производительности базовых компиляторов для платформ x86, IA64 и PowerPC компаний Intel и IBM с производительностью для этих платформ, полученной с помощью АР. Замеры проводились для подмножества задач из пакетов Spec2006 и NAS Parallel Benchmarks

Ощутимый прирост производительности от применения АР зафиксирован как на задачах пакета Spec2006, так и на задачах NPB. В среднем, автоматический распараллеливатель (utlcc) дает больший прирост производительности по отношению к исходному уровню gcc, чем функциональность автоматического распараллеливания базовых компиляторов компаний Intel и IBM (reference) по отношению к их исходному уровню (без распараллеливания).

Ниже (рис. 11 и 12) приведены сравнительные характеристики АР (utlcc) и автоматического распараллеливания от базовых компиляторов компаний Intel и IBM (reference). Для получения сравниваемых значений время исполнения задачи, скомпилированной без распараллеливания, делится на время исполнения распараллеленной версии. Затем эти отношений усреднялись по каждому из пакетов (по 6 задачам из каждого). Результат выражается в процентах. В скобках указано количество ядер на аппаратных системах, для которых производилось сравнение (<архитектура> (х<количество ядер>)).

Spec2006

Рис. 11. Интегральные результаты по производительности (Spec2006)

NAS Parallel Benchmarks

Рис. 12. Интегральные результаты по производительности (NAS)

Как видно из приведенных на рис.11 и рис.12 диаграмм, авто-распараллеливатель, созданный на основе компонентного подхода, распараллеливает более эффективно, чем авто-распараллеливатели базовых компиляторов компаний Intel и IBM.

Компилятор общего назначения для архитектуры Эльбрус-3М позволил вычислительному комплексу, построенному на базе этой архитектуры, реализовать заложенный в него потенциал и достичь требований производительности, которые поставил перед разработчиками заказчик и которые были подтверждены государственными испытаниями вычислительного комплекса Эльбрус-3М в 2007 году.

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

Выводы по результатам диссертации

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

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

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

Статический анализ программ

Предложен алгоритм группового (для множества переменных) построения формы статического единственного присваивания, позволяющий существенно ускорить построение формы единственного статического присваивания.
Предложена новая структура данных (дерево значений), позволяющая объединить в единое целое информацию о потоке данных и доминировании, и показано, как на ее основе применяется широкий класс преобразований потока данных.
Предложен оригинальный алгоритм перевода программы в предикатную форму, основанный на использовании предикатной формы статического единственного присваивания. Это позволило существенно уменьшить накладные расходы при проведении этого преобразования.
Предложен алгоритм, расширяющий применимость анализа предикатов для программ, в который поток управления переведен в поток данных с использованием предикатных операций. Этот метод позволяет включить в рассмотрение поток данных, входящих в регион через φ-узлы.
Показано, как на основе расширенного анализа предикатов можно улучшить эффективность многих преобразований на предикатном коде, и предложены новые преобразования, основанные на использовании результатов такого анализа.
Предложен оригинальный интерфейс решателя систем диофантовых уравнений и неравенств, позволивший снять многие ограничения на применимость анализа зависимостей в циклах.
Введено понятие минимального вектора расстояния зависимости и предложен метод его вычисления.
Предложен механизм сохранения информации о длинах измерений многомерных массивов, позволяющий проводить анализ зависимостей в циклах после всех преобразований на графе управления практически без потерь в точности получаемых результатов.
Разработана реализация решателя систем диофантовых неравенств на основе симплекс-метода. Показано, что симплекс-метод имеет преимущество перед методом Фурье по скорости работы на задачах, работающих с многомерными массивами.
Предложен единый подход к решению задачи межпроцедурного анализа потока данных на основе механизма частичных трансферных функций, позволяющий существенно расширить область применения анализа с высокой степенью детализации результатов.
Показано, как с помощью предложенного подхода решаются задачи межпроцедурного распространения указателей, констант, выравниваний объектов, диапазонов значений переменных.
Предложен алгоритм решения задачи межпроцедурной нумерации значений.

Глобальное планирование программ

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

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

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

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

Все представленные в диссертационной работе алгоритмы и методы, реализованы в составе оптимизирующего компилятора с языков высокого уровня С, С++, F77 для архитектуры Эльбрус-3М и составляют основу оптимизирующей части этого компилятора. На основе предложенной блочной технологии построения оптимизирующих компиляторов были созданы анализатор программ и автоматический распараллеливатель программ для архитектур x86 (Intel, AMD), Itanium (Intel), Power PC, Power Cell. Автоматические распараллеливатели были построены на основе совместного использования компонентной технологии построения оптимизирующих компиляторов и технологии GCC.

Список работ, опубликованных по теме диссертации

Дроздов А.Ю. Компонентный подход к построению оптимизирующих компиляторов. // Программирование. 2009. № 5, с. 70-80
Дроздов А.Ю., Особенности и перспективы Универсальной технологии оптимизирующей компиляции. // Сборник научных трудов ИТМиВТ им. С.А. Лебедева РАН, Выпуск №1, Материалы Всероссийской конференции Перспективы развития высокопроизводительных архитектур. История, современность и будущее отечественного компьютеростроения, 2008, С. 62-74.
А.Ю. Дроздов, С.В. Новиков. Авто-распараллеливатель программ, реализованный на основе компонентной технологии построения оптимизирующих компиляторов. // Программирование. 2009. № 6, с. 1-24.
Дроздов А. Ю., Кирнасов А.Е. Анализ предикатных выражений и его использование в оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом // Информационные технологии, № 7, 2005 г., с. 40-45.
Дроздов А.Ю., Новиков С.В. Эффективный алгоритм построения формы статического единственного присваивания // Информационные технологии, № 3, 2005 г.
Дроздов А.Ю, Владиславлев В.Е. Межпроцедурный анализ указателей // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 2-13.
Дроздов А. Ю., Сыркин А. Г. Методы контекстного межпроцедурного распространения свойств значений переменных программы // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 14-18.
Дроздов А. Ю., Тютюник О. М., Шилов В.В. Эффективная реализация графа потока зависимостей // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 19-23.
Дроздов А. Ю., Новиков С. В., Шилов В.В. Эффективный алгоритм преобразования потока управления в поток данных // Информационные технологии, Приложение № 2, Февраль 2005 г., с. 23-31.
Дроздов А.Ю, Боханко А.С. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании // Информационные технологии, № 12, 2004 г.
Дроздов А. Ю., Корнев Р.М., Боханко А.С. Индексный анализ зависимостей по данным // Информационные технологии и вычислительные системы, № 3, 2004г., с. 27-37.
Дроздов А. Ю., Степаненков А. М. Управляемые пакеты оптимизаций // Информационные технологии и вычислительные системы, № 3, 2004г., с. 93-101.
Дроздов А. Ю., Степаненков А. М. Технология оптимизации циклов для архитектур с аппаратной поддержкой конвейеризации циклов // Информационные технологии и вычислительные системы, № 3, 2004г., с. 52-62.
Волконский В.Ю., Дроздов А.Ю., Ровинский Е.В. Метод использования мелкоформатных векторных операций в оптимизирующем компиляторе // Информационные технологии и вычислительные системы, № 3, 2004г.. с. 63-77.
Дроздов А. Ю., Кан А.В. Анализ межпроцедурная нумерация значений. // Компьютеры в учебном процессе, № 6, 2005 г.
Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б., Def-Use граф и методы его использования в современных оптимизирующих компиляторах. // Компьютеры в учебном процессе. № 12. 2005. C. 3-14.
Дроздов А.Ю., Новиков С.В. Исследование методов преобразования программы в предикатную форму для архитектур с явно выраженной параллельностью. // Компьютеры в учебном процессе, № 5, 2005 г.
Дроздов А.Ю., Перекатов В.И., Шлыков С.Л. Задача планирования операций по кластерам для архитектур с разделением исполнительных устройств на кластеры // Компьютеры в учебном процессе, № 3, 2005 г.
Дроздов А.Ю., Кирнасов А.Е., Перекатов В.И. Использование результатов анализа предикатных выражений для эффективного применения оптимизирующих преобразований программ // Компьютеры в учебном процессе, № 3, 2005 г.
Дроздов А.Ю., Степаненков А.М. Методы комбинирования алгоритмов анализа и оптимизаций в современных оптимизирующих компиляторах // Компьютеры в учебном процессе, № 11, 2004 г.
Дроздов А.Ю., Степаненков А.М. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10, 2004 г.
Дроздов А.Ю., Ровинский Е.В. Технология использования векторных операций для получения оптимального кода // Компьютеры в учебном процессе, № 9, 2004 г.
Боханко А.С., Дроздов А.Ю., Корнев Р.М. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004 г.
Дроздов А. Ю., Новиков С. В., Боханко А. С., Галазин А. Б., Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ. // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005
Боханко А. С., Дроздов А. Ю., Новиков С. В., Шлыков С. Л., Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур. // Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выпуск N8, 2005.
Дроздов А.Ю., Новиков С.В. Улучшение алгоритмов построения формы статического единственного присваивания // IХ Санкт-Петербургская Международная конференция Региональная Информатика-2004 РИ-2004 Санкт-Петербург, 22-24 июня 2004 года.
Дроздов А.Ю., Владиславлев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IХ Санкт-Петербургская Международная конференция Региональная Информатика-2004 РИ-2004 Санкт-Петербург, 22-24 июня 2004 года.
Боханко А.С., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IХ Санкт-Петербургская Международная конференция Региональная Информатика-2004 РИ-2004 Санкт-Петербург, 22-24 июня 2004 года.
Боханко А.С., Дроздов А.Ю. Оптимизация Расширенное удаление излишних операций чтения из памяти // В трудах Международной молодежной научной конференции XXX Гагаринские чтения, Москва, 2004.
Б. А. Бабаян А. К. Ким, Ю. Х. Сахин, А. Ю. Дроздов и др. ИМВС РАН Научно-технический отчет по НИР Поисковые исследования и разработка архитектурных и логических принципов построения универсальных вычислительных систем Эльбрус-4 с производительностью пентафлопового диапазона. Разработка принципов построения однокристального мультипроцессора. Глава 3: Исследование зависимостей по данным и управлению в алгоритмах задач. Москва 2003г.
Б. А. Бабаян , А. К. Ким, Ю. Х. Сахин, А. Ю. Дроздов и др. Российская академия наук. Институт микропроцессорных вычислительных систем (ИМВС). Отчет о научно-исследовательской работе. Программа фундаментальных научных исследований ОИТВС РАН "Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий". Направление № 2 "Высокопараллельная, масштабируемая кластерная архитектура, приспосабливаемая под конкретные приложения". Раздел 9: Особенности генерации кода для архитектур с разделением исполнительных устройств на кластеры. Москва 2003.
Дроздов А.Ю., Степаненков А.М. Методы глобального планирования программ, предлагаемые для использования в современных оптимизирующих компиляторах для архитектур с явно выраженным параллелизмом. "Сборник тезисов XXI научно-технической конфренции войсковой части 03425"
Москва, в/ч 03425, 2003г.
Дроздов А.Ю., Новиков С.В. Методы совместного планирования путей программы, предлагаемые для использования в современных оптимизирующих компилятора. "Сборник тезисов XXI научно-технической конфренции войсковой части 03425" Москва, в/ч 03425, 2003г.
Дроздов А.Ю. Методы анализа программ, предлагаемые для использования в современных оптимизирующих компиляторах. "Сборник тезисов XXI научно-технической конференции войсковой части 03425",
Москва, в/ч 03425, 2003г.
A. Drozdov, I. Moukhin, A. Kasinsky, S. Okunev, A. Ostanevich, Y. Rumyantsev, A. Sushentsov, V. Tikhonov, V. Volkonski, K. Yaremenko. The optimizing compiler for the Elbrus-3 supercomputer // In Proceedings of the "International Congress on Computer Systems and Applied Mathematics ( CSAM'93 )", Abstracts. - St. Petersburg, July 19-23, 1993. - P. 127-128.
В. Ю. Волконский, А. Ю. Дроздов, А. И. Касинский, И. А. Мухин, С. К. Окунев, А. Ю. Останевич, А. Л. Сушенцов и др. Оптимизирующая транслирующая система для МВК "Эльбрус-3" // В трудах международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованияхФ, Тезисы. - Алма-Ата, сентябрь 1991 г. - С. 70.