Skip to Main content Skip to Navigation
New interface
Journal articles

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 metadata
Contributor : Pierre Michaud Connect in order to contact the contributor
Submitted on : Friday, January 27, 2017 - 10:25:09 AM
Last modification on : Friday, July 8, 2022 - 10:05:12 AM


Files produced by the author(s)



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



Record views


Files downloads