Should caches be split or shared? Analysis using the superposition of bursty stack depth processes

Abstract

We address the question as to whether caches containing items of different types should be split or shared. We characterize the access to those caches as stack depth processes and show that the process defining the mixing of the access streams to the different types is the critical determining factor, with the burstiness of the individual streams being a key parameter. We characterize the mixing process using a double-geometric model, and give an exact solution for the behavior of a LRU cache when it is subjected to such a mixed stream of stack depth processes. We show that this minimalist approach is quite successful in dealing with real data from a database application. We further extend the model to a Markov mixing model which is more accurate but has higher complexity.