Cache Performance of Algorithms

CSE Home

About Us

Search

Contact Info

People  Richard Ladner  Jeremy Cho  Kevin Dick (Cal Tech) Alumni  Anthony LaMarca  Jim Fix  Cary Cherng  Shen Pan  Kevin Zatloukal  Ray Fortna  Bao-Hoang Nguyen  Gabriel Deal  Eric Hesselgesser  Lam Nguyen

Overview Because modern computer have relatively slow memories, caches are employed to speedup access to recently reference data. In this project we study how caches affect the performance of algorithms. There are two component problems to study: (i) the problem of how to design algorithms which have good memory performance and good overall performance, and (ii) the problem of how to analytically predict the memory performance of an algorithm. We design, implement, and evaluate memory optimized algorithms in a number of areas and systematically compare the memory optimized algorithms with the classic versions of these algorithms. We compare algorithms using trace-driven cache simulation, cache miss analysis, and timings of implementations. We also use new analytic techniques to accurately predict the number of cache misses. Universally, the implicit advice given in data structures and algorithms texts is that if you want to solve a problem faster, then try to find an algorithm that uses fewer instructions. This advice is no longer true because, on modern processors with caches, an algorithm with a low instruction count and a high number of cache misses may not perform as well as one with a high instruction count and a low number of cache misses. Publications S. Pan, C. Cherng, K. Dick and R.E. Ladner. Algorithms to Take Advantage of Hardware Prefetching. To appear Workshop on Algorithm Engineering and Experiments (ALENEX '07). C. Cherng and R.E. Ladner. Cache Efficient Simple Dynamic Progamming. 2005 International Conference on the Analysis of Algorithms. (AofA 2005), 49-58. R.E. Ladner, R. Fortna, and B.-H. Nguyen. A Comparison of Cache Aware and Cache Oblivious Static Search Trees using Program Instrumentation. Published in Experimental Algorithmics, From Algorithm Design to Robust and Efficient Software, LNCS 2547, edited by R. Fleischer, B. Moret, and E.M. Schmidt, Springer-Verlag, Berlin, 2002, 78-92. R.E. Ladner, J.D. Fix and R.E. Ladner. Cache Performance Analysis of Traversals and Random Accesses. To appear in Proceeding of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1999 A. LaMarca and R.E. Ladner. The Influence of Caches on the Performance of Sorting. Journal of Algorithms Vol. 31, 1999, 66-104. A. LaMarca and R.E. Ladner. The Influence of Caches on the Performance of Sorting. Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 370-379, 1997. A. LaMarca and R.E. Ladner. The Influence of Caches on the Performance of Heaps. Journal of Experimental Algorithmics, Vol. 1, 1996.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to ladner]