Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

G. Kwasniewski, T. Ben-Nun, A. Nikolaos Ziogas, T. Schneider, M. Besta, T. Hoefler:

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

(arXiv:2010.05975. Oct. 2020)

Abstract

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× 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× less than the second-best implementation and is expected to communicate 2.1× less on a full-scale run on Summit.

Documents

download article:
access preprint on arxiv:
 

BibTeX

@article{kwasniewski2020on,
  author={Grzegorz Kwasniewski and Tal Ben-Nun and Alexandros Nikolaos Ziogas and Timo Schneider and Maciej Besta and Torsten Hoefler},
  title={{On the Parallel I/O Optimality of Linear Algebra Kernels: Near-Optimal LU Factorization}},
  journal={arXiv:2010.05975},
  year={2020},
  month={10},
  doi={10.48550/arXiv.2010.05975},
}