Partitioning
The following figure shows the flowchart for partitioning of mesh-system. There are three main stages: Initial uni-weight graph partitioning, geometric partitioning and weighted graph partitioning. The last two are inter-connected and executed iteratively.
Initially, Gmsh partitiones a mesh into n partitions with the underlying graph partitioner (METIS, Chaco, Scotch, etc.). With default settings of Gmsh, each vertex of graph partitioner has the same weight. This results in partitions which have approximately the same number of cells. This kind of partitioning is suitable when the time-cost of each cell is the same. For example, for basic flow solvers, the same discretized equation is solved on each cell. However, for overset mesh technique, overlapping mesh cells need to be in the same partitions. For this reason, a geometric partitioning follows the initial uni-weight graph partitioning.
Out of possible spatial partitioning structures, a natural three-dimensional structure, octree is chosen to organize cells based on their spatial locations. Processes such as registration and refinement on the octree are simultaneous in all processors.
Initially, the octree is 2x2x2. If the problem is pseudo three-dimensional or 2.5 dimensional, the initial octree dimensions are 2x2x1. Each processor registers its mesh-cells into correct bin/voxel of the octree. Registration is based on intersection of AABB of the cell and a bin. Once registration is over, load is calculated in each bin of the octree. There are different possible ways of computing load as shown below.
- The volume of overlapping meshes.
- The number of cells that belong to different meshes.
- The number of cells.
The load calculation methods result in better load balance for a typical flow solver in the order from top to bottom. While for the assembler reverse is true. Results indicate that solver takes more than the assembler, therefore, load balance is maintained for the specifically for the flow solver.
The most-loaded bin of the octree is refined into either 2x2x2 or 2x2x1 sub-bin and the cells are re-registered into the sub-bin.
Each vertex of the octree bin is assigned to a graph vertex. Face-to-face connections between bins constitutes the edges of the graph. Unlike the initial graph partitioning, here the weight of each vertex can be different. METIS_PartGraphKway is used to obtain n partitions. If a balanced distribution obtained, partitioning is over and the partitions are going to be distributed to the processors. Otherwise, the bin-loads are recomputed and refinement process continues until balanced distribution is obtained.