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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
DVS (Dynamic Voltage Scaling) — технология позволяет снижать напряжение на процессоре,
 
и добиваться экономии электроэнергии за счет увеличения времени выполнения задачи.
 
  
Пусть процессор поддерживает два уровня напряжения — <m>U_L < U_H</m>.
+
==Стенина Мария, группа 974==
Есть набор из ''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 "Рюкзак": динамическое программирование)

Версия 12:04, 3 октября 2014

Стенина Мария, группа 974

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

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

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

Решение

Рассмотрим сперва частные случаи, в которых ответ можно дать сразу.

1) . Все работы исполняем в режиме L.

2) . Решения не существует.

3) . Все работы в режиме H.

Теперь общий случай . Введем следующие величины.

--- нормированное время,

--- выигрыш по мощности,
--- потери по времени.

С помощью этих величин запишем, используя вектор длины из 0 и 1, рассматриваемую задачу в виде максимизации выйгрышей по мощности с ограничением потерь по времени.

.

Решим поставленную задачу методом динамического программирования. Заведем словарь, в котором ключами будут значения потерь по времени, а значениями --- наборы работ, выполняемые в режиме L. Каждому ключу будет соответствовать набор работ, обеспечивающих максимальный выигрыш по мощности при данных потерях по времени. Сперва поместим в него ключ 0 и значение "пустой набор". Затем в цикле по всем работам будем делать следующее.

Итерация цикла. Обозначим рассматриваемую на итерации работу :

Завести пустой список. Для каждого элемента словаря сформировать новый набор работ, добавляя к набору, взятому из словаря. Если потери по времени вновь сформированного набора не превосходят и элемента с весом, как у этого набора, в словаре пока еще нет, либо есть, но с меньшим выигрышем по мощности, то добавить набор в список. После того, как пройдемся по всем имеющимся элементам словаря, добавим наборы, оказавшиеся в списке, в словарь. Если нужного значения потерь по времени в словаре еще нет, то создаем его, если есть, то обновляем при нем набор работ.

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

(Предложенный алгоритм описан в учебнике на с.106 - алгоритм 24 "Рюкзак": динамическое программирование)