Representation-transparent Matrix Algorithms with Scalable Performance

Peter Gottschling, David S. Wise, and Michael D. Adams

Status: Published

Abstract

Positive results from new object-oriented tools for scientific programming are reported. Using template classes, abstractions of matrix representations are available that subsume conventional row-major, column-major, either Z- or И-Morton-order, as well as block-wise combinations of these. Moreover, the design of the Matrix Template Library (MTL) has been independently extended to provide recursators, to support block-recursive algorithms, supplementing MTL’s iterators. Data types modeling both concepts enable the programmer to implement both iterative and recursive algorithms (or even both) on all of the aforementioned matrix representations at once for a wide family of important scientific operations.

We illustrate the unrestricted applicability of our matrix-recursator on matrix multiplication. The same generic block-recursive function, unaltered, is instantiated on different triplets of matrix types. Within a base block, either a library multiplication or a user-provided, platform-specific code provides excellent performance. We achieve 77% of peak-performance using hand-tuned base cases without explicit prefetching. This excellent performance becomes available over a wide family of matrix representations from a single program. The techniques generalize to other applications in linear algebra.

Keywords

Matrix Template Library, Morton-order, dilated Integers, doppled integers

Citation

Peter Gottschling, David S. Wise, and Michael D. Adams. Representation-transparent matrix algorithms with scalable performance. In ICS ’07: Proceedings of the 21st annual international conference on Supercomputing, pages 116–125. ACM, New York, NY, USA, 2007. ISBN 978-1-59593-768-1. doi: 10.1145/1274971.1274989.

BibTeX Entry

@inproceedings{gottschling2007representationtransparent,
  author = {Gottschling, Peter and Wise, David S. and Adams, Michael D.},
  title = {Representation-transparent Matrix Algorithms with Scalable Performance},
  booktitle = {ICS '07: Proceedings of the 21st annual international conference on Supercomputing},
  pages = {116--125},
  year = {2007},
  address = {New York, NY, USA},
  publisher = {ACM},
  isbn = {978-1-59593-768-1},
  doi = {10.1145/1274971.1274989},
}

Copyright Notice

© ACM, 2007. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ICS ’07: Proceedings of the 21st annual international conference on Supercomputing, (2007). http://doi.acm.org/10.1145/1274971.1274989.