Динамическое программирование для задачи о рюкзаке/Задачи/Dynamic Voltage Scaling — различия между версиями
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | + | ==Стенина Мария, группа 974== | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
+ | [[Категория:На проверку]] | ||
+ | |||
+ | 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>, при этом добиться минимального энергопотребления. | ||
− | + | ==Решение== | |
− | < | + | |
+ | Рассмотрим сперва частные случаи, в которых ответ можно дать сразу. | ||
+ | |||
+ | 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 "Рюкзак": динамическое программирование)