Динамическое программирование для задачи о рюкзаке/Задачи/Dynamic Voltage Scaling — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Отмена правки 3121, сделанной участницей SteninaMariya (обс.))
Строка 1: Строка 1:
 +
DVS (Dynamic Voltage Scaling) — технология позволяет снижать напряжение на процессоре,
 +
и добиваться экономии электроэнергии за счет увеличения времени выполнения задачи.
  
==Стенина Мария, группа 974==
+
Пусть процессор поддерживает два уровня напряжения — <m>U_L < U_H</m>.
 +
Есть набор из ''n'' задач, каждая из которых имеет энергоемкость и время выполнения
 +
для обоих режимов~--- т.\,е. <m>\forall i</m>:
 +
;энергоемкости: <m>c^H_i</m> и <m>c^L_i</m>
 +
;длительности: <m>t^H_i</m> и <m>t^L_i</m>.
  
[[Категория:На проверку]]
 
 
DVS (Dynamic Voltage Scaling) — технология позволяет снижать напряжение на процессоре, и добиваться экономии электроэнергии за счет увеличения времени выполнения задачи. Пусть процессор поддерживает два уровня напряжения — <m>U_L < U_H</m>. Есть набор из ''n'' задач, каждая из которых имеет энергоемкость и время выполнения для обоих режимов~--- т.\,е. <m>\forall i</m>:
 
;энергоемкости: <m>c^H_i</m> и <m>c^L_i</m>
 
;длительности: <m>t^H_i</m> и <m>t^L_i</m>.
 
 
Нужно выполнить все задачи на одном процессоре за время не более <tt>T</tt>, при этом добиться минимального энергопотребления.
 
Нужно выполнить все задачи на одном процессоре за время не более <tt>T</tt>, при этом добиться минимального энергопотребления.
  
==Решение==
+
[[Category:Решенные задачи]]
 
+
<!--Вообще-то, решения уже есть-->
Рассмотрим сперва частные случаи, в которых ответ можно дать сразу.
+
 
+
1) <m>\sum_{i=1}^n t_i^L \leq T</m>. Все работы исполняем в режиме L.
+
 
+
2) <m>\sum_{i=1}^n t_i^H > T</m>. Решения не существует.
+
 
+
3) <m>\sum_{i=1}^n t_i^H = T</m>. Все работы в режиме H.
+
 
+
Теперь общий случай <m>\sum_{i=1}^n t_i^H \leq T \leq \sum_{i=1}^n t_i^L</m>. Введем следующие величины.
+
 
+
<m>T' = T - \sum_{i=1}^n t_i^H \geq 0</m> --- нормированное время,
+
; <m>c_i = c_i^H - c_i^L > 0</m> --- выигрыш по мощности,
+
; <m>t_i = t_i^L - t_i^H > 0</m> --- потери по времени.
+
 
+
С помощью этих величин запишем, используя вектор <m>x</m> длины <m>n</m> из 0 и 1, рассматриваемую задачу в виде максимизации
+
выйгрышей по мощности с ограничением потерь по времени.
+
;<m>\max_x \sum_{i=1}^n c_i x_i</m>
+
;<m>\sum_{i=1}^n t_i x_i \leq T'</m>.
+
 
+
Решим поставленную задачу методом динамического программирования. Заведем словарь, в котором ключами будут значения потерь по времени, а значениями
+
--- наборы работ, выполняемые в режиме L. Каждому ключу будет соответствовать набор работ, обеспечивающих максимальный выигрыш по мощности при данных потерях по времени. Сперва поместим в него ключ 0 и значение "пустой набор". Затем в цикле по всем работам будем делать следующее.
+
 
+
Итерация цикла. Обозначим рассматриваемую на итерации работу <m>work_j</m>:
+
 
+
Завести пустой список. Для каждого элемента словаря сформировать новый набор работ, добавляя <m>work_j</m> к набору, взятому из словаря. Если потери по времени вновь сформированного набора не превосходят <m>T'</m> и элемента с весом, как у этого набора, в словаре пока еще нет, либо есть, но с меньшим выигрышем по мощности, то добавить набор в список. После того, как пройдемся по всем имеющимся элементам словаря, добавим наборы, оказавшиеся в списке, в словарь. Если нужного значения потерь по времени в словаре еще нет, то создаем его, если есть, то обновляем при нем набор работ.
+
 
+
После завершения цикла будем иметь в словаре для каждого возможного допустимого значения потерь по времени набор работ, выполнение которых в режиме L дает такое значение потерь по времени. Пройдемся по словарю и выберем набор, обеспечивающий максимальный выигрыш по мощности. Он и будет решением задачи.
+
 
+
(Предложенный алгоритм описан в учебнике на с.106 - алгоритм 24 "Рюкзак": динамическое программирование)
+

Версия 20:55, 24 декабря 2014

DVS (Dynamic Voltage Scaling) — технология позволяет снижать напряжение на процессоре, и добиваться экономии электроэнергии за счет увеличения времени выполнения задачи.

Пусть процессор поддерживает два уровня напряжения — . Есть набор из n задач, каждая из которых имеет энергоемкость и время выполнения для обоих режимов~--- т.\,е. :

энергоемкости
и
длительности
и .

Нужно выполнить все задачи на одном процессоре за время не более T, при этом добиться минимального энергопотребления.