Shuchang Zhou proposed a efficient algorithm to calculating the hit probability for cache with random replacement policy.

How much one cache can influence performance are often evaluated by running a cache simulator by collected traces. Different associativities, sizes and replacement policies will lead to different result. But for one special cache with random replacement policies, single round simulation can only gives one possible result of performance because of the randomness. So we have to run the simulation multiple times to get a average performance which is very inefficiency.

Based on this observation, they came up with a efficient way to calculate hit probability of each memory access by using expectation, which can be used to derive miss ratio.

Foundation:

The trace of the accessed sequence (cache lines) is:

a0, a1, a2, …, aN.

The miss event of time *i* is X*i.* if a miss event happens at *i, *then X*i* = 1, else X*i *= 0.

X0, X1, X2, … XN.

So the hit event will be 1-X*i* at time i.

Assume k is the time when the reuse window starts, the number of misses since k to time i will be Z*i.*

If the reuse window exists,

Z*i *= sum(X*l*), ( k+1<=*l<= *i-1 )

Else,

Z*i = *infinite

The expectation will be the following according to the linearity of expectation,

E(Z*i*) = sum( E(X*l*) ) , ( k+1<=*l<= *i-1 ) or infinite

With the definition number of misses Z*i, *E(X*i*) can be defined as:

E(X*i*) = 1 – E( (1-1/M)^Z*i* ), M is the cache size

When M is very large,

E(X*i*) ~ 1-(1-1/M)^E(Z*i*)

Proof:

if Z*i* == infinite:

1-(1-1/M)^E(Z*i*) = 1 – E( (1-1/M)^Z*i* ) = 0

Else:

Then they proposed two algorithms to calculate E(Z*i* ) efficiently from E(X*i*) and compared the results with average 5, 50, 500 round naive simulation which proves their method has less error.

Random replacement in cache has been used in various caching models. A often neglected issue is the non-determinism of random replacement. This paper solves the problem with a one-pass solution to compute the expected miss ratio.