多层直角网格划分算法研究及其在CFD软件中的应用

计算流体力学（Computational Fluid Dynamics）是在20世纪60年代随着计算机技术的发展而兴起的学科。随着CFD在工业领域的广泛应用和对模拟精度的追求，单CPU的计算已不足以满足需求，必须引入并行计算。在并行CFD中，网格划分至关重要。由于网格的种类复杂多样，CFD软件开发中需要根据具体的网格结构，采用合适的网格划分算法。

多层直角网格是一种用于CFD模拟的网格类型，通常用于处理复杂的几何形状，并在流体域中生成结构化的网格。这种类型的网格通常包含多个层次，每个层次都以直角网格的形式构建。在划分多层直角网格时，由于其结构比单层直角网格更复杂，划分的约束条件更多，故常用的结构网格划分算法不能满足其所有约束条件。为了提高CFD软件性能，不能直接采用时间复杂度较高的非结构网格划分算法。因此多层直角网格的划分算法成为了CFD软件开发中的一个难题。

本文选取几何划分类的RCB（Recursive Coordinate Bisection）算法和图划分类的LDG（Linear Deterministic Greedy）算法，设计了简易的网格划分系统，主要分为网格生成、网格划分和网格可视化三部分。测试了这些算法在单层直角网格划分中的性能，为后续CFD网格划分模块开发做准备。根据测试结果，选择了基于RCB算法改进的NG（Naive Greedy）算法作为多层直角网格划分的主要算法。此算法在负载均衡、空间局部性和时间性能上均有良好表现。

在设计多层直角网格划分时，基于NG算法提出了几种可行的思路，并实现了其中一种，称为MGD（Multilayer Global Division）算法。通过子层网格与父层网格间的相互转换，将多层网格映射到单层，并使用NG算法划分映射后的网格，划分完成后再将网格还原。使用模型的STL文件作为输入，采用原软件设计的网格生成模块，生成多层直角网格，划分后的结果表明，多层网格满足整体负载均衡和空间局部性条件，但每个单层的负载均衡较差，需要进一步改进算法。

为解决前一种划分算法的不足，通过结合NG算法和LDG算法以及K-L（Kernighan-Lin）算法，提出了解决多层直角网格划分的新算法——CMD（Constraint Multilayer Division）算法。采用NG算法划分最密层的单层网格，再将子层网格的划分结果作为父层划分的约束条件，运用LDG算法的评估划分机制得到约束划分的初步结果，这一阶段称为网格约束的粗划分阶段。使用K-L算法的优化思路，在损失小部分空间局部性的代价下，获得了每层网格更好的负载均衡，这一阶段称为网格约束的细划分阶段。划分后的结果表明，这种新算法满足了多层直角网格划分的整体负载均衡和空间局部性，以及各单层内部的负载均衡和空间局部性等多项条件。最终这种多层直角网格划分算法成功应用在了CFD软件中。

Computational Fluid Dynamics is a discipline that emerged with the development of computer technology in the 1960s. With the widespread application of CFD in the industrial field and the pursuit of simulation accuracy, the calculation of a single CPU is no longer enough to meet the demand, and parallel computing must be introduced. In parallel CFD, meshing is crucial. Due to the complexity and variety of grid types, CFD software development needs to use appropriate mesh partition algorithms based on the specific grid structure.

Multilayer Cartesian mesh is a mesh type used in CFD simulations, often used to handle complex geometries and generate structured meshes in fluid domains. This type of grid usually contains multiple levels, each level being constructed in the form of a rectangular grid. When dividing multi-layer rectangular grids, since their structures are more complex than single-layer rectangular grids and have more constraints, commonly used structural meshing algorithms cannot satisfy all of their constraints. In order to improve the performance of CFD software, unstructured meshing algorithms with high time complexity cannot be directly used. Therefore, the division algorithm of multi-layer rectangular grid has become a difficult problem in CFD software development.

In this paper, a simple meshing system is designed by selecting the Recursive Coordinate Bisection algorithm for geometric division and the Linear Deterministic Greedy algorithm for graph partitioning, which is mainly divided into three parts: mesh generation, meshing and meshing visualization. The performance of these algorithms in single-layer right-angle meshing was tested to prepare for the subsequent development of CFD meshing module. According to the test results, the improved Naive Greedy algorithm based on RCB algorithm was selected as the main algorithm for multi-layer Cartesian meshing. This algorithm has good performance in load balancing, spatial locality, and temporal performance.

