Оптимизирующие компиляторы

Основным продуктом таких компаний, как Intel, AMD, MIPS являются процессоры, быстродействие которых, однако, связано не только с аппаратной архитектурой, но и с введением новых команд и технологиями вычислений. Например, в течение короткого промежутка времени произошло бурное развитие процессоров семейства IA32 в области векторных и мультемедийных расширений — от MMX к SSE, SSE2, SSE3, SSE4 к AVX, и это развитие будет продолжаться. Однако без компилятора, преобразующего скалярные вычисления пользовательской программы в векторные, нельзя продемонстрировать мощь новой технологии – новые версии компилятора выпускаются практически каждый год, что позволяет поддержать выпуск новых процессоров.

Компилятор Intel учитывает все особенности архитектур выпускаемых компанией процессоров, что обычно обеспечивает достижение высокой производительности приложений. Новые версии компилятора появляются практически каждый год, и это позволяет оперативно поддержать выпуск новых вычислительных систем. Компания также предлагает свой компилятор в качестве дополнительной возможности к уже имеющимся у пользователей компиляторам Microsoft Visual Studio для Windows, gcc для Linux и для Mac OS, гарантируя совместимость с ними на уровне объектных файлов. Фактически это означает возможность компиляции наиболее критических к производительности исходных файлов, а затем сборки их в приложение вместе с файлами, откомпилированными MVS или gcc. Компилятор Intel интегрируется в Microsoft Visual Studio, что позволяет выбрать его в качестве основного и получить улучшение производительности на 10-15% для платформы х86. Кроме того, библиотеки MKL и IPP содержат математические функции и примитивы, демонстрирующие лучшую производительность на различных вычислительных платформах Intel.

Существует несколько характеристик кода программы, оказывающих влияние на производительность приложения, и соответственно имеются методы, которые применяются внутри компилятора для достижения того или иного свойства приложения. Многие методы можно применять и вручную, а знание различных оптимизационных техник и ключей компилятора помогает управлять компилятором. Поскольку оценить последствия оптимизаций при компиляции иногда достаточно сложно, то могут возникать ситуации, когда оптимизация только ухудшает производительность. Компания Intel выпускает инструменты для анализа производительности приложения, такие как VTune Amplifier, используя которые, анализируя и модифицируя «горячий» код, экспериментируя с различными директивами и ключами компиляции, можно иногда достигать удивительных результатов.

Первая характеристика — эффективность вычислений: эффективное переиспользование полученных ранее результатов вычислений, выполнение максимального количества вычислений во время компиляции, эффективное удаление «мертвого» кода, вынос инвариантов из циклов и другие оптимизации, обычно называемые скалярными и требующие для своего выполнения аккуратного анализа потоков данных (просчета того, какие свойства тот или иной объект может иметь в различных местах его использования в зависимости от его определений и графа потока управления). Наиболее известными оптимизациями такого класса является протяжка констант (подстановка в выражение величин известных констант), протяжка копий, удаление общих подвыражений и т. п., приводящих к тому, что вычисления могут выполняться при создании приложения, а не во время его работы. Эффективность такого анализа увеличивается при использовании двухпроходной компиляции (межпроцедурного анализа). В этом случае анализ потока данных становится глобальным — анализируется перенос свойств объектов не только на уровне конкретной обрабатываемой компилятором процедуры, но и внутри графа вызовов. Изучаются и протягиваются внутрь процедуры свойства конкретных аргументов, с которыми эта процедура вызывалась из разных мест приложения, изучаются свойства глобальных объектов, для каждой функции создается список объектов, которые могут быть использованы или модифицированы внутри этой функции, и т. д.

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

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

Рис. 1. Примерная схема векторизации цикла

Все современные процессоры, как правило, многопроцессорные и многоядерные, поэтому умение задействовать для вычислений все доступные ресурсы – еще одна важная задача для оптимизирующего компилятора. Компилятор Intel предлагает разработчикам использовать автопараллелизацию – механизм автоматического распараллеливания циклов. Это, по сути, самый дешевый в плане затрат труда способ создать многопоточное приложение – запустить построение приложения со специальной опцией. Но с точки зрения оптимизируещего компилятора это непростая задача. Необходимо доказать допустимость оптимизации, необходимо правильно оценить объем работы, выполняемой внутри цикла, чтобы решение о параллелизации улучшило производительность. Автоматическая параллелизация активно взаимодействует с другими цикловыми оптимизациями, изменяя порядок и эвристические механизмы принятия решений по оптимизации. В этой области наилучшие оптимизационные алгоритмы еще не написаны, и простор для экспериментов и новаторских идей по прежнему велик. Для развития более наглядных для программистов методов параллелизации создаются новые языковые расширения и различные библиотеки поддержки, такие как CILK+ или Threading Building Blocks. На рис. 2 приведена схема автоматической параллелизации цикла.

Рис. 2. Примерная схема реализации автоматической параллелизации цикла

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

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

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

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

Рис. 3. Примерный порядок выполнения оптимизаций при однопроходной и двухпроходной схеме компиляции

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

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

***

За рамками статьи остались вопросы реализации языковых расширений в Си/C++ и Фортран, поддержки различных операционных систем и вычислительных архитектур, а также поддержки и накопления тестовой базы, поиска и правки ошибок, интеграции со средами разработки, такими как Microsoft Visual Studio. В области разработки компиляторов, создания базовых оптимизационных алгоритмов и архитектуры компилятора идет динамичное развитие, направленное на достижение нового качества производимых программных продуктов.

Андрей Ануфриенко (andrei.v.anufrienko@intel.com) — ведущий инженер-программист компании Intel (Новосибирск).