Abstract | ||
---|---|---|
We derive tight bounds on cache misses for evaluation of explicit stencil operators on rectangular grids. Our lower bound is based on the isoperimetric property of the discrete crosspolytope. Our upper bound is based on a good surface-to-volume ratio of a parallelepiped spanned by a reduced basis of the interference lattice of a grid. Measurements show that our algorithm typically reduces the number of cache misses by a factor of three, relative to a compiler optimized code. We show that stencil calculations on grids whose interference lattices have a short vector feature abnormally high numbers of cache misses. We call such grids unfavorable and suggest to avoid these in computations by appropriate padding. By direct measurements on a MIPS R10000 processor we show a good correlation between abnormally high numbers of cache misses and unfavorable three-dimensional grids. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1145/567112.567115 | J. ACM |
Keywords | DocType | Volume |
fundamental parallelepiped,cache use,cache memory,tight bound,reduced basis,lattice,interference lattice,explicit stencil operator,good correlation,lower and upper bounds,short vector feature abnormally,structured grids,high number,rectangular grid,abnormally high number,unfavorable three-dimensional grid,scientific computing,cache misses,stencil calculation,stencil operation,good surface-to-volume ratio | Journal | 49 |
Issue | ISSN | Citations |
3 | 0004-5411 | 4 |
PageRank | References | Authors |
0.54 | 7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael A. Frumkin | 1 | 126 | 19.68 |
Rob F. Van der Wijngaart | 2 | 374 | 45.61 |