Numerical Experiments with New Algorithms for Parallel Decomposition of Large Computational Meshes

The paper presents new algorithms for parallel decomposition of large computational meshes. The problem of load balancing arises in parallel mesh-based numerical solution of problems of continuum mechanics, pulsed-power energetics, electrodynamics etc. on high-performance computing systems. Geometric parallelism is commonly used in most of the applications for large-scale 3D simulations of the problems listed above. It implies that every branch of an application code processes a subset of computational mesh (a subdomain), while data exchanges provide a possibility of computations in the vicinity of subdomain borders. In order to increase processors efficiency it is necessary to provide rational domain decomposition, taking into account the requirements of making balanced mesh distribution among processors and reducing interprocessor communications, that depend on the number of bonds between subdomains. A principal goal of the presented work was to design rational parallel decomposition algorithms, working with unstructured meshes with up to 1 billion elements with irregular structure whose cells may be tetrahedrons, triangular or quadrilateral prisms. To this end, the program package for parallel mesh decomposition GRIDSPIDERPAR was developed. The complex includes two algorithms: parallel incremental algorithm of graph partitioning and parallel geometric algorithm of mesh partitioning. The developed algorithms were investigated experimentally in two stages. First we examined a number of “finite volume” meshes built in different geometric domains. For each test mesh we constructed a dual graph and carried out a comparative partitioning into the equal number of subdomains with use of the methods incorporated into PARMETIS, PT-SCOTCH and ZOLTAN versus the techniques of our tool GRIDSPIDERPAR. Second, we performed computer simulations of some problems of magnetohydrodynamics to evaluate the efficiency of the developed algorithms. The results of numerical experiments are presented in this paper.