Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Un travail de recherche de David Monniaux :
Complexité de l’analyse du cache
Article mis en ligne le 12 février 2020

par Laurent Bloch

En octobre 2018 David Monniaux, chercheur au laboratoire Verimag du CNRS à Grenoble, évoquait sur son fil Twitter son travail de recherche sur la complexité de l’analyse du cache. Curieux du sujet, je lui demandai des détails, il me fit parvenir un article en cours de rédaction à l’époque, désormais consultable sur arXiv, On the complexity of cache analysis for different replacement policies. La lecture en était assez ardue, aussi lorsqu’il annonça, toujours sur son fil Twitter, qu’il donnerait un séminaire à Paris le 10 février 2020, je retins la date pour y assister, dans l’espoir de mieux comprendre la démarche.

La vraie nature du cache

Le cache [1] mémoire, naguère nommé antémémoire, est un dispositif d’organisation hiérarchique de la mémoire. Plus la mémoire est rapide, plus elle est chère, alors les processeurs modernes disposent d’une mémoire très petite mais sur le même composant que le processeur, dit cache de niveau 1 (L1), accessible en deux ou trois intervalles de cycles [2] ; puis d’un cache de niveau 2 (L2), plus grand mais moins proche, accessible typiquement en une vingtaine d’intervalles de cycles, peut-être un cache L3, enfin la mémoire principale, très vaste mais dont le temps d’accès peut se compter en centaines d’intervalles de cycles. Ces ordres de grandeur montrent que l’organisation du cache et le choix des données qui y seront copiées auront une très grande influence sur les performances d’ensemble du système. L’efficacité du dispositif repose sur la capacité à maintenir le plus près possible du processeur (idéalement en L1) les données dont on suppute qu’elles seront utilisées bientôt, et à évincer du cache les données qui, selon les calculs de l’algorithme de gestion du cache, ont la plus faible probabilité d’être prochainement utilisées.

Je m’intéresse au cache parce qu’il est apparu à l’époque où je débutais en informatique, sur l’IBM 360/85, en 1968. Je l’ai rencontré personnellement en 1973, sur un IBM 370/158, de la première gamme IBM à mémoire virtuelle, et c’était un sujet de discussions passionnées, par exemple autour de la notion de working set, c’est-à-dire du petit sous-ensemble de la mémoire d’un processus réellement utilisée à un instant donné.

La technique du cache s’est avérée extrêmement efficace, elle a été transposée aux accès disque (on garde en mémoire centrale les blocs de données qui ont la plus forte probabilité d’être bientôt utilisés), ainsi qu’aux traductions d’adresses virtuelles en adresses réelles : on conserve dans un buffer du processeur, le Translation lookaside buffer (TLB), les résultats des traductions effectuées récemment, parce qu’il est probable qu’elle resserviront bientôt. Dans le cas du TLB, la technique s’est révélée si efficace que dans bien des cas (architecture MIPS par exemple) elle a permis de supprimer le circuit matériel de traduction d’adresse.

Empiriquement, la technique du cache est très efficace, sans elle les processeurs contemporains seraient de quelques ordres de grandeur plus lents, mais aussi moins chauds, parce qu’ils passeraient leur temps à attendre que la mémoire réponde. Remédier à cette lenteur demanderait un recours massif au parallélisme des traitements, et là ce sont les cerveaux des programmeurs qui seraient menacés de surchauffe. Mais en fait, à ma connaissance, on ne dispose d’aucun modèle algorithmique qui explique cette efficacité. Je pensais que David Monniaux se proposait de combler cette lacune, en fait le problème auquel il s’attaque n’est pas exactement celui-là.

Gestion du cache en environnement critique

David Monniaux travaille sur des systèmes informatiques destinés à des applications critiques, tels que ceux prévus pour des véhicules autonomes ou utilisés dans l’aéronautique. Si un métro automatique est équipé d’un dispositif de détection d’obstacle sur la voie qui déclenche l’exécution d’un programme qui va arrêter le véhicule, il faut pouvoir garantir que le temps de réaction de l’ensemble a une borne supérieure, dont en outre la valeur soit connue. Idem pour les nombreux calculateurs spécialisés qui supervisent les commande de vol d’un avion (sans ces calculateurs un avion contemporain ne pourrait pas voler, on est loin de la Caravelle de ma jeunesse qui montait à la verticale du Bourget, coupait ses moteurs et descendait en planant se poser à Dijon).

