Cache Oblivious Algorithms
Univ.-Prof. Dipl.-Ing. Dr. Volker Strumpen
Oct. 28, 2009, 4:15 p.m. HF 9901The random access memory model, where each memory access incurs the same latency, does not hold for todays technologies any longer. Propagation delays across a single chip have increased to tens of clock cycles, resulting in nonuniform memory latencies even within a chip. As a result, processor utilization of many high-performance programs has dipped below 10 percent, and for transaction processing well below 40 percent.
Cache oblivious algorithms cope with the memory bottleneck by minimizing the number of data transfers between the levels of a memory hierarchy. These algorithms offer portable performance, because they do not contain any parameters about a machines cache configuration.
In this talk, I will review the ideas underlying cache oblivious algorithms, and demonstrate their value for applications that can be expressed as stencil computations, including linear algebra and scientific programs.
