Algorithme cache-agnostique

L'idée (et le nom) des algorithmes indépendants du cache a été conçue par Charles E. Leiserson dès 1996 et publiée pour la première fois par Harald Prokop dans sa thèse de maîtrise au Massachusetts Institute of Technology en 1999^[1]. De nombreuses études antérieures ont analysé des problèmes spécifiques ; ceux-ci sont examinés en détail dans Frigo et al. 1999. Parmi les premiers exemples cités, on peut citer Singleton 1969 pour une transformée de Fourier rapide récursive, des idées similaires dans Aggarwal et al. 1987, Frigo 1996 pour la multiplication matricielle et la décomposition LU, et Todd Veldhuizen 1996 pour les algorithmes matriciels dans la bibliothèque Blitz++ .

Généralement, on peut rendre un programme plus sensible au cache^[2] :

• Localité temporelle, c'est-à-dire lorsque l'algorithme accède plusieurs fois aux mêmes zones de mémoire;
• Localité spatiale, dans laquelle les accès successifs à la mémoire se produisent à des adresses mémoire adjacentes ou proches.

Les algorithmes indépendants du cache sont généralement analysés à l'aide d'un modèle idéalisé du cache, parfois appelé « modèle du cache-agnostique ». Ce modèle est beaucoup plus facile à analyser que les caractéristiques d'un cache réel (qui présente une associativité complexe, des politiques de remplacement, etc.), mais il est souvent démontré qu'il se situe à un facteur constant près des performances d'un cache plus réaliste. Il diffère du modèle de mémoire externe car les algorithmes indépendants du cache ne connaissent ni la taille des blocs ni la taille du cache.

