"Parallel partitioning tool GridSpiderPar for large mesh decomposition"
Golovchenko E.N. and Yakobovskiy M.V.

The problem of load balancing arises in parallel mesh-based numerical solution of problems of continuum mechanics, energetics, electrodynamics etc. on high-performance computing systems. The number of processors to run a computational problem is often unknown. It makes sense, therefore, to partition a mesh into a great number of microdomains which then are used to create subdomains. Graph partitioning methods implemented in state-of-the-art parallel partitioning tools ParMETIS, Jostle, PT-Scotch and Zoltan are based on multilevel algorithms. That approach has a shortcoming of forming unconnected subdomains. Another shortcoming of present graph partitioning methods is generation of strongly imbalanced partitions. The program package for parallel large mesh decomposition GridSpiderPar was developed. We compared different partitions into microdomains, microdomain graph partitions and partitions into subdomains of several meshes (108 vertices, 109 elements) obtained by means of the partitioning tool GridSpiderPar and the packages ParMETIS, Zoltan and PT-Scotch. Balance of the partitions, edge-cut and number of unconnected subdomains in different partitions were compared as well as the computational performance of gas-dynamic problem simulations run on different partitions. The obtained results demonstrate advantages of the devised algorithms.

Keywords: parallel programming, graph partitioning, mesh decomposition.

  • Golovchenko E.N. – Keldysh Institute of Applied Mathematics, Russian Academy of Sciences; Miusskaya ploshchad’ 4, Moscow, 125047, Russia; Ph.D., Scientist, e-mail: ge03@imamod.ru
  • Yakobovskiy M.V. – Keldysh Institute of Applied Mathematics, Russian Academy of Sciences; Miusskaya ploshchad’ 4, Moscow, 125047, Russia; Dr. Sci., Professor, Head of Sector, e-mail: lira@imamod.ru