FR 2311385 A1 19761210 FR 7515116 A 19750515 L'invention concerne une ire à décalage applicable dans les telecaw nications et en particulier pour la commutation de paquets d'informations, appelée mémoire-paquets. Le but de l'invention est de réaliser une moire a hautes performances et a gestion optimale de l'espace memoire, en particulier dans le cas de la commutation de paquets dtinformations en node voies virtuelles. En effet les exigences de la commutation de paquets iP,posent des performances contradictoires et difficiles a tenir. te tres grand nombre de paquets à traiter chaque seconde, qui peut atteindre plusieurs dizaines de milliers par }egabit comité, impose de ne pas perdre de temps à la gestion de la mémoire. ce qui risque d'entraîner une sous-utilisation de l'espace disponible et d'amener à surdimensionner la noire réservée au stockage des paquets. La mémoire selon l'invention permet la gestion d'un grand nombre de files d'attente de façon que les paquets relatifs à une voie virtuelle donnée ressortent dans l'ordre où ils sont entrés. L'invention a pour objet une mémoire a décalage comportant un contrôleur de commande et des modules de mémoire contenant des registres à décalage caractérisée par le fait que les registres a décalage sont assemblés sous forme de modules qui sont associés les uns aux autres en série de façon a former une channe fermée, chaque module comportant une logique d'acces en liaison avec une ligne bus de commande et avec une ligne de données elle-même reliée au contrôleur de commande, les informations nouvelles étant introduites au milieu des anciennes qui s'écartent pour leur faire place, ou extraites d'entre des informations qui se tassent a mesure. Les caractéristiques et avantages de l'invention ressortiront de la description d'un exemple de réalisation donné ci-apres en référence au dessin annexé dans lequel: La figure 1 représente un schéma synoptique de l'organisation générale d'une mémoire-paquets selon l'invention, la figure 2 représente la constitution d'un module de mémoire, la figure 3 donne le schéma d'une logique d'accès, la figure 4 montre l'emplacement des données dans la mémoire La mémoire-paquets représentée sur la figure 1 se compose d'un contrôleur Cl et d'un ensemble de modules de mémoire M1, M2 ... n.Le contrôleur CI est relié a un bus externe B et a deux bus internes, l'un B1 de données, l'autre B2 de commande, auxquels sont reliés tous les modules H1 a Mn. Chaque module est constitue d'une logique d'acces LA et d'une mémoire constituée de registres a décalage en parallele, R. Les modules 1A1 a lu sont associés les uns aux autres en série par des lignes mémoire circulante B3 de façon a former une chaîne fermée aussi longue que l'on veut. Pour fixer les idées, la chaîne peut comprendre 100 modules de 128 octets. On verra plus loin que la capacité individuelle des modules est fixée par les performances recherchées, leur nombre se déduisant de la capacité désirée. La figure 2 représente le détail d'un module MI à bta de mémoire. La logique d'accès LA de la figure 1 est constituée par des aiguilleurs A1 et A2 et A3, une logique d'état t, et un conparateur CR. Le registre a décalage RD est relié par l'intermédiaire des aiguilleurs A1, A2 soit a la ligne mémoire circulante B3 soit a la ligne bus de données BI. I1 reçoit une commande d'avancement a partir de la logique d'état L. Canne représenté sur la figure 3, la logique d'état L de type connu comporte une bascule "J14" T34 permettant de définir deux états des modules : état "amont" et état "aval". Elle comporte une sortie f pour rendre son état accessible par l'étage suivant.Elle comporte en outre des portes P qui contrôlent son passage a l'état "amont" ou "aval". Les fils utilisés sur les entrées de ces portes sont les fils a et b du bus de commande B2 qui dénotent la cofflmande, le fil e qui indique l'état de l'étage précédent et deux fils c et d qui proviennent du comparateur rR. A titre d'exewle, les états présents sur ces fils ont la signification suivante a b = recherche a b = initialisation a b = lecture a b = écriture c = identité entre les neuf bits de données présentés par l'étage précédent et les 9 bits présentés par -le bus de données B1 d = égalité a 1 de chacun des neuf bits de données présentés par 11 étage précédent ("drapeau 255") e = état "aval" de l'étage précédent Avec ces conventions, une logique telle que celle qui est représentée sur la figure 3 contrôle le passage du module a l'état "amont" si l'opération est une recherche et qu'il n'y a pas coincidence d'adresse et l'état "aval" dans le cas d'une opération d'initialisation ou d'une recherche avec coïncidence d'adresse ou encore dans le cas ou l'opération n'est pas une recherche et o en meme temps le module précédent est "aval" et où les données présentées ne sont pas le "drapeau 255". ITne "horloge" h synchronise les changements d'état de la bascule. Cette horloge h provient du bus de commande B2. La logique d'état comporte encore deux portes Pi, P2 comparant l'état, f, du module à l'état e du module précédent, et a l'information d pour en tirer deux informations qu'elle renvoie par le bus de commande B2 au contrôleur Cl. Ces informations représente tent le fait que le module est le "premier amont" ou le "premier aval". On verra pas la suite que, moyennant une initialisation convenable, il y a au plus un seul module qui soit ' premier amont et un seul qui soit "premier aval". La logique d'état délivre également A l'ensemble des registres à décalage RD du module une impulsion d'avancement. Cette IMpulsion provient d'un signal présente par le contr81eur Cl sur le bus de commande B2, que la logique état ne transmet au module que si celui-ci est aval (f) et si l'opération n'est pas une lecture ou bien ai le module est amont et l'opération n'est pas une écriture. Ces fonctions sont assurées par l'ensemble des portes P6. Le comparateur CR délivre les deux informations précédemment appelées c et d. Il peut obtenir c au moyen de neuf portes OU EXCLUSIF 01 ... 09 et d'une porte "NI" Ni. Il peut obtenir d au moyen d'une porte "ET" E1. L'aiguilleur A de la figure 2 est constitué par des aiguilleurs Ai, A2 et A3 qui conprennent chacun neuf amplificateurs qui ont un état de sortie à impédance infinie et un à impédance nulle.L'impédance de ces aiguilleurs est coz andee par des portes P3, P4 et P5 qui reçoivent les signaux de comande a et b et le signal "premier aval" élaboré par la logique d'ttat. L'aiguilleur Ai présente une basse impédance sauf lorsque le module est le "premier aval". A2 présente une basse impédance seulement dans le cas d'une lecture Ca b) et lorsque le module est le "premier aval". Aj présente une basse impédance seulement dans le cas d'une écriture ou d'une initialisation (b) et lorsque le module est le "premier aval". On a vu que, dans le cas d'une initialisation, les bascules de tous les modules sont dans l'état "aval". Pour que néammoins un module se considère comme le "premier aval", un et un seul module reçoit du module précédent le signal logique (a + b). f (l'initialisation correspond à la condition a b). L'ensemble de ces éléments peut être réalisé en circuits intégrés et le module sous la forme d'un bottier. ta mémoire-paquets peut être réalisée sur une carte de circuit imprime supporta,t les bottiers de circuits intégrés. Le nombre de 8 bits de données et d'un bit de drapeau n'a été indiqué qut titre d'exemple. En particulier, on peut utiliser 16 bits de données et I bit de drapeau. On peut encore réaliser un ensemble de 16 bits de données au moyen de deux modules de huit bits. On peut à cet effet insérer sur chacune des liaisons c et d allant du comparateur CR à la logique d'état L une porte ET à deux entrées.Si la deuxieme entrée est rel@ée à un signal vrai en permanence, le module fonctionne de façon autonome. Si la deuxième entrée est reliée à la sortie c ou, selon le cas, d d'un autre module relié au ligne bus de commande B2 que le premier module, mais à un bus de données B'1 différent, et inséré sur une ligne de données B'3 différente, et si ce deuxième module utilise lui-meme la sortie c, ou d, du premier module, alors le couplage réalisé entre les deux modules réalise un ensemble à 16 + 2 bits. Pour que la mémoire fonctionne, il faut encore que la capacité des deux channes soit égale. Dans un tel ensemble, on dispose de deux bits de drapeaux.On peut les utiliser tous n'en utiliser qu'un seul comme drapeau et le deuxième comme bit de parité. L'ensemble des registres à décalage constitue une boucle sans fin équivalente à une bande magnétique dans laquelle sont stockées les informations. A un moment donné le contenu de la mémoire est ordonné. La figure 4 donne à titre d'exemple trois positions de la mémoire : la colonne de gauche représente les bits de drapeau - la position A représente l'état de la mémoire après initialisation, - la position B représente l'état de la mémoire à un certain moment après introduction d'un paquet pour la voie 41, c'est-à-dire entre les drapeaux 41 et 42, le premier octet donnant la longueur du paquet, - la position C représente le même état de la mémoire après adjonction d'un deuxième paquet pour la voie 41, le premier octet donnant la longueur de ce paquet.Comme le montre la figure 4, les paquets d'informations relatifs à l'ensemble des voies sont placés de façon consécutive telle que le paquet i de la voie j est suivi du paquet i + 10 de la voie j ; le dernier paquet de la voie j est suivi du premier paquet de la voie j + 1. La taille de chaque paquet est détermine, par exemple, par un octet de contrôle Situé en tête. Les zones de mémoire occupées par les différentes voies sont séparées par des caractères ayant chacun un bit de repérage identifiable appelé "drapeau". A cet effet, la mémoire est organisée sur neuf bits en parallèle (sans compter un éventuel bit de parité). Les données s' Itenclert sur huit pistes ; la neuvième est la piste des repères drapeau. Le bit de drapeau est O eur les dorées ; il est de 1 pour les drapeau::; les huit autres indiquent alors le nuriéro de la voie. Initialisation. Le contrôleur Cl présente sur le bus de commande B2 une instruction ( b) qui provoque le passage de tous les modules à l'état "aval". Le câblage entre l'un particulier des modules et son suivant diffère toutefois de tous les utres : le signal représentart ltetat aval du module preédent est inhibe par la conbinaisoIl ab de l'initialisation, en sorte que le module suivant se reconnait "premier aval". Ceci a pour effet de fermer l'aiguilleur AI et d'ouvrir l'aiguilleur A3. La combinaison ah a suffi pour bloquer l'aiguilleur A2. Le contrôleur C1 présente alors sur le bus de données B1 la combinaison "drapeau 255" ne contenant que des 1. Puis, il envoie un nomhre d'impulsions d'avancement très élevé (par exemple, supérieur à la capacité en octets de la mémoire). La logique d'accès de chaque module transmet ces impulsions d'avan cernent aux registres à décalage PJ) qu'elle contrôle. Par l'aiguilleur A3 du module "premier aval", la mémoire se remplit donc de "drapeau 255". Puis le contrôleur C1 présente successivement sur le bus de données BI, les combinaisons drapeau 0, drapeau 1, drapeau 2, ... drapeau 254, drapeau 255 å raison d'une combinaison par impulsion d'avance'cent, et s'arrête. L'opération d'initialisation est alors terminée. La mémoire contint, dans l'ordre, les drapeaux 0, I, 2, .. 254.Tout le reste de la wire. c' est-à-dire la partie non utilisée que l'on appelle la "bulle", est rempli de "drapeau 255". Recherche. Une opération de lecture ou d'écriture commence normaleoent par une opération de recherche. Â cet effet, le contrôleur Cl présente sur le bus de données BI le drapeau recherche. Simultanément, il présente sur le bus de comande B2 l'ordre de recherche (ab), ce qui a pour effet de faire passer tous les a > dules dans I 'état amont, et il envoie sur le bus B2 des impulsions d'avancement que chaque logique d'accès lA transmet aux registres A décalage RD qu'elle commande. Après chaque nouvelle impulsion d'avancement, le compara- teur CB de chaque module compare le drapeau demandé sur le bus de données Bi i au nouveau caractère qui se présente devant lui sur la ligne de données B3.Pour l'exemple cite de ioe modules de 128 octets, c'est à chaque cycle 100 octets qui sont testés en parallèle. Si les registres fonctionnent à 5 MIz, le drapeau recherché sera trouve au plus tard en 26 ps et, en moyenne, au bout de 13 1s s. La recherche se termine lorsque l'un des comparateur CP détecte sur la ligne de données B3 un caractère identique A celui présenté sur le bus de données Bl. Sa bascule d'état passe alors dans l'état "aval".Sa logique d'état, comparant son propre état celui du module précelent, génère un signal "premier aval" qu'elle injecte sur le bus de coDuande par l'intermédiaire d'un amplifica- teur de decouplage A4; lorsqu'il reçoit ce signal, le contrôleur C1 cesse d'envoyer des impulsions d'avancement et présente, selon le cas, un ordre de lecture ou d'ecriture. Dans le cas général, les modules suivant le premier aval vont successivement passer dans l'état aval. Il faut pour cela que le module qui les précède soit aval et que leur comparateur CP, ne détecte pas un caractère coaposé exclusivement de 1 (drapeau 255).Les modules basculent successivement dans l'état aval, un pat impulsion d'horloge distribuée par le bus, jusqu'au premier dont le comparateur CR voie sur la ligne de donnes B3 le drapeau 255, exclusi vexent. Ce module injecte alors sur le bus de commande "2, par l'intermédiaire d'un amplificateur de découplage A5, l'information "premier amont" que le contr8- leur Cl interprète comme l'autorisant à commencer à envoyer des impulsions d'avancement. L'état de la mémoire est alors le suivant: le module qui a trouvé le drapeau recherche est le "premier aval", les modules qui suivent, jusqu'au début de la "bulle" sont aval.Le premier module dont le comparateur CR voit la bulle est le "premier amont". te reste de la bulle et le début de la mémoire utile jusqu'au drapeau recherché correspondent à des modules amont. On a vu que le contrôleur Cl s'abstient d'envoyer des impulsions d'avancement entre le moment où il reçoit le signal "premier aval" et le signal "premier amont". Le temps qui sépare ces deux évènements correspond à autant d'impulsions d'horloge qu'il y a de nodules aval. Dem variantes sont possibles. La pralliare consiste à laisser les modules basculer de façon asynchrone. La deuxième consis- te à gagner du teiaps en recourant à un dispositif connu dans les additionneurs, dans lequel sont constitués des blocs de modules et utilisant le procédé du report de la retenue.Si auncun module d'un bloc ne détecte dans son compara- teur le drapeau 255, le bloc peut retransmettre au bloc suivant l'information "aval" dès que le bloc précédent, éventuellement, lui transmet l'information "aval". Dans toutes les realisations, une temporisation dans le contrtleus Cl permet de détecter un éventuel fonctionnement anormal. Ecriture. te contrôleur CI présente sur le bus de commande l'ordre d'écri- ture (ah). Ceci a un double effet: en premier lieu, dans le module "premier aval" l'aiguilleur f3 s'ouvre, tandis que l'aiguilleur A2 se ferme, AI étant fermé par le fait que le module est premier aval. Dans tous les autres modules, Al est ouvert tandis que A2 et A3 sont fentes. En deuxième lieu, la logique d'état L des modules aval transmettra aux registres à décalage RT > qu'elle contrô- le les impulsions d'avancement présentées sur le bus de commandes B2, tandis que les modules amont ne les laisseront pas passer.De la sorte, les données présen- tées successivement sur le bus de données B1 vont entrer par ttaiguilleur A3 du module premier aval dans l'espace qui se forme entre l'information aval, qui répond aux impulsions d'avancement, et l'info;rmation amont, qui ne bouge pas. Le dernier module aval contient donc de plus en plus de données et de groins en moins de drapeaux 255, jusqu ' ce qu'éventuellement il n'en contienne plus du tout. Le comparateur CR du module suivant, ne voyant plus la combinaison drapeau 255 cesse de se déclarer "premier amont" pour passer dans état aval. Désormais, il répondra aux impulsions d'avancement.Dans le cas général, le module suivant est tel que son comparateur CP voit le drapeau 255. Ce dernier va donc à son tour se déclarer premier amont et ce n'est éventuellement que pendant un treks court instant inférieur à une période de l'horloge h que cette innovation aura disparu du bus de commande B2. Si le contrôleur Cl détecte que cette absence se prolonge, c'est le signe que la bulle a une taille inférieure à un nodule. Le contrôleur est alors à même de prendre les actions appropriées pour éviter un débordement, par exemple, cesser d'écrire (mais la bulle n'est pas encore for cement nulle) et indiquer la condition exceptionnelle sur le bus externe. On vient donc de voir que lors d'une opération d'ecriture, l'information rentre à la bonne place au milieu des données qui s'écartont pour lui faire de la place, tandis que la taille de la bulle diminue. Lecture. Le fonctionnement resseml 1c à celui de l'écriture. Cette fois, ce sont les modules amont qui avancent et, daIls le module "premier aval" l'aiguilleur A2 fait sortir les donnes sur le bus de données B1. La taille de la bulle croît car le module "premier amont" fait rentrer dans ses registres a décalage RD l'information que lui présente le module précédent qui, lui, ne bouge pas, et cette information est un drapeau 255. Donc les opérations de lecture et d'écriture respectent le principe d'une bulle unique. Organisation de la mémoire. On a vu qu'à l'initialisation, la mémoire contient, dans l'ordre, les combinaisons drapeau 0, drapeau 1, drapeau 2, ... drapeau 254, puis la bulle (fig. 4). Pour écrire un paquet relatif à la voie i, il faut rechercher le drapeau i + 1. Bne opération d'écriture consécutive viendra donc mettre le paquet juste avant le drapeau i + I, c'est-a-dire à la suite des informations plus anciennes relatives à la voie i, s'il en existe, ou juste après le drapeau i, s'il n'en existe pas. On pourra juger utile de faire précéder chaque paquet d'un octet qui indique sa longueur. Même dans le cas d'une réalisation à 16 bits, cet octet, par sa parité, permettra au contrôleur lors d'une opération de lecture de savoir combien d'impulsions d'avancement envoyer. Pour lire un paquet relatif à la voie i, il faut rechercher le drapeau i et le sauter. Si la combinaison suivante n'a pas le bit de drapeau, il s'agit bien d'un paquet, le plus ancien relatif à la voie i, et le premier octet lu pourra éventuellement renseigner sur sa longueur. Pour sauter le drapeau i, on peut le lire (opération destructive) et le récrire. Le contrôleur Cl commande quatre opérations indispensables, I'initialisation, la recherche, l'écriture et la lecture. L'arrêt n'est pas à proprement parler une opération, puisqu'il suffit au contrôleur de ne plus envoyer d'inpu- sion d'avancement pour obtenir l'arrêt. On peut toutefois iLIagirer enrichir le contrôleur d'opérations supplémentaires. La plus utile serait sans doute la lecture non-destructive qui, comme la recherche, fait mouvoir tant l'amont que l'aval avec une connexion en sortie du module premier aval. Une opération utile à d'autres applications pourrait être le remplacement, s'analysant en une écri- ture simultanée à une lecture, mais il suppose des bus séparés pour l'entrée et la sortie. Ensuite, une écriture suffit à initialiser. L'élimination d'un module de mémoire en défaut peut être effectuée au noyen d'un shunt automatique. Il faut pour cela un moyen le détection et un noen d'action. Le moyen de détection consiste à la base en une foène piste de parité. La détection d'une faute de parité met au travail une bascule d'erreur si la bascule correspondante du module précédent n'est pas elle-même au travail. L'action va consister à organiser un shunt autour du module précédent. A cet effet, le shunt existe automatiquement en sortie, en ce sens que chaque module alimente à la fois le module suivant et un shunt. Le passage au oode dégradé consiste en ce qu'un module utilise conne entrée le siiunt du module précédent plutôt que la sortie de ce module . Pour éviter les défauts dus au système de détection ou de shunt, les shunts sont arrangés de façon que l'organe détecteur se shunte luimrne. Si la capacité de la mémoire a été excessivement réduite le contrôleur cessera de recevoir l'information "premier amont" comme il a été indiqué. En ce qui concerne le contrôleur, on peut envisager de le doubler mais en le shuntant, l'erreur de l'un libérant le shunt de l'autre. Des deux contrôleurs CI, un seul serait en service à un moment donné, l'autre étant déconnecté des bus de données BI et de commande B2. L'activation Oit la désactivation d'un contrôleur Cl se faisant soit sous la supervision d'un organe distant relié au bus externe B, soit sous le contrôle de l'autre contrôleur. Les fonctions du contrôleur Cl sont les suivantes - recevoir une commande sur la ligne bus externe et en déduire les commandes à émettre sur le bus B2 de commande. - assurer la transmission des données sur la ligne bus Bl et sur le bus externe, en jouant éventuellement le rôle de mémoire tampon. - éventuellement tenir à jour un octet d'état et être capable de le présenter sur le bus externe. ta mémoire circulante décrite est associative, c' est--dire qu'on ne sait jamais où se trouve l'information et c'est par le contenu de l'information, en fait par le drapeau, que l'on est capable de la retrouver. La metroire circulante est élastique et ce sens qu'on est capable d'y faire de la place pour y insérer des informations ou de rapprocher les informations. Elle permet de gérer des files d'attente dans lesquelles le premier paquet arrivé doit être le premier à partir. La description qui précède a donné un exemple de mémoire paquets mais les applications de l'invention ne sont pas limitées à la coisautation de paquets ; cette mémoire circulante peut avoir des applications générales dans les tél - communications pour gérer des lignes de communication collportant p1u.:iriirs files d'attente et de façon plus générale en informatique pour gérer des fichiers. Bien entendu l'invention n1 est nullement limitée à ltexelulple décrit, en particulier on pourra sans sortir du cadre de l'invention, rerplacer certains moyens par des moyens équivalents. REVENDICATIONS 1/ Mémoire à décalage comportant un contrôleur de commande et des registres à décalage caractérisée par le fait que les registres a décalage (RP) sont assemblés sous forme de modules (MI à Mn) qui sont associés les uns aux autres en série de façon à formater une chaîne ferlée, chaque module (s'1 à stn) comportant une logique d'accès (LA) en liaison avec une livre Sus de cernées (B1) et une ligne bus de commande (B2) elles-mêmes reliées au contrôleur de coninande (c1), les informations nouvelles étant introduites au milieu des anciennes qui stécar- tent pour leur faire place, ou extraites d'entre des informations qui se tassent à mesure. 2/ Mémoire selon la revendication 1, caractérisée par le fait que les registres à décalage (RD) sont reliés par une ligne mémoire circulante (B3), les lignes bus de données (B1) et de commande (B2) longeant la mémoire et formant une boucle fermée par le contrôleur (C1). 3 Mémoire selon la revendication I ou 2, caractérisée par le fait que la logique d'accès (LA) comprend une logique d'état (L), un comparateur ((:P) auquel elle est reliée, le comparateur (CR) étant intercalé entre la ligne mémoire circulante (B3) et la ligne bus de données (BI), la logique d'état envoyant des commandes d'avancement aux registres à décalage (RD), la logique d'état étant reliée à l'étage précédent qui lui indique si le module précédent est "amont" ou "aval" et étant reliée à l'étage suivant pour l'aviser qu'elle est elle-même "amont" ou "aval", la logique d'accès comportant un aiguilleur (A) intercalé dans la ligne mémoire circulante (B3) et commandé par la logique d'état (L), cet aiguilleur a trois états: dans un état, les données de la ligne mémoire circulante (B3) sont dirigées sur la ligne bus de données (B1) ; dans l'autre état, elles continuent dans la ligne mémoire circulante (B3) ; dans le troisième, les données de la ligne bus de données (B1) sont dirigées sur la ligne mémoire circulante (B3). 4/ Mémoire selon l'une des revendications I à 3, caracterisee par le fait que les zones mémoires occupées par les paquets de données sont séparées par des bits de repérage identifiables ou drapeaux, qui sont utilisés pour retrouver le paquet considéré. 5/ mémoire selon la revendication 4, caractérisée par le fait que la mémoire est organisée sur n bits en parallèle, les données s'étendant sur n-l pisteS, la nième étant réservée aux signaux de repérage ou drapeaux. 6/ Mémoire selon la revendication 5, caracterisee par le fait qu'une organisation sur 2n bits peut s'obtenir par l'interconnexion de 2 mémoires In bits. 7/ Mémoire selon l'une des revendications précédentes caracterisee par le fait que le contrôleur (CI) de la mémoire circulante connande quatre opérations : initialisation, recherche du drapeau considéré, insertion des données et extrac- tion de données. 81 mémoire selon l'une des revendications précédentes, caractérisée par le fait qu'elle comporte une piste de parité, la détection d'une faute de parité mettant au travail une bascule d'erreur de la logique d'état (L). 9/ Mémoire selon l'une des revendications précédentes caractérisée par le fait qu'un shunt automatique est organisé autour de chaque module, et activé par la détection d'une erreur. 10/ Mémoire selon la revendication 1, caractérisée par le fait que le contrEì- leur est doublé et muni d'un dispositif de shuntage.