Abstract

Cache-Oblivious Algorithms

Computers with multiple levels of caching have traditionally required techniques such as data blocking in order for algorithms to exploit the cache hierarchy effectively. These "cache-aware" algorithms must be properly tuned to achieve good performance using so-called "voodoo" parameters which depend on hardware properties, such as cache size and cache-line length. Surprisingly, however, for a variety of problems -- including matrix multiplication, FFT, and sorting -- asymptotically optimal "cache-oblivious" algorithms do exist that contain no voodoo parameters. They perform an optimal amount of work and move data optimally among multiple levels of cache. Since they need not be tuned, cache-oblivious algorithms are more portable than traditional cache-aware algorithms. We employ an "ideal-cache" model to analyze these algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal across a multilevel cache hierarchy. We also show that the assumption of optimal replacement made by the ideal-cache model can be simulated efficiently by LRU replacement. We also provide some empirical results on the effectiveness of cache-oblivious algorithms in practice.

Prof. Charles E. Leiserson's research centers on developing theoretical principles of parallel and distributed computing, especially as they relate to engineering reality. He pioneered the development of VLSI theory and co-authored the first paper on systolic architectures. While at Thinking Machines Corporation, he designed and led the implementation of the network architecture for the Connection Machine CM-5 Supercomputer, which incorporates the fat-tree interconnection network he developed at MIT. Prof. Leiserson's recent research has focused on dynamic, asynchronous parallel computing. His Cilk multithreaded language features a provably good work-stealing scheduler that guarantees the efficient execution of user programs. He and his research group designed and implemented the StarTech, *Socrates, and Cilkchess parallel chess-playing programs, which have won numerous prizes in international competition. Prof. Leiserson's textbook, Introduction to Algorithms, Second Edition coauthored with Cormen, Rivest, and Stein) is currently the leading textbook on computer algorithms.

Back to Distinguished Lecture Series - Fall 2003 / Spring 2004 Schedule