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

Размещено на http://www.allbest.ru/

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

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. компилятор оптимизирующий алгоритмический затраты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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