Компиляция программ для современных архитектур

А. Белеванцев, Д. Журихин, Д. Мельник
Труды Института системного программирования РАН

Назад Содержание Вперёд

3. Оптимизации энергопотребления встраиваемых систем, управляемые компилятором

Исследования по оптимизации энергопотребления встраиваемых систем активно ведутся в последнее десятилетие. Из наиболее популярных направлений можно отметить динамическое изменение напряжения на процессоре и его частоты; оптимизации доступа к памяти, в том числе отключение неактивных банков памяти; оптимизацию энергопотребления на стадии разработки новых чипов и т.д. (хорошие обзоры можно найти в работах [5, 5]). В данном разделе рассматриваются программные оптимизации энергопотребления, управляемые компилятором. Мы исследовали несколько направлений таких оптимизаций с использованием компилятора GCC для архитектуры ARM: динамическое изменение напряжения, основанное на данных профиля программы; влияние оптимизаций работы с памятью на энергопотребление; оптимизацию переключения битов на шине команд через модификации планировщика команд. Тестирование оптимизаций проводилось с помощью пакетов Aburto [5], MediaBench [5] и MiBench [5] на платах OMAP2430 [5] и MV320 [5], содержащие процессоры ARM 11-го поколения. Рассматриваемые тестовые пакеты состоят из небольших приложений, представляющих из себя обработку изображений и звука, а также другие вычисления, типичные для встраиваемых систем.

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

3.1. Динамическое изменение напряжения

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

Существует несколько классов алгоритмов ДИН, известные в литературе как статические (offline), динамические (online) и смешанные (mixed). Разница между этими классами заключается в моменте, в который принимается решение, во-первых, о местонахождении точек управления напряжением, и во-вторых, о величине, на которую изменяется напряжение. Динамические алгоритмы ДИН принимают все эти решения во время работы программы (например, в планировщике ОС); статические алгоритмы определяют как точки, так и величины изменения напряжения во время компиляции (хотя непосредственно изменение напряжения также происходит во время работы программы); наконец, смешанные алгоритмы обычно вычисляют возможные точки изменения напряжения во время компиляции, а величина изменения определяется динамически.

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

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

3.1.1. Реализованный алгоритм ДИН

Алгоритм обрабатывает т.н. базовые и комбинированные регионы. Базовым регионом является либо базовый блок, либо гнездо циклов. Комбинированный регион – это объединение базовых регионов, имеющее один вход и один выход, при этом вход доминирует, а выход постдоминирует регион. Это определение предоставляет больше возможностей по созданию регионов, чем поиск по набору шаблонов графа потока управления, как предлагается в [5]. Тем не менее, существует ряд дополнительных ограничений на регионы. Во-первых, в первоначальной реализации не рассматривались регионы, содержащие вызовы функций, так как алгоритм был внутрипроцедурным (в текущей реализации это ограничение снято). Во-вторых, регионы с «нетипичным» потоком управления (например, несколько дуг пересекают границы цикла) не обрабатываются. В-третьих, небольшие регионы также исключаются из рассмотрения, так как затраты на переключение напряжения наверняка превысят возможный выигрыш на таком регионе.

Алгоритм состоит из следующих основных шагов:

• Построение базовых и комбинированных регионов для данной функции.
• Профилирование времени выполнения, T(R,v), и количества раз, N(R), которое выполнился регион, для каждого базового региона на каждом доступном уровне напряжения.
• Вычисление этих величин для комбинированных регионов. Время выполнения считается как сумма времен по всем базовым регионам, составляющим данный комбинированный регион; количество выполнений берется из базового региона, находящегося на входе в комбинированный.
• Поиск такого региона, на котором понижение напряжения минимизирует энергопотребление системы во время выполнения программы, а сама программа замедляется не больше, чем на p%. Потребленная энергия оценивается по времени работы региона на данном уровне напряжения с учетом затрат на выполнение команд переключения напряжения.
• Вставка команд изменения напряжения в начале и конце выбранного региона.

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

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

Тестирование реализации проводилось на пакете тестов Aburto и тестовой плате MV320. Из пакета предварительно было удалены тесты, калибрующиеся автоматически, так как они выполняют разный объем вычислений на разных частотах. В качестве базового использовался уровень оптимизации -O2.

Из 196 функций, содержащихся в программах пакета Aburto, наша реализация алгоритма нашла 144 функции, которые подходят для динамического изменения напряжения. Для значения параметра p допустимого замедления программы от 10% до 40% было найдено от 3 до 14 подходящих регионов соответственно. При запуске оптимизированной версии время работы составило 8 минут, а потребленная энергия – 750 мВч. Неоптимизированные программы работали 7 минут 30 секунд, требуя 720 мВч. При этом потребление незагруженной системы составило 59 мВч за 45 секунд. Вычитая это потребление из обоих результатов, получаем, что при замедлении системы на 6.6% сокращение потребления энергии только процессором составило 7%. Если же принять за ограничение времени работы системы 8 минут, то за это время неоптимизированные версии программ потребили бы 759.3 мВч, что соответствует сокращению потребления оптимизированной версией на 1.24%.

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

