Brevet FR3024310A1 — publié le 20160129

La présente invention concerne un procédé de régulation dynamique de débits de consigne dans un réseau sur puce. Elle concerne également un programme d'ordinateur et un dispositif de traitement de données correspondants. Dans un système intégré, la communication entre les unités de calcul se fait au moyen d'un réseau sur puce. Le trafic dans ce réseau doit être régulé de façon précise pour éviter toute congestion tout en assurant la meilleure efficacité possible dans le transfert des données. Une telle régulation peut se faire à la source à l'aide d'un limiteur de trafic dont la fonction est de réguler les données injectées dans le réseau en fonction de débits de consigne affectés respectivement à toutes les sources émettrices de ces données. L'invention s'applique ainsi plus particulièrement à un procédé de régulation dynamique de débits de consigne de sources émettrices de paquets de données vers des cibles réceptrices de ces paquets de données dans un réseau sur puce comportant une pluralité de noeuds, parmi lesquels se trouvent les sources et les cibles, et une pluralité de liens entre ces noeuds pour la transmission des paquets de données. Dans une configuration topologique donnée et pour une activité donnée des sources d'émission, chaque source active émet ses paquets de données vers une cible selon un canal de transmission point à point, défini par un ensemble de noeuds et de liens entre ces noeuds, et selon un débit de consigne défini pour cette source ou, de façon équivalente, pour ce canal de transmission. L'ensemble de ces canaux de transmission définit ce que l'on appelle une configuration de routage. Chaque lien étant susceptible d'appartenir à plusieurs canaux de transmission différents et présentant lui-même une capacité de débit maximal qui lui est propre, une optimisation des débits de consigne dans une configuration de routage donnée est nécessaire pour fluidifier le trafic de données tout en respectant les besoins en flux de chacune des sources. Cette optimisation est généralement complexe mais importante parce que l'on cherche à utiliser au mieux la bande passante globalement disponible dans le réseau sur puce. Dans le domaine plus général des réseaux à transmission de données par 30 paquets, de nombreuses études ont été menées et différentes méthodes d'optimisation distribuée entre les noeuds d'un réseau ont été proposées. Ainsi par exemple, dans l'article de Jaffe, intitulé « Bottleneck flow control », publié dans IEEE Transactions on Communications, vol. COM-29, n° 7, Juillet 1981, il est proposé un procédé itératif de régulation de débit à la source comportant une 35 répétition des étapes suivantes : 3024310 2 pour chaque lien d'un réseau sollicité par la transmission de paquets de données et en fonction de débits de consigne définis pour chaque source émettrice et chaque canal de transmission correspondant, l'estimation d'une marge de débit disponible incluant l'estimation d'une marge calculée 5 sur la base d'une capacité de débit maximal du lien, pour chaque source émettrice d'au moins un paquet de données, le calcul et l'application d'une mise à jour de son débit de consigne en fonction des marges de débits disponibles estimées. Plus précisément, la marge calculée pour chaque lien tient compte de la 10 différence entre le débit maximal que peut supporter ce lien et la somme des débits de consigne des canaux de transmission incluant ce lien. Plus précisément également l'itération des deux étapes précédentes est répétée tant que toutes les sources émettrices ne sont pas saturées, c'est-à-dire tant qu'il existe au moins une source dont aucun lien du canal de transmission associé 15 n'est saturé selon un critère de saturation prédéterminé. D'autres méthodes d'optimisation procèdent d'une formalisation différente, par optimisation globale non linéaire à l'aide d'un solveur, mais restent distribuées. De telles méthodes sont par exemple décrites dans l'article de Kelly, intitulé « Charging and rate control for elastic traffic », publié dans European Transactions on 20 Telecommunications, vol. 8 (1997), pages 33-37, ou dans l'article de Low et al, intitulé « Optimization flow control, I: basic algorithm and convergence », publié dans IEEE/ACM Transactions on Networking, 7(6), pages 861-874, décembre 1999. Toutes ces méthodes sont directement transposables dans le domaine des transmissions de données dans un réseau sur puce. 25 Mais comme cela a par ailleurs été montré dans l'article de Zhang, intitulé « Service disciplines for guaranteed performance service in packet-switching networks », publié dans Proceedings of the IEEE, vol. 83, n° 10, octobre 1995, la prise en compte de la capacité en débit de chaque lien ne suffit pas à garantir une absence de congestion. Il existe en effet un phénomène de distorsion de forme de trafic dû à des dépassements sporadiques possibles des débits de consigne aux points de convergences entre canaux de transmission. Ces dépassements sporadiques ont notamment été identifiés et formalisés dans l'article de Cruz, intitulé « A calculus for network delay, Part I: network elements in isolation » publié dans IEEE Transactions on Information Theory, vol. 37, n° 1, janvier 1991, puis dans l'article de Zhang précité. 3024310 3 Les solutions consistant alors à prévoir éventuellement une marge constante supplémentaire pour éviter ces congestions ne sont cependant pas satisfaisantes parce que non optimales. Il peut ainsi être souhaité de prévoir un procédé de régulation dynamique de 5 débits de consigne dans un réseau sur puce qui permette de s'affranchir d'au moins une partie des problèmes et contraintes précités. Il est donc proposé un procédé de régulation dynamique de débits de consigne de sources émettrices de paquets de données vers des cibles réceptrices de ces paquets de données dans un réseau sur puce comportant une pluralité de 10 noeuds, parmi lesquels se trouvent les sources et les cibles, et une pluralité de liens entre ces noeuds pour la transmission des paquets de données, comportant : pour chaque lien du réseau sur puce sollicité par la transmission des paquets de données, l'estimation d'une marge de débit disponible incluant l'estimation d'une première marge calculée sur la base d'une capacité de 15 débit maximal du lien, pour chaque source émettrice d'au moins un paquet de données, le calcul et l'application d'une mise à jour de son débit de consigne en fonction des marges de débits disponibles estimées, dans lequel l'estimation de la marge de débit disponible pour chaque lien comporte 20 en outre : l'estimation d'une deuxième marge calculée sur la base d'une capacité d'absorption locale maximale, par mémoire tampon, de dépassements sporadiques possibles des débits de consigne, la détermination d'une valeur de la marge de débit disponible en fonction 25 des première et deuxième marges calculées. Chaque lien du réseau sur puce peut en effet être vu comme l'association d'une connexion physique point à point, entre deux noeuds voisins dans une certaine direction, et d'au moins une mémoire tampon. Cette mémoire tampon peut être une mémoire tampon de sortie du noeud de départ du lien ou une mémoire tampon 30 d'entrée dans le noeud d'arrivée du lien. Quel que soit le modèle choisi, cette mémoire tampon possède une capacité limitée d'absorption de dépassements sporadiques des débits de consigne pouvant survenir aux points de convergences des canaux de transmission et il est judicieux d'en tenir compte. Ainsi selon l'invention, cette capacité d'absorption locale maximale de 35 dépassements sporadiques possibles des débits de consigne est prise en compte au 3024310 4 niveau du routage entre les liens du réseau sur puce dans la détermination des marges à distribuer entre sources émettrices, de sorte que la régulation des débits de consigne peut se faire de façon vraiment optimale. De façon optionnelle, pour une configuration de routage donnée incluant un 5 ensemble de canaux de transmission des paquets de données entre les sources et les cibles, les étapes d'estimation des marges de débits disponibles et de calcul de mises à jour des débits de consigne sont exécutées uniquement pour des canaux de transmission non saturés, c'est-à-dire des canaux de transmission n'ayant encore aucun lien sans marge de débit disponible, et répétées jusqu'à ce que tous les 10 canaux de transmission soient saturés. De façon optionnelle également : - l'estimation de la première marge notée « rcink » pour chaque lien noté « lnk », calculée sur la base de la capacité de débit maximal du lien notée « Clnk », est effectuée sur la base de l'équation suivante : rcink = Clnk E Pch chEccink 15 dans laquelle c est une constante de marge résiduelle en dessous de laquelle on considère que la marge de débit disponible est nulle pour ce lien, CCInk est l'ensemble des canaux de transmission notés « ch » qui incluent le lien lnk et pch désigne le débit de consigne du canal de transmission ch, et - l'estimation de la deuxième marge notée « rdink » pour chaque lien lnk, 20 calculée sur la base de la capacité d'absorption locale maximale du lien notée « 13Fink », est effectuée sur la base de l'équation suivante : rdink = BFink E Dch,Ink Pch chEccink dans laquelle Dch,Ink désigne un coefficient prédéterminé propre à chaque lien de chaque canal de transmission. De façon optionnelle également, la régulation de débit étant faite à la source 25 par fenêtre glissante selon une discipline d'arbitrage de type « work conserving » : - la capacité d'absorption locale maximale de chaque lien lnk est définie par l'équation suivante : (Nink - 1) BFink = QSIZE DMAX - Tw , NInk dans laquelle QSIZE est la taille de la mémoire tampon associée au lien lnk, Nink est le nombre de canaux de transmission passant par le lien lnk, DMAX est une 3024310 5 constante de débit instantané maximal d'injection et Tw est la longueur de la fenêtre glissante, et - chaque coefficient Dch,ink est défini par l'équation suivante : Dch,Ink = dl,ch leRR ch,Ink dans laquelle FIRch,Ink est l'ensemble des liens traversés en amont du lien lnk dans le 5 canal de transmission ch, « I » désignant l'un de ces liens, et di,ch est un coefficient défini par di,ch = (ncli - 1) - PSIZE, où ndi est le nombre de directions contributrices sur la mémoire tampon associée au lien I et PSIZE est la taille maximale des paquets de données exprimée dans la même unité que QSIZE. De façon optionnelle également, les étapes d'estimation des marges de débits 10 disponibles et de calcul de mises à jour des débits de consigne sont exécutées de façon séquentielle, cette séquence étant elle-même exécutée de façon itérative. De façon optionnelle également, les étapes d'estimation des marges de débits disponibles et de calcul de mises à jour des débits de consigne sont séquentiellement exécutées à l'aide de barrières de synchronisation implémentées sous la forme de 15 décompteurs de messages pour chaque lien du réseau sur puce sollicité par la transmission des paquets de données et pour chaque source émettrice d'au moins un paquet de données. De façon optionnelle également, les étapes d'estimation des marges de débits disponibles et de calcul de mises à jour des débits de consigne sont exécutées de 20 façon incrémentielle et entrelacée par une sérialisation de messages de régulation dynamique des débits de consigne selon des chemins prédéfinis. De façon optionnelle également, la valeur de marge de débit disponible est déterminée pour chaque lien en tant que minimum entre les première et deuxième marges calculées pour ce lien. 25 Il est également proposé un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, comprenant des instructions pour l'exécution des étapes d'un procédé de régulation dynamique de débits de consigne selon l'invention, lorsque ledit programme est exécuté sur un ordinateur. 30 Enfin, il est également proposé un dispositif de traitement de données à réseau sur puce, comportant : 3024310 6 une pluralité de noeuds, parmi lesquels se trouvent des sources émettrices de paquets de données et des cibles réceptrices de ces paquets de données, une pluralité de liens entre ces noeuds pour la transmission des paquets de 5 données, et des calculateurs de régulation dynamique de débits de consigne des sources, répartis entre les noeuds du réseau sur puce et programmés pour : - pour chaque lien du réseau sur puce sollicité par la transmission des 10 paquets de données, estimer une marge de débit disponible en estimant une première marge calculée sur la base d'une capacité de débit maximal du lien, - pour chaque source émettrice de paquets de données, calculer une mise à jour de son débit de consigne en fonction des marges de débits 15 disponibles estimées, dans lequel chaque calculateur programmé pour estimer la marge de débit disponible de l'un quelconque des liens est en outre programmé pour : estimer une deuxième marge calculée sur la base d'une capacité d'absorption locale maximale, par mémoire tampon, de dépassements 20 sporadiques possibles des débits de consigne, déterminer une valeur de la marge de débit disponible en fonction des première et deuxième marges calculées. L'invention sera mieux comprise à l'aide de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés 25 dans lesquels : la figure 1 représente schématiquement la structure générale d'un dispositif de traitement de données à réseau sur puce, selon un mode de réalisation de l'invention, la figure 2 représente schématiquement la structure générale d'un exemple 30 de routeur disposé au niveau d'un noeud de réseau du dispositif de traitement de données de la figure 1, la figure 3 illustre les étapes successives d'un procédé de régulation dynamique de débits de consigne mis en oeuvre dans le dispositif de traitement de données de la figure 1, 3024310 7 la figure 4 est un exemple simplifié d'exécution du procédé de régulation de la figure 3, avec la mise en oeuvre d'un mécanisme de synchronisation selon un premier mode de réalisation de l'invention, les figures 5 et 6 illustrent schématiquement les fonctionnements de liens 5 et de sources du dispositif de traitement de données de la figure 1 pour la mise en oeuvre du mécanisme de synchronisation de la figure 4, la figure 7 est un exemple simplifié d'exécution du procédé de régulation de la figure 3, avec la mise en oeuvre d'un mécanisme de synchronisation selon un deuxième mode de réalisation de l'invention, et 10 les figures 8 et 9 illustrent schématiquement les fonctionnements de liens et de sources du dispositif de traitement de données de la figure 1 pour la mise en oeuvre du mécanisme de synchronisation de la figure 7. Le dispositif 10 de traitement de données illustré sur la figure 1 comporte un réseau sur puce partiellement représenté. Ce réseau sur puce, réalisé sous la forme 15 d'un circuit intégré, est constitué d'une pluralité de noeuds disposés en matrice et interconnectés entre eux par des liens bidirectionnels orientés dans quatre directions matricielles Nord (N), Sud (S), Ouest (W) et Est (E). Les liens permettent la transmission de paquets de données d'un noeud à l'autre. Dans l'exemple de la figure 1, seuls quatre noeuds sont représentés de façon 20 non limitative et notés Ni+1,, et Ni+1,J+1. Quatre liens bidirectionnels L,,,(N), L,,,(W) et L,,,(E) partent du noeud dans les quatre directions précitées. Quatre liens bidirectionnels L;,;+, (N), Liel(W) et 1-,,,±1(E) partent du noeud Ni,J+1 dans les quatre directions précitées. Quatre liens bidirectionnels L,±1,,(N), L,±1,,(S), L,±1,,(W) et L,±1,,(E) partent du noeud N,+1,, dans les quatre directions précitées. Enfin, 25 quatre liens bidirectionnels 1-,±1,,±i(N), 1-,±1,,±1(S)1 Li+1,j+1(W) et Li+1,j+1(E) partent du noeud N,+1,J+1 dans les quatre directions précitées. On notera que le lien bidirectionnel L,,,(E) correspond au lien bidirectionnel L,,,±1(W), que le lien bidirectionnel L,±1,,(E) correspond au lien bidirectionnel 1-41,,±1(W), que le lien bidirectionnel L,,,(S) correspond au lien bidirectionnel L,±1,,(N) et que le lien bidirectionnel L,,,±1(S) correspond au lien 30 bidirectionnel 1-41,,±1(N). Le noeud comporte plus précisément un processeur et un routeur La fonction du routeur R,,,, est d'orienter chaque paquet de données qu'il reçoit du processeur ou de l'une des quatre directions précitées vers le processeur ou l'une des quatre directions précitées, sachant que l'entrée doit être différente de la 35 sortie pour que le transfert des données ait un sens. De façon bien connue, le 3024310 8 processeur comporte une interface réseau 12,,,, apte à communiquer avec le routeur des éléments de traitement 14,,,, aptes à réaliser des opérations programmées de traitement de données, et une mémoire locale par exemple configurée en mémoire cache à un ou plusieurs niveaux. Il comporte en outre un 5 calculateur de régulation dynamique de débits de consigne, par exemple intégré fonctionnellement dans un module de contrôle de communication. De même, le noeud N,,J+1 comporte un processeur P,,,±1 et un routeur le processeur P,e, comportant une interface réseau 12,,,±1, des éléments de traitement une mémoire locale 16,e, et un calculateur 18,,,±1 de régulation dynamique de 10 débits de consigne ; le noeud N,+1,, comporte un processeur et un routeur le processeur comportant une interface réseau 12,4,p des éléments de traitement 14,,,,,, une mémoire locale 16,±1,, et un calculateur 18,±1,, de régulation dynamique de débits de consigne ; le noeud Ni+1,J+1 comporte un processeur Pi+1,J+1 et un routeur R,+1,J+1, le processeur Pi+1,J+1 comportant une interface réseau 12,±1,,±1, des éléments de 15 traitement 14,±1,,±1, une mémoire locale 16,±1,,±1 et un calculateur 18,±1,,±1 de régulation dynamique de débits de consigne. Parmi les noeuds du réseau sur puce, pour une configuration de routage et une activité données, certains sont des sources émettrices de paquets de données, d'autres sont des cibles réceptrices de ces paquets de données et tous remplissent 20 potentiellement une fonction de routage de paquets de données lorsqu'ils se trouvent sur leur trajet parcouru dans le réseau sur puce, c'est-à-dire lorsqu'ils se trouvent dans un canal de transmission point à point. Pour chaque canal de transmission point à point, c'est-à-dire pour chaque source de données, un débit de consigne doit être calculé et mis à jour pour être 25 ensuite appliqué par un limiteur de trafic. Ce calcul est réalisé par les calculateurs 18,,, de régulation dynamique de débits de consigne définis précédemment, de la façon suivante : pour chaque source émettrice de paquets de données, matérialisée par l'un des éléments de traitement définir une valeur initiale de son débit de 30 consigne, celle-ci pouvant être prédéfinie en mémoire et/ou nulle, pour chaque lien du réseau sur puce sollicité par la transmission de paquets de données, estimer une marge de débit disponible à répartir entre les sources actives non saturées dont le canal de transmission inclut ce lien, 3024310 9 - pour chaque source émettrice de paquets de données, calculer une mise à jour de son débit de consigne en fonction des marges de débits disponibles estimées pour les liens de son canal de transmission, et - répéter les deux étapes précédentes tant que les sources actives ne sont 5 pas toutes saturées. Comme indiqué précédemment, une source active saturée est une source qui a des paquets de données à émettre selon un débit de consigne imposé par le limiteur de trafic et dont au moins un lien sur son canal de transmission est saturé. Un lien saturé est avantageusement défini comme étant un lien qui n'a plus de marge de 10 débit disponible. En ce qui concerne les calculs effectués pour les sources, ils peuvent être faits par les calculateurs 18,,, de régulation dynamique de débits de consigne situés dans les mêmes noeuds que ces sources. En ce qui concerne les calculs effectués pour les liens, ils peuvent être faits 15 par les calculateurs 18,,, de régulation dynamique de débits de consigne situés en amont ou en aval de ces liens dans les canaux de transmission concernés. Pour mieux comprendre les calculs qui peuvent être faits au niveau de chaque lien, il convient de détailler la structure possible de chaque routeur du réseau du puce. Un exemple non limitatif d'une telle structure est illustré sur la figure 2. 20 Chaque lien bidirectionnel L,,,(N), L,,,(S), L,,,(E) vers un autre noeud du réseau est illustré avec un double flux entrant et sortant. Un lien supplémentaire L,,,(P) illustré sur cette figure représente le double flux entrant de et sortant vers le processeur Chaque paquet de donnés entrant par un lien ou provenant du processeur est orienté vers un module d'arbitrage de l'un des quatre autres liens 25 par un module de resynchronisation et redirection. Par ailleurs, chaque module d'arbitrage est précédé d'une mémoire tampon pour chaque flux arrivant et suivi d'une mémoire tampon de sortie. Ainsi, tout paquet de données arrivant par le lien L,,,(N) est orienté par un module de resynchronisation et redirection 20,,,(N) vers l'un des quatre autres liens L,,,(S), L,,,(E) ou L,,,(P) en fonction du canal de 30 transmission qu'il doit suivre, c'est à dire vers une mémoire tampon d'entrée du module d'arbitrage correspondant A,,,(S), A,,,(E) ou A,,,(P) (ce dernier n'étant pas illustré sur la figure 2 par souci de clarté du dessin). Tout paquet de données arrivant par le lien L,,,(S) est orienté par un module de resynchronisation et redirection 20,,,(S) vers l'un des quatre autres liens L,,,(N), L,,,(W), L,,,(E) ou L,,,(P), c'est à dire vers 35 une mémoire tampon d'entrée du module d'arbitrage correspondant A,,,(N), 3024310 10 A,,,(E) ou A,,,(P). Tout paquet de données arrivant par le lien L,,,(W) est orienté par un module de resynchronisation et redirection 20,,,(W) vers l'un des quatre autres liens L,,,(E) ou L,,,(P), c'est à dire vers une mémoire tampon d'entrée du module d'arbitrage correspondant A, J(N), A,,,(S), A, ;(E) ou A,,,(P). Tout paquet de 5 données arrivant par le lien L,,,(E) est orienté par un module de resynchronisation et redirection 20,,,(E) vers l'un des quatre autres liens L,,,(N), L,,,(W) ou L,,,(P), c'est à dire vers une mémoire tampon d'entrée du module d'arbitrage correspondant A,,,(N), A,,,(W) ou A,,,(P). Enfin, tout paquet de données arrivant par le lien L,,,(P) est orienté par un module de resynchronisation et redirection 20,,,(P) (non illustré sur la 10 figure 2 par souci de clarté du dessin) vers l'un des quatre autres liens L,,,(N), L,,,(W) ou L,,,(E), c'est à dire vers une mémoire tampon d'entrée du module d'arbitrage correspondant A,,,(N), A,,,(W) ou A,,,(E). Les modules d'arbitrage A,,,(N), , A; ;(E) et A, (P) fonctionnent par exemple selon le principe bien connu du Round-Robin. 15 Conformément à cette structure de chaque routeur R,,,, on comprend pourquoi chaque lien du réseau sur puce peut être considéré comme l'association d'une connexion physique point à point, entre deux noeuds voisins dans une certaine direction, et d'au moins une mémoire tampon (notamment soit la mémoire tampon de sortie du module d'arbitrage situé dans le noeud d'origine du lien, soit l'une 20 quelconque des mémoires tampons d'entrée des modules d'arbitrage situés dans le noeud de destination du lien). On comprend donc aussi pourquoi il est avantageux de prendre en considération non seulement la capacité de débit maximal du lien (liée à la capacité de sa connexion physique), mais également sa capacité d'absorption locale 25 maximale de dépassements sporadiques possibles des débits de consigne (liée à la capacité de sa ou ses mémoires tampons), lorsque l'on souhaite estimer la marge de débit disponible de ce lien pour une configuration de routage et des débits de consigne donnés. En effet, il a été montré dans l'article de Cruz précité que pour un débit de consigne donné, les dépassements sporadiques sont plafonnés à une valeur 30 seuil dépendante de ce débit de consigne, de sorte que l'on peut en tenir compte pour établir une marge entre cette valeur seuil et la capacité du lien à absorber les dépassements sporadiques de débits de consigne. Ainsi, conformément à l'invention, pour chaque lien lnk du réseau sur puce sollicité par la transmission de paquets de données, sa marge de débit disponible à 35 répartir est estimée à partir : 3024310 11 d'une première marge rcink calculée sur la base d'une capacité de débit maximal Cink du lien, cette première marge résultant par exemple d'une différence entre la somme des débits de consigne des canaux de transmission passant par ce lien et sa capacité de débit maximal, et 5 d'une deuxième marge rdink calculée sur la base d'une capacité d'absorption locale maximale, par mémoire tampon, de dépassements sporadiques possibles des débits de consigne des canaux de transmission passant par ce lien, cette deuxième marge résultant par exemple d'une différence entre une fonction des débits de consigne des canaux de 10 transmission passant par ce lien et sa capacité d'absorption locale maximale. En ce qui concerne la première marge rcink, si l'on note CCInk l'ensemble des canaux de transmission ch qui incluent le lien Ink, Pch les valeurs courantes des débits de consigne de ces canaux de transmission et c une constante de marge résiduelle 15 en dessous de laquelle on considère que la marge de débit disponible à répartir est nulle, alors elle peut être définie de la façon suivante : rcink = Clnk - E - 1 Pch (1) chEccink En ce qui concerne la deuxième marge rdink, on montre qu'elle peut prendre la forme similaire suivante : rdink = BFink - E - f ({Pch, ch E CCInk I) (2) Dans cette équation, BFInk est une valeur de capacité d'absorption locale 20 maximale propre au lien Ink et dépendante de la taille de la mémoire tampon qui lui est associée (dépendante elle-même des mémoires tampons des routeurs comme cela a été vu en référence à la figure 2), mais également dépendante d'autres paramètres du réseau sur puce tels que la longueur maximale des paquets de données transitant dans le réseau et le nombre de flux contributeurs sur le lien Ink. 25 Dans cette équation également, f (tpch, ch E CC/na est l'expression générale d'une fonction à déterminer de l'ensemble des valeurs des débits de consigne des canaux de transmission passant par le lien Ink. Cette expression dépend notamment de la discipline d'arbitrage choisie, de la régulation de débit à la source choisie et d'autres paramètres du réseau sur puce. 30 On montre en particulier qu'elle prend une forme linéaire lorsque la discipline d'arbitrage choisie est de type « work conserving », c'est-à-dire lorsque l'émission 3024310 12 d'une source de trafic éligible reste inactive seulement quand sa file d'entrée est vide. Dans ce cas, l'expression de la deuxième marge rdink devient plus simplement : rdlnk = BFInk E Dch,Ink Pch (3) chEccink Dans cette équation, chaque valeur Dch,Ink est un coefficient à déterminer résultant lui-même d'une somme de coefficients propres à tous les liens situés en 5 amont du lien lnk dans l'ensemble CCInk. A titre d'exemple non limitatif, un calcul de BFInk et des coefficients Dch,Ink va maintenant être détaillé, dans le cas d'une régulation de débit à la source par fenêtre glissante. Lorsque la discipline d'arbitrage est « work conserving », il est connu que 10 l'inégalité suivante doit être vérifiée : (ach + )dix* ' Pch QSIZE ChECCInk IERRch,Ink (4) Dans cette inégalité, Pch est la valeur seuil de plafonnement des dépassements sporadiques possibles compte tenu du débit de consigne Pch du canal de transmission ch, telle qu'enseignée dans l'article de Cruz précité. Dans cette inégalité également, FIRch,Ink est l'ensemble des liens traversés en 15 amont du lien lnk dans le canal de transmission ch, QSIZE est la taille de la mémoire tampon associée au lien lnk et die, est un coefficient calculé de la façon suivante : di,ch = (ncli- 1) - PSIZE (5) Dans cette équation, ncli est le nombre de directions contributrices sur la mémoire tampon associée au lien I et PSIZE est la taille maximale des paquets de données exprimée dans la même unité que QSIZE (i.e. flits, bytes ou autres). 20 Dans le cas particulier d'une régulation de débit à la source par fenêtre glissante, le régulateur respecte le débit de consigne pch sur une fenêtre glissante de longueur Tw en limitant le nombre d'unités de paquets de données (i.e. flits, bytes ou autres) avec un débit instantané maximal d'injection de valeur constante notée DMAX. On montre que l'expression Y -chEccink ach de l'inégalité (4) prend alors la forme 25 suivante : ach Pch' (1 Pch (6) DMAX) Tw ChECCInk ChECCInk Cette expression n'est pas linéaire en pch. Néanmoins, en notant Nink le nombre de sources contributrices au lien lnk, c'est-à-dire le nombre de canaux de transmission passant par le lien lnk, ou autrement dit le nombre d'éléments ch dans 3024310 13 l'ensemble CCInk, on peut astucieusement la simplifier en remarquant que la borne supérieure de l'expression (6) est atteinte lorsque V ch, Pch = NSink DMAX On obtient : Sup ( 1 a- ch - c chECCink hEccink Pch 7 DMAX\ 1 Nink Tw DMAX/ (Nink - 1) DMAX - Tw (7) DMAX NInk IVInk L'inégalité (4) peut ainsi être avantageusement remplacée par une inégalité plus contraignante mais linéaire en pch : (N1nk - 1) di,ch - Pch QSIZE DMAX - Tw (8) NInk ChECCink IERRch,Ink 5 En notant : BFInk = QSIZE (NInk -1) DMAX - Tw (9) et Dch,Ink = 1 Nink di,* , (10) LERRch,lnk on obtient l'inégalité : Dch,lnk . Pch REVENDICATIONS1. Procédé de régulation dynamique de débits de consigne de sources émettrices de paquets de données vers des cibles réceptrices de ces paquets de données dans un réseau sur puce (10) comportant une pluralité de noeuds (N,,,), parmi lesquels se trouvent les sources et les cibles, et une pluralité de liens (L,,,(N), L,,,(E)) entre ces noeuds pour la transmission des paquets de données, comportant : pour chaque lien du réseau sur puce sollicité par la transmission des paquets de données, l'estimation (110) d'une marge de débit disponible incluant l'estimation (1121, ..., 112ink, 112k) d'une première marge calculée sur la base d'une capacité de débit maximal (Cink) du lien, pour chaque source émettrice d'au moins un paquet de données, le calcul et l'application (120) d'une mise à jour de son débit de consigne en fonction des marges de débits disponibles estimées, caractérisé en ce que l'estimation (110) de la marge de débit disponible pour chaque lien comporte en outre : l'estimation (1141, ..., 114ink, - - -, 1140 d'une deuxième marge calculée sur la base d'une capacité d'absorption locale maximale (BFInk), par mémoire tampon, de dépassements sporadiques possibles des débits de consigne, la détermination (1161, ..., 116ink, 116L) d'une valeur de la marge de débit disponible en fonction des première et deuxième marges calculées. 2. Procédé de régulation dynamique de débits de consigne selon la revendication 1, dans lequel, pour une configuration de routage donnée incluant un ensemble de canaux de transmission des paquets de données entre les sources et les cibles, les étapes d'estimation (110) des marges de débits disponibles et de calcul (120) de mises à jour des débits de consigne sont exécutées uniquement pour des canaux de transmission non saturés, c'est-à-dire des canaux de transmission n'ayant encore aucun lien sans marge de débit disponible, et répétées jusqu'à ce que tous les canaux de transmission soient saturés. 3. Procédé de régulation dynamique de débits de consigne selon la revendication 2, dans lequel : 3024310 33 - l'estimation (1121, ..., 112ink, - - -, 1120 de la première marge notée « rcink » pour chaque lien noté « lnk », calculée sur la base de la capacité de débit maximal du lien notée « Cink », est effectuée sur la base de l'équation suivante : rcInk = Clnk E Pch chECCink 5 dans laquelle c est une constante de marge résiduelle en dessous de laquelle on considère que la marge de débit disponible est nulle pour ce lien, CCInk est l'ensemble des canaux de transmission notés « ch » qui incluent le lien lnk et pch désigne le débit de consigne du canal de transmission ch, et - 10 l'estimation (1141, ..., 114ink, - - ., 114k) de la deuxième marge notée « rdink » pour chaque lien lnk, calculée sur la base de la capacité d'absorption locale maximale du lien notée « SFInk », est effectuée sur la base de l'équation suivante : chEccink dans laquelle Dch,ink désigne un coefficient prédéterminé propre à chaque lien de chaque canal de transmission. 15 4. Procédé de régulation dynamique de débits de consigne selon la revendication 3, dans lequel la régulation de débit étant faite à la source par fenêtre glissante selon une discipline d'arbitrage de type « work conserving » : - la capacité d'absorption locale maximale de chaque lien lnk est définie par l'équation suivante : (Nink - 1) BFink = QSIZE DMAX - Tw , NInk 20 dans laquelle QSIZE est la taille de la mémoire tampon associée au lien lnk, Nink est le nombre de canaux de transmission passant par le lien lnk, DMAX est une constante de débit instantané maximal d'injection et Tw est la longueur de la fenêtre glissante, et - chaque coefficient Dch,ink est défini par l'équation suivante : IERRch,lnk 25 dans laquelle FIRch,Ink est l'ensemble des liens traversés en amont du lien lnk dans le canal de transmission ch, « I » désignant l'un de ces liens, et est un coefficient défini par di,ch = (ncli - 1) - PSIZE, où ncli est le nombre de directions contributrices rdlnk = BFInk E Dch,Ink Pch Dch,Ink = dl,ch 3024310 34 sur la mémoire tampon associée au lien I et PSIZE est la taille maximale des paquets de données exprimée dans la même unité que QSIZE. 5. Procédé de régulation dynamique de débits de consigne selon l'une quelconque des revendications 1 à 4, dans lequel les étapes d'estimation (110) des 5 marges de débits disponibles et de calcul (120) de mises à jour des débits de consigne sont exécutées de façon séquentielle, cette séquence étant elle-même exécutée de façon itérative. 6. Procédé de régulation dynamique de débits de consigne selon la revendication 5, dans lequel les étapes d'estimation (110) des marges de débits 10 disponibles et de calcul (120) de mises à jour des débits de consigne sont séquentiellement exécutées à l'aide de barrières de synchronisation (CL1, CL2, CL3, CL4, CS1, CS2) implémentées sous la forme de décompteurs de messages (34, 46) pour chaque lien du réseau sur puce sollicité par la transmission des paquets de données et pour chaque source émettrice d'au moins un paquet de données. 15 7. Procédé de régulation dynamique de débits de consigne selon l'une quelconque des revendications 1 à 4, dans lequel les étapes d'estimation (110) des marges de débits disponibles et de calcul (120) de mises à jour des débits de consigne sont exécutées de façon incrémentielle et entrelacée par une sérialisation de messages de régulation dynamique des débits de consigne selon des chemins 20 prédéfinis. 8. Procédé de régulation dynamique de débits de consigne selon l'une quelconque des revendications 1 à 7, dans lequel la valeur de marge de débit disponible est déterminée (1161, ..., 116ink, 116k) pour chaque lien en tant que minimum entre les première et deuxième marges calculées pour ce lien. 25 9. Programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions pour l'exécution des étapes d'un procédé de régulation dynamique de débits de consigne selon l'une quelconque des revendications 1 à 8, lorsque ledit programme est exécuté sur un 30 ordinateur. 10. Dispositif de traitement de données à réseau sur puce (10), comportant : une pluralité de noeuds (N,,,), parmi lesquels se trouvent des sources émettrices de paquets de données et des cibles réceptrices de ces paquets de données, 3024310 35 une pluralité de liens (L,,,(N), L,,,(S), L,,,(E)) entre ces noeuds pour la transmission des paquets de données, et des calculateurs (36, 48 ; 70, 72, 82) de régulation dynamique de débits de consigne des sources, répartis entre les noeuds du réseau 5 sur puce et programmés pour : - pour chaque lien du réseau sur puce sollicité par la transmission des paquets de données, estimer une marge de débit disponible en estimant une première marge calculée sur la base d'une capacité de débit maximal (Cink) du lien, 10 - pour chaque source émettrice de paquets de données, calculer une mise à jour de son débit de consigne (Pch,i) en fonction des marges de débits disponibles estimées, caractérisé en ce que chaque calculateur (36 ; 70, 72) programmé pour estimer la marge de débit disponible de l'un quelconque des liens est en outre programmé 15 pour : estimer une deuxième marge calculée sur la base d'une capacité d'absorption locale maximale (BFInk), par mémoire tampon, de dépassements sporadiques possibles des débits de consigne, déterminer une valeur de la marge de débit disponible en fonction 20 des première et deuxième marges calculées.