Планирование напряжения
Ключевые слова и синонимы
Динамическое масштабирование скорости (Dynamic speed scaling)
Постановка задачи
Задача связана с планированием выполнения заданий с минимальным потреблением энергии за счет разумной подстройки скорости процессора. В ее основе лежит технология динамического масштабирования напряжения (ДМН) (или масштабирования скорости), которая позволяет процессору работать в некотором диапазоне напряжений и частот. Поскольку энергопотребление является как минимум квадратичной функцией от напряжения питания (а значит, и частоты/скорости процессора), выполнение задач с минимально возможной скоростью при одновременном соблюдении всех временных ограничений позволяет экономить энергию. Соответствующая задача планирования называется планированием ДМН с минимальным энергопотреблением. Предыдущие исследования показали, что расписание ДМН с минимальным энергопотреблением можно вычислить за кубическое время. В работе Ли и Яо [7] рассматривается дискретная модель, в которой процессор может выбирать свою скорость только из конечного набора скоростей. В ней разработан двухфазный алгоритм с временем выполнения [math]\displaystyle{ O(d \; n \; log \; n) }[/math] для вычисления расписания ДМН с минимальным энергопотреблением для дискретной модели ([math]\displaystyle{ d }[/math] представляет количество скоростей), а также доказана нижняя граница [math]\displaystyle{ \Omega(n \; log \; n) }[/math] сложности вычислений.
Нотация и определения
Модель планирования с переменным напряжением включает два важных множества:
1. Множество [math]\displaystyle{ J }[/math] (множество заданий) состоит из [math]\displaystyle{ n }[/math] заданий: [math]\displaystyle{ j_1, j_2, ..., j_n }[/math]. Каждое задание [math]\displaystyle{ j_k }[/math] имеет три параметра в связанной с ним информации: [math]\displaystyle{ a_k }[/math] представляет время поступления [math]\displaystyle{ j_k }[/math], [math]\displaystyle{ b_k }[/math] – крайний срок выполнения [math]\displaystyle{ j_k }[/math], а [math]\displaystyle{ R_k }[/math] – полное количество циклов процессора, требуемых [math]\displaystyle{ j_k }[/math]. Параметры удовлетворяют условию [math]\displaystyle{ 0 \le a_k \le b_k \le 1 }[/math].
2. Множество [math]\displaystyle{ SD }[/math] (множество скоростей) состоит из возможных скоростей, на которых может работать процессор. В соответствии со свойствами [math]\displaystyle{ SD }[/math] модель планирования делится на две следующие категории:
Непрерывная модель: [math]\displaystyle{ SD }[/math] представляет собой множество положительных действительных чисел.
Дискретная модель: [math]\displaystyle{ SD }[/math] состоит из [math]\displaystyle{ d }[/math] положительных значений: [math]\displaystyle{ s_1 \gt s_2 \gt ... \gt s_d }[/math].
Расписание [math]\displaystyle{ S }[/math] состоит из следующих двух функций: [math]\displaystyle{ s(t) }[/math], которая задает скорость процессора в момент времени [math]\displaystyle{ t }[/math], и [math]\displaystyle{ job(t) }[/math], которая определяет задание, выполняемое в момент времени [math]\displaystyle{ t }[/math]. Обе функции являются кусочно-постоянными с конечным числом разрывов.
Выполнимое расписание должно предоставить каждому заданию необходимое количество циклов между временем поступления и крайним сроком выполнения, тем самым удовлетворяя следующему свойству: [math]\displaystyle{ \int_{a_k}^{b_k} s(t) \delta(k, job(t))dt = R_k }[/math], где [math]\displaystyle{ \delta(i, j) = 1 }[/math], если [math]\displaystyle{ i = j }[/math], и [math]\displaystyle{ \delta(i, j) = 0 }[/math] в противном случае.
Принцип EDF (Earliest Deadline First) определяет порядок заданий в соответствии с их крайними сроками выполнения. В любой момент времени [math]\displaystyle{ t }[/math] среди заданий [math]\displaystyle{ j_k }[/math], доступных для выполнения (то есть [math]\displaystyle{ j_k }[/math], удовлетворяющих условию [math]\displaystyle{ t \in [a_k, b_k) }[/math] и [math]\displaystyle{ j_k }[/math], еще не завершенных к моменту [math]\displaystyle{ t }[/math]), задание с минимальным [math]\displaystyle{ b_k }[/math] будет выполняться в промежутке [math]\displaystyle{ [t, t + \epsilon] }[/math].
Мощность [math]\displaystyle{ P }[/math], или энергия, потребляемая в единицу времени, является выпуклой функцией от скорости процессора. Энергопотребление расписания [math]\displaystyle{ S = (s(t), job(t)) }[/math] определяется как [math]\displaystyle{ E(S) = \int_{0}^{1} P(s(t))dt }[/math].
Расписание называется оптимальным, если его энергопотребление является минимально возможным среди всех выполнимых расписаний. Отметим, что в рамках непрерывной модели оптимальное расписание использует одинаковую скорость для одной и той же задачи.
В работе Ли и Яо рассматривается задача вычисления оптимального расписания для дискретной модели при следующих допущениях.
Допущения
1. Один процессор: в любой момент времени [math]\displaystyle{ t }[/math] может выполняться только одна задача.
2. Допустимость вытеснений: любое задание может быть прервано во время его выполнения.
3. Отсутствие предшествования: между любыми парами заданий не имеется отношений предшествования.
4. Оффлайновый подход: процессор знает информацию обо всех заданиях в момент времени 0.
Эта задача носит название «Дискретное динамическое масштабирование напряжения с минимальным энергопотреблением» (MEDDVS).
Задача 1 (MEDDVS[math]\displaystyle{ _{J, SD} }[/math])
Дано: Целое число [math]\displaystyle{ n }[/math], множество [math]\displaystyle{ J = \{ j_1, j_2, ..., j_n \} }[/math] и [math]\displaystyle{ SD = \{ s_1, s_2, ..., s_d \} }[/math]. [math]\displaystyle{ jk = \{ a_k, b_k, R_k \} }[/math].
Требуется: Найти выполнимое расписание [math]\displaystyle{ S = (s(t), job(t)) }[/math], минимизирующее [math]\displaystyle{ E(S) }[/math].
Квон и Ким [6] доказали, что оптимальное расписание для дискретной модели можно получить, сначала рассчитав оптимальное расписание для непрерывной модели, а затем индивидуально скорректировав скорость каждого задания в соответствии со смежными уровнями в множестве [math]\displaystyle{ SD }[/math]. Временная сложность составляет [math]\displaystyle{ O(n^3) }[/math].
Основные результаты
В работе Ли и Яо найден прямой подход к решению задачи MEDDVS без предварительного вычисления оптимального расписания для непрерывной модели.
Определение 1. s-расписанием для J является расписание, соответствующее принципу EDF и использующее постоянную скорость s при выполнении любого задания из J.
Лемма 1. s-расписание для J может быть вычислено за время O(n log n).
Определение 2. Для заданного множества заданий J и любой скорости s обозначим за J-s и J s и < s. Разбиение (J-s, J<s) называется s-разбиением J.
Извлекая информацию из s-расписания, был разработан алгоритм разбиения для доказательства следующей леммы:
Лемма 2. s-разбиение для J может быть вычислено за время O(n log n).
Применяя s-разбиение к J с использованием всех d скоростей в SD последовательно, можно получить d подмножеств J1;J2 ■ ■ ,Jd из J, где задания в одном и том же подмножестве Ji используют две одинаковые скорости si и si+1 в оптимальном расписании для дискретной модели (sd+1 = 0).
Лемма 3. Оптимальное расписание для множества заданий Ji с использованием скоростей si и si+1 может быть вычислено за время O(nlog n).
Объединяя три вышеприведенные леммы, получаем основную теорему:
Теорема 4. Дискретное расписание ДМН с минимальным энергопотреблением может быть вычислено за время O(dn log n).
Нижняя граница для вычисления оптимального расписания для дискретной модели в рамках алгебраической модели дерева решений также была доказана Ли и Яо.
Теорема 5. Любой детерминированный алгоритм для вычисления дискретного расписания ДМН с минимальным энергопотреблением с d > 2 уровнями напряжения требует времени £?(nlog n) для n заданий.
Применение
В настоящее время технология динамического масштабирования напряжения применяется крупнейшими мировыми производителями микросхем, например, в виде технологий SpeedStep от Intel и PowerNow от AMD. Хотя используемые алгоритмы планирования в основном являются онлайновыми, оффлайн-алгоритмы все же могут найти свое применение в реальных приложениях. Кроме того, методы, разработанные в работе Ли и Яо для вычисления оптимальных расписаний, могут иметь потенциальное применение в других областях.
Также изучаются проблемы энергоэффективного планирования для других типов множеств заданий. Юн и Ким [ ] доказали, что вычисление оптимального расписания для задач с приоритетами является NP-трудной задачей, и предложили схему аппроксимации с полностью полиномиальным временем выполнения (FPTAS) для этой задачи. Айдин и коллеги. [1] рассмотрели энергоэффективное планирование для периодических задач в реальном времени и предложили алгоритм планирования с временем выполнения O(n2 log n). Чен и др. [ ] изучили слабо дискретную модель для заданий без вытеснения, в которой скорость не может изменяться во время выполнения одного задания. Они доказали NP-сложность вычисления оптимального расписания.
Еще одним важным вариантом применения этой работы является помощь в исследовании модели планирования с большим количеством аппаратных ограничений (Берд и Бродерсен [ ] пояснили различные вопросы этапа проектирования, которые могут возникнуть при динамическом изменении напряжения). Помимо однопроцессорной модели, интерес представляет также модель с несколькими процессорами [11].
Открытые вопросы
Некоторые задачи, имеющие отношение к работе Ли и Яо, остаются нерешенными. В дискретной модели алгоритм Ли и Яо для вычисления оптимального расписания требует O(dn log n) времени. Это значение отличается от известной на настоящий момент нижней границы Q(n log n). Устранение этого разрыва при рассмотрении d как переменной является открытым вопросом.
Еще одной актуальной областью исследований является вычисление оптимального расписания для непрерывной модели. Ли, Яо и Яо [8] получили алгоритм с временем выполнения O(n2 log n) для вычисления оптимального расписания. Узким местом для коэффициента log n является вычисление s-расписаний. Задача сокращения временной сложности вычисления s-расписаний остается нерешенной. Также можно рассматривать другие методы работы с непрерывной моделью.
См. также
Литература
1. Aydin, H., Melhem, R., Mosse, D., Alvarez, P.M.: Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics. Euromicro Conference on Real-Time Systems, pp. 225-232. IEEE Computer Society, Washington, DC, USA (2001)
2. Bansalm, N., Kimbrel, T., Pruhs, K.: Dynamic Speed Scaling to Manage Energy and Temperature, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 520-529. IEEE Computer Society, Washington, DC, USA (2004)
3. Burd, T.D., Brodersen, R.W.: Design Issues for Dynamic Voltage Scaling, Proceedings of the 2000 international symposium on Low power electronics and design, pp. 9-14. ACM, New York, USA (2000)
4. Chen, J.J., Kuo, T.W., Lu, H.I.: Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices Workshop on Algorithms and Data Structures (WADS). LNCS, vol. 3608, pp. 338-349. Springer, Berlin, Germany (2005)
5. Irani, S., Pruhs, K.: Algorithmic Problems in Power Management. ACM SIGACT News 36(2), 63-76. New York, NY, USA (2005)
6. Kwon, W., Kim, T.: Optimal Voltage Allocation Techniques for Dynamically Variable Voltage Processors. ACM Trans. Embed. Comput. Syst. 4(1), 211 -230. New York, NY, USA (2005)
7. Li, M., Yao, F.F.: An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. SIAM J. Comput. 35(3), 658-671. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2005)
8. Li, M., Yao, A.C., Yao, F.F.: Discrete and Continuous Min-Energy Schedules for Variable Voltage Processors, Proceedings of the National Academy of Sciences USA, 103, pp. 3983-3987. National Academy of Science of the United States of America, Washington, DC, USA (2005)
9. Yao, F., Demers, A., Shenker, S.: A Scheduling Model for Reduced CPU Energy, Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp. 374-382. IEEE Computer Society, Washington, DC, USA (1995)
10. Yun, H.S., Kim, J.: On Energy-Optimal Voltage Scheduling for Fixed-Priority Hard Real-Time Systems. ACM Trans. Embed. Comput. Syst. 2, 393-430. ACM, New York, NY, USA (2003)
11. Zhu, D., Melhem, R., Childers, B.: Scheduling with Dynamic Voltage/Speed Adjustment Using Slack Reclamation in Multi-Processor RealTime Systems. Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), pp. 84-94. IEEE Computer Society, Washington, DC, USA (2001)