Orthogonal Layers of Parallelism in Large-Scale Eigenvalue Computations

Alvermann A, Hager G, Fehske H (2023)

Publication Type: Journal article

Publication year: 2023

Journal

ACM Transactions on Parallel Computing Association for Computing Machinery (ACM)

Book Volume: 10

Article Number: 3614444

Journal Issue: 3

DOI: 10.1145/3614444

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.

Authors with CRIS profile

Georg Hager Regionales Rechenzentrum Erlangen (RRZE)

Involved external institutions

Universität Greifswald DE Germany (DE)

How to cite

APA:

Alvermann, A., Hager, G., & Fehske, H. (2023). Orthogonal Layers of Parallelism in Large-Scale Eigenvalue Computations. ACM Transactions on Parallel Computing, 10(3). https://doi.org/10.1145/3614444

MLA:

Alvermann, Andreas, Georg Hager, and Holger Fehske. "Orthogonal Layers of Parallelism in Large-Scale Eigenvalue Computations." ACM Transactions on Parallel Computing 10.3 (2023).

BibTeX: Download