Pour celui qui réalise de tels systèmes informatiques critiques, les aléas de mémoire sont des adversaires redoutables. Il bannit les langages à gestion automatique de la mémoire par un « glaneur de cellules » (Garbage Collector, GC), susceptible de se déclencher à l’improviste pour réorganiser la mémoire d’un processus. Il se méfie de la mémoire virtuelle et des opérations d’allocation dynamique, dont le comportement est peu prévisible. Et s’il se résigne à l’existence des caches, il veut pouvoir prédire qu’une donnée y sera présente, en fonction d’une analyse statique du texte du programme. C’est l’objet de la recherche de David Monniaux.

Si une donnée est dans le cache (par exemple L1), on dit que c’est un cache hit. Si elle n’y est pas c’est un cache miss, il faut aller chercher à un niveau inférieur et on prend quelques dizaines de temps de cycle dans la vue.

Comme il a été souligné lors du séminaire, les constructeurs possèdent des informations précises sur le comportement des caches de leurs processeurs, mais ils ne les divulguent pas, ce qui oblige le chercheur à l’inférer de comportements observés.

Le cache est organisé en lignes, qui peuvent typiquement contenir 64 octets consécutifs en mémoire, en subsets qui comportent N lignes (N = 4 ou 8) et en sets. Certaines plages d’adresses sont vouées à être « cachées » dans certaines zones (sets) du cache, selon une fonction de hash non documentée.

L’algorithme de remplacement des données dans le cache le plus fréquemment utilisé est LRU (Least Recently Used). L’auteur discute les vertus (et la complexité) de cet algorithme en regard de ses concurrents FIFO (First In First Out), PLRU (pseudo-LRU), NMRU (Non-Most-Recently-Used)... Je renvoie le lecteur à l’article de l’auteur, ainsi qu’à Wikipédia pour Algorithmes de remplacement des lignes de cache, pour une introduction à ces sujets.

L’interprétation abstraite à la rescousse

Comme je l’espérais, l’exposé oral de David Monniaux lors de son séminaire du 10 février m’a aidé à comprendre des choses qui m’avaient laissé perplexe à la lecture de son article (encore à l’époque dans un état inachevé). Une présentation de moins d’une heure oblige à laisser dans l’ombre certains détails et à simplifier le sujet, ce qui en rend l’abord plus accessible. J’ai mieux compris (du moins je crois) ce qu’est l’interprétation abstraite et à quoi elle peut servir : dans ce cas par exemple, on ne s’intéresse qu’aux accès aux différents niveaux de mémoire, pour en déduire un temps d’exécution d’une séquence d’instructions dans le pire des cas (Worst-Case Execution Time, WCET). On déduira du texte du programme (le texte objet, compilé, en l’occurrence) un résumé qui n’en retient que les accès aux différentes données, ce qui va permettre d’énoncer des assertions sur leur présence dans le cache.

Si l’on cherche à répondre à des questions telles que :

 existe-t-il un chemin d’exécution tel que x soit dans le cache ?
 existe-t-il un chemin d’exécution tel que x soit en dehors du cache ?

on se heurte au mur de l’explosion combinatoire.

L’interprétation abstraite permet une analyse préalable qui, à chaque point de contrôle, donne l’ensemble Ax des âges possibles de x dans le cache, selon tous les chemins d’exécution possibles, ce qui rend le problème plus accessible.

Il existe des systèmes de calcul de temps d’exécution dans le pire des cas, tel Otawa (Open Tool for Adaptive WCET Analyses), des systèmes d’interprétation abstraite, tel Absint. Ces outils ont été utilisés par David Monniaux et son co-auteur Valentin Touzeau pour réduire la complexité du problème du cache, qui reste quand même, comme on dit, NP-difficile.

Bien évidemment, si l’on envisage un contexte où viendraient s’ajouter de l’allocation dynamique de mémoire et du parallélisme, la complexité serait encore plus grande. Et c’est bien dans cette direction que se dirige l’auteur, puisqu’il travaille avec l’entreprise Kalray, dont le processeur MPPA3 Coolidge comporte 80 cœurs VLIW (Very Long Instruction Word).