Geodesic
Allocation optimization for reducing resource fragmentation in angara high-speed interconnect
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 2, pp. 50-62 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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%.
Keywords: Angara interconnect, deterministic routing, direction ordered routing, allocation.
Mots-clés : multidimensional torus, fragmentation 
@article{VYURV_2018_7_2_a3,
     author = {A. V. Mukosey and A. S. Semenov},
     title = {Allocation optimization for reducing resource fragmentation in angara high-speed interconnect},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {50--62},
     year = {2018},
     volume = {7},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a3/}
}
TY  - JOUR
AU  - A. V. Mukosey
AU  - A. S. Semenov
TI  - Allocation optimization for reducing resource fragmentation in angara high-speed interconnect
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2018
SP  - 50
EP  - 62
VL  - 7
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a3/
LA  - ru
ID  - VYURV_2018_7_2_a3
ER  - 
%0 Journal Article
%A A. V. Mukosey
%A A. S. Semenov
%T Allocation optimization for reducing resource fragmentation in angara high-speed interconnect
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2018
%P 50-62
%V 7
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a3/
%G ru
%F VYURV_2018_7_2_a3
A. V. Mukosey; A. S. Semenov. Allocation optimization for reducing resource fragmentation in angara high-speed interconnect. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 2, pp. 50-62. http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a3/

[1] Z. Lan, W. Tang, J. Wang, X. Yang, Z. Zhou, X. Zheng, “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, 22–26 | DOI

[2] IBM Redbooks Publication: IBM System Blue Gene Solution: Blue Gene/Q System Administration, 2013, 282 pp.

[3] W. Tang, Z. Lan, N. Desai, D. Buettner, Y. Yu, “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, 16–20 | DOI

[4] Cray Document: Managing System Software for Cray XE and Cray XT Systems, 2010

[5] A. A. Agarkov, T. F. Ismagilov, D. V. Makagon, “Performance Evaluation of the Angara Interconnect”, Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, Russia, September 26–27, 2016), Publishing House of Moscow State University, Moscow, 2016, 626–639

[6] A. S. Simonov, D. V. Makagon, I. A. Zhabin, A. N. Shcherbak, E. L. Syromyatnikov, D. A. Polyakov, “The First Generation of Angara High-Speed Interconnect”, Science Technologies, 15:1 (2014), 21–28

[7] V. Puente, R. Beivide, J. A. Gregorio, J. M. Prellezo, J. Duato, C. Izu, “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, 21–24 | DOI

[8] N. R. Adiga, M. Blumrich, D. Chen, “Blue Gene/L Torus Interconnection Network”, IBM Journal of Research and Development, 49:2 (2005), 265–276 | DOI

[9] S. L. Scott, The Cray T3E Network Adaptive Routing in a High Performance 3D Torus, 1996

[10] I. A. Pozhilov, A. S. Semenov, D. V. Makagon, “Connectivity Problem Solution for Direction Ordered Deterministic Routing in nD Torus”, Software Engineering, 2015, no. 3, 13–19

[11] R. R. Kagirov, “Multiple Knapsack Problem: New Solving Methods”, Vestnik of the Reshetnev Siberian State Aerospace University, 2007, no. 3, 16–20

[12] J. F. Gonçalves, M. G. Resende, “A Parallel Multi-population Biased Random-key Genetic Algorithm for a Container Loading Problem”, Computers Operations Research. February 2012. Vol, 39:2 (2), 179–190 | DOI

[13] A. V. Mukosey, A. S. Semenov, “An Approximate Algorithm for Choosing the Optimal Subset of Nodes in the Angara Interconnect with Failures”, Numerical methods and Programming, 18:1 (2017), 53–64

[14] A. V. Baranov, E. A. Kiselev, D. S. Lyakhovets, “The Quasi Scheduler for Utilization of Multiprocessing Computing System’s Idle Resources under Control of the Management System of the Parallel Jobs”, Bulletin of South Ural State University. Series: Compuational Mathematics and Software Engineering, 3:4 (2014), 75–84 | DOI

[15] P. N. Polezhaev, “Simulator of Computer Cluster and Its Management System Used for Research of Job Scheduling Algorithms”, Bulletin of South Ural State University. Series: Mathematical Modeling, Programming Computer Software, 6:35 (2010), 79–90