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

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

Динамическое масштабирование скорости (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. [math]\displaystyle{ s }[/math]-расписанием для множества [math]\displaystyle{ J }[/math] является расписание, соответствующее принципу EDF и использующее постоянную скорость [math]\displaystyle{ s }[/math] при выполнении любого задания из [math]\displaystyle{ J }[/math].

Лемма 1. [math]\displaystyle{ s }[/math]-расписание для [math]\displaystyle{ J }[/math] может быть вычислено за время [math]\displaystyle{ O(n \; log \; n) }[/math].

Определение 2. Для заданного множества заданий [math]\displaystyle{ s }[/math] и любой скорости [math]\displaystyle{ s }[/math] обозначим за [math]\displaystyle{ J^{\ge s} }[/math] и [math]\displaystyle{ J^{\lt s} }[/math] подмножества [math]\displaystyle{ J }[/math], состоящие из заданий, скорость выполнения которых в оптимальном расписании для [math]\displaystyle{ J }[/math] в непрерывной модели больше или равна [math]\displaystyle{ s }[/math] либо меньше [math]\displaystyle{ s }[/math], соответственно. Разбиение [math]\displaystyle{ \langle J^{\ge s}, J^{\lt s} \rangle }[/math] называется [math]\displaystyle{ s }[/math]-разбиением [math]\displaystyle{ J }[/math].

Извлекая информацию из [math]\displaystyle{ s }[/math]-расписания, был разработан алгоритм разбиения для доказательства следующей леммы:

Лемма 2. [math]\displaystyle{ s }[/math]-разбиение для [math]\displaystyle{ J }[/math] может быть вычислено за время [math]\displaystyle{ O(n \; log \; n) }[/math].

Применяя [math]\displaystyle{ s }[/math]-разбиение к [math]\displaystyle{ J }[/math] с использованием всех [math]\displaystyle{ d }[/math] скоростей в [math]\displaystyle{ SD }[/math] последовательно, можно получить [math]\displaystyle{ d }[/math] подмножеств [math]\displaystyle{ J_1, J_2, ..., J_d }[/math] множества [math]\displaystyle{ J }[/math], где задания в одном и том же подмножестве [math]\displaystyle{ J_i }[/math] используют те же две скорости [math]\displaystyle{ s_i }[/math] и [math]\displaystyle{ s_{i+1} }[/math] в оптимальном расписании для дискретной модели [math]\displaystyle{ (s_{d+1} = 0) }[/math].

Лемма 3. Оптимальное расписание для множества заданий [math]\displaystyle{ J_i }[/math] с использованием скоростей [math]\displaystyle{ s_i }[/math] и [math]\displaystyle{ s_{i+1} }[/math] может быть вычислено за время [math]\displaystyle{ O(n \; log \; n) }[/math].

Объединяя три вышеприведенные леммы, получаем основную теорему:

Теорема 4. Дискретное расписание ДМН с минимальным энергопотреблением может быть вычислено за время [math]\displaystyle{ O(d \; n \; log \; n) }[/math].

Нижняя граница для вычисления оптимального расписания для дискретной модели в рамках алгебраической модели дерева решений также была доказана Ли и Яо.

Теорема 5. Любой детерминированный алгоритм для вычисления дискретного расписания ДМН с минимальным энергопотреблением с [math]\displaystyle{ d \ge 2 }[/math] уровнями напряжения требует времени [math]\displaystyle{ \Omega(n \; log \; n) }[/math] для [math]\displaystyle{ n }[/math] заданий.

Применение

В настоящее время технология динамического масштабирования напряжения применяется крупнейшими мировыми производителями микросхем, например, в виде технологий SpeedStep от Intel и PowerNow от AMD. Хотя используемые алгоритмы планирования в основном являются онлайновыми, оффлайн-алгоритмы все же могут найти свое применение в реальных приложениях. Кроме того, методы, разработанные в работе Ли и Яо для вычисления оптимальных расписаний, могут иметь потенциальное применение в других областях.

Также изучаются проблемы энергоэффективного планирования для других типов множеств заданий. Юн и Ким [10] доказали, что вычисление оптимального расписания для задач с приоритетами является NP-трудной задачей, и предложили схему аппроксимации с полностью полиномиальным временем выполнения (FPTAS) для этой задачи. Айдин и коллеги. [1] рассмотрели энергоэффективное планирование для периодических задач в реальном времени и предложили алгоритм планирования с временем выполнения [math]\displaystyle{ O(n^2 log \; n) }[/math]. Чен и др. [4] изучили слабо дискретную модель для заданий без вытеснения, в которой скорость не может изменяться во время выполнения одного задания. Они доказали NP-трудность вычисления оптимального расписания.

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

Открытые вопросы

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

Еще одной актуальной областью исследований является вычисление оптимального расписания для непрерывной модели. Ли, Яо и Яо [8] получили алгоритм с временем выполнения [math]\displaystyle{ O(n^2 log \; n) }[/math] для вычисления оптимального расписания. Узким местом для коэффициента [math]\displaystyle{ log \; n }[/math] является вычисление [math]\displaystyle{ s }[/math]-расписаний. Задача сокращения временной сложности вычисления [math]\displaystyle{ s }[/math]-расписаний остается нерешенной. Также можно рассматривать другие методы работы с непрерывной моделью.

См. также

• Списочное планирование
• Балансировка нагрузки
• Параллельные алгоритмы для двухпроцессорного расписания с ограничением предшествования
• Планирование с учетом наименьшего прошедшего времени обработки

Литература

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)