Балансировка нагрузки

Ключевые слова и синонимы

Планирование временных задач в режиме онлайн

Постановка задачи

Балансировка нагрузки временных задач представляет собой проблему онлайнового характера. В этом случае прибывающие задачи (или задания) необходимо назначать процессорам, также называемым машинами. Далее обсуждается детерминированная онлайновая процедура балансировки нагрузки для временных задач с неизвестной длительностью. Входная последовательность состоит из поступлений и убытий задач. Если последовательность состоит только из поступлений, задачи называются постоянными. События происходят одно за другим, следующее событие возникает после того, как алгоритм завершил работу с предыдущим событием.

Очевидно, что проблема с временными задачами отличается от проблемы с постоянными. Одно из таких отличий состоит в том, что в случае постоянных задач максимальная нагрузка всегда достигается в конце последовательности. Для временных задач это не всегда так. Более того, для разных алгоритмов максимальная нагрузка может быть достигнута в разное время.

В наиболее общей модели имеется m машин – 1, ..., m. Информация о поступающем задании j представляет собой вектор [math]\displaystyle{ p_j }[/math] длины m, где [math]\displaystyle{ p^i_j }[/math] – это нагрузка или размер задания j, если оно назначено машине i. Как было сказано выше, каждое задание должно быть назначено машине до следующего поступления или убытия. Нагрузка на машину i в момент времени t обозначается [math]\displaystyle{ L^t_i }[/math] и представляет собой сумму нагрузок (на машину i) заданий, назначенных машине i, которые поступили к моменту времени t и не убыли к этому времени. Цель заключается в сведении к минимуму максимальной нагрузки любой машины при всех значениях t. Эта машинная модель носит название «несвязанные машины» (см. в [3] исследование проблемы балансировки нагрузки при выполнении постоянных задач на несвязанных машинах). Было определено немало более специальных моделей. Далее будет описано несколько таких моделей.

Для алгоритма [math]\displaystyle{ \mathcal{A} }[/math] мы обозначаем его стоимость также как [math]\displaystyle{ \mathcal{A} }[/math]. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность событий заранее, обозначается OPT. Балансировка нагрузки изучается в терминах (абсолютного) коэффициента конкурентоспособности. Коэффициентом конкурентоспособности алгоритма [math]\displaystyle{ \mathcal{A} }[/math] является инфимум [math]\displaystyle{ \mathcal{R} }[/math], такой, что для любых входных данных [math]\displaystyle{ \mathcal{A} \le \mathcal{R} \cdot OPT }[/math]. Если коэффициент конкурентоспособности онлайнового алгоритма не превышает С, этот алгоритм также называется С-конкурентным.

Равномерно связанными машинами [3, 12] являются машины, с которыми ассоциированы скорости; таким образом, машина i имеет скорость [math]\displaystyle{ s_i }[/math], а информацией, которую задание j должно предоставить по прибытии, является только его размер, или нагрузка, которую он налагает на машину с единичной скоростью, что обозначается [math]\displaystyle{ p_j }[/math]. Положим [math]\displaystyle{ p^i_j = p_j / s_i }[/math]. Если все скорости одинаковы, в результате получаются идентичные машины [15].

Ограниченное назначение [8] представляет собой модель, в которой каждое задание может выполняться только на подмножестве машин. Задание j ассоциируется со временем выполнения, равным времени выполнения на любой из разрешенных ему машин [math]\displaystyle{ M_j }[/math]. Таким образом, если [math]\displaystyle{ i \in M_j }[/math], то [math]\displaystyle{ p^i_j = p_j }[/math], в противном случае [math]\displaystyle{ p^i_j = \infty }[/math].

Основные результаты

Известные результаты по всем четырем моделям представлены ниже.

Идентичные машины

