Brevet FR3042051A1 — publié le 20170407

MISE EN OEUVRE D'UNE OPERATION ATOMIQUE SUR UN PROCESSEUR MONO-COEUR MULTI-FILS Domaine technique L'invention est relative à des processeurs multi-fils d'exécution (« multithread » en 5 anglais), et plus spécifiquement à l'exécution d'opérations atomiques sur de tels processeurs. Arrière-plan Dans un système multitâche, un fil d'exécution comprend une succession d'instructions qui peuvent être exécutées en parallèle avec les instructions de fils concurrents sur le 10 système. Sur un processeur multi-coeurs, les fils d'exécution sont typiquement distribués sur des coeurs respectifs pour être exécutés simultanément. Un processeur mono-coeur peut être multitâche en ce qu'il exécute en temps partagé plusieurs fils d'exécution. Dans un système multi-fils, on a souvent besoin d'exécuter des opérations atomiques, comme une opération de lecture-modification-écriture pour échanger des données entre 15 des fils ou synchroniser des fils. De telles opérations nécessitent la plupart du temps l'exécution d'une séquence de plusieurs instructions successives. Une opération atomique dans ce contexte est l'exécution ce cette séquence d'instructions sans interférence avec des instructions de fils concurrents, comme si la séquence était la seule à s'exécuter sur le système. 20 Certains processeurs mono-coeur multi-fils possèdent des couples d'instructions servant à organiser une séquence d'instructions en une opération atomique. Généralement, l'instruction initiale du couple lit une variable partagée et l'instruction terminale ne met à jour la variable partagée que si elle n'a pas été modifiée depuis sa lecture. Des exemples connus de tels couples d'instructions sont « Load-Link/Store-Conditional » 25 (LL/SC), et « Read/Compare-And-Swap » (R/CAS). Si la mise à jour de la variable partagée par l'instruction terminale échoue, parce qu'elle a été modifiée par un autre fil d'exécution, l'échec est traité par le système d'exploitation ou au niveau applicatif pour réitérer l'opération atomique qui a échoué. Résumé 30 On prévoit de façon générale un coeur de processeur comprenant dans son jeu d'instructions un couple d'instructions prévues pour définir une opération atomique. La première instruction du couple est conçue pour lire une variable partagée, activer un 3042051 2 point de mémorisation associé à la variable partagée, lire l'état initial du point de mémorisation, et annuler l'exécution de l'opération atomique si l'état initial du point de mémorisation est actif. La deuxième instruction du couple peut être conçue pour mettre à jour la variable partagée et désactiver le point de mémorisation. La première instruction du couple peut avoir comme paramètre l'adresse mémoire de la variable partagée, le coeur comprenant en outre un groupe de points de mémorisation à double accès attribué à une plage d'adresses mémoire allouée à des variables partagées ; un circuit de génération d'index recevant l'adresse mémoire, configuré pour mapper la plage d'adresses sur le nombre de points de mémorisation, et câblé pour sélectionner le point de mémorisation à utiliser par la première instruction ; et une unité de traitement configurée pour lire l'état initial et simultanément écrire un état actif dans le point de mémorisation sélectionné. On prévoit également un procédé d'exécution d'une opération atomique dans un coeur de processeur, comprenant les étapes consistant à attribuer un groupe de points de mémorisation à double accès à un groupe d'emplacements dans une mémoire destinés à stocker des variables partagées ; répartir des instructions de programme dans plusieurs fils d'exécution indépendants ; initier l'opération atomique dans un fil courant par l'exécution d'une instruction de chargement-acquisition ayant comme paramètre une adresse mémoire d'une variable partagée. L'exécution de cette instruction provoque le chargement de la variable partagée contenue à l'adresse mémoire dans un registre du coeur de processeur ; la sélection d'un point de mémorisation correspondant à l'adresse mémoire ; la mise à un état actif du point de mémorisation sélectionné et l'observation simultanée de l'état précédent du point de mémorisation sélectionné ; et l'annulation de l'opération atomique si l'état précédent du point de mémorisation sélectionné est actif Le procédé peut comprendre en outre, à la fin de l'opération atomique, les étapes consistant à exécuter dans le fil courant une instruction de stockage-libération avec comme paramètre la même adresse mémoire que l'instruction de chargement-acquisition, laquelle exécution provoque l'écriture du contenu d'un registre du coeur de processeur à l'adresse mémoire ; la sélection du point de mémorisation correspondant ; et la mise à un état inactif du point de mémorisation sélectionné. L'opération atomique annulée peut être réitérée ultérieurement. Le coeur de processeur peut comprendre une unité de traitement d'instructions de type pipeline à plusieurs étages, le procédé comprenant alors les étapes consistant à fournir 3042051 3 au pipeline des instructions consécutives de manière que, à tout instant, les instructions contenues dans les étages du pipeline appartiennent à de fils d'exécution différents ; identifier les instructions à fournir au pipeline par des compteurs de programme respectivement associés aux fils d'exécution ; et, lors de l'annulation d'une opération 5 atomique dans un fil d'exécution courant, omettre la mise à jour du compteur de programme du fil d'exécution courant, d'où il résulte que l'opération atomique est réitérée au cycle d'exécution suivant du fil d'exécution courant. Le procédé peut comprendre en outre les étapes consistant à générer une valeur d'index à partir de l'adresse mémoire de la variable partagée ; et utiliser la valeur d'index pour 10 sélectionner le point de mémorisation. 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 est un schéma-bloc d'éléments d'un processeur mono-coeur multi-fils 15 incluant un mode de réalisation d'une unité de traitement conçue pour mettre en oeuvre un couple d'instructions de définition d'une opération atomique ; - la figure 2 est un graphe temporel illustrant un exemple d'utilisation du couple d'instructions de définition d'une opération atomique ; et - la figure 3 est un tableau représentant un exemple de pipeline et l'évolution du 20 contenu de ses étages dans le cadre de l'exemple de séquence d'instructions de la figure 2. Description de modes de réalisation Comme on l'a précédemment indiqué, pour définir des opérations atomiques dans certains processeurs d'architecture classique, on prévoit un couple d'instructions 25 dédiées. Un point commun des ces couples d'instructions est qu'ils établissent un point de synchronisation à la fin de l'opération atomique, au moment de mettre à jour la variable partagée. Le traitement d'un échec de la mise à jour de la variable partagée implique de nombreux cycles d'instructions, ajoutés aux cycles de l'opération atomique elle-même. 30 On propose ci-après une architecture de processeur offrant un couple d'instructions de définition d'opérations atomiques qui établit un point de synchronisation au début des 3042051 4 opérations atomiques. En d'autres termes, la première instruction du couple est conçue pour détecter que l'opération atomique est vouée à l'échec et provoquer la réitération de l'opération atomique. Avec cette configuration, l'opération atomique n'est pas démarrée et peut-être réitérée automatiquement au cycle suivant sans introduire de cycles 5 supplémentaires pour traiter l'échec. Plus spécifiquement on prévoit une instruction dite de chargement-acquisition (« acquire-load ») ou AQLD, et une instruction dite de stockage-libération (« store-release » ou STRL. L'instruction de chargement-acquisition AQLD est conçue pour simultanément charger 10 une variable partagée à partir de la mémoire, l'acquérir en activant inconditionnellement un drapeau correspondant, et vérifier l'état initial du drapeau. (Des événements sont considérés comme « simultanés » à l'échelle des cycles d'instruction, c'est-à-dire que les événements simultanés peuvent avoir lieu à des instants différents, mais à l'intérieur d'un même cycle d'instruction.) 15 Si le drapeau était déjà activé, l'instruction se termine en retournant un état d'échec. Cela signifie que la variable était déjà acquise par une instruction AQLD précédemment exécutée, probablement par un fil d'exécution concurrent. L'état d'échec peut, soit provoquer une interruption, soit être signalé via le résultat retourné par l'instruction, pour que le système d'exploitation ou l'application gère 20 l'échec. Un tel échec peut être géré en réitérant l'opération ultérieurement. Cependant, grâce au fait que l'instruction AQLD est la première instruction de l'opération atomique, et que l'état d'échec est déterminé dès l'exécution de cette instruction, les instructions restantes de l'opération atomique ne sont pas exécutées. De plus, l'instruction AQLD étant une instruction de lecture, elle ne modifie pas l'état du 25 système. La seule modification qu'elle provoque est l'activation du drapeau associé à la variable partagée. Toutefois, en cas d'échec, ce drapeau était déjà activé, de sorte que l'instruction AQLD n'a alors aucun effet sur le système. Il suffit alors de réitérer l'opération atomique au cycle suivant, ce qui peut être obtenu tout simplement en annulant l'instruction AQLD, c'est-à-dire en ne mettant pas à jour 30 l'adresse de la prochaine instruction à exécuter. En absence d'échec, la fin de l'opération atomique est déterminée par l'instruction de stockage-libération STRL. Cette instruction STRL écrit une valeur dans la variable partagée, valeur calculée par des instructions quelconques insérées entre les instructions 3042051 5 AQLD et STRL, et désactive simultanément le drapeau associé à la variable partagée, la libérant pour une autre opération atomique. La figure 1 est un schéma-bloc d'éléments d'un processeur mono-coeur multi-fils incluant un mode de réalisation d'une unité de traitement conçue pour mettre en oeuvre 5 un tel couple d'instructions. L'unité de traitement peut comprendre plusieurs étages fonctionnant en mode pipeline, c'est-à-dire que chaque instruction transite successivement par chaque étage au rythme des cycles d'une horloge système. Une instruction met ainsi plusieurs cycles à compléter, mais les étages opèrent généralement simultanément sur plusieurs instructions, de sorte que le pipeline peut recevoir une 10 instruction par cycle d'horloge. A titre d'exemple, un pipeline générique comprend quatre étages dits « Fetch » 10, « Decode » 12, « Execute » 14, et « Write-Back » 16. Le premier étage 10 détermine l'adresse de l'instruction à exécuter à chaque cycle et lit cette instruction dans une mémoire de travail 18 par un bus d'instructions (A, INST). L'adresse de l'instruction 15 est généralement contenue dans un registre dit « compteur de programme » ou PC. Le deuxième étage 12 lit, le cas échéant, les opérandes de l'instruction dans des registres de travail 20 du processeur. Le troisième étage 14 exécute une opération sur les opérandes et/ou des valeurs immédiates véhiculées par l'instruction elle-même. L'opération peut également être une opération mémoire impliquant une lecture ou une écriture dans la 20 mémoire 18 par un bus de données (A, D). Les bus de données et d'instructions sont souvent confondus. L'opération en 14 peut également produire un résultat à récrire dans les registres 20. Le quatrième étage 16 se charge de mettre à jour les registres et éventuellement le compteur de programme PC. Une unité de traitement de type pipeline se prête bien au traitement en parallèle en 25 temps partagé de plusieurs fils d'exécution indépendants. S'il y a au moins autant de fils qu'il y a d'étages dans le pipeline, l'occupation du processeur peut être optimale, en assurant que tous les étages contiennent, à chaque cycle, des instructions de fils différents. Cela évite notamment des difficultés liées aux dépendances des instructions au sein d'un même fil. Dans ce cas, l'ordonnancement des instructions peut être 30 organisé en « revolver », c'est-à-dire en sélectionnant les instructions de manière circulaire parmi les fils actifs. Ce type d'ordonnancement n'est pas souhaité dans des processeurs récents comprenant une mémoire cache. En effet, les données traitées par les différents fils peuvent avoir des localités spatiales et temporelles très disparates qui rendraient la mémoire cache peu 3042051 6 efficace. Mais ce type d'ordonnancement est particulièrement efficace dans les situations où le processeur serait dépourvu de mémoire cache. La commutation d'un fil à un autre est effectuée par un « changement de contexte », le contexte d'un fil comprenant une valeur de compteur de programme PC. L'étage 10 peut 5 comprendre plusieurs compteurs de programme PC, ici autant que d'étages de pipeline (PCa, PCb, PCc, et PCd). Chaque compteur de programme peut être alloué à un fil d'exécution différent et être utilisé à tour de rôle de manière circulaire. Pour mettre en oeuvre les instructions AQLD et STRL, on prévoit une mémoire atomique AMEM à double accès par ces instructions. La mémoire est à « double 10 accès » en ce que son contenu peut être lu et mis à jour en un seul cycle. Lors d'un tel accès simultané, la valeur initiale est lue tandis que la valeur écrite devient accessible en lecture au cycle suivant. L'accès à la mémoire AMEM peut être effectué au niveau de l'étage d'exécution 14 du pipeline. La mémoire AMEM comprend une série de points de mémorisation ou drapeaux FL à 15 double accès, par exemple des bascules de type D. Chaque drapeau est associé à une variable partagée dans la mémoire 18. En pratique, le nombre de drapeaux sera plus petit que l'espace adressable par le bus d'adresses A. On peut dans ce cas prévoir un circuit de génération d'index 22, par exemple de type Hash, qui mappe la plage d'adresses allouée aux variables partagées vers un index IDX dont la plage de variation 20 correspond au nombre de drapeaux. Lorsqu'une instruction AQLD arrive dans l'étage 14 du pipeline, l'étage 14 interprète l'instruction en présentant sur le bus mémoire l'adresse A de la variable partagée. L'adresse est aussitôt convertie par le circuit 22 en un index IDX qui sélectionne le drapeau correspondant dans la mémoire atomique AMEM. L'étage 14 reçoit l'état du 25 drapeau sélectionné FL et active simultanément le drapeau par un signal SET. Si le drapeau était inactif, l'exécution du fil continue normalement. Le drapeau est désormais actif et la variable partagée est réservée exclusivement à l'opération atomique qui démarre ainsi. Si le drapeau était actif, c'est que la variable partagée est déjà réservée à une autre 30 opération atomique. L'exécution de l'instruction se termine en renvoyant un état d'échec. Cet état d'échec peut être écrit dans une variable d'état par l'étage final 16, ou bien l'étage 16 peut annuler l'instruction en suspendant la mise à jour du compteur de programme PC associé au fil courant. Il en résulte que la prochaine instruction exécutée 3042051 7 dans le fil sera de nouveau l'instruction AQLD. L'instruction AQLD sera réitérée à chaque cycle du fil tant que le drapeau est trouvé actif. Dans certains cas, la fonction Hash peut produire une collision, c'est-à-dire générer une même valeur d'index pour deux variables partagées différentes. Dans un cas de 5 collision, la variable partagée courante peut être libre mais son drapeau avoir été activé par la réservation d'une autre variable partagée. Le processeur ne pouvant pas discerner entre ces deux cas, l'instruction AQLD échoue. De tels cas de collision sont statistiquement peu probables et ont un effet négligeable sur les performances du système. 10 A la fin de l'opération atomique, l'instruction STRL arrive dans l'étage d'exécution 14. Elle provoque la mise à jour de la variable partagée par le bus mémoire. L'adresse est convertie en un index IDX qui sélectionne le drapeau correspondant. L'adresse étant la même que celle de l'instruction AQLD, c'est le même drapeau qui est sélectionné. Ce drapeau est simultanément désactivé par un signal CLR, rendant la variable partagée 15 disponible à une autre opération atomique. La figure 2 est un graphe temporel illustrant un exemple d'utilisation du couple d'instructions AQLD et STRL. On, considère trois fils d'exécution THa, THb, THc, et les accès à la mémoire atomique AMEM par des axes temporels verticaux. Les effets des instructions sont illustrés par des flèches horizontales. La main sur le processeur est 20 cédée de façon circulaire aux fils, de sorte que les instructions du fil THa sont exécutées à des cycles tO + 4k, les instructions du fil THb à des cycles tl + 4k, et les instructions du fil THc à des cycles t2 + 4k, où k = 0, 1, 2... Un quatrième fil, non explicité ci-après, peut être exécuté à des cycles t3 + 4k. A un instant tO, le fil THa démarre une opération atomique en exécutant une instruction 25 AQLD à l'adresse An. Le drapeau FL sélectionné par l'index IDX correspondant était inactif (0) - il est aussitôt activé (1). Le fil THa peut continuer par les instructions de l'opération atomique, par exemple une instruction notée OP(Vn). Au cycle suivant tl, la main est cédée au fil THb. Le fil THb démarre également une opération atomique sur la variable à l'adresse An par une instruction AQLD(An). Le 30 drapeau correspondant FL est à 1, provoquant l'échec de l'instruction. L'instruction est annulée est sera exécutée de nouveau au cycle suivant t5 du fil THb. Cette nouvelle exécution échouera également. 3042051 8 Au cycle suivant t2, la main est cédée au fil THc. Le fil THc démarre également une opération atomique sur la variable à l'adresse An par une instruction AQLD(An). Le drapeau correspondant FL est toujours à 1, provoquant l'échec de l'instruction. L'instruction est annulée est sera exécutée de nouveau au cycle suivant t6 du fil THc. 5 Cette nouvelle exécution échouera également. Des cycles t3 et t7 correspondent éventuellement à un quatrième fil d'exécution qui ne sera pas décrit. Au cycle t4, le fil THa a la main et exécute l'opération OP(Vn). Cette opération consiste, par exemple, à incrémenter la valeur Vn de la variable partagée. Cette valeur 10 Vn a été chargée dans un des registres 20 du processeur par l'instruction AQLD. L'instruction OP ajoute alors un incrément à cette valeur et écrit la valeur modifiée dans le même ou un autre registre. Au cycle t8, le fil THa a de nouveau la main et termine l'opération atomique par l'exécution d'une instruction STRL à l'adresse An. Cette instruction peut mettre à jour 15 la variable partagée à l'adresse An par la valeur Vn incrémentée par l'instruction OP, contenue dans un registre 20. En même temps, l'instruction STRL désactive le drapeau FL identifié par l'index correspondant à l'adresse An. Au cycle suivant t9, le fil THb a la main et réitère l'instruction AQLD(An) qui trouve enfin le drapeau FL inactif. La variable partagée à l'adresse An est maintenant réservée 20 à l'opération atomique du fil THb, opération atomique qui sera exécutée aux cycles suivants du fil THb. L'instruction AQLD(An) du fil THc échouera au cycle t10 et suivants, tant que le drapeau FL correspondant à l'adresse An n'a pas été désactivé par une instruction STRL(An). 25 La figure 3 est un tableau illustrant l'évolution du contenu des étages d'un pipeline du type de la figure 1 dans le cadre de l'exemple d'exécution de la figure 2. Les cycles d'instruction sont illustrés par des colonnes successives. La première rangée indique le cycle et le compteur de programme PC utilisé par le premier étage (FETCH) du pipeline. On suppose dans cet exemple qu'on utilise quatre 30 compteurs de programme indépendants PCa à PCd associés à quatre fils qui peuvent coexister simultanément dans le pipeline. 3042051 9 Les quatre rangées suivantes correspondent aux quatre étages du pipeline et leurs contenus. Chaque contenu est préfixé par son fil d'appartenance. Des instructions d'un quatrième fil THd ne sont pas explicitées et désignées par des numéros. Les cycles identifiés à la figure 2 et à la première rangée du tableau correspondent à l'arrivée des 5 instructions dans l'étage EXECUTE 14 du pipeline. Ainsi, à la première colonne correspondant au cycle tO, l'instruction AQLD du fil THa est dans l'étage EXECUTE, tandis que les deux instructions AQLD des fils THb et THc sont respectivement dans les étages DECODE et FETCH. La dernière rangée du tableau indique l'opération faite sur le compteur de programme 10 associé à l'instruction qui quitte le pipeline. La notation « ++ » indique que le compteur de programme est incrémenté, et la notation « = » indique que le compteur de programme n'est pas modifié, c'est-à-dire que l'instruction qui quitte le pipeline sera exécutée de nouveau au prochain cycle du fil. Au cycle tl, l'instruction AQLD du fil THb échoue, ce qui est représenté par une case 15 barrée du tableau. Au cycle t2, le dernier étage du pipeline, recevant normalement l'instruction AQLD de l'étage EXECUTE, peut rester vide, puisqu'il est inutile de finir l'exécution de cette instruction AQLD. Le compteur de programme PCb du fil THb n'est pas modifié. Il en résulte que, au cycle t3, l'instruction AQLD du fil THb est de nouveau chargée dans le pipeline par l'étage FETCH. Des événements similaires se 20 produisent pour l'instruction AQLD du fil THc, qui échoue au cycle t2. REVENDICATIONS1. Procédé d'exécution d'une opération atomique dans un coeur de processeur, comprenant les étapes suivantes : - attribuer un groupe de points de mémorisation à double accès (AMEM) à un groupe d'emplacements dans une mémoire (18) destinés à stocker des variables partagées ; - répartir des instructions de programme dans plusieurs fils d'exécution indépendants (TH) ; - initier l'opération atomique dans un fil courant par l'exécution d'une instruction de chargement-acquisition (AQLD) ayant comme paramètre une adresse mémoire (An) d'une variable partagée, laquelle exécution provoque : - le chargement de la variable partagée contenue à l'adresse mémoire dans un registre (20) du coeur de processeur ; - la sélection d'un point de mémorisation correspondant à l'adresse mémoire ; - la mise à un état actif du point de mémorisation sélectionné et l'observation simultanée de l'état précédent (FL) du point de mémorisation sélectionné ; et - l'annulation de l'opération atomique si l'état précédent du point de mémorisation sélectionné est actif 2. Procédé selon la revendication 1, comprenant en outre les étapes suivantes : - à la fin de l'opération atomique, exécuter dans le fil courant une instruction de stockage-libération (STRL) avec comme paramètre la même adresse mémoire (An) que l'instruction de chargement-acquisition, laquelle exécution provoque : - l'écriture du contenu d'un registre du coeur de processeur à l'adresse mémoire ; - la sélection du point de mémorisation correspondant ; et - la mise à un état inactif du point de mémorisation sélectionné. 3042051 11 3. Procédé selon la revendication 1, dans lequel l'opération atomique annulée est réitérée ultérieurement. 4. Procédé selon la revendication 3, dans lequel le coeur de processeur comprend une unité de traitement d'instructions de type pipeline à plusieurs étages, le procédé 5 comprenant les étapes suivantes : - fournir au pipeline des instructions consécutives de manière que, à tout instant, les instructions contenues dans les étages du pipeline appartiennent à de fils d'exécution différents ; - identifier les instructions à fournir au pipeline par des compteurs de 10 programme (PCa-PCd) respectivement associés aux fils d'exécution ; et - lors de l'annulation d'une opération atomique dans un fil d'exécution courant, omettre la mise à jour du compteur de programme du fil d'exécution courant, d'où il résulte que l'opération atomique est réitérée au cycle d'exécution suivant du fil d'exécution courant. 15 5. Procédé selon la revendication 3, comprenant en outre les étapes suivantes : - générer une valeur d'index (IDX) à partir de l'adresse mémoire (An) de la variable partagée ; et - utiliser la valeur d'index pour sélectionner le point de mémorisation. 6. Coeur de processeur comprenant dans son jeu d'instructions un couple 20 d'instructions prévues pour définir une opération atomique, la première instruction du couple étant conçue pour lire une variable partagée et activer un point de mémorisation associé à la variable partagée, caractérisé en ce que la première instruction (AQLD) est conçue en outre pour lire l'état initial (FL) du point de mémorisation et annuler l'exécution de l'opération atomique si l'état initial du point 25 de mémorisation est actif 7. Coeur de processeur selon la revendication 6, dans lequel la deuxième instruction du couple (STRL) est conçue pour mettre à jour la variable partagée et désactiver le point de mémorisation (FL). 3042051 12 8. Coeur de processeur selon la revendication 6, dans lequel la première instruction du couple a comme paramètre l'adresse mémoire (A) de la variable partagée, le coeur comprenant en outre : - un groupe de points de mémorisation à double accès (AMEM) attribué à une 5 plage d'adresses mémoire allouée à des variables partagées ; - un circuit de génération d'index (22) recevant l'adresse mémoire (A), configure pour mapper la plage d'adresses sur le nombre de points de mémorisation, et câblé pour sélectionner le point de mémorisation à utiliser par la première instruction ; et 10 - une unité de traitement (14) configurée pour lire l'état initial et simultanément écrire un état actif dans le point de mémorisation sélectionné.