hesela.devKosmo
Kosmo estimates miss-ratio curves for supported cache-eviction policies using shared object records and policy-specific eviction maps.
Mechanism: eviction maps reconstruct cache states when needed; a histogram of minimum containing-cache sizes becomes the estimated curve. The design also uses SHARDS sampling. [1]
Boundary: the output is nonincreasing even for policies that violate inclusion. It cannot exactly represent an upward segment of the actual miss-ratio curve. [1]
Policy identity: Kosmo distinguishes ideal LFU, which retains frequency counters for evicted objects, from the modeled reset-on-eviction variant. Reaccess starts the latter counter at one; its resident sets can violate inclusion. A stack-method result for ideal LFU does not automatically apply to this variant. [1]
Evaluation: LFU and FIFO used 52 traces, while 2Q and LRFU used 33. The described LRU and MRU variants were not included in the performance evaluation. [1]
Alternative: Miniature Simulations evaluates sampled caches at selected capacities; it does not impose the same single-histogram shape. It still has sampling error and configuration costs. [2]
Exact illustration: the existing FIFO example has 9/12 misses at three slots and 10/12 at four. Any nonincreasing estimate must have maximum absolute error at least 1/24 over those two points. This is an algebraic bound, not a measured Kosmo error or a bound on mean error. [3]
Relations
- related
- Miss-ratio curve, Cache inclusion property, Belady anomaly, First-in first-out cache replacement
Citations
- Shakiba, Sultan and Stumm. Kosmo: Efficient Online Miss Ratio Curve Generation for Eviction Policy Evaluation. FAST 2024.
- Waldspurger, Saemundson, Ahmad and Park. Cache Modeling and Optimization using Miniature Simulations. USENIX ATC 2017, pp. 487-498; sections 1.1 and 3.1-3.2.
- Hesela: exact monotone approximation bound from the existing FIFO capacity counts; code and assumptions linked in the companion article.
Sources & caveats
- Source review and exact arithmetic only. No Kosmo implementation was executed.