FR2742894A1 - Systeme d'echange d'informations entre plusieurs operateurs - Google Patents

Abstract

L'invention concerne un réseau d'échange de transactions entre des opérateurs (CPU, MEM), comprenant une pluralité de noeuds (N) dont chacun comporte des entrées et des sorties en même nombre, reliées à des opérateurs ou à d'autres noeuds, et des moyens pour router plusieurs transactions de même destination vers des sorties respectives différentes.

Description

SYST D'E D'INFORMXTIONS ENTRE PLUSIEURS OPÎRATEURS
La présente invention concerne un système d'échange d'informations entre plusieurs opérateurs, tels que des processeurs, des mémoires, et des périphériques.

Dans un système particulièrement performant pour échanger des informations, on utilise des aiguillages ou "crossbars".

Chaque opérateur, souvent prévu sur une carte individuelle, est muni d'un aiguillage de sortie et d'un aiguillage d'entrée.

L'aiguillage de sortie est destiné à transmettre des informations émises par l'opérateur vers un opérateur sélectionné dans un premier ensemble d'opérateurs, et l'aiguillage d'entrée est destiné à transmettre à l'opérateur les informations provenant d'un deuxième ensemble d'opérateurs.

Dans un système typique comprenant des cartes processeur et des cartes mémoire, les aiguillages d'entrée et de sortie de chaque carte processeur permettent d'échanger des informations avec chacune des cartes mémoire, et les aiguillages d'entrée et de sortie de chaque carte mémoire permettent d'échanger des informations avec chacune des cartes processeur.

Une transaction, que ce soit une requête issue d'un processeur ou une réponse issue d'une mémoire, comprend une adresse de destination et une adresse d'émetteur. Chaque aiguillage examine les adresses de destination des transactions qui lui arrivent et détermine les sorties associées à ces transactions. Si plusieurs transactions sont en collision, c'està-dire que ces transactions sont associées à une même sortie, une seule des transactions est envoyée vers cette sortie et les autres sont mises en attente dans une mémoire tampon.

Un aiguillage d'un tel système est particulièrement coûteux. L'une des raisons est que le mécanisme de gestion des collisions, éventuellement au moyen de niveaux de priorité, est complexe.

Une autre raison est que chaque aiguillage comporte une mémoire tampon de taille relativement importante et dont la vitesse doit être adaptée à la vitesse élevée des transferts. La taille de la mémoire tampon détermine les performances du système. En effet, si la mémoire tampon déborde, les opérateurs qui émettent des transactions vers l'aiguillage doivent être arrêtés. La taille mémoire est d'autant plus importante que chaque transaction à stocker est constituée d'un grand nombre de bits (elle comporte au moins une adresse d'émetteur, une adresse de destination, une instruction, une adresse de donnée, et une donnée).

Encore une autre raison est que la densité de connexion des aiguillages croît rapidement avec la complexité du système, de sorte que les connecteurs doivent être réalisés avec extrême précision. En effet, le nombre de couples d'entrées/sorties de chaque carte est égal au nombre de cartes avec lesquelles ladite carte doit communiquer. Et chaque entrée ou sortie est de la taille d'une transaction.

Outre les inconvénients de coût susmentionnés, un système à aiguillages est de structure rigide. C'est-à-dire que, une fois que le système a été défini et assemblé, il est impossible de le faire évoluer par rajout d'opérateurs.

Pour limiter la densité de connexion des aiguillages, les cartes processeur ne sont généralement reliées qu'aux cartes mémoire. Si un premier processeur doit communiquer avec un deuxième, il faut alors instaurer un système de sémaphore, c'est à-dire que le premier processeur écrit à un emplacement mémoire spécifique une donnée en validant un drapeau. Le deuxième processeur vérifie périodiquement l'état du drapeau pour savoir si l'emplacement spécifique contient des données qui lui sont destinées. Outre le ralentissement des échanges entre deux processeurs qu'entraîne un système de sémaphore, un tel système doit être mis en oeuvre par une programmation des processeurs, ce qui constitue une contrainte supplémentaire pour le programmeur.

