Parallel partitioning tool GridSpiderPar for large mesh decomposition




parallel programming, graph partitioning, mesh decomposition


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.

Author Biographies

E.N. Golovchenko

M.V. Yakobovskiy


  1. B. Smith, P. Bjorstad, and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations (Cambridge Univ. Press, New York, 1996).
  2. A. I. Ilyushin, A. A. Kolmakov, and I. S. Menshov, “Construction of a Parallel Computational Model by Composition of Computational Facilities,” Mat. Model. 23 (7), 97-113 (2011) [Math. Models Comput. Simul. 4 (1), 118-128 (2012)].
  3. A. A. Voropinov, “Data Decomposition for TIM-2D Code Parallelizing Method and Its Quality Evaluation Criteria,” Vestn. South Ural State Univ. Ser. Math. Model. Comput. Softw., No. 4, 40-50 (2009).
  4. M. V. Yakobovskii, “An Incremental Algorithm for Graph Decomposition,” Vestn. Lobachevskii Univ. Nizhni Novgorod, No. 1, 243-250 (2005).
  5. E. Boman, K. Devine, U. Catalyurek, et al., Zoltan: Parallel Partitioning, Load Balancing and Data-Management Services , Sandia Nat. Labs. . Cited October 22, 2015.
  6. M. V. Yakobovskii, “Parallel Sorting Algorithms for Large Data Volumes,” in Fundamental Physico-Mathematical Problems and Modeling of Technological Systems (Yanus, Moscow, 2004), Issue 7, pp. 235-249.
  7. E. N. Golovchenko, “Parallel Partitioning Tool for Large Mesh Decomposition,” Mat. Model. 23 (10), 3-18 (2011).
  8. V. A. Gasilov, A. S. Boldarev, S. V. D’yachenko, et al., “Program Package MARPLE3D for Simulation of Pulsed Magnetically Driven Plasma Using High Performance Computing,” Mat. Model. 24 (1), 55-87 (2012).



How to Cite

Головченко Е., Якобовский М. Parallel Partitioning Tool GridSpiderPar for Large Mesh Decomposition // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2015. 16. 507-517. doi 10.26089/NumMet.v16r448



Section 1. Numerical methods and applications