Примечательно, что хорошо известный алгоритм Грэма [15], LIST SCHEDULING, который определен для идентичных машин, пригоден как для временных, так и для постоянных задач. Этот алгоритм жадным образом назначает новое задание наименее загруженной машине. Коэффициент конкурентоспособности этого алгоритма составляет 2 - 1/m, что является наилучшим возможным значением (см. [5]). Отметим, что коэффициент конкурентоспособности здесь тот же, что и для постоянных задач, однако для постоянных задач можно достичь коэффициента конкурентоспособности, который не стремится к 2 для больших m – см., например, [11].

Равномерно связанные машины

Для равномерно связанных машин ситуация не слишком отличается. В этом случае алгоритмы Аспнеса и др. [3], а также Бермана и др. [12] не могут применяться в исходном виде и требуют определенных модификаций. Алгоритм Азара и др. [7] имеет коэффициент конкурентоспособности не выше 20; он основан на общем методе, предложенном в [3]. Алгоритм в работе [3] сохраняет предполагаемое значение [math]\displaystyle{ \lambda }[/math], которое является оценкой стоимости оптимального оффлайнового алгоритма OPT. Инвариантом, который необходимо сохранить, является [math]\displaystyle{ \lambda \le 2 OPT }[/math]. На каждом шаге процедура применяется для некоторого значения [math]\displaystyle{ \lambda }[/math] (которое может быть инициализировано как загрузка первого задания на самой быстрой машине). Процедура для заданного значения [math]\displaystyle{ \lambda }[/math] применяется до тех пор, пока она не завершится неудачей, т. е. некоторое задание не может быть назначено, несмотря на выполнение всех условий. Процедура спроектирована таким образом, что в случае, когда она завершается неудачей, а это должно быть при [math]\displaystyle{ OPT \gt \lambda }[/math], значение [math]\displaystyle{ \lambda }[/math] удваивается, и процедура заново вызывается для нового значения, игнорируя все назначения, выполненные для малых значений [math]\displaystyle{ \lambda }[/math]. Этот подход называется методом удвоения, в результате чего получается алгоритм с коэффициентом конкурентоспособности, который не более чем в четыре раза превышает коэффициент конкурентоспособности, достигнутый процедурой. Процедура для заданного [math]\displaystyle{ \lambda }[/math] действует следующим образом. Обозначим целевой коэффициент конкурентоспособности для процедуры как c. Отсортируем машины по их скорости. Каждое задание назначается первой машине согласно порядку сортировки, такой, что задание может быть ей назначено. Задание j, поступающее в момент времени t, может быть назначено машине i, если [math]\displaystyle{ p_j / s_i \le \lambda }[/math] и [math]\displaystyle{ L^{t - 1}_i + p_j / s_i \le c \lambda }[/math]. В работе [7] было показано, что значение c = 5 позволяет алгоритму успешно назначать все задания (т. е. иметь хотя бы одну допускающую назначение машину для каждого задания), до тех пор, пока [math]\displaystyle{ OPT \le \lambda }[/math]. Заметим, что константа c для постоянных задач, используемая в [3], равна 2. Что касается нижних границ, то в [7] было показано, что коэффициент конкурентоспособности [math]\displaystyle{ \mathcal{R} }[/math] любого алгоритма удовлетворяет условию [math]\displaystyle{ \mathcal{R} \ge 3 - o(1) }[/math]. Верхнюю границу до значения [math]\displaystyle{ 6 + 2 \sqrt{5} \approx 10,47 }[/math] улучшили Бар-Ной и др. [9].

Ограниченное назначение

Что касается ограниченных назначений, то временные задачи делают эту модель гораздо более сложной, чем постоянные. Коэффициент конкурентоспособности O(log m), достигаемый простым жадным алгоритмом [8], в данном случае сохранить не удается. Для этого алгоритма он составляет [math]\displaystyle{ \Omega(m^{\frac{2}{3}}) }[/math] [4]. Более того, в той же работе было показано, что нижняя граница коэффициента конкурентоспособности любого алгоритма равна [math]\displaystyle{ \Omega (\sqrt{m}) }[/math]. При этом его построение было весьма сложным; впрочем, Ма и Плоткин [16] предложили упрощенное построение, дающее тот же результат.

