PT-Scotch: A tool for efficient parallel graph ordering

Abstract

The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which are also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-Scotch software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-Scotch produces consistently better orderings than ParMeTiS on large numbers of processors.

Cited by in corpus (19)

• The JOREK non-linear extended MHD code and applications to large-scale instabilities and their control in magnetically confined fusion plasmas
• Nektar++: enhancing the capability and application of high-fidelity spectral/$hp$ element methods
• Extreme-Scale Block-Structured Adaptive Mesh Refinement
• Heterogeneous CPU/GPU co-execution of CFD simulations on the POWER9 architecture: Application to airplane aerodynamics
• SIESTA-PEXSI: Massively parallel method for efficient and accurate \textit{ab initio} materials simulation without matrix diagonalization
• GHOST: Building blocks for high performance sparse linear algebra on heterogeneous systems
• An Approach for Accelerating Incompressible Turbulent Flow Simulations Based on Simultaneous Modelling of Multiple Ensembles
• Fully Parallel Mesh I/O using PETSc DMPlex with an Application to Waveform Modeling
• PsiQuaSP -- A library for efficient computation of symmetric open quantum systems
• Parallel Controllability Methods For the Helmholtz Equation
• A tetrahedral space-filling curve for non-conforming adaptive meshes
• Scalable computation of thermomechanical turbomachinery problems
• A Robust Hierarchical Solver for Ill-conditioned Systems with Applications to Ice Sheet Modeling
• Hardware locality-aware partitioning and dynamic load-balancing of unstructured meshes for large-scale scientific applications
• Domain decomposition and locality optimization for large-scale lattice Boltzmann simulations
• Revisiting Performance of BiCGStab Methods for Solving Systems with Multiple Right-Hand Sides
• A Meta-graph Approach to Analyze Subgraph-centric Distributed Programming Models
• Parallel high-order resolution of the Shallow-water equations on real large-scale meshes with complex bathymetries
• A Scalable Two-Level Domain Decomposition Eigensolver for Periodic Schrödinger Eigenstates in Anisotropically Expanding Domains