Insertion Policy Selection Using Decision Tree Analysis

Abstract : The last-level cache (LLC) mitigates the impact of long memory access latencies in today's microarchitectures. The insertion policy in the LLC can have a significant impact on cache efficiency. However, a fixed insertion policy can allow useless blocks to remain in the cache longer than necessary, resulting in inefficiency. We introduce insertion policy selection using Decision Tree Analysis (DTA). The technique requires minimal hardware modification over the least-recently-used (LRU) replacement policy. This policy uses the fact that the LLC filters temporal locality. Many of the lines brought to the cache are never accessed again. Even if they are reaccessed they do not experience bursts, but rather they are reused when they are near to the LRU position in the LRU stack. We use decision tree analysis of multi-set-dueling to choose the optimal insertion position in the LRU stack. Inserting in this position, zero reuse lines minimize their dead time while the non-zero reuse lines remain in the cache long enough to be reused and avoid a miss. For a 1MB 16 way set-associative last level cache in a single core processor, our entry uses only 2069 bits over the LRU replacement policy.
Type de document :
Communication dans un congrès
Joel Emer. JWAC 2010 - 1st JILP Worshop on Computer Architecture Competitions: cache replacement Championship, Jun 2010, Saint Malo, France. 2010
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00492972
Contributeur : Ist Rennes <>
Soumis le : jeudi 17 juin 2010 - 15:03:58
Dernière modification le : lundi 20 juin 2016 - 14:10:32
Document(s) archivé(s) le : lundi 20 septembre 2010 - 17:09:37

Fichier

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

Identifiants

  • HAL Id : inria-00492972, version 1

Collections

Citation

Samira Khan, Daniel A. Jimenez. Insertion Policy Selection Using Decision Tree Analysis. Joel Emer. JWAC 2010 - 1st JILP Worshop on Computer Architecture Competitions: cache replacement Championship, Jun 2010, Saint Malo, France. 2010. 〈inria-00492972〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

183