Portal de Periódicos da CAPES

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

2006; Elsevier BV; Volume: 417; Issue: 2-3 Linguagem: Inglês

10.1016/j.laa.2006.03.018

1873-1856

Michael Bäder, Christoph Zenger,

Interconnection Networks and Systems

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.