  A number of known techniques for improving cache performance in scientific
computations involve the reordering of the iteration space. Some of these
reorderings 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 computations 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 local 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 multidimensional
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 grid of the same size.
