О задаче эффективного управления вычислительной инфраструктурой
https://doi.org/10.15514/ISPRAS-2018-30(6)-7
Аннотация
В настоящее время такие компании как Amazon, Google, Facebook, Microsoft, Yahoo! и другие управляют огромными дата-центрами из десятков тысяч узлов. Эти кластеры используются одновременно многими организациями и пользователями (облачная модель вычислений). Пользователи запускают задания, каждое из которых может состоять из одной или нескольких параллельных задач. Поток задач обычно представляет собой смесь: коротких, долгих, интерактивных, пакетных, и задач с различным приоритетом. Планировщик кластера решает, как разместить эти задачи на узлах, где они запускаются в виде процессов, контейнеров или виртуальных машин. Оптимизация размещения задач планировщиком позволяет улучшить степень использования узлов (machine utilization), сократить время отклика, сбалансировать нагрузку на части кластера, получить предсказуемую производительность приложений, повысить отказоустойчивость. Получить оптимальное размещение сложно. Для этого требуется решить задачу многокритериальной оптимизации, что требует времени. Это приводит к задержке при размещении очередной задачи, негативно сказывается на времени отклика и пропускной способности. С ростом размеров кластера и потока задач удовлетворить оба данных критерия становится сложным, и необходимо отдавать приоритет только одному. В данной статье мы рассмотрим архитектуру современных планировщиков и математические постановки задачи оптимизации.
Об авторах
Д. А. Грушин
Институт системного программирования им. В.П. Иванникова РАН
Россия
Россия
Н. Н. Кузюрин
Институт системного программирования им. В.П. Иванникова РАН; Московский физико-технический институт
Россия
Россия
Список литературы
1. Sinnen O. Task scheduling for parallel systems. John Wiley & Sons, 2007, 30 p.
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. Ehrgott M. Multicriteria optimization. Springer, 2005, 320 p.
4. Аветисян А., Грушин Д., Рыжов А. Системы управления кластерами. Труды ИСП РАН, том 3, 2002, стр. 39–62.
5. Message P Forum. MPI: A message-passing interface standard. Technical Report. University of Tennessee, Knoxville, 1994, 228 p.
6. Kaplan Joseph A., Nelson Michael L. A comparison of queueing, cluster and distributed computing systems. NASA Langley Technical Report, 1994, 49 p.
7. Baker M., Fox G., Yau H. A review of commercial and research cluster management software. Northeast Parallel Architectures Center, 1996, 63 p.
8. Foster I., Kesselman C. The grid: Blueprint for a new computing infrastructure. Morgan Kaufmann Publishers Inc., 1999, 675 p.
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. Delgado P., Dinu F., Kermarrec A.-M. et al. Hawk: Hybrid datacenter scheduling. In Proc. of the 2015 USENIX annual technical conference, 2015.
11. Schwarzkopf M. Cluster scheduling for data centers. Queue, vol. 15, no. 5, 2017.
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. Ye D., Han X., Zhang G. Online multiple-strip packing. Theoretical Computer Science, vol. 412, no. 3, 2011, pp. 233–239.
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. Zhuk S. On-line algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 17, no. 5, 2007, pp. 517–531.
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. 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. 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. 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. 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. 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. Аветисян А.И., Гайсарян С.С., Грушин Д.А., Кузюрин Н.Н., Шокуров А.В. Эвристики распределения задач для брокера ресурсов Grid. Труды ИСП РАН, том 5, 2004, стр. 41–62.
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. 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. Nissimov A., Feitelson D.G. Probabilistic backfilling. Lecture Notes in Computer Science, vol. 4942, 2008. pp. 102–115.
26. Иванников В.П., Грушин Д.А., Кузюрин Н.Н. и др. Программная система увеличения энергоэффективности вычислительного кластера. Программирование, том 36, no. 6, 2010, pp. 28–40.
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. 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. Кузюрин Н.Н., Поспелов А.И. Вероятностный анализ нового класса алгоритмов упаковки прямоугольников в полосу. Журнал вычислительной математики и математической физики, том 51, No. 10, 2011, стр. 1931–1936.
30. Трушников М.А. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу. Труды ИСП РАН, том 24, 2013, стр. 457-468. DOI: 10.15514/ISPRAS-2013-24-21.
31. Лазарев Д.О., Кузюрин Н.Н. Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем. Труды ИСП РАН, том 29, вып. 6, 2017, стр. 221–228. DOI: 10.15514/ISPRAS-2017-29(6)-13.
32. Жук С.Н. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012, стр. 447-454. DOI: 10.15514/ISPRAS-2012-23-27.
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. Грушин Д.А., Кузюрин Н.Н. Энергоэффективные вычисления для группы кластеров. Труды ИСП РАН, том 23, 2012, стр. 433–46. DOI: 10.15514/ISPRAS-2012-23-26.
35. Goldberg R.P. Survey of virtual machine research. Computer, vol. 7, no. 9, 1974, pp. 34–45.
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. Helsley M. LXC: Linux container tools. IBM devloperWorks Technical Library, 2009.
38. Merkel D. Docker: Lightweight linux containers for consistent development and deployment. Linux Journal, no. 239, 2014.
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. Delimitrou C., Kozyrakis C. Paragon: QoS-aware scheduling for heterogeneous datacenters. ACM SIGPLAN Notices, vol. 48, no. 4, 2013, pp. 77–88.
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. 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. 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. 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. 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. 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. 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. 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. 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. Scheduling in Nomad. Available at: https://www.nomadproject.io/docs/internals/scheduling.html. Accessed 01.12.2018.
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. 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. 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. 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. 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. 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. The Open Container Initiative. Available at: https://www.opencontainers.org/, accessed 01.12.2018.
58. Аветисян А.А., Гайсарян С.С., Самоваров О.И. и др. Организация предметно-ориентированных научно-исследовательский центров в рамках программы университетский кластер. Труды конференции «Научный сервис в сети интернет: Суперкомпьютерные центры и задачи», 2010, стр. 213–5.
59. Самоваров О.И., Гайсарян С.С. Архитектура и особенности реализации платформы unihub в модели облачных вычислений на базе открытого пакета openstack. Труды ИСП РАН, том 26, вып. 1, 2014, стр. 403-420. DOI: 10.15514/ISPRAS-2014-26(1)-17.
60. Грушин Д.А., Кузюрин Н.Н. Балансировка нагрузки в системе Unihub на основе предсказания поведения пользователей. Труды ИСП РАН, том 27, вып. 5, 2015, стр. 23-34. DOI: 10.15514/ISPRAS-2015-27(5)-2.
61. Грушин Д.А., Кузюрин Н.Н. Задачи оптимизации размещения контейнеров MPI-приложений на вычислительных кластерах. Труды ИСП РАН, том 29, вып. 6, 2017, стр. 229–244. DOI: 10.15514/ISPRAS-2017-29(6)-14.
Рецензия
Для цитирования:
Грушин Д.А., Кузюрин Н.Н. О задаче эффективного управления вычислительной инфраструктурой. Труды Института системного программирования РАН. 2018;30(6):123-142. https://doi.org/10.15514/ISPRAS-2018-30(6)-7
For citation:
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
Послать статью по эл. почте 