|
|
|
|
|
|
|
Appendix C
Modeling System Effects in Caches |
|
|
|
|
|
|
|
|
Our miss rates for cold start caches are computed from a stochastic model based on Haikala's work [116, 117]. Haikala's basic model assumes fullyassociative LRU caches. An application program always starts with a coldstart cache and runs for a geometric distributed interval of an average of Q memory references before task switches. The entire cache is flushed at task switch. Cache behavior is modeled as a Markov chain. For a cache of n lines, the Markov chain has n + 1 states: S0, ,Sn (Figure C.1). The cache is said to be in the state Si when it contains only i valid lines. The probability that a task switch occurs before the next memory reference is e. If there is no task switch and the next memory reference is a cache hit, the cache remains in the same state. Otherwise a cache miss occurs and a new line is brought into the cache. The cache state then changes from Si to Si+1 unless the cache state is already in Sn. When a cache is in Sn, it remains there until task switch. Since the cache is fully associative and uses LRU replacement, the probability that the next memory reference is a cache miss is the same as the miss rate of a warm-start cache of i lines, MRwarm. By solving the stationary state probabilities of the Markov chain, P0, ,Pn, the cache miss rate MRn can be determined from the following equations: |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
Haikala has shown that miss rates calculated from the preceding Markov chain model are at most 12% off simulation results. |
|
|
|
|
|