On the Parallel I/O Optimality of Linear Algebra Kernels: Near-Optimal LU Factorization

Dense linear algebra kernels, such as linear solvers or tensor contractions, are fundamental components of many scientific computing applications. In this work, we present a novel method of deriving parallel I/O lower bounds for this broad family of programs. Based on the X-partitioning abstraction,...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-10
Main Authors: Kwasniewski, Grzegorz, Ben-Nun, Tal, Ziogas, Alexandros Nikolaos, Schneider, Timo, Besta, Maciej, Hoefler, Torsten
Format: Article
Language:English
Subjects:
Algorithms
Asymptotic properties
Communication
Empirical analysis
Factorization
Kernels
Linear algebra
Lower bounds
Microprocessors
Optimization
Solvers
Tensors
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Dense linear algebra kernels, such as linear solvers or tensor contractions, are fundamental components of many scientific computing applications. In this work, we present a novel method of deriving parallel I/O lower bounds for this broad family of programs. Based on the X-partitioning abstraction, our method explicitly captures inter-statement dependencies. Applying our analysis to LU factorization, we derive COnfLUX, an LU algorithm with the parallel I/O cost of \(N^3 / (P \sqrt{M})\) communicated elements per processor -- only \(1/3\times\) over our established lower bound. We evaluate COnfLUX on various problem sizes, demonstrating empirical results that match our theoretical analysis, communicating asymptotically less than Cray ScaLAPACK or SLATE, and outperforming the asymptotically-optimal CANDMC library. Running on \(1\),\(024\) nodes of Piz Daint, COnfLUX communicates 1.6\(\times\) less than the second-best implementation and is expected to communicate 2.1\(\times\) less on a full-scale run on Summit.
ISSN:2331-8422