|
|
|
|
|
|
|
Figure C.1
The Markov chain cold-start cache model. |
|
|
|
|
|
|
|
|
We adopt Haikala's basic model to compute cold start misses for different task switch intervals. In our computation, the warm-start cache miss rates are determined from DTMR. |
|
|
|
|
|
|
|
|
C.2 Cache Misses in Multiprogramming Environment |
|
|
|
|
|
|
|
|
We extend the stochastic cold-start cache model to compute cache miss rates in multiprogramming environment. If needed, fully associative LRU caches are assumed. All multiprogramming programs' cache behaviors are assumed statistically the same and have DTMR as their warm-start cache miss rates. Similar to the cold-start cache modeling, each program runs for a geometric distributed interval of an average of Q memory references before task switches to other program. However, cache is not flushed at task switch. Next time when the program is scheduled to resume execution, some valid memory lines (known as foot prints) may remain in the cache. |
|
|
|
|
|
|
|
|
We model the multiprogramming effect by a two-dimensional Markov chain. For a cache of n lines, the Markov chain has 2n states (Figure C.2). Besides the n states (S0, ,Sn) as defined in the cold-start cache model, n new states (X0, ,Xn) are introduced to model the effect of other programs on the cache. When other programs are running and the cache still contains i valid lines, the cache is said in the state Xi. All other programs can be viewed just as another program (the equivalent program) and the cache behaves as if it contains n - i lines for the equivalent program. For a multiprogramming level of N, other programs (so is the equivalent program) will run for an interval of an average of (N 1) * Q memory references before task switches back to the program. When the program resumes execution, |
|
|
|
|
|
