Cache-Oblivious and Cache-Aware Algorithms

Motivation

A recent trend in algorithmic design and analysis is to pay increasing attention to the memory hierarchy of a modern computer, motivated by the major impact it has on the performance of algorithms. Many approaches and models have been developed, one of the more successful of which is the body of work in external-memory algorithms , which effectively models a two-level memory hierarchy, traditionally main memory and disk. Recently (1999), the concept of cache-oblivious algorithms was proposed as a powerful theoretical model with potential for major practical impact, especially for cache efficiency. The idea is to hide any parameters of the memory hierarchy--such as block transfer sizes and the size of each memory level--from the algorithm. This simple idea has powerful ramifications:

1. Cache-oblivious algorithms automatically adapt to arbitrary memory hierarchies.
2. Cache-oblivious algorithms can be analyzed on a simple two-level memory hierarchy, and then automatically perform as well on a complex multilevel memory hierarchy with particular page replacement strategies, limited associativity, etc.

Motivated by these exciting consequences, an increasing number of researchers have started to develop algorithms and data structures in this model. In the past 3 years, there have been over a dozen papers developing efficient cache-oblivious algorithms and data structures. The field has been shown to have substantial depth and has led to new general techniques for maintaining data locality in a memory hierarchy.

Yet the field of cache-oblivious algorithms is still in its infancy. Several theoretical issues remain unsolved and ripe for exploration, bridging the gap between the best algorithms known in the external-memory and cache-oblivious contexts. On the practical side, the main issue is to what extent cache-oblivious algorithms are useful in the real world and throughout computer science. One issue here is how well the cache-oblivious model matches real caches, for example, in the context of the Translation Lookaside Buffer (TLB). In addition to the need for more thorough algorithmic experiments, the algorithms community needs to become aware of more practical problems for which cache-oblivious algorithms may be useful.

The goal of this seminar is to bring together people from various disciplines in order to address these issues and mature the field of cache-oblivious and other cache-efficient algorithms. These disciplines include both the algorithms community--specifically, external-memory algorithms, data structures, and experimental algorithmics, in addition to cache-oblivious algorithms--as well as various applied communities in computer science.