Декомпозиция поверхностной неструктурированной расчетной сетки для масштабирования вычислений на суперкомпьютере
Аннотация
В настоящее время при решении сложных вычислительных задач компьютерного моделирования используются расчетные сетки, содержащие десятки и сотни миллионов ячеек. Для выполнения вычислений такого объема требуется использование суперкомпьютерных кластеров, состоящих из многих вычислительных узлов, связанных между собой высокоскоростной коммуникационной сетью. При этом необходимо выполнять декомпозицию расчетной сетки на отдельные домены. Эти домены распределяются по вычислительным узлам суперкомпьютера и обрабатываются параллельно, независимо друг от друга. Для синхронизации вычислений после каждой итерации обработки ячеек производятся обмены данными на границах между соседними соприкасающимися доменами. Для эффективности выполнения вычислений и масштабирования их на большое количество вычислительных узлов требуется разработка эффективных алгоритмов декомпозиции расчетных сеток, порождающих множество доменов с накладываемыми на них требованиями по количеству ячеек, равномерности распределения ячеек по доменам, связности доменов и размеру границ между ними. В статье в качестве объекта исследования рассматривается неструктурированная поверхностная сетка, используемая для расчета процессов взаимодействия объемного тела с окружающей средой. Для сетки такого вида рассматриваются различные классы алгоритмов декомпозиции и предлагается иерархический алгоритм декомпозиции с выбором оптимального критерия разбиения доменов. Предложенный алгоритм реализован в программном коде, приводятся результаты сравнения работы данного алгоритма на тестовых сетках с алгоритмами других классов.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
