Brevet FR2721727A1 — publié le 19951229

BYSTEMZ DE ROUTAGE DE PAQUETS DE DONNES DANS UN RESEAU D'ORDINATEUR MASSIVEMENT PARALLELE ET CIRCUIT DE ROUTAGE D'UN NOEUD CONSTITUTIP DUDIT RESEAU L'invention concerne un système de routage de paquets de données dans un réseau d'ordinateur massivement parallèle et un circuit de routage d'un noeud constitutif dudit réseau. Un réseau d'ordinateur massivement parallèle est constitué par une multitude de noeuds chacun constituant un ordinateur local. De façon idéale chacun de ces noeud devrait être connecté à tous les autres afin d'optimiser au maximum les communications entre les noeuds, cependant un tel dispositif serait d'un court prohibitif pour des ordinateurs massivement parallèles ayant un nombre conséquent de noeuds. Pour obvier au problème de coût, les noeuds sont organisés en réseau, un noeud n'étant connecté qu'à un nombre limité de ses semblables. De ce fait les messages ou paquets de données transmis par un noeud sont forcés de voyager par des noeuds intermédiaires jusqu'à leur noeud de destination. Cela a pour conséquence la possible création de situations d'interblocage des messages ou paquets de données. Un noeud est bloqué si le noeud suivant (ou les noeuds suivants si plusieurs chemins sont possibles) est déjà occupé par un autre paquet. C'est la dépendance circulaire sur la libération des noeuds qui crée des situations d'interblocage. Pour remédier à ces situations d'interblocage, il a été développé des systèmes de routage adaptatifs fondés sur la technique des réseaux virtuels tels qu'ils préviennent les situations d'interblocage possibles dans le réseau. La technique des réseaux virtuels consiste à décomposer le réseau en un certain nombre de sous-réseaux (réseaux virtuels) qui sont autant de "feuillets" effectuant un routage de paquets indépendamment les uns les autres. Notamment chaque réseau virtuel possède son propre lot de mémoire tampon capable de stocker les paquets en cours de routage. L'ensemble des réseaux virtuels partagent par contre les mêmes liens physiques inter-noeuds sur lesquels les transferts des divers réseaux virtuels sont multiplexés dans le temps.Les situations d'interblocage sont éliminées en imposant des restrictions sur le mouvement des paquets dans les sous-réseaux de telle sorte que d'une part, il n'y ait pas de boucle de dépendance circulaire à l'intérieur de chaque sous-réseau ; et que d'autre part, l'ensemble des mouvements possibles en combinant ceux qui sont possibles dans chaque sous-réseau recouvre tous ceux possibles dans le réseau réel. Routage adaptatif signifie que le chemin pour transporter un paquet d'un noeud à un autre n'est pas imposé et, non seulement peut être différent d'un cas à l'autre, mais aussi s'adapte dynamiquement en fonction de l'engorgement des différents noeuds pouvant être traversés. Le routage peut être plus ou moins adaptatif suivant les contraintes que l'on impose au chemin - le routage le moins adaptatif dit routage forcé consiste à imposer d'abord un déplacement suivant un axe et ensuite suivant l'autre. - Dans le type de routage objet de l'invention, les contraintes sont que le chemin est quelconque, mais les paquets doivent toujours progresser d'une manière qui les rapproche de leur destination. - D'autres systèmes encore plus adaptatifs permettent aux paquets de revenir en arrière en cas d'engorgement en aval ou de défection d'anneaux intermédiaires. D'un point de vue pratique, plus le système est adaptatif, plus il est performant et robuste. Cependant, plus le système est adaptatif, plus il faut un nombre élevé de canaux virtuels pour éliminer les situations d'interblocage. Dans un réseau bidimensionnel de type torique avec rebouclage aux frontières dans les deux dimensions, un système de routage adaptatif du deuxième type cité plus haut c'est-à-dire un système de routage adaptatif "sans marche arrière" comprend des moyens pour éliminer les situations d'interblocage liées à la présence de boucles circulaires dans le plan desdits sous-réseaux, des moyens pour éliminer les situations d'interblocage liées à la présence de boucles dans la fermeture torique, et des moyens pour éliminer les situations d'interblocage liées à la présence de boucles d'aller-retour lorsqu'un paquet de données doit effectuer un aller-retour. Lesdits moyens pour éliminer les situations d'interblocage liées à la présence de boucles circulaires dans le plan comprennent un routage adaptatif ayant des quadrants directionnels virtuels, chaque quadrant ayant une direction privilégiée différente et définissant une série de réseaux virtuels associés dans lesquels le message ou paquet de données suivra la direction privilégiée. Ces moyens comprennent en outre des moyens pour déterminer et imposer le quadrant directionnel virtuel qui offre le chemin le plus court entre le noeud émetteur et chaque noeud récepteur. Chaque quadrant directionnel virtuel correspondant à un ensemble de directions au sens classique. Les paquets sont triés en fonction des signes de leur déplacement en X et en Y à effectuer pour rejoindre leur destination. Si l'un des déplacements est nul ou si les deux sont nuls, le choix est fait de manière arbitraire mais définitif durant le routage. Chaque quadrant est caractérisé par sa direction moyenne mais toutes les directions dans un intervalle angulaire donné sont dans le même quadrant. Dans chaque direction privilégiée, les moyens pour éliminer les situations d'interblocage liées à la présence de boucles dans la fermeture torique comprennent un routage adaptatif ayant des niveaux toriques virtuels successifs, chaque niveau torique étant associé à un réseau virtuel différent et distinct des autres; et des moyens pour faire passer un paquet de données d'un premier réseau virtuel d'un premier niveau torique à un deuxième réseau virtuel du niveau torique supérieur dès que ledit paquet franchit une des frontières. Si N représente le nombre de niveaux toriques et Q le nombre de quadrants, le nombre de réseaux virtuels est de N x Q. Lesdits moyens pour éliminer les situations d'interblocage liées à la présence de boucles aller-retour comprennent un routage adaptatif à deux séries de réseaux virtuels, l'une réservée aux allers, l'autre réservée aux retours soit au total 2 x N x Q réseaux virtuels à implémenter physiquement sur chaque circuit de routage de chaque noeud du réseau bidimensionnel. L'un des buts de la présente invention est de proposer un système de routage adaptatif tel que décrit cidessus dans lequel le nombre de réseaux virtuels à implémenter sur chaque circuit de routage de chaque noeud du réseau bidimensionnel est inférieur à 2 x N x Q. A cet effet l'invention concerne un système de routage tel que décrit ci-dessus, le réseau bidimensionnel étant de forme générale rectangulaire d'axe perpendiculaire X, Y à maille carrée, les bordures opposées étant connectées entre elles. Le système de routage comprend - des quadrants directionnels virtuels ayant chacun une direction privilégiée - des moyens pour déterminer quelle direction privilégiée offre le chemin le plus court entre lesdits noeuds - chaque quadrant directionnel virtuel définissant des frontières toriques et comprenant des niveaux toriques; - chaque niveau torique correspondant à un réseau virtuel distinct - des moyens pour détecter quand le paquet franchit une des frontières toriques et des moyens pour faire passer le paquet d'un réseau virtuel de niveau torique donné au réseau virtuel de niveau torique supérieur dès qu'un franchissement est détecté. Selon l'invention, chaque réseau virtuel comprend une zone de noeuds dits actifs, c'est-a-dire susceptibles d'être effectivement utilisés pour router le paquet considéré, et une zone de noeuds inactifs dans laquelle le paquet considéré ne doit pas circuler; les parties inactives de certains réseaux virtuels constituant les parties actives d'autres réseaux virtuels et vice versa. Selon l'invention, le réseau bidimensionnel étant de forme générale rectangulaire d'axe perpendiculaire X, Y, les bordures opposées étant connectées entre elles, le système de routage comprend - quatre quadrants directionnels virtuels, lesdites directions privilégiées étant opposées deux à deux - chaque quadrant directionnel virtuel comprenant un niveau torique de base et un premier et un deuxième niveau torique, chacun correspondant à un réseau virtuel distinct ; - à savoir respectivement un réseau de base, un premier et un deuxième réseau - les noeuds actifs dans chaque réseau virtuel de base représentent la totalité du réseau bidimensionnel réel; - les noeuds actifs dans chaque premier réseau représentent la réunion des deux moitiés de réseau virtuel de base issues des frontières toriques dans les directions X, Y, c'est-à-dire les trois quarts du réseau bidimensionnel réel;; - les noeuds actifs dans chaque deuxième réseau représentent l'intersection des deux moitiés de premier réseau issues des frontières toriques dans les directions X, Y, c'est-à-dire un quart du réseau bidimensionnel réel. direction opposée, lesdits deux réseaux virtuels étant réunis en un réseau virtuel mixte unique de la taille du réseau bidimensionnel réel. L'invention concerne aussi un circuit de routage implémentant le système de routage décrit ci-dessus L'invention sera mieux comprise par la description qui va suivre en référence aux dessins annexés dans lesquels La figure 1 représente une vue schématique d'un réseau bidirectionnel à maille carrée dans lequel un système de routage selon l'invention est mis en oeuvre. Les figures 2A, 2B, 2C, 2D représentent une vue schématique des quatre quadrants directionnels ayant chacun trois niveaux toriques selon l'invention. La figure 3 représente une vue schématique partielle d'un circuit de routage selon l'invention Le système de routage adaptif de paquets de données dans un réseau 1 bidimensionnel de type torique comportant une multitude de noeuds 100 comprend, selon l'invention, des moyens pour éliminer les situations d'interblocage liées à la présence de boucles circulaires dans le plan dudit réseau 1, des moyens pour éliminer les situations d'interblocage liées à la présence de boucles dans la fermeture torique, et des moyens pour éliminer les situations d'interblocage liées à la présence de boucles d'aller-retour lorsqu'un paquet de données doit effectuer un aller-retour. Le réseau bidimensionnel étant de forme générale rectangulaire d'axe perpendiculaire X, Y à maille carrée, les bordures opposées étant connectées entre elles. Le système de routage comprend - des quadrants directionnels virtuels ayant chacun une direction privilégiée 2a, 2b, 2c, 2d; - des moyens pour déterminer quelle direction privilégiée 2a, 2b, 2c, 2d offre le chemin le plus court entre les noeuds émetteurs et récepteurs; - chaque quadrant directionnel virtuel définissant des frontières toriques 3X, 3Y et comprenant des niveaux toriques, chacun correspondant à un réseau virtuel distinct 4a, 4b, 4c; - des moyens pour détecter quand le paquet franchit une des frontières toriques 3X, 3Y et des moyens pour faire passer le paquet d'un réseau virtuel 4a, 4b, 4c de niveau torique donné au réseau virtuel 4b, 4c de niveau torique supérieur dès qu'un franchissement est détecté. Dans le mode de réalisation représenté sur les figures, le système de routage est utilisé pour un réseau bidimensionnel X, Y réel 1 à mailles carrées de type torique avec rebouclage aux frontières X, Y (fig 1). Les quadrants directionnels virtuels sont au nombre de quatre définissant quatre directions privilégiées 2a, 2b, 2c, 2d à savoir respectivement -X,+Y ; +X,+Y ; -X,-Y ; +X,-Y codées sur deux bits Sx et Sy par exemple respectivement 10, 00, 11, 01. Chaque quadrant a des frontières toriques associées 3X, 3Y. Toutes les directions à plus ou moins 45" autour d'une direction privilégiée 2a, 2b, 2c, 2d appartiennent au quadrant de ladite direction privilégiée considérée. Les niveaux toriques de chaque quadrant sont au nombre de trois, à savoir un niveau torique de base NO, un premier niveau torique N1 et un deuxième niveau torique N2, chacun correspondant respectivement à un réseau virtuel de base 4a, un premier réseau virtuel 4b, et un deuxième réseau virtuel 4c. Du fait des symétries existant dans la forme torique et des moyens qui déterminent et imposent le chemin le plus court, si un paquet de données ou un message franchit une frontière torique il n'effectuera pas, dans le réseau virtuel supérieur dans lequel il passe, un chemin plus long que la moitié de la taille dans les directions X et Y du réseau virtuel dans lequel il était. Si tel n'était pas le cas, cela voudrait dire que le quadrant choisi n'était pas celui qui offrait le plus court chemin entre le noeud émetteur et le noeud récepteur. Ainsi chaque réseau virtuel 4a, 4b, 4c de la taille du réseau réel 1 comprend une zone 5 de noeuds 100 actifs, c'est- -dire susceptible d'être effectivement utilisé pour router le paquet considéré, et une zone 6 de noeuds 100 inactifs dans laquelle le paquet considéré ne doit pas circuler. Les deux zones sont complémentaires. - la zone 5 des noeuds actifs dans chaque réseau virtuel de base 4a représente la totalité du réseau bidimensionnel réel 1; - la zone 5 des noeuds actifs dans chaque premier réseau virtuel 4b représente la réunion des deux moitiés de réseau virtuel de base 4a issues des frontières toriques 3X, 3Y dans les directions X, Y, c'est-à-dire les trois quarts du réseau bidimensionnel réel 1; - la zone 5 des noeuds actifs dans chaque deuxième réseau virtuel représente la réunion des deux moities de premier réseau 4b issues des frontières toriques 3X, 3Y dans les directions X, , c'est-à-dire un quart du réseau bidimensionnel réel 1. Du fait de ce qui précède la zone active 5 d'un premier réseau virtuel 4b d'un quadrant directionnel virtuel de direction donnée 2a, 2b, 2c, 2d correspond à la zone inactive 6 du deuxième réseau virtuel 4c du quadrant directionnel virtuel de direction opposée 2d, 2c, 2b, 2a, lesdits deux réseaux virtuels 4b et 4c étant réunis en un réseau virtuel actif mixte unique de la taille du réseau bidimensionnel réel 1. Le système de routage selon l'invention comprend donc quatre réseaux virtuels de base aller, quatre réseaux virtuels de base retour, quatre réseaux virtuels mixtes aller, et quatre réseaux virtuels mixtes retour, soit seize réseaux chacun repéré par un numéro de réseau virtuel actif compris entre 0 et 15. Dans l'art antérieur un tel réseau bidimensionnel avec un système de routage présentant les memes moyens aurait nécessité 2 x Q=4 x N=3 = 24 réseaux virtuels au lieu des seize nécessaires selon la présente invention. Le système de routage selon l'invention comprend par exemple - des moyens pour détecter le premier ou le deuxième franchissement d'un paquet dans un quadrant directionnel virtuel de direction donnée 2a, 2b, 2c, 2d; et dans le cas d'un deuxième franchissement - des moyens pour déterminer le quadrant directionnel virtuel de direction opposée 2d, 2c, 2b, 2a, et des moyens pour faire passer le paquet concerné dans le réseau virtuel mixte correspondant au premier niveau torique N1 dudit quadrant virtuel de direction opposée 2d, 2c, 2b, 2a. Avantageusement les quadrants directionnels virtuels étant codés sur deux bits Sx et Sy, le niveau torique de base NO et le premier niveau torique N1 étant codés sur un bit T1, l'aller et le retour étant codés sur un bit Rt, ledit système comprend des moyens de calcul pour calculer le numéro de réseau virtuel actif selon la formule: 8 x Rt + 4 x Sy + 2 x Sx + Tl lorsque l'on est dans un niveau torique de base NO ou que l'on passe dans un premier niveau torique, et selon la formule 8 x Rt ; 4 x (1 - Sy) + 2 x (1 - Sx) + 1 lorsque l'on passe dans un deuxième niveau torique. Un paquet de données ou message ne change de réseau virtuel que lorsqu'il franchit une frontière torique. Dans ce cas, il passe dans le niveau torique immédiatement supérieur mais reste toujours dans le même quadrant directionnel. Dans le cas d'un aller-retour, le paquet de données ou message est extrait du réseau puis il est réinjecté. A cette occasion, il change de réseau virtuel aller-retour, de quadrant directionnel, et éventuellement de niveau torique. Pour permettre 'a mise en oeuvre du système de routage tel que décrit ci-dessus chaque noeud du réseau doit comprendre un circuit de routage selon l'invention. Chacun de ces circuits de routage doit implémenter les seize réseaux virtuels. A cet effet chaque circuit de routage comprend - cinq connexions 10a, 10b, soit quatre 10a associées aux quatre circuits de routage du réseau les plus proches, et une 10b connectée localement à une unité d'interface 101 avec le processeur de travail local ; - une pluralité de tampons 11 et de sélecteurs "cross-bar" 12 pour mettre en oeuvre le système de routage à réseau virtuel - des contrôleurs de priorité 13, 15 pour gérer les déplacements des paquets de données dans le circuit de routage et/ou en sortie dudit circuit. Le circuit comprend en outre - des circuits logiques pour les synchronisations et les interruptions réseau - des circuits logiques de test et d'initialisation - des circuits logiques de contrôle ; et - un système de sauvegarde et de restauration automatique de tous les tampons. Dans le mode de réalisation décrit, le paquet de données ou le message comprend au moins une en-tete contenant au moins les informations suivantes - la longueur du paquet de données sans l'en-tête - les instructions pour le noeud de destination - un bit de copie locale du paquet de données - le bit Rt d'aller-retour - la distance dx restant à couvrir en X jusqu'au noeud de destination - la distance dy restant à couvrir en Y jusqu'au noeud de destination - les bits Sx et Sy de direction privilégiée - le bit Tl de niveau torique. Du fait de la décomposition en quadrant, chaque noeud actif de chaque réseau virtuel a seulement trois entrées, à savoir une entrée en X (+ ou - X) relative à Sx, une entrée en Y (+ ou - Y) relative à Sy, et une entrée en local. De ce fait le circuit de routage comprend seize sélecteurs "cross-bar" trois entrées - trois sorties 12, chacun d'entre eux étant destiné à un réseau virtuel du système de routage, deux des trois entrées et deux des trois sorties correspondant aux deux directions X,Y dans le plan, la troisième entrée et la troisième sortie correspondant à la direction locale vers l'unité d'interface. Un contrôleur de priorité 13 est associé à chaque sélecteur "cross-bar" 12 pour décider quelles entrées sont connectées à quelles sorties. En outre chaque sélecteur 12 "cross-bar" 3 x 3 comprend trois tampons 11, un pour chaque direction, pour stocker les paquets de données, si, à un temps donné, il est impossible d'effectuer le routage. Du fait que tous les réseaux virtuels partagent les meme liens physiques 16 inter-noeud, les sorties des sélecteurs 12 / contrôleurs 13 sont connectées aux ports de sortie 10a", 10b" des connexions 10a, 10b à travers une des entrées d'un multiplexeur 14 (seize entrées/ une sortie). Chacun de ces cinq multiplexeurs 14 est associé à un contrôleur de priorité 15 décidant lequel des réseaux virtuels doit utiliser, à un temps donné, le lien physique 16 qui lui est associé. La figure 3 représente une vue partielle d'un circuit de routage selon l'invention où seuls deux réseaux virtuels ont été implémentés afin de ne pas surcharger la figure. Pour un réseau virtuel donné, chacune des entrées des trois tampons 11 est connectée aux ports d'entrée 10a', 10b' des connecteurs 10a, 10b de direction X, Y, ou locale qui lui est associée ; chacune des sorties des trois tampons 11 est connectée à une entrée du sélecteur cross- bar" 12/contrôleur 13; chacune des sorties du sélecteur "cross-bar" 12/contrôleur 13 est connectée aux ports de sortie des connexions de direction X, Y, ou locale qui lui est associée à travers une entrée d'un multiplexeur (seize entrées/une sortie) 14/contrôleur 15. Le paquet de données ou message arrive donc d'un des noeuds voisins ou de l'interface locale par un lien physique 16 à travers la connexion 10a, 10b associée, puis est envoyé simultanément aux seize tampons 11 associés à ladite connexion, les tampons 11 ayant chacun des moyens pour reconnaître si le paquet lui est adressé, puis le paquet est, en sortie du tampon du réseau virtuel concerné, transmis au sélecteur 12/contrôleur 13 du réseau virtuel concerné qui décide et sélectionne la direction de sortie du paquet, puis le paquet, en sortie du sélecteur 12/contrôleur 13, dans la direction sélectionnée et décidée, arrive sur le multiplexeur 14/contrôleur 15 qui décide a quel moment le lien physique de sortie du paquet pourra être affecté au réseau virtuel concerné. Un lien physique est affecté à un réseau virtuel donné lorsque le réseau virtuel est actif dans les deux noeuds connectés par ce lien. Cette règle est adaptée aux frontières toriques lorsque un paquet change de réseau virtuel. Un mouvement élémentaire (entre deux noeuds adjacents) est autorisé par le système de routage - si le tampon source est plein (ou commence à se remplir), et - si le tampon destination est vide (ou commence à se vider), et - si le lien physique est affecté au réseau virtuel concerné. A cet effet, dans chaque circuit, un bit d'état est associé à tous les tampons destination possibles. Ce bit informe que le tampon destination n'est pas vide. Les bits d'état sont mis à 0 en même temps que la réinitialisation des circuits (tous les tampons sont initialement vides). Les opérations sur les bits d'état concernent trois circuits - le circuit-source, qui envoie le paquet, - le circuit-destination, qui reçoit le paquet, - le circuit en amont du circuit-source. Les bits d'état se trouvent dans les circuitssources et contiennent l'état des tampons dans les circuits destination. Donc lorsqu'un paquet est envoyé du circuit-source vers le circuit-destination - le circuit-source doit mettre à 1 le bit d'état du tampon correspondant dans le circuit-destination; - le circuit en amont doit mettre à zéro le bit d'état correspondant au tampon du circuit-source qui vient d'être libéré. A cet effet, le circuit-source doit envoyer physiquement un accusé de réception au circuit en amont pour l'informer de cette libération. Dans le mode de réalisation décrit, les liens physiques 16 sont composés de deux bus 16 bits parallèles, unidirectionnels et réciproques, l'un 16a étant en entrée, l'autre 16b en sortie. Une des autres caractéristiques des circuits de routage selon l'invention est qu'ils disposent chacun d'un dispositif de contrôle d'injection de paquets de données ou de messages. Lorsqu'un réseau est engorgé, ses performances diminuent sensiblement. Plus précisément, lorsque le taux d'occupation du réseau (nombre de paquets de données ou messages en circulation dans le réseau) augmente, le débit des messages ou paquets de données au sein- du réseau varie. Dans un premier temps, le débit augmente à peu près proportionnellement au taux d'occupation de 0 jusqu'à une valeur maximale. Cette valeur maximale correspond à la valeur optimale du taux d'occupation. Au delà de cette valeur, le débit chute brutalement d'un facteur important (jusqu'à 2 ou 3). Une solution pour optimiser le débit de paquets de données ou de messages dans le réseau et ainsi d'éviter les engorgements, est de contrôler et de maintenir le taux d'occupation à la valeur optimale. La solution proposée par la présente invention consiste à limiter le taux d'injection (rapport entre le nombre de paquets de données ou messages effectivement envoyés dans le réseau et le nombre maximal que pourrait envoyer le lien physique entre le circuit d'interface 101 et le circuit de routage) de chaque noeud. Cette limitation intervient uniquement au niveau du lien physique local entre le circuit de routage et le circuit d'interface. Le dispositif de contrôle d'injection selon l'invention a pour but de limiter l'injection au niveau du circuit d'interface directement en fonction du taux d'occupation du circuit de routage qui lui est connecté. A cet effet, le circuit de routage comporte un dispositif de comptage de paquets. Un compteur/décompteur, initialisé à 0, est incrémenté chaque fois qu'un paquet entre dans le circuit de routage et décrémenté chaque fois qu'un paquet en sort. Un comparateur permet de savoir si le nombre de paquets est ou n'est pas inférieur au seuil optimal. Cette information est transmise au circuit d'interface. En fonction de cette information, le circuit d'interface autorise ou non l'injection de nouveaux paquets de données ou de messages. Ce dispositif permet un contrôle de l'injection des paquets qui s'adaptent dynamiquement à la charge du réseau. Bien sur, le contrôle n'est que local, les décisions d'injection se font au niveau de chaque circuit d'interface en fonction du taux d'occupation du seul circuit de routage qui lui est connecté. Mais comme les paquets de données ou messages circulent librement (sans délimitation) dans le réseau, la charge d'occupation s'équilibre automatiquement et l'injection est effectivement contrôlée globalement en fonction du taux d'occupation du réseau complet. De plus, on peut facilement ajuster le seuil par noeuds de réseau de telle sorte que le débit de paquets de données ou messages dans le réseau soit très proche du débit maximal sans que ce seuil ne dépende du type de communication (local ou longue distance, régulière ou irrégulière). Le circuit de routage sur l'invention comporte l'implémentation physique de 16 réseaux virtuels comprenant chacun 3 tampons (soit 48 tampons en tout), la définition élémentaire de la valeur seuil est donc 1/48ème. REVENDICATIONS 1. Système de routage adaptatif de paquets de données suivant des chemins de routage dans un réseau (1) d'ordinateur massivement parallèle, comprenant des moyens pour éliminer les situations d'interblocage liées à la présence de boucles circulaires dans le plan dudit réseau (1), des moyens pour éliminer les situations d'interblocage liées à la présence de boucles dans la fermeture torique, et des moyens pour éliminer les situations d'interblocage liées à la présence de boucles d'aller-retour lorsqu'un paquet de données doit effectuer un aller-retour, le réseau (1) étant bidirectionnel de forme générale rectangulaire d'axe perpendiculaire X, Y, les bordures opposées étant connectées entre elles, le système de routage comprenant - des quadrants directionnels virtuels ayant chacun une direction privilégiée (2a, 2b, 2c, 2d) - des moyens pour déterminer quelle direction privilégiée offre le chemin le plus court entre des noeuds émetteurs et de noeuds récepteurs - chaque quadrant directionnel virtuel définissant des frontières toriques 3X, 3Y et comprenant des niveaux toriques; - chaque niveau torique correspondant à un réseau virtuel (4a, 4b, 4c) - des moyens pour détecter quand le paquet franchit une des frontières toriques et des moyens pour faire passer le paquet d'un réseau virtuel de niveau torique donné au réseau virtuel de niveau torique supérieur dès qu'un franchissement est détecté; caractérisé en ce que - chaque réseau virtuel (4a, 4b, 4c) comprend une zone (5) de noeuds dits actifs, c'est-à-dire susceptibles d'être effectivement utilisés pour router le paquet considéré, et une zone (6) de noeuds inactifs dans laquelle le paquet considéré ne doit pas circuler;; et en ce que - la zone (6) de noeuds inactifs d'au moins un des réseaux virtuels (4b, 4c) constitue la zone (5) de noeuds actifs d'un autre des réseaux virtuels (4c, 4b) et vice versa. 2. Système de routage selon la revendication 1 caractérisé en ce qu'il comprend - quatre quadrants directionnels virtuels, lesdites directions privilégiées (2a, 2b, 2c, 2d) étant opposées deux à deux - chaque quadrant directionnel virtuel comprenant un niveau torique de base (NO) et un premier (N1) et un deuxième (N2) niveau torique - chaque niveau torique (NO, N1, N2) correspondant respectivement à un réseau virtuel de base (4a), et un premier (4b) et un deuxième (4c) réseau virtuel; et en ce que - la zone (5) des noeuds actifs dans chaque réseau virtuel (4a) de base représente la totalité du réseau bidimensionnel réel (1) - la zone (5) des noeuds actifs dans chaque premier réseau virtuel (4b) représente la réunion des deux moitiés de réseau virtuel de base (4a) issues des frontières toriques (3X, 3Y) dans les directions X, Y, c'est-à-dire les trois quarts du réseau bidimensionnel total réel (1) - la zone (5) des noeuds actifs dans chaque deuxième réseau virtuel (4c) représente l'intersection des deux moitiés de premier réseau virtuel (4b) issues des frontières toriques (3X, 3Y) dans les directions X, Y, c'est-à-dire un quart du réseau bidimensionnel total réel (1) c'est-à-dire un quart du réseau bidimensionnel total réel (1) 3.Système de routage selon la revendication 1 ou 2 caractérisé en ce que la zone (5) active d'un premier réseau virtuel (4b) de direction donnée (2a, 2b, 2c, 2d) correspond à la zone inactive (6) du deuxième réseau virtuel (4c) du quadrant directionnel virtuel de direction (2d, 2c, 2b, 2a) opposée, lesdits deux réseaux virtuels (4b, 4c) étant réunis en un réseau virtuel mixte unique de la taille du réseau bidimensionnel total réel (1). 4. Système de routage selon la revendication 3 caractérisé en ce qu'il comprend quatre réseaux virtuels de base aller, quatre réseaux virtuels de base retour, quatre réseaux virtuels mixtes aller, et quatre réseaux virtuels mixtes retour, chacun repéré par un numéro de réseau virtuel actif. 5. Système de routage selon la revendication 4 caractérisé en ce qu'il comprend en outre - des moyens pour détecter le premier ou le deuxième franchissement d'un paquet dans un quadrant directionnel virtuel de direction (2a, 2b, 2c, 2d) donnée ; et dans le cas d'un deuxième franchissement - des moyens pour déterminer le quadrant directionnel virtuel de direction (2d, 2c, 2b, 2a) opposée, et des moyens pour faire passer le paquet concerné dans le réseau virtuel mixte correspondant au premier niveau torique (N1) dudit quadrant virtuel de direction (2d, 2c, 2b, 2a) opposée 6.Système de routage selon la revendication 4 ou 5 caractérisé en ce que les quadrants directionnels virtuels étant codés sur deux bits Sx et Sy, le niveau torique de base (NO) et le premier niveau torique (N1) étant codés sur un bit T1, l'aller et le retour étant codés sur un bit Rt, ledit système comprend des moyens de calcul pour calculer le numéro de réseau virtuel actif selon la formule 8 x Rt + 4 x Sy + 2 x Sx + Tl lorsque l'on est dans un niveau torique (NO) de base ou que l'on passe dans un premier niveau torique (N1), et selon la formule 8 x Rt + 4 x (1 - Sy) + 2 x (1 - Sx) + 1 lorsque l'on passe dans un deuxième niveau torique (N2). 7. Circuit de routage d'un noeud 100 d'un réseau bidimensionnel 1 de type torique d'ordinateur massivement parallèle, caractérisé en ce qu'il comprend des moyens pour mettre en oeuvre un système de routage selon l'une quelconque des revendications 1 à 6. 8. Circuit de routage selon la revendication 7 caractérisé en ce qu'il comprend - cinq connexions, (10a, 10b) soient quatre (10a) associées aux quatre circuits de routage du réseau les plus proches, et une (10b) connectée localement à une unité d'interface (101) avec le processeur de travail local ; - une pluralité de tampons (11) et de sélecteurs "cross-bar" (12) pour mettre en oeuvre le système de routage à réseaux virtuels (4a, 4b, 4c) - des circuits logiques pour les synchronisations et les interruptions réseau - des circuits logiques de test et d'initialisation ; - des circuits logiques de controle ; et - un système de sauvegarde et de restauration automatique de tous les tampons. 9. Circuit de routage selon la revendication 8 caractérisé en ce qu'il comprend seize sélecteurs cross- bar" (12) trois entrées - trois sorties , chacun d'entre eux étant destiné à un réseau virtuel (4a, 4b, 4c) du système de routage, deux des trois entrées et deux des trois sorties correspondant aux deux directions X,Y dans le plan, la troisième entrée et la troisième sortie correspondant à la direction locale vers l'unité d'interface (101) ; un contrôleur de priorité (13) étant associé à chaque sélecteur "cross-bar" (12) pour décider quelles entrées sont connectées à quelles sorties. 10. Circuit de routage selon la revendication 9 caractérisé en ce que chaque sélecteur "cross-bar" 3 x 3 comprend trois tampons (11), un pour chaque direction, pour stocker les paquets de données, si, à un temps donné, il est impossible d'effectuer le routage. 11. Circuit de routage selon les revendications 7 à 10 caractérisé en ce que tous les réseaux virtuels implémentés partagent les mêmes liens physiques (16) internoeuds. 12. Circuit de routage selon la revendication 11 caractérisé en ce que, pour chaque réseau virtuel, chacune des entrées des trois tampons (11) est connectée aux ports d'entrée (10a', lOb') des connecteurs (lOa, lOb) de direction X, Y ou locale qui lui est associée ; chacune des sorties des trois tampons (11) est connectée à une entrée des sélecteurs "cross-bar'1/contrôleur (12, 13) du réseau virtuel concerné; chacune des sorties des sélecteurs "cross-bar"/contrleur (12, 13) est connectée aux ports de sortie (10a", 10b")des connecteurs (10a, 10b) de direction X, Y ou locale qui lui est associé à travers une entrée d'un multiplexeur (seize entrées/une sortie) / contrôleur (14, 15). 13. Circuit de routage selon l'une quelconque des revendications 7 à 12 caractérisé en ce qu'il comprend en outre un dispositif de contrôle d in d'injection de nouveaux paquets de données ou messages dans le réseau, ledit dispositif étant local et dynamique. 14. Circuit de routage selon la revendication 13 caractérisé en ce que le dispositif de contrôle d'injection comprend - un compteur / décompteur incrémenté chaque fois qu'un paquet ou message entre dans le circuit de routage, et décrémenté chaque fois qu'un paquet ou message sort du circuit de routage; - un comparateur qui compare le nombre de paquets ou messages présents dans le circuit avec une valeur seuil prédéterminée de saturation du circuit de routage; - des moyens de transmission du résultat de la comparaison vers l'unité d'interface; ; ladite unité d'interface comprenant des moyens pour autoriser une injection locale d'au moins un nouveau paquet ou message dans le circuit de routage si le nombre de paquets ou messages déjà présents est inférieur à la valeur seuil et pour bloquer l'injection locale de nouveaux paquets ou messages dans le circuit de routage si le nombre de paquets ou messages déjà présents est supérieur ou égal à ladite valeur seuil.