Accessing Multiple Sequences Through Set Associative Caches

The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms which perform well in practice. We start from the empirical observation that external memory algorithms often turn out to be good algorithms for cached memory. This is not self evident since caches have a fixed and quite restrictive algorithm choosing the content of the cache. We investigate the impact of this restriction for the frequently occurring case of access to multiple sequences. We show 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