Allocation Optimization for Reducing Resource Fragmentation in Angara High-Speed Interconnect
DOI:
https://doi.org/10.14529/cmse180204Keywords:
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 compute nodes in a supercomputer provided that network traffic from different user’s tasks should not overlap. This paper proposes a method for searching nodes with an evaluation of the fragmentation of the system based on ideas from multidimensional container loading problem. For such an evaluation, the concept of rectangles is introduced, which can be inscribed into the system after placing the next user task. Each set of nodes that is suitable for placing the task is evaluated by the proposed function taking into account the size and the number of found rectangles of maximum size. The proposed method was evaluated using computer system model. A set of different computer systems with three-dimensional and four-dimensional topologies was considered. The minimum system size is 32 compute 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 a real ones. 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. The study showed that the increase of the resources utilization for the proposed method averaged 11% compared to the base method, and the average time spent in queue is reduced by 45,3%.
References
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) (Madrid, Spain, September 22–26, 2014). 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. Proceedings of the 2011 IEEE International Parallel Distributed Processing Symposium (IPDPS’11) (Anchorage, Alaska, USA, May 16–20, 2011), 2011. pp. 828–839. DOI: 10.1109/IPDPS.2011.82.
Cray Document: Managing System Software for Cray XE and Cray XT Systems. 2010.
Agarkov A.A., Ismagilov T.F., Makagon D.V. Performance Evaluation of the Angara Interconnect. Supercomputernie dni v Rossii: Trudy meghdunarodnoj konferentsii (Moscva, 26–27 sentyabra 2016) [Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, Russia, September 26–27, 2016)]. Moscow, Publishing House 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 technologii [Science 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 (Wakamatsu, Japan, September 21–24, 1999), 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. Programmnaya inzheneriya [Software Engineering]. 2015. no. 3. pp. 13–19. (in Russian)
Kagirov R.R. Multiple Knapsack Problem: New Solving Methods. Vestnik SibGAU [Vestnik of the Reshetnev Siberian State Aerospace University]. 2007. no. 3. pp. 16–20. (in Russian)
Gonçalves 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.
Mukosey A.V., Semenov A.S. An Approximate Algorithm for Choosing the Optimal Subset of Nodes in the Angara Interconnect with Failures. Vyichislitelnyie metodyi i programmirovanie [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 Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Vychislitelnaya Matematika i Informatika" [Bulletin of South Ural State University. Series: Computational Mathematics and Software Engineering]. 2014. vol. 3, no. 4. pp. 75–84. DOI: 10.14529/cmse140405. (in Russian)
Polezhaev P.N. Simulator of computer cluster and its management system used for research of job scheduling algorithms. Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Matematicheskoe Modelirovanie i Programmirovanie" [Bulletin of South Ural State University. Series: Mathematical Modeling, Programming & Computer Software]. 2010. vol. 6. pp. 79–90. (in Russian)
