Efficient Calculation of Expected Miss Ratios in the Independent Reference Model

In the independent reference model of program behavior, King’s formulas for the expected FIFO (“first-in-first-out”) and expected LRU (“least-recently-used”) miss ratios each contain an exponential number of terms (very roughly n^CAP, where n is the number of pages and CAP is the capacity of main memory). Hence, under the straightforward algorithms, these formulas are computationally intractable. We present an algorithm which is both efficient (there are O(n · CAP) additions, multiplications, and divisions) and provably numerically stable, for calculating the expected FIFO miss ratio. In the case of LRU, we present an efficient method, based on an urn model, for obtaining an unbiased estimate of the expected LRU miss ratio (the method requires O(n · CAP) additions and comparisons, and O(CAP) divisions and random number generations).