Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 04301

Cache-Oblivious and Cache-Aware Algorithms

( Jul 18 – Jul 23, 2004 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



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.

  • Deepak Ajwani (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Luca Allulli (Sapienza University of Rome, IT)
  • Lars Arge (Aarhus University, DK) [dblp]
  • Michael A. Bender (SUNY - Stony Brook, US) [dblp]
  • Gianfranco Bilardi (University of Padova, IT)
  • Henrik Blunck (Universität Münster, DE)
  • Gerth Stølting Brodal (Aarhus University, DK) [dblp]
  • Andrej Brodnik (University of Primorska, SI) [dblp]
  • Sergio Cabello (University of Ljubljana, SI) [dblp]
  • Alexandru Caracas (International University Bruchsal, DE)
  • Rezaul Chowdhury (University of Texas - Austin, US) [dblp]
  • Andrew Danner (Duke University - Durham, US)
  • Mark de Berg (TU Eindhoven, NL) [dblp]
  • Erik D. Demaine (MIT - Cambridge, US) [dblp]
  • Roman Dementiev (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Camil Demetrescu (Sapienza University of Rome, IT) [dblp]
  • Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
  • Rolf Fagerberg (University of Southern Denmark - Odense, DK) [dblp]
  • Martin Farach-Colton (Rutgers University - Piscataway, US) [dblp]
  • Arash Farzan (University of Waterloo, CA)
  • Jeremy Fineman (MIT - Cambridge, US) [dblp]
  • Irene Finocchi (University of Rome "Tor Vergata", IT) [dblp]
  • Jim Fix (Reed College - Portland, US)
  • Seth Gilbert (MIT - Cambridge, US) [dblp]
  • Tracy Grauman (Rutgers University - New Brunswick, US)
  • Roberto Grossi (University of Pisa, IT) [dblp]
  • Herman J. Haverkort (TU Eindhoven, NL) [dblp]
  • John Iacono (Polytechnic Institute of NYU - Brooklyn, US) [dblp]
  • Alon Itai (Technion - Haifa, IL)
  • Shahid Jabbar (TU Dortmund, DE)
  • Riko Jacob (ETH Zürich, CH) [dblp]
  • Bradley C. Kuszmaul (MIT - Cambridge, US) [dblp]
  • Stefan Langerman (Free University of Brussels, BE) [dblp]
  • Charles E. Leiserson (MIT - Cambridge, US) [dblp]
  • Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Ulrich Carsten Meyer (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Gabriel Moruz (Aarhus University, DK) [dblp]
  • Miguel A. Mosteiro (Rutgers University - Piscataway, US) [dblp]
  • Ian Munro (University of Waterloo, CA) [dblp]
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Keshav Pingali (Cornell University, US) [dblp]
  • Harald Prokop (Akamai Technologies - Cambridge, US)
  • Naila Rahman (University of Leicester, GB)
  • Vijaya Ramachandran (University of Texas - Austin, US) [dblp]
  • Rajeev Raman (University of Leicester, GB) [dblp]
  • Ulrich Rüde (Universität Erlangen-Nürnberg, DE) [dblp]
  • Vasilis Samoladas (TU Crete - Chania, GR)
  • Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Vasilis Saoladas (University of Crete - Heraklion, GR)
  • Jop Frederik Sibeyn (Martin-Luther-Universität Halle-Wittenberg, DE)
  • Sivan Toledo (Tel Aviv University, IL) [dblp]
  • Laura I. Toma (Bowdoin College - Brunswick, US) [dblp]
  • Jan Vahrenhold (Universität Münster, DE) [dblp]
  • David Wise (Indiana University - Bloomington, US)
  • Norbert Zeh (Dalhousie University, CA) [dblp]