Алгоритм YDS

YDS — это алгоритм планирования для процессоров с динамическим масштабированием скорости , который минимизирует общее потребление энергии. Он был назван в честь и разработан Яо и др. Существует как онлайн, так и оффлайн версия алгоритма.

Автономный алгоритм

Определения:

• Имеется набор из n заданий $J:=J_{1},...,J_{n}$, где каждое задание $J_{i}$ есть время выпуска $r_{i}$, крайний срок $d_{i}$ и объем обработки $w_{i}$.
• $I$ это определенный интервал времени.
• Также у нас есть $\Delta _{I}={\frac {1}{|I|}}\sum _{J_{i}\in S_{I}}w_{i}$, плотность работы в $I$.
• И наконец $S_{I}\in J$ это набор заданий, которые должны быть обработаны в $I$, это означает, что Джобс с $[r_{i},d_{i}]\in I$.

Тогда алгоритм работает следующим образом:

While $J\neq \{\}$
  Determine the time interval $I$ of maximum density $\Delta _{I}$.
  In $I$ process the jobs of $S_{I}$ at speed $\Delta _{I}$ according to EDF
  Set $J:=J\setminus S_{I}$. 
  Remove $I$ from the time horizon and update the release times and deadlines of unscheduled jobs accordingly.
end While

Другими словами, это рекурсивный алгоритм , который будет выполнять следующие шаги, пока все задания не будут запланированы:

1. Рассчитайте все интенсивности для всех возможных комбинаций интервалов. Это означает, что для каждой комбинации времени начала и окончания рассчитывается интенсивность работы. Для этого времена всех заданий, время прибытия и крайний срок которых лежат внутри интервала, суммируются и делятся на длину интервала. Чтобы ускорить процесс, необходимо учитывать только комбинации времени прибытия и более поздних сроков, поскольку время без прибытия процесса или крайнего срока может быть сокращено до меньшего интервала с теми же процессами, тем самым увеличивая интенсивность, а отрицательные интервалы недействительны. Затем выбирается максимальный интервал интенсивности. В случае нескольких одинаково интенсивных интервалов один из них можно выбрать произвольно, так как интенсивности непересекающихся интервалов не влияют друг на друга, а удаление части интервала не изменит интенсивность остальных, поскольку процессы удаляются пропорционально.
2. Процессы внутри этого интервала планируются с использованием метода «Сначала самый ранний срок», что означает, что задание внутри этого интервала, крайний срок которого наступит раньше, запланировано первым, и так далее. Задания выполняются с рассчитанной выше интенсивностью, чтобы уместить все задания внутри интервала.
3. Интервал будет удален с временной шкалы, поскольку здесь невозможно запланировать дальнейшие вычисления. Для упрощения дальнейших расчетов все времена прибытия и сроки оставшихся работ пересчитываются, чтобы исключить уже занятое время. Например, возьмем работу $A$ со временем прибытия $a_{A}=0$, крайний срок $d_{A}=10$ и рабочая нагрузка $w_{A}=5$и работа $B$ с $a_{B}=5$, $d_{B}=10$ и $w_{B}=4$. Предположим, что предыдущий интервал был от времени $3$ к $8$. Чтобы опустить этот интервал, время $A$ и $B$ необходимо отрегулировать; рабочие нагрузки не затронуты, так как ни для одного из них не было выполнено никакой работы. $A$ или $B$. $a_{A}$ остается прежним, так как на него не влияют последующие упущения. $d_{A}$однако необходимо изменить на $5$, как $10-(8-3)=5$. Это работа на время $A$ ушел раньше установленного срока. Время прибытия $a_{B}$ становится $3$, как это было бы внутри удаленного интервала. $d_{B}$ также становится $5$, так как время, оставшееся после удаленного интервала, равно $2$. Однако важно помнить фактическое время прибытия и крайние сроки для последующего составления расписания.
4. Повторяйте шаги 1–3, пока все задания не будут запланированы.
5. Соберите задания в окончательное расписание в соответствии с выделенными им временными интервалами. Однако помните, что интервал может быть разделен на две части другим интервалом, рассчитанным ранее.

Для любого экземпляра задания алгоритм вычисляет оптимальное расписание, минимизирующее общее потребление энергии.

См. также

• Первое планирование самого раннего срока