Cache oblivious matrix multiplication using an element ordering based on a Peano curve

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

One of the keys to tap the full performance potential of current hardware is the optimal utilization of cache memory. Cache oblivious algorithms are designed to inherently benefit from any underlying hierarchy of caches, but do not need to know about the exact structure of the cache. In this paper, we present a cache oblivious algorithm for matrix multiplication. The algorithm uses a block recursive structure and an element ordering that is based on Peano curves. In the resulting code, index jumps can be totally avoided, which leads to an asymptotically optimal spatial and temporal locality of the data access.

Original languageEnglish
Pages (from-to)301-313
Number of pages13
JournalLinear Algebra and Its Applications
Volume417
Issue number2-3
DOIs
StatePublished - 1 Sep 2006

Keywords

  • Cache oblivious algorithms
  • Matrix multiplication
  • Space filling curves

Fingerprint

Dive into the research topics of 'Cache oblivious matrix multiplication using an element ordering based on a Peano curve'. Together they form a unique fingerprint.

Cite this