Impact of modern memory subsystems on cache optimizations for stencil computations

ABSTRACT

In this work we investigate the impact of evolving memory system features, such as large on-chip caches, automatic prefetch, and the growing distance to main memory on 3D stencil computations. These calculations form the basis for a wide range of scientific applications from simple Jacobi iterations to complex multigrid and block structured adaptive PDE solvers. First we develop a simple benchmark to evaluate the effectiveness of prefetching in cache-based memory systems. Next we present a small parameterized probe and validate its use as a proxy for general stencil computations on three modern microprocessors. We then derive an analytical memory cost model for quantifying cache-blocking behavior and demonstrate its effectiveness in predicting the stencil-computation performance. Overall results demonstrate that recent trends memory system organization have reduced the efficacy of traditional cache-blocking optimizations.

REFERENCES

• 1: Sriram Sellappa , Siddhartha Chatterjee, Cache-Efficient Multigrid Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.115-133, February 2004 [doi>10.1177/1094342004041295]
• 2: Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
• 3: Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.103-112, June 2001, Snowbird, Utah, United States
• 4: D. Bailey, "Littleś law and high performance computing," RNR Technical Report, 1997.
• 5: J. McCalpin, "Memory bandwidth and machine balance in current high performance computers," IEEE TCAA Newsletter, December 1995.
• 6: "Chombo homepage." http://seesar.lbl.gov/anag/chombo/, 2004.
• 7: "Cactus Homepage." http://www.cactuscode.org, 2004.
• 8: W. Benger, I. Foster, J. Novotny, E. Seidel, J. Shalf, W. Smith, and P. Walker, "Numerical relativity in a distributed environment," in Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, 1999.
• 9: M. Alcubierre, G. Allen, B. Brgmann, E. Seidel, and W.-M. Suen, "Towards an understanding of the stability properties of the 3+1 evolution equations in general relativity," Phys. Rev. D, vol. (gr-qc/9908079), 2000.
• 10: J. A. Font, M. Miller, W. M. Suen, and M. Tobias, "Three dimensional numerical general relativistic hydrodynamics: Formulations, methods, and code tests," Phys. Rev. D, vol. Phys. Rev. D61, 2000.
• 11: "Performance API homepage." http://icl.cs.utk.edu/papi, 2005.
• 12: "CHUD homepage." http://developer.apple.com/tools/performance/, 2005.
• 13: Zhiyuan Li , Yonghong Song, Automatic tiling of iterative stencil loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.975-1028, November 2004 [doi>10.1145/1034774.1034777]
• 14: M. M. Strout, L. Carter, J. Ferrante, J. Freeman, and B. Kreaseck, "Combining performance aspects of irregular gauss-seidel via sparse tiling," in 15th Workshop on Languages and Compilers for Parallel Computing (LCPC), (College Park, Maryland), July 25-27, 2002.

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

General Terms:
Measurement, Performance

Keywords:
cache blocking, performance modeling, prefetch, stencil