Algorithmes Cache-Oblivious

Prudence : document en construction, et structure en émergence...

Un algorithme est Cache-Oblivious s'il est écrit pour tenir compte de la réalité de l'existence d'une Cache au sens large sans toutefois être paramétré spécifiquement pour les caractéristiques d'une Cache particulière.

L'idée ici est d'en arriver à des algorithmes qui soient « optimaux » dans un sens général, quitte à pouvoir être optimisés un peu plus en connaissant les caractéristiques de la hiérarchie de la mémoire sur un ordinateur spécifique.

Technique générale

La plupart des algorithmes Cache-Oblivious suivent une démarche de type « diviser pour régner », du fait qu'en procédant ainsi, dans la mesure où le subtrat entrepose les données de manière contiguë en mémoire, l'algorithme en vient éventuellement à traiter des données qui se trouvent logées en Cache. En gros, un algorithme Cache-Oblivious demande des retouches pour être vraiment optimal, mais ces retouches sont souvent de l'ordre du bon choix de constante plutôt que de l'ordre des changements en profondeur.

On réfléchit un algorithme Cache-Oblivious comme s'il était écrit pour un ordinateur muni d'une mémoire vive et d'une zone de Cache d'une certaine taille (on utilise une constante symbolique pour en faire abstraction). On estime que la Cache sera mise à jour selon une stratégie raisonnable dans le contexte (typiquement : LRU, pour Least-Recently Used, où le bloc de Cache le moins récemment utilisé sera remplacé par le prochain bloc requis mais non en Cache)

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !