Cache Oblivious Stencil Computations

by Matteo Frigo and Volker Strumpen.

Proceedings of the 19th ACM International Conference on Supercomputing (ICS05).
[Full text]


We present a cache oblivious algorithm for stencil computations, which arise for example in finite-difference methods. Our algorithm applies to arbitrary stencils in $n$-dimensional spaces. On an ``ideal cache'' of size $Z$, our algorithm saves a factor of $Theta(Z^{1/n})$ cache misses compared to a naive algorithm, and it exploits temporal locality optimally throughout the entire memory hierarchy.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009