In the design of multi-layer Cartesian meshing, several feasible ideas were proposed based on the NG algorithm, and one of them was implemented, which was called the Multilayer Global Division algorithm. Through the mutual conversion between the child layer mesh and the parent layer mesh, the multi-layer mesh is mapped to a single layer, and the mapped mesh is divided by NG algorithm, and the mesh is restored after the division is completed. Using the STL file of the model as input, the mesh generation module designed by the original software is used to generate a multi-layer right-angle mesh, and the results show that the multi-layer mesh satisfies the overall load balancing and spatial locality conditions, but the load balancing of each single layer is poor, and the algorithm needs to be further improved.

In order to solve the shortcomings of the previous partition algorithm, a new algorithm for solving multilayer Cartesian meshing, the Constraint Multilayer Division algorithm was proposed by combining the NG algorithm, the LDG algorithm and the Kernighan-Lin algorithm. The NG algorithm is used to divide the single-layer mesh of the densest layer, and then the division result of the sub-layer mesh is taken as the constraint condition of the parent layer division, and the preliminary results of the constraint division are obtained by using the evaluation and partitioning mechanism of the LDG algorithm, which is called the coarse division stage of the mesh constraint. Using the optimization idea of K-L algorithm, at the cost of losing a small part of the spatial locality, a better load balancing of each layer of the grid is obtained, which is called the fine division stage of grid constraints. The results show that the new algorithm satisfies the overall load balancing and spatial locality of multi-layer Cartesian meshing, as well as the load balancing and spatial locality within each single layer. Finally, this multi-layer right-angle meshing algorithm was successfully applied to the CFD software.

