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

Ссылки сюда (15) →

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

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

энергоемкости

и

длительности

и .

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

Решение

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

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

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

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

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

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

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

--- потери по времени.

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

.

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

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.