Fonctionnement d'un ordinateur/Le cache d'instructions
Sur certains processeurs, il y a deux caches L1 séparés : un cache d'instructions, dédié aux instructions, et un autre pour les données. Les deux caches sont reliés au reste du processeur, ainsi qu'au cache L2. Pour les liaisons avec le processeur proprement dit, il y a un bus séparé pour le cache d'instruction et un autre pour le cache de données. Une telle organisation permet de charger une instruction tout en lisant une donnée en même temps. C'est théoriquement possible avec un cache L2 multiport, mais l'usage de caches séparés est plus simple. Pour les connexions avec le cache L2, tout dépend du processeur. Certains utilisent un cache L2 multiport, qui permet aux deux caches L1 de lire ou écrire dans le cache L2 simultanément.
Si le cache L2 ne gère pas les accès simultanés, il n'y a qu'un seul bus relié aux caches L1 et au cache L2. On doit effectuer un arbitrage pour décider quel cache a la priorité, chose qui est réalisé par un circuit d'arbitrage spécialisé.
Généralement, les caches d'instructions peuvent se permettre d'être plus petits que les caches de données, car les programmes sont souvent plus petits que les données manipulées. Songez que des programmes de quelques mébioctets peuvent parfois remplir la RAM avec plusieurs gibioctets de données. Lancez votre navigateur internet et ouvrez une page web un peu chargée, pour vous en convaincre !
Pourquoi séparer instructions et données dans des caches séparés ?[modifier | modifier le wikicode]
En soi, le fait de dédier un cache séparé pour les instructions est assez logique, vu que données et instructions sont deux choses radicalement différentes. Leur usage, leur utilisation, leur mode d'accès : tout cela est différent. Les conséquences sont multiples : les algorithmes de remplacement des lignes de cache optimaux pour les données ne le sont pas pour les instructions, de même que la taille du cache optimale pour les données ne l'est pas pour les instructions, la taille optimale des lignes de cache n'est pas la même, ou même les algorithmes de préchargement.
Par exemple, pour le remplacement des lignes de cache, un simple algorithme LRU est presque optimal pour les instructions, autant il peut donner de mauvaises performances quand on manipule beaucoup de tableaux. Cela justifie d'utiliser des caches spécialisés pour chacune. On peut adapter le cache d'instruction à son contenu, ce qui le rend plus rapide ou plus petit à performance égale.
La différence principale est que, comparé aux données, les instructions ont tendance à avoir une bonne localité spatiale et temporelle. Localité spatiale tout d'abord parce que des instructions consécutives se suivent en mémoire. On pourrait rétorquer que les branchements sont à l'origine de sauts dans le programme, mais les branchements qui sautent à un point éloigné dans le programme sont rares. La plupart des branchements font sauter à un endroit proche, ce qui conserve une bonne localité. De plus, les branchements sont beaucoup utilisés pour faire des boucles qui répètent la même séquence d'instruction. Les boucles sont tellement fréquentes et utilisées que la localité temporelle des instructions est généralement très bonne. Par contre, les données ont une localité moins bonne. Il faut dire que rien ne garantit que des données utilisées ensemble soient regroupées en mémoire comme le sont les instructions consécutives.
C'est aussi la raison pour laquelle, sur les architectures conventionnelles, le cache d'instruction a plus d'impact sur les performances que le cache de données. Et il existe des processeurs assez extrêmes qui se contentent d'un cache d'instruction unique, sans cache de données. C'est le cas sur les processeurs vectoriels ou les GPU que nous verrons dans les chapitres de fin de ce wikilivres. La raison est que ces processeurs sont spécialisés dans la manipulation de tableaux de données, traitement qui a une faible localité temporelle. En conséquence, utiliser un cache de données n'est pas vraiment utile, voire peu être contreproductif. Par contre, un cache d’instruction fonctionne parfaitement, les programmes exécutés ayant une bonne localité, aussi bien temporelle que spatiale.
Les avantages et inconvénients des caches d'instructions[modifier | modifier le wikicode]
Les arguments précédents justifient que l'on puisse dédier un cache aux instructions. Cependant, ces arguments sont valables à tous les niveaux de la hiérarchie mémoire, y compris au niveau du cache L2 et L3, qui sont eux unifiés. On n'a pas de cache L2 dédié aux instructions ou aux données, mais un cache L2 unique pour les deux. Comment expliquer alors que la spécialisation se fasse spécifiquement au niveau du cache L1 ? La raison est que les contraintes au niveau du cache L1 et L2 ne sont pas les mêmes. Les caches L1 et L2/L3 ont des usages différents : cache petit mais rapide pour le L1, gros et lent pour le L2/L3. Et ces contraintes sont déterminantes pour décider si tel ou tel niveau de cache est séparé en deux caches spécialisés ou non.
L'usage d'un cache d’instruction séparé du cache de données est à contraster avec l'usage d'un cache unique, capable de mémoriser à la fois instructions et données. Les deux solutions sont possibles ont été utilisées. Les premiers processeurs disposant d'un cache avaient un cache unique et multiport, mais ce n'est plus le cas sur les processeurs modernes, car les contraintes ne sont pas les mêmes. N'oublions pas que les concepteurs de processeurs sont limités en transistors et doivent faire des choix. Les transistors utilisés pour le cache d'instruction auraient pu être utilisés pour autre chose, comme augmenter la capacité des caches existants, et notamment le cache L1. Ajouter un cache d'instruction demande de faire des choix, de bien peser le pour et le contre, de bien juger des avantages et inconvénients d'un cache d'instruction.
Le premier compromis à faire est celui entre capacité des caches et performances, plus précisément entre le temps d'accès et la capacité totale du cache L1. Pour faire simple, on a le choix entre deux petits caches rapides et un gros cache plus lent. Pour rappel, plus un cache est petit, plus il est rapide et chauffe moins. Donc au lieu d'utiliser, par exemple, un gros cache lent de 64 Kibioctets, on utilise deux caches de 32 kibioctets, plus rapides. La capacité totale est la même, mais le temps d'accès plus faible. Cependant, cela vient avec un défaut qui réduit la capacité effective. Par exemple, pour un cache d'une capacité de 64 kibioctets, on peut décider de réserver 10 kb aux instructions et le reste aux données, ou encore 40 Kb aux instructions, etc. La répartition se fait naturellement, en fonction de la politique de remplacement du cache et est proche de l'optimal. Avec deux caches séparés, la répartition de la capacité du cache L1 est fixée une bonne fois pour toutes. Par exemple, avec un cache d'instruction de 32 Kb et un cache de données de 32 Kb, impossible d'allouer 40 Kb aux données et 20 aux instructions : le cache de données est trop petit. C'est là un désavantage des caches d'instructions/données séparés : une capacité effective moindre. Et cela explique en grande partie pour seul le cache L1 est séparé en deux : c'est le temps d'accès qui prime pour le cache L1, alors que la capacité effective prime pour les niveaux L2 et au-delà.
La communication du cache d'instruction avec le séquenceur[modifier | modifier le wikicode]
Une autre différence entre instructions et données est la suivante : les instructions sont utilisées par le séquenceur et les données par le chemin de données. Et cela se marie bien avec deux caches séparés, placés à des endroits très différents du processeur. Le cache d’instruction se situe en théorie entre l'unité de chargement et l'unité de décodage. En effet, ce cache prend en entrée une adresse et fournit une instruction. L'adresse est fournie par le program counter, l'instruction est envoyée dans l'unité de décodage. Le cache se situe donc entre les deux. Il est parfois intégré à l'unité de chargement, par simplicité de conception du processeur. Quant au cache de données L1 est connecté au chemin de données, et notamment aux unités de communication avec la mémoire, pas au séquenceur.
Les deux caches sont reliés au processeur par des bus séparés. Pour simplifier, l'ensemble ressemble à une architecture Harvard, mais où les caches remplacent les mémoires RAM/ROM. Le cache d'instruction prend la place de la mémoire ROM et le cache de données prend la place de la mémoire RAM. Évidemment, il y a des niveaux de caches en dessous des caches de données/instruction, et ceux-ci contiennent à la fois données et instructions, les deux ne sont pas séparées dans des mémoires/caches séparés. Raison pour laquelle l'ensemble est appelé une architecture Harvard modifiée. Architecture Harvard, car l'accès aux données et instructions se font par des voies séparées pour le processeur, modifiée car la séparation n'est effective que pour le cache L1 et pas les autres niveaux de cache, et encore moins la RAM.
Une telle organisation facilite l'implémentation de certaines optimisations, voire rend celles-ci possibles. Citons comme exemple, la technique dite du prédécodage. Pour accélérer le décodage des instructions, certains concepteurs de processeurs ont décidés d'utiliser la (ou les) mémoire cache dédiée aux instructions pour accélérer ce décodage. Lorsque ces instructions sont chargées depuis la RAM ou les niveaux de cache inférieurs, celles-ci sont partiellement décodées. On peut par exemple rajouter des informations qui permettent de délimiter les instructions ou déterminer leur taille, ce qui est utile pour décoder les instructions de taille variable. Bref, le cache d'instructions peut se charger d'une partie du décodage des instructions, grâce à un circuit séparé de l'unité de décodage d'instruction.
Le cache d'instruction est souvent en lecture seule[modifier | modifier le wikicode]
Un point important est que les instructions sont rarement modifiées ou accédées en écritures, contrairement aux données. Et cela permet d'utiliser un cache simplifié pour les instructions. Autant un cache généraliste doit permettre les lectures et écritures depuis le processeur (avec les échanges avec la RAM), autant un cache d'instruction peut se contenter des lectures provenant du CPU et des échanges avec la RAM. Le cache d'instructions est donc très souvent en « lecture seule » : le processeur ne peut pas écrire dedans, mais juste le lire ou charger des instructions dedans.
Un cache d'instruction est donc plus simple qu'un cache pour les données : on peut retirer les circuits en charge de l'écriture (mais on doit laisser un port d'écriture pour charger les instructions dedans). Le gain en circuits permet d'utiliser un cache d'instruction plus gros ou au contraire de laisser de la place pour le cache de données. Le gain en termes de capacité compense alors un peu les inconvénients des caches séparés.
Par contre, cela complique la gestion du code automodifiant, c'est-à-dire des programmes dont certaines instructions vont aller en modifier d'autres, ce qui sert pour faire de l'optimisation ou est utilisé pour compresser ou cacher un programme (les virus informatiques utilisent beaucoup de genre de procédés). Quand le processeur exécute ce genre de code, il ne peut pas écrire dans ce cache L1 d'instructions, mais doit écrire dans le cache L2 ou en RAM, avant de recharger les instructions modifiées dans le cache L1. Cela qui prend du temps et peut parfois donner lieu à des erreurs si le cache L1 n'est pas mis à jour.
L'usage d'un cache L1 unique demande d'utiliser un cache multiport[modifier | modifier le wikicode]
En théorie, on pourrait utiliser un cache L1 unique et le relier à la fois au séquenceur et au chemin de données. Mais utiliser un seul cache unifié demanderait un effort de câblage assez important, le cache devant être à la fois proche du séquenceur et du chemin de données. Les connexions entre le cache L1 unifié et le reste du processeur sont donc assez longues, tortueuses, et difficiles à câbler. De plus, ces longues connexions font que le transfert des bits prend plus de temps pour traverser le fil en longueur, ce qui pose des problèmes à haute fréquence. Avec deux caches séparés, on n'a pas ce problème, ce qui permet de garder des caches L1 très rapides. La lenteur et les problèmes de connexion sont reportés aux connexions entre les caches L1 et le cache L2, mais celui-ci accepte des temps d'accès plus longs.
Sur les processeurs modernes, il arrive très souvent que le processeur doive charger une instruction et lire/écrire une donnée en même temps. Et à vrai dire, c'est la règle plus que l'exception. L'usage d'une architecture Harvard modifiée permet cela très facilement : on peut accéder au cache d'instruction via un bus, et au cache de donnée avec l'autre. Mais cet avantage peut s'obtenir avec un cache L1 unique, en utilisant un cache multiport, avec un port relié au séquenceur et un autre au chemin de données. Et le choix entre les deux n'est pas évident. Les caches multiports sont clairement une solution viable : les caches L2 et L3 sont tous des caches multiports. Là encore, tout est histoire de compromis : les mémoires multiport sont plus lentes, plus grosses, plus compliquées à fabriquer. L'impact en termes de temps d'accès est en faveur de la mémoire simple port, tout comme la simplicité de conception. Mais pour ce qui est de l'économie de circuits, c'est moins évident. Entre deux mémoires simple port et une mémoire multiport, la différence en termes de transistors est ambigüe et dépend de la capacité des caches. Pour les caches L1 de petite capacité, le temps d'accès est très important, ce qui favorise les caches séparés. De plus, utiliser deux caches séparés n'a pas trop d'impact sur le budget en transistors, car les caches L1 sont petits. Par contre, pour les caches L2/L3/L4, le temps d'accès n'est pas déterminant, alors que l'économie en circuits est significative.
Et cette histoire de cache simple ou multiport est de plus en plus contraignante. Les processeurs modernes sont capables d’exécuter plusieurs instructions en parallèle, comme on le verra dans quelques chapitres. Et la conséquence est que les caches L1 doivent être capables de lire/écrire plusieurs données en même temps, tout en chargeant plusieurs instructions simultanément. Les deux caches L doivent donc être multiports tous les deux. Le choix est donc entre deux caches avec chacun un nombre limité de ports, ou un cache unique avec beaucoup de ports. S'il fallait utiliser un cache unique, celui-ci aurait au moins une dizaine de ports, voire plus, ce qui serait impraticable. Les concepteurs de processeurs se facilitent la vie en utilisant deux caches séparés avec peu de ports. Mais le fond du compromis est le même : soit un cache rapide avec peu de ports, soit un cache plus lent avec beaucoup de ports.
Le préchargement des instructions[modifier | modifier le wikicode]
Plus haut, nous avions dit que les données ont une moins bonne localité spatiale et temporelle que les instructions. En fait, on peut être plus général et dire que l'accès aux données est plus irrégulier que l'accès aux instructions. Je veux dire par là que les instructions sont généralement accédées dans un ordre assez prédictible : on passe d'une instruction à la suivante, sauf en cas de sauts. Par contre, les données sont généralement accédées dans le désordre, tout dépendant du traitement fait sur les dites données. Tous les programmes exécutent une suite d'instruction, mais tous ne gèrent pas les mêmes types de données, ne font pas les mêmes traitements dessus, ne les gèrent pas de la même manière, n'utilisent pas les mêmes structures de données, etc.
De fait, si les accès sont différents, alors le préchargement doit en tenir compte pour obtenir de bonnes performances. Précharger des instructions est différent de précharger des données et le prefetcher doit en tenir compte. Pour cela, certains processeurs utilisent un prefetcher séparé pour les instructions, chose qui fonctionne à la perfection si le cache d'instruction est séparé des caches de données. Les techniques utilisés par les préfetchers d'instructions sont multiples et nombreux sont ceux qui réutilisent les techniques vues précédemment. Le préchargement séquentiel est notamment utilisé sur certains prefetchers relativement simples, de même que les prefetchers de Markov. Mais certaines techniques sont spécifiques au préchargement des instructions. Il faut dire que les branchements sont une spécificité du flux d'instruction, qui doit être prise en compte par le prefetcher pour obtenir un résultat optimal.
Le préchargement séquentiel, le retour ![modifier | modifier le wikicode]
Le préchargement séquentiel est adapté au préchargement des instructions d'un programme, vu que ses instructions sont placées les unes après les autres en mémoire. Mais un prefetcher purement séquentiel gère mal les branchements.
Sur certains processeurs, cette technique est utilisée non seulement pour charger des instructions dans le cache, mais aussi pour charger à l'avance certaines instructions dans le séquenceur. Sur ces processeurs, l'unité de chargement et de décodage sont séparées par une petite mémoire tapon de type FIFO : le tampon d’instructions (instruction buffer). En utilisant du préchargement séquentiel, on peut précharger des instructions dans le tampon d’instructions à l'avance, permettant ainsi de masquer certains accès au cache ou à la mémoire assez longs. Lorsqu'un branchement est décodé, ce tampon d’instructions est totalement vidé de son contenu.
Le Target line prefetching[modifier | modifier le wikicode]
Pour gérer au mieux les branchements, il faudrait trouver un moyen de connaître l'adresse de destination. Néanmoins, le processeur peut supposer que l'adresse de destination est fixe : il suffit de s'en souvenir pour la prochaine fois. C'est ce qu'on appelle le target line prefetching.
Pour implémenter cette technique, le prefetcher incorpore un cache pour stocker les adresses de destination des branchements déjà rencontrés. Plus précisément, ce cache contient les correspondances entre une ligne de cache, et la ligne de cache à charger à la suite de celle-ci. Pour plus d'efficacité, certains processeurs ne stockent pas les correspondances entre lignes de cache consécutives. Si deux lignes de cache sont consécutives, on fait face à un défaut de cache dans la mémoire qui stocke nos correspondances. Le prefetcher utilise alors automatiquement un préchargement séquentiel. Ainsi, la table de correspondances est remplie uniquement avec des correspondances utiles.
Le préchargement du mauvais chemin[modifier | modifier le wikicode]
On peut améliorer la technique précédente pour s'adapter aux branchements conditionnels. En plus de charger les instructions correspondant à un branchement pris, on peut aussi charger les instructions situées juste après le branchement. Comme ça, si le branchement n'est pas pris, les instructions suivantes seront disponibles quand même. On appelle cette technique le préchargement du mauvais chemin (wrong path prefetching).