[1] 吕涛. 区域分解算法[J]. 数学的实践与认识, 1992: 71-76.
[2] 李晓梅, 莫则尧. 多重网格算法综述[J/OL]. 中国科学基金, 1996: 8-15. DOI: 10.16262/j.cnki.1000-8217.1996.01.002.
[3] 姚征, 陈康民. CFD 通用软件综述[J]. 上海理工大学学报, 2002(2): 137-144.
[4] 刘梅梅. CFD 技术在重卡领域的应用综述[J]. 汽车实用技术, 2012(12): 1-6.
[5] 太海燕. CFD 软件在石化行业的应用综述[J]. 中国石油和化工标准与质量, 2016(36):32-34.
[6] 汪淼. 面向并行 CFD 迭代计算的网格划分关键技术研究[D]. 国防科技大学, 2017.
[7] ZHANG L, ZHANG G, LIU Y, et al. Mesh Partitioning Algorithm Based on Parallel FiniteElement Analysis and Its Actualization[J]. Mathematical Problems in Engineering, 2013, 2013:1-6.
[8] BOMAN E G, DEVINE K D, RAJAMANICKAM S. Scalable matrix computations on largescale-free graphs using 2D graph partitioning[C/OL]//SC ’13: Proceedings of the InternationalConference on High Performance Computing, Networking, Storage and Analysis. 2013: 1-12.DOI: 10.1145/2503210.2503293.
[9] 王鑫, 陈蔚雪, 杨雅君, 等. 知识图谱划分算法研究综述[J]. 计算机学报, 2021, 44: 235-260.
[10] HENDRICKSON B, DEVINE K. Dynamic load balancing in computational mechanics[J].Computer Methods in Applied Mechanics and Engineering, 2000(184): 485-500.
[11] D.K.DEVINE, E.G.BOMAN, R.T.HEAPHY. New challenges in dynamic load balancing[J].Applied Numerical Mathematics, 2004(52): 133-152.
[12] 朱自强, 李津, 张正科, 等. 计算流体力学中的网格生成方法及其应用[J]. 航空学报, 1998:25-31.
[13] WALSHAW C, CROSS M. Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm[J/OL]. SIAM Journal on Scientific Computing, 2000, 22(1): 63-80. DOI: 10.1137/S1064827598337373.
[14] JONES M T, PLASSMANN P E. Computational results for parallel unstructured mesh computations[J]. Computing Systems in Engineering, 1994(5): 297-309.
[15] M.J.BERGER, S.H.BOKHARI. A partitioning strategy for nonuniform problems on multiprocessors[J]. IEEE Trans.Computers, 1987(C-36): 570-580.
[16] KARYPIS G, KUMAR V. Parallel multilevel k-way partitioning scheme for irregular graphs[C/OL]//Supercomputing ’96: Proceedings of the 1996 ACM/IEEE Conference on Supercomputing. USA: IEEE Computer Society, 1996: 35–es. DOI: 10.1145/369028.369103.
[17] SIMON H. Partitioning of unstructured problems for parallel processing[J]. Computing Systems in Engineering, 1991, 2(2): 135-148.
[18] CATALYUREK U V, AYKANAT C. Decomposing Irregularly Sparse Matrices for ParallelMatrix-Vector Multiplication[C]//Workshop on Parallel Algorithms for Irregularly StructuredProblems. 1996.
[19] DEVINE K D, BOMAN E G, HEAPHY R T, et al. New challenges in dynamic load balancing[J]. Appl. Numer. Math., 2005, 52(2–3): 133–152.
[20] ADONI H W Y, NAHHAL T, KRICHEN M, et al. A survey of current challenges in partitioningand processing of graph-structured data in parallel and distributed systems[J]. Distributed andParallel Databases, 2019, 38: 495 - 530.
[21] CATALYUREK, UMIT, DEVINE, et al. More Recent Advances in (Hyper)Graph Partitioning[J/OL]. ACM Comput. Surv., 2023, 55(12). DOI: 10.1145/3571808.
[22] GALTIER J. Automatic partitioning techniques for solving partial differential equations onirregular adaptive meshes[C/OL]//ICS ’96: Proceedings of the 10th International Conferenceon Supercomputing. New York, NY, USA: Association for Computing Machinery, 1996: 157–164. DOI: 10.1145/237578.237598.
[23] HENDRICKSON B, LELAND R. A Multi-Level Algorithm For Partitioning Graphs[C]//Supercomputing ’95:Proceedings of the 1995 ACM/IEEE Conference on Supercomputing.1995: 28-28.
[24] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J/OL].Phys. Rev. E, 2004, 69: 026113. DOI: 10.1103/PhysRevE.69.026113.
[25] BARNARD S T, SIMON H D. Fast multilevel implementation of recursive spectral bisectionfor partitioning unstructured problems[C]//Concurrency Practice and Experience. 1994.
[26] VAN DRIESSCHE R, ROOSE D. Dynamic load balancing with a spectral bisection algorithmfor the constrained graph partitioning problem[C]//HERTZBERGER B, SERAZZI G. High Performance Computing and Networking. Berlin, Heidelberg: Springer Berlin Heidelberg,1995: 392-397.
[27] POTHEN A, SIMON H D, LIOU K P. Partitioning Sparse Matrices with Eigenvectors of Graphs[J/OL]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452. DOI:10.1137/0611030.
[28] GEORGE A, LIU J W. Computer Solution of Large Sparse Positive Definite Systems[J/OL].SIAM Review, 1984, 26(2): 289-291. DOI: 10.1137/1026055.
[29] FARHAT C. A simple and efficient automatic fem domain decomposer[J]. Computers andStructures, 1988, 28(5): 579-602.
[30] DONATH W, HOFFMAN A. Algorithms for partitioning graphs and computer logic basedon eigenvectors of connection matrices[J]. IBM Technical Disclosure Bulletin, 1972, 15(3):938-944.
[31] HENDRICKSON B, LELAND R. An Improved Spectral Graph Partitioning Algorithm forMapping Parallel Computations[J/OL]. SIAM Journal on Scientific Computing, 1995, 16(2):452-469. DOI: 10.1137/0916028.
[32] WANG M, TANG Y, GUO X, et al. Performance analysis of the graph-partitioning algorithmsused in OpenFOAM[C/OL]//2012 IEEE Fifth International Conference on Advanced Computational Intelligence (ICACI). 2012: 99-104. DOI: 10.1109/ICACI.2012.6463129.
[33] SCHLOEGEL K, KARYPIS G, KUMAR V. Parallel static and dynamic multi-constraint graphpartitioning[J/OL]. Concurrency and Computation: Practice and Experience, 2002, 14: 219-240. DOI: 10.1002/cpe.605.
[34] NISHIMURA J, UGANDER J. Restreaming graph partitioning: simple versatile algorithms foradvanced balancing[C/OL]//Proceedings of the 19th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining. New York, NY, USA: Association for ComputingMachinery, 2013: 1106–1114. https://doi.org/10.1145/2487575.2487696.
[35] LASALLE D, KARYPIS G. A Parallel Hill-Climbing Refinement Algorithm for Graph Partitioning[C/OL]//2016 45th International Conference on Parallel Processing (ICPP). 2016: 236-241. DOI: 10.1109/ICPP.2016.34.
[36] MOKASHI V, KULKARNI D B. A Review: Scalable Parallel Graph Partitioning for ComplexNetworks[C/OL]//2018 Second International Conference on Intelligent Computing and ControlSystems (ICICCS). 2018: 1869-1871. DOI: 10.1109/ICCONS.2018.8662954.
[37] LI X, PANG Y, ZHAO C, et al. A new multi-level algorithm for balanced partition problem onlarge scale directed graphs[J]. Advances in Aerodynamics, 2021, 3.
[38] ALPERT C J, KAHNG A B, YAO S Z. Spectral partitioning with multiple eigenvectors[J].Discrete Applied Mathematics, 1999, 90(1): 3-26.
[39] 周爽, 鲍玉斌, 王志刚, 等. BHP: 面向 BSP 模型的负载均衡 Hash 图数据划分[J]. 计算机科学与探索, 2014, 8: 40-50.
[40] UGANDER J, BACKSTROM L. Balanced label propagation for partitioning massive graphs[C]//Proceedings of the Sixth ACM International Conference on Web Search and Data Mining.New York, NY, USA: Association for Computing Machinery, 2013: 507–516.
[41] STANTON I, KLIOT G. Streaming graph partitioning for large distributed graphs[C]//KDD’12: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discoveryand Data Mining. New York, NY, USA: Association for Computing Machinery, 2012: 1222–1230.
[42] HAGEN L, KAHNG A. Fast spectral methods for ratio cut partitioning and clustering[C]//1991IEEE International Conference on Computer-Aided Design Digest of Technical Papers. 1991:10-13.
[43] NEWMAN M E J. Modularity and community structure in networks.[J]. Proceedings of theNational Academy of Sciences of the United States of America, 2006, 103 23: 8577-82.
[44] DONATH W E, HOFFMAN A J. Lower Bounds for the Partitioning of Graphs[J]. IBM Journalof Research and Development, 1973, 17(5): 420-425.
[45] KARYPIS G, KUMAR V. Analysis of Multilevel Graph Partitioning[C]//Supercomputing’95:Proceedings of the 1995 ACM/IEEE Conference on Supercomputing. 1995: 29-29.
[46] KARYPIS G, KUMAR V. A Fast and High Quality Multilevel Scheme for Partitioning IrregularGraphs[J]. SIAM Journal on Scientific Computing, 1998, 20(1): 359-392.
[47] GRADY L, SCHWARTZ E. Isoperimetric graph partitioning for image segmentation[J]. IEEETransactions on Pattern Analysis and Machine Intelligence, 2006, 28(3): 469-475.
[48] JISHA R C, INDRAJITH P S, ABHISHEK S. Community Detection Using Graph Partitioning[C]//2021 2nd Global Conference for Advancement in Technology (GCAT). 2021: 1-6.
[49] ACER S, KAYAASLAN E, AYKANAT C. A Recursive Bipartitioning Algorithm for Permuting Sparse Square Matrices into Block Diagonal Form with Overlap[J]. SIAM Journal on Scientific Computing, 2013, 35(1): C99-C121.
[50] HENDRICKSON B, KOLDA T G. Graph partitioning models for parallel computing[J]. Parallel Computing, 2000, 26(12): 1519-1534.
[51] GLANTZ R, MEYERHENKE H, NOE A. Algorithms for Mapping Parallel Processes onto Grid and Torus Architectures[C]//2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. 2015: 236-243.