Decomposition of a Surface Unstructured Computational Mesh for Scaling Computations on a Supercomputer
Abstract
Currently, when solving complex computational problems of computer modeling, computational grids containing tens and hundreds of millions of cells are used. To perform computations of such amount, it is required to use supercomputer clusters consisting of many computational nodes connected by a high-speed communication network. In this case, it is necessary to decompose the computational mesh into separate domains. These domains are distributed among the computational nodes of the supercomputer and are processed in parallel, independently of each other. To synchronize computations, after each iteration of cell processing, data exchanges are performed at the boundaries between adjacent contiguous domains. To efficiently perform computations and scale them to a large number of computational nodes, it is necessary to develop efficient algorithms for decomposition of computational meshes that generate many domains with imposed requirements for the number of cells, the uniformity of the distribution of cells across domains, the connectivity of domains and the size of boundaries between them. The article considers an unstructured surface mesh as an object of research, which is used to calculate the processes of interaction of a volumetric body with the environment. For a mesh of this type, various classes of decomposition algorithms are considered, and a hierarchical decomposition algorithm is proposed with the choice of the optimal criterion for partitioning domains. The proposed algorithm is implemented in the program code, the results of comparing the operation of this algorithm on test meshes with algorithms of other classes are presented.
References
[2] Schadt E., Linderman M., Sorenson J., Lee L., Nolan G.P. Computational solutions to large-scale data management and analysis. Nature Reviews Genetics. 2010; 11:647-657. (In Eng.) DOI: https://doi.org/10.1038/nrg2857
[3] Wright N.J., Dosanjh S.S., Andrews A.K. et al. Cori: A Pre-Exascale Supercomputer for Big Data and HPC Applications. In: Advances in Parallel Computing. Big Data and High Performance Computing. 2015; 26:82-100. (In Eng.) DOI: https://doi.org/10.3233/978-1-61499-583-8-82
[4] Golovchenko E., Dorofeeva E., Gasilova I., Boldareva A. Numerical Experiments with New Algorithms for Parallel Decomposition of Large Computational Meshes. In: Advances in Parallel Computing. Parallel Computing: Accelerating Computational Science and Engineering (CSE). 2014; 25:441-450. (In Eng.) DOI: https://doi.org/10.3233/978-1-61499-381-0-441
[5] Savin G.I., Benderskiy L.A., Lyubimov D.A., Rybakov A.A. RANS/ILES Method Optimization for Effective Calculations on Supercomuter. Lobachevskii Journal of Mathematics. 2019; 40(5):566-573. (In Eng.) DOI: https://doi.org/10.1134/S1995080219050172
[6] Dorris J., Kurzak J., Luszczek P., YarKhan A., Dongarra J. Task-Based Cholesky Decomposition on Knights Corner Using OpenMP. In: Taufer M., Mohr B., Kunkel J. (ed.) High Performance Computing. ISC High Performance 2016. Lecture Notes in Computer Science. 2016; 9945:544-562. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-46079-6_37
[7] Petrov M.N., Titarev V.A., Utyuzhnikov S.V., Chikitkin A.V. A multithreaded OpenMP implementation of the LU-SGS method using the multilevel decomposition of the unstructured computational mesh. Computational Mathematics and Mathematical Physics. 2017; 57(11):1895-1905. (In Eng.) DOI: https://doi.org/10.1134/S0965542517110124
[8] Shabanov B.M., Rybakov A.A., Shumilin S.S. Vectorization of High-performance Scientific Calculations Using AVX-512 Intruction Set. Lobachevskii Journal of Mathematics. 2019; 40(5):580-598. (In Eng.) DOI: https://doi.org/10.1134/S1995080219050196
[9] Krzikalla O., Wende F., Höhnerbach M. Dynamic SIMD Vector Lane Scheduling. In: Taufer M., Mohr B., Kunkel J. (eds) High Performance Computing. ISC High Performance 2016. Lecture Notes in Computer Science. 2016; 9945:354-365. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-46079-6_25
[10] Chunduri S., Parker S., Balaji P., Harms K., Kumaran K. Characterization of MPI Usage on a Production Supercomputer. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. Dallas, TX, USA; 2018. p. 386-400. (In Eng.) DOI: https://doi.org/10.1109/SC.2018.00033
[11] Ross J.A., Richie D.A., Park S.J., Shires D.R. Parallel Programming Model for the Epiphany Many-Core Coprocessor Using Threaded MPI. In: Proceedings of the 3rd International Workshop on Many-core Embedded Systems (MES '15). Association for Computing Machinery, New York, NY, USA; 2015. p. 41-47. (In Eng.) DOI: https://doi.org/10.1145/2768177.2768183
[12] Klenk B., Fröning H. An Overview of MPI Characteristics of Exascale Proxy Applications. In: Kunkel J., Yokota R., Balaji P., Keyes D. (ed.) High Performance Computing. ISC 2017. Lecture Notes in Computer Science. 2017; 10266:217-236. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-58667-0_12
[13] Benderskiy L.A., Lyubimov D.A., Rybakov A.A. Scaling of fluid dynamic calculations using the RANS/ILES method on supercomputer. Proceedings of NIISI RAS. 2017; 7(4):32-40. (In Russ., abstract in Eng.) DOI: https://doi.org/10.25682/NIISI.2018.4.9975
[14] Rybakov A.A. Raspredelenie vychislitel'noj nagruzki mezhdu uzlami geterogennogo vychislitel'nogo klastera [Distribution of computational load between nodes of a heterogeneous computational cluster]. Software Journal: Theory and Applications. 2018; (1):26-32. (In Russ., abstract in Eng.) DOI: https://doi.org/10.15827/2311-6749.26.300
[15] Rybakov A. A. Inner representation and crossprocess exchange mechanism for block-structured Grid for supercomputer calculations. Program Systems: Theory and Applications. 2017; 8(1):121-134. (In Russ., abstract in Eng.) DOI: https://doi.org/10.25209/2079-3316-2017-8-1-121-134
[16] Farhat C. A simple and efficient automatic fem domain decomposer. Computers & Structures. 1988; 28(5):579-602. (In Eng.) DOI: https://doi.org/10.1016/0045-7949(88)90004-1
[17] Preis R., Diekmann R. PARTY - a Software Library for Graph Partitioning. In: Topping B.H.V. (ed.) Advances in Computational Mechanics for Parallel and Distributed Processing. Civil-Comp Press, Edinburgh, UK; 1997. p. 63-71. (In Eng.) DOI: https://doi.org/10.4203/ccp.45.3.1
[18] Yakobovskii M.V. Inkremental'nyj algoritm dekompozicii grafov [An incremental algorithm for graph decomposition]. Vestn. Nizhegorod. Univ. im. N.I. Lobachevskogo. Ser. Mat. Model. Optim. Upr. 2005; (1):243-250. (In Russ.)
[19] Urschel J.C., Zikatanov L.T. Spectral bisection of graphs and connectedness. Linear Algebra and its Applications. 2014; 449:1-16. (In Eng.) DOI: https://doi.org/10.1016/j.laa.2014.02.007
[20] Zhao L., Liu Y., Zhang C., Zhang X. Automatic optimal block decomposition for structured mesh generation using genetic algorithm. Journal of the Brazilian Society of Mechanical Sciences and Engineering. 2019; 41(1):10. (In Eng.) DOI: https://doi.org/10.1007/s40430-018-1510-0
[21] Karypis G., Kumar V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing. 1998; 20(1):359-392. (In Eng.) DOI: https://doi.org/10.1137/S1064827595287997
[22] Golovchenko E.N. Obzor algoritmov dekompozicii grafov [Survey of graph partitioning algorithms]. Keldysh Institute PREPRINTS. 2020; (2):1-38. (In Russ., abstract in Eng.) DOI: https://doi.org/10.20948/prepr-2020-2
[23] Zheleznyakova A.L. Load Balancing Methods for Molecular Dynamics Applications. Physical-Chemical Kinetics in Gas Dynamics. 2017; 18(1):1-20. Available at: https://www.elibrary.ru/item.asp?id=35136792 (accessed 16.09.2020). (In Russ., abstract in Eng.)
[24] Li S., Qin J., He M., Paoli R. Fast Evaluation of Aircraft Icing Severity Using Machine Learning Based on XGBoost. Aerospace. 2020; 7(4):36. (In Eng.) DOI: https://doi.org/10.3390/aerospace7040036
[25] Bourgault-Côté S., Hasanzadeh K., Lavoie P., Laurendeau E. Multi-Layer Icing Methodologies for Conservative Ice Growth. In: 7th European Conference for Aeronautics and Aerospace Sciences (EUCASS). 2017. (In Eng.) DOI: https://doi.org/10.13009/EUCASS2017-258
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
