ALCOMFT-TR-03-74

Gerth Stølting Brodal and Rolf Fagerberg
On the Limits of Cache-Obliviousness
Århus. Work packages 1 and 4. 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.

Postscript file: ALCOMFT-TR-03-74.ps.gz (174 kb).