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