Plus précisément, le modèle indépendants au cache est une machine abstraite (c'est-à-dire un modèle théorique de calcul ). Il est similaire au modèle de machine RAM qui remplace le ruban infini de la machine de Turing par un tableau infini. Chaque emplacement du tableau est accessible dans ${\displaystyle O(1)}$ Le temps, similaire à la mémoire vive d'un ordinateur, est utilisé. Contrairement au modèle basé sur la mémoire vive (RAM), il intègre également un cache : un deuxième niveau de stockage situé entre la mémoire vive (RAM) et le processeur. Les autres différences entre les deux modèles sont énumérées ci-dessous. Dans le modèle sans cache:

• La mémoire est divisée en blocs de ${\displaystyle B}$ objets chacun.
• Les opérations de chargement ou de stockage entre la mémoire principale et un registre du processeur peuvent désormais être effectuées à partir du cache.
• Si une charge ou un stockage ne peut pas être traité à partir du cache, on parle d'un échec de cache.
• Un défaut de cache entraîne le chargement d'un bloc depuis la mémoire principale vers le cache. Autrement dit, si le processeur tente d'accéder au mot ${\displaystyle w}$ et ${\displaystyle x}$ est la ligne contenant ${\displaystyle w}$, alors ${\displaystyle x}$ est chargé dans le cache. Si le cache était déjà plein, une ligne sera également supprimée (voir la politique de remplacement ci-dessous).
• La cache contient ${\displaystyle M}$ objets, où ${\displaystyle M=\Omega (B^{2})}$. Ceci est également connu sous le nom d'hypothèse de cache haut.
• Le cache est entièrement associatif : chaque ligne peut être chargée à n'importe quel emplacement du cache^[3].
• La stratégie de remplacement est optimale. En d'autres termes, on suppose que le cache dispose de la séquence complète des accès mémoire pendant l'exécution de l'algorithme. S'il doit évacuer une ligne à l'instant 𝑡, il examine la séquence des requêtes futures et évacue la ligne dont le premier accès est le plus éloigné dans le temps. Ce comportement peut être reproduit en pratique avec la politique LURU (Least Recently Used), dont les performances sont très proches de celles de la stratégie de remplacement optimale hors ligne, à un facteur constant près ^[4]

Pour mesurer la complexité d'un algorithme s'exécutant dans le modèle indépendant du cache, on mesure le nombre de défauts de cache qu'il subit. Le modèle prenant en compte le fait que l'accès aux éléments du cache est beaucoup plus rapide que l'accès à la mémoire principale, le temps d'exécution de l'algorithme est uniquement déterminé par le nombre de transferts de mémoire entre le cache et la mémoire principale. Ceci est similaire au modèle de mémoire externe, qui présente toutes les caractéristiques mentionnées ci-dessus, mais les algorithmes indépendants du cache sont indépendants des paramètres du cache. ${\displaystyle B}$ et ${\displaystyle M}$ L’avantage d’un tel algorithme est que ce qui est efficace sur une machine ne tenant pas compte du cache l’est probablement aussi sur de nombreuses machines réelles, sans qu’il soit nécessaire de l’optimiser en fonction des paramètres spécifiques de chaque machine. Pour de nombreux problèmes, un algorithme optimal ne tenant pas compte du cache sera également optimal pour une machine disposant de plus de deux niveaux de hiérarchie de mémoire^[4].

L'algorithme le plus simple, indépendants du cache, présenté dans Frigo et al., est une transposition de matrice hors place ( des algorithmes sur place ont également été conçus pour la transposition, mais ils sont beaucoup plus complexes pour les matrices non carrées). Étant donné un tableau A de dimensions m × n et un tableau B de dimensions n × m, nous souhaitons stocker la transposée de A dans B La solution naïve parcourt un tableau par lignes et l'autre par colonnes. Il en résulte que, lorsque les matrices sont grandes, une erreur de cache se produit à chaque étape du parcours par colonnes. Le nombre total d'erreurs de cache est ${\displaystyle \Theta (mn)}$.

L'algorithme insensible au cache possède une complexité de travail optimale ${\displaystyle O(mn)}$ et la complexité optimale du cache ${\displaystyle O(1+mn/B)}$ L'idée de base est de réduire la transposée de deux grandes matrices à la transposée de petites (sous-)matrices. Pour ce faire, on divise les matrices en deux selon leur plus grande dimension jusqu'à n'avoir plus qu'à transposer une matrice dont la taille tient dans le cache. Comme la taille du cache est inconnue de l'algorithme, les matrices continueront d'être divisées récursivement même après ce point, mais ces subdivisions supplémentaires seront stockées dans le cache. Une fois que les dimensions m et n sont suffisamment petites pour qu'un tableau d'entrée de taille ${\displaystyle m\times n}$ et un tableau de sortie de taille ${\displaystyle n\times m}$ Pour tenir dans le cache, les parcours par lignes et par colonnes donnent tous deux le même résultat. ${\displaystyle O(mn)}$ travail et ${\displaystyle O(mn/B)}$ défauts de cache. En utilisant cette approche diviser pour régner, nous pouvons atteindre le même niveau de complexité pour la matrice globale.

(En principe, on pourrait continuer à diviser les matrices jusqu'à atteindre un cas de base de taille 1 × 1, mais en pratique, on utilise un cas de base plus grand (par exemple 16 × 16) afin d'amortir la surcharge des appels de sous-routines récursives.)

La majorité des algorithmes indépendants du cache s'appuient sur une approche de type « diviser pour régner ». Ils décomposent le problème de manière à ce qu'il tienne finalement dans le cache, quelle que soit sa taille, et interrompent la récursion à une taille réduite, déterminée par la surcharge liée aux appels de fonction et à d'autres optimisations similaires sans rapport avec le cache. Ils utilisent ensuite un modèle d'accès au cache efficace pour fusionner les résultats de ces petits problèmes résolus.

Comme le tri externe dans le modèle de mémoire externe, le tri indépendant du cache est possible sous deux formes : le tri en entonnoir, qui ressemble au tri fusion ; et le tri par distribution indépendant du cache, qui ressemble au tri rapide. À l’instar de leurs homologues en mémoire externe, les deux atteignent un temps d’exécution de ${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$, qui correspond à une borne inférieure et est donc asymptotiquement optimale.

Une comparaison empirique de deux algorithmes basés sur la mémoire vive (RAM), d'un algorithme prenant en compte le cache et de deux algorithmes ne tenant pas compte du cache, mettant en œuvre des files d'attente prioritaires a révélé que :

• Les algorithmes ne tenant pas compte du cache ont obtenu des performances inférieures à celles des algorithmes basés sur la RAM et des algorithmes prenant en compte le cache lorsque les données tiennent dans la mémoire principale.
• L'algorithme prenant en compte le cache ne semblait pas significativement plus complexe à mettre en œuvre que les algorithmes ne tenant pas compte du cache, et a offert les meilleures performances dans tous les cas testés dans l'étude.
• Les algorithmes ne tenant pas compte du cache ont surpassé les algorithmes basés sur la RAM lorsque la taille des données dépassait celle de la mémoire principale.

Une autre étude a comparé les tables de hachage (basées sur la RAM ou ne tenant pas compte du cache), les arbres B (tenant compte du cache) et une structure de données insensible au cache appelée « ensemble de Bender ». En termes de temps d'exécution et d'utilisation de la mémoire, la table de hachage s'est avérée la plus performante, suivie de l'arbre B, l'ensemble de Bender étant le moins performant dans tous les cas. L'utilisation de la mémoire pour tous les tests n'a pas dépassé la mémoire principale. Les tables de hachage ont été décrites comme faciles à implémenter, tandis que l'ensemble de Bender « nécessitait un effort plus important pour être implémenté correctement »^[5].

• tri de distribution insensible au cache
• Algorithme de mémoire externe
• Tri en entonnoir