Name
Abstract | ||
|---|---|---|
A number of known techniques for improving cache performance in scientific computations involve the reordering of the iteration space. Some of these reorder- ings can be considered coverings of the iteration space with sets having small surface- to-volume ratios. Use of such sets may reduce the number of cache misses in compu- tations of local operators having the iteration space as their domain. First, we derive lower bounds on cache misses that any algorithm must suffer while computing a lo- cal operator on a grid. Then, we explore coverings of iteration spaces of structured and unstructured discretization grid operators which allow us to approach these lower bounds. For structured grids we introduce a covering by successive minima tiles based on the interference lattice of the grid. We show that the covering has a small surface-to-volume ratio and present a computer experiment showing actual reduction of the cache misses achieved by using these tiles. For planar unstructured grids we show existence of a covering which reduces the number of cache misses to the level of that of structured grids. Next, we introduce a class of multidimen- sional grids, called starry grids in this paper. These grids represent an abstraction of unstructured grids used in, for example, molecular simulations and the solution of partial differential equations. We show that starry grids can be covered by sets having a low surface-to-volume ratio and, hence have the same cache efficiency as structured grids. Finally, we present a triangulation of a three-dimensional cube that has the property that any local operator on the corresponding grid must incur a significantly larger number of cache misses than a similar operator on a structured |
Year | Venue | Keywords |
|---|---|---|
2002 | Clinical Orthopaedics and Related Research | scientific computing,computer experiment,c 4,lower bound,unstructured grid,partial differential equation,three dimensional |
Field | DocType | Volume |
Computer experiment,Discretization,Cache,Computer science,Parallel computing,Maxima and minima,Cache algorithms,Triangulation (social science),Computational science,Operator (computer programming),Grid | Journal | cs.PF/0205 |
Citations | PageRank | References |
1 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Frumkin | 1 | 126 | 19.68 |
| Rob F. Van der Wijngaart | 2 | 374 | 45.61 |