3.1.2. Оптимизация переключения битов (bit-switching)

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

Мы исследовали вопрос о том, можно ли минимизировать переключения влиянием на порядок команд через планировщик команд компилятора. Во-первых, были выяснена верхняя оценка на количество энергии, которое можно сохранить через минимизацию переключения битов. Были подготовлены тесты, использующие команды с как можно более различающимся кодированием. Так, в битовой кодировке команд ands r6,r8,r0 и bicne r9,r7,#0x3FC только 3 из 32 битов одинаковы. Из двух тестовых программ, первая содержала цикл из 1000 команд: 500 команд первого типа, за которыми следовали 500 команд второго типа; вторая содержала цикл из 500 пар команд первого и второго типа. Оба цикла выполнялись достаточное количество раз для того, чтобы имелась возможность замерить энерго-потребление. Эксперименты с выполнением этих двух тестах показали, что разница в энергопотреблении составляет 1-2% для одной тестовой платы и около 5% для второй платы. Учитывая, что энергопотребление процессора является лишь частью энергопотребления всей системы, можно было утвер-ждать, что экономия в энергопотреблении процессора составила около 10%.

Для минимизации переключения битов в компиляторе необходимо знать, как команда во внутреннем представлении компилятора будет закодирована в битовой форме. В случае компилятора GCC, результатом компиляции является ассемблерный листинг программы, а информации о кодировании команд нет, так как этим занимается ассемблер. Для преодоления этого препятствия мы реализовали машинно-зависимую функцию (т.н. target hook), «предсказывающую» финальную кодировку команды во внутреннем представлении компилятора в той части, в которой это известно компилятору (то есть, за исключением вычисления адресов, неизвестных на этапе компиляции). При сравнении предсказанных кодировок с реально получившимися на ряде тестов обнаружилось практически полное совпадение, за исключением случаев, когда из данной команды во внутреннем представлении можно было сгенерировать несколько вариантов машинной команды, и в итоге был выбран менее вероятный вариант.

С помощью полученной функции была реализована новая эвристика для планировщика команд GCC, которая дает предпочтение командам, образующим меньшее количество переключений битов с предыдущей запланированной командой. Эвристика использует параметр, изменяющийся от 0 до 32, который может рассматриваться как количество одинаковых битов на шине команд, которые увеличивают приоритет этой команды на 1. Так, если параметр установлен в 5, и планировщик выбирает между двумя командами с приоритетами 3 и 4, которые оцениваются как переключающие 7 и 22 бита на шине команд соответственно, то приоритет первой команды составит 3+(32-7)/5=8, а приоритет второй команды – 4+(32-22)/5=6, и будет выбрана первая команда вместо второй.

При тестировании данной эвристики на пакете тестов Aburto максимальное сокращение переключений битов было зафиксировано на тесте sim и составило 7%, а в среднем – около 3%. К сожалению, этого недостаточно, чтобы значительно повлиять на энергопотребление. Возможно, одной из причин было то, что большое количество операций с плавающей точкой, реализованных через библиотечные вызовы, не позволяло достаточно точно предсказать кодирование этих операций. Аналогичные эксперименты с оптимизацией, комбинирующей несколько команд в одну, показали, что переключение битов меняется еще меньше, чем для планирования. Вообще говоря, видно, что для изменения энергопотребления на 1% необходимо изменить количество переключений битов как минимум на порядок больше, чего не получается достигнуть в рамках компилятора.

3.1.3. Оптимизация работы с памятью

Подсистема работы с памятью является одной из самых потребляющих компонентов встраиваемых систем. Мы проанализировали ряд оптимизаций доступа к памяти, имеющихся в компиляторе GCC. Так, префетчинг данных поддерживается для некоторых реализаций процессора ARM через команду pld, и, в частности, поддерживается на тестовой плате OMAP2430. Тестирование реализации префетчинга массивов в циклах в компиляторе GCC версий 4.2 и 4.3 показало, что некоторые тесты ускоряются при использовании префетчинга, а некоторые замедляются – общая картина получается достаточно противоречивой, чтобы не рекомендовать использовать префетчинг по умолчанию для компиляции программ для данной тестовой платы. Другие машинно-независимые оптимизации, улучшающие производительность и, как следствие, уменьшающие энергопотребление, не дают большого эффекта в текущих версиях GCC для архитектуры ARM (автоматическая векторизация, преобразования циклов). Мы предполагаем, что в будущем, с появлением в GCC инфраструктуры Graphite для оптимизации циклов [5], можно будет разрабатывать цикловые оптимизации, имеющие своей целью, в том числе, уменьшение энергопотребления.