При построении в работе [16] выбирается значение p, которое представляет собой наибольшее целое число, удовлетворяющее соотношению [math]\displaystyle{ p + p^2 \le m }[/math]. Очевидно, что [math]\displaystyle{ p = \Theta (\sqrt{m}) }[/math]. Для расчета нижней границыиспользуются два набора машин – [math]\displaystyle{ p }[/math] машин, которые называются «малой группой», и [math]\displaystyle{ p^2 }[/math] машин, называемые «большой группой». Построение состоит из [math]\displaystyle{ p^2 }[/math] фаз, каждая из которых состоит из [math]\displaystyle{ p }[/math] заданий и предназначена для одной машины в большой группе. На фазе i задание k этой фазы может выполняться либо на k-й машине малой группы, либо на i-й машине большой группы. После этого поступления только одно из этих [math]\displaystyle{ p }[/math] заданий не убывает. Оптимальный оффлайновый алгоритм на каждой фазе назначает все задания малой группы, за исключением одного задания, которое не убывает. Таким образом, после завершения построения на каждую машину большой группы приходится по одной задаче. Максимальная нагрузка, когда-либо достигаемая OPT, равна 1. Однако алгоритм не знает на каждой фазе, какое из имеющихся заданий не уйдет. Если на фазе i малой группе не назначено ни одного задания, то нагрузка на машину i полагается равной [math]\displaystyle{ p }[/math]. В противном случае задание, которое алгоритм назначает малой группе, выбирается как задание, которое не убывает вместе с остальными. Таким образом, после [math]\displaystyle{ p }[/math] фаз на малой группе накапливается совокупная нагрузка [math]\displaystyle{ p^2 }[/math], что означает, что по крайней мере одна машина в ней имеет нагрузку [math]\displaystyle{ p }[/math]. На этом конструирование завершается.

Альтернативный алгоритм под названием ROBIN HOOD был предложен в работе [7]. Этот алгоритм сохраняет нижнюю границу на OPT, которая представляет собой максимум из двух следующих функций. Первой из них является максимальная средняя загрузка машины за прошедшее время работы алгоритма. Второй – максимальный размер работы среди всех, поступивших за это время. Обозначим эту нижнюю границу на время t (после того, как произошли t событий) за [math]\displaystyle{ B^t }[/math]. Машина i называется «богатой» в момент времени t, если [math]\displaystyle{ L^t_i \ge \sqrt{m B^t} }[/math]. В противном случае она называется «бедной». Временем «удачи» богатой машины i является такой момент времени t, что в момент времени t' - 1 она еще является бедной, а в моменты t', ..., t, – уже богатой; т. е. именно в этот момент машина i перешла в разряд богатых. Очевидно, что машины могут стать бедными из-за обновления [math]\displaystyle{ B^t }[/math] или убытия заданий. Стать богатой машина может в результате поступления заданий, назначенных ей.

Алгоритм назначает задание j бедной машине в M(j), если такая машина существует. В противном случае j присваивается машине в M(j) с самым последним временем «удачи». Анализ использует тот факт, что одновременно богатыми могут быть не более [math]\displaystyle{ \sqrt{m} }[/math] машин.

Заметим, что для малых значений m [math]\displaystyle{ (m \le 5) }[/math] коэффициент конкурентоспособности жадного алгоритма все еще является наилучшим, как было показано в [1]. В данной работе было показано, что для эта граница равна (m + 3)/2 для m = 3, 4, 5. Нетрудно заметить, что для m = 2 лучшая граница равна 2.

Несвязанные машины

Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности [math]\displaystyle{ \Omega(m / log \; m) }[/math]. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей имеет минимальную нагрузку, коэффициент конкурентоспособности не превышает m [3].

