On the Limits of Cache-Obliviousness

Gerth Stølting Brodal and Rolf Fagerberg

In Proc. 35th Annual ACM Symposium on Theory of Computing, pages 307-315, 2003.

Abstract

In this paper, we present lower bounds for permuting and sorting in the cache-oblivious model. We prove that (1) I/O optimal cache-oblivious comparison based sorting is not possible without a tall cache assumption, and (2) there does not exist an I/O optimal cache-oblivious algorithm for permuting, not even in the presence of a tall cache assumption.

Our results for sorting show the existence of an inherent trade-off in the cache-oblivious model between the strength of the tall cache assumption and the overhead for the case M >> B, and show that Funnelsort and recursive binary mergesort are optimal algorithms in the sense that they attain this trade-off.

Copyright notice

Copyright © 2003 by the Association for Computer Machinery, Inc.

Online version

stoc03.pdf (158 Kb)

DOI

10.1145/780542.780589

BIBTEX entry

@inproceedings{stoc03,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 35th Annual ACM Symposium on Theory of Computing",
  doi = "10.1145/780542.780589",
  isbn = "1-58113-674-9",
  pages = "307-315",
  title = "On the Limits of Cache-Obliviousness",
  year = "2003"
}

Other versions