Implicit and explicit optimizations for stencil computations

ABSTRACT

Stencil-based kernels constitute the core of many scientific applications on block-structured grids. Unfortunately, these codes achieve a low fraction of peak performance, due primarily to the disparity between processor and main memory speeds. We examine several optimizations on both the conventional cache-based memory systems of the Itanium 2, Opteron, and Power5, as well as the heterogeneous multicore design of the Cell processor. The optimizations target cache reuse across stencil sweeps, including both an implicit cache oblivious approach and a cache-aware algorithm blocked to match the cache structure. Finally, we consider stencil computations on a machine with an explicitly-managed memory hierarchy, the Cell processor. Overall, results show that a cache-aware approach is significantly faster than a cache oblivious approach and that the explicitly managed memory on Cell is more efficient: Relative to the Power5, it has almost 2x more memory bandwidth and is 3.7x faster.

REFERENCES

• 1: Applied Numerical Algorithms Group (ANAG), Lawrence Berkeley National Laboratory, Berkeley, CA. Chombo website. http://seesar.lbl.gov/ANAG/software.html.
• 2: M. Berger and J. Oliger. Adaptive mesh refinement for hyperbolic partial differential equations. Journal of Computational Physics, 53:484--512, 1984.
• 3: M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms (extended abstract).
• 4: Leonid Oliker , Andrew Canning , Jonathan Carter , John Shalf , David Skinner , Ethier Ethier , Rupak Biswas , Jahed Djomehri , Rob Van der Wijngaart, Evaluation of Cache-based Superscalar and Cacheless Vector Architectures for Scientific Computations, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.38, November 15-21, 2003
• 5: Shoaib Kamil , Parry Husbands , Leonid Oliker , John Shalf , Katherine Yelick, Impact of modern memory subsystems on cache optimizations for stencil computations, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111589]
• 6: J. McCalpin and D. Wonnacott. Time skewing: A value-based approach to optimizing for memory locality. Technical Report DCS-TR-379, Department of Computer Science, Rugers University, 1999.
• 7: Performance Application Programming Interface. http://icl.cs.utk.edu/papi/.
• 8: H. Prokop. Cache-oblivious algorithms, June 1999. Master's thesis, MIT Department of Electrical Engineering and Computer Science.
• 9: 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]
• 10: Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
• 11: Samuel Williams , John Shalf , Leonid Oliker , Shoaib Kamil , Parry Husbands , Katherine Yelick, The potential of the cell processor for scientific computing, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128027]
• 12: Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
• 13: Using Time Skewing to Eliminate Idle Time due to Memory Bandwidth and Network Limitations, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.171, May 01-05, 2000

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies; Microprocessors and microcomputers
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance