Publications of Torsten Hoefler

Niels Gleinig, Maciej Besta, Torsten Hoefler:

I/O-Optimal Cache-Oblivious Sparse Matrix-Sparse Matrix Multiplication

(In Proceedings of the 36th IEEE Interational Parallel and Distributed Processing Symposium (to appear), Jun. 2022)

Abstract

Data movements between different levels of the memory hierarchy (I/O-transitions, or simply I/Os) are a critical performance bottleneck in modern computing. Therefore it is a problem of high practical relevance to find algorithms that use a minimal number of I/Os. We present a cache-oblivious sparse matrix-sparse matrix multiplication algorithm that uses a worst-case number of I/Os that matches a previously established lower bound for this problem. This improves the worst-case I/O-complexity of the previously best known algorithm for this problem (which is cache-aware) by a logarithmic multiplicative factor.

Documents

download article:

BibTeX

@inproceedings{,
  author={Niels Gleinig and Maciej Besta and Torsten Hoefler},
  title={{I/O-Optimal Cache-Oblivious Sparse Matrix-Sparse Matrix Multiplication}},
  year={2022},
  month={Jun.},
  booktitle={Proceedings of the 36th IEEE Interational Parallel and Distributed Processing Symposium (to appear)},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 13.59.58.68:9884	© Torsten Hoefler