StatStack
StatStack estimates fully associative LRU cache miss ratios from sparsely sampled intervals between references to the same cache line.
Mechanism: sampled intervals feed an expected stack-distance distribution, which approximates the distribution used to estimate misses. StatCache instead models random replacement. [1] [2]
Naming: the paper calls the count of intervening accesses reuse distance and the count of distinct intervening lines stack distance. Its first quantity is a request-index reuse interval minus one; immediate repetition gives zero. [1]
Averaging: thresholding an expected distance can hide misses when individual distances straddle capacity. Sampling and approximation errors are separate; smaller sampling windows can reduce phase mixing but miss longer reuse behavior. [1]
Worked example: the final A in ABBA and ABCA has request-index interval 3, but distinct-entry distances 1 and 2. At two-slot LRU capacity, one of these two reuses misses. Comparing their mean distance 1.5 with capacity 2 predicts neither miss. This is a constructed illustration of averaging, not a StatStack implementation. [3]
Relations
Citations
- Eklov and Hagersten. StatStack: Efficient Modeling of LRU Caches. ISPASS 2010; thesis Paper I, sections I.3-I.6.
- Uppsala University. Efficient Modeling Technology: separate random-replacement and LRU models.
- Hesela. Constructed reuse intervals and mean-distance threshold example; exact event ledgers.
Further reading
Sources & caveats
- Paper I was read in the author's thesis copy, PDF pages 41-66. No original benchmark data, sampler or implementation was reproduced.
- The example checks conditional averaging only; it does not estimate StatStack accuracy or storage latency.