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

被引：24

作者：

Bader, Michael ^{[1
]}

Zenger, Christoph ^{[1
]}

机构：

[1] Tech Univ Munich, Inst Informat, D-85748 Garching, Germany

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2006年 / 417卷 / 2-3期

关键词：

cache oblivious algorithms; matrix multiplication; space filling curves;

D O I：

10.1016/j.laa.2006.03.018

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (c) 2006 Elsevier Inc. All rights reserved.

引用

页码：301 / 313

页数：13