ПРОГРАММИРОВАНИЕ, 2014, No 3, с. 30-43
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ -
УДК 681.3.06
АВТО-РАСПАРАЛЛЕЛИВАТЕЛЬ И ВЕКТОРИЗАТОР
ПРОГРАММ, РЕАЛИЗОВАННЫЙ НА ОСНОВЕ УНИВЕРСАЛЬНОЙ БИБЛИОТЕКИ ТРАНСЛЯЦИИ И
ТЕХНОЛОГИИ LLVM
© 2014 г. А.Ю. Дроздов, C.B. Новиков, В.Е. Владиславлев, E.J1. Кочетков,
П.В. Ильин
Московский физико-технический институт 141700 г. Долгопрудный, Институтский пер., 9 E-mail: alexander. у. drozdov@gmail. com Поступила в редакцию 27.09.2013
Работа посвящена интеграции компилятора на основе библиотеки LLVM и инструментария, созданного с использованием Универсальной Библиотеки Трансляции (УБТ) - авто-распараллеливателя и векторизатора. Проведен сравнительный анализ промежуточных представлений, используемых в интегрируемых библиотеках. Приведено описание механизмов, которые потребовалось реализовать для интеграции. Также описаны наиболее важные компоненты УБТ. Наконец, были выполнены сравнительные замеры производительности системы трансляции, которая получилась в результате этой интеграции, и существующих компиляторов. Замеры производились на многоядерных системах на основе архитектур ARM и х86 на ряде задачах из пакетов SPEC/CPU2006 и NAS Parallel Benchmarks.
1. ВВЕДЕНИЕ
Разработка компилятора, как правило, связана с созданием новой архитектуры микропроцессора. Новые архитектуры продолжают появляться, и чем дальше, тем сложнее они становятся. Здесь можно вспомнить и гетерогенные системы, и мультиядерность, и графические вычислители. Для отработки новых архитектурных черт и эффективной настройки имеющихся разработчикам аппаратуры необходима обратная связь от разработчиков системного ПО. Поэтому создание железа и софта - процессы параллельные и взаимовлияющие.
Сегодня усилия микропроцессорной индустрии направлены, в частности, на то, чтобы сократить время разработки новых аппаратных решений. Уже сейчас большинство компаний на рынке относятся к так называемым ГагЫевв компаниям, то есть не имеющим собственных фабрик для изготовления финальных решений. Даже компании, имевшие фабрики,
зачастую стараются избавиться он них, чтобы сосредоточиться именно на разработке нового железа. Так, например, сделала компания AMD. Следующей ступенью абстракции является так называемая chipless модель, при которой компания не только не производит финальной продукции, но и в разработке сосредотачивается лишь на проектировании определенной компоненты, скажем, вычислительного ядра, оставляя все прочее сторонним компаниям. Таким образом, сейчас процесс создания нового железа представляет собой конвейер.
Другим примером акселератора для разработки процессоров может служить инициатива компании IBM по созданию облачного сервиса для предоставления САПР как услуги. Причем, предлагаются как собственные решения, так и решения основных независимых производителей - Cadence, Synopsvs и Mentor Graphics.
Успевает ли за этими процессами компиля-торостроение? Оптимизирующий компилятор, с одной стороны, остается, пожалуй, одним из са-
мых сложных и наукоемких программных продуктов, разработка, отладка и тюнинг которого - процесс длительный, а жизненный цикл измеряется десятилетиями. С другой стороны, все оптимизирующие компиляторы похожи друг на друга - три четверти их кода реализуют идентичную, или, во всяком случае, весьма близкую функциональность. Но какие-то особенности того внутреннего языка, на котором в компиляторе выражена семантика транслируемой программы, заставляет разработчиков каждый раз заново создавать весь тот сложный и специфический инструментарий, который необходим в компиля-торостроении.
Современному компиляторостоению, как и процессу создания новых аппаратных решений, присуща определенная модульность. Например, создатель компилятора для новой архитектуры не занимается написанием компилятора переднего плана, а берет готовое решение - коммерческое или открытое. Для создания кодогенератора на новую архитектуру также достаточно лишь специфицировать ее ассемблер, например, на специальном языке описания, как в GNU [1], или же реализовав ограниченный набор несложных С++ классов, как в LLVM [2], и кодогенератор готов. То есть задачу быстрого получения технологической цепочки трансляции можно считать решенной. Но если просто компилятора недостаточно, и стоит задача в сжатые сроки получить компилятор, порождающий эффективный код для данной архитектуры, имеющихся решений недостаточно. Для этих целей была разработана Универсальная Библиотека Трансляции (УБТ) [3]. В одной из предыдущих работ была описана интеграция УБТ с системой трансляции на основе технологии GNU [4]. Данная же работа посвящена интеграции УБТ с компилятором, созданным на основе технологии LLVM. В работе также описываются ключевые алгоритмы оптимизаций, добавленные в LLVM из библиотеки УБТ. К ним относятся алгоритмы распараллеливания и векторизации. Кроме того, к рассмотренным ранее архитекторам добавилась столь популярная сегодня архитектура ARM. В конце работы дается сравнение производительности созданного компилятора и существующих на рынке решений.
2. БИБЛИОТЕКА УБТ
В рамках создания УБТ были разработаны технологии и алгоритмы, оформленные в виде блоков оптимизирующей компиляции, которые позволяют как улучшать существующие компиляторы, так и создавать новые. Эти блоки используют информацию об окружении, хранящуюся в Базе Данных Программы (БДИ). БДП содержит информацию о семантике программы, символьные таблицы, типы, размерности и прочую информацию, которая существует в языках высокого уровня. Кроме того, БДП содержит описание целевой архитектуры. Блоки трансляции естественным образом разбиты на классы, образующие иерархическую структуру: каждый следующий уровень иерархии использует результаты уровня предыдущего. Базовый уровень составляют инструментальные блоки, они, в свою очередь, используются блоками моделей, модели используются алгоритмами анализа, а результаты анализа применяются для оптимизаций, требуемых для данной архитектуры и/или данного компилятора. Именно параметризация оптимизирующего компилятора при помощи БДП позволяет переносить создаваемые решения в любые технологические цепочки - как новые, так и уже существующие.
Все алгоритмы анализа и оптимизаций пишутся с использованием конкретных особенностей того или иного Промежуточного Представления (ПП), с помощью которого выражена семантика программы в конкретной цепочке трансляции, что делает алгоритмы непереносимыми в другую среду. Для достижения желаемого уровня портируемости, необходимо абстрагировать реализацию блоков трансляции от конкретного ПП. Для этого в УБТ была реализована концепция разделения промежуточного представления на две составляющие части - семантическую и аналитическую. Семантическая часть содержит в себе информацию о языке и архитектуре. В аналитическую часть в абстрактном виде вынесена информация об операциях и аргументах операций.
3. ТЕХНОЛОГИЯ 1.1ДМ И АСПЕКТЫ ЕЕ ИСПОЛЬЗОВАНИЯ
Изначально 1ЛЛА1 стартовал в 2000 году как
Таблица 1. Соответствие классов промежуточных представлений LLVM и УБТ
Название сущности Классы LLVM IR Классы ANLS IR
Модуль программы Module World
Глобальная переменная GlobalVariable Location
Функция программы Function Routine
Аргумент функции Argument Location
Список инструкций ПИ iplist<BasicBlock> Reptn
Результат функции Returnlnst Location
Инструкция ПП Instruction Statement -собственно операция
AccessDef - вырабатывает результат
Location - переменная для результата
Аргумент инструкции Use AccessUseValue
Константы Constant Literal
университетский проект в Иллинойсе, Урбана-Шампейн. Теперь LLVM используют такие гиганты индустрии, как Adobe, Apple и Google. На LLVM, в частности, основана подсистема OpenGL в MacOSX 10.5.
В основе LLVM лежит промежуточное представление кода, над которым можно производить трансформации во время компиляции, компоновки и выполнения. Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически - Just-In-Time компиляция. LLVM версии 3.1 поддерживает статическую генерацию кода для таких архитектур, как х86, х64, ARM, PowerPC, SPARC, MIPS, Qualcomm Hexagon. Генерация машинного кода во время исполнения поддержана для архитектур х86, х64, PowerPC, MIPS и, частично, для ARM - без расширений NEON и Thumb.
LLVM написан на С++ и портирован на большинство nix-систем и Windows. Система имеет модульную структуру, отдельные ее модули могут быть встроены в различные программные комплексы, она может расширяться дополнительными алгоритмами трансформации, а также кодогенераторами для новых аппаратных платформ.
Используя различные компиляторы переднего плана, в том числе сторонние, LLVM позволяет компилировать программы, написанные на языках С, С++, Objective-C, FORTRAN, Ada, Haskell, Java, Python, Ruby, JavaScript, GLSL. В рамках проекта LLVM был разработан компи-
лятор переднего плана Clang для языков С и С++. Существует множество программ, использующих данную инфраструктуру, в частности, Glasgow Haskell Compiler.
В рамках данной работы использовался сценарий трансляции, включающий в себя компилятор переднего плана Clang, а также компилятор переднего плана GCC 4.6 для языка FORTRAN. Интеграция LLVM и GCC выполнена в рамках проекта DragonEgg и представляет собой LLVM-плагин для GCC.
В качестве целевых архитектур в этой работе рассматриваются х86 и ARM. Как и GCC, технология LLVM позволяет транслировать программу как в помодульном режиме, так и в режиме, допускающем межмодульные оптимизации на этапе линковки - Link Time Optimization (LTO). В режиме LTO на этапе трансляции происходит построение промежуточного представления, незначительная его обработка и сохранение в объектные файлы. Блок оптимизаций запускается на этапе компоновки, который начинается с загрузки промежуточного представления в память и его линковки, что позволяет полностью стереть межмодульные границы.
4. ИНТЕГРАЦИЯ УБТ И LLVM
Целью данной работы является использование алгоритмов анализа и оптимизаций УБТ в контексте двух современных технологий трансляции - GCC и LLVM, без каких-либ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.