Brevet FR3091363A1 — publié le 20200703

Description Titre de l'invention : Système de synchronisation inter-processeurs configurable Domaine technique [0001] L'invention est relative à la synchronisation de plusieurs processeurs exécutant en parallèle des fils d'un même programme partageant une même ressource, et plus spécifiquement à un système de communication point-à-point inter-processeurs permettant à des processeurs de communiquer directement avec d'autres processeurs par l'intermédiaire de registres de travail. Arrière-plan technique [0002] La figure 1 représente un exemple de matrice de 4x4 processeurs PE pouvant être intégrés sur une même puce. Les processeurs sont alors aussi appelés « coeurs » et forment un système mufti-coeurs. Les coeurs ou processeurs PE peuvent être reliés à un bus commun également relié à une mémoire partagée MEM. La mémoire MEM peut contenir le code des programmes exécutés par les processeurs et les données de travail des programmes. [0003] La demande de brevet US2015-0339256 décrit une technique de communication inter-processeurs point-à-point, où les processeurs peuvent être groupés par quatre processeurs voisins, comme cela est représenté. Chaque processeur d'un groupe est relié aux trois autres processeurs du groupe par des liens point-à-point câblés. Les liens point-à-point sont conçus pour permettre à chaque processeur d'écrire directement une notification dans un registre de travail désigné d'un autre processeur quelconque du groupe. [0004] Ainsi, les liens point-à-point auxquels on se réfère ici sont des liens physiques qui véhiculent des états de bits directement entre des registres des processeurs. Ces liens physiques ne sont pas à confondre avec des voies de communication génériques entre les processeurs, comme un bus ou un réseau sur puce, qui permettent aussi de transférer des données entre des registres, mais cela de manière logicielle, en exécutant des instructions génériques sur les processeurs qui font transiter les données par une mémoire partagée. [0005] Plus spécifiquement, les processeurs ont dans leur jeu d'instructions une instruction de synchronisation de groupe qui exécute simultanément une commande d'attente avec un premier paramètre et une commande de notification avec un deuxième paramètre. La commande d'attente provoque l'arrêt du processeur et l'attente de l'apparition dans un registre d'événements d'un motif de bits correspondant à celui véhiculé dans son paramètre. La commande de notification provoque l'écriture des bits actifs de son 2 paramètre directement dans les registres d'événements des autres processeurs du groupe. Cette écriture n'a effectivement lieu qu'au moment où le processeur sort de son état d'arrêt. Résumé de l'invention [0006] On prévoit de façon générale un système de synchronisation inter-processeurs, comprenant une pluralité de processeurs ; une pluralité de lignes de notification unidirectionnelles connectant les processeurs dans une chaîne ; dans chaque processeur : un registre de synchronisation ayant des bits respectivement associés aux lignes de notification, connectés pour enregistrer les états respectifs de lignes de notification amont, propagés par un processeur amont, et une porte commandée par un registre de configuration pour propager les états des lignes de notification amont sur des lignes de notification aval à un processeur aval. [0007] Chaque processeur peut être configure en outre pour activer sélectivement des lignes de notification aval en fonction d'un paramètre d'une instruction machine de notification exécutée par le processeur. [0008] Chaque processeur peut être configure en outre pour suspendre l'exécution d'un programme respectif en fonction d'un paramètre d'une instruction machine d'attente exécutée par le processeur, la suspension étant levée lorsque le registre de synchronisation contient un motif de bits actifs correspondant au paramètre de l'instruction d'attente. [0009] Chaque processeur peut être configure en outre pour, à la levée de la suspension ré- initialiser le registre de synchronisation. [0010] L'instruction d'attente et l'instruction de notification peuvent former partie d'une instruction machine unique exécutable par le processeur. [0011] Le registre de configuration peut comprendre des bits respectivement associés aux lignes de notification amont, la porte étant configurée pour propager sélectivement les états des lignes de notification amont en fonction des états respectifs des bits du registre de configuration. [0012] Un procédé de synchronisation inter-processeurs peut comprendre des étapes consistant à connecter une pluralité de processeurs dans une chaîne par l'intermédiaire de lignes configurées pour transmettre des bits de notification respectifs dans une même direction ; dans un premier processeur de la chaîne, envoyer un bit de notification vers un deuxième processeur, succédant au premier processeur dans la chaîne ; et dans le second processeur, en fonction de l'état d'un bit de configuration local, propager le bit de notification vers un troisième processeur, succédant au second processeur dans la chaîne. [0013] Le second processeur peut mettre en oeuvre des étapes consistant à enregistrer le bit 3 de notification clans un registre de synchronisation ; exécuter une instruction machine d'attente avec un paramètre, provoquant l'arrêt du processeur ; et sortir le processeur de l'état d'arrêt lorsque le registre de synchronisation contient un motif de bits correspondant au paramètre de l'instruction d'attente. [0014] Le second processeur peut en outre mettre en oeuvre des étapes consistant à exécuter une instruction machine de notification avec un paramètre ; et configurer des bits de notification à envoyer au troisième processeur en fonction du paramètre de l' instruction de notification. [0015] Le second processeur, à la sortie de l'état d'arrêt, peut réinitialiser le registre de syn- chronisation. Présentation des figures [0016] Des modes de réalisation seront exposés dans la description suivante, faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : [0017] [fig.1] la figure 1, précédemment décrite, est un schéma-bloc d'une matrice de processeurs divisée en plusieurs groupes dans lesquels des processeurs peuvent communiquer par des liaisons point à point ; [0018] [fig.21 la figure 2 est un schéma-bloc d'un mode de réalisation de matrice de processeurs où les processeurs sont tous connectés dans une chaîne de liaisons de notification ; [0019] [fig.31 la figure 3 est un schéma-bloc d'un mode de réalisation d'une unité de synchro- nisation avant d'un processeur ; [0020] [fig.4] la figure 4 est un schéma-bloc d'un mode de réalisation d'une unité de synchro- nisation arrière d'un processeur ; et [0021] [fig.51 la figure 5 illustre un exemple de configuration d'une chaîne de processeurs. Description détaillée de l'invention 100221 La structure connue de la figure 1 permet de mettre en oeuvre une synchronisation avec une latence quasi nulle entre les quatre processeurs de chaque groupe. Des processeurs externes à un groupe peuvent aussi participer à une synchronisation, mais la synchronisation entre les groupes a lieu alors de manière logicielle par l'intermédiaire d'une voie de communication partagée par tous les processeurs, qui augmente significativement la latence. 100231 La figure 2 est un schéma-bloc d'un mode de réalisation de matrice de processeurs organisés selon une structure de synchronisation qui permet à un nombre quelconque de processeurs de la matrice de participer à une synchronisation avec une faible latence. Plus spécifiquement, les processeurs sont organisés dans une chaîne configurablc de liens point-à-point de synchronisation. Par « chaîne », on entend que chaque processeur est relié physiquement à un seul autre processeur qui le précède, ou processeur amont, et à un seul autre processeur qui le succède, ou processeur aval. Comme cela est représenté par des flèches, chaque lien entre deux processeurs peut être bidirectionnel, et la chaîne peut être fermée. De préférence, la chaîne est configure° pour que chaque processeur soit relié à deux processeurs physiquement adjacents. Comme cela est représenté, la chaîne peut parcourir les processeurs par rangées, en inversant le sens d'une rangée à l'autre. [0024] Chaque processeur comprend une paire d'unités de synchronisation, la première unité FSYNC gérant les liens dans un sens dit « avant », et l'autre unité BSYNC gérant les liens dans le sens inverse, dit « arrière ». Chaque lien avant FN ou arrière BN entre deux processeurs peut inclure plusieurs lignes physiques, chacune prévue pour véhiculer l'état d'un bit représentant un événement ou une notification. Un tel lien à plusieurs lignes peut ainsi véhiculer plusieurs notifications différenciées par les rangs des lignes. [0025] Les unités FSYNC et BSYNC étendent des unités d'exécution classiquement prévues dans un processeur, et peuvent être configurées pour répondre à deux instructions machine dédiées, à savoir une instruction d'attente et une instruction de notification. Comme dans la demande de brevet US2015-0339256 susmentionnée, les instructions d'attente et de notification peuvent faire partie d'une instruction machine unique dite de synchronisation de groupe SYNCGROUP ayant deux paramètres, l'un identifiant des canaux d'attente et l'autre des canaux de notification. Si le paramètre des canaux d'attente est nul, l'instruction se comporte comme une simple instruction de notification. Inversement, si le paramètre des canaux de notification est nul, l'instruction se comporte comme une simple instruction d'attente. L'exécution d'une instruction SYNCGROUP a la particularité, s'il identifie au moins un canal d'attente, de placer le processeur dans un état d'attente avant d'émettre toute notification. Les notifications sont émises dès que le processeur sort de l'état d'attente. [0026] Ici, l'instruction de synchronisation de groupe peut avoir un paramètre composite de 64 bits, répartis en 16 bits de notification avant notifyF, 16 bits de notification arrière notifyB, 16 bits de canaux d'attente avant waitclrF, et 16 bits de canaux d'attente arrière waitclrB. [0027] La figure 3 est un schéma-bloc d'un mode de réalisation d'unité de synchronisation avant FSYNC d'un processeur PEi, où i est le rang du processeur dans la chaîne. Le processeur comprend des unités d'exécution 10 configurées pour réagir à des instructions machine exécutées sur le processeur, notamment l'instruction de synchro- nisation de groupe. Le processeur comprend également un banc de registres de travail, parmi lesquels un registre est dédié à la synchronisation, que l'on appelle registre IPE (« Inter-Processor Event register » ou registre d'événements inter-processeurs). Par exemple, un registre IPE de 64 bits peut comporter un champ FE d'événements avant de 16 bits, un champ BE d'événements arrière de 16 bits, un champ FM de mode avant de 16 bits, et finalement un champ BM de mode arrière de 16 bits. [0028] Dans l'unité FSYNC représentée à la figure 3, gérant le lien de notification avant EN, ce sont les champs FE et FM qui sont utilisés, ainsi que les paramètres waitclrF et notifyF des instructions de synchronisation. Les champs BE et BM du registre IPE, et les paramètres waitclrB et notifyB sont utilisés par l'unité BSYNC gérant le lien de notification arrière BN et décrite ultérieurement. [0029] Le champ NE du registre IPE est configure pour enregistrer les notifications arrivant sur les 16 lignes de notification avant entrantes FNin, produites par le processeur précédent PEi-1. Par exemple, chaque bit du champ FE, initialement à «0 », passe à « 1 » lorsque la ligne de notification correspondante passe à « 1 », et le bit reste à « 1 » même si la ligne passe ensuite à « 0 ». [0030] Les 16 bits du champ de mode FM du registre IPE forment une première entrée d'une porte ET bit à bit 12, l'autre entrée recevant les 16 lignes de notification entrantes FNin. La sortie sur 16 bits de la porte 12 contribue aux états des 16 lignes de notification avant sortantes FNout, allant au processeur suivant PEi+1. [0031] Ainsi, les états des lignes entrantes FNin peuvent être individuellement bloqués ou propagés sur les lignes de notification sortantes FNout en fonction des bits contenus dans le champ de mode FM. En d'autres termes, des notifications émises par le processeur précédent PEi-1 peuvent être propagées sélectivement au processeur suivant PEi+1. [0032] Le processeur courant PEi peut également émettre des notifications avant à des- tination du processeur suivant. Pour cela les bits du paramètre notifyF d'une instruction de synchronisation exécutée par le processeur PEi sont combinés à la sortie de la porte ET 12 par une porte OU bit à bit 14. Ainsi, tout bit à « 1 » du paramètre notifyF est transmis sur une ligne de notification sortante correspondante, indépendamment de l'état du bit correspondant de la sortie de la porte ET 12. [0033] Lorsqu'une instruction de synchronisation est exécutée par le processeur PEi avec un paramètre waitclrF non-nul, le processeur est mis dans un état d'attente et le paramètre waitclrF détermine la condition requise pour sortir le processeur de l'état d'attente. Plus spécifiquement, le paramètre waitclrF identifie, par des positions de bit respectives, les notifications qui doivent être reçues par le processeur PEi. Toutes les notifications entrantes sont enregistrées dans le champ de registre FE, y compris celles qui transitent par le processeur mais qui ne sont pas destinées au processeur. Ainsi, le 6 contenu du champ FE est comparé en 16 au paramètre waitclrF, de manière que la comparaison produise un résultat « vrai » lorsque les bits à « 1 » du champ de registre FE incluent les bits à « 1 » du paramètre waitclrF. Le résultat « vrai » est pris en compte par les unités d'exécution 10 du processeur pour que le processeur sorte de l'état d'attente et poursuive l'exécution de son programme. Par ailleurs, le résultat « vrai » de la comparaison provoque une réinitialisation des bits du champ de registre FE correspondant aux bits à « 1 » du paramètre waitclrF pour qu'une nouvelle vague de notifications puisse être prise en compte. [0034] La figure 4 est un schéma-bloc d'un mode de réalisation d'unité de synchronisation arrière BSYNC du processeur PEi. Cette unité utilise les champs BE et BM du registre IPE, et les paramètres waitclrB et notifyB de l'instruction de synchronisation, cela pour gérer les liens de notification arrière BN de manière similaire à l'unité de la figure 3. La structure est symétrique pour traiter des lignes de notification entrantes BNin provenant du processeur PEi+1, et des lignes de notification sortantes BNout allant au processeur PEi-1. [0035] Les champs de mode FM et BM des registres IPE des processeurs peuvent être ini- tialisés par un système d'exploitation au démarrage du système, pour configurer des groupes de processeurs à l'intérieur desquels les processeurs se synchronisent entre eux. De préférence, pour réduire la latence, chaque groupe est formé de processeurs consécutifs dans la chaîne. [0036] Par défaut, lorsque les champs BM et FN sont à 0 pour tous les processeurs, il n'y a pas de propagation de notifications et seules des notifications directes sont possibles. On crée ainsi des groupes de trois processeurs, où chaque processeur PEi peut émettre 16 notifications différentes vers chacun de ses deux processeurs adjacents PEU, PEi+1, et recevoir 16 notifications différentes de chacun de ses deux processeurs adjacents. [0037] La mise à « 1 » d'un bit d'un champ de mode BM ou FM dans un processeur PEi perniet la propagation d'une notification correspondante entre les processeurs PEi-1, PEi+1 de part et d'autre du processeur PEi. [0038] Lorsqu'un même bit est à 1 dans tous les champs de mode, tous les processeurs en aval, dans le sens des liens, reçoivent une notification correspondante émise par l'un quelconque des processeurs. Si la chaîne est configurée en anneau, comme cela est le cas à la figure 2, on empêche un bouclage infini de la propagation en mettant à 0 le bit correspondant dans l'un des champs de mode. [0039] En jouant sur les valeurs des bits dans les champs de mode, on peut configurer entre ces deux extrêmes un grand nombre de combinaisons de groupements de processeurs, et les groupements peuvent différer d'une ligne de notification à l'autre. [0040] En outre, quel que soit le groupement choisi, chaque processeur à l'extrémité d'un 7 groupe est à l'intersection de deux groupes adjacents. En effet, même si cc processeur ne propage pas de notification d'un groupe vers l'autre, il peut lui-même émettre une notification vers chacun des groupes, et recevoir une notification de chacun des groupes. [0041] On décrit ci-après un exemple d'application de cette structure à une synchronisation de type barrière. Dans une telle synchronisation, tous les processeurs impliqués doivent atteindre un même point, ou barrière, pour pouvoir poursuivre la suite du traitement. [0042] Dans la structure de la demande de brevet US2015-0339256 la barrière, impliquant au plus quatre processeurs d'un groupe, est matérialisée dans chaque processeur par un registre ayant un bit pour chaque processeur du groupe. Dès qu'un processeur atteint la barrière, il le notifie aux autres processeurs en positionnant le bit qui lui est associé dans les registres des autres processeurs, puis s'arrête pour attendre que les autres processeurs atteignent la barrière. Un processeur à l'arrêt reprend son activité dès que tous les bits correspondant aux autres processeurs sont positionnés dans son registre, en commençant par réinitialiser les bits du registre. [0043] La figure 5 illustre une configuration des processeurs de la figure 2 permettant d'effectuer une synchronisation de type barrière impliquant, par exemple, un groupe de huit processeurs consécutifs 0 à 7 de la chaîne. Pour cela, une seule ligne de notification avant et une seule ligne de notification arrière peuvent être utilisées entre chaque paire de processeurs adjacents du groupe. Bien que les lignes de notification puissent être différentes d'une paire de processeurs à l'autre, on suppose ici, par souci de clarté, que les lignes de notification utilisées ont toutes le même rang k, où k est compris entre 0 et 15 - on utilise ainsi une ligne de notification avant notée FNk et une ligne de notification arrière notée BNk entre les paires de processeurs. [0044] Les processeurs 0 à 7 sont tous configurés pour ne pas propager les notifications avant FNk, c'est-à-dire que le bit de rang k de leurs champs de registre FE est à O. En d'autres termes, un processeur du groupe ne peut recevoir une notification FNk que de son prédécesseur immédiat, comme cela est illustré par des flèches coudées vers la droite partant de l'intérieur des processeurs. [0045] En outre, les processeurs 1 à 6 sont configurés pour propager les notifications arrière BNk, c'est-à-dire que le bit de rang k de leurs champs de registre BE est à 1. Cet état est illustré par des flèches horizontales vers la gauche. [0046] Bien entendu, chaque processeur peut toujours émettre une notification quelconque dans les deux sens, et ses champs de registre FE et BE enregistrent les notifications qui transitent par le processeur. Ainsi, le processeur 7 est illustré avec une flèche coudée vers la gauche indiquant qu'il peut émettre une notification arrière BNk. [0047] Les processeurs 1 à 6 sont programmés pour, en arrivant à la barrière, exécuter suc- cessivement : 8 [0048] - une instruction d'attente d'une notification avant FNk, [0049] - une instruction d'émission d'une notification avant FNk, et [0050] - une instruction d'attente d'une notification arrière BNk. [0051] Les deux premières instructions peuvent être mises en oeuvre par une seule ins- truction SYNCGROUP avec des paramètres waitclrF et notifyF identifiant chacun seulement le rang k. La troisième instruction peut être une instruction SYNCGROUP avec tous ses paramètres nuls sauf le paramètre waitclrB qui identifie seulement le rang k. [0052] Le processeur 0 est programmé pour, en arrivant à la barrière exécuter succes- sivement: [0053] - une instruction d'émission d'une notification avant FNk, et [0054] - une instruction d'attente d'une notification arrière BNk. [0055] Ces deux instructions peuvent être mises en oeuvre par deux instructions SYNCGROUP consécutives dont tous les paramètres sont nuls, sauf respectivement les paramètres notifyF et waitclrB, identifiant chacun seulement le rang k. [0056] Finalement, le processeur 7 est programmé pour, en arrivant à la barrière, exécuter successivement : [0057] - une instruction d'attente d'une notification avant FNk, et [0058] - une instruction d'émission d'une notification arrière BEL [0059] Les deux instructions peuvent être mises en oeuvre par une seule instruction SYNCGROUP avec des paramètres waitclrE et notifyB identifiant chacun seulement le rang k. [0060] Les processeurs 0 à 7 se mettent ainsi en attente au fur et à mesure qu'ils atteignent la barrière. Les processeurs 1 à 7, commençant par exécuter une instruction d'attente, n'émettent pas de notification tant que la barrière n'est pas levée. Seul le processeur 0 commence par une instruction de notification ENk dès qu'il atteint la barrière, avant de s'arrêter à son tour sur une attente. [0061] La notification ENk émise par le processeur 0 est enregistrée par le processeur 1, qui sort de son état d'attente en émettant une notification ENk au processeur 2 suivant. Le processeur 1 se met de nouveau en attente, cette fois d'une notification arrière BNk. En effet, bien que le processeur 1 ait atteint la barrière, on ne sait pas si les autres processeurs en aval l'ont atteinte. [0062] Ces événements se propagent de processeur en processeur jusqu'au processeur 7. Dès qu'il reçoit la notification FNIc, le processeur 7 émet une notification arrière BNk au processeur 6, et poursuit son programme. La barrière a été atteinte par tous les processeurs, car le dernier processeur 7 ne reçoit de notification que si tous les processeurs précédents en ont émis une en atteignant la barrière. [0063] Le processeur 6, ainsi que les processeurs 1 à 5, étant configurés pour propager la no- 9 tification arrière BNk, la notification BNk arrive quasi simultanément à tous les processeurs 0 à 6. Chacun de ces processeurs sort de son état d'attente et poursuit son programme. [0064] Cette structure de synchronisation ouvre également de nouvelles perspectives d'exécution de traitements parallèles, notamment de boucles dont les itérations ne sont pas indépendantes. Des itérations sont indépendantes dans une boucle quand leurs accès à des données partagées comme des tableaux s'effectuent sur des éléments différents. [0065] Une structure multi-coeurs classique permet d'allouer plusieurs processeurs pour exécuter en parallèle plusieurs itérations d'une boucle. Par exemple, chaque itération d'une boucle du type suivant est indépendante et peut être affectée à un coeur différent : [0066] for (i=0; i 0 et variable : [0097] for (i=0; i