Brevet FR3048526A1 — publié le 20170908

INSTRUCTION ATOMIQUE DE PORTÉE LIMITÉE À UN NIVEAU DE CACHE INTERMÉDIAIRE Domaine technique L'invention est relative aux instructions atomiques de type lecture-modification-écriture 5 mises en oeuvre dans un processeur multi-coeur ayant une mémoire cache partagée, couramment une mémoire cache de niveau 2 ou supérieur. Arrière-plan La figure 1 est un schéma simplifié d'un processeur quadri-coeur connecté à une mémoire système MEM, typiquement une mémoire dynamique DDR, par 10 l'intermédiaire de deux niveaux de mémoires cache. Chaque coeur de processeur CPU possède sa propre mémoire cache Ll de niveau 1. Chaque paire de coeurs partage une mémoire cache L2 de niveau 2. Enfin, chaque mémoire cache L2 partage l'accès à la mémoire système MEM. Dans certains processeurs, on peut trouver en outre une mémoire cache de niveau 3 partagée entre les mémoires cache L2. 15 Chaque mémoire cache comprend un gestionnaire CTRL qui réalise les opérations mises en oeuvre dans la mémoire cache, y compris la gestion de la cohérence (co) entre les mémoires cache. Dans un tel processeur, on peut avoir besoin de partager des données entre des morceaux de code, ou fils de programme, exécutés sur des coeurs différents, ce qui pose 20 des difficultés compte tenu des multiples mémoires cache interposées entre les coeurs qui peuvent stocker des versions différentes des données partagées. Pour permettre un partage fiable de données entre plusieurs coeurs, on a souvent recours à des instructions atomiques de type lecture-modification-écriture, par exemple les instructions dites « Fetch-and-Add » (lecture-et-addition, FA) ou « Compare-And- 25 Swap » (comparaison-et-échange, CAS). Ces instructions ont pour caractéristique de produire un effet perçu comme instantané sur le contenu de la mémoire système, en d'autres termes les différentes opérations qui les composent, souvent la lecture d'une variable, la modification de la variable, et la récriture de la variable, sont exécutées en garantissant l'absence d'interférence externe sur la variable entre la lecture et la 30 récriture. Pour garantir l'atomicité, une première technique repose sur un verrouillage de la mémoire système, interdisant tout accès à la mémoire, ou à une zone de la mémoire, par 3048526 2 d'autres processus, même si ces processus n'accèdent pas à la variable concernée par la séquence de lecture-modification-écriture. Une autre technique repose sur un protocole de cohérence de cache selon lequel la ligne de cache contenant la variable cible de l'instruction atomique est acquise en mode « exclusif» par le coeur exécutant l'instruction. Cette acquisition entraîne l'invalidation de la ligne dans les autres mémoires cache, en interdisant en outre aux autres coeurs d'y accéder, et ainsi d'accéder à la zone associée de la mémoire système, jusqu'à ce que le mode exclusif soit levé par le coeur l'ayant acquis. Cette technique limite l'interdiction d'accès à seulement la zone mémoire correspondant 10 à la ligne de cache, mais elle est complexe à réaliser, et présente des restrictions sur l'alignement des données. Les deux techniques ont pour résultat de temporairement interdire l'accès à la variable partagée en mémoire, l'une utilisant un mécanisme mis en oeuvre au niveau de la mémoire système, l'autre un mécanisme mis en oeuvre au niveau des mémoires cache. 15 Résumé On prévoit de façon générale un processeur multi-coeurs comprenant une mémoire cache partagée par un groupe de plusieurs coeurs configurés pour déléguer les instructions atomiques à la mémoire cache ; un gestionnaire de mémoire cache configuré pour recevoir et traiter chaque instruction atomique exécutée par un coeur du 20 groupe ; et, dans son jeu d'instructions, une instruction atomique de lecturemodification-écriture en-cache prenant comme paramètre une adresse d'une variable stockée dans une mémoire système. Le gestionnaire de mémoire cache est configuré pour recevoir chaque instruction atomique en-cache et la traiter par la réalisation des opérations de lecture et écriture de l'instruction atomique dans un mode en-cache, 25 provoquant un accès à une ligne de la mémoire cache attribuée à l'adresse de la variable ; et le verrouillage de la ligne de cache sans interdire l'accès à la variable dans la mémoire système, jusqu'à la mise à jour de la variable dans la ligne de cache. Le gestionnaire de mémoire cache peut être configuré pour verrouiller la ligne de cache sans invalider la ligne de cache dans d'autres mémoires cache de même niveau. 30 L'instruction atomique en-cache peut être une instruction de lecture-et-addition, ayant en outre comme paramètre une valeur d'incrément, le gestionnaire de mémoire cache étant configuré pour ajouter l'incrément à la variable. 3048526 3 Le processeur peut comprendre, dans son jeu d'instructions, une instruction atomique de lecture-modification écriture hors-cache prenant comme paramètre une adresse d'une variable stockée dans la mémoire système. Le gestionnaire de mémoire cache est alors configuré en outre pour recevoir chaque instruction atomique hors-cache exécutée par 5 un coeur et la traiter par la réalisation des opérations de lecture et écriture de l'instruction atomique dans un mode hors-cache, provoquant un accès à la variable dans la mémoire système, et l'interdiction d'accès à la variable dans la mémoire système jusqu'à la mise à jour de la variable dans la mémoire système. On prévoit en outre un procédé de mise à jour d'une variable partagée entre plusieurs coeurs de processeur, comprenant les étapes suivantes mises en oeuvre à l'exécution dans un des coeurs d'une instruction atomique de lecture-modification-écriture en-cache avec comme paramètre l'adresse mémoire de la variable partagée : réaliser une opération de lecture dans un mode en-cache à l'adresse mémoire de la variable partagée, d'où il résulte la vérification de validité d'une ligne de cache attribuée à l'adresse mémoire, et que la ligne de cache est mise à jour à partir de la mémoire en cas d'invalidité ; modifier la variable ; réaliser une opération d'écriture de la variable modifiée dans le mode en-cache, d'où il résulte que la variable est écrite dans la ligne de cache et que la ligne de cache est vidée en mémoire ; et verrouiller la ligne de cache jusqu'à sa mise à jour par l'opération d'écriture. Le procédé peut comprendre l'étape consistant à verrouiller la ligne de cache sans invalider la ligne de cache dans d'autres mémoires cache de même niveau. Description sommaire des dessins Des modes de réalisation seront exposés dans la description suivante, faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : - la figure 1, précédemment décrite, est un schéma simplifié d'un processeur quadri-coeur comprenant deux niveaux de mémoires cache ; - la figure 2 est un chronogramme illustrant une mise en oeuvre d'une instruction atomique classique de lecture-et-addition ; et - la figure 3 est un chronogramme illustrant une mise en oeuvre d'une instruction atomique « en-cache » de lecture-et-addition. 3048526 4 Description de modes de réalisation La figure 2 illustre par un chronogramme une mise en oeuvre d'une instruction atomique classique de lecture-et-addition, à titre d'exemple, dans un système du type de la figure 1 et utilisant la méthode classique de verrouillage de la mémoire système évoquée ci- 5 dessus. L'instruction est notée AFAU, pour Atomic Fetch-and-Add, le suffixe « U » signifiant hors-cache (« Uncached »), c'est-à-dire effective au niveau de la mémoire MEM. Une telle instruction prend comme paramètres l'adresse de la variable partagée et l'incrément à lui ajouter. L'instruction place le coeur en attente du retour de la valeur de la variable partagée avant sa modification. 10 Toutes les adresses mentionnées ci-après se réfèrent à des adresses dans la mémoire système MEM. A un instant tO, un coeur CPUa exécute une instruction AFAU a 1, i, où le paramètre al est l'adresse de la variable partagée et le paramètre i est l'incrément à lui ajouter. Les opérations atomiques peuvent être déléguées à l'une des mémoires cache, par exemple 15 celle la plus proche de la mémoire système, L2, dont le circuit de gestion peut être pourvu d'une unité de traitement PU conçue pour mettre en oeuvre les opérations. Ainsi, à l'instant tO, l'instruction atomique est transmise à la mémoire cache L1, qui la transmet à sont tour, à l'instant tl, à la mémoire cache L2. A un instant t2, en réponse à l'instruction atomique, la mémoire cache L2 exécute une 20 commande LDU de lecture hors-cache (« LoaD Uncached ») à l'adresse al, laquelle commande est associée à une commande de verrouillage LCK de la zone mémoire contenant l'adresse al. La mémoire MEM réagit en verrouillant la zone, signifiant qu'à partir de l'instant t2 l'accès à la zone mémoire est réservé exclusivement au coeur CPUa ayant exécuté l'instruction atomique. L'intervalle de verrouillage est indiqué par un trait 25 gras. En outre, l'exécution d'une telle commande hors-cache active la gestion de cohérence des mémoires cache, par exemple en provoquant l'invalidation (INVAL al) de la ligne de cache attribuée à l'adresse al dans toutes les mémoires cache. Ainsi, un autre coeur qui accède en lecture à la variable provoque un rafraîchissement de sa mémoire cache 30 avec la variable à jour dans la mémoire système. Si un tel accès a lieu pendant que la zone mémoire est verrouillée, il est mis en attente du déverrouillage de la zone mémoire. 3048526 5 A un instant t3, en réponse à la commande de lecture LDU, la mémoire renvoie la valeur val de la variable stockée à l'adresse al. Il peut s'écouler un nombre relativement important de cycles d'horloge entre l'exécution de la commande LDU et le renvoi de la valeur val. 5 A un instant t4, la mémoire cache L2 renvoie la valeur lue val à la mémoire cache L1 et ajoute localement l'incrément i à la valeur val. A un instant t5, la mémoire cache L1 renvoie la valeur lue val au coeur CPUa tandis que la mémoire cache L2 exécute une commande STU d'écriture hors-cache (« STore Uncached ») de la variable modifiée à l'adresse al, laquelle commande est associée à 10 une commande de déverrouillage ULCK de la zone mémoire contenant l'adresse al. A un instant t6, en réponse à la commande STU, la mémoire système renvoie à la mémoire cache L2 un signal d'acquittement ACK indiquant la fin du verrouillage. Il peut s'écouler un nombre relativement important de cycles d'horloge entre l'exécution de la commande STU et le renvoi du signal d'acquittement. La mémoire système 15 déverrouille alors la zone mémoire contenant l'adresse al. A partir de l'instant t6, les autres coeurs ont accès à la variable partagée à jour dans la mémoire système. Si un autre coeur a demandé la lecture de la variable partagée entre les instants t2 et t6, la variable ne lui est renvoyée qu'à partir de l'instant t6. Les commandes LDU et STU exécutées dans la mémoire cache L2, plus précisément 20 par le gestionnaire de la mémoire cache, peuvent être similaires aux réponses de la mémoire cache à des instructions de même nom exécutées par le coeur. Cela signifie que la ligne de cache attribuée à l'adresse al est mise à jour par ces instructions. Ainsi, après l'exécution de la commande d'écriture STU, la ligne de cache est à jour avec la valeur courante en mémoire de la variable. 25 L'intervalle de verrouillage de la mémoire système, indiqué en trait gras, peut être relativement important, du fait que la latence de la mémoire système peut être comptée en centaines de cycles de l'horloge des coeurs. Cette latence intervient deux fois pour chaque instruction atomique, une fois pour la commande de lecture LDU et une autre fois pour la commande d'écriture STU. Pendant que la mémoire système est verrouillée, 30 aucun autre processus n'y a accès et est mis en attente, même si le processus n'accède pas à la variable partagée. On peut verrouiller des zones partielles de la mémoire, correspondant par exemple à des bancs mémoire, mais ces zones restent relativement grandes de sorte que leur verrouillage est pénalisant pour les performances du système. 3048526 6 Dans des processeurs du type de la figure 1, on peut trouver des mémoires cache qui sont partagées par plusieurs coeurs, par exemple deux ou quatre pour une mémoire cache de niveau 2. Certains processeurs peuvent avoir une mémoire cache de niveau 3 qui est partagée par encore plus de processeurs. Par ailleurs, dans de nombreuses 5 situations, on peut intervenir sur la répartition des fils de programme sur les coeurs de manière que des fils interdépendants soient affectés à des coeurs partageant une même mémoire cache. Par exemple, dans la figure 1, on affectera deux fils interdépendants respectivement aux coeurs CPUa et CPUb, ou CPUc et CPUd. En outre, une variable partagée par un groupe de fils de programme interdépendants n'a 10 généralement aucune utilité pour d'autres processus, notamment des processus qui pourraient être exécutés sur des coeurs qui ne partagent pas la mémoire cache. En d'autres termes, les autres processus n'ont pas besoin d'accéder à une valeur à jour de la variable partagée. Sur ce constat, on propose d'introduire dans le jeu d'instructions du processeur des 15 instructions atomiques que l'on qualifiera de « en-cache ». Plus spécifiquement, une telle instruction n'est atomique que jusqu'à un niveau de mémoire cache intermédiaire. Dans un processeur comprenant plusieurs niveaux de mémoires cache partagées, on préfèrera attribuer l'instruction atomique en-cache à la mémoire cache partagée la plus proche des coeurs. 20 Le jeu d'instructions du processeur pourra comporter, en plus d'une famille d'instructions atomiques classiques (que l'on qualifiera de « hors-cache »), une famille d'instructions atomiques en-cache homologues. Ainsi, par exemple, si le processeur comporte une instruction atomique lecture-et-addition classique AFAU (Add-and-Fetch Uncached), on introduit son instruction homologue en-cache AFA. 25 Alors, les instructions atomiques hors-cache classiques pourront être utilisées dans des fils interdépendants exécutés sur des coeurs quelconques qui ne partagent pas forcément la même mémoire cache, tandis que les nouvelles instructions atomiques en-cache seront utilisées dans des fils interdépendants exécutés sur des coeurs qui partagent une mémoire cache. 30 La figure 3 est un chronogramme illustrant un exemple de mise en oeuvre d'une instruction atomique de lecture-et-addition en-cache dans le cadre de l'exemple de processeur de la figure 1. Dans le processeur de la figure 1, la mémoire cache partagée la plus proche des coeurs est celle de niveau 2 (L2). Les instructions atomiques en-cache 3048526 7 sont alors attribuées aux mémoires cache L2 dont le circuit de gestion sera configuré pour les traiter. A un instant tO, le coeur CPUa exécute une instruction AFA a 1, i, où le paramètre al est l'adresse de la variable partagée et le paramètre i est l'incrément à lui ajouter. 5 L'instruction est attribuée à la mémoire cache partagée la plus proche des coeurs, L2. Ainsi, à l'instant tO, l'instruction atomique est transmise à la mémoire cache L1, qui la transmet à sont tour, à l'instant tl, à la mémoire cache L2. A un instant t2, en réponse à l'instruction atomique, la mémoire cache L2 exécute une commande LD de lecture en-cache à l'adresse al, laquelle commande est associée à une 10 commande de verrouillage LCK, non pas d'une zone mémoire, mais de la ligne de cache locale L(al) attribuée à l'adresse al. Les lignes de cache sont soumises à des accès concurrents par les coeurs qui partagent cette mémoire cache. En pratique, comme cela est représenté dans la figure 1 pour les mémoires cache L2, le gestionnaire de la mémoire cache comprend une unité de 15 traitement indépendante PU associée à chaque coeur, et ce sont ces unités de traitement qui sont en concurrence pour initier des accès aux lignes de cache. A partir de l'instant t2 l'accès à la ligne de cache est réservé exclusivement au coeur CPUa ayant exécuté l'instruction atomique. L'intervalle de verrouillage est indiqué par un trait gras. La commande de lecture LD (« LoaD ») peut être similaire à la réponse de la mémoire 20 cache à une instruction de lecture de même nom exécutée par le coeur. Cette commande provoque alors, selon les mécanismes de gestion de cache habituels, la vérification de la validité de la ligne de cache attribuée à l'adresse al, en d'autres termes si cette ligne est présente et n'a pas été invalidée par le mécanisme de gestion de cohérence. Si la ligne de cache est invalide ou absente (« cache-miss »), le gestionnaire de cache requiert sa 25 mise à jour (REQ REFILL) à la mémoire aval, la mémoire aval pouvant être la mémoire système MEM, ou une mémoire cache de niveau supérieur (L3), si le processeur en comporte une. A un instant t3, si une mise à jour a été requise, le nouveau contenu de la ligne de cache est reçu de la mémoire aval, incluant la valeur val à jour de la variable partagée à 30 l'adresse al. Lors d'une mise à jour de ligne de cache, l'intervalle t2 à t3 correspond à la latence de la mémoire aval. Cependant, la ligne de cache a une probabilité non négligeable d'être 3048526 8 valide, auquel cas la mise à jour de la ligne de cache est omise et l'intervalle t2 à t3 est nul, puisque le gestionnaire de mémoire cache peut enchaîner immédiatement les opérations suivantes. A un instant t4, la mémoire cache L2 renvoie la valeur lue val à la mémoire cache Ll et 5 ajoute localement l'incrément i à la valeur val. A un instant t5, la mémoire cache Ll renvoie la valeur lue val au coeur CPUa et la mémoire cache L2 exécute une commande ST d'écriture (« STore ») de la variable modifiée à l'adresse al. La commande ST (« STore ») peut être similaire à la réponse de la mémoire cache à une instruction d'écriture de même nom exécutée par le coeur. 10 Cette commande peut alors provoquer, selon les mécanismes de gestion de cache habituels, la mise à jour de la ligne de cache attribuée à l'adresse al, et le marquage de la ligne comme « sale » (« dirty »). Alors, la ligne est par exemple mise dans un tampon d'écriture vers la mémoire système, et elle est invalidée dans les autres mémoires cache L2 selon le mécanisme de gestion de cohérence. 15 Selon une variante, on peut omettre d'invalider la ligne dans les autres mémoires cache de même niveau, puisque la variable modifiée est partagée seulement entre les coeurs connectés à la même mémoire cache. En d'autres termes, les autres coeurs pourront continuer à accéder sans latence aux données dans la ligne de leur mémoire cache et n'accèderont en principe pas à la variable partagée obsolète dans cette ligne. 20 A un instant t7, dès que la variable partagée est à jour dans la ligne de cache, la ligne de cache peut être déverrouillée (ULCK) et un acquittement peut être envoyé vers la mémoire cache L 1. A partir de cet instant, la mémoire cache L2 peut vider son tampon d'écriture (FLUSH) vers la mémoire système MEM, ou vers une mémoire cache de niveau supérieur L3 qui répercute le vidage vers la mémoire système. 25 On s'aperçoit que l'intervalle de verrouillage de la ligne de cache est plus court que l'intervalle de verrouillage de la mémoire système dans le cas de la figure 2, notamment lorsque la variable partagée est à jour dans la ligne de cache, évitant la lecture de la mémoire aval entre les instants t2 et t3. Un gain remarquable provient du fait que ce n'est pas la mémoire système qui est 30 verrouillée, mais seulement une ligne de cache attribuée à l'adresse de la variable partagée. Les accès à d'autres lignes de cache et à l'ensemble de la mémoire système restent autorisés aux coeurs concurrents pendant les opérations atomiques en-cache. 3048526 9 Comme on l'a précédemment évoqué, dans certaines architectures de processeur, les instructions atomiques classiques peuvent être mises en oeuvre par une deuxième technique, reposant sur un protocole de cohérence de cache selon lequel la ligne de cache contenant la variable cible de l'instruction atomique est acquise en mode 5 « exclusif» par le coeur exécutant l'instruction atomique. Dans une telle architecture, une instruction atomique de portée limitée à un niveau de cache (par exemple L2) améliore la réactivité par l'élimination du mode de verrouillage exclusif, nécessitant l'échange de messages entre les gestionnaires de cache de même niveau. En outre, comme la ligne de cache n'est pas verrouillée en mode exclusif, les coeurs reliés à une 10 autre mémoire cache de même niveau continuent à avoir accès à leur ligne de cache de façon habituelle. REVENDICATIONS1. Processeur multi-coeurs comprenant : - une mémoire cache (L2 CACHE) partagée par un groupe de plusieurs coeurs (CPUa, CPUb) configurés pour déléguer les instructions atomiques à la mémoire cache ; - un gestionnaire de mémoire cache (CTRL) configuré pour recevoir et traiter chaque instruction atomique exécutée par un coeur du groupe ; caractérisé en ce qu'il comprend dans son jeu d'instructions une instruction atomique de lecture-modification-écriture en-cache (AFA) prenant comme paramètre une adresse d'une variable stockée dans une mémoire système (MEM), le gestionnaire de mémoire cache étant configuré pour recevoir chaque instruction atomique en-cache et la traiter par : - la réalisation des opérations de lecture (LD) et écriture (ST) de l'instruction atomique dans un mode en-cache, provoquant un accès à une ligne de la mémoire cache attribuée à l'adresse (al) de la variable ; et - le verrouillage de la ligne de cache sans interdire l'accès à la variable dans la mémoire système, jusqu'à la mise à jour de la variable dans la ligne de cache. 2. Processeur selon la revendication 1, dans lequel le gestionnaire de mémoire cache est configuré pour verrouiller la ligne de cache sans invalider la ligne de cache dans d'autres mémoires cache de même niveau. 3. Processeur selon la revendication 1, dans lequel l'instruction atomique en-cache est une instruction de lecture-et-addition, ayant en outre comme paramètre une valeur d'incrément (i), le gestionnaire de mémoire cache étant configuré pour ajouter l'incrément à la variable. 4. Processeur selon la revendication 1, comprenant : - dans son jeu d'instructions, une instruction atomique de lecture-modification écriture hors-cache (AFAU) prenant comme paramètre une adresse (al) d'une variable stockée dans la mémoire système (MEM) ; 3048526 11 - le gestionnaire de mémoire cache (CTRL) étant configuré en outre pour recevoir chaque instruction atomique hors-cache exécutée par un coeur et la traiter par - la réalisation des opérations de lecture (LDU) et écriture (STU) de 5 l'instruction atomique dans un mode hors-cache, provoquant un accès à la variable dans la mémoire système, et - l'interdiction d'accès à la variable dans la mémoire système jusqu'à la mise à jour de la variable dans la mémoire système. 5. Procédé de mise à jour d'une variable partagée entre plusieurs coeurs de processeur, 10 comprenant les étapes suivantes mises en oeuvre à l'exécution dans un des coeurs d'une instruction atomique de lecture-modification-écriture en-cache (AFA) avec comme paramètre l'adresse mémoire (al) de la variable partagée : - réaliser une opération de lecture dans un mode en-cache (LD) à l'adresse mémoire de la variable partagée, d'où il résulte la vérification de validité 15 d'une ligne de cache attribuée à l'adresse mémoire, et que la ligne de cache est mise à jour à partir de la mémoire en cas d'invalidité ; - modifier la variable ; - réaliser une opération d'écriture (ST) de la variable modifiée dans le mode en-cache, d'où il résulte que la variable est écrite dans la ligne de cache et que la 20 ligne de cache est vidée en mémoire ; et - verrouiller la ligne de cache jusqu'à sa mise à jour par l'opération d'écriture. 6. Procédé selon la revendication 5, comprenant l'étape suivante : - verrouiller la ligne de cache sans invalider la ligne de cache dans d'autres mémoires cache de même niveau.