Brevet FR2096544A1 — publié le 19720218

Cette invention est relative à un système de mémoire d'un calculateur numé -rique électronique. L'invention concerne plus particulièrement un système de mémoire à deux niveaux comprenant une mémoire principale ou auxiliaire contenant l'information du système et une mémoire ultra-rapide ou mémoire intermédiaire 5 par comparaison à laquelle l'information est traitée utilisant un dispositif de répertôire, et dans laquelle l'information est adressée en termes d'adresse virtuelle. Afin de répondre aux besoins présent et futur du traitement de données, des calculateurs numériques à grande échelle ultra-rapides ont été et sont toujours 10 créés. Ces calculateurs sont potentiellement aptes a traiter des quantités considérables de données dans des périodes de temps courtes. Néanmoins, le potentiel total de ces calculateurs numériques n'a pas été pleinement exploité pour diverses raisons. L'une des plus importantes de ces raisons est l'impossibilité de déplacer les données hors d'une zone de mémorisation vers une zone de traite-15 ment à la vitesse désirée. Afin de surmonter cette difficulté, des systèmes de mémorisation ont été conçus avec deux niveaux de mémoire. Les systèmes de l'art antérieur conçus pour accroître considérablement l'utiliation effective de la puissance de calcul potentiel des calculateurs numériques électroniques rapides, utilisent un répertoire qui est employé comme un catalogue de noms ou d'adresses 20 virtuelles des données et de l'emplacement physiq-je qui leur correspond dans la mémoire principale. Néanmoins, ces systèmes ont été affectés par un problème impliquant une période de temps trop longue consacrée à l'exploration du répertoire lorsqu'il s'agit de localiser une entité de données désirée. L'objet général de la présente invention est, en conséquence, de fournir un 25 système de mémoire utilisant un répertoire amélioré qui permet le positionnement d'une entité de données désirée dans une mémoire principale au prix d'un temps de recherche minimum. Un objet plus particulier de l'invention est de fournir un répertoire dans un calculateurnoraérique ultra-rapide afin de déterminer l'adresse physique dans 30 la mémoire principale de pages de données de format variable. Un objet encore plus particulier de la présente invention est dé fournir un répertoire utilisant un/pslu So-seSectif dans lequel des pages de format différent comportent certaines positions d'entrée permises dans le répertoire, de telle sorte que les formats de page donnant lieu aux accès les plus fréquents se 35 rontcêcouverts plus tôt dans une exploration du répertoire. L'invention se rapporte ainsi à un système de mémoire à deux niveaux, dans lequel l'information est stockée dans la mémoire principale en termes de page à format variable et est traitée par comparaison avec la sortie d'une mémoire ultra-rapide ou auxiliaire, utilisant un répertoire. Dans le cas de la présente 40 réalisation, les formats de page considérés correspondent à des pages de 64 mots 71 18041 2 2096544 de 256 mots, da 1024 mots et de 4096 mots. Une adresse virtuelle, particulière peut être comprise dans n'importe laquelle des quatre pages, et, en l'occurence, il peut se faire que la page de 64 mots ou celle de 256, de 1024 ou 4096 mots contienne l'adresse. Le format est inconnu au départ de la recherche et la sé-5 quence d'adresses de répertoire fournie, lorsque l'adresse est recherchée, doit positionner ladite adresse sans qu'il ait été tenu compte des dimensions de la page. Le répertoire comporte un jeu d'emplacements d'inscriptions ou adresses de répertoire. Chaque adresse virtuelle se voit assigné un sous-jeu de ce jeif à 1'-1Q intérieur duquel l'adresse physique appropriée peut résider en tant qu'inscription. Le sous-jeu d'adresse est fourni pr la détermination au hasard de l'adresse virtuelle et par l'utilisation du résultat pour l'adressage du répertoire; en d'atres termes, l'emplacement dans le répertoire est calculé comme étant fonction de l'accès pseudo-sélectif de deux paramètres: l'adresse virtuelle et un 15 compte. La recherche est effectuée comme suit; la première inscription du réper -toire recherchée est celle correspondant au compte 0. L'inscription du répertoire comprend un identificateur qui peut être une copie de l'adresse virtuelle et l'adresse physique dans la mémoire principale CMS) à laquelle commence la page contenant les données désignées par l'adresse virtuelle. Si l'identificateur 20 n'identifie pas une page contenant l'adresse virtuelle, l'inscription du réper- ant toire correspond/âlTcompte 1 est prélevée et essayée. Ce processus se poursuit en augmentant le compte de 1 après chaque comparaison jusqu'à ce que l'identificateur en place corresponde à l'adresse virtuelle demandée ou jusqu'à ce que le compte dépasse le nombre d'adresses contenues dans le sous-jeu, cas pour le-25 quel une exception d'adresse manquante est manifestée. Une page de dimensions relativement grandes sera l'objet d'accès plus fréquent qu'une page de dimensions relativement petites. C'est ainsi qu'une page de 4096 mots connaîtra 64 fois plus souvent des accès qu'une page de 64 mots. En conséquence, 1'algorithme de répertoire prévoit schématiquement que le couple 30 adresse virtuelle adresse, physique correspondant à une page de 4096 mots peut être introduit dans le répertoire seulement une fois par compte de quatre pour une réalisation à 32 inscriptions de répertoire . De la m§me façon, une page de 1024 mots ne connaîtra d'entrée que deux fois par compte de quatrej une page de 256 mots : trois fois par compte de quatre - et une entrée de page de 64 mots 35 peut avoir lieu à chaque compte. La suite des comptes correspondant à toute adresse virtuelle sera dénommée sa "chaîne". En conséquence, ce qui précède et les autres objets caractéristiques et avantages de l'invention ressortiront de la description plus particulière suivante de la réalisation préférée de l'invention telle qu'elle est représentée dans les 40 dessins joints. 71 13041 3 2096544 La figure 1 est un schéma synoptique d'un système de mémoire à deux niveaux conforme à la présente invention. La figure 2 est une représentation schématique dudit répertoire utilisé dans le système de mémoire. 5 La figure 3 est une illustration d'un équipement d'explotation du répertoire La figure 4 est une représentation graphique montrant le fonctionnement général de l'algorithme de pseudo-sélection. La figure 5 est une représentation schématique d'une chaîne d'algorithme conformément à laquelle sont effectuées les inscriptions. 10 La figure 6 est une représentation d'une réalisation mettant en application la stratégie d'entrée des inscriptions du répertoire. Avant d'aborder la description de la structure d'une réalisation préférée de l'invention il est désirable de présenter et de définir certains termes de la terminologie utilisée ci-après. 15 Inscriptions du répertoire: index des pages stockées dans la mémoire principale. Clée: quantité utilisée afin de préserver l'intégrité des espaces d'adresses et d'assurer la protection de leur mémorisation Ligne: quantité de mémoire d'une longueur de 64 mots dans le cas de cette 20 réalisation. Il existe 2, 8, 32 ou 128 lignes dans une page. Indicateur MS: Chmap de l'inscription du répertoire qui spécifie l'adresse physique du début de la page de la mémoire principale dans laquelle résident les données référencées. Page: Entité de stockage dans la mémoire principales dans notre exemple cet-25 te entité est de 64, 256, 1024 ou 4096 mots. Identificateur de page: Champ de l'inscription du répertoire qui fournit un identificateur particulier à la page représentée à ce moment par cette inscription du répertoire. Adresse virtuelle: Adresse de mémoire logique qui définit particulièrement 30 ou désigne une quantité spécifique de données. L'adresse virtuelle possède une largeur de 36 bits dans la réalisation considérée. Mot: Entité physique de mémoire. La figure 1 est un schéma synoptique général d'un système de mémoire à deux niveaux conforme à l'invention. Dans ladite figure une unité centrale de traite-35 ment 3 est reliée par la ligne 5 à une mémoire ultra-rapide 1. L'unité centrale 3 fournit une demande en termes d'adresse virtuelle à la mémoire ultra-rapide 1. Si les données désignées par l'adresse virtuelle sont à ce moment stockées dans la mémoire 1, elles sont aussitôt renvoyées à l'unité centrale par le bus de donnée aux fins de traitement: la mémoire ultra-rapide 1 est reliée par le bus référencé V.A. au répertoire 11 lui-même relié à la mémoire principale 9. 71 18041 2096544 Si l'adresse virtuelle demandée n'est pas au moment considéré présente dans la mémoire 1, l'adresse virtuelle est alors envoyée au répertoire qui est exploré afin de localiser l'adresse physique (P.A) de la mémoire principale 9 à lequE^Ia commence la page contenant la quantité de données désirées. Il est alors a cca": 5 à la mémoire principale 9 et une pluralité de mots de données qui comprener4: les données demandées par l'adresse virtuelle originale sont envoyés à la • re ultra-rapide 1. Les données demandées seront en dernier lieu envoyées à té centrale par le bus de données. La littérature spécialisée fournira des descriptions plus complètes de ce type de mémoire à deux niveaux évoquée de fôç: 10 générale dans la figure 1. La figure 2, à laquelle nous nous reportons maintenant est une représentâtloi graphique de l'inscription mémorisée dans le répertoire. Les inscriptions ui: répertoire sont numérotées de 0 à N et chacune d'elles comporte un identificateur, qui est essentiellement une adresse virtuelle, et également une adresse phyni-15 que dans la mémoire principale correspondant à l'adresse virtuelle qui lui est associée. En outre, chaque inscription comporte associée à elle, les dimensions CS) de la page dans laquelle les données indiquées par l'adresse virtuelle seront trouvées. De plus, un bit de validité (V) peut être inclus de façon à indiquer que l'élément est présentemment valable. Les dimensions ou format de la pa-20 ge ne sont pas comprises dans le traitement d'adresse virtuelle mais peuvent être ajoutées à l'inscription du répertoire par le système d'opération. Ceci peut être effectué par un moyen choisi parmi une pluralité de moyens bien connus tels que, par exemple, l'emploi d'une inspection de table associant une adresse virtuelle donnée à un format de page donné, et l'insertion du format de page 25 dans l'inscription du répertoire correspondant lorsqu'il est procédé à l'entrée de cette inscription. La figure 3 représente le dispositif utilisé pour l'exploration du répertoire lorsqu'il est déterminé que les données demandées par une adresse virtuelle issue de l'unité centrale ne séjournent pas au moment considéré dans la mémclr-3 30 ultra-rapide, afin d'être traitées . A ce moment, l'adresse virtuelle est tée au répertoire pour une recherche. Afin d'assurer la fonction de recherche, l'adresse virtuelle est présentée par le bus 12 au générateur d'adresses sél:,c tif 13 et également par le bus 19 au comparateur 17. Le générateur d'adresses sélectif 13 fournit une adresse de répertoire physique dans le bus 15, qui asc 35 utilisée pour accéder à la portion d'identificateur de l'inscription -au réperioi re à l'adresse de répertoire fournie. L'identificateur est envoyé au circuî*: is comparaison17, Si l'identificateur contenu dans l'inscription du répertoire correspond à l'adresse virtuelle, l'adresse physique correspondante est alors t. rans mise par la porte 21 et utilisée pour accéder à la page désirée dans la mémoir» 40 principale. Certains des bits de droite de l'adresse virtuelle peuvent être uri- êAO ORIGINAL i 71 18041 5 2096544 Usés pour l'adressage d'un sous-ensemble particulier de mots afin qu'il soit transféré dans la mémoire ultra-rapide. Ceci sera exposé en détails ultérieurement. Si, par ailleurs l'identificateur ne correspond pas avec l'adresse virtuel-5 le entrante, un signal sur la ligne 25 fait alors avancer d'une position le compteur 27, une nouvelle adresse sélectionnée au hasard est fournie et le processus se poursuit. Ainsi qu'il ressortira clairement d'une description ultérieure détaillée du générateur d'adresses sélectif, il existe pour cette réalisation un ensemble de 512 adresses de répertoire possibles. Chaque adresse virtuelle du 10 fait de l'algorithme pseudo-sélacteur utilisé dans le générateur d'adresses sélectif peut résider dans un sous-ensemble de 32 adresses de répertoire parmi 512. Il sera évident pour le spécialiste que ce nombre peut être accru ou réduit en modifiant l'algorithme. En conséquence du fait que le compteur est initialisé à 0 s'il y a un avancement de compteur 27 jusqu'à un compte de 31 sans qu'une 15 comparaison ait été réussie, une exception de page manquante, bien connue dans l'art, peut être fournie. Ce processus ne faisant toutefois pas partie de l'invention, il ne sera pas évoqué de façon plus détaillée. Le générateur d'adresses sélectif qui correspond au bloc 13 de la figure 3 peut être construit conformément à l'enseignement suivant, par tout spécialiste 20 de compétence normale. L'adressage virtuel est bien connu. Dans la présente réalisation, une adresse virtuelle comprend 36 bits. En outre, le compte du compteur 27, figure 3, variera de 0 à 31; de la sorte cinq bits d'information de compte rentreront dans l'algorithme de pseudo-sélection dans la générateur d'adresse sélectif. L'adresse physique du répertoire est une quantité à dix bits indiquant 25 512 adresses dans le répertoire proprement dit. Cette information d'adresse et de compte est résumée ci-dessous. Adresse virtuelle aoa1a2 a35 Compte C0C1C2C3C4 Adresse physique de 30 répertoire ... P1Q Grâce à des appareils à décalage et à des circuits OU exclusif, OU et ET, les uns comme les autres bien connus, le générateur d'adresse sélectif fournit une adresse sélective correspondant à la valeur de chaque ccompte pour chacune des 35 adressés virtuelles recherchées. Ceci est effectué comme suit: les bits a^a2 .... a^2 subissent une rotation sur la gauche de 2n positions, n étant la valeur du compte, ce qui fournit le'résultat intermédiaire: n n n g1 g2 g22 L'adresse physique de répertoire est aLors formée: 71 18041 B 2096544 o a. = n o °ii V n g12 V Uc3 V C4 3 23 CO CL n = g5 n V g18 pi = n g10 V n g13 V CtC3 V °4] A324] P7 " n g4 ' * g" 19 P2 S n g3 g8 V n g14 V tc3 A 3255 PB = n g3 n v s. 20 CO CL = V 15 V tC3 A a263 P4 = g" 7 V n g16 V ((C3 A °4) Aa273 P9 = n g2 n V g21 P5 = n g6 V n g17 V ttC3 A V Aa28] P10= n gi n V g22 Cet algorithme peut être expliquée plus clairement si on l'examine 10 en même temps que la figure 4. L'on se souviendra que la portion particulière de donnée désignée par une adresse virtuelle peut être comprise dans l'une quelconque de 4 pages en l'occurence, la page de 64 mots ou, les pages de 256, 1024 ou 4096 mots. L'adresse virtuelle proprement dite ne contient pas l'indication du format de cette page et la séquence d'adresses de répertoire fournie par le 15 générateur d'adresses sélectif doit localiser ladite portion sans tenir compte du format de la page. Ceci est effectué grâce à l'utilisation de l'argument de compte de l'algorithme pseudo-sélectif. Les deux bits de compte des positions de droite marquent effectivement les paires appropriées de bits d'adresses virtuelles a_„ à a„0, selon que la valeur de compte est 0, 1, 2 ou 3 modulo 4. Ces Zo Zo 20 bits groupés en paires, sont ceux qui établissent la distinction entre les pages de même format. Ceci reproduit la stratégie d'entrée d'élément dans laquelle une inscription du répertoire correspondant à une page de 4096 mots ne peut être introduit légitimement qu'avec un compte de 0, 4, 6 .... De la même façon, une inscription de répertoire correspondant à une base de 1024 mots peut être introduit 25 avec un compte de 0, 1, 4, 5, B, 9 s'il s'agit d'une page de 256 mots, ce compte sera 0, 2, 4, 5, 6, 6, 9, 1D et dans le cas d'une page de 64 mots, l'entrée est possible avec un compte quelconque. De la sorts, lorsqu'une inscription du répertoire est effectuée elle a lieu de telle sorte qu'une nouvelle inscription du répertoire est également effectuée dans le premier emplacement qui, 30 dans sa chaîne, contiend alors un élément non valable ou un élément en provenance d'une page de format inférieur. En conséquence du fait qu'une page de grand format sera l'objet d'accès plus fréqueîit qu'une page de petit format, le temps de recherche moyen dans le répertoire sera réduit à un minimum. Ce qui précède est résumé dans1la figure 5. Une- inscription destinée à une 35 adresse virtuelle donnée de 4096 Cou 4K.) mots peut être effectuée avec un compte de 0, 4, Q ... 28. Les inscriptions correspondant e dës pages d'autres formats sont faites de la-mime façon ainsi qu'il a été indiqué . Lors de la recherche, une inscription de page dé grand format sera en conséquence, découverte plus tôt dans sa chaîne. " 71 18041 2096544 La façon dont l'algorithme utilise le compte pour démasquer deux paires appropriées de bits d'adresse virtuelle lors de la recherche et quand le compte est O, 1, 2 ou 3 modulo 4, peut être comprise grâce à l'examen de l'algorithme ci-dessus. Par exemple, si le compte est 0 modulo 4, les bits de compte C3 et 5 seront tous deux 0. De la sorte, le bit d'adresse virtuel a23 est démasqué en vertu de p , a24 est démasqué par p., a25 par p , a26 par p , a27 par p et U I Z . • o 4 a28 par p,.. Aussi, seuls les bits 0-22 entrent dans la sélection dans le cas d'une page de 4096 mots correspondant à un compte de 0 modulo 4 dans l'algorithme. Un résumé des bits démasqués et de ceux qui entrent dans l'algorithme pour cha-que valeur de compte modulo 4 est fourni ci-après. Compte Modulo 4 Bits démasqués • Bits compris dans la sélection C3C4 00 23,24,25,26,27,28 — 01 25,26,27,28 23,24 10 27,28 23,24,25,26 11 — 23,24,25,26,27,28 20 De la sorte, en se reportant à la figure 4 et à l'algorithme ci-dessus, il apparait que les bits 0-22 entrent dans la sélection au hasard pour une page du format de 4096 mots et pour les formats inférieurs! que les bits 0-24 entrent dans la sélection au hasard pour une page du format de 1024 mots et pour les formats inférieurst que les bits 0-26 entrent dans la sélection au hasard pour 25 Une page du format de 256 mots et au-dessous; et les bits 0-28 entrent dans la sélection au hasard pour une page de 64 mots. En résumé, lorsqu'une adresse virtuelle entrante est en cours de recherche . dans le répertoire, l'algortihme de sélection ci-dessus est utilisé pour fournir les adresses de répertoire qui sont recherchées afin de déterminer l'adresse 30 physique correspondant au début de la page qui, dans la mémoire principale comprend le mot désigné par l'adresse virtuelle. Lorsqu'une comparaison fait apparaître une concordance, l'adresse physique qui adresse le début d'une entité de format de page particulière est transmise hors du répertoire ainsi qu'il a été décrit au sujet de la figure 3. Ladite adresse physique est alors utilisée; pour 35 accéder au début de la page. Le nombre de mots particuliers comprenant le mot demandé qui doit être repositionné de la mémoire principale dans la mémoire ultra-rapide aux fins de transmission ultérieures à l'utilisateur ou à l'unité centrale peut être déterminé de maintes façons. L'une des façons qui illustre, sans limiter, la manière dont le nombre particulier de mots contenus dans une 1 8041 a 2096544 paga da format donné est obtenu, consiste à utiliser certains des bits des posi- à tians de droite da l'adresse virtuelle ainsi qu'il est fait allusion/la figure 3. Par exemple, lorsque l'adresse virtuelle est originalement affectée, le fait de norrmer la portion de donnée demandée, les 6 bits d'ordre de droite,en l'oc-5 curence pour cette réalisation les bits 30-35r adressent le mot ou demi-mot désiré, selon le cas. Les bits 23-29 peuvent être choisis au temps d'affectation afin de définir certaines entités de mots à l'intérieur d'une page d'un format donné. Si l'on se reports à la figure 4, l'on est en présence d'une façon de réaliser cette opération pour des entités"de 64 mots. Par exemple, en supposant 1Q que la portion de donnée désirée définie par l'adresse virtuelle a été décourver te dans le répertoire exploré, corme ressortissant à une page de 64 mots, la totalité des 64 mots peut être alors lue comme une ligne de données à la mémoire ultra-rapide de la figure 1, grâce à l'utilisation du bit a29. Si l'on découvre que l'adresse virtuelle est contenue dans une page de 25S mots, les bits-27 et 15 28 qui n'ont pas été impliqués à la génération au hasard destinés à l'adresse de répertoire pourront alors être utilisés pour définir l'une de 4 lignes de 64 mots lesquels sont alors transmis dans la mémoire ultra-rapide. Ceci correspond à A da la figure 4. De même, pour une page de 1024 mots, les bits 25-23 pourront être utilisés pour déterminer laquelle des 16 lignes de 64 mots sera transmise 20 dans la mémoire ultra-rapide. Ceci correspond à S dans la figure 4. De même encore, la totalité des bits 23-28 qui .ne sont pas entrés dans la génération au hasard correspondant à une page de 4096 mots pourront être utilisés pour déterminer lequel des 64 groupes de 64 mots compris dans la page' de 4096 mots doit être introduit dans la mémoire ultra-rapide en provenance de la mémoire princi-25 pale aux fins de traitement. Ceci correspond à C_ dans la figure 4. Il existe bien entendu de multiples autres moyens, qui sembleront évidents au spécialiste, de déterminer quelle partie de la page contenue dans la mémoire principale 4 doit être replacée dans la mémoire ultra-rapide. Une description détaillée de la stratégie à laquelle il a été fait allusion 30 ci-dœsus et qui préside aux inscriptions dans le répertoire est fournie ci-après En se reportant à la figure 5 relative à une adresse virtuelle donnée, une nouvelle inscription de répertoire doit être faite dans le premier des emplacements en suivant sa chaîne qui contient soit une inscription non valable Cen l'nccu-rence vide) ou une inscription d'une page de format intérieur. Aussi peut-il s'-35 avérer nécessaire de repositionner un format de page inférieure plus bas dans la chaîne. L'avantage de cette stratégie ainsi qu'il a été signalé ci-dessus réside en ce que l'entrée de format de page supérieur qui donnera lieu à des accès plus fréquents sera découverte plus tôt dans sa chaîne qu'une entrée de format de page inférieure. 40 Bien que le format de page ne soit pas compris dans l'adresse virtuelle, il ÛÔPY 71 18041 9 2096544 est par contre compris dans l'entrée d'inscriptions de répertoire. Ainsi qu'il a été mentionné précédemment, ceci peut être accompli de bien des façons familières à l'homme de l'art. C'est ainsi qu'après avoir procédé à l'introduction originale des inscriptions du répertoire, un plan d'inspection de table peut 5 être utilisé afin d'associer une adresse virtuelle donnée et son adresse physique dans la mémoire principale à son format de page. Un exemple-de structure qui peut être employé pour effectuer les inscriptions une fois cette association de format accomplie et représentée dans la figure B. Cette figure représente un générateur d'adresses au hasard 100 du même type que celui du générateur 10 de la figure 2, et qui peut être, et est généralement, le même élément de dispositif. Le compteur en anneau d'entrée de répertoire 102 qui peut être le même élément d'équipement que le compteur 27 de la figure 3 est relié par le bus 104 au générateur d'adresses au hasard. Une seconds entrés du générateur 100 est constituée par l'adresse virtuells associée à l'entrée à effectuer. La ligne 106 15 est une ligne reliée au compteur qui indique qu'une inscription va avoir lieu et initialise le compteur à zéro. Ledit compteur est également relié par le bus en 108 au décodeur 110 qui décode le compte. Le décodeur 110 rend active la ligne 112 si le compte est zéro modulo 4, il rend active la ligne 114 si le compte est zéro ou 1 modulo 4, et rend active la ligne 116 si le compte est 0, 1 ou 2 20 modulo 4. Les lignes indiquant un format de base correspondant à une inscription particulière se présentent ainsi comme étant les lignes 110, 120, 122 et 124. Ce qui pourrait correspondre à des indications du plan d'inspection de tables é-voqué ci-dessus. La fonction ET des lignes 112, 114 et 116 par rapport aux lignes indiquant un format de page donné permettra à une inscription qui est liée à un 25 format de page particulier d'être introduite dans un emplacement de répertoire légitime conforme à sa chaîne d'algorithme telle qu'elle est représentée dans la figure 5. Cette opération-.sera rendue plus claire par un exemple détaillé d'opérations suivantes. Chacune des lignes 118, 120, 122 et 124 sont reliées aux portes OU 126, 128, 130 et 132 respectivement. Les sorties des portes OU 128-132 30 sont reliées à deux portes ET. Par exemple, la sortie de la porte OU 132 est reliée à la porte ET 134 et à la porte ET 136 par l'intermédiaire de l'inverseur 138. De la même façon la sortie de la ligne 112 est reliée en tant que seconde entrée aux portes ET 134 et 136. Des dispositions semblables sont prises en ce qui concerne la sortie du/S6rsfy&^et la ligne 114 respectivement et la sortie du 35 circuit DU 128 et la ligne 116 respectivement. Les sorties des portes ET 134, 140, 144 et la sortie de la porte OU 126 sont reliées à la porte OU 141. La porte OU 125 est reliée directement à la porte OU 141 puisque l'inscription qui lui est appliquée indique un format de page de 64 mots qui peut être introduit avec n'importe quel compte, comme 1^indique la figure 5. La sortie du circuit OU 141 40 dans l'état actif est utilisée pour extraire, aux fins d'essai le bit de validité COPY 71 18041 10 2096544 et l'indicateur de format à l'inscription de répertoire indiquée par la sortie du générateur d'adresses au hasard afin de déterminer si les conditions sont appropriées à une inscription. Les sorties des portes ET 136, 142 et 146 sont reliées à un circuit OU 146 dont la sortie est utilisée afin d'accroître d'une uni 5 té le compteur en anneau d'entrée de répertoire 102. Le bus 154 qui contient le format de l'inscription de répertoire en cours d'accès a l'adresse fournie par le générateur d'adresses au hasard 100 est appliqué à un circuit de comparaison 152. Une seconde série d'entrées du circuit de comparaison 152 est constituée par un groupe de lignes indiquant le format 10 de page auquel serapporte l'entrée qui va être faite. Ces lignes peuvent être les mêmes que les lignes 118, 120, 122 et 124 mentionnées ci-dessus. La ligne 156 relie le circuit de comparaison à la porte ET 158, et, lorsqu'elle est active, indique que le format de page associé à l'inscription de répertoire en cours d'accès est supérieur ou égal au format de page qui se rapporte à l'inscription 15 qui va être introduite. La ligne 160 relie le circuit de comparaison 152 à la porte ET 162. La ligne 160, lorsqu'elle est active, indique que le format de l'inscription en cours d'accès est inférieur au format de page qui se rapporte à l'inscription qui va être faite. La ligne 164 relie la portion de validité du répertoire aux portes ET 158 et 162, et, lorsqu'elle est active, indique que 1'-20 adresse de répertoire en cours d'accès est dotée d'une entrée valable. La sortie de la porte ET 162 et la ligne 166 qui lorsqu'elle est active indique que l'inscription de répertoire en cours d'action contient une inscription dont le format est inférieur au format de l'entrée qui va être faite. En conséquence, la ligne 166 est reliée en tant que signal d'autorisation à la porte 168. La porte 168 25 a pour fonction de transmettre l'inscription de répertoire située à l'adresse présentemment accédée au registre 170 à des fins de stockage temporaire en atten dant qu'elle soit relogée dans un emplacement situé plus bas dans la chaîne conformément à la stratégie des inscriptions. En d'autres termes, la ligne 166 indique que l'inscription située dans l'emplacement de répertoire en cours de con-30 trôle est plus petite que l'inscription prête à être introduite dans le répertoi re. En conséquence, elle sera relogée.plus bas dans sci châine et l'entrée prête à être introduite sera dirigée par le bus 101 dans 1',emplacement de répertoire en cours d'accès grâce à l'intervention de la porte 188 et par l'intermédiaire de OU 172. La ligne 174 relie le complément du bit de validité relatif à la ran-35 gée accédée par l'adresse issue du générateur d'adresses au hasard 100, à la par te OU 172. Lorsque la ligne 174 est active cela signifie que le bit de validité correspondant à l'emplacement de l'accès est un zéro (en l'occurence: un emplacement vide) et que, partant, l'emplacement peut recevoir l'inscription prête à être introduite sans qu'il soit nécessaire de.reloger une inscription de dIus 40 petit format plus baf dans sa chaîne. , 71 18041 2096544 Il sera remarqué que le registre de mémorisation temporaire 170 contient l'identificateur d'adresse virtuelle, l'adresse physique et le format d'une inscription à reloger plus bas dans sa chaîne du fait qu'il a été déterminé que ladite inscription est relative à une page d'un format inférieur à celui de l'ins-5 cription prête à être introduite. Le champ de format S est relié par le bus 176 au dicodeur170. Le décodeur 170 est bien connu dans l'art et décode le champ de format dans les lignes significatives 180, 182, 184 et 186. Ces lignes sont respectivement reliées aux portes OU 126, 128, 130 et 132 afin de commander l'accès de l'adresse vers le bas de la chaîne dans laquelle l'inscription faite dans le 10 registre 170 sera relogée. Le fonctionnement du mécanisme d'entrée et de relogement de la figure 6 apparaît lorsque l'on étudie conjointement les figures 5 et 6. On suppose qu'une inscription de répertoire est prête à être effectuée et qu'elle se rapporte à une page de 4K dans la mémoire principale. On suppose en outre que les cinq pre-15 mières adresses de répertoire fournies avec les comptes 0-4 soient précédées d'inscriptions établies dans les formats suivants. Compte Format de page de l'inscription 0 4K 1 1 1K 2 1/16 K 20 3 1/16 K 4 1 K. 5 vide Ainsi qu'il ressort de la table ci-dessus, une inscription relative au format de base 4K. a été précédemment admise dans l'emplacement de répertoire géné-25 ré par l'algoritfwBde répartition auhasard en utilisant un compte de 0. De même, une inscription relative à un format de page de 1K. a été antérieurement admise dans le générateur d'adresses au hasard avec un compte de 1j de même encore des inscriptions de 1/16 K. ont été admises avec les comptes de 2 et 3 et une inscription de 1K a été admise avec un compte de 4. Il s'agit là d'inscription légitimes 30 ainsi qu'il ressort de la figure 5. si l'on désire maintenant effectuer une inscription de répertoire relative à une base de 4K, la ligne 124 de la figure 6 est rendue active. De même, la ligne 106 initialise le compteur en anneau d'inscriptions de répertoire 102 qui envoit une adresse de 0 au générateur d'adresses au hasard 100, lequel fournira 35 une adresse de répertoire. Le décodeur 110 reçoit également le compte de zéro dans le bus 108 et rend active la ligne 112 qui ouvre la porte ET 134, laquelle à son tour autorise la porte OU 141 à extraire le bit de validité et le champ de format de l'adresse accédée du répertoire 150. Ainsi qu'il ressort de la table ci-dessus, un mot de 4K. occupant déjà cette adresse, la ligne 164 est ren- 71 18041 12 2096544 due active. Eh outre, la ligne 4K sera également activé en tant qu'entrée du circuit de comparaison 152. L'entrée appliquée se rapportant au même format de page (4K) que celui actuellement correspondant à l'entrée présente dans l'adresse d'accès, la ligne 156 est rendue active. La combinaison des lignes 164 et 5 156 aura pour effet de rendre active la porte ET 158 et d'augmenter le compteur jusqu'à l'unité suivante en l'occurencè 0001. Ce compte et l'adresse virutelle, ou la portion d'identificateur de l'inscription à admettre, provoquent la génération par le générateur d'adresses au hasard 100 d'une seconde adresse. De fait que le'compte est 0001, le décodeur 110 rend actives les lignes 114 et 116. Né-1q anmoins, du fait que ni la porte OU 128, ni la porte OU 130 ne sont actives à ce moment, la porte OU 141 ne sera pas non plus rendue active. Cependant, grâce à l'effet des inverseurs associés aux sorties des portes OU 128 et 130, les portes ET 142 et 146 sont actives et rendent active à son tour la porte OU 148, ce qui a pour effet d'augmenter le compteur d'une unité. L'opération se 15 poursuit ainsi jusqu'à ce que l'augmentation du compteur atteigne le compte 4. A ce moment, la ligne 112 redevient active . Comme l'inscription en instance se rapporte à une page de 4K, la ligne 124 est active. En conséquence, la sortie de la potte ET 134 provoquera l'extraction par la porte OU 141 du bit de validité et du champ de format hors de l'emplacement de répertoire objet de l'accès 20 à l'adresse au hasard fournie avec un compte de quatre. A ce point, le format extrait dont il était postulé qu'il était de 1K dans l'exemple ci-dessus, est transmis par le bus 154 au circuit de comparaison 152. De même, la ligne 4K appliquée au circuit de comparaison 152 est de nouveau active. En conséquence, la ligne 160 est rendue active du fait que le format de page correspondant à l'ins-25 cription localisée dans l'adresse de l'accès est inférieur au format de page de l'inscription en instance. En outre, la ligne 164 est également active. Ceci provoque la mise en activité de la ligne 166 par la porte ET 162. A ce moment, en supposant une synchronisation adéquate bien connue du spécialiste, la ligne 166 transmet l'inscription de répertoire de 1K. par la porte 16B dans le registre 30 de mémoire temporaire 170. De la même façon, après un retard approprié permettant à l'inscription d'être transmise à l'extérieur, la ligne 166 actionne la porte OU 172 afin que la nouvelle inscription soit transmise du bus 101, dans la position à laquelle il a été accédé dans le répertoire. A ce point, la nouvelle inscription est complète mais l'inscription qui a été expulsée dans le regis-35 tre 170 doit être relogée plus bas dans sa chaîne. En conséquence, le champ de format issue du registre de repositionnement 170 est décodé dans le décodeur 178. Du fait que le format postulé est 1K, la ligne 184 rend active la porte OU 130. L'adresse virtuelle est transmise par le bus 145 au générateur d'adresses au hasard 100. De même la porte OU 143 activée, fait augmenter d'une unité le 40 compteur en anneau d'inscription de répertoire-1'amenant en l'occurence à 5-afin 1 18041 de permettre la génération d'adresses au hasard. A ce point, la ligne 114 issue du décodeur 110 est rendue active. Du fait que la porte OU 130 a été rendue active par le format de page se rapportant à l'inscription en instance de relogement plus bas dans la chaîne, la porte ET 140 rend active la porte OU 141 qui extrait alors le bit de validité et le bit de format de l'adresse de répertoire générée avec un compte de 5. Etant donné que cette adresse a été postulée comme étant vide dans la table ci-dessus, la ligne 174 rend active la porte OU 172 qui achemine l'inscription présente dans le registre de repositionnement 170 dans l'adresse de répertoire en cours d'accès. Bien que l'exemple ci-dessus se rapporte à un processus d'inscription en répertoire d'une inscription correspondant à une page de 4K. mots, et comprenne le repositionnement d'une page de format inférieur, plus bas dans sa chaîne, le spécialiste pourra construire des exemples parallèles correspondant à chaque format de page. Bien que la réalisation ci-dessus ait été décrite comme se rapportant plus particulièrement à un environnement d'unité centrale avec un système de mémoire à deux niveaux, comportant une mémoire principale et une mémoire ultra-rapide, il sera évident pour le spécialiste de l'art du calculateur que le répertoire pourrait aussi bien être utilisé pour d'autres types de mémorisation. C'est ainsi qu'il peut être utilisé entre une mémoire, à grande capacité, telle qu'une unité à disques ou à bandes, et une mémoire à faible capacité. Bien que l'on ait décrit dans ce qui précède et représenté sur les dessins, les caractéristiques principales de l'invention appliquées à un mode de réalisation préférée de celle-ci, il est évident que l'homrre de l'art peut y apporter toutes modifications de forme ou de détails qu'il juge utiles sans pour autant sortir du cadre de ladite invention. 2096544 71 18041 14 REVENDICATIONS 2096544 1.- Système de mémoire à deux niveaux utilisant un répertoire fournissant des informations d'index, caractérisé en ce qu'il comprend: - un dispositif de mémorisation pour stocker des informations d'index en 5 tant qu'inscriptions dans un jeu d'emplacements, - des moyens de génération au hasard couplés au dispositif de mémorisation, - des pramiars moyens sensibles aux moyens de génération au hasard, pour introduire les informations d'index dans le dispositif de mémorisation, et - des seconds moyens sensibles aux moyens de génération au hasard, pour 10 retrouver les informations d'index à partir du dispositif de mémorisation. revendication 1 2.- Système de mémoire selon la / , caractérisé en ce que les moyens de génération au hasard comprennent des moyens sensibles à une désignation logique de données, pour générer une pluralité d'adresses pour accéder à un sous-jeu du 15 jeu d'emplacements. revendication 2 3-"Système de mémoire selon la / , caractérisé en ce que les premiers moyens comprennent des moyens sensibles à la pluralité d'adresses pour les informations d'index dans le sous-jeu d'emplacements. on revendication 2 4.- Système de mémoire selon 1h i , caractérisé en ce que Ibs seconds moyens comprennent des moyens sensibles à la pluralité d'adresses, poùr interroger les informations stockées dans le sous-jeu d'emplacements, pour détecter une inscription contenant l'information d'index identifiée par la désignation logique des 25 données. 5.- Système de mémoire contenant des pages de données de format variable stockées dans une mémoire, et permettant la localisation d'adresse physique du début de la page de données dans la mémoire en réponse à la désignation logique 30 d'une entité de données contenue dans la page, caractérisé en ce qu'il comprend: - un répertoire ayant un jeu d'emplacements adressables pour contenir des inscriptions associant les désignations logiques des données et les adresses physiques dans la mémoire, -des moyens de génération au hasard couplés au répertoire et sensibles aux 35 désignations logiques de données, pour générer une séquence d'adresses pour accéder un sous-jeu du jeu d'emplacements du répertoire, - des prérmters moyens sensibles aux moyens de génération, pour introduire une inscription associant une désignation logique et une adresse physique, dans un emplacement de sous-jeu d'emplacements, et 40 - des seconds moyens sensibles aux moyens de génération pour interroger les 71 18041 2096544 inscriptions dens le sous-jeu d'emplacements, pour détecter l'inscription associant uns désignation logique et une adresse physique. revendication 5 B.- Système de mémoire selon la/ , caractérisé en ce que les premiers moyens comprennent des moyens sensibles au format de page relatif à chaque inscription, pour introduire une inscription relative à un format de page supérieur à un emplacement du sous-jeu d'emplacements du répertoire, avant d'introduire une inscription relative à un format de page inférieur.