Exact Analysis of Bernoulli Superposition of Streams Into a Least Recently Used Cache

Abstract

We present an exact analysis of the superposition of address streams into a cache buffer which is managed according to a least recently used (LRU) replacement policy. Each of the streams is characterized by a stack depth distribution, and we seek the cache hit ratio for each stream, when the combined, or superposed, stream is applied to a shared LRU cache. In this paper the combining process is taken to be a Bernoulli switching process. This problem arises in a number of branches of computer science, particularly in database systems and processor architecture. Previously, a number of approximation techniques of various complexities have been proposed for the solution of this problem. The main contribution of this paper is the description of an exact technique. We evaluate the performance of the exact and an approximate technique on realistic data, both in a lab environment and a large database installation. The results allow comparisons of the techniques, and provide insight into the validity of the Bernoulli switching assumption. © 1995 IEEE