Un objet de la présente invention est de prévoir un système d'échange de transactions entre des opérateurs, qui soit particulièrement rapide tout en étant évolutif et de coût relativement bas.

Cet objet est atteint en connectant les opérateurs à un réseau formé de noeuds de routage particuliers qui peuvent être disposés selon une structure quelconque. Chaque noeud comporte autant d'entrées que de sorties et est prévu pour router vers des sorties différentes plusieurs transactions entrantes de même destination. En d'autres termes, si plusieurs transactions sont en collision dans un noeud, l'une des transactions est routée vers la sortie qui lui est associée et les autres transactions sont forcément routées vers des sorties respectives différentes.

Ainsi, plutôt que de mettre une transaction en attente dans une mémoire tampon, cette transaction est déviée de son chemin nominal et parviendra à sa destination par un deuxième chemin éventuellement plus long. I1 en résulte que toutes les transactions ayant pénétré dans le réseau de routage selon l'invention sont en circulation continue et arrivent toutes à destination, soit par un chemin optimal, soit par un chemin dévié.

Selon un mode de réalisation de l'invention, chaque noeud comprend une table de routage qui associe 1 'une des sorties du noeud à chaque destination d'une transaction.

Selon un mode de réalisation de l'invention, chaque noeud comprend autant de tables de routage que d'entrées ou sorties, chaque table associant une sortie différente à une méme destination de transaction, de manière que plusieurs transactions de même destination soient associées à des sorties différentes fournies par des tables respectives.

Selon un mode de réalisation de l'invention, les tables de routage successives sont associées à des chemins de préférence décroissante pour une destination donnée et à des priorités décroissantes des transactions, chaque noeud étant prévu pour incrémenter la priorité d'une transaction lorsque cette transaction n'est pas routée selon la table de préférence maximale.

Selon un mode de réalisation de l'invention, chaque noeud comprend une table de routage supplémentaire qui associe à chaque entrée une sortie qui se trouve, avec ladite entrée, sur un chemin reliant tous les noeuds et tous les opérateurs, cette table étant utilisée pour les transactions dont la priorité a atteint une limite supérieure.

Selon un mode de réalisation de l'invention, chaque noeud associe au hasard des tables respectives à plusieurs transactions de même priorité et de même destination.

Selon un mode de réalisation de l'invention, chaque opérateur comporte une entrée et une sortie reliées respectivement à une sortie et à une entrée d'un ou deux noeuds, l'opérateur étant prévu pour recevoir toute transaction sur son entrée et la renvoyer aussitôt à sa sortie si la transaction ne lui est pas destinée.

Selon un mode de réalisation de l'invention, chaque opérateur renvoie une transaction qui lui est destinée lorsque cette transaction arrive à un moment où l'opérateur est occupé.

Selon un mode de réalisation de l'invention, chaque opérateur génère et envoie une transaction de priorité nulle lorsque l'opérateur n'a aucune transaction à envoyer, cette transaction de priorité nulle étant ignorée par tout opérateur qui la reçoit.

Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles
la figure 1 représente schématiquement un noeud de routage selon l'invention comportant des tables utilisées dans un exemple optimisé d'algorithme de routage selon l'invention
la figure 2 représente schématiquement un mode de réalisation d'interface entre un réseau de noeuds de routage selon l'invention et un opérateur connecté à ce réseau
la figure 3 représente un exemple de réseau selon l'invention à quatre noeuds de routage pour interconnecter huit opérateurs ; et
la figure 4 représente un exemple de réseau selon l'invention à seize noeuds de routage pour interconnecter huit opérateurs.

Selon l'invention, une pluralité d'opérateurs, tels que des processeurs, des mémoires, des périphériques, etc. qui doivent échanger des informations, sont reliés à un réseau formé de noeuds de routage qui peuvent être reliés les uns aux autres de manière quelconque. L'invention réside plus particulièrement dans la fonction de chaque noeud de routage.

La figure 1 représente schématiquement un noeud de routage N selon l'invention. Il est nécessaire que le noeud comporte autant d'entrées que de sorties. De bons résultats sont obtenus avec des noeuds comportant, comme cela est représenté, quatre couples d'entrées/sorties E/S, mais tout autre nombre supérieur à deux peut être utilisé.