Применение

Аналогичная модель известна и для задачи упаковки в контейнеры. В этой задаче последовательность состоит из поступлений и убытий элементов размером (0, 1]. Цель заключается в том, чтобы сохранить разбиение имеющихся в данный момент элементов на подмножества (контейнеры), где сумма элементов в каждом подмножестве не превышает 1. Стоимостью является максимальное количество одновременно используемых в любой момент времени контейнеров. Эта задача изучалась в работах [13, 14].

В [10] исследовалась иерархическая модель. Это специальный случай ограниченного задания, в котором для каждого задания j M(j) является префиксом машин. Они показали, что даже для временных заданий для этой модели существует алгоритм с константным коэффициентом конкурентоспособности.

В работе [6], в которой изучалось приращение ресурсов при балансировке нагрузки, рассматривались также и временные задачи. Приращение ресурсов представляет собой вид анализа, при котором онлайновый алгоритм сравнивается с оптимальным оффлайновым алгоритмом, имеющим меньшее количество машин.

Открытые вопросы

По-прежнему остаются небольшие пробелы как для равномерно связанных, так и для несвязанных машин. Для несвязанных машин может быть любопытно выяснить, существует ли алгоритм с коэффициентом конкурентоспособности o(m), а также имеет ли простой алгоритм, описанный выше, оптимальный коэффициент конкурентоспособности (с поправкой на мультипликативный множитель).

См. также

статью Списочное планирование для получения дополнительной информации по идентичным машинам и работу [15].

Литература

1. Armon, A., Azar, Y., Epstein, L., Regev, O.: On-line restricted assignment of temporary tasks with unknown durations. Inf. Process. Lett. 85(2), 67-72 (2003)

2. Armon, A., Azar, Y., Epstein, L., Regev, O.: Temporary tasks assignment resolved. Algorithmica 36(3), 295-314 (2003)

3. Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line load balancing with applications to machine scheduling and virtual circuit routing. J. ACM 44,486-504 (1997)

4. Azar, Y., Broder, A.Z., Karlin, A.R.: On-line load balancing.Theor. Comput. Sci. 130, 73-84 (1994)

5. Azar, Y., Epstein, L.: On-line load balancing of temporary tasks on identical machines. SIAM J. Discret. Math. 18(2), 347-352 (2004)

6. Azar, Y., Epstein, L., van Stee, R.: Resource augmentation in load balancing. J. Sched. 3(5), 249-258 (2000)

7. Azar, Y., Kalyanasundaram, B., Plotkin, S., Pruhs, K., Waarts, O.: On-line load balancing of temporary tasks. J. Algorithms 22(1), 93-110(1997)

8. Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. J. Algorithms 18, 221-237 (1995)

9. Bar-Noy, A., Freund, A., Naor, J.: New algorithms for related machines with temporary jobs. J. Sched. 3(5), 259-272 (2000)

10. Bar-Noy, A., Freund, A., Naor, J.: On-line load balancing in a hierarchical server topology. SIAM J. Comput. 31, 527-549 (2001)

11. Bartal, Y., Fiat, A., Karloff, H., Vohra, R.: New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci. 51(3), 359-366(1995)

12. Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. J. Algorithms 35,108-121 (2000)

13. Chan, W.-T., Wong, P.W.H., Yung, F.C.C.: On dynamic bin packing: an improved lower bound and resource augmentation analysis. In: Proc. of the 12th Annual International Conference on Computing and Combinatorics (COCOON2006), 2006, pp. 309-319

14. Coffman, E.G.,Garey, M.R., Johnson, D.S.: Dynamic bin packing. SIAM J. Comput. 12(2), 227-258 (1983)

15. Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45,1563-1581 (1966)

16. Ma, Y., Plotkin, S.: Improved lower bounds for load balancing of tasks with unknown duration. Inf. Process. Lett. 62, 31-34 (1997)