О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью
https://doi.org/10.15514/ISPRAS-2012-23-27
Аннотация
Предложен онлайновый алгоритм распределения параллельных задач на группе кластеров с различными производительностями процессоров и показано, что он гарантирует для любого потока задач построение расписания, отличающегося от оптимального не более чем в 2e раз.
Список литературы
1. Bernam P., Charikar M., Karpinski M., On-line load balancing for related machines, Proc. WADS, 1997, LNCS, 1272, Springer-Ferlag, p. 116-125.
2. Aspens J., Azar Y., Fiat A., Plotkin S., Waarts O., On-line load balancing with applications to machine scheduling and virtual circuit routing, Proc. 25th ACM STOC, 1993, p. 623-631.
3. Жук С.Н., Приближенные онлайновые алгоритмы упаковки прямоугольников в несколько полос, Дискретная математика, 2007, т. 19, N 4.
Рецензия
Для цитирования:
Жук С.Н. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью. Труды Института системного программирования РАН. 2012;23. https://doi.org/10.15514/ISPRAS-2012-23-27
For citation:
Zhuk S.N. On-line algorithm for scheduling parallel tasks on a group of related clusters. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;23. (In Russ.) https://doi.org/10.15514/ISPRAS-2012-23-27
Послать статью по эл. почте 