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).

Un exemple simpliste d'un algorithme Cache-Oblivious serait celui d'un tri fusion. La version naïve (proposée à droite) illustre cette propriété de Cache-Obliviousness, du moins si le substrat est contigu en mémoire :

Soit deux fonctions,(complexité $O(n^2)$ : inefficace, sauf si l'intervalle à trier est de petite taille) et(complexité $O(n \times log_{2}n)$ : efficace sur des intervalles de grande taille), en plus d'une fonction tri() servant d'interface et permettant de choisir la meilleure parmi les deux premières en fonction de la taille de l'intervalle
La fonction tri_bulles(), malgré sa complexité, peut être rapide pour des intervalles de petite taille, en partie car sa complexité y est moins un facteur, et en partie parce que la petite taille facilite le positionnement en Cache des éléments
La fonction tri_fusion(), quant à elle, coupe la séquence en deux sous-séquences de plus petite taille, ce qui tend à faire converger les intervalles à trier vers des blocs d'une taille convenant à une ligne de Cache

Exprimé sous cette forme, peu importe la taille des lignes de Cache, si le substrat est contigu en mémoire, la taille des plages à trier finira par être assez petite pour y entrer.

Enfin, notez que dans un, après les tris des sous-séquences, une étape de fusion des sous-séquences triées est requise. Cette opération est de complexité linéaire (complexité $O(n)$ ) et est très Cache-Friendly

#include <iterator>
#include <utility>
#include <algorithm>
// déclarations a priori
// tri_bulles() : inefficace sauf si distance(debut,fin) très petit
template <class It>
   void tri_bulles(It, It);
// tri_fusion() : plus efficace, et converge vers une Cache Line
template <class It>
   void tri_fusion(It, It);
// interface vers les tris
template <class It>
   void tri(It debut, It fin) {
      using std::distance;
      if (distance(debut, fin) <= 10) // seuil à valider
         tri_bulles(debut, fin);
      else
         tri_fusion(debut, fin);
   }
template <class It>
   void tri_bulles(It debut, It fin) { 
      using namespace std;
      for(; debut != fin; ++debut)
         for(auto p = next(debut); p != fin; ++p)
            if (*p < *debut)
               swap(*p, *debut);
   }
template <class It>
   void tri_fusion(It debut, It fin) {
      using namespace std;
      auto n = distance(debut, fin);
      auto mid = next(debut, n / 2);
      tri(debut, mid);
      tri(mid, fin);
      inplace_merge(debut, mid, mid, fin)
   }

Lectures complémentaires

Quelques liens pour enrichir le propos.

http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms
Transformer un algorithme qui ne tient pas compte de l'antémémoire en son équivalent Cache-Aware ou encore en son équivalent Cache-Oblivious sans modifier sa complexité algorithmique, texte d'Ian Fraser en 2013 : http://iainkfraser.blogspot.co.uk/2013/01/cache-money-hoes-attached-code.html
Mémoire par Harald Prokop en 1999 : http://supertech.csail.mit.edu/papers/Prokop99.pdf
Article sur le sujet, par Erik Demain en 2002 : http://erikdemaine.org/papers/BRICS2002/paper.pdf
Survol du concept par Erik Demain en 2003 : http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L15/lecture15.pdf
Présentation de Gerth Stølting Brodal en 2004 : http://cs.au.dk/~gerth/slides/swat04invited.pdf