Brevet FR2982049A1 — publié le 20130503

GESTION DE FLUX DANS UN RESEAU SUR PUCE Domaine technique de l'invention L'invention est relative aux techniques de gestion de flux sur un réseau, notamment une 5 gestion selon la technique des « crédits » dans un réseau sur puce (NoC). État de la technique Les techniques de gestion de flux cherchent à organiser de manière optimale la transmission de paquets de données entre un producteur et un consommateur situés sur deux noeuds distincts d'un canal de transmission partagé asynchrone, par exemple un 10 réseau. Dans le cadre d'une gestion de flux selon la technique des crédits, le consommateur comprend une mémoire tampon ou file d'entrée pour chaque producteur, dans laquelle sont stockés les paquets en attente de consommation. Chaque producteur dispose d'un compteur de crédit qui démarre à la taille, en nombre de paquets, de la file d'entrée du 15 consommateur. A chaque envoi d'un paquet, le producteur décrémente son compteur de crédit. Il cesse les envois lorsque son compteur atteint zéro. Les paquets envoyés arrivent dans la file d'entrée du consommateur. Celui-ci, après avoir consommé un certain nombre de paquets de sa file, renvoie au producteur un 20 crédit indicatif de la place disponible dans la file. En recevant ce crédit, le producteur incrémente son compteur du nombre correspondant, ce qui lui permet de continuer à envoyer des paquets. Des optimisations de cette technique consistent à régler le seuil d'envoi des crédits pour que le producteur les reçoive avant que son compteur n'ait atteint zéro, mais pour que 25 leur nombre n'engorge pas le canal de transmission en sens inverse. Une telle gestion de flux est utilisée, par exemple, dans le bus dénommé « PCIExpress ». La technique des crédits est généralement utilisée dans les situations où la bande passante du canal de transmission est faible par rapport à la capacité de traitement des 30 producteurs et consommateurs, par exemple dans le cadre d'un réseau macroscopique. Cela signifie que le consommateur est capable de vider sa file d'entrée plus vite qu'elle ne peut être remplie par le canal de transmission, et que le producteur est capable de remplir une file de sortie en moins de temps qu'il ne faut pour la vider par le canal de transmission. Dès lors, la structure des paquets importe peu, car les producteurs et consommateurs disposent de suffisamment de ressources entre deux envois de paquet pour mettre en oeuvre des conversions de format, si cela est requis. Dans un réseau sur puce, la bande passante du réseau est adaptée à la capacité des producteurs et consommateurs. On est alors amené à tenir compte des tailles de mot exploitées par le consommateur et le producteur, de sorte qu'un même paquet peut être formé de mots de tailles différentes, selon qu'il est vu par le producteur ou par le consommateur. Compter des crédits en nombres de paquets peut alors s'avérer inadapté. Résumé de l'invention On souhaite ainsi disposer d'une gestion de flux par crédits satisfaisante dans une situation où la bande passante du canal de transmission est adaptée à la capacité des producteurs et consommateurs. On souhaite notamment que cette gestion tienne compte 15 des tailles de mot différentes utilisées par les producteurs et les consommateurs. On tend à satisfaire ce besoin en prévoyant un procédé de gestion de flux de données entre un producteur et un consommateur selon la technique des « crédits », comprenant les étapes consistant à décrémenter un compteur de crédit à chaque émission d'une série de données par le producteur ; cesser d'émettre des données lorsque le compteur de 20 crédit atteint zéro ; envoyer un crédit à chaque fois que le consommateur a consommé une série de données ; et incrémenter le compteur de crédit à la réception du crédit. La taille Wc des données utilisable par le consommateur et la taille Wp des données émises par le producteur sont telles que Wc/Wp > 1, et le crédit, en nombre de données de taille Wc, s'exprime par : 25 C = (Na - Q-F)/Q où Na est la place disponible, en nombre de données de taille Wc, dans une file d'entrée du consommateur prévue pour stocker les données en attente de consommation, Q un facteur tel que 1 Selon un mode de mise en oeuvre, le facteur Q est choisi égal à Wc/Wp lorsque les mots des paquets sont stockés à des emplacements aléatoires de la mémoire. Selon un mode de mise en oeuvre, le facteur Q tend vers (P+1)/P, où P est la taille d'une salve de mots de Wp bits à stocker dans des emplacements contigus de la mémoire. Selon un mode de mise en oeuvre, un crédit est envoyé à chaque fois que le consommateur a consommé un nombre seuil de mots de Wc bits au plus égal à S/Q, où S est la capacité de la file. Selon un mode de mise en oeuvre, le nombre seuil est égal à S/Q diminué du nombre de mots transmissibles pendant la durée d'arrivée à destination d'un crédit. Selon un mode de mise en oeuvre, F est déterminé comme la différence entre le cumul des crédits envoyés et le nombre des données reçues par le consommateur. 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 représente schématiquement un réseau sur puce connecté à une mémoire externe ; - la figure 2 représente schématiquement et partiellement des circuits impliqués dans une gestion de flux par crédits, dans la situation de la figure 1 ; - la figure 3 représente un exemple de succession de mots tels que produits en un noeud du réseau et tels que consommés par la mémoire externe ; et - la figure 4 représente un autre exemple de succession de mots tels que produits en un noeud du réseau et tels que consommés par la mémoire externe. Description d'un mode de réalisation préféré de l'invention La figure 1 représente schématiquement une matrice de processeurs PA comprenant 4x4 noeuds de calcul N agencés dans un réseau sur puce de topologie torique repliée, telle que décrite dans la demande de brevet US 2011-0058569. Dans une topologie matricielle, chaque noeud est relié à deux autres noeuds de la même rangée et à deux autres noeuds de la même colonne, par des liaisons point à point bidirectionnelles. Dans une topologie torique, les noeuds de la matrice sont en outre reliés en boucle dans chaque rangée et dans chaque colonne, de sorte que tous les noeuds ont la même structure physique quant à leurs interconnexions, notamment les noeuds situés aux bords de la matrice. Dans une topologie repliée, qui est celle représentée en figure 1, chaque noeud (sauf s'il est situé en bord de matrice) est relié à deux autres noeuds de même parité dans la rangée et dans la colonne, de sorte que les liaisons entre les noeuds aient sensiblement la même longueur. Chaque noeud N comprend un routeur à cinq voies qui gère les quatre liaisons, dites Nord, Sud, Est et Ouest, vers les noeuds suivants dans la rangée et la colonne, et une liaison avec un module de calcul, non représenté, constitué par exemple d'une grappe de 10 processeurs interconnectés par un bus parallèle. La matrice PA, pouvant être sous la forme d'un circuit intégré indépendant, est généralement associée à une mémoire dynamique externe DRAM. Cette mémoire est reliée à la matrice PA par une ou plusieurs de ses interfaces d'entrée/sortie IO, en fonction de la bande passante des interfaces et de la mémoire. On s'intéresse ci-après 15 essentiellement à l'écriture de données dans la mémoire DRAM, qui sera donc considérée comme le « consommateur », les noeuds de la matrice étant les « producteurs ». Dans l'exemple représenté, on utilise quatre interfaces IO reliées à un circuit d'arbitrage ARBTR qui gère les transferts de données entre les interfaces IO et le bus unique de la 20 mémoire. Dans un exemple pratique, le bus de la mémoire a une largeur de 64 bits et chacune des interfaces IO communique par un bus de 32 bits, de même largeur que les bus servant aux liaisons internes du réseau. Avec cette configuration, il y a un équilibre théorique entre les bandes passantes de la mémoire et du réseau lorsque le débit par fil des bus du réseau est la moitié du débit par fil du bus mémoire. 25 Ainsi, la mémoire consomme des mots de Wc = 64 bits, alors que le réseau produit des paquets de mots de Wp = 32 bits. La figure 2 représente schématiquement et partiellement une structure permettant de mettre en oeuvre une gestion de flux par crédits dans l'exemple de la figure 1. L'arbitre ARBTR comprend une file d'entrée 10 pour chaque noeud N du réseau susceptible 30 d'écrire des données dans la mémoire DRAM. En pratique, les rôles des noeuds N sont interchangeables, d'où il résulte que l'arbitre comprend une file pour chaque noeud, donc 16 files dans le cadre de l'exemple. Les files 10 sont prévues pour contenir les mots en attente de consommation par la mémoire DRAM. Ces mots sont donc, de préférence, des mots de la largeur du bus mémoire, ici 64 bits. Par contre, les paquets arrivant par le réseau sont formés de mots conformes à la largeur des liaisons internes du réseau, ici 32 bits. Ainsi, chaque file est précédée d'un circuit de réalignement RALGN qui juxtapose les mots de 32 bits du paquet entrant pour former des mots de 64 bits à placer dans la file. Chaque file est gérée par un circuit de commande CTRL qui comptabilise la place disponible dans la file et les mots consommés pour envoyer des crédits C au noeud producteur, par le réseau. En recevant un crédit, le producteur incrémente son compteur 10 de crédit, et envoie de nouvelles données tant que son compteur n'atteint pas zéro. Selon les techniques classiques, l'unité du crédit est le paquet. Cela sous-entend que le producteur et le consommateur utilisent la même définition de « paquet ». Or, dans le cas présent, un paquet est formé de mots de 32 bits alors que le consommateur requiert des mots de 64 bits. Un paquet n'est pas vu de la même manière du côté consommateur 15 que du côté producteur. Pour échapper à cette difficulté, on commence par redéfinir l'unité du crédit. On propose que le crédit soit indicatif du nombre de mots de la largeur Wc de la file d'entrée, ici des mots de 64 bits directement consommables par la mémoire DRAM. Si on intègre cette définition directement dans les calculs classiques, le crédit à renvoyer 20 vaudrait +1 pour chaque emplacement libre de la mémoire FIFO. Du côté du producteur, un crédit de 1 correspondrait à 64 bits, donc à une paire de mots de 32 bits à envoyer. Or ces deux mots peuvent ne pas correspondre à des emplacements contigus dans la mémoire DRAM, de sorte qu'ils ne peuvent pas être écrits en un seul mot de 64 bits 25 dans la mémoire. Même s'ils ont des destinations contiguës, le premier mot de 32 bits peut avoir une adresse qui démarre à la deuxième moitié d'un mot mémoire de 64 bits. Dans ce cas également, les deux mots ne peuvent pas être écrits en mémoire en un seul mot de 64 bits. De tels mots « désalignés », comme des mots à écrire à des adresses aléatoires, sont 30 écrits en mémoire par l'intermédiaire de deux mots de 64 bits consécutifs, c'est-à-dire en deux cycles. Pour cela, le circuit de réalignement RALGN a pour fonction d'analyser les destinations en mémoire des mots de 32 bits entrants, destinations figurant dans l'entête du paquet : - si deux mots de 32 bits ont des destinations contiguës, et que la destination du premier mot correspond à une adresse d'un mot mémoire de 64 bits, les deux mots sont juxtaposés dans un seul emplacement de 64 bits de la file ; - dans le cas contraire, c'est-à-dire si les mots de 32 bits sont désalignés, ils sont placés dans deux mots de 64 bits consécutifs de la file, dans la première moitié ou la deuxième moitié du mot de 64 bits respectif, selon l'adresse de la destination en mémoire. La moitié inutilisée du mot de 64 bits est marquée comme « invalidée » à l'écriture dans la mémoire. En effet, il est possible, à l'écriture d'un mot dans une mémoire DRAM, d'invalider des octets individuels, de sorte que les emplacements correspondants ne soient pas affectés par l'écriture. Cela permet d'écrire des octets individuels en mémoire malgré une taille de bus supérieure à l'octet. Il en résulte que deux mots de 32 bits peuvent occuper deux emplacements de 64 bits dans la file. Cela correspond au pire cas. Pour en tenir compte, le crédit effectivement 15 utilisé est divisé par 2. Cela revient à présenter au producteur une file de taille deux fois plus petite, du point de vue du nombre de bits. Ainsi, le crédit effectif à utiliser s'exprime par : C = Na/2, où Na est le nombre de places disponibles dans la mémoire FIFO, en mots de 64 bits 20 côté consommateur, ou en paires de mots de 32 bits côté producteur. De façon générale, si la taille des mots du côté producteur est Wp, et la taille des mots du côté consommateur est Wc, le crédit effectif s'exprime par : C = Na-Wp/Wc. Compte tenu du fait que dans un réseau sur puce on travaille en « flux tendus », c' est-à- 25 dire que la bande passante du réseau est adaptée à la capacité des producteurs et consommateurs, ce calcul peut s'avérer trop optimiste, même s'il tient compte du pire cas. En effet, ce calcul ne tient pas compte du fait que la place Na disponible dans la file à un instant d'observation pourrait être remplie à tout moment par des données encore en transit ou « en vol », ces données correspondant aux derniers crédits envoyés. Dans 30 un réseau macroscopique, où les producteurs et consommateurs disposent d'importantes ressources matérielles, ce problème est transparent du fait que la taille des files d'entrée est dimensionnée avec suffisamment de marge. Dans un réseau sur puce, on cherche à minimiser la taille des files. Ainsi, on propose d'affiner le calcul du crédit pour tenir compte de ces données « en vol ». Le crédit s'exprime alors par : C = (Na - K.F)/K, (1) où K = Wc/Wp et F correspond aux données « en vol ». F est égal à la différence entre le cumul des crédits C envoyés et le nombre de mots de 64 bits écrits dans la file d'entrée. Cette valeur F est fournie, par exemple, par un compteur géré par le circuit de commande CTRL, incrémenté du montant de chaque crédit C envoyé et décrémenté à chaque occupation d'un emplacement (de 64 bits) de la file d'entrée. On n'a pas encore précisé à quel moment envoyer un crédit. Le critère d'envoi des crédits est également susceptible d'optimisation. En effet, les envois de crédits ne doivent pas être trop fréquents, sous peine d'engorger le réseau, ni trop peu fréquents, sous peine d'arrêter prématurément la production de données. Un critère simple est d'envoyer un crédit à chaque fois que la mémoire a consommé un nombre seuil de mots. Le seuil est inférieur ou égal à 1/K = 1/2 de la capacité de la file d'entrée. En effet, avec les techniques des crédits classiques, le plus grand intervalle d'attente pour envoyer un crédit correspond à la durée minimale nécessaire à vider une file pleine, auquel cas le crédit est susceptible d'être égal à la taille de la file. Dans le cas présent, comme un crédit de 1 peut résulter, dans le pire cas, à une occupation de K emplacements dans la file, les crédits sont envoyés à une fréquence K fois supérieure, et sont au plus égaux à 1/K de la taille de la file. En fait, il vaut mieux fixer le seuil à une valeur légèrement inférieure à S/K = S/2, où S est la capacité de la file, mais pas trop basse non plus, pour éviter un trafic de crédits 25 trop important. Dans l'exemple considéré, on choisit S/2 diminué du nombre de paires de mots de 32 bits transmissibles pendant la durée de transit d'un crédit. Dans le cas général, où K est un entier quelconque supérieur à 1, on exprime le seuil par : Tc = S/K - Nt,(K), 30 où Nt,(K) est le nombre de K-uplets de mots producteur transmissibles pendant le temps de transit tc d'un crédit. Le temps de transit tc pouvant être exprimé en cycles d'horloge, et puisqu'on transmet en général un mot producteur par cycle, on a Nt,(K) = tc/K. Le temps de transit d'un crédit dépendant du nombre de routeurs à traverser pour arriver à destination, on prendra une valeur moyenne. Jusqu'ici on a fait intervenir dans les divers calculs un facteur K correspondant à une situation pire cas. Il existe des situations où on peut, à la place de K, utiliser un facteur Q réglable tendant vers 1. Les figures suivantes permettent d'illustrer cela par des exemples. L'expression du crédit devient : C = (Na - Q-F)/Q = Na/Q - F, où Q est un facteur tel que 1 La figure 4 représente un deuxième exemple de succession de mots tels que produits (à gauche) et tels que consommés par la mémoire DRAM. Le producteur envoie une succession de 32 octets contigus, mais dont le premier est désaligné. Ces octets sont transmis dans deux paquets successifs de 8 mots de 32 bits. On n'a représenté que le premier mot du deuxième paquet, en position 8. Lorsque ces 32 octets, transmis en 9 mots de 32 bits, auront été écrits en mémoire, on aura utilisé 5 mots de 64 bits. Dans cet exemple, on peut se contenter d'un facteur Q = 10/9. De façon générale, si la succession de données produites présente un caractère régulier, 10 on peut ajuster le facteur Q en fonction de la nature de cette régularité. Pour une salve de données transmissible dans P mots contigus de Wp bits, on peut choisir Q = (P+1)/P. Dans le premier exemple, on a P = 2, et dans le deuxième P = 9. La taille de salve P peut être connue d'avance, au moins par le processus producteur des données, par exemple à la compilation du programme de mise en oeuvre du processus, 15 ou par le programmeur. Cette taille P peut être transmise dans l'entête des paquets afin de paramétrer le calcul des crédits au niveau du consommateur. En pratique, il n'est pas prudent de modifier le facteur Q à chaque paquet, du moins vers des valeurs plus favorables (décroissantes), car chaque facteur reste en vigueur au début du paquet suivant, pouvant avoir un facteur Q moins favorable, pendant le temps 20 de transit du nouveau facteur Q. Ainsi, on envisagera plutôt d'utiliser un facteur Q constant, programmé à l'initialisation du système, pour chaque file. Bien que l'on puisse envisager un circuit dédié aux calculs impliquant le facteur variable Q, celui-ci, nécessitant une division, est relativement complexe et devrait être prévu pour chaque file 10 du circuit d'arbitrage ARBTR, dans l'exemple étudié. On 25 préfèrera appliquer un coefficient Q majoré plus facile à utiliser. En rendant Q sélectionnable parmi 2, 4/3, 8/7... 2'/(2' - 1), le crédit s'exprime par : C = Na - (Na » n) - 1 - F, si les n bits de poids faible de Na ne sont pas tous nuls, ou C = Na - (Na » n) - F, si les n bits de poids faible sont tous nuls, 30 où « » n » désigne un décalage à droite de n bits, et : - n= 1 pour Q = 2, - n = 2 pour Q = 4/3, - n = 3 pour Q = 8/7... - n = i pour Q = 21/(21- 1). Le calcul se résume alors à un décalage à droite et deux ou trois soustractions. Dans ce cas, pour une taille de salve de P = 2, pour laquelle on a idéalement Q = 3/2, on prendra Q = 2, soit n = 1. Pour une taille de salve de P = 9, pour laquelle on a idéalement Q = 10/9, on prendra Q = 8/7, soit n = 3. De façon générale, on choisit Q = r(2' - 1), où i est un entier choisi pour que Q soit le plus proche possible de (P+1)/P par excès. Les deux expressions, conditionnelles, du crédit ci-dessus, sont équivalentes à 10 l'expression unique : C = ((Na n) - Na) » n - F. Un décalage à droite ou à gauche de « n » s'effectue à l'aide d'un multiplexeur qui sélectionne la partie souhaitée du mot à décaler, et substitue les bits manquants par des bits à 0. 15 On a considéré dans ce qui précède que la file d'entrée avait des emplacements de la taille du bus mémoire (64 bits). On peut également envisager que ces emplacements soient adaptés à la taille des mots entrants, de 32 bits. Le circuit de réalignement RALGN serait alors placé à la sortie de la file, et configuré pour former des mots de 64 bits à écrire dans la mémoire. Ces mots de 64 bits pourraient être formés au vol en lisant 20 les mots de la file à deux fois la cadence d'écriture dans la mémoire. REVENDICATIONS1. Procédé de gestion de flux de données entre un producteur et un consommateur selon la technique des « crédits », comprenant les étapes suivantes : - décrémenter un compteur de crédit à chaque émission d'une série de données par le producteur ; - cesser d'émettre des données lorsque le compteur de crédit atteint zéro ; - envoyer un crédit à chaque fois que le consommateur a consommé une série de données ; et - incrémenter le compteur de crédit à la réception du crédit ; caractérisé en ce que la taille Wc des données utilisable par le consommateur et la taille Wp des données émises par le producteur sont telles que Wc/Wp > 1, et le crédit, en nombre de données de taille Wc, s'exprime par : C = (Na - Q-F)/Q où Na est la place disponible, en nombre de données de taille Wc, dans une file d'entrée (10) du consommateur prévue pour stocker les données en attente de consommation, Q un facteur tel que 1 2. Procédé selon la revendication 1, dans lequel le consommateur est une mémoire (DRAM) de mots de Wc bits et les données sont émises sur un réseau sous forme de paquets de mots de Wp bits. 3. Procédé selon la revendication 2, dans lequel le facteur Q est choisi égal à Wc/Wp lorsque les mots des paquets sont stockés à des emplacements aléatoires de la mémoire. 4. Procédé selon la revendication 2, dans lequel le facteur Q tend vers (P+1)/P, où P est la taille d'une salve de mots de Wp bits à stocker dans des emplacements contigus de la mémoire. 5. Procédé selon la revendication 1, dans lequel un crédit est envoyé à chaque fois que le consommateur a consommé un nombre seuil de mots de Wc bits au plus égal à S/Q, où S est la capacité de la file. 6. Procédé selon la revendication 5, dans lequel le nombre seuil est égal à S/Q diminué du nombre de mots transmissibles pendant la durée d'arrivée à destination d'un crédit. 7. Procédé selon la revendication 1, dans lequel F est déterminé comme la différence entre le cumul des crédits envoyés et le nombre des données reçues par le consommateur. 8. Procédé selon la revendication 4, dans lequel Q = r(2' - 1), où i est un entier choisi pour que Q soit le plus proche possible de (P+1)/P par excès, le crédit étant alors exprimé par : C = Na - (Na » i) - 1 - F, si les i bits de poids faible de Na ne sont pas tous nuls, ou C = Na - (Na » i) - F, si les i bits de poids faible sont tous nuls, où « » i » désigne un décalage à droite de i bits. 9. Procédé selon la revendication 4, dans lequel Q = r(2' - 1), où i est un entier choisi pour que Q soit le plus proche possible de (P+1)/P par excès, le crédit étant alors exprimé par : C = ((Na « i) - Na) » i - F, où « » i » désigne un décalage à droite de i bits, et « « i » un décalage à gauche de i bits.