Кроме этого, известен ряд машинно-зависимых оптимизаций работы с памятью, направленных исключительно на энергопотребление. Например, скрэтч-память (scratch-pad memory) является по сути дополнительным кэшем, контролируемым компилятором. Использование такой памяти во встраиваемых системах позволяет экономить энергию, если память более эффективна, чем главная память, либо просто ускорять программу. К сожалению, в имеющихся у нас тестовых платах скрэтч-память присутствовала только в OMAP2430, и ее предназначение не позволяло использовать ее для этих целей. Оптимизация, отключающая неиспользуемые банки памяти, также возможна на тестовой плате OMAP2430, однако размер банка памяти в ней достаточно велик, и более разумным представляется распределять банки памяти по процессам в операционной системе вместо контроля распределения памяти компилятором.

4. Динамические оптимизации для языков общего назначения

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

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

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

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

1. Динамическая оптимизация во время работы программы (JIT). Имеет то преимущество, что программа оптимизируется на конкретном наборе входных данных для данного конкретного запуска. Собранная статистика используется только для оптимизации данного запуска. Разные запуски программы могут приводить к различным оптимизациям. Необходим баланс между уровнями оптимизации «холодного» и «горячего» кода.

JIT-оптимизации на языке Java, учитывающие профиль пользователя, подробно исследованы. Максимальный эффект в этом случае дают: оптимизация встраивания функций, развертка циклов, оптимизация обращений к памяти и распределение регистров. Эти оптимизации могут быть применены и в JIT-компиляторе для Си/Си++. Меньшая эффективность от этих оптимизаций из-за необходимости сложного анализа алиасов для Си/Си++ не уменьшает их актуальности.

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

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

1. Динамическая оптимизация во время работы программы, применяемая только к «горячим» участкам кода (аналогично пункту 1 для оптимизаций с учетом профиля).
2. Статическая оптимизация во время установки программы. Для этого требуется лишь распространение программы во внутреннем представлении, компилятор и компоновщик на стороне пользователя, а виртуальная машина и JIT-компилятор не требуются. Этот подход используется при развертывании .NET-программ (оптимизатор NGEN от Microsoft).

В качестве основы для проведения работ мы выбрали систему LLVM (Low Level Virtual Machine) [5] с открытыми исходными кодами на языке Си++, поддерживаемый компанией Apple. Все необходимые компоненты – внутреннее представление достаточно высокого уровня, компоновщик, виртуальная машина, JIT-компилятор – представлены или разрабатываются в рамках проекта LLVM. Из-за модульной организации и высокоуровневого языка реализации LLVM является популярным исследовательским компилятором. В LLVM была предложена концепция “lifelong optimization”, представляющая из себя компоненты для оптимизации программы на всем жизненном цикле ее существования, включая оптимизацию на машине пользователя. Кроме того, LLVM поддерживает межмодульные оптимизации и JIT-компиляцию, но не оптимизацию на стороне пользователя. В компании Apple реализован JIT-компилятор для OpenGL программ с помощью LLVM, позволивший отказаться от специализированного JIT-компилятора, использовавшегося до этого, и значительно улучшить производительность графических операций.

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

• исследование и разработка системы поддержки времени выполнения для LLVM, позволяющей осуществлять динамический мониторинг и профилирование работы программы – необходимо организовать интерпретацию программы во внутреннем представлении LLVM, динамическое малозатратное профилирование программы, сохранение результатов профилирования в промежуточных файлах;
• исследование и разработка динамических оптимизаций, которые применимы к языкам общего назначения C/Си++, а также реализация выбранных оптимизаций c учетом профиля программы в JIT-компиляторе LLVM;
• исследование и разработка подсистемы оптимизации программы во внутреннем представлении LLVM с учетом параметров целевой машины.
• сравнительный анализ возможностей статического компилятора с возможностями JIT-компилятора LLVM с использованием пакета тестов SPEC CPU2006 и на реальных приложениях.

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

5. Заключение

Мы выполнили краткий обзор части работ, которые проводятся по компиляторным технологиям для современных архитектур в Институте системного программирования РАН. Завершенные работы по оптимизациям для архитектуры Intel Itanium, проводившиеся в течение последних трех лет, привели к среднему ускорению тестов SPEC CPU FP 2000 около 10%. При этом большинство реализаций, в том числе новый планировщик команд и конвейеризатор циклов, были включены в официальную версию компилятора GCC.

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

Назад Содержание Вперёд