Tight bounds on cache use for stencil operations on rectangular grids

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.

REFERENCES

• 1: David H. Bailey, Unfavorable strides in cache memory systems (RNR Technical Report RNR-92-015), Scientific Programming, v.4 n.2, p.53-58, Summer 1995
• 2: Cassels, J. W. S. 1957. Introduction to Diophantine Approximations (Ch. I Theorem VIII). Cambridge Univ. Press. Cambridge, Mass.
• 3: Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
• 4: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
• 5: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 6: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: John L. Hennessy , David A. Patterson, Computer organization and design (2nd ed.): the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 8: Hong, J. W., and Kung, H. T. 1981. I/O complexity: The red-blue pebble game. In Proceedings of the IEEE Symposium on Theoretical Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 326--333.
• 9: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 10: Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia [doi>10.1145/277830.277917]
• 11: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 12: Wang, D. L., and Wang, P. 1977. Discrete isoperimetric problems. SIAM J. Appl. Math. 32, 860--870.
• 13: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
Cache memory, cache misses, fundamental parallelepiped, lattice, lower and upper bounds, reduced basis, scientific computing, structured grids