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