On-line algorithm for scheduling parallel tasks on related computational clusters with processors of different capacities and its average-case analysis
https://doi.org/10.15514/ISPRAS-2018-30(6)-6
Abstract
In this article the on-line problem of scheduling parallel tasks on related computational clusters with processors of different capacities was studied in average case. In the problem the objective is to make a schedule on k clusters with w processors each of N tasks, where the task i,i≤N requires time hi on cluster with nominal capacity of processors and wi≤w processors. We presume for all 1≤i≤N that wi has uniform distribution on (0,w] and that hi has uniform distribution on (0,1]. The processors on different clusters have different capacities v1,…,vk. The task with nominal time hi will require wi processors be computed in time hi/vj on cluster number j. Let sum volume of computations W be the sum of volumes of computations for each task. Let L be the minimal time at which all clusters will compute all the tasks, assigned to them, where each task is assigned to one cluster. The expected value of free volume of computations E(Vsp) is used to analyze the quality of an algorithm, where Vsp=∑1≤i≤kviL-W. It was shown that for every algorithm for scheduling parallel tasks on related clusters E(Vsp)=Ω(w√N). An online scheduling algorithm Limited Hash Scheduling was proposed that distribute tasks to limited areas. This algorithm works in a closed-end mode and has a mathematical expectation of a free calculation volume equal to O(w√(N ln N)). The idea of the algorithm is to schedule tasks of close required number of required processors into different limited in time and the number of allowed to use processors areas on clusters.
About the Authors
D. O. Lazarev
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
N. N. Kuzyurin
Ivannikov Institute for System Programming of the Russian Academy of Sciences; Moscow Institute of Physics and Technology (State University)
Russian Federation
Russian Federation
References
1. . Aspens J., Azar Y., Fiat A., Plotkin S., Waarts O. On - line load balancing with applications to machine scheduling and virtual circuit routing. In Proc. of the 25th ACM STOC. 1993. pp. 623 - 631, DOI: 10.1145/167088.167248
2. . Berman P., Charikar M., Karpinski M. On-line load balancing for related machines. LNCS, v. 1272, 1997, pp. 116-125, DOI: https://doi.org/10.1007/3-540-63307-3_52
3. . С.Н. Жук. О построении расписаний выполнения параллельных задач на гуппах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012, стр. 447-454, DOI: 10.15514/ISPRAS-2012-23-27
4. . S.N. Zhuk. Approximate algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol 18, issue 1, 2006, pp. 91-105, DOI: https://doi.org/10.1515/156939206776241264
5. . М.А. Трушников. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу. Труды ИСП РАН, том 22, 2012, стр. 456-462, DOI: 10.15514/ISPRAS-2012-22-24
6. . Лазарев Д. О., Кузюрин Н. Н. Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем. Труды ИСП РАН, том 29, вып. 6, 2017 г., стр. 221-228, DOI: 10.15514/ ISPRAS-2017-29(6)-13
7. . Трушников М. А. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу., Труды ИСП РАН, том 24, 2013, стр. 457-468, DOI: 10.15514/ISPRAS-2013-24-21
8. . Лазарев Д.О., Кузюрин Н.Н. Об онлайновых алгоритмах для задач упаковки в контейнеры и полосы, их анализе в худшем случае и в среднем. Труды ИСП РАН, том 30, вып. 4, 2018 г., стр. 209-230. DOI:10.15514/ISPRAS-2018-30(4)-14
9. . E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, L. A. McGeoch, P. W. Shor, R. R. Weber, M. Yannakakis. Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study. In Proc. of the twenty-third annual ACM Symposium on Theory of computing, 1991, pp. 230-240, doi:10.1145/103418.103446
10. . Кузюрин Н., Грушин Д., Фомин С. Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах. Труды ИСП РАН, том 26, вып. 1, 2014 г., стр. 483–502, DOI: 10.15514/ISPRAS-2014-26(1)-21
11. . Ye D., Han X., Zhang G. Online multiple-strip packing. Theoretical Computer Science, Volume 412, Issue 3, 2011, pp. 233-239. DOI: https://doi.org/10.1016/j.tcs.2009.09.29
12. . Жук С.Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности. Труды ИСП РАН, том 12, 2007 г., стр. 7-16, ISSN 2079-8056
13. . Zhuk S.N. On-line algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 17, issue 5, 2007, pp. 517-531. DOI: https://doi.org/10.1515/dma.2007.040
14. . Жук С.Н. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012 г., стр. 447-454. DOI: https://doi.org/10.15514/ISPRAS-2012-23-27
15. . Foster I., Kesselman C. The grid: Blueprint for a new computing infrastructure. Morgan Kaufmann Publishers Inc., 1999, 748 p.
Review
For citations:
Lazarev D.O., Kuzyurin N.N. On-line algorithm for scheduling parallel tasks on related computational clusters with processors of different capacities and its average-case analysis. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(6):105-122. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(6)-6
Email this article 