Cache-Oblivious Algorithms and Data Structures

Gerth Stølting Brodal

In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, pages 3-13. Springer Verlag, Berlin, 2004.

Abstract

Frigo, Leiserson, Prokop and Ramachandran in 1999 introduced the ideal-cache model as a formal model of computation for developing algorithms in environments with multiple levels of caching, and coined the terminology of cache-oblivious algorithms. Cache-oblivious algorithms are described as standard RAM algorithms with only one memory level, i.e. without any knowledge about memory hierarchies, but are analyzed in the two-level I/O model of Aggarwal and Vitter for an arbitrary memory and block size and an optimal off-line cache replacement strategy. The result are algorithms that automatically apply to multi-level memory hierarchies. This paper gives an overview of the results achieved on cache-oblivious algorithms and data structures since the seminal paper by Frigo et al.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2004. All rights reserved.

Online version

swat04invited.pdf (128 Kb)

DOI

10.1007/978-3-540-27810-8_2

Links

• Springer Verlag
• Lecture Notes in Computer Science

Slides

swat04invited.pdf (545 Kb)

BIBT_EX entry

@incollection{swat04invited,
  author = "Gerth Stølting Brodal",
  booktitle = "Proc. 9th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/978-3-540-27810-8_2",
  isbn = "978-3-540-22339-9",
  pages = "3-13",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Cache-Oblivious Algorithms and Data Structures",
  volume = "3111",
  year = "2004"
}