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

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

 Deinsum: Practically I/O Optimal Multilinear Algebra

(In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC'22), Nov. 2022)

Abstract

Multilinear algebra kernel performance on modern massively-parallel systems is determined mainly by data movement. However, deriving data movement-optimal distributed schedules for programs with many high-dimensional inputs is a notoriously hard problem. State-of-the-art libraries rely on heuristics and often fall back to suboptimal tensor folding and BLAS calls. We present Deinsum, an automated framework for distributed multilinear algebra computations expressed in Einstein notation, based on rigorous mathematical tools to address this problem. Our framework automatically derives data movement-optimal tiling and generates corresponding distributed schedules, further optimizing the performance of local computations by increasing their arithmetic intensity. To show the benefits of our approach, we test it on two important tensor kernel classes: Matricized Tensor Times Khatri-Rao Products and Tensor Times Matrix chains. We show performance results and scaling on the Piz Daint supercomputer, with up to 19x speedup over state-of-the-art solutions on 512 nodes.

Documents

download article:
 

BibTeX

@inproceedings{,
  author={Alexandros Nikolaos Ziogas and Grzegorz Kwasniewski and Tal Ben-Nun and Timo Schneider and Torsten Hoefler},
  title={{Deinsum: Practically I/O Optimal Multilinear Algebra}},
  year={2022},
  month={11},
  booktitle={Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC'22)},
}