https://www.dagstuhl.de/04301

July 18 – 23 , 2004, Dagstuhl Seminar 04301

Cache-Oblivious and Cache-Aware Algorithms

Organizers

Lars Arge (Aarhus University, DK)
Michael A. Bender (SUNY – Stony Brook, US)
Erik D. Demaine (MIT – Cambridge, US)
Charles E. Leiserson (MIT – Cambridge, US)
Kurt Mehlhorn (MPI für Informatik – Saarbrücken, DE)

For support, please contact

Dagstuhl Service Team

Documents

List of Participants
Dagstuhl's Impact: Documents available

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.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.