Chaque entrée ou chaque sortie peut être reliée indif férertirent à une sortie ou à une entrée d'un autre noeud, du même noeud, ou d'un opérateur quelconque muni d'une interface adaptée à un réseau de routage selon l'invention.

La fonction essentielle de chaque noeud N est de router plusieurs transactions entrantes de même destination vers des sorties différentes. En d'autres termes, si n transactions entrent simultanément dans le noeud (n étant inférieur ou égal au nombre de couples d'entrées/sorties), ces n transactions sont aussitôt routées vers n sorties respectives, même si certaines des transactions doivent ainsi emprunter un chemin plus long vers leur destination. Plutôt que de mettre une transaction en attente dans une mémoire tampon, toute transaction qui a pénétré dans le réseau est mise en circulation continue jusqu'à ce qu'elle atteigne sa destination. Bien entendu, on souhaite que chaque transaction atteigne sa destination le plus vite possible.

La présente invention prévoit un algorithme pour gérer le routage des entrées vers les sorties d'un noeud de manière à obtenir un transfert optimal des transactions vers leurs destinations. Cet algorithme, particulièrement simple, est de préférence mis en oeuvre par des circuits logiques et séquentiels dans chaque noeud N.

Pour mettre en oeuvre l'algorithme, chaque noeud N comporte une table (T1 à T4) par couple d'entrée/sortie, qui affecte un numéro de sortie à chaque destination possible d'une transaction. Les numéros de sortie affectés à une même destination diffèrent d'une table à 1' autre. Les numéros de sortie de la première table correspondent à un chemin préférentiel, et les numéros de sortie des autres tables correspondent à des chemins déviés de préférence décroissante.

Une transaction circulant dans un réseau selon l'invention comporte, de manière classique, un champ d'adresse de destination qui identifie l'opérateur destinataire de la transaction.

Ce sont toutes les adresses de destination utilisées qui constituent les entrées des tables susmentionnées. Par ailleurs, chaque transaction comporte, de manière classique, un champ d'adresse d'émetteur, un champ d'adresse de donnée, un champ de donnée, un champ d'instruction, et un champ de priorité. Dans un réseau selon l'invention, la priorité d'une transaction est initialisée à 1 par l'émetteur de la transaction.

Selon l'algorithme optimisé susmentionné, lorsqu'un noeud N reçoit une transaction par l'une quelconque de ses entrées, la transaction est routée vers la sortie associée à l'adresse de destination de cette transaction dans la première table T1.

Dans un cas de collision, plusieurs transactions entrantes ont la même adresse de destination. Dans ce cas, les transactions sont routées respectivement, par ordre décroissant de priorité, selon les premières tables successives qui associent une sortie différente à chacune des transactions en collision.

Dans un cas de collision entre un nombre limité de transactions, par exemple deux, la sortie associée par la deuxième table à la deuxième transaction, moins prioritaire, peut coïncider avec la sortie associée par la première table à une troisième transaction qui n'était pas en collision. Alors la transaction de priorité la plus élevée est routée vers la sortie débattue et l'autre est routée selon une table différente (la troisième transaction serait routée selon la deuxième table ou la deuxième transaction serait routée selon la troisième table). Et ainsi de suite, jusqu'à ce qu'une sortie différente soit attribuée à chacune des transactions entrantes.

I1 en résulte que toutes les transactions entrantes sont routées simultanément vers des sorties respectives différentes, même si ces sorties ne correspondent pas à des chemins préférentiels.

Une transaction qui n'est pas routée selon la première table préférentielle, voit sa priorité incrémenter de un.

Bien entendu, il peut arriver que plusieurs transactions en collision aient la même priorité. Dans ce cas, les transactions sont affectées aux différentes tables par un tirage au sort aléatoire.

La priorité d'une transaction comporte une limite supérieure déterminée par le nombre de bits du champ de priorité de chaque transaction. Si une transaction atteint cette limite supérieure, il est probable que des concours de circonstances font que le routage selon les tables normales susmentionnées est défavorable. On adopte alors, de préférence, une autre stratégie de routage.

