On the Limits of Cache-Obliviousness

Gerth Stølting Brodal and Rolf Fagerberg

Technical Report, ALCOMFT-TR-03-74, ALCOM-FT, 17 pages, November 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.

Online version

alcomft-tr-03-74.pdf (190 Kb)

BIBTEX entry

@techreport{alcomft-tr-03-74,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  institution = "ALCOM-FT",
  month = "November",
  number = "ALCOMFT-TR-03-74",
  pages = "17",
  title = "On the Limits of Cache-Obliviousness",
  year = "2003"
}