Orthogonal layers of parallelism in large-scale eigenvalue computations

Abstract

We address the communication overhead of distributed sparse matrix-(multiple)-vector multiplication in the context of large-scale eigensolvers, using filter diagonalization as an example. The basis of our study is a performance model which includes a communication metric that is computed directly from the matrix sparsity pattern without running any code. The performance model quantifies to which extent scalability and parallel efficiency are lost due to communication overhead. To restore scalability, we identify two orthogonal layers of parallelism in the filter diagonalization technique. In the horizontal layer the rows of the sparse matrix are distributed across individual processes. In the vertical layer bundles of multiple vectors are distributed across separate process groups. An analysis in terms of the communication metric predicts that scalability can be restored if, and only if, one implements the two orthogonal layers of parallelism via different distributed vector layouts. Our theoretical analysis is corroborated by benchmarks for application matrices from quantum and solid state physics, road networks, and nonlinear programming. We finally demonstrate the benefits of using orthogonal layers of parallelism with two exemplary application cases -- an exciton and a strongly correlated electron system -- which incur either small or large communication overhead.

arXiv commentFinal version, almost as published. 32 pages, 12 figures

References in corpus (18)

• Correlated Electrons in High Temperature Superconductors
• Observation of many-body localization of interacting fermions in a quasi-random optical lattice
• The Kernel Polynomial Method
• Nonthermal pathways to ultrafast control in quantum materials
• A Density Matrix-based Algorithm for Solving Eigenvalue Problems
• Giant Rydberg Excitons in Cuprous Oxide
• Observing non-ergodicity due to kinetic constraints in tilted Fermi-Hubbard chains
• A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units
• Polynomially filtered exact diagonalization approach to many-body localization
• Shift-invert diagonalization of large many-body localizing spin chains
• High-performance implementation of Chebyshev filter diagonalization for interior eigenvalue computations
• GHOST: Building blocks for high performance sparse linear algebra on heterogeneous systems
• Polynomial filter diagonalization of large Floquet unitary operators
• Level-based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication
• Chebyshev Filter Diagonalization on Modern Manycore Processors and GPGPUs
• Exciton mass and exciton spectrum in the cuprous oxide
• Variational discrete variable representation for excitons on a lattice
• A domain-specific language and matrix-free stencil code for investigating electronic properties of Dirac and topological materials