Towards a theory of cache-efficient algorithms

ABSTRACT

We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our cache model, an extension of Aggarwal and Vitter's I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations. As a corollary, we obtain cache-efficient algorithms in the single-level cache model for fundamental problems like sorting, FFT, and an important subclass of permutations. We also analyze the average-case cache behavior of mergesort, show that ignoring associativity concerns could lead to inferior performance, and present supporting experimental evidence.We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting. Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and for dealing with the hitherto unresolved problem of limited associativity.

REFERENCES

• 1: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 2: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 3: Aggarwal, A., Chandra, A., and Snir, M. 1987b. Hierarchical memory with block transfer. In Proceedings of IEEE Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 204--216.
• 4: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 5: Alpern, B., Carter, L., Feig, E., and Selker, T. 1994. The uniform memory hierarchy model of computation. Algorithmica 12, 2, 72--109.
• 6: Rakesh D. Barve , Edward F. Grove , Jeffrey Scott Vitter, Simple randomized mergesort on parallel disks, Parallel Computing, v.23 n.4-5, p.601-631, June 1, 1997 [doi>10.1016/S0167-8191(97)00015-X]
• 7: Gianfranco Bilardi , Enoch Peserico, A Characterization of Temporal Locality and Its Portability across Memory Hierarchies, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.128-139, July 08-12, 2001
• 8: Larry Carter , Kang Su Gatlin, Towards an Optimal Bit-Reversal Permutation Program, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.544, November 08-11, 1998
• 9: Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305231]
• 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: Chatterjee, S., and Sen, S. 2000. Cache-efficient matrix transposition. In Proceedings of HPCA-6 (Toulouse, France). 195--205.
• 12: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 13: Thomas H. Cormen , Thomas Sundquist , Leonard F. Wisniewski, Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems, SIAM Journal on Computing, v.28 n.1, p.105-136, Feb. 1999 [doi>10.1137/S0097539795283681]
• 14: Floyd, R. 1972. Permuting information in idealized two-level storage. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, N.Y., 105--109.
• 15: Christine Fricker , Olivier Temam , William Jalby, Influence of cross-interferences on blocked loops: a case study with matrix-vector multiply, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.561-575, July 1995 [doi>10.1145/210184.210185]
• 16: Frigo, M., and Johnson, S. G. 1998. FFTW: An adaptive software architecture for the FFT. In Proceedings of ICASSP'98, vol. 3 (Seattle, Wash.). IEEE Computer Society Press, Los Alamitos, Calif., 1381.
• 17: 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
• 18: Goodrich, M., Tsay, J., Vengroff, D., and Vitter, J. 1993. External memory computational geometry. In Proceeding of IEEE Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 714--723.
• 19: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 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: Kamath, A., Motwani, R., Palem, K., and Spirakis, P. 1994. Tail bounds for occupancy and the satisfiability threshold conjecture. In Proceeding of IEEE Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 592--603.
• 22: Richard E. Ladner , James D. Fix , Anthony LaMarca, Cache performance analysis of traversals and random accesses, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.613-622, January 17-19, 1999, Baltimore, Maryland, United States
• 23: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 24: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 25: Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
• 26: Mehlhorn, K., and Sanders, P. 2000. Scanning multiple sequences via cache memory. citeseen.nj.nec.com/506957.html.
• 27: Steven A. Przybylski, Cache and memory hierarchy design: a performance-directed approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 28: Peter Sanders, Accessing Multiple Sequences Through Set Associative Caches, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.655-664, July 11-15, 1999
• 29: John E. Savage, Extending the Hong-Kung Model to Memory Hierarchies, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.270-281, August 24-26, 1995
• 30: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 31: Mithuna Thottethodi , Siddhartha Chatterjee , Alvin R. Lebeck, Tuning Strassen's matrix multiplication for memory efficiency, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
• 32: Jeffrey Scott Vitter , Mark H. Nodine, Large-scale sorting in uniform memory hierarchies, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.107-114, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1008]
• 33: Vitter, J., and Shriver, E. 1994. Algorithms for parallel memory. I: Two-level memories. Algorithmica 12, 2, 110--147.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.0 General
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Experimentation, Theory, Verification

Keywords:
Hierarchical memory, I/O complexity, lower bound