ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
ЭНЕРГОСБЕРЕГАЮЩАЯ КОМПИЛЯЦИЯ ДЛЯ МОБИЛЬНЫХ
СИСТЕМ
© 2011 г. Д.М. Журихин Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: zhur@ispras.ru Поступила в редакцию 23.05.2011 г.
В данной работе представлен алгоритм оптимизации программы на этапе компиляции, анализирующий выполнение различных ее участков на доступных частотах процессора и выбирающий энергоэффективное расписание частот с учетом ограничений возникающего дополнительного времени работы. Этот алгоритм дополнен менеджером операционной системы, контролирующим установку нужного режима процессора и разрешающим конфликты, возникающие в случае мультипрограммной системы.
1. ВВЕДЕНИЕ
Проблема регулирования энергопотребления компьютерных систем существует уже давно. Однако в последнее десятилетие ее значение резко выросло, в связи с широким распространением мобильных устройств и увеличением мощности компьютеров. Для современных мобильных устройств энергопотребление является одним из важнейших параметров, способных обеспечить конкурентное преимущество. За счет улучшения этого показателя можно как увеличить время работы от одной подзарядки, так и уменьшить массу устройства при использовании аккумуляторов меньшей мощности. Хотя важную роль в снижении потребления энергии играет выбор эффективных аппаратных компонентов, именно программное обеспечение в итоге определяет его характер.
Технологии сбережения энергии в настоящее время активно развиваются. Это развитие происходит одновременно в разных направлениях (понятие о существующих подходах можно получить из исследования [1]). Предлагаемые решения начинаются с полностью аппаратных оптимизаций, таких как автоматическое отключение питания и логики
для неиспользуемых устройств [2], уменьшение паразитных токов [3], корректировка в протоколах взаимодействия устройств [4] и другие. Некоторое время назад начали активно развиваться программные методы оптимизации. Среди них можно выделить ряд статических оптимизаций программ: доступное описание распространенных подходов приведено в работе [5]. В работе [6] предлагается использовать планирование инструкций для уменьшения количества переключений битов на шинах процессора. В статье [7] рассматривается техника отключения компонентов процессора в тех местах программы, где их активность не требуется. Работа [8] описывает работающую на уровне инструкций модель энергопотребления программы и статические оптимизации, основанные на этой модели. Стоит отметить также работы, исследующие менеджеры энергосбережения операционных систем. Такие менеджеры анализируют данные о загруженности системы в предыдущих временных интервалах и выбирают режим работы процессора на следующие. Примеры алгоритмов таких менеджеров с различными эвристиками приведены в работах [9], [10] и [11]. Работа [12] описывает систему управления кластером с возможностью отключения узлов
и перераспределения нагрузки для экономии энергии.
Как правило, существующие подходы к энергосбережению обладают свойством уменьшать потребляемую энергию за счет снижения эффективности работы системы, например, переход из энергосберегающих режимов работы периферийных устройств требует некоторого времени, в течение которого устройство недоступно, аналогично динамическое изменение напряжения процессора ограничивает его тактовую частоту, т.е. производительность. Минимизировать такого рода потери в принципе возможно, располагая информацией о текущем и прогнозируемом состояниях работающей системы. Очевидно, что дополнение информации, получаемой от аппаратной составляющей системы, информацией о выполняющихся на ней программах должно положительно сказываться на эффективности энергосберегающих оптимизаций. Поэтому перспективным направлением исследований являются комбинированные методы энергосбережения, где программная составляющая оценивает текущее состояние системы, в случае необходимости составляет прогноз ее будущего состояния и принимает решение о применении оптимизации, в то время как аппаратное обеспечение поставляет ей необходимую информацию и производит саму оптимизацию.
Одним из направлений современных исследований является оптимизация прикладных программ с учетом энергоэффективности их выполнения в конкретной программно-аппаратной среде. В большинстве случаев с этой целью используют динамическое изменение частоты и напряжения центрального процессора. Эта технология позволяет добиться значительного снижения энергопотребления центрального процессора, пожертвовав при этом некоторой долей его производительности. Как правило, ее выгодно применять, когда не требуется пиковая производительность процессора, например, если узким местом является подсистема памяти.
Данная работа описывает алгоритм сбережения энергии, ставящий в соответствие каждому участку программы свой режим процессора
таким образом, чтобы минимизировать энергию, затраченную на выполнение данной программы. Также описывается менеджер операционной системы, который позволяет данному алгоритму эффективно работать в многопрограммном окружении.
Глава 2 посвящена формализации задачи сбережения энергии, на основе которой построен описываемый алгоритм. В главе 3 приводится описание практической реализации алгоритма в компиляторе GCC и операционной системе Linux. Глава 4 содержит результаты тестирования реализации алгоритма. В главе 5 приводятся заключение и будущие работы.
2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ СБЕРЕЖЕНИЯ ЭНЕРГИИ
Последовательность исполненных в процессе выполнения программы центральным процессором инструкций будем называть трассой программы. Выделим из трассы программы базовые блоки, разделив трассу программы по инструкциям перехода или вызова подпрограмм. С помощью заданной таким образом трассы можно наглядно получить описываемую программную оптимизацию энергопотребления.
Пусть центральный процессор обладает возможностью изменения напряжения своего питания и тактовой частоты. При этом его энергопотребление и производительность в различных режимах отличается. Пусть количество этих режимов равно C. Обозначим E(c) — энергопотребление процессора в режиме c за единицу времени.
Рассмотрим выполнение трассы программы в различных режимах работы процессора. Пусть количество базовых блоков в трассе равно N. Обозначим T(n, с) - время выполнения базового блока с номером n в режиме с. При этом допускаем, что выбор режима выполнения базовых блоков не влияет на время выполнения других базовых блоков.
Поставим задачу энергоэффективного выполнения трассы следующим образом. Пусть дан коэффициент допустимого замедления а. Необходимо выбрать режим работы процессора для каждого базового блока трассы таким образом, чтобы затраченная на выполнение трассы энергия была минимальной, но при этом
время, затраченное на выполнение трассы, не превышало времени выполнения всей трассы в режиме по умолчанию более чем в 1 + а раз. Формально это условие можно записать следующим образом:
тгп(£ ?=1 Е(/(г)) * Т (г,/ (г))) Ег=х Т(г, /(г)) < (1 + а) * Ег=1 Т(г, /умолч)
где за f (г) обозначен номер режима, в котором выполняется базовый блок с номером г. Необходимо найти дискретную функцию f(г). В данной формулировке задача представляет собой разновидность задачи о рюкзаке.
В реальности переключение между режимами процессора может занимать значительное время и приводить к дополнительным потерям энергии. Эти потери также необходимо учитывать. Обозначим Епр - энергию, а Тп - время, тратящиеся на переключение между режимами процессора. Для упрощения рассуждений сделаем допущение, что они одинаковы для всех пар режимов. Тогда та же задача принимает вид, приведенный ниже. Стоит заметить, что в этом случае для сохранения симметричности нужно ввести дополнительное требование завершения выполнения трассы в том же режиме, в котором оно начиналось, т.е. в режиме по умолчанию. Чтобы упростить запись для этого случая, искусственно введем дополнительные первый и последний базовые блоки с номерами 0 и N + 1 и нулевым временем выполнения, которые будут всегда выполняться в режиме по умолчанию. С этой же целью также введем функции Ве(г) и От (г), показывающие дополнительные затраты энергии и времени на переключение режима процессора при выполнении г-го базового блока соответственно.
тгп(£=1(Е(/(г)) * Т(г,/(г)) + Ве(г)))
Ег=+11(Т (г, / (г)) + Вт (г)) < (1 + а) * £ N=1 Т (г, /тЬох)
где
Бе (г) =
0, если /(г) = /(г - 1)
Епер, иначе
0, если /(г) = /(г - 1)
Вт (г) = ,
Тпер, иначе
В данную формулировку задачи просто ввести еще один фактор — накладные расходы на выбор нового режима в начале выполнения базового
блока. Если режим работы не выбирается заранее (например, на этапе компиляции), то эти затраты будут ненулевыми. Практический алгоритм выбора режима работы процессора должен учитывать такие затраты. Сделаем это с помощью введения новой константы, а именно, времени выбора нового режима Твыб. Конечно, это время может отличаться для разных вариантов алгоритмов выбора режима и может зависеть от разных факторов, в том числе и значений, известных только при выполнении. Но здесь предполагается, что оно может быть ограничено сверху, и эта верхняя граница и берется консервативно за значение константы. Добавим новые значения в выражения, показывающие дополнительные затраты энергии и времени на переключение режима процессора. Тогда задача примет следующий вид:
тгп(£ 1+11(Е(/(г)) * Т(г, /(г)) + Ве (г))) ЕГ=+1(Т(г, /(г)) + Вт (г)) < (1 + а) * £N=1 Т(г, /) : где
Ов(г) = IЕ(/(г - 1)) * Твыб' если /(г) = /(г - 1)
[Е(/(г - 1)) * Твыб + Епер, иначе
Вт(г) = /Твыб, если /(г) = /(г - 1)
\ Твыб + Тпер, иначе Теперь рассмотрим вопрос соответствия базовых блоков подпрограммы базовым блокам трассы. К стандартному определению базового блока подпрограммы добавим требование выделить все инструкции вызова подпрограмм в отдельные базовые блоки. Очевидно, что при нормальном выполнении на процессоре подпрограммы, не содержащей переходов, вызванных внешними причинами (вроде сигналов или исключений), будет получена трасса в смысле, описанном ранее. Каждый базовы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.