An experimental comparison of cache-oblivious and cache-conscious programs

ABSTRACT

Cache-oblivious algorithms have been advanced as a way of circumventing some of the difficulties of optimizing applications to take advantage of the memory hierarchy of modern microprocessors. These algorithms are based on the divide-and-conquer paradigm -- each division step creates sub-problems of smaller size, and when the working set of a sub-problem fits in some level of the memory hierarchy, the computations in that sub-problem can be executed without suffering capacity misses at that level. In this way, divide-and-conquer algorithms adapt automatically to all levels of the memory hierarchy; in fact, for problems like matrix multiplication, matrix transpose, and FFT, these recursive algorithms are optimal to within constant factors for some theoretical models of the memory hierarchy.

An important question is the following: how well do carefully tuned cache-oblivious programs perform compared to carefully tuned cache-conscious programs for the same problem? Is there a price for obliviousness, and if so, how much performance do we lose? Somewhat surprisingly, there are few studies in the literature that have addressed this question.

This paper reports the results of such a study in the domain of dense linear algebra. Our main finding is that in this domain, even highly optimized cache-oblivious programs perform significantly worse than corresponding cacheconscious programs. We provide insights into why this is so, and suggest research directions for making cache-oblivious algorithms more competitive.

REFERENCES

• 1: Basic Linear Algebra Routines (BLAS). http://www.netlib.org/blas.
• 2: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 3: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 4: L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):78--101, 1966.
• 5: David A. Berson , Rajiv Gupta , Mary Lou Soffa, Integrated Instruction Scheduling and Register Allocation Techniques, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.247-262, August 07-09, 1998
• 6: Gianfranco Bilardi, 2005. Personal communication.
• 7: Gianfranco Bilardi , Paolo D'Alberto , Alexandru Nicolau, Fractal Matrix Multiplication: A Case Study on Portability of Cache Performance, Proceedings of the 5th International Workshop on Algorithm Engineering, p.26-38, August 28-31, 2001
• 8: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 9: Ernie Chan , Enrique S. Quintana-Orti , Gregorio Quintana-Orti , Robert van de Geijn, Supermatrix out-of-order scheduling of matrix operations for SMP and multi-core architectures, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248397]
• 10: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 11: Rezaul Alam Chowdhury , Vijaya Ramachandran, The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248392]
• 12: 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
• 13: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611]
• 14: J. J. Dongarra, F. Gustavson, and A. Karp. Implementing linear algebra algorithms for dense matrices on a vector pipeline machine. SIAM Review, 26(1):91--112, 1984.
• 15: Matteo Frigo, 2005. Personal communication.
• 16: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 17: J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France [doi>10.1145/55364.55407]
• 18: Jia Guo, María Jesús Garzarán, and David Padua. The power of Belady's algorithm in register allocation for long basic blocks. In Proc. 16th International Workshop in Languages and Parallel Computing, pages 374--390, 2003.
• 19: F. G. Gustavson, Recursion leads to automatic variable blocking for dense linear-algebra algorithms, IBM Journal of Research and Development, v.41 n.6, p.737-756, Nov. 1997
• 20: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 21: Piyush Kumar. Cache-oblivious algorithms. In Lecture Notes in Computer Science 2625. Springer-Verlag, 1998.
• 22: Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA computers, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.353-375, Nov. 1993 [doi>10.1145/161541.159766]
• 23: Cindy Norris , Lori L. Pollock, An experimental study of several cooperative register allocation and instruction scheduling strategies, Proceedings of the 28th annual international symposium on Microarchitecture, p.169-179, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 24: Jack Dongarra , Robert Schreiber, Automatic Blocking of Nested Loops, University of Tennessee, Knoxville, TN, 1990
• 25: Sivan Toledo, A survey of out-of-core algorithms in numerical linear algebra, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 26: Clint Whaley. personal communication, 2005.
• 27: R. Clint Whaley, Antoine Petitet, and Jack J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, 2001.
• 28: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
• 29: Kamen Yotov, Xiaoming Li, Gang Ren, Maria Garzaran, David Padua, Keshav Pingali, and Paul Stodghill. Is search really necessary to generate high-performance BLAS? Proceedings of the IEEE, 93(2), 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Optimization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
cache-conscious algorithms, cache-oblivious algorithms, memory bandwidth, memory hierarchy, memory latency, numerical software