Some mathematical facts about optimal cache replacement

Pierre Michaud 1
1 PACAP - Pushing Architecture and Compilation for Application Performance
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : This paper exposes and proves some mathematical facts about optimal cache replacement that were previously unknown or not proved rigorously. An explicit formula is obtained, giving OPT hits and misses as a function of past references. Several mathematical facts are derived from this formula, including a proof that OPT miss curves are always convex, and a new algorithm called OPT tokens, for reasoning about optimal replacement.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01411156
Contributor : Pierre Michaud <>
Submitted on : Friday, January 27, 2017 - 10:25:09 AM
Last modification on : Thursday, March 14, 2019 - 9:44:05 AM

Files

halopt.pdf
Files produced by the author(s)

Identifiers

Citation

Pierre Michaud. Some mathematical facts about optimal cache replacement. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2016, 13 (4), ⟨10.1145/3017992⟩. ⟨hal-01411156v2⟩

Share

Metrics

Record views

991

Files downloads

778