Some mathematical facts about optimal cache replacement - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue ACM Transactions on Architecture and Code Optimization Année : 2016

Some mathematical facts about optimal cache replacement

Pierre Michaud
  • Fonction : Auteur
  • PersonId : 738135
  • IdHAL : pmichaud
Pushing Architecture and Compilation for Application Performance

Résumé

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.

Domaines

Architectures Matérielles [cs.AR]
Fichier principal
Vignette du fichier
halopt.pdf (365.43 Ko) Télécharger le fichier
HiPEAC2017.pdf (435.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Présentation
Origine : Fichiers produits par l'(les) auteur(s)

Pierre Michaud  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01411156

Soumis le : vendredi 27 janvier 2017-10:25:09

Dernière modification le : vendredi 24 mars 2023-14:53:03

Télécharger pour visualiser

Dates et versions

hal-01411156 , version 1 (07-12-2016)
hal-01411156 , version 2 (27-01-2017)

Identifiants

Citer

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

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

INSTITUT-TELECOM UNIV-RENNES1 CNRS INRIA INSA-RENNES IRISA IRISA-D3 INRIA2 UR1-MATH-STIC UR1-UFR-ISTIC UNIV-RENNES UR1-MATH-NUM
799 Consultations
1465 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More