18. – 23. Juli 2004, Dagstuhl-Seminar 04301

Cache-Oblivious and Cache-Aware Algorithms


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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Dagstuhl's Impact: Dokumente verfügbar


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.


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.