Реализованный алгоритм ДИН
Алгоритм обрабатывает т.н. базовые и комбинированные регионы. Базовым регионом является либо базовый блок, либо гнездо циклов. Комбинированный регион – это объединение базовых регионов, имеющее один вход и один выход, при этом вход доминирует, а выход постдоминирует регион. Это определение предоставляет больше возможностей по созданию регионов, чем поиск по набору шаблонов графа потока управления, как предлагается в []. Тем не менее, существует ряд дополнительных ограничений на регионы. Во-первых, в первоначальной реализации не рассматривались регионы, содержащие вызовы функций, так как алгоритм был внутрипроцедурным (в текущей реализации это ограничение снято). Во-вторых, регионы с «нетипичным» потоком управления (например, несколько дуг пересекают границы цикла) не обрабатываются. В-третьих, небольшие регионы также исключаются из рассмотрения, так как затраты на переключение напряжения наверняка превысят возможный выигрыш на таком регионе.
Алгоритм состоит из следующих основных шагов:
- Построение базовых и комбинированных регионов для данной функции.
- Профилирование времени выполнения, 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%.
В настоящий момент ведутся работы по реализации межпроцедурного алгоритма, в котором регионы могут содержать вызовы функций, а также вход и выход региона могут принадлежать разным функциям. Кроме того, разрабатывается эвристический алгоритм, понижающий напряжение на множестве регионов.По результатам предварительного тестирования, количество регионов, на которых происходит понижение напряжения, выросло в два раза, что позволяет предположить об увеличении эффективности алгоритма.
