On an effective scheduling problem in computation clusters
https://doi.org/10.15514/ISPRAS-2018-30(6)-7
Abstract
At present, big companies such as Amazon, Google, Facebook, Microsoft, Yahoo! own huge datacenters with thousands of nodes. These clusters are used simultaneously by many users. The users submit jobs containing one or more tasks. Task flow is usually a mix of short, long, interactive, batch, and tasks with different priorities. Cluster scheduler decides on which server to run the task, where the task is then run as a process, container or a virtual machine. Scheduler optimizations are important as they provide higher server utilization, lower latency, improved load balancing, and fault tolerance. Achieving good task placement is hard. The problem has multiple dimensions and requires algorithmically complex optimizations. This increases placement latency and limits cluster scalability. In this paper we consider different cluster scheduler architectures and optimization problems.
About the Authors
D. A. Grushin
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
Russian Federation
Russian Federation
References
1. [1] Sinnen O. Task scheduling for parallel systems. John Wiley & Sons, 2007, 30 p.
2. [2] Verma A., Pedrosa L., Korupolu M. et al. Large-scale cluster management at google with borg. In Proc. of the Tenth European conference on computer systems, 2015, pp. 18:1–18:17.
3. [3] Ehrgott M. Multicriteria optimization. Springer, 2005, 320 p.
4. [4] Аветисян А., Грушин Д., Рыжов А. Системы управления кластерами. Труды ИСП РАН, том 3, 2002, стр. 39–62.
5. [5] Message P Forum. MPI: A message-passing interface standard. Technical Report. University of Tennessee, Knoxville, 1994, 228 p.
6. [6] Kaplan Joseph A., Nelson Michael L. A comparison of queueing, cluster and distributed computing systems. NASA Langley Technical Report, 1994, 49 p.
7. [7] Baker M., Fox G., Yau H. A review of commercial and research cluster management software. Northeast Parallel Architectures Center, 1996, 63 p.
8. [8] Foster I., Kesselman C. The grid: Blueprint for a new computing infrastructure. Morgan Kaufmann Publishers Inc., 1999, 675 p.
9. [9] Boutin E., Ekanayake J., Lin W. et al. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In Proc. of the 11th USENIX conference on Operating Systems Design and Implementation, 2014. pp. 285–300.
10. [10] Delgado P., Dinu F., Kermarrec A.-M. et al. Hawk: Hybrid datacenter scheduling. In Proc. of the 2015 USENIX annual technical conference, 2015.
11. [11] Schwarzkopf M. Cluster scheduling for data centers. Queue, vol. 15, no. 5, 2017.
12. [12] Herbein S., Dusia A., Landwehr A. et al. Resource management for running hpc applications in container clouds. Lecture Notes in Computer Science, vol. 9697, 2016. pp. 261–278.
13. [13] Ye D., Han X., Zhang G. Online multiple-strip packing. Theoretical Computer Science, vol. 412, no. 3, 2011, pp. 233–239.
14. [14] Hurink J. L., Paulus J. J. Online algorithm for parallel job scheduling and strip packing. Lecture Notes in Computer Science, vol. 4927, 2007. pp. 67–74.
15. [15] Zhuk S. On-line algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 17, no. 5, 2007, pp. 517–531.
16. [16] Johnson D. S., Demers A., Ullman J. D. et al. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on computing, vol. 3, no. 4, 1974, pp. 299–325.
17. [17] Garey M. R., Graham R. L., Johnson D. S. et al. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, vol. 21, no. 3, 1976, pp. 257–298.
18. [18] Zhuk S., Chernykh A., Avetisyan A. et al. Comparison of scheduling heuristics for grid resource broker. In Proc. of the Fifth Mexican International Conference, 2004, pp. 388–392.
19. [19] Tchernykh A., Ramı́rez-Alcaraz J. M., Avetisyan A. et al. Two level job-scheduling strategies for a computational grid. Lecture Notes in Computer Science, vol. 3911, 2005. pp. 774–781.
20. [20] Tchernykh A., Schwiegelshohn U., Yahyapour R. et al. On-line hierarchical job scheduling on grids with admissible allocation. Journal of Scheduling, vol. 13, no. 5, 2010, pp. 545–52.
21. [21] Tchernykh A., Schwiegelshohn U., Yahyapour R. et al. Online hierarchical job scheduling on grids. In From grids to service and pervasive computing, Springer, 2008, pp. 77–91.
22. [22] Avetisyan A.I., Gaissaryan S.S., Grushin D.A. et al. Scheduling heuristics for grid resource broker. Trudy ISP RAN/Proc. ISP RAS, vol. 5, 2004, pp. 41–62 (in Russian).
23. [23] Baraglia R., Capannini G., Pasquali M. et al. Backfilling strategies for scheduling streams of jobs on computational farms. In Making Grids Work, Springer, 2008, pp. 103–115.
24. [24] Mu’alem A.W., Feitelson D.G. Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling. IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 6, 2001, pp. 529–543.
25. [25] Nissimov A., Feitelson D.G. Probabilistic backfilling. Lecture Notes in Computer Science, vol. 4942, 2008. pp. 102–115.
26. [26] Ivannikov V.P., Grushin D.A., Kuzyurin N.N., Pospelov A.I., Shokurov A.V. Software for improving the energy efficiency of a computer cluster. Programming and Computer Software, vol. 36, no. 6, 2010, pp. 327-336.
27. [27] Baraglia R., Capannini G., Dazzi P. et al. A multi-criteria job scheduling framework for large computing farms. Journal of Computer and System Sciences, vol. 79, no. 2, 2013, pp. 230–244.
28. [28] Csirik J., Van Vliet A. An on-line algorithm for multidimensional bin packing. Operations Research Letters, vol. 13, no. 3, 1993, pp. 149–158.
29. [29] Kuzjurin N.N., Pospelov A.I. Probabilistic analysis of a new class of rectangle strip packing algorithms. Computational Mathematics and Mathematical Physics, vol. 51, no. 10, 2011, pp. 1931–1936.
30. [30] Trushnikov M.A. Probabilistic analysis of a new rectangle strip packing algorithm. Trudy ISP RAN/Proc. ISP RAS, vol. 24, 2013, pp. 457-468 (in Russian). DOI: 10.15514/ISPRAS-2013-24-21.
31. [31] Lazarev D.O., Kuzjurin N.N. Rectangle packing algorithm into several strips and average case analisys. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 6, 2017, pp. 221–228 (in Russian). DOI: 10.15514/ISPRAS-2017-29(6)-13.
32. [32] Zhuk S. On parallel task scheduling on a group of clusters with different speeds. Trudy ISP RAN/Proc. ISP RAS, vol. 23, 2012, pp. 447-454. DOI: 10.15514/ISPRAS-2012-23-27.
33. [33] Tsai C.-W., Rodrigues J. J. Metaheuristic scheduling for cloud: A survey. IEEE Systems Journal, vol. 8, no. 1, 2014, pp. 279–291.
34. [34] Grushin D.A., Kuzjurin N.N. Energy effective computations on a group of clusters. Trudy ISP RAN/Proc. ISP RAS, vol. 23, 2012, pp. 433–46 (in Russian). DOI: 10.15514/ISPRAS-2012-23-26.
35. [35] Goldberg R.P. Distributed, low latency scheduling. In Proc. of the twenty-fourth ACM Symposium on operating systems principles, 2013, pp. 69–84.
36. [36] Magic Quadrant for Cloud Infrastructure as a Service, Worldwide. Available at: https://www.gartner.com/doc/3875999/magic-quadrant-cloud-infrastructure-service. Accessed 01.12.2018.
37. [37] Helsley M. LXC: Linux container tools. IBM devloperWorks Technical Library, 2009.
38. [38] Merkel D. Docker: Lightweight linux containers for consistent development and deployment. Linux Journal, no. 239, 2014.
39. [39] Barroso L. A., Clidaras J., Hoelzle U. The datacenter as a computer: An introduction to the design of warehouse-scale machines. Morgan & Claypool, 2013, 154 p.
40. [40] Delimitrou C., Kozyrakis C. Paragon: QoS-aware scheduling for heterogeneous datacenters. ACM SIGPLAN Notices, vol. 48, no. 4, 2013, pp. 77–88.
41. [41] Delimitrou C., Kozyrakis C. Quasar: Resource-efficient and qos-aware cluster management, ACM SIGPLAN Notices, vol. 49, no. 4, 2014, pp. 127–144.
42. [42] Romero F., Delimitrou C. Mage: Online and interference-aware scheduling for multi-scale heterogeneous systems. In Proc. of the 27th international conference on parallel architectures and compilation techniques, 2018, pp. 19:1–19:13.
43. [43] Gog I., Schwarzkopf M., Gleave A. et al. Firmament: Fast, centralized cluster scheduling at scale. In Proc. of the 12th usenix conference on operating systems design and implementation, 2016, pp. 99–115.
44. [44] Breitgand D., Epstein A. Improving consolidation of virtual machines with risk-aware bandwidth oversubscription in compute clouds. In Proc. of the IEEE INFOCOM, 2012. pp. 2861–2865.
45. [45] Wang M., Meng X., Zhang L. Consolidating virtual machines with dynamic bandwidth demand in data centers. In Proc. of the IEEE INFOCOM, 2011. pp. 71–75.
46. [46] Urgaonkar B., Shenoy P., Roscoe T. Resource overbooking and application profiling in shared hosting platforms. In Proc. of the 5th symposium on operating systems design and implementation, 2002. pp. 239–254.
47. [47] Hindman B., Konwinski A., Zaharia M. et al. Mesos: A platform for fine-grained resource sharing in the data center. In Proc. of the 8th USENIX conference on Networked systems design and implementation, 2011. pp. 295-308.
48. [48] Vavilapalli V. K., Murthy A. C., Douglas C. et al. Apache hadoop yarn: Yet another resource negotiator. In Proc. of the 4th annual symposium on cloud computing, 2013, pp. 5:1–5:16.
49. [49] Schwarzkopf M., Konwinski A., Abd-El-Malek M. et al. Omega: Flexible, scalable schedulers for large compute clusters. In Proc. of the 8th ACM European conference on computer systems, 2013. pp. 351–364.
50. [50] Scheduling in Nomad. Available at: https://www.nomadproject.io/docs/internals/scheduling.html. Accessed 01.12.2018.
51. [51] Mitzenmacher M. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 10, 2001, pp. 1094–1104.
52. [52] Ousterhout K., Wendell P., Zaharia M. et al. Sparrow: Distributed, low latency scheduling. In Proc. of the twenty-fourth ACM Symposium on operating systems principles, 2013, pp. 69–84.
53. [53] Fagin R., Williams J. H. A fair carpool scheduling algorithm. IBM Journal of Research and development, vol. 27, no. 2, 1983, pp. 133–139.
54. [54] Delimitrou C., Sanchez D., Kozyrakis C. Tarcil: Reconciling scheduling speed and quality in large shared clusters. In Proc. of the sixth ACM Symposium on cloud computing, 2015, pp. 97–110.
55. [55] Karanasos K., Rao S., Curino C. et al. Mercury: Hybrid centralized and distributed scheduling in large shared clusters. In Proc. of the USENIX annual technical, 2015. pp. 485–497.
56. [56] Delgado P., Dinu F., Kermarrec A.-M. et al. Hawk: Hybrid datacenter scheduling In Proc. of the USENIX annual technical conference, 2015. pp. 499–510.
57. [57] The Open Container Initiative. Available at: https://www.opencontainers.org/, accessed 01.12.2018.
58. [58] Avetisyan A.A., Gaissaryan S.S., Samovarov O.I. et al. Organization of scientific centers in univercity cluster program. In Proc. of the All-Russian Conference on Scientific service in Internet: Supercomputer centers and problems, 2010, pp. 213–215 (in Russian).
59. [59] Samovarov O.I., Gaissaryan S.S. Architecture and implementation details of Unihub platform in cloud computing architecture based on Openstack package. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 1, 2014, pp. 403-420 (in Russian). DOI: 10.15514/ISPRAS-2014-26(1)-17.
60. [60] Grushin D.A., Kuzyurin N.N. Load balancing in unihub saas system based on user behavior prediction. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 5, 2015, pp. 23–34 (in Russian). DOI: 10.15514/ISPRAS-2015-27(5)-2.
61. [61] Grushin D.A., Kuzyurin N.N. Optimization problems running mpi-based hpc applications. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 6, 2017, pp. 229–244 (in Russian). DOI: 10.15514/ISPRAS-2017-29(6)-14.
Review
For citations:
Grushin D.A., Kuzyurin N.N. On an effective scheduling problem in computation clusters. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(6):123-142. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(6)-7
Email this article 