Алгоритм YDS - YDS algorithm - Wikipedia

YDS это алгоритм планирования за процессоры динамического масштабирования скорости что сводит к минимуму общее потребление энергии. Он был назван в честь и разработан Yao et al.^[1] Существует как онлайн-версия, так и офлайн-версия алгоритма.

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

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

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

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

Пока ${\displaystyle J\neq \{\}}$  Определить временной интервал ${\displaystyle I}$ максимальной плотности ${\displaystyle \Delta _{I}}$. В ${\displaystyle I}$ обрабатывать рабочие места ${\displaystyle S_{I}}$ на скорости ${\displaystyle \Delta _{I}}$ в соответствии с EDF  Набор ${\displaystyle J:=J\setminus S_{I}}$. Удалять ${\displaystyle I}$ от временного горизонта и соответственно обновите время выпуска и крайние сроки внеплановых заданий. end Пока

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

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

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

Смотрите также

• EDF алгоритм

Рекомендации

1. F.F. Яо, А.Дж. Демерс и С. Шенкер. Модель планирования для сокращенного ЦПУ энергия. Proc. 36-й IEEE Симпозиум по основам информатики , 374–382, 1995.
2. Сюзанна Альберс, «Алгоритмы динамического масштабирования скорости»