Brevet FR2769387A1 — publié le 19990409

Procédé de gestion d'une mémoire élastique et dispositif pour la mise en oeuvre du procédé Dans les systèmes électroniques numériques, les transmissions de données entre un émetteur et un récepteur nécessitent souvent d'interposer une mémoire tampon de stockage temporaire. Selon l'application, cela permet à l'émetteur et au récepteur de fonctionner à des rythmes instantanés différents, ou encore de tolérer des fluctuations du flux entrant, grâce à un lissage. Une mémoire tampon, récepteur intermédiaire, est donc interposée entre l'émetteur et le récepteur final. Les données provenant de l'émetteur sont stockées dans le tampon au rythme de la voie d'accès entrante, fixé par l'émetteur, et retransmises au récepteur au rythme de la voie d'accès sortante, de lecture par le récepteur. A l'équilibre, cette mémoire est sensiblement à moitié remplie. Une crête temporaire de fluctuation positive de trafic sera ainsi stockée sans perte et retransmise ultérieurement. De même, une crête négative pourra être masquée puisque la sortie s'alimente sur la réserve de trafic stocké. La mémoire a ainsi un volume utilisé qui est élastique. Lorsqu'une crête de trafic se prolonge, la mémoire va déborder ou se vider si aucune mesure de régulation n' intervient. I1 est donc intéressant d'implémenter des indicateurs de remplissage. Grâce à ces indicateurs, un processus de gestion des voies d'accès peut alors modifier si nécessaire le flux entrant et/ou sortant pour les rééquilibrer, par exemple en modifiant le débit de la voie de sortie ou, symétriquement, en avertissant le circuit émetteur. Parmi les indicateurs, on peut citer les deux indicateurs de débordement "VIDE" et "PLEIN", qui correspondent aux limites d'élasticité de capacité, et les indicateurs de remplissage qui permettent de détecter par exemple que la mémoire tampon est quasipleine ou quasi-vide. Comme, dans une mémoire tampon les données sont écrites à des adresses successives et forment donc une zone de données ou bloc de longueur variable, il suffit théoriquement, pour mesurer ce bloc, et en déduire le taux de remplissage, de connaître les adresses de début et de fin de celui-ci. En pratique, on lit les diverses données en conservant leur ordre d'arrivée, c'est-à-dire qu'on lit à chaque fois la donnée la plus anciennement écrite. Cette exploitation est dite FIFO, pour Premier entré - Premier sorti. Pour cela, on écrit les données successivement reçues à des adresses que l'on fait croître progressivement, qui constituent une sorte de front avant par où le bloc se développe. Pour la lecture et la retransmission qui suit vers le récepteur final, qui va rendre disponible l'adresse lue, on lit l'adresse de fin de bloc (données les plus anciennes) et la fait croître progressivement à chaque lecture. Le front arrière de bloc modifié "poursuit" ainsi le front avant. En bout de plage disponible, on reboucle sur le début, c'est-à-dire que le front avant poursuit aussi le front arrière, constituant ainsi un tampon en anneau. De façon classique, on adresse la boucle par deux compteurs avançant pas à pas à chaque événement respectif, écriture et lecture, compteurs qui pointent l'adresse considérée. Une soustraction des adresses des deux pointeurs fournit alors la taille du bloc de données et permet d'en déduire le taux de remplissage. Cependant, comme expliqué plus haut, les horloges d'écriture et de lecture ne sont souvent pas synchronisées entre elles, par exemple si les rythmes entrant et sortant sont différents, si bien qu'on ne peut garantir l'existence d'un temps mort qui serait réservé à la soustraction des adresses et celle-ci risque d'être faussée si l'adresse d'un des pointeurs évolue alors. Le résultat ainsi parasité n'a alors aucune signification. On peut prévoir des mécanismes de synchronisation ou de réitération de la soustraction, avec vote majoritaire, mais cela accroît nettement la complexité de l'électronique de calcul et le temps de décision. La présente invention vise à améliorer la fiabilité des résulats de calcul ou d'estimation du remplissage d'une mémoire élastique sans toutefois accroître la complexité du calcul. A cet effet, l'invention concerne tout d'abord un procédé de gestion d'une mémoire élastique, dont on remplit et vide une zone de données de taille variable indiquée par deux pointeurs d'adresses de début et de fin de zone, dans une plage d'adresses de taille déterminée, procédé caractérisé par le fait qu'on modifie fictivement la taille de la zone, par décalage déterminé de l'adresse de l'un des pointeurs, on détecte qu'un seuil de remplissage de la mémoire est atteint en recherchant l'identité entre 1' adresse décalée et une adresse correspondant à l'autre pointeur et on modifie en conséquence le vidage/remplissage de la mémoire. Par exemple, pour détecter un remplissage excessif, on peut associer au pointeur de lecture un pointeur décalé en arrière de celui-ci de N pas d'adresse. La détection de l'identité entre l'adresse de lecture décalée et l'adresse d'écriture signale alors que l'espace mémoire libre n'est plus que de N unités, c'est-à-dire N (paquets de) bits ou octets. Pour la détection d'un vidage excessif, le principe est le même que ci-dessus. On peut associer au pointeur d'écriture un pointeur décalé en arrière de celui-ci de M pas. La détection de l'identitié de l'adresse d'écriture décalée avec l'adresse de lecture signale alors que l'espace de données restant à lire n'est plus que de M unités. Comme il s'agit d'une détection par identité, ou égalité, il se produit beaucoup moins de parasites, ou résultats erronés transitoires, lors des changements d'adresse. En effet, une égalité entre deux nombres d'adresse est une juxtaposition d'égalités entre bits de même rang, sans interaction latérale (retenue) entre rangs. Bref, dans l'invention, on remplace la propagation transversale d'une pluralité de changements d'état de bits, liée à l'utilisation d'un soustracteur, par une simple propagation aval, beaucoup plus rapide et ne comportant qu'un seul chemin par bit. Avantageusement, on déplace la zone dans la plage d'adresses, par écriture à l'adresse du pointeur de début et par lecture à l'adresse du pointeur de fin, selon une séquence d'adresses suivant un code de Gray. Ainsi, à chaque changement d'adresse, le code de Gray permet de limiter à un seul bit le changement qui intervient dans les bits d'adresse, ce qui exclut donc tout résultat parasite le bit qui change d'état fait apparaître, de façon stable, par un seul chemin, une fenêtre de résultat d'égalité, ou maintient simplement fermée cette fenêtre en cas d'inégalité persistante. Avantageusement encore, on engendre deux décalages de l'adresse de l'un des pointeurs, et on détecte le sens de franchissement d'un seuil associé aux décalages d'après l'ordre dans lequel se produisent les identités correspondantes. L'invention concerne aussi un dispositif de gestion d'une mémoire élastique, pour la mise en oeuvre du procédé de l'invention, agencé pour écrire et lire une zone de données de taille variable délimitée par deux pointeurs d'adresses à l'intérieur d'une plage d'adresses, caractérisé par le fait qu'il comporte des moyens pour décaler l'adresse d'un des pointeurs et des moyens comparateurs pour détecter 1' identité entre l'adresse décalée et une adresse correspondant à l'autre pointeur. L'invention sera mieux comprise à l'aide de la description détaillée du mode de mise en oeuvre préféré du procédé de l'invention, en référence au dessin annexé, sur lequel - la figure 1 représente le schéma de principe d'un dispositif de gestion mettant en oeuvre le procédé de l'invention, et - la figure 2 représente un circuit détecteur d'identité d'adresses. Le dispositif représenté est intégré dans un système de transmission de données et comporte une mémoire tampon 1, exploitée ici selon un fonctionnement en anneau, dans laquelle des données sont inscrites par un circuit d'entrée 2 au rythme d'un signal d'horloge H1 et sont lues par un circuit de sortie 3, de restitution différée, selon un signal d'horloge H2. Un compteur 4, pointeur d'écriture, d'horloge H1, aiguille les données du circuit d'entrée 2 vers une adresse évoluant à chaque écriture. Un compteur 5, pointeur de lecture, d'horloge H2, adresse la mémoire 1, de façon évolutive à chaque lecture, pour alimenter en données le circuit de lecture 3. Les écritures successives, par bit ou paquets de bits, constituent, dans la plage des adresses de la mémoire 1, une zone 12 de données dont la taille évolue, ici par déplacement de chacune de ses deux extrémités. Les pointeurs évoluent ici selon une séquence déterminée et rebouclée d'adresses successives, si bien que la zone 12 est une zone d'un seul tenant dans la mémoire 1. Si, en variante, les pointeurs évoluaient selon une séquence de Gray, la zone 12 serait physiquement répartie dans la mémoire 1 de façon morcelée, tout en restant logiquement d'un seul tenant puisque toutes les adresses appartiennent à un même tronçon de la séquence de gestion de la mémoire 1. Pour la clarté de l'exposé, la zone 12 est représentée d'un seul tenant dans la figure 1. La zone 12 se translate dans la plage de la mémoire 1, son front avant 23 (adresse AD1) progressant, à chaque écriture (hui) d'une unité d'adresse dans la direction de la flèche 20. Le front arrière 21 (adresse AD2) de la zone 12 se déplace dans le même sens au rythme des lectures (H2) (flèche 22), qui libèrent à chaque fois une adresse. Autrement dit, la zone 13 libre diminue d'une unité à chaque écriture et se dilate d'une unité à chaque lecture intervenant dans la zone 12 complémentaire. Au compteur de lecture 5 est associé un compteur décalé 6 et, dans cet exemple, un autre compteur décalé 7, qui pointent respectivement sur des adresses 24 et 25. L'écart entre les adresses 21 et 24 est ici fixe, c'est-à-dire que le front arrière fictif 24, retardé d'un décalage 15, se déplace (flèche 26) à la vitesse du front arrière 21 dont il est l'image. Le compteur 6 reçoit le signal d'horloge H2, tout comme le compteur 5, et comporte une entrée de prépositionnement qui fixe, à la mise sous tension ou de façon cyclique grâce à un signal de synchronisation 14 issu du compteur 5, son écart (15) (nombre de pas d'adresse) par rapport au compteur de lecture 5, autrement dit le seuil de remplissage à détecter. Quant au compteur 7, il est ici décalé d'une unité en plus par rapport au compteur 6 et se présente en fait sous la forme d'un registre tampon (registre à décalage à un étage) à entrées et sorties parallèles lisant l'état du compteur 6. On conçoit que, de même, le compteur retardé 6 pourrait être remplacé par un registre à décalage ayant le nombre d'étages correspondant au décalage 15. Un double comparateur 8 reçoit les adresses issues des pointeurs, d'écriture 4, d'une part et, d'autre part, de lecture décalée 6, respectivement 7. Il fournit des signaux, en cas d'égalité, à un circuit machine d'états 11 élaborant un indicateur de remplissage 10. Le double comparateur 8 est constitué de deux comparateurs identiques. Le premier compare les adresses des pointeurs 4 et 6, le second compare celles des pointeurs 4 et 7. La figure 2 représente la structure du premier des comparateurs 8. Il est constitué d'une rangée de portes OU exclusif 81 à 88 en parallèle, à deux entrées, dont l'une reçoit un bit d'adresse de poids spécifique du pointeur 4 et l'autre le bit homologue du pointeur 6. Il y a autant de portes OU exclusif que de bits d'adresse, ici huit. Une porte OU classique collecte les résultats des portes OU exclusif 81 à 88. En cas d'identité d'adresses (4, 6), chaque paire de bits de même poids a la représentation binaire "00" ou "11" et toutes les portes OU exclusifs 81 à 88 fournissent donc un état logique "0", si bien que la porte OU 89 fournit de même un état logique "O". Par contre, une paire de bits de même poids présentant une discordance "01 " ou "10" fait passer à " 1 " la sortie de la porte OU exclusif 81 à 88 considérée. La sortie du OU 89 est alors forcée à " 1 " et l'état des autres bits en entrée ne peut que confirmer cet état "1", sans pouvoir l'annuler. Comme le montre la figure 2, la propagation des transitions d'état des adresses en entrée s'effectue uniquement vers l'aval (89) sans propagation latérale entre les portes OU exclusif 81 à 88. De ce fait, une transition d'un bit d'adresse n'a qu'un seul chemin de propagation, si bien qu'il n'y a aucun risque d'apparition d'états transitoires en sortie de la porte OU 89 dus à un seul bit, comme ce serait le cas s'il existait deux chemins en parallèle avec des temps de propagation différents. Bref, l'identité d'adresses est un état particulier que l'on détecte par des moyens matériels beaucoup plus simples qu'un bloc de calcul d'amplitude de différence, puisqu'il y a pas de retenue à propager transversalement, donc le temps de traversée est bien plus court. En cas de changement de plusieurs bits d'adresse, il subsiste cependant, au moins en théorie, un risque d'apparition d'état transitoire au niveau de la porte OU 89 si, parmi les portes OU exclusif 81 à 88, qui commutent, l'une présente un temps de traversée nettement inférieur à celui d'une autre et ouvre la fenêtre avant que l'autre porte n'ait eu le temps d'en confirmer la fermeture. De même, un compteur classique (4, 6) peut présenter des états (adresses) transitoires entre deux états stables successifs. Afin d'éviter le risque correspondant, les compteurs (4, 5, 6, 7 peuvent en variante, comme déjà évoqué, progresser selon un code de Gray, c'est-à-dire que les adresses successives qu'ils fournissent ne diffèrent deux à deux que d'un seul bit ...0000, ...0001, ...0011, 0010, .0110, ...0111, ...0101, ...0100, etc. La mémoire 1 est gérée de la façon suivante. A la mise sous tension, les compteurs-pointeurs 4 et 5 ont un même état, par exemple l'adresse "0", l'adresse du pointeur 6 se trouvant décalée en arrière de celle du pointeur 5 avec l'écart prédéterminé 15. Après écritures et lectures, la mémoire 1 présente une zone de données 12, comme sur la figure 1. Le problème général est de fournir des indicateurs de remplissage au système pour permettre si nécessaire de réguler la taille de la zone 12 pour éviter une saturation complète (débordement) de la mémoire (perte d'élasticité) et éventuellement éviter son vidage complet (débordement de capacité négative). La figure 1 illustre simplement la détection de franchissement d'un seuil de remplissage avec risque de débordement positif. Lorsque la taille de la zone 12 s'accroît, le front d'écriture 23 dépasse dans l'ordre les adresses de fronts de lecture décalés en arrière 25 et 24 pour atteindre ensuite l'adresse du front de lecture 21. Lorsqu'intervient la coïncidence des front d'écriture 23 et front de lecture décalé le plus en arrière 25, puis celle des fronts 23 et 24, le double comparateur 8 fournit alors des signaux permettant à la machine d'états 1 1 de signaler par le signal de remplissage 10 que le seuil de remplissage fixé par le décalage 15 vient être franchi dans le sens croissant. Autrement dit, on signale que la réserve de sécurité 15, correspondant au décalage, est entamée. En toute rigueur, on détecte que le remplissage atteint en croissant le front 24, et que la réserve 15 risque d'être entamée si, comme c'est probable, le remplissage se poursuit. Par contre, si l'on s'intéresse au front 25 de plus grand décalage et à la réserve qu'il forme avec le front arrière 21 (ici la réserve 15 augmentée d'une unité) cette réserve est entamée avec certitude. Les fronts 24, 25 définissent ainsi ici fonctionnellement un seuil unique associé. Bien entendu, il aurait pu être prévu que les deux adresses 24 et 25 de seuils de remplissage soient disjointes, avec entre elles une zone tampon. Si le système prend des mesures pour ralentir les écritures, la zone 12 décroît et il y a de nouveau coïncidence des fronts ci-dessus, mais dans l'ordre inverse. La machine d'états 1 1 indique alors que le seuil de remplissage vient d'être franchi dans le sens décroissant. Autrement dit, on signale que la réserve de sécurité 15 est de nouveau disponible. Comme il s'agit en définitive de détecter la présence ou non d'une réserve de sécurité de remplissage comme 15, accolée ici derrière le front arrière de lecture 21 dans la figure 1, on conçoit que cette réserve aurait, de façon équivalente, tout aussi bien pu être accolée devant le front avant d'écriture 23. Auquel cas, on associerait au pointeur d'écriture 4 un pointeur décalé en avant (ou plusieurs) et on détecterait sa coïncidence avec le pointeur de lecture 5. Si, contrairement à l'exemple de la figure 1, on cherchait à détecter un vidage excessif de la mémoire 1, le principe exposé ci-dessus (pointeur(s) décalé(s) en arrière ou en avant) reste valable. Par exemple, on peut associer au pointeur d'écriture 4 (ou un des) pointeur(s) décalé(s) en arrière pour marquer une réserve de sécurité de vidage et on détecte sa coïncidence avec le pointeur de lecture 5. On remarquera de même qu'un décalage dans un sens équivaut au décalage complémentaire (par rapport à la taille totale de la mémoire 1) dans l'autre sens. Dans certaines applications, il peut être utile de créer une sorte d'hystérésis sur la taille de la réserve (15), c'est-à-dire qu'on engendre une paire de décalages pour la détection du franchissement du seuil de remplissage dans un sens et on engendre une paire différente de décalages pour la détection du franchissement, dans l'autre sens, d'un autre seuil. REVENDICATIONS 1. - Procédé de gestion d'une mémoire élastique (1), dont on remplit et vide une zone de données de taille variable (12) indiquée par deux pointeurs d'adresses de début (23) et de fin (21) de zone, dans une plage d'adresses de taille déterminée, procédé caractérisé par le fait qu'on modifie fictivement la taille de la zone (12), par décalage déterminé (15) de l'adresse (21) de l'un des pointeurs, on détecte qu un seuil de remplissage de la mémoire est atteint en recherchant l'identité entre l'adresse décalée (24; 25) et une adresse (23) correspondant à l'autre pointeur et on modifie en conséquence le vidage/remplissage de la mémoire. 2.- Procédé selon la revendication 1, dans lequel on déplace la zone (12) dans la plage d'adresses, par écriture à l'adresse du pointeur de début (23) et par lecture à l'adresse du pointeur de fin (21), selon une séquence d'adresses suivant un code de Gray. 3.- Procédé selon l'une des revendications 1 et 2, dans lequel on engendre deux décalages de l'adresse de l'un des pointeurs (24, 25), et on détecte le sens de franchissement d'un seuil associé aux décalages d'après l'ordre dans lequel se produisent les identités correspondantes. 4.-Procédé selon la revendication 3, dans lequel on engendre une paire de décalages pour la détection du franchissement du seuil de remplissage dans un sens et on engendre une paire différente de décalages pour la détection du franchissement, dans l'autre sens, d'un autre seuil. 5.- Dispositif de gestion d'une mémoire élastique, pour la mise en oeuvre du procédé de la revendication 1, agencé pour écrire et lire dans une zone de données de taille variable (12) délimitée par deux pointeurs (4, 5) d'adresses (23, 21) à l'intérieur d'une plage d'adresses, caractérisé par le fait qu'il comporte des moyens (6) pour décaler l'adresse de l'un des pointeurs (5) et des moyens comparateurs (8) pour détecter l'identité entre l'adresse décalée (24; 25) et une adresse (23) correspondant à 1' autre pointeur (4). 6.- Dispositif selon la revendication 5, dans lequel il est prévu des moyens de comptage (4, 5, 6) selon le code de Gray, pour fournir les pointeurs d'adresses. 7.- Dispositif selon la revendication 6, dans lequel les moyens de comptage comportent au moins deux compteurs selon le code de Gray, à commande d'avance commune (5, 6), agencés pour présenter entre eux ledit décalage d'adresses (15). 8.- Dispositif selon la revendication 7, dans lequel les moyens comparateurs comportent, en sortie des compteurs (4, 6), des portes OU exclusif (81 - 88) de comparaison d'adresses bit à bit. 9.- Dispositif selon la revendication 8, dans lequel les portes OU exclusif (81 - 88), montées en parallèle, sont reliées à l'entrée d'une porte OU (89).