4652
правки
Планирование с учетом наименьшего прошедшего времени обработки: различия между версиями
Перейти к навигации
Перейти к поиску
Планирование с учетом наименьшего прошедшего времени обработки (посмотреть исходный код)
Версия от 17:15, 23 февраля 2022
, 23 февраля 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
'''Теорема 2 [1]. SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(log^2 P)</math>-конкурентным алгоритмом для минимизации средней растяжимости, где P – отношение максимального размера задания к минимальному. С другой стороны, даже при скорости O(1) любой алгоритм без предвидения, по меньшей мере, <math>\Omega(log \; P)</math>-конкурентен. Любопытно, что с точки зрения n любой алгоритм без предвидения должен быть <math>\Omega(n)</math>-конкурентным даже при ускорении O(1). Более того, SETF является O(n)-конкурентным (даже без дополнительного ускорения).''' | '''Теорема 2 [1]. SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(log^2 P)</math>-конкурентным алгоритмом для минимизации средней растяжимости, где P – отношение максимального размера задания к минимальному. С другой стороны, даже при скорости O(1) любой алгоритм без предвидения, по меньшей мере, <math>\Omega(log \; P)</math>-конкурентен. Любопытно, что с точки зрения n любой алгоритм без предвидения должен быть <math>\Omega(n)</math>-конкурентным даже при ускорении O(1). Более того, SETF является O(n)-конкурентным (даже без дополнительного ускорения).''' | ||
'''Для специального случая, когда все задания поступают в момент времени 0, алгоритм SETF является оптимальным вплоть до константных коэффициентов. Он O(logP)-конкурентен (без дополнительного ускорения). Более того, любой алгоритм без предвидения должен быть <math>\Omega(log \; P)</math>-конкурентным даже при ускорении порядка O(1).''' | |||
Для специального случая, когда все задания поступают в момент времени 0, алгоритм SETF является оптимальным вплоть до константных коэффициентов. Он O(logP)-конкурентен (без дополнительного ускорения). Более того, любой алгоритм без предвидения должен быть | |||
| Строка 35: | Строка 34: | ||
Бансал и Прус [ ] рассмотрели задачу минимизации | Бансал и Прус [2] рассмотрели задачу минимизации <math>\ell_p</math>-норм продолжительности потока и растяжимости на одной машине. Они получили следующий результат: | ||
Теорема 3 [ ]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + <math>\epsilon</math>)-скоростными, O(1/<math>\epsilon</math>)-конкурентными для минимизации | '''Теорема 3 [2]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + <math>\epsilon</math>)-скоростными, O(1/<math>\epsilon</math>)-конкурентными для минимизации <math>\ell_p</math>-норм времени потока и растяжимости. С другой стороны, для <math>1 < p < \infty</math> ни один онлайновый алгоритм (возможно, с предвидением) не может быть O(1)-конкурентным для минимизации <math>\ell_p</math>норм растяжимости или продолжительности потока без ускорения. В частности, любой рандомизированный онлайн-алгоритм является по меньшей мере <math>\Omega(n^{(p - 1) / 3p^2})</math>-конкурентным для <math>\ell_p</math>-норм растяжимости и по меньшей мере <math>\Omega(n^{(p - 1) / p (3p - 1)})</math>-конкурентным для <math>\ell_p</math>-норм продолжительности потока.''' | ||
| Строка 44: | Строка 43: | ||
Бансал и Прус [ ] также рассматривают вариант задачи без предвидения. | Бансал и Прус [2] также рассматривают вариант задачи без предвидения. | ||
Теорема 4 [ ]. В постановке задачи без предвидения алгоритм SETF является (1 + <math>\epsilon</math>)-скоростными, 0(l/€2+2lt>)-конкурентным для минимизации | Теорема 4 [2]. В постановке задачи без предвидения алгоритм SETF является (1 + <math>\epsilon</math>)-скоростными, 0(l/€2+2lt>)-конкурентным для минимизации <math>\ell_p</math>-норм продолжительности потока. Для минимизации <math>\ell_p</math>-нормы растяжимости SETF является (1 + <math>\epsilon</math>)-скоростным, O(l/e3+1/? - log1+1/p P)-конкурентным. | ||
| Строка 53: | Строка 52: | ||
Теорема 5. Для любого p > 1 существует e > 0, такое, что даже при наличии в (1 + e) раз более быстрого процессора алгоритм RR не является оптимальным для минимизации | Теорема 5. Для любого p > 1 существует e > 0, такое, что даже при наличии в (1 + e) раз более быстрого процессора алгоритм RR не является оптимальным для минимизации <math>\ell_p</math>-норм продолжительности потока. В частности, для e < 1/2p алгоритм RR является (1 + e)-скоростным, ^(п^-^РЩ-конкурентным. Для <math>\ell_p</math>-норм растяжимости RR является Q(n)-конкурентным, как и фактически любой рандомизированный алгоритм без предвидения. | ||
Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [ ] распространили эти результаты на взвешенные | Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [ ] распространили эти результаты на взвешенные <math>\ell_p</math>-нормы продолжительности потока и растяжимости. Чекури, Ханна, Кумар и Гель [4] распространили их результаты на случай нескольких машин. Их алгоритмы особенно элегантны: каждое задание назначается некоторой машине случайным образом, и все задания на определенной машине обрабатываются с помощью алгоритма SRPT или SETF (в зависимости от применимости). | ||
== Применение == | == Применение == | ||