Brevet FR2655445A1 — publié le 19910607

DESCRIPTION L'invention concerne un dispositif de contrôle pour une mémoire tampon qui est organisée selon au moins une classe de E éléments-mémoire munis de clés et répartis sur E voies, la mémoire étant adressée par des adresses ayant des champs d'indices de classe et/ou de clé, chaque voie étant munie d'au moins un comparateur des adresses d'entrée et des adresses stockées et lorsque l'adresse d'entrée n Lest pas trouvée (échec) dans la mémoire tampon, le dispositif permet de la trouver dans une mémoire source puis de transférer le contenu des informations qui s'y rapportent vers la mémoire tampon suivant une méthode de remplacement. L'invention concerne également une méthode de gestion de données numériques mise en oeuvre dans une mémoire tampon. Les méthodes de remplacement s'appliquent plus particulièrement à des systèmes comportant une mémoire hiérarchisée et/ou une mémoire virtuelle. Elles concernent donc en particulier la plupart des ordinateurs. Elles permettent de gérer la mémoire paginée (mémoire centrale), les caches (mémoire cache) et les traducteurs d'adresses (Translation Lookaside Buffers TLB) de la plupart des ordinateurs. Un système à mémoire hiérarchisée comporte un processeur et un organe de stockage d'informations ayant une grande capacité de stockage appelé mémoire de masse (disques durs, bandes...). Un tel organe de stockage est bien plus lent que le processeur, et il n'est pas possible de concevoir un système basé uniquement sur ces deux éléments. On intercale donc entre le processeur et cet organe de stockage un certain nombre de niveaux de mémoire, ce nombre dépendant de la complexité du système considéré. Plus le niveau de mémoire considéré est proche du processeur plus ce niveau a une vitesse de fonctionnement élevée, mais plus il a une capacité de stockage faible. De ce fait chaque niveau de mémoire ne contient qu'une partie des informations que contient le niveau qui le suit immédiatement du côté de la mémoire de masse.La capacité d'un niveau étant limitée, il s'ensuit que lorsque le processeur délivre une adresse qui est absente de ce niveau, le système de gestion de la mémoire doit chercher l'information dans un niveau amont et la charger dans ledit niveau. Si ledit niveau est plein, le système de gestion de la mémoire doit supprimer l'information qui était présente dans un des éléments-mémoire constitutifs de la mémoire tampon afin d'allouer sa place à la nouvelle information. Il est donc nécessaire de définir une méthode de remplacement qui permette de conserver dans les niveaux proches du processeur les informations les plus utiles. Lorsqu'il est nécessaire d'aller la chercher très en amont dans le système hiérarchisé, il y a une perte considérable de temps. Un problème de remplacement similaire se pose dans les systèmes à mémoire virtuelle. Pour éviter de traduire à chaque accès le numéro de page virtuelle en numéro de page physique, on conserve dans un petit registre tampon appelé traducteur d'adresses (Translation Lookaside Buffers TLB) quelques couples "page virtuelle, page physique" qui ont été utilisés. Quand une nouvelle page est adressée il faut choisir le couple à supprimer du traducteur d'adresses. Différents algorithmes de remplacement ont été proposés notamment ceux décrits dans "Cache memories, A.J. SMITH, Computing Surveys, vol.14, n03, 1982". Les trois algorithmes les plus classiques sont LRU (Least Recently Used en langue anglaise) cet algorithme consiste à remplacer l'élément qui est resté inutilisé le plus longtemps. FIFO (First In First Out) : cet algorithme consiste à remplacer l'élément qui est présent depuis le plus longtemps. Random : cet algorithme remplace un élément au hasard. Il est possible de comparer les algorithmes entre eux en déterminant un taux d'échec c'est-à-dire le taux d'adresses appelées par le processeur qui ne sont pas trouvées dans la mémoire considérée et qu'il faut donc aller chercher dans une mémoire placée en amont. Dans la plupart des cas l'algorithme LRU donne les meilleures performances. En effet la plupart des programmes tendent à ne pas réutiliser des adresses (donc des éléments-mémoire) qui n'ont pas été utilisés depuis longtemps. Il existe toutefois un cas particulier simple où cet algorithme n'est pas satisfaisant : si un programme adresse cycliquement une certaine zone mémoire successivement par des adresses croissantes, puis en recommençant, et si cette zone mémoire a une taille telle qu'elle renferme plus d'éléments-mémoire à adresser que ne peut en contenir la mémoire tampon; alors à chaque fois qu'un nouvel élément-mémoire est adressé un échec se produit et un remplacement est nécessaire. L'algorithme FIFO est moins performant que l'algorithme LRU. Dans le cas particulier des boucles il présente le même inconvénient que l'algorithme LRU. L'algorithme Random a des performances voisines de celles de l'algorithme FIFO. Toutefois il ne présente pas d'inconvénient particulier en cas de boucles. Les situations où des difficultés d'exploitation de ces méthodes classiques apparaissent sont multiples - soit qu'il n'est pas aisé de concevoir des circuits compacts les mettant en oeuvre, - soit que des fonctionnements en boucle donnent lieu à des difficultés de remplacement, - soit que l'exploitation de la totalité de la mémoire soit mal réalisée, - soit que la mémoire possède un nombre élevé d'éléments E par classe. Généralement plusieurs de ces difficultés apparaissent simultanément. Le problème qui est posé est de déterminer une méthode de remplacement et un dispositif de contrôle qui soient plus efficaces que les précédents pour traiter au mieux ces différentes difficultés selon des conditions d'exploitation variées. Ce problème est résolu par l'invention à l'aide d'un dispositif de contrôle qui comprend - pour chaque élément-mémoire, un organe de stockage de B bits (B(E), avec E multiple de B, qui permet de repérer si l'élément-mémoire a été utilisé par les adresses d'entrée au cours de phases successives antérieures, une phase pouvant couvrir l'analyse de plusieurs adresses d'entrée, - des premiers moyens pour scruter au cours desdites phases successives au moins un des B bits de chacun des éléments-mémoire; les E bits de même rang des E éléments-mémoire d'une même classe, formant une banque BKC, étant scrutés au cours d'une même phase, sous le contrôle d'un compteur de phases, lesdits premiers moyens comprenant en outre un compteur de transitions qui, au cours d'une même phase, est incrémenté d'une unité lorsqu'au moins un des bits scrutés d'un élémentmémoire a changé d'état, ledit compteur délivrant, après un nombre E/B dtincrémentations, un signal de fin de phase, celui-ci activant des moyens de forçage qui forcent un état logique de non succès dans la banque BKC+1 à utiliser à la phase suivante, - des seconds moyens pour sélectionner des éléments-mémoire qui n'ont pas été adressés ni au cours des B-i phases précédentes ni sur la partie de la phase en cours qui précède l'instant d'analyse de l'adresse d'entrée en détectant que tous les bits de leur organe de stockage sont à l'état logique de non-succès, - des troisièmes moyens pour sélectionner un des élémentsmémoire parmi lesdits éléments-mémoire non adressés précédents pour y effectuer le remplacement. Ainsi, pour un élément-mémoire donné, lorsque les B bits de son organe de stockage sont à l'état de "succès" ceci signifie que cet élément-mémoire vient d'être adressé et qu'il n'est plus disponible pendant cette phase. Pour la même raison si l'organe de stockage renferme certains bits à l'état de "non succès", le nombre de ces bits va permettre d'en déduire l'ancienneté du dernier appel de cet élément-mémoire et selon la méthode proposée de permettre son utilisation pour effectuer le remplacement. Tous les organes de stockage des E éléments-mémoire appartenant à la même classe K sont répartis sur les E voies différentes. Dans une même classe les bits de même rang des organes de stockage sont lus simultanément. Tous ces E bits de même rang C constituent la banque BKC et peuvent incrémenter au cours d'une même phase un compteur de transitions A à condition qu'ils soient passés de l'état de non succès à l'état de succès au cours de cette phase. Pour opérer de la sorte lesdits premiers moyens peuvent comprendre E multiplexeurs placés chacun entre la sortie des E organes de stockage et le compteur de transitions, les multiplexeurs étant contrôlés par le compteur de phases.Il est également possible de ne pas utiliser de multiplexeurs, les sorties des E organes de stockage étant alors réunies directement au compteur de transitions qui dans ce cas est incrémenté d'une unité si une ou plusieurs des entrées sont passées d'un état de non-succès à un état de succès au cours du traitement d'une adresse. Pour cela le compteur de transitions possède E.B entrées connectées aux B bits des E éléments-mémoire d'une même classe. Avantageusement cette seconde disposition permet une réalisation matérielle plus compacte. Lorsqu'un état d'échec est détecté une opération de remplacement doit être effectuée. Pour cela lesdits seconds moyens déterminent pour chaque organe de stockage si tous les bits sont à l'état logique de non-succès. Dans le cas général plusieurs éléments-mémoire ont tous leurs bits à l'état de non succès". Parmi ceux-ci, selon l'invention, lesdits troisièmes moyens de sélection déterminent un premier élément-mémoire disponible en testant, selon un classement préétabli, chacun des éléments-mémoire non adressés. Avantageusement le classement préétabli peut être mis en oeuvre dans un circuit qui privilégie la vitesse. La clé et la donnée qui se rapportent à l'adresse concernée sont donc écrites dans cet élémentmémoire sélectionné. Le dispositif de contrôle selon l'invention peut constituer un circuit qui peut être intégré à la mémoire tampon et/ou au processeur. Mais il est également possible de réaliser l'invention selon une méthode de remplacement qui est mise en oeuvre par programme dans un calculateur. Dans ce cas il s'agit d'une méthode de gestion de données numériques dans une mémoire tampon formée de E voies, chaque voie étant formée d'éléments-mémoire repérés par une clé, les voies étant divisées en classes, chaque classe étant formée de E élémentsmémoire pris un à un dans chaque voie, la mémoire tampon recevant des adresses d'entrée ayant des indices de classe et/ou de clé, la méthode opérant une recherche, dans la mémoire tampon, d'une adresse d'entrée en la comparant aux indices de classes et/ou aux clés d'adresses stockées, - et lorsque l'adresse d'entrée est trouvée (succès), la méthode met en oeuvre des opérations de lecture/écriture de la mémoire tampon, - et lorsque l'adresse d'entrée n'est pas trouvée (échec), la méthode met en oeuvre une recherche dans une mémoire source puis un transfert du contenu des informations qui se rapportent à cette adresse d'entrée vers la mémoire tampon suivant une méthode de remplacement, caractérisé en ce que, à chaque fois qu'une adresse est présentée en entrée, la méthode de remplacement effectue le stockage des succès de la comparaison dans B variables logiques Po...Pc...PB~1 associées à chaque élément-mémoire avec B=E/k (k entier > 1) la méthode se subdivisant en deux branches - une branche succès, auquel cas l'étape de lecture/écriture des informations selon l'adresse d'entrée est effectuée, - une branche échec, auquel cas la méthode comprend les étapes suivantes sélection des éléments-mémoire ayant leur variable logique PC+1 à l'état logique de non succès, sélection, parmi ces éléments-mémoire, de celui qui est muni d'un accès privilégié pour y effectuer le remplacement en écrivant les informations et les champs de clé selon l'adresse d'entrée, l'une et l'autre branche comprenant ensuite les étapes suivantes - pour tous les E éléments-mémoire d'une même classe, mise à jour puis scrutation des B variables logiques au cours de B phases successives et, dans une même phase; comptage du nombre A de changements d'états des bits PC d'un même rang C formant ensemble une banque BKC, - comparaison du nombre A de changements d'états avec la valeur E/B et lorsque A et lorsque A=E/B, remise à l'état non succès des bits PC+1 de la banque BRC+l suivante puis incrémentation à C+1 (modulo B) du comptage de rang, remise à zéro du compteur A et passage à l'adresse suivante. La sélection des éléments-mémoire, en testant que leur variable logique PC+1 est à l'état logique de non-succès, est plus facile à opérer dans une mise en oeuvre par programme que la sélection qui consiste à tester que toutes les variables Po à #B-1 sont à l'état logique de non-succès. Cette dernière solution est mieux adaptée à une réalisation matérielle d'un dispositif de contrôle du fait que le bit PC+1 à tester change en fonction de la banque adressée. La méthode de remplacement selon l'invention garantit que pour chaque classe on dispose toujours d'élémentsmémoire ayant toutes leurs variables logiques P0. ..... #B-1 à l'état logique de non-succès, par exemple l'état 0. En effet considérons la situation au début de la dernière phase sur une durée de B phases. Si l'on suppose que sur les B-l phases précédentes toutes les présentations d'adresses d'entrée ont donné lieu à un succès, comme il ne peut y avoir qu'au maximum E/B succès par phase, il y a donc au maximum eu (B-1).E/B succès sur des éléments-mémoire tous différents. Comme il ne peut y avoir que B.E/B succès sur B phases (car au début d'une phase tous les bits d'une banque sont tous remis à jour), il reste obligatoirement au minimum E/B éléments-mémoire ayant tous leurs bits à zéro au début de la Bième phase.Comme au cours d'une phase, d'après la méthode selon l'invention, il n'est pas possible d'adresser plus de E/B éléments-mémoire il y a donc assez d'éléments-mémoire jus qu a la fin de la Bième phase ayant tous leurs bits à zéro. C'est la remise à zéro, en fin de phase, de tous les bits d'une banque qui garantit cette propriété. La comparaison des clés d'entrée avec les clés stockées est généralement effectuée sous le contrôle d'un bit de présence L propre à chaque élément-mémoire. Ce bit de présence est mis à un certain état logique lors de l'écriture de cet élément-mémoire. L'état de ce bit de présence révèle ainsi si l'élément-mémoire est occupé ou inoccupé. Ceci s'avère utile lors du premier chargement de la mémoire où une situation d'erreur peut apparaître sans l'existence de ce bit de présence. Dans la phase de chargement des éléments-mémoire au début d'un cycle de fonctionnement il peut être utile de différer la mise en oeuvre du mécanisme de remplacement jusqu'à ce que tous les éléments-mémoire disponibles de la classe considérée aient été utilisés. Pour cela au lieu d'un bit de présence L affecté à un bloc de donnée on utilise un bit de présence Q affecté à tous les éléments-mémoire d'une même classe. Ce bit Q est testé, et si une situation de non-succès est détectée le chargement de la donnée est alors effectué dans un élément-mémoire libre. Lorsque ce bit change d'état tous les éléments-mémoire de la classe ont été utilisés et contiennent des informations valides. Ainsi avantageusement on obtient de meilleures performances car on remplit toujours complètement la classe avant d'opérer le premier remplacement. Dans ce cas la méthode de remplacement comprend pour chaque classe, préalablement au remplacement une étape de chargement de tous les éléments-mémoire inoccupés d'une même classe, ladite étape comprenant la détection du changement d'état d'un bit de présence unique affecté à la signalisation de l'occupation de tous les éléments-mémoire de ladite classe. Pour opérer préalablement l'étape de chargement l'invention concerne alors un dispositif de contrôle qui comprend un élément de stockage d'un bit de présence unique pour tous les éléments-mémoire d'une même classe afin d'opérer le chargement de tous les éléments-mémoire inoccupés de ladite classe préalablement au remplacement, ce bit de présence contrôlant le compteur de transitions de ladite classe pour qu'il opère un comptage modulo E/B si le bit de présence indique le chargement complet des éléments-mémoire inoccupés et un comptage modulo E dans le cas inverse. L'invention peut aussi concerner un calculateur agencé pour mettre en oeuvre cette méthode de gestion de données. L'invention sera mieux comprise à l'aide des figures suivantes données à titre d'exemple non limitatif et qui représentent Figure 1 : un système général de traitement de données mettant en relief les échanges entre différents niveaux de mémoire. Figure 2 : un schéma de l'organisation générale d'une mémoire tampon. Figure 3 : un schéma d'un dispositif de contrôle selon l'invention. Figures 4A, 4B : un chronogramme se rapportant au schéma de la figure 3. Figure 5 : une représentation de l'organisation des organes de stockage. Figure 6 : un exemple de transfert des données opéré dans les registres sur plusieurs éléments-mémoire. Figure 7 : un exemple de l'évolution sur plusieurs phases du contenu d'un registre. Figure 8 : un schéma d'un circuit de remplacement dans un élément-mémoire prédéterminé. Figures 9A1 9B : un organigramme concernant les différentes étapes de la méthode de gestion de données selon l'invention. La description qui va suivre opère la distinction entre le terme "donnée" qui est la valeur à échanger et le terme "adresse" qui est l'adresse de cette valeur. Dans un sens général bien évidemment toutes deux sont par essence des données numériques qui sont celles gérées selon l'invention. La figure 1 représente un système général de traitement de données numériques où sont plus particulièrement mis en relief les échanges qui s'opèrent entre les différents niveaux successifs de mémoire. Un tel système va comprendre notamment un processeur 10 qui pour fonctionner va opérer avec les couples adresses-données. Ainsi il va pouvoir délivrer une adresse afin de recevoir une donnée ou bien il va délivrer une donnée et une adresse à laquelle cette donnée doit être transmise. Dans la forme la plus générale de ce système, le processeur 10 va délivrer une adresse virtuelle ADVIR à un traducteur d'adresses Il qui à son tour va délivrer une adresse physique ADPHY. Celle-ci va permettre de trouver l'élément-mémoire où la donnée doit être soit lue soit transmise.Les systèmes importants vont disposer de plusieurs niveaux de mémoire, par exemple une mémoire cache 12, une mémoire centrale 13, une mémoire de masse 14. L'adresse physique délivrée par le traducteur d'adresses 11 va parvenir à la mémoire cache 12. Deux cas peuvent se présenter - la mémoire cache 12 contient la donnée adressée (ou la place pour cette donnée) et dans ce cas elle la transmet (ou la reçoit) vers (ou en provenance du) le processeur, - la mémoire cache 12 ne contient pas la donnée (ou la place pour cette donnée) et dans ce cas elle la requiert de la mémoire d'amont du niveau le plus proche en l'occurence ici d'une mémoire centrale 13. La mémoire centrale 13 la transmet alors à la mémoire cache 12 qui à son tour la transmet au processeur. Les mêmes mécanismes d'échanges opèrent entre la mémoire centrale 13 et la mémoire de masse 14. Pour recevoir une nouvelle donnée il est nécessaire de mettre en oeuvre une méthode de remplacement des données anciennes.- Celle-ci s'applique pour les remplacements effectués aussi bien dans le traducteur d'adresses Il que dans la mémoire de cache 12 ou que dans la mémoire centrale 13. Pour mettre en oeuvre les algorithmes LRU, FIFO, Random déjà présentés, les différents niveaux de mémoire doivent disposer chacun d'un dispositif de contrôle du remplacement. L'organisation générale de la mémoire cache ainsi contrôlée est représentée sur le schéma de la figure 2. Une organisation similaire s'applique pour les autres niveaux de mémoire. Le dispositif reçoit une adresse 20 qui comprend généralement plusieurs champs : un champ de clé CE, un champ de classe K et un champ d'indice de mot de donnée IM. La mémoire est structurée selon plusieurs voies V1, V2... Une voie (par exemple V1) comprend plusieurs éléments-mémoire EO, El, E2... Chaque élément-mémoire stocke d'une part la clé CE correspondant aux données et d'autre part les données proprement dites dans des blocs BL qui peuvent chacun stocker plusieurs mots de données. Un champ de classe K1 permet de distinguer les éléments-mémoire entre eux dans une voie donnée. Ce même champ de classe KI se retrouve sur plusieurs voies. Ceci est représenté sur la figure 2 sous la forme de couches correspondant à des classes Kî, K2... Le champ d'indice de mot de donnée IM de l'adresse permet de distinguer les différentes données dans un bloc d'informations associées BL. Généralement un élément-mémoire EO contient pour chaque bloc un bit de présence L qui permet au processeur de connaître si une donnée a déjà été stockée à cette position depuis l'initialisation du dispositif. Ce bit de présence est testé en même temps que l'adresse d'entrée est elle-même testée. Lorsqu'une adresse d'entrée est reçue, le dispositif de contrôle détermine la classe et la clé puis teste la clé. Si celle-ci est trouvée dans la mémoire tampon la donnée concernée présente dans le bloc BL correspondant est transmise (bus IF). Si la clé n'est pas trouvée, la donnée concernée doit être cherchée dans la mémoire d'amont puis la clé d'entrée et la donnée sont inscrites dans la mémoire du niveau en cours d'opération. Il est donc nécessaire de remplacer une des données jugées anciennes par la donnée qui vient juste d'être adressée. Ceci est effectué par un dispositif de contrôle qui gère le remplacement. Le dispositif de contrôle selon l'invention est représenté sur la figure 3. Pour la clarté de l'exposé le dispositif de contrôle de la figure 3 est limité à la gestion de seulement deux éléments-mémoire appelés (K1rV1) et (K1rV2) appartenant à la même classe K1 mais situés sur deux voies VI et V2 différentes. A chaque élément-mémoire est associé un organe de stockage 301, 302 d'un mot logique formé de plusieurs bits Po PC -PB-1 Cet organe est par exemple un registre formé de bascules RS. Ce mot logique va conserver la trace des adressages antérieurs selon une méthode dynamique de renouvellement qui permet au dispositif de contrôle d'opérer avec un taux de succès élevé dans des conditions variées. Les registres 301r 302 peuvent recevoir leurs informations par deux voies différentes. Ils sont notamment chargés respectivement par des comparateurs 311r 312 qui comparent une clé CR d'une adresse d'entrée à chercher avec les clés CEl, CE2 présentes respectivement dans les éléments-mémoire (Kî,VI) et (K1,V2). Les comparateurs 311r 312 sont respectivement validés par les bits de présence Li et L2. En cas de succès, les comparateurs 311r 312 délivrent des signaux COI, COz à un état logique déterminé. Pour la suite de la description l'état de succès sera représenté par le niveau logique 1. Les portes logiques sont donc décrites en fonction de ce niveau logique I. Une convention inverse peut être choisie et dans ce cas l'homme du métier peut sans difficulté modifier le type des portes logiques. Les signaux COi, C02 traversent respectivement des portes OU 321 322 et actionnent l'entrée forçage à 1 (set) des bascules RS. Un niveau logique 0 pour COi, C02 est inopérant. Les bascules RS de chaque registre 3 1 r 302 sont lues à l'aide de multiplexeurs 331r 332 qui sont commandés simultanément par un compteur de phases 34 (compteur C). Dans une même phase les bascules de même rang des registres 3oui, 302 sont lues. Si la lecture concerne par exemple les bits P1, ceux-ci arrivent sur un compteur de transition 35 (compteur A) qui comptabilise pour tous les bits P1 leur changement de l'état logique O (non succès) à l'état logique 1 (succès). En fonction de l'état du compteur de phase 34 tous les bits Po à #B-I sont ainsi testés. Une autre variante consiste à ne pas utiliser les multiplexeurs 331r 332, mais un compteur de transitions 35 possédant E.B entrées reliées aux sorties des bascules RS de la classe. Le compteur est incrémenté d'une unité par le passage à 1 d'une ou de plusieurs bascules au cours du traitement de l'adresse considérée. Dans les deux cas, le compteur de transition 35 opère un comptage modulo E/B (E : nombre d'éléments-mémoire par voie, B : nombre de bits du mot logique). Lorsque le comptage atteint E/B il délivre un signal (connexion 30) qui incrémente le compteur de phases 34 et le bit suivant de chaque mot logique est testé. Le compteur de phases 34 passe ainsi d'une valeur C à une valeur C+î (modulo B) qui est transmise à une logique de forçage 38 par un sélecteur 36 après validation (connexion 37) par la sortie du compteur de transition 35. La logique de forçage 38 active l'entrée remise à zéro (reset) de la bascule RS qui suit celle qui a provoqué le comptage jus qu a E/B du compteur de transition 35. Ainsi lorsque les bits PI testés ont provoqué par leur transition un comptage à E/B, les bits suivants P2 de tous les registres sont mis à zéro. Ceci permet de pouvoir stocker un adressage de cet élément-mémoire (succès dans cet élément-mémoire) à la phase suivante C+1 si celui-ci se produit. Sinon ce bit P2 restera à zéro. Lorsque le compteur de transition 35 n'atteint pas la valeur E/B aucune des actions précédentes n'est effectuée et le dispositif de contrôle passe à l'analyse de l'adresse suivante. Quand une adresse d'entrée est testée elle peut ne pas être trouvée dans la mémoire gérée par le dispositif de contrôle. La procédure de remplacement proprement dite est alors mise en oeuvre. Pour déterminer l'élément-mémoire dans lequel va s'opérer le remplacement il faut alors tester les états logiques des bits contenus dans les registres 3 1r 302 à l'aide respectivement d'une porte logique OU 391 392. Si l'un quelconque des bits d'un mot logique est à 1, l'élément-mémoire a été adressé durant les phases précédentes ou la phase en cours et n'est plus disponible. Si tous les bits du mot logique sont à zéro l'élément-mémoire n'a pas été référencé au cours des (B-l) phases précédentes ni jusqu'à l'instant où s'effectue l'analyse de l'adresse en cours.Si par exemple l'élément-mémoire (R1,V1) est disponible, la porte 391 délivre un signal DI1 à l'état logique O qui active une logique combinatoire 40. Celle-ci peut en effet recevoir des signaux analogues en provenance d'autres éléments-mémoire disponibles. Dans ce cas la logique combinatoire 40 sélectionne un des élémentsmémoire selon un critère prédéterminé. Ce critère peut privilégier la vitesse d'accès à l'élément-mémoire. Si par exemple la logique combinatoire 40 sélectionne l'élément-mémoire (K1,V1), elle délivre alors un signal INDI à l'état logique 1 à cet élément-mémoire, signal IND1 qui est validé par un signal S1 délivré par la porte NON-OU 41 qui détecte que tous les comparateurs 311, 312 n'ont pas détecté un succès (C01=O, CO2=O).Cette validation est effectuée par l'organe de validation 42 qui transmet le signal IND1 à la porte OU 321 qui met à 1 les bascules du registre 3 1 pour prendre en compte le succès de l'adressage dû au remplacement. La figure 3A représente un schéma d'une modification à apporter à la figure 3 pour que la méthode de remplacement opère avec préalablement une étape de chargement de tous les éléments-mémoire inoccupés. Pour cela un bit de présence Q concernant l'ensemble de la classe K1 est stocké dans une bascule 29. La bascule 29 et le compteur de transition 35 interagissent mutuellement l'un sur l'autre. Lorsque Q=O la bascule 29 (connexion 27) place le compteur de transition 35 pour opérer un comptage jusqu'à la valeur de seuil E. Lorsque le compteur de transition 35 atteint la valeur de seuil prévue il fait passer Q à 1 (connexion 28) et le compteur opère alors avec la valeur de seuil E/B. Le signal de fin de phase (connexion 28) est alors transmis par la connexion 37 comme précédemment vers le sélecteur 36.Pour opérer ces étapes de chargement une autre modification est à effectuer consistant à valider le fonctionnement des comparateurs 31l, 312... des éléments-mémoire non par les bits de présence L1, L2 mais par respectivement les sorties de portes logiques OU (non représentées) qui reçoivent chacune respectivement le bit de présence Q de la classe et le bit PO de l'élément-mémoire concerné. Une partie du diagramme des temps concernant le schéma de la figure 3 est représenté sur les figures 4A et 4B. La figure 4A se rapporte au cas où la comparaison des clés a donné lieu à un succès. La figure 4B se rapporte au cas où la comparaison des clés a donné lieu à un échec. Les niveaux logiques significatifs sont représentés en traits gras sur ces figures. On suppose que les événements décrits concernent uniquement l'élément-mémoire (ksi, V1). Dans le cas de la figure 4A une adresse d'entrée ADR donne lieu à un succès ce qui provoque le passage du signal C01 et du signal Si au niveau logique 1. Le passage à 1 du signal Si entraîne le transfert de la "donnée" proprement dite.Le passage à 1 du signal COi force un état logique 1 dans tous les bits Po à #B-i du registre. La situation de succès est ainsi conservée dans le registre. En supposant que le compteur de phase soit calé sur le bit Pc et en supposant qu'avant de passer à 1 le bit Pc était à l'état 0, il se produit alors une transition qui provoque une incrémentation INCA du compteur A. Simultanément le signal Dli passe au niveau logique 1 ce qui signifie que l'élément-mémoire El vient d'être utilisé et n'est plus disponible pendant la phase en cours ni pendant les (B-1) phases suivantes. Le signal INDI relatif à l'élément-mémoire (K7,V1) passe à l'état logique 0. Le système opère alors le traitement de fin de phase avec éventuellement mise à jour des compteurs A et C. L'analyse de l'adresse d'entrée est alors terminée et l'adresse suivante est analysée. Dans le cas de la figure 4B est représentée une situation d'échec pour tous les éléments-mémoire de la mémoire. L'adresse d'entrée ADR donne lieu à un échec ce qui provoque le passage des signaux COI et Si au niveau logique 0. On suppose de plus que le remplacement s'opère dans l'élément-mémoire (Kl,Vi) afin de faciliter la présentation du chronogramme. Son signal IND1 est donc à 1. Ce signal est validé par Si (niveau 1) ce qui provoque le chargement de la clé et de la donnée associée dans l'élément-mémoire. La porte OU 321 (figure 3) passe ainsi à 1 et provoque le passage à 1 des bits PO à PB~1 du registre 301. Le signal DI1 passe à 1 et fait redescendre IND1 à zéro pour indiquer que l'élément (K?,V1) n'est plus libre. Le remplacement qui est ainsi effectué se trouve alors mémorisé. La procédure qui suit devient alors identique à celle déjà décrite en cas de succès. La figure 5 représente l'organisation des différents registres de stockage. Comme cela a été expliqué préalablement une classe déterminée K1 est répartie sur plusieurs voies V1, V2... Pour une même classe Ki on dispose donc des éléments-mémoire (K1,V1),..., (K1,V3),...,(K1,V8) dans un cas de mémoire à 8 voies. En prenant pour exemple des registres stockant 4 bits Po à P31 à chaque élément-mémoire est associé un tel registre. Le compteur de phase va être pointé simultanément sur les bits de même rang appartenant à ces registres. L'organisation des registres de la figure 5 se présente sous une forme matricielle. Tous les bits de même rang, par exemple de rang 2, prennent le nom de banque BK2. Lors de l'opération de forçage à zéro (pour le rang C+1) décrite précédemment c'est toute la banque BKC+1 de rang suivant C+1 qui est concernée. Lorsque le compteur de phase a atteint le dernier bit du registre (P3 dans l'exemple) il revient à la position de départ Po. Pour bien mettre en évidence le changement d'état logique des bits P0. . #B-i des registres un exemple très simplifié est représenté sur la figure 6. Il concerne quatre éléments-mémoire (Ki,Vi), (Ki,V2), (Ki,V3), (K1,V4) ayant chacun un registre à seulement deux bascules pour stocker deux bits Po et P1. La valeur E/B est donc égale à 2. A titre d'exemple, au départ, après le temps tO1 les bits P1 des éléments (Ki,V1) et (Ki,V2) sont à 1 et tous les autres bits sont à zéro. Le compteur de phase (C=O) est pointé sur la banque BRO. Le compteur A est à 0. Au temps t=t1 le test de l'adresse d'entrée se traduit par un succès dans l'élément-mémoire (Ki,Vi). Ceci provoque pour cet élément-mémoire, le passage de Po du niveau logique O au niveau logique 1 (repéré par une *). Le compteur de transition compte une transition. L'adresse d'entrée suivante est testée et donne lieu au temps t=t2 à un succès dans l'élément-mémoire (K1rV3). Pour cet élément-mémoire ceci provoque le passage de PO et P1 du niveau logique O au niveau logique 1 (repéré par une *). Le compteur de transition compte une transition supplémentaire. Il atteint la valeur E/B=2 ce qui provoque au temps t=t3 un changement de phase (C=1) avec simultanément forçage à zéro de toute la banque suivante c'est-à-dire BRI. Tous les bits P1 sont mis à zéro. Le compteur de transition est remis à zéro. Au temps t=t4 le test de l'adresse d'entrée se traduit par un échec dans tous les éléments-mémoire. En supposant que l'élément-mémoire retenu pour le remplacement soit l'élément-mémoire (Kî,V2), les bits Po et P1 de cet élémentmémoire passent à l'état logique 1 (repéré par une *). Le compteur de transition compte une transition. Au temps t=t5 le test de l'adresse d'entrée se traduit par un échec dans tous les éléments-mémoire. En supposant que l'élément-mémoire retenu pour le remplacement soit l'élément-mémoire (Kî;V4), les bits Po et Pj de cet élémentmémoire passent à l'état logique 1 (repéré par une *). Le compteur de transition compte une transition supplémentaire. Il atteint la valeur E/B=2 ce qui provoque un changement de phase (C=O) pour t=t6 avec forçage à zéro de toute la banque suivante c'est-à-dire BKo. Le compteur de transition est remis à zéro. Les bits Po à #B-i d'un registre d'un élément-mémoire déterminé représentent le nombre de fois et l'époque à laquelle cet élément-mémoire a été adressé. Ceci est représenté sur la figure 7 pour différentes situations. Dans le cas I le compteur de phase opère sur la banque BK4, tous les bits du registre sont au niveau logique 1 ce qui signifie que cet élément-mémoire vient d'être adressé pendant la phase en cours (et peut être aussi avant). Dans le cas Il le compteur de phase opère sur la banque BKs. Le bit P5 est à zéro et tous les autres bits sont à 1. Ceci signifie que cet élément-mémoire n'a pas été adressé pour la phase en cours mais a été adressé à la phase précédente, et peut-être avant. Dans le cas III le compteur de phase opère sur la banque BK3. Les bits P1, P2 et P3 sont à zéro et tous les autres bits sont à 1. Ceci signifie que cet élément-mémoire n'a pas été adressé pour la phase en cours ni au cours des deux phases précédentes mais par contre a été adressé à la troisième phase précédente et peut-être avant. Dans le cas IV le compteur de phase opère sur la banque BK1. Les bits P2 et P3 sont au niveau logique 1 et tous les autres bits sont au niveau logique zéro. Ceci signifie que cet élément-mémoire n'a pas été adressé pour la phase en cours ni au cours des cinq phases précédentes. Les moyens qui sélectionnent dans une classe donnée l'élément-mémoire dans lequel doit s'effectuer le remplacement peuvent opérer selon un critère prédéterminé sur l'un quelconque de ces éléments-mémoire ayant tous leurs bits Po à Pg-l à O (non-succès). Préférentiellement selon l'invention ce critère prédéterminé va consister à choisir un élément-mémoire selon un classement prédéterminé qui privilégie la vitesse d'accès, par exemple selon l'ordre des indices de voie, à l'aide du circuit représenté sur la figure 8. Ainsi avantageusement la sélection est faite avec une grande rapidité. La figure 8 concerne 4 éléments-mémoire d'une même classe mais ceci n'est nullement limitatif. Considérons les voies V1 à V4 dont les indices de voies vont en augmentant. Les moyens de sélection comprennent alors 4 portes logiques - une porte inverseuse qui reçoit le signal Dli (figure 3) de la première voie, - une porte ET 82 qui reçoit le signal Dli de la voie précédente et le signal DI2 de la deuxième voie qui est appliqué inversé, - une porte ET 83 qui reçoit les signaux DI1 et DI2 des deux voies précédentes et le signal DI3 de la troisième voie qui est appliqué inversé, - une porte ET 84 qui reçoit les signaux Dli, DI2 et DI3 des trois voies précédentes et le signal DIs de la quatrième voie qui est appliqué inversé. Lorsqu'il y a un plus grand nombre de voies le même mécanisme itératif est appliqué. Ainsi à l'aide du circuit de la figure 8, il est possible d'opérer un classement des voies selon un classement prédéterminé. Tout autre classement que celui présenté peut être utilisé. Ce classement est par exemple ici celui des indices de voies. Ainsi sur la figure 8, l'élément sélectionné sera celui ayant l'indice le plus faible. L'avantage réside dans la rapidité de fonctionnement d'un tel circuit qui ne nécessite qu'un étage logique entre les signaux DI et les signaux IND. Le dispositif de contrôle qui vient d'être décrit peut être exploité pour gérer les mécanismes de remplacement de mémoires de différentes natures. Il peut s'agir par exemple de traducteur d'adresses ou de mémoire cache ou de mémoire centrale pour gérer leurs échanges avec les mémoires d'amont. Egalement, la même méthode de remplacement peut être utilisée pour programmer un calculateur ou un processeur afin de gérer ses échanges avec les mémoires environnantes. L'organigramme de la méthode est représenté sur les figures 9A et 9B. Dans une étape 102 d'initialisation un compteur de phases C et un compteur de transitions A par classe sont mis à zéro ainsi que tous les bits PO à PB-1 de tous les éléments-mémoire. Le bit de présence L s'il existe est mis à 0. Etape 104 :introduction de l'adresse d'entrée Etape 106 : sélection de la classe de l'adresse d'entrée et détermination de la clé, Etape 108 : comparaison de la clé de l'adresse d'entrée avec les clés stockées et vérification que le bit de présence L a été activé lorsqu'il y a succès (branche 109) il y a sélection (étape 110) de l'élément-mémoire ayant l'adresse concernée puis lecture ou écriture de la "donnée" (étape 112) selon l'opération à effectuer. lorsqu'il y a échec dans tous les éléments-mémoire il faut opérer une procédure de remplacement (branche 111). Celle-ci comprend la sélection de tous les éléments-mémoire ayant leur bit P+1 à l'état logique zéro (ou bien ceux ayant tous leurs bits Po...PB~1 à l'état logique zéro) (étape 114), puis sélection parmi ceux-ci de l'élément-mémoire ayant un numéro d'ordre prédéterminé (étape 116). Enfin écriture des champs de clé et des données relatives à l'adresse d'entrée dans l'élément-mémoire sélectionné de la mémoire tampon (étape 118). Le bit de présence L de l'élément-mémoire concerné est mis à l'état logique 1 (occupé) (étape 119). En cas de succès ou en cas d'échec (dans toute la mémoire) la méthode tient compte du nombre et de la nature des opérations effectuées. Lorsqu'un élément-mémoire a été adressé, que ce soit après une situation de succès ou une situation d'échec suivi d'un remplacement, tous les bits PO...Pg~1 de cet élément-mémoire sont mis à l'état logique 1 (étape 120). Le compteur de phase étant pointé sur la banque BKC, il y a comparaison pour le bit de cette banque, correspondant à l'élément-mémoire adressé, entre son état avant et après son éventuel passage à 1 pour détecter sa transition (étape 122). Si les deux états sont différents, il y a incrémentation du compteur A (étape 124). Sinon le compteur reste inchangé. La valeur de ce compteur est testée (étape 126). Si sa valeur est inférieure à la valeur E/B, l'adresse d'entrée suivante est analysée (retour à l'étape 104). Si sa valeur est égale à la valeur E/B ce compteur A est remis à zéro, le compteur de phase C est incrémenté (étape 128) pour se pointer sur la banque suivante BKC+i. Si le compteur de phase atteint la valeur B du nombre de variables logiques (étape 130) il est remis à zéro (étape 132) pour revenir à la première position et opérer cycliquement. Les variables logiques Pc correspondant à la nouvelle banque pointée (suite à l'incrémentation) sont mises à zéro (étape 134). L'adresse d'entrée suivante est analysée (retour à l'étape 104). Une autre manière d'opérer peut consister à remplacer les étapes 120, 122 et 124 par les étapes suivantes étape 140 : test du bit Pc de l'élément-mémoire concerné Si ce bit PcrO, ne rien faire, Si ce bit Pc=O, incrémenter le compteur de transition A (étape 142) puis mettre toutes les variables logiques PO~~~PB-1 de l'élément concerné à l'état logique 1 (étape 144). Bien évidemment l'homme du métier peut inverser les états logiques 1 et O sans changer le cadre de l'invention. Lorsque la méthode de remplacement comprend préalablement au remplacement une étape de chargement de tous les éléments-mémoire inoccupés, l'organigramme des figures 9A et 9B est modifié de la manière suivante - l'étape 102 comprend la désactivation du bit de présence Q1 (Q=O logique, par exemple). - l'étape 108 comprend non seulement le test de la clé d'entrée S mais aussi le test pour connaître si le bit de présence Q ou le bit Po de l'élément-mémoire concerné sont à l'état logique 1. Une première situation peut être constituée par l'égalité des clés. Le test ci-dessus étant satisfait, la donnée relative à cette clé peut être adressée. Une seconde situation peut être constituée soit par l'inégalité des clés soit par le fait que le test ci-dessus n'est pas satisfait. Dans ce cas la méthode peut avoir à opérer soit une étape de chargement soit une étape de remplacement. lorsque Q=O l'ensemble de la classe n'est pas occupé. . lorsque Q=1 l'ensemble de la classe est occupé. Quelle que soit la valeur de Q, la clé et la donnée sont chargées selon les étapes déjà décrites pour le remplacement. L'étape 119 est supprimée. L'étape 126 est modifiée pour opérer de la manière suivante : le bit Q est testé, i) lorsque Q=O on teste Si A=E . Si la réponse est positive, il faut remettre à O tous les bits Po...PB~1 de tous les éléments de la classe et faire Q=i puis passer à l'étape 128 Si la réponse est négative, il faut passer à l'étape 104 ii) lorsque Q=i on teste Si A=E/B . Si la réponse est positive, il faut passer à l'étape 128 . Si la réponse est négative, il faut passer à l'étape 104. Lorsque cette méthode de gestion est mise en oeuvre dans un calculateur l'invention concerne alors un calculateur agencé pour mettre en oeuvre ladite méthode. Pour illustrer les performances de la méthode de remplacement selon l'invention, le tableau I permet de la comparer avec les autres méthodes de remplacement les plus utilisées. M 256 512 1024 B=1 bit 17,9 7,83 2,10 B=2 bits 18,1 8,32 2,29 LRU 18,1 9,32 2,82 Random 19,8 8,44 2,59 FIFO 20,2 9,74 3,07 TABLEAU I Ce tableau indique le pourcentage d'échecs pour un même nombre d'accès à une mémoire cache ayant des tailles M=256; 512; 1024 octets. La comparaison est fournie dans le cas de la méthode selon l'invention avec la variable logique ayant B=i bit et B=2 bits. Les algorithmes qui servent à la comparaison sont LRU, Random et FIFO. On observe que pour M=256 octets la méthode selon l'invention avec B=2 bits délivre des résultats identiques (18,1%) avec l'algorithme LRU. Pour M=1024 octets, l'écart est en faveur de l'invention (2,29% pour l'invention et 2,82% pour LRU). Lorsque B=1 bit l'invention fournit alors un gain appréciable. Pour M=256 octets, le taux d'échecs est réduit à 17,9% pour l'invention (18,1% pour LRU) et pour M=1024 octets, le taux d'échecs est réduit à 2,10% pour l'invention (2,82% pour LRU). Les autres algorithmes sont globalement de qualité inférieure. REVENDICATIONS 1. Dispositif de contrôle pour une mémoire tampon qui est organisée selon au moins une classe de E éléments-mémoire munis de clés et répartis sur E voies, la mémoire étant adressée par des adresses ayant des champs d'indices de classe et/ou de clé, chaque voie étant munie d'au moins un comparateur des adresses d'entrée et des adresses stockées, et lorsque l'adresse d'entrée n'est pas trouvée (échec) dans la mémoire tampon, le dispositif permet de la trouver dans une mémoire source puis de transférer le contenu des informations qui s'y rapportent vers la mémoire tampon suivant une méthode de remplacement, caractérisé en ce que pour opérer ledit remplacement le dispositif comprend - pour chaque élément-mémoire, un organe de stockage de B bits (B - des premiers moyens pour scruter au cours desdites phases successives au moins un des B bits de chacun des éléments-mémoire, les E bits de même rang des E éléments-mémoire d'une même classe, formant une banque BKC, étant scrutés au cours d'une même phase sous le contrôle d'un compteur de phases, lesdits premiers moyens comprenant en outre un compteur de transitions qui, au cours d'une même phase, est incrémenté d'une unité lorsqu'au moins un des bits scrutés d'un élémentmémoire a changé d'état, ledit compteur délivrant après un nombre E/B d'incrémentations, un signal de fin de phase, celui-ci activant des moyens de forçage qui forcent un état logique de non succès dans la banque BKC+1 à utiliser à la phase suivante, - des seconds moyens pour sélectionner des éléments-mémoire qui n'ont pas été adressés ni au cours des B-i phases précédentes ni sur la partie de la phase en cours qui précède l'instant d'analyse de l'adresse d'entrée, en détectant que tous les bits de leur organe de stockage sont à l'état logique de non-succès, - des troisièmes moyens pour sélectionner un des élémentsmémoire parmi lesdits éléments-mémoire non adressés précédents pour y effectuer le remplacement. 2. Dispositif de contrôle selon la revendication 1 caractérisé en ce que lesdits premiers moyens comprennent E multiplexeurs placés chacun entre la sortie des E organes de stockage et le compteur de transitions, les multiplexeurs étant contrôlés par le compteur de phases, 3. Dispositif de contrôle selon la revendication 1 caractérisé en ce que le compteur de transitions possède E.B entrées connectées aux B bits des E éléments-mémoire d'une même classe. 4. Dispositif de contrôle selon une des revendications 1 à 3 caractérisé en ce que lesdits troisièmes moyens déterminent un premier élément-mémoire disponible en testant, selon un classement préétabli, chacun des éléments-mémoire non adressés. 5. Dispositif de contrôle selon une des revendications 1 à 4 caractérisé en ce qu'il comprend un élément de stockage d'un bit de présence unique pour tous les élémentsmémoire d'une même classe afin d'opérer le chargement de tous les éléments-mémoire inoccupés de ladite classe préalablement au remplacement, ce bit de présence contrôlant le compteur de transitions de ladite classe pour qu il opère un comptage modulo E/B si le bit de présence indique le chargement complet des éléments-mémoire inoccupés et un comptage modulo E dans le cas inverse. 6. Dispositif de contrôle selon une des revendications 1 à 5 caractérisé en ce qu'il gère les échanges soit entre un traducteur d'adresses et une mémoire cache, soit entre un traducteur d'adresse et une mémoire centrale, soit entre une mémoire cache et une mémoire centrale, soit entre une mémoire centrale et une mémoire de masse. 7. Méthode de gestion de données numériques dans une mémoire tampon formée de E voies chaque voie étant formée d'éléments-mémoire repérés par une clé, les voies étant divisées en classes, chaque classe étant formée de E éléments-mémoire pris un à un dans chaque voie, la mémoire tampon recevant des adresses d'entrée ayant des indices de classe et/ou de clé, la méthode opérant une recherche dans la mémoire tampon d'une adresse d'entrée en la comparant aux indices de classes et/ou aux clés d'adresses stockées, - et lorsque l'adresse d'entrée est trouvée (succès), la méthode met en oeuvre des opérations de lecture/écriture de la mémoire tampon, - et lorsque l'adresse d'entrée n'est pas trouvée (échec), la méthode met en oeuvre une recherche dans une mémoire source puis un transfert du contenu des informations qui se rapportent à cette adresse d'entrée vers la mémoire tampon suivant une méthode de remplacement, caractérisé en ce que, à chaque fois qu'une adresse est présentée en entrée, la méthode de remplacement effectue le stockage des succès de la comparaison dans B variables logiques Po...Pc...PB~ associées à chaque élément-mémoire avec B=E/k (k entier > 1) la méthode se subdivisant en deux branches - une branche succès, auquel cas l'étape de lecture/écriture des informations selon l'adresse d'entrée est effectuée, - une branche échec, auquel cas la méthode comprend les étapes suivantes sélection des éléments-mémoire ayant leur variable logique PC+1 à l'état logique de non-succès, sélection, parmi ces éléments-mémoire, de celui qui est muni d'un accès privilégié pour y effectuer le remplacement en écrivant les informations et les champs de clé selon l'adresse d'entrée, l'une et l'autre branche comprenant ensuite les étapes suivantes - pour tous les E éléments-mémoire d'une même classe, mise à jour puis scrutation des B variables logiques au cours de B phases successives et, dans une même phase, comptage du nombre A de changements d'états des bits Pc d'un même rang C formant ensemble une banque BKC, - comparaison du nombre A de changements d'états avec la valeur E/B . et lorsque A . et lorsque A=E/B remise à l'état non succès des bits PC+1 de la banque BKC+l suivante puis incrémentation à C+1 (modulo B) du comptage de rang, remise à zéro du compteur A et passage à l'adresse suivante. 8. Méthode selon la revendication 7 caractérisée en ce qu'elle comprend, pour chaque classe, préalablement au remplacement, une étape de chargement de tous les éléments-mémoire inoccupés d'une même classe, l'étape comprenant la détection du changement d'état d'un bit de présence unique affecté à la signalisation de l'occupation de tous les éléments-mémoire de ladite classe. 9. Méthode selon les revendications 7 ou 8 caractérisée en ce que la méthode gère les échanges soit entre un traducteur d'adresses et une mémoire cache, soit entre un traducteur d'adresses et une mémoire centrale, soit entre une mémoire cache et une mémoire centrale, soit entre une mémoire centrale et une mémoire de masse. 10. Calculateur caractérisé en ce qu'il est agencé pour mettre en oeuvre la méthode selon une des revendications 7 à 9.