Allocation Optimization for Reducing Resource Utilization in Angara High-speed Interconnect
DOI:
https://doi.org/10.14529/cmse190101Keywords:
Angara interconnect, multidimensional torus, deterministic routing, direction ordered routing, fragmentation, allocationAbstract
This paper considers a high-speed interconnect with a multidimensional topology. The paper is devoted to the optimization of fragmentation resulting from sequential allocation of computing nodes in a supercomputer provided that network traffic from different user’s tasks should not overlap. This paper is the continuation of resources fragmentation optimization work. In this work, the method for scheduling tasks based on the policy of choosing the first suitable task (First-Fit) in a certain task window has been added to the accounting for fragmentation when choosing nodes. A set of different computer systems with three-dimensional and four-dimensional topologies was considered. The minimum system size is 32 computing nodes, and the maximum is 144. A synthetic queue of tasks is set for each system. The parameters of the synthetic queues are close to real ones and are based on data received from the Desmos cluster equipped with Angara interconnect. The average utilization of the resources of the computer system and the average waiting time for the tasks in the queue is chosen as a method quality criterion. Various sizes of task windows have been evalauated. The study showed that the increase of the resources utilization for the proposed method averaged 7 % compared to the base method, and the average time spent in queue was reduced by 36.6 %.
References
Agarkov A.A., Ismagilov T.F., Makagon D.V. Performance Evaluation of the Angara Interconnect. Superkomp’yuternye dni v Rossii: Trudy mezhdunarodnoi konferentsii (Moskva, 26–27 sentyabrya 2016) [Russian Supercomputing Days: Proceedings of the International Scientific Conference (Moscow, Russia, September, 26–27, 2016)]. Moscow, Publishing of Moscow State University, 2016. pp. 626–639. (in Russian)
Simonov A.S., Makagon D.V., Zhabin I.A., Shcherbak A.N., Syromyatnikov E.L., Polyakov D.A. The First Generation of Angara High-Speed Interconnect. Naukoemkie tekhnologii [Science Intensive Technologies]. 2014. vol. 15. no. 1. pp. 21–28. (in Russian)
Puente V., Beivide R., Gregorio J.A., Prellezo J.M., Duato J., Izu C. Adaptive Bubble Router: a Design to Improve Performance in Torus Networks. Proceedings of the International Conference Parallel Processing (ICPP). 1999. pp. 58–67. DOI: 10.1109/ICPP.1999.797388.
Adiga N.R., Blumrich M., Chen D.. Blue Gene/L Torus Interconnection Network. IBM Journal of Research and Development. 2005. vol. 49. no. 2. pp. 265–276. DOI: 10.1147/rd.492.0265.
Scott S.L., et al. The Cray T3E Network: Adaptive Routing in a High. Performance 3D Torus. 1996.
Pozhilov I.A., Semenov A.S., Makagon D.V., Connectivity Problem Solution for Direction Ordered Deterministic Routing in nD Torus. Software Engineering. 2015. no. 3. pp. 13–19. (in Russian)
Lan Z., Tang W., Wang J., Yang X., Zhou Z., Zheng X. Balancing job Performance with System Performance via Locality-aware Scheduling on Torus-connected Systems. 2014 IEEE International Conference on Cluster Computing (CLUSTER). 2014. pp. 140–148. DOI: 10.1109/CLUSTER.2014.6968751.
IBM Redbooks Publication: IBM System Blue Gene Solution: Blue Gene/Q system administration. 2013. 282 p.
Tang W., Lan Z., Desai N., Buettner D., Yu Y. Reducing Fragmentation on Torus-Connected Supercomputers. In Proceedings of the 2011 IEEE International Parallel Distributed Processing Symposium (IPDPS’11). IEEE Computer Society, Washington, DC, USA. 2011. pp. 828–839 DOI: 10.1109/IPDPS.2011.82.
Cray Document: Managing System Software for Cray XE and Cray XT Systems. 2010.
Schwiegelshohn U., Yahyapour R. Analysis of First-Come-First-Serve Parallel Job Scheduling. SODA. 1998. vol. 98. pp. 629–638.
Polezhaev P.N. The Study of Parallel Job Scheduling Algorithms for Cluster
Computing Systems Using a Simulator. Parallelnye vychislitelnye tekhnologii (PaVT’2010): Trudy mezhdunarodnoj nauchnoj konferentsii (Ufa, 29 marta–2 aprelya 2010) [Parallel Computational Technologies (PCT’2010): Proceedings of the International Scientific Conference (Ufa, Russia, March, 29–April, 2, 2010)]. Chelyabinsk, Publishing of the South Ural State University, 2010. pp. 287—298. (in Russian)
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. 2001. vol. 12. no. 6. pp. 529–543. DOI: 10.1109/71.932708.
Henderson R.L. Job Scheduling Under the Portable Batch System. Workshop on Job Scheduling Strategies for Parallel Processing. Springer, Berlin, Heidelberg, 1995. pp. 279–294.
Staples G. TORQUE Resource Manager. Proceedings of the 2006 ACM/IEEE conference on Supercomputing. ACM, 2006. pp. 8.
Jackson D., Snell Q., Clement M. Core Algorithms of the Maui Scheduler. Workshop on Job Scheduling Strategies for Parallel Processing. Springer, Berlin, Heidelberg, 2001. pp. 87–102.
Gentzsch W. Sun Grid Engine: Towards Creating a Compute Power Grid. Cluster Computing and the Grid, 2001. Proceedings. First IEEE/ACM International Symposium on. IEEE, 2001. pp. 35–36.
Baranov A.V., Smirnov S.V., Khramtsov M.Yu., Sharf S.V. Modernizatsiya SUPZ MVS-1000 [Modernization of the SUPZ MBS-1000]. Materialy Vserossiiskoi nauchnoi konferentsii “Nauchnyi servis v seti Internet” [Materials of the All-Russian Scientific Conference “Scientific Service on the Internet”]. Novorossiysk. 2008.
SchedMD L. L. C. SLURM Workload Manager. 2018. https://slurm.schedmd.com/overview.html (accessed: 20.09.2018)
Mukosey A.V., Semenov A.S. Allocation Optimization for Reducing Resource Fragmentation in Angara High-speed Interconnect. Parallelnye vychislitelnye tekhnologii (PaVT’2010): Trudy mezhdunarodnoj nauchnoj konferentsii (Rostov-na-Donu, aprel’ 2–6 2018) [Parallel Computational Technologies (PCT’2018): Proceedings of the International Scientific Conference (Rostov-na-Donu, Russia, April, 2–6, 2018)]. Chelyabinsk, Publishing of the South Ural State University, 2018. pp. 310–318. (in Russian)
Woo S.H. Task Scheduling in Distributed Computing Systems with a Genetic Algorithm. High Performance Computing on the Information Superhighway. 1997. HPC Asia’97. IEEE. 1997. pp. 301–305.
Vecher V.S., Kondratyuk N.D., Smirnov G.S., Stegailov V.V. Angara-based hybrid supercomputer for efficient acceleration of computational materials science studies. Superkomp’yuternye dni v Rossii: Trudy mezhdunarodnoj konferentsii (Moskva, sentyabr’ 25–26 2017) [Russian Supercomputing Days: Proceedings of the International Conference (Moscow, Russia, September, 25–26, 2017)]. Moscow, Publishing of Moscow State University, 2017. pp. 557–571. (in Russian)
Mukosey A.V., Semenov A.S. An Approximate Algorithm for Choosing the Optimal Subset of Nodes in the Angara Interconnect with Failures. Numerical methods and Programming. 2017. vol. 18. pp. 53–64. (in Russian)
Baranov A.V., Kiselev E.A., Lyakhovets D.S. The Quasi Scheduler for Utilization of Multiprocessing Computing System’s Idle Resources Under Control of the Management System of the Parallel Jobs. Vestnik Yuzho-Uralskogo gosudarstvennogo universiteta. Seriya “Matematicheskoe modelirovanie i programmirovanie” [Bulletin of South Ural State University. Series: Mathematical Modeling, Programming & Computer Software]. 2014. vol. 3. no. 4. pp. 75–84. (in Russian) DOI: 10.14529/cmse140405.
Gon¸calves J.F., Resende M.G.C. A Parallel Multi-Population Based Random-key Genetic Algorithm for a Container Loading Problem. Computers & Operations Research. February 2012. vol. 39. no. 2. pp. 179–190. DOI: 10.1016/j.cor.2011.03.009.
