Brevet FR2663136A1 — publié le 19911213

DESCRIPTION "DISPOSITIF DE CONTROLE D'UNE MEMOIRE TAMPON ET METHODE DE GESTION DE DONNEES NUMERIQUES". L'invention concerne un dispositif de contrôle pour une mémoire tampon qui met en oeuvre une méthode de remplacement des données présentes lorsque les données cherchées ne sont pas trouvées dans la mémoire tampon. 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, n"3, 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. L'algorithme LRU se caractérise par - de bonnes performances qui sont obtenues en mémorisant avec précision l'ordre dans lequel les éléments de la mémoire tampon sont utilisés. Cette mémorisation est faite à l'aide de bits de remplacement; - une mise en oeuvre complexe et coûteuse : il faut E bits de remplacement par élément, soit E2 bits de remplacement par classe, une classe étant formée par E éléments-mémoire répartis sur E voies. A ceci s'ajoute de la circuiterie logique. L'algorithme FIFO se caractérise par - de moins bonnes performances que LRU. Ceci est dû en partie au fait que FIFO choisit l'élément à remplacer sans tenir compte de l'ordre dans lequel les éléments de sa classe sont réutilisés après chargement d'une nouvelle clé; - une mise en oeuvre assez simple, basée essentiellement sur l'utilisation d'un compteur par classe. Chaque compteur peut prendre les valeurs O à (E-l) et possède donc log#E bits. L'algorithme Random a des performances voisines de celles de l'algorithme FIFO. 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 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 remplacement des données dans une mémoire-tampon est généralement réalisé soit par l'algorithme LRU qui est performant mais assez complexe à mettre en oeuvre et nécessite un matériel important, soit par l'algorithttte FIFO qui ne nécessite qu'un matériel réduit mais au prix de performances assez restreintes Le problème posé consiste à déterminer une méthode de remplacement et un dispositif de contrôle la mettant en oeuvre qui permettent d'atteindre de bonnes performances avec un matériel raisonnablement limité donc d'un coût réduit. Il s'agit en quelque sorte de déterminer une situation de compromis entre les deux algorithmes LRU et FIFO. La solution à ce problème posé consiste en 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 répartis sur E voies et munis chacun d'une clé, le dispositif de contrôle comprenant des moyens pour comparer, pour une classe courante adressée, une clé d'adresse courante avec des clés stockées et pour détecter ainsi des situations de succès/ échec, et lorsqu'une clé d'adresse courante n'est pas trouvée (échec) dans la mémoire tampon, le dispositif met en oeuvre un remplacement des données contenues dans un des éléments-mémoire de la classe courante adressée qui est sélectionné par un indice de voie C contenu dans un pointeur qui est mis à jour à la fin du remplacement caractérisé en ce que lorsque lesdits moyens détectent un succès, le dispositif de contrôle détermine l'indice de voie INV relatif à l'élément-mémoire adressé, un organe de validation comparant l'indice de voie INV avec ledit indice de voie C puis chargeant dans ledit pointeur la valeur consécutive à l'indice de voie INV dans une suite ordonnée d'indices de voies lorsque l'indice de voie INV est un des successeurs de l'indice de voie C dans ladite suite, et conservant l'indice de voie C dans le cas inverse. Il peut s'agir également d'une méthode de gestion de données dans une mémoire tampon organisée selon au moins une classe de E éléments-mémoire répartis sur E voies et munis chacun d'une clé, la méthode opérant une comparaison, pour une classe courante adressée, d'une clé d'adresse courante avec des clés stockées et détectant des situations de succès/échec, et lorsqu'une clé d'adresse courante n'est pas trouvée (échec) dans la mémoire tampon, la méthode met en oeuvre un remplacement des données contenues dans un des éléments-mémoire de la classe courante adressée qui est sélectionné par un indice de voie C contenu dans un pointeur qui est mis à jour à l'issue du remplacement caractérisée en ce que lorsqu'un succès est détecté, la méthode comprend les étapes suivantes - détermination de l'indice de voie INV relatif à l'élé- ment-mémoire adressé, - comparaison de l'indice de voie INV avec ledit indice de voie C contenu dans le pointeur, - chargement dans le pointeur de la valeur consécutive à l'indice de voie INV dans une suite ordonnée d'indices de voies lorsque l'indice de voie INV est un des successeurs de l'indice de voie C dans ladite suite et conservation de l'indice de voie C dans le cas inverse. Ainsi avantageusement on obtient selon l'inven- tion des performances assez voisines de celles obtenues par l'algorithme LRU tout en ayant une complexité de mise en oeuvre qui soit assez proche de l'algorithme FIFO. Comme pour LRU et FIFO l'invention permet de garantir que tous les élémentsmémoire d'une même classe ont déjà été remplis avant de commencer le remplacement. En effet l'ordre dans lequel les éléments-mémoire ont été utilisés est pris en compte mais d'une manière telle que le matériel nécessaire est réduit. En effet le nombre de bits de remplacement nécessaires pour définir une classe de E éléments-mémoire est égal à E2 bits pour LRU (E bits par élément) et à log#E pour FIFO et pour la méthode selon l'invention. Cette situation est particulièrement avantageuse lorsque le nombre d'éléments-mémoire est moyennement élevé par exemple 4 ou 8. Néanmoins lorsque le nombre d'éléments-mémoire croît la complexité du dispositif selon l'invention reste raisonnable, comparée à celle relative à l'algorithme LRU qui nécessite de prendre en compte E2 bits ce qui devient rapidement inacceptable quand E croît. L'invention sera mieux comprise à l'aide des figures suivantes données à titre d'exemples non limitatifs qui représentent - figure 1 : un schéma général simplifié d'une mémoire tampon limitée à deux voies Vo, V1 et à quatre classes Ko à K3. - figure 2 : un dispositif de contrôle selon l'invention coopérant avec des éléments-mémoire d'une mémoire tampon. - figure 3 : un organigramme de la méthode de gestion selon l'invention. La figure I représente un exemple simplifié, mais non limitatif, d'une mémoire tampon selon l'invention. Elle comprend deux voies Vo, Vr renfermant chacune 4 classes Ko, K1, K2, K3 d'éléments-mémoire. Une classe contient un élémentmémoire par voie c'est-à-dire 2 selon l'exemple présenté. La voie Vo contient les éléments-mémoire 500, 510r 520, 530. La voie V1 contient les éléments-mémoire SOi, 511, 521, 531. La classe Ko contient les éléments-mémoire 500, 501. Chaque élément-mémoire par exemple 500 comprend plusieurs positions de stockage pour - un bit de présence P, - une clé stockée CS, - un bloc de données BL, qui contient les informations de l'élément, c'est-à-dire des mots ayant des adresses consécutives. Les données sont délivrées par un bus de données 5D qui délivre les champs de données BL. Les adresses sont délivrées par un bus d'adresses SA qui délivre trois champs - un champ de clés d'adresses d'entrée CE, - un champ de classes d'adresses d'entrée K, - un champ d'indice de mot IM qui permet de distinguer les mots contenus dans un champ de données BL. Le champ IM et le bit de présence P peuvent ne pas exister. Lorsque le bit de présence P n'existe pas, une autre solution consiste à avoir un drapeau associé à chaque classe. Le processeur (non représenté) qui coopère avec la mémoire tampon fournit une adresse sur le bus 5A. Selon l'opération en cours ce processeur peut soit délivrer soit recevoir un mot de données sur le bus 5D. A partir de l'adresse, le décodeur 55 extrait l'indice de classe de l'adresse d'entrée et sélectionne la classe correspondante. Les éléments-mémoire de cette classe sont alors activés. Lorsque par exemple la classe Ko est sélectionnée, les éléments-mémoire 500 et 501 sont activés. Ils transmettent alors leur bit de présence P (s'il existe) et leur clé stockée CS au dispositif de contrôle 10 qui reçoit par ailleurs la clé d'entrée CE de l'adresse d'entrée. Sur le schéma de la figure 1 on a représenté un seul dispositif de contrôle 10 pour l'ensemble de la mémoire tampon, Ceci a l'avantage de minimiser la complexité des moyens matériels.Il est également possible d'utiliser un dispositif de contrôle pour une ou plusieurs classes ce qui présente l'avantage d'une rapidité d'exécution accrue. Des pointeurs 40, 41, 42, 43 relatifs à chaque classe contiennent chacun un indice de voie qui permet à l'aide d'un décodeur 56 de sélectionner l'élément-mémoire dans lequel doit s'opérer l'opération de remplacement si la recherche de l'adresse donne lieu à un échec. Le remplacement consiste à écrire le champ de données BL avec sa clé CS et son bit de présence P (s'il existe). Si la recherche de l'adresse donne lieu à un succès, l'opération consiste alors à opérer une lecture ou écriture des données BL dans l'élément-mémoire réalisant le succès et à mettre à jour le pointeur de la classe sélectionnée. La figure 2 représente un dispositif de contrôle 10 qui est affecté à une seule classe Ko relative aux éléments-mémoire 500 501, 502, 503 qui reçoivent leur champ d'adresses du bus SA. Pour simplifier le dessin le décodeur 56 n'est pas représenté. Chaque élément-mémoire transmet sa clé stockée CS à l'un des comparateurs 12o, 121, 122, 123 qui re çoivent tous la clé CE de l'adresse d'entrée et qui opèrent la comparaison sous le contrôle des bits de présence respectifs Po à P3. En cas d'échec, tous les comparateurs ont leur sortie à l'état inactif (SVo à SV3). Dans ce cas une validation formée par exemple des portes logiques NON-OU16 et ET17 permet de charger dans le pointeur un indice de voie C qui peut par exemple être lu dans une table 152, par exemple une mémoire. Cet indice de voie C ainsi chargé est destiné lors du premier remplacement ultérieur à déterminer la voie dans laquelle doit s'effectuer le remplacement suivant. L'indice de voie C peut également être obtenu par incrémentation ou décrémentation de l'indice de voie précédent. En cas de succès, un des comparateurs a sa sortie à l'état actif. Un sélecteur 13 détermine l'indice de voie INV de l'élément réalisant le succès. Le sélecteur agit sur un organe de validation 20 qui met à jour le pointeur 40. L'organe de validation 20 comprend un comparateur 14 qui compare cet indice de voie INV avec l'indice de voie C contenu dans le pointeur - lorsque l'indice de voie INV est un des successeurs de l'indice de voie C dans une suite ordonnée d'indices, alors la valeur consécutive à l'indice de voie INV est substituée à l'indice de voie C dans le pointeur (porte logique ET18). Cette valeur consécutive est par exemple lue dans une table par exemple stockée dans une mémoire 151. - lorsque l'indice de voie INV est un prédécesseur de l'indice de voie C dans ladite suite ordonnée d'indices, l'indice de voie C est conservé dans le pointeur. Ceci permet de tenir compte de l'ordre dans lequel les éléments-mémoire de la classe ont été utilisés en se déplaçant selon un sens unique dans la suite ordonnée d'indices. Ceci permet de ne pas sélectionner systématiquement l'élément-mémoire suivant comme dans FIFO où cela s'avère peu performant. De même ceci permet de ne pas mettre en oeuvre une procédure et une architecture lourdes pour déterminer l'élément-mémoire utilisé le moins récemment comme dans LRU. Les performances atteintes par l'invention se situent pratiquement au niveau de celles atteintes par LRU tout en gardant une complexité d'architecture réduite proche de FIFO. Ainsi avantageusement selon l'invention il n'y a qu'un pointeur (40-43) par classe (figure 1) qui peut contenir des valeurs allant de O à (E-1) soit log2E bits. Chaque pointeur opère modulo E. Les suites formant les tables 151, 152 peuvent être stockées dans une ou plusieurs mémoires. Lorsque les suites ordonnées sont distinctes elles doivent être coordonnées. Ainsi l'une peut être une suite de chiffres pairs et l'autre une suite-de chiffres impairs. Toute autre manière de coordonner les deux suites est possible. Préférentiellement il peut s'agir d'une suite unique par exemple celle formée d'une suite d'entiers qui peuvent se suivre par incrémentation ou décrémentation opérées par au moins respectivement un incrémenteur ou un décrémenteur qui se substituent alors aux tables 151, 152. Ceci conduit à une plus grande rapidité d'exécution et à une plus grande simplicité de mise en oeuvre. L'invention concerne également une méthode de gestion de données dans une mémoire tampon pour opérer le remplacement desdites données. L'organigramme de cette méthode est représenté sur la figure 3. Dans une étape d'initialisation 71, pour chaque classe, le pointeur C et les E bits de présence P (un par élément) sont remis à 0. Etape 72 : introduction de l'adresse d'entrée Etape 73 : sélection de la classe et détermination de la clé de l'adresse d'entrée Etape 74 : recherche d'un succès pour cette adresse : existet-il un élément de la classe qui 1) a sa clé stockée CS égale à la clé d'entrée CE et 2) a son bit de présence P à 1 (s'il existe). . il y a succès (branche 100) il y a sélection (étape 75) de l'élément-mémoire qui vérifie les conditions de succès indiquées ci-dessus, puis lecture ou écriture (étape 76) de la donnée, selon l'opération à effectuer; . s il y a échec sur tous les éléments de la classe, il faut opérer une procédure de remplacement (branche 101). L'élément sélectionné est celui qui a pour indice de voie la valeur contenue dans le pointeur C (étape 80). Il y a écriture de la clé et des données relatives à l'adresse d'entrée dans cet élément sélectionné (étape 81). Enfin, le bit de présence de cet élément est mis à 1 (étape 82). Les indices de voies INV peuvent prendre des valeurs de O à E-i. En cas de succès la méthode prend en compte l'indice de voie INV de l'élément-mémoire qui a été sélectionné. Ainsi après l'étape 76 la valeur de l'indice INV est comparée à l'indice de voie C du pointeur (étape 77). - Lorsque INV est l'un des successeurs de C, le pointeur est chargé par la valeur SUC (INV) qui est la valeur consécutive à INV dans la suite ordonnée d'indices (étape 78); - Sinon on ne change pas le contenu du pointeur et on passe à l'adresse d'entrée suivante. En cas d'échec lorsque l'opération de remplacement a été opérée avec l'indice de voie C contenu dans le pointeur, cet indice de voie C est remplacé par SUC(C) qui est la valeur consécutive à C dans la suite ordonnée d'indices (étape 83). L'étape 84 constitue un test pour déterminer si le dernier indice de voie de la suite a à être dépassé auquel cas la méthode reboucle sur le premier indice de voie de la suite (étape 85). La méthode selon l'invention présente un nombre réduit d'étapes et se prête bien pour être réalisée par logiciel. L'invention peut alors concerner un calculateur qui est agencé pour mettre en oeuvre la méthode de gestion de données. A titre d'exemple le tableau I donne une comparaison des performances obtenues par l'invention et par les algorithmes LRU et FIFO. Dans cet exemple le nombre d'éléments-mémoire par classe est égal à 4 (E=4) et la taille T de la mémoire tampon est variable. Les valeurs du tableau I concernent les pourcentages de recherche d'adresses qui conduisent à un échec. On observe que quelle que soit la taille T de la mémoire tampon, la méthode selon l'invention délivre des résultats meilleurs qu'avec FIFO. Dans certaines situations la comparaison avec l'algorithme LRU est à l'avantage de la méthode selon l'invention. T (octets) 256 512 1024 2048 4096 8192 16384 LRU 24,33 19,80 13,03 6,14 1,85 1,18 0,88 FIFO 26,01 20,87 14,06 7,15 2,57 1,44 0,96 Invention 25,27 19,81 12,76 5,97 2,22 1,30 0,96 TABLEAU I Un dispositif de contrôle conforme à l'invention peut présenter l'avantage d'opérer également selon l'algorithme FIFO lors de certaines séquences d'adresses qui ne seraient pas favorables à la méthode présentée conduisant ainsi à un taux d'échec plus élevé. Dans ces situations, il est possible de neutraliser la mise à jour des pointeurs en cas de succès et d'opérer selon l'autre mode. Cette double possibilité, qui ne nécessite aucun moyen matériel supplémentaire, donne audit dispositif de contrôle une grande souplesse d'utilisation. 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 l500 à 503) répartis sur E voies et munis chacun d'une clé, le dispositif de contrôle comprenant des moyens (120 à 123) pour comparer, pour une classe courante adressée, une clé d'adresse courante avec des clés stockées et pour détecter ainsi des situations de succès/échec, et lorsqu'une clé d'adresse courante n'est pas trouvée (échec) dans la mémoire tampon, le dispositif (10) met en oeuvre un remplacement des données contenues dans un des éléments-mémoire de la classe courante adressée qui est sélectionné par un indice de voie C contenu dans un pointeur qui est mis à jour à la fin du remplacement caractérisé en ce que lorsque lesdits moyens (120 à 123) détectent un succès, le dispositif de contrôle (10) détermine l'indice de voie INV relatif à l'élément-mémoire réalisant le succès, un organe de validation (20) comparant l'indice de voie INV avec ledit indice de voie C puis chargeant dans ledit pointeur (40) la valeur consécutive à l'indice de voie INV dans une suite ordonnée d'indices de voies lorsque l'indice de voie INV est un des successeurs de l'indice de voie C dans ladite suite, et conservant l'indice de voie C dans le cas inverse. 2. Dispositif selon la revendication 1 caractérisé en ce que, un organe de validation (20) est attribué à chaque classe d'éléments-mémoire. 3. Dispositif selon la revendication 1 caractérisé en ce que, un organe de validation (20) unique est attribué à tous les éléments-mémoire. 4. Dispositif selon une des revendications 1 à 3 caractérisé en ce que, à la fin d'un remplacement, l'indice de voie C mis à jour dans le pointeur est pris dans une autre suite ordonnée d'indices coordonnée avec ladite suite. 5. Dispositif selon une des revendications I à 4 caractérisé en ce qu'au moins une desdites suites d'indices est stockée dans une mémoire. 6. Dispositif selon une des revendications 1 à 4 caractérisé en ce que les suites ordonnées d'indices se succèdent par incrémentation ou décrémentation opérées par au moins respectivement un incrémenteur ou un décrémenteur. 7. Méthode de gestion de données dans une mémoire tampon organisée selon au moins une classe de E éléments-mémoire (SOn à 503) répartis sur E voies et munis chacun d'une clé, la méthode opérant une comparaison (120 à 123), pour une classe courante adressée, d'une clé d'adresse courante avec des clés stockées et détectant des situations de succès/échec, et lorsqu'une clé d'adresse courante n'est pas trouvée (échec) dans la mémoire tampon, la méthode met en oeuvre un remplacement des données contenues dans un des éléments-mémoire de la classe courante adressée qui est sélectionné par un indice de voie C contenu dans un pointeur (40) qui est mis à jour à l'issue du remplacement caractérisée en ce que lorsqu'un succès est détecté, la méthode comprend les étapes suivantes - détermination (13) de l'indice de voie INV relatif à l'élément-mémoire adressé, - comparaison (14) de l'indice de voie INV avec ledit indice de voie C contenu dans le pointeur, - chargement (151,18) dans le pointeur (40) de la valeur consécutive à l'indice de voie INV dans une suite ordonnée d'indices de voies lorsque l'indice de voie INV est un des successeurs de l'indice de voie C dans ladite suite et conservation de l'indice de voie C dans le cas inverse. 8. Méthode selon la revendication 7 caractérisée en ce que, la détermination des indices de voie dans ladite suite s'opère par au moins une incrémentation ou une décrémentation. 9. Calculateur caractérisé en ce qu'il est agencé pour mettre en oeuvre la méthode de gestion de données dans une mémoire-tampon selon une des revendications 7 ou 8.