Pour cela, chaque noeud N comporte une table supplémentaire TS associée aux transactions de priorité en butée supérieure. Cette table affecte un numéro de sortie différent à chacun des numéros d'entrée. La table TS est telle qu'une entrée et la sortie associée se trouvent sur un chemin (chemin eulérien) qui relie tous les éléments du réseau (noeuds et opérateurs). Une transaction de priorité en butée supérieure est nécessairement routée vers la sortie fournie par cette table supplémentaire TS.

Une autre transaction à laquelle aurait été affectée la même sortie par une table normale est routée selon une autre table normale. Ainsi, toutes les transactions de priorité en butée supérieure empruntent un chemin sur lequel ils trouveront nécessairement leur destination.

Parmi plusieurs transactions entrantes de priorité en butée supérieure, une seule, tirée au sort, est routée selon la table supplémentaire et les autres sont routées selon les tables normales, également tirées au sort, le cas échéant.

La figure 2 représente schématiquement une interface entre un réseau selon l'invention et un opérateur 10. L'interface comporte un commutateur 12 qui relie une entrée d'un noeud et une sortie d'un noeud respectivement à la sortie et à l'entrée de l'opérateur 10.

Lorsque le commutateur 12 reçoit du réseau une transaction, cette transaction est fournie à l'opérateur 10 si son adresse de destination correspond à l'opérateur 10. Du fait du fonctionnement précédemment décrit des noeuds selon 1' inven- tion, le commutateur 12 est susceptible de recevoir également des transactions qui ne sont pas destinées à l'opérateur 10. Dans ce cas, la transaction est aussitôt renvoyée vers le réseau par le commutateur 12. Pendant ce temps, le commutateur 12 active un signal 13 de réseau occupé qui empêche la fourniture d'une transaction par l'opérateur 10. Ce mécanisme particulièrement simple permet de gérer automatiquement les cas de saturation du réseau.

Lorsque l'opérateur 10 ne peut pas traiter une transaction, il active un signal 14 d'opérateur occupé. Dans ce cas, si la transaction reçue par le commutateur 12 est destinée à l'opé- rateur 10, la transaction est aussitôt renvoyée vers le réseau.

Selon une première variante, la transaction est renvoyée vers le réseau telle quelle, de sorte qu'elle est susceptible de revenir rapidement vers l'opérateur. Selon une deuxième variante, le commutateur 12 intervertit l'adresse de destination et l'adresse d'émetteur, de sorte que la transaction retourne vers l'émetteur qui saura de ce fait que la transaction n'a pas été traitée et pourra prendre des mesures adaptées.

Comme pour les noeuds de routage, aucune transaction n'est mise en attente dans un opérateur.

De préférence, si un opérateur 10 ne fournit aucune transaction alors que le réseau est libre, le commutateur 12 génère une transaction fantôme de priorité nulle. Chaque noeud génère également de telles transactions fantômes sur des sorties non-occupées. Ceci simplifie les circuits de réception et de traitement des transactions dans un noeud ou dans un opérateur.

Le commutateur 12 associé à un opérateur est alors prévu pour ignorer toute transaction fantôme lui parvenant et la remplacer, le cas échéant, par une vraie transaction.

Des opérateurs et des noeuds de routage selon l'invention peuvent être interconnectés de manière tout à fait quelconque, à condition que chaque sortie (d'un noeud ou d'un cpéra- teur) soit toujours reliée à une entrée (d'un opérateur, d'un autre noeud, ou du même noeud). Bien entendu, les tables normales (T1-T4) et la table supplémentaire (TS) de chaque noeud contiennent des valeurs qui dépendent de la configuration du réseau. Les tables de chaque noeud sont, par exemple, stockées dans des mémoires non-volatiles (ROM), ou bien dans des mémoires volatiles initialisées à la mise sous tension par un programme exécuté par l'un des opérateurs. Pour accéder aux tables afin de les mettre à jour, il suffit qu'elles soient reliées à un bus classique qui n'a pas besoin d'être rapide. De préférence, on utilise pour cela un bus de test (norme IEEE 1149.1) qui est par ailleurs utilisé pour tester les composants du système.

Bien entendu, les performances du système dépendent de la configuration choisie pour le réseau. De façon générale, il vaut mieux regrouper les noeuds de routage dans un noyau central autour duquel sont connectés les opérateurs.

La figure 3 représente un exemple de réseau selon l'invention à quatre noeuds de routage Nll à N22 pour interconnecter huit opérateurs (quatre processeurs CPU1 à CPU4 et quatre mémoires MEM1 à MEM4). Les noeuds sont connectés en anneau par deux couples d'entrées/sorties de chacun des noeuds. Les deux couples restants d'entrées/sorties de chacun des noeuds sont reliés à deux opérateurs. Comme cela est représenté pour les processeurs CPU1 et CPU3, et pour les mémoires MEM2 et Mes4, 1' entrée et la sortie d'un opérateur ne sont pas forcément reliées à la sortie et à l'entrée d'un même noeud.

La figure 4 représente une interconnexion des mêmes processeurs et mémoires par l'intermédiaire d'un exemple de réseau à seize noeuds N11 à N44 selon l'invention. Par souci de clarté, chaque couple d'entrée/sortie est représenté par une liaison bidirectionnelle unique. La configuration représentée du réseau de seize noeuds est une optimisation par rapport à une simple configuration en matrice. Ici, chaque noeud Nij est relié au noeud Ni+1,j et au noeud Ni+1,j+11 où i et j varient entre 1 et 4 et où i+l et j +1 sont calculés modulo 4. Les noeuds Nll à N14 sont reliés respectivement aux opérateurs CPU1, MEM2, CPU3, MEM4 et les noeuds N41 à N44 sont reliés respectivement aux opérateurs
CPU2, MET3, CPU4, MEM1.

Généralement, chaque processeur CPU travaille essen tellement avec une seule mémoire qui lui est dédiée et occasionnellement avec d'autres merrires. Ainsi, les processeurs sont disposés le plus près possible de leurs mémoires dédiées.

Dans la figure 4, chaque mémoire dédiée à un processeur est reliée à ce processeur par l'intermédiaire de deux noeuds seule ment (par exemple, la mémoire MEM2 est reliée au processeur CPU2 par l'intermédiaire des noeuds N12 et N41).

I1 est particulièrement simple de faire évoluer un système d'échange d'informations selon l'invention.

Lors du retrait d'un opérateur, il suffit de relier lune à l'autre l'entrée et la sortie libérées sur le réseau. I1 n'est pas nécessaire de reprogrammer les tables mais il faut s'assurer que les opérateurs restant sur le réseau n'émettent pas de transaction vers l'opérateur retiré.

Pour ajouter un opérateur, on dispose d'une multitude de solutions. Par exemple, l'opérateur est inséré dans une liaison entre deux noeuds en connectant 1' entrée de l'opérateur à la sortie du premier noeud et la sortie de l'opérateur à 1 'entrée du deuxième noeud. Une telle modification est représentée en pointillés à la figure 3 entre les noeuds N2l et N22. Bien entendu, on complète les tables de chacun des noeuds de routage par les sorties associées à la nouvelle adresse de destination correspondant au nouvel opérateur. Dans 1' exemple de la figure 3, dans la première table du noeud N21, 1' adresse de destination du nouvel opérateur est associée à la sortie directement reliée à cet opérateur. Dans la première table du noeud N22, la nouvelle adresse est associée à la sortie reliée au noeud N21.

Bien entendu, on peut chercher à reproduire la régularité du réseau de noeuds lors de l'ajout d'opérateurs, ceci en rajoutant des noeuds au réseau.

Dans une réalisation pratique, chaque opérateur et chaque noeud se trouve sur une carte individuelle. Dans ce cas, le choix de quatre couples d'entrées/sorties pour chaque noeud correspond à un bon compromis entre le nombre de noeuds nécessaires pour interconnecter de manière optimale tous les opérateurs et la densité de connexion des cartes. La densité de connexion maximale est celle d'une carte-noeud et elle est comparable, dans cet exemple, à celle d'une carte d'un système classique à aiguillages avec cinq cartes dont chacune peut communi- quer avec les quatre autres. Un réseau selon l'invention permet avantageusement de relier un nombre quelconque de cartes avec une densité de connexion fixe.

Les noeuds et les opérateurs sont reliés entre eux par nappes de fils. Les nappes sont constituées, selon les besoins, de fils simples, de paires torsadées, ou de fils coaxiaux. La fréquence de fonctionnement du système est déterminée par la longueur maximale ininterrompue des fils. Si le système doit fonctionner à une fréquence particulièrement élevée, la longueur des fils est réduite en multipliant le nombre de cartes-noeud interposées entre deux points distants à connecter ; chaque carte-noeud sert de relais de synchronisation.

La taille mémoire occupée par les tables d'un noeud est comparable à celle d'une mémoire tampon d'un aiguillage classique, mais les tables ne sont pas organisées selon une structure de mémoire tampon et on n'y accède à vitesse élevée qu'en lecture, ce qui réduit notablement leur coût.

L'algorithme de routage particulièrement simple selon l'invention, incorporant les tables, peut être directement programmé dans des circuits FPGA ("Fast Programmable Gate Array") à partir desquels on peut constituer économiquement des noeuds fonctionnant à vitesse élevée.

La présente invention a été décrite en relation avec un algorithme optimisé pour gérer chaque noeud de routage. Toutefois, d'autres algorithmes moins performants sont envisageables.

Par exemple, chaque noeud peut ne comporter qu'une table. Parmi des transactions en collision, une seule est routée selon la table et les autres sont affectées de sorties différentes de manière aléatoire.

Claims (9)

REUEHD I cL= S

1. Réseau d'échange de transactions entre des cpéra- teurs (CPU, MEM), caractérisé en ce qutil comprend une pluralité de noeuds (N) dont chacun comporte des entrées et des sorties en même nombre, reliées à des opérateurs ou à d'autres noeuds, et des moyens pour router plusieurs transactions de même destination vers des sorties respectives différentes.

2. Réseau d'échange selon la revendication 1, caractérisé en ce que chaque noeud comprend une table de routage (T1) qui associe 1 'une des sorties du noeud à chaque destination d'une transaction.

3. Réseau d'échange selon la revendication 2, caractérisé en ce que chaque noeud comprend autant de tables de routage (T1-T4) que d'entrées ou sorties, chaque table associant une sortie différente à une même destination de transaction, de manière que plusieurs transactions de même destination soient associées à des sorties différentes fournies par des tables respectives.

4. Réseau d'échange selon la revendication 3, caractérisé en ce que les tables de routage successives sont associées à des chemins de préférence décroissante pour une destination donnée et à des priorités décroissantes des transactions, chaque noeud étant prévu pour incrémenter la priorité d'une transaction lorsque cette transaction n'est pas routée selon la table de préférence maximale.

5. Réseau d'échange selon la revendication 4, caractérisé en ce que chaque noeud comprend une table de routage supplémentaire (TS) qui associe à chaque entrée une sortie qui se trouve, avec ladite entrée, sur un chemin reliant tous les noeuds et tous les opérateurs, cette table étant utilisée pour les transactions dont la priorité a atteint une limite supérieure.

6. Réseau d'échange selon la revendication 4 ou 5, caractérisé en ce que chaque noeud associe au hasard des tables respectives à plusieurs transactions de même priorité et de même destination.

7. Réseau d'échange selon l'une quelconque des revendications 1 à 6, caractérisé en ce que chaque opérateur (10) comporte une entrée et une sortie reliées respectivement à une sortie et à une entrée d'un ou deux noeuds, l'opérateur étant prévu pour recevoir toute transaction sur son entrée et la renvoyer aussitôt à sa sortie si la transaction ne lui est pas destinée.

8. Réseau d'échange selon la revendication 7, caractérisé en ce que chaque opérateur renvoie une transaction qui lui est destinée lorsque cette transaction arrive à un moment où 1' opérateur est occupé.

9. Réseau d'échange selon la revendication 7, caractérisé en ce que chaque opérateur génère et envoie une transaction de priorité nulle lorsque l'opérateur n'a aucune transaction à envoyer, cette transaction de priorité nulle étant ignorée par tout opérateur qui la reçoit.