Планирование напряжения

Ключевые слова и синонимы

Динамическое масштабирование скорости (Dynamic speed scaling)

Постановка задачи

Задача связана с планированием выполнения заданий с минимальным потреблением энергии за счет разумной подстройки скорости процессора. В ее основе лежит технология динамического масштабирования напряжения (ДМН) (или масштабирования скорости), которая позволяет процессору работать в некотором диапазоне напряжений и частот. Поскольку энергопотребление является как минимум квадратичной функцией от напряжения питания (а значит, и частоты/скорости процессора), выполнение задач с минимально возможной скоростью при одновременном соблюдении всех временных ограничений позволяет экономить энергию. Соответствующая задача планирования называется планированием ДМН с минимальным энергопотреблением. Предыдущие исследования показали, что расписание ДМН с минимальным энергопотреблением можно вычислить за кубическое время. В работе Ли и Яо [7] рассматривается дискретная модель, в которой процессор может выбирать свою скорость только из конечного набора скоростей. В ней разработан двухфазный алгоритм с временем выполнения [math]\displaystyle{ O(d \; n \; log \; n) }[/math] для вычисления расписания ДМН с минимальным энергопотреблением для дискретной модели ([math]\displaystyle{ d }[/math] представляет количество скоростей), а также доказана нижняя граница [math]\displaystyle{ \Omega(n \; log \; n) }[/math] сложности вычислений.

Нотация и определения

Модель планирования с переменным напряжением включает два важных множества:

1. Множество J (множество заданий) состоит из n заданий: j1; j2..: jn. Каждое задание jk имеет три параметра в связанной с ним информации: ak представляет время поступления jk, bk – крайний срок выполнения jk, а Rk – полное количество циклов процессора, требуемых jk. Параметры удовлетворяют условию 0 < ak < bk < 1.

2. Множество SD (множество скоростей) состоит из возможных скоростей, на которых может работать процессор. В соответствии со свойствами SD модель планирования делится на две следующие категории:

Непрерывная модель: SD представляет собой множество положительных действительных чисел.

Дискретная модель: SD состоит из d положительных значений: s1 > s2 > ::: > sd.

Расписание S состоит из следующих двух функций: s(t), которая задает скорость процессора в момент времени t, и job(t), которая определяет задание, выполняемое в момент времени t. Обе функции являются кусочно-постоянными с конечным числом разрывов.

Выполнимое расписание должно предоставить каждому заданию необходимое количество циклов между временем поступления и крайним сроком выполнения, тем самым удовлетворяя следующему свойству: / * s(t)S(k, job(t))dt = Rk, где 8(i, j) = 1, если i = j, и S(i,j) = 0 в противном случае.

Принцип EDF (Earliest Deadline First) определяет порядок заданий в соответствии с их крайними сроками выполнения. В любой момент времени t среди заданий jk, доступных для выполнения (то есть jk, удовлетворяющих условию t 2 [ak;bk) и jk, еще не завершенных к моменту t), задание с минимальным bk будет выполняться в промежутке [t; t + e].

Мощность P, или энергия, потребляемая в единицу времени, является выпуклой функцией от скорости процессора. Энергопотребление расписания S = (s(t); задание(t)) определяется как E(S)=R01P(s(t))dt.

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

В работе Ли и Яо рассматривается задача вычисления оптимального расписания для дискретной модели при следующих допущениях.

Допущения

1. Один процессор: в любой момент времени t может выполняться только одна задача.

2. Допустимость вытеснений: любое задание может быть прервано во время его выполнения.

3. Отсутствие предществования: There is no precedence relationship between any pair of jobs.

4. Оффлайновый подход: процессор знает информацию обо всех заданиях в момент времени 0.

Эта задача носит название «Дискретное динамическое масштабирование напряжения с минимальным энергопотреблением» (MEDDVS).

Задача 1 (MEDDVSJ, SD)

Дано: Целое число n, множество J = fj1; j2, ■ ■ ■, )„} и SD = {sus2,...,sd}. jk = {ak,bk,Rk}.

Требуется: Найти выполнимое расписание S = (s(t); job(t)), минимизирующее E(S).

Квон и Ким [ ] доказали, что оптимальное расписание для дискретной модели можно получить, сначала рассчитав оптимальное расписание для непрерывной модели, а затем индивидуально скорректировав скорость каждого задания в соответствии со смежными уровнями в множестве SD. Временная сложность составляет O(n3).

Основные результаты

В работе Ли и Яо найден прямой подход к решению задачи 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)