A Novel Adaptive Match Scheme for Parallel Mesh-Decomposition in OpenFOAM

Abstract:

A parallel multilevel k-way partitioning algorithm is used in OpenFOAM to perform parallel mesh-decomposition. Before the parallel decomposition procedure, mesh has to be pre-decomposed by the Simple method in OpenFOAM. Match-computation for the algorithms parallel coarsening phase is based on a kind of global match scheme which introduces large amount of communication overhead. However, the domains of the mesh generated by Simple maintain good locality and continuity, which makes it unnecessary to adopt global match scheme in the parallel coarsening phase. In this paper, a novel adaptive match scheme AMS is brought forward for the parallel multilevel k-way partitioning algorithm. An adaptive critical x is calculated firstly according to the scale of the mesh and the parallel degree. For the first x stages of the coarsening phase, a local match scheme is adopted in which vertexes are only allowed to match with their adjacent unmatched vertexes with heaviest edge-weight on their local processors. For the rest stages, the traditional global match scheme is introduced and match of two vertexes on different processors is allowed. AMS can efficiently reduce the communication overhead introduced by simply adopting global match scheme. The experiment is performed on mesh of LinearPTT application on Tianhe-1A. The results show that the parallel multilevel k-way paritioning algorithm based on AMS has a better performance than that based on traditional global match scheme.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 3265-3270
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.3265
• Online since: September 2013
• Authors: Miao Wang, Yu Hua Tang, Hong Yun Zhang
• Keywords: Adaptive Match Scheme, Mesh-Decomposition, OpenFOAM, Parallel Graph-Partitioning

References

[1] Jasak H. OpenFOAM: Programming tutorial [R]. (2007).

[2] Karypis G, Kumar V. A Coarse-Grain Parallel Formulation of Multilevel k-way Graph Partitioning Algorithm [C]. In Parallel Processing for Scientific Computing. (1997).

[3] Karypis G, Kumar V. Parallel multilevel k-way partitioning scheme for irregular graphs [C]. In Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM). Washington, DC, USA, (1996).

DOI: 10.1145/369028.369103

[4] Schloegel K, Karypis G, Kumar V. Parallel static and dynamic multi-constraint graph partitioning [J]. CONCURRENCY AND COMPUTATION: PRACTICE AND EXPERIENCE. 2002, 14: 219–240.

DOI: 10.1002/cpe.605

[5] Luby M. A simple parallel algorithm for the maximal independent set problem [C]. In Proceedings of the seventeenth annual ACM symposium on Theory of computing. New York, NY, USA, 1985: 1–10.

DOI: 10.1145/22145.22146

[6] Hendrickson B, Kolda T G. Graph partitioning models for parallel computing [J]. Parallel Computing. 1999, 26 (2000): 1519–1534.

DOI: 10.1016/s0167-8191(00)00048-x

[7] Miao Wang, Yuhua Tang, Xiaowei Guo and Xiaoguang Ren. Performance Analysis of the Graph-partitioning Algorithms Used in OpenFOAM [C]. In Proceedings of International Conference on Advanced Computational Intelligence. (2012).

DOI: 10.1109/icaci.2012.6463129