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.
Type de document :
Article dans une revue
ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2016, 13 (4), 〈10.1145/3017992〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01411156
Contributeur : Pierre Michaud <>
Soumis le : vendredi 27 janvier 2017 - 10:25:09
Dernière modification le : mercredi 16 mai 2018 - 11:24:11

Fichiers

halopt.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

874

Téléchargements de fichiers

417