Running External Memory Algorithms on Hardware Caches

has to be taken into account in order to design algorithms which
perform well for large inputs.
It has been empirically observed that
external memory algorithms, i.e., algorithm originally
developed to work with disks,
often also turn out to
be good algorithms for the hierarchy between cache and main memory.
This is not self evident since
caches have a fixed and quite restrictive algorithm choosing
the content of the cache (\emph{$a$-way associative caches}).
The impact of this restriction is studied here.
It is argued that the most interesting case is
the concurrent traversal of multiple sequences.
It turns out that any access pattern to
$k=\Th{M/B^{1+1/a}}$ sequential data streams can be efficiently
supported on an $a$-way set associative cache with capacity $M$ and line
size $B$.
The bounds are tight up to lower order terms.