Brevet FR2059687A1 — publié le 19710604

La présente invention concerne les systèmes de mémorisation de l'information. L'informatique fait un usage croissant des mémoires de masse à accès aléatoire, telles que les mémoires à disques de forte capacité» Il faut généralement que la modification des enregistrements présents dans le fichier et l'addition de nouveaux enregistrements s'effectuent rapidement et de manière simple» Les enregistrements doivent avoir des adresses significatives à l'intérieur de la mémoire pour permettre la lecture sélective d'un enregistrement quelconque. Le système d'adressage le plus simple consiste à allouer un bloc de mémoire à chaque enregistrement qui peut être nécessaire, les enregistrements étant rangés dans un ordre logique quelconque, par exemple séquentiellement selon leur numéro de référence» Le numéro de référence d'un enregistrement est ainsi lié de manière simple à une adresse de bloc» Un tel système présente deux inconvénients. Le premier est qu'à un instant donné, un nombre important d'enregistrements peut ne pas exister. Si les numéros de référence des enregistrements correspondent à des numéros de compte affectés en séquence, il est clair qu'il n'y aura pas d'enregistrement pour les comptes qui ont été clos ni pour les nouveaux comptes qui n'ont pas encore été ouverts» Deuxièmement, la longueur des enregistrements peut varier dans des proportions considérables, de sorte que de nombreux blocs de la mémoire ne sont que partiellement remplis car la longueur du bloc standard doit être suffisante pour contenir l'enregistrement le plus long» Diverses tentatives ont été faites pour améliorer le coefficient d'utilisation de la mémoire par rapport à celui que procure un système d'adressage simple» Ces solutions font principalement appel à la programmation et peuvent être classées en deux catégories générales» Dans la première catégorie, les informations d'adresse nécessaire sont contenues dans une partie séparée de la mémoire sous la forme d'une .table ou annuaire des adresses» Chaque entrée de l'annuaire contient une identification de l'enregistrement, par exemple les adresses de référence des enregistrements» Ainsi, pour obtenir un enregistrement contenu dans la mémoire, on parcourt séquentiellement l'annuaire pour trouver l'entrée correspondante qui fournit l'information d'adresse nécessaire pour accéder à la mémoire» BAD ORIGfNAL " 70 31112 2 2059687 La seconde catégorie de solutions utilise une technique d'affectation aléatoire des adresses. Par exemple, une séquence d'opérations arithmétiques peut être effectuée sur une partie des données de l'enregistrement pour produire un résultat qui constitue l'adresse» Cette technique peut conduire à donner la même adresse à plusieurs enregistrements, de sorte qu'il 5 est nécessaire de vérifier que l'adresse calculée est vide avant d'y introduire un enregistrement. Dans le cas où l'adresse est déjà occupée, un sous-programme de débordement détermine une nouvelle adresse et introduit à l'adresse initiale un "pointeur" indiquant la nouvelle adresse. Ces techniques plus élaborées améliorent considérablement le 10 coefficient d'utilisation de la mémoire. On conçoit cependant que la recherche et la mise à Jour de l'annuaire ou le calcul des adresses aléatoires impliquent un temps improductif important. Selon une caractéristique essentielle de l'invention, un système de mémorisation d'enregistrement de données comprend une mémoire 15 de masse à plusieurs emplacements adressables,un système de mémoire associa-, tive à plusieurs emplacements destinés à recevoir les informations d'adresse, un dispositif pour introduire initialement des enregistrements dans la mémoire de masse, un dispositif pour introduire dans la mémoire associative une indication de référence pour chaque enregistrement mémorisé et une information 20 spécifiant l'adresse de ce dernier dans la mémoire de masse, un dispositif interrogeant la mémoire associative pour y lire l'information d'adresse d'un enregistrement pour lequel a été formulée au moins une demande partielle dlaccès, enfin un dispositif utilisant cette information d'adresse pour lire dans la mémoire de masse l'enregistrement spécifié par ladite demande d'accès. 25 D'autres caractéristiques et avantages de l'invention rassor tiront de la description d'une forme de réalisation détaillée et des dessins sur lesquels ; La figure 1 est un schéma synoptique d'un système de mémorisation sur disques. 30 La figure 2 représente une forme particulière de l'unité de. test de la figure 1» Les enregistrements de données sont contenus dans une mémoire de masse qui, dans la forme illustrée, est une mémoire à disques 1. La mémoire à disques 1 est de conception classique, c'est-à-dire qu'elle corn-35 prend plusieurs disques rotatifs d'enregistrement magnétique auxquels sont ORIGINAL* 70 31112 3 2059687 associées des têtes mobiles de lecture et d®enregistrement» Chaque disque comporte plusieurs pistes d'enregistrement subissant chacune une division de principe en plusieurs secteurs- Chaque secteur constitue un emplacement de mémoire adressable dont l'adresse est constituée par une série de chiffres spécifiant un disque particulier, une piste de ce disque et un secteur de cette piste. Un enregistrement, à ranger dans la mémoire à disque 1 peut être temporairement contenu dans une mémoire intermédiaire d'accès 2S telle qu'une matrice de tores, qui est associée à une unité centrale de traitement 3. L'unité de traitement 3 élabore une instruction de transfert de données qui comprend l'adresse de l'emplacement de la mémoire à disques 1 à laquelle doit débuter l'inscription de 1'enregistrement. Pour simplifier l'explication, on supposera que les enregistrements sont introduits séquentiellement dans la mémoire à disques 1 et que l'unité de traitement 3 conserve l'adresse du dernier emplacement de mémoire qui a été utilisé . L'adresse de départ de l'enregistrement en cours d'inscription est donc l'adresse suivant en séquence. L'adresse de départ peut cependant être déterminée par d'autres procédés. L'adresse de départ est appliquée par une ligne 4 à un sélecteur d'adresse 5 pour préparer la mémoire à disques 1 à la réception des données, c'est-à-dire pour positionner et/ou choisir la tête d'enregistrement voulue. A la fin de cette opération, un signal de commande est transmis par une ligne 6 à la mémoire à tores 2 pour faire débuter la lecture de l'enregistrement. L'enregistrement est transmis à une unité d'entrée/ sortie 7 qui reçoit également l'indication du secteur et d'autres signaux de synchronisation transmis du sélecteur d'adresse 5 par une ligne 8. Chaque enregistrement de données est généralement constitué par un nombre grand et variable d'articles individuels. On supposera pour simplifier la description que chaque article occupe un emplacement de mémoire. La position d'un enregistrement dans la mémoire à disques 1 est donc parfaitement déterminée lorsque l'on connaît les adresses du premier et du dernier emplacement de mémoire qu'il occupe. En variante, la position de l'enregistrement peut être spécifiée par ses adresses relatives de début et de fin et l'adresse de départ de la mémoire de masse. Si l'on utilise un système séquentiel pour charger initiale-laont les enregistrements dans la mémoire de masse, cette dernière sera fortement remplie. Ultérieurement, il peut devenir nécessaire de modifier ou 70 31112 4 2059687 d'allonger certains des enregistrements. Dans ce dernier cas, on utilise un système appelé "chaînage" des adresses consistant à transférer le débordement de la zone d'enregistrement initiale dans une ou plusieurs zones physiquement séparées de la mémoire à disques 1» La zone initiale fournit l'adresse de la première zone de débordement qui fournit l'adresse de la seconde zone de 5 débordement, et ainsi de suite. On peut ainsi obtenir l'enregistrement complet, bien qu'il soit physiquement fragmenté dans la mémoire à disques 1. En même temps que l'enregistrement est transféré de la mémoire à tores 2 à la mémoire à disques 1, l'unité de traitement 3 transmet par une ligne 10 l'information d'adresse nécessaire à une mémoire associative 10 9 de construction classique. L'entrée consiste essentiellement en une information identifiant l'enregistrement et en une information définissant son adresse dans la mémoire de masse 1» Le détail du format de cette information peut être choisi en fonction des processus de manipulation d'enregistrement qu'utilise l'unité de traitement 3» Par exemple, on peut spécifier les 15 adresses fictives de début et de fin d'un fragment d'enregistrement, l'adresse de "chaînage" correspondant à l'adresse de début du fragment suivant dans la mémoire et l'adresse de début du fragment recherché. Ce processus est valable lorsque le programme de l'unité de traitement 3 identifie un enregistrement par ses adresses fictives. En variante, les adresses fictives peuvent être 20 complétées ou remplacées par une autre indication de référence d'enregistrement, par exemple par un nom ou un numéro d'enregistrement. Un autre format utilisable peut comprendre le nom de l'enregistrement, le nombre d'articles que contenaient les fragments précédents, les adresses de début et de fin de ce fragment dans la mémoire de masse et une adresse de "chaînage" 25 conduisant au fragment suivant. Quel que soit le format adopté dans la mémoire associative 9, les informations que contient l'entrée suffisent pour accéder à la totalité, à une partie ou à un article individuel d'un enregistrement quelconque de la mémoire à disques 1. L'information d'identification de l'enregistrement ou 30 de la partie d'enregistrement est transmise sur une ligne 11 de l'unité de traitement 3 à la mémoire associative 9» Cette information est comparée en parallèle avec la partie d'identification d'enregistrement de toutes les entrées de la mémoire 9, de manière connue, et toutes les entrées qui sont identiques à l'information sont marquées. La mémoire associative utilisée 35 dans l'invention peut être du type décrit dans le brevet des EUA n° 3 339 l8l 70 31112 2059687 ou dans le brevet britannique n° 973 866, Les entrées marquées sont extraites de la mémoire 9 et transmises à une unité de test 12 qui reçoit également l'information d'entrée sur une ligne 11» L'unité 12 détermine l'adresse de la donnée recherchée dans la mémoire à disques 1= Par exemple, si l'on désire obtenir un article particulier, l'unité de test 12 peut déterminer à partir 5 des adresses fictives le fragment d'enregistrement qui contient l'article désiré, puis calculer l'adresse de ce dernier dans la mémoire à disques. Cette adresse est transmise sur une ligne 13 au sélecteur d'adresse 5 qui commanda la lecture de la donnée dans la mémoire à disques 1 et son transfert à la mémoire 2 par l'intermédiaire de l'unité d'entrée/sortie 7, selon un 10 processus analogue à celui qui a servi à l'introduction d'une donnée. Les opérations particulières qui sont effectuées par l'unité 12 dépendent du format des entrées de la mémoire associative 9 et du type de séleotion, par exemple si l'on désire un fragment entier ou.un article individuel, La figure 2 représente une forme de réalisation de 15 l'unité de test 12 permettant de calculer une adresse d'article dans la mémoire de masse 1, Ainsi, dans le cas où l'on utilise le premier format décrit ci-dessus, l'adresse fictive indique le fragment particulier de l'enregistrement, de sorte qu'une seule entrée de la mémoire 9 est marquée. L'unité de test 12 calcule ensuite l'adresse de l'article en soustrayant au 20 moyen d'un circuit soustracteur 14 l'adresse fictive de début du fragment A2 de l'adresse fictive de l'article A^ et en ajoutant le résultat A^ - A2 à l'adresse de début du fragment A^ dans la mémoire de masse. L'adresse de l'article dans la mémoire de masse 1 est ensuite transmise au sélecteur d'adresse 5 P&r la ligne 13. 25 On comprendra que l'accès presque instantané à toutes les informations d'adresse d'enregistrement de la mémoire associative 9,combiné à la simplicité des calculs d'adresse effectués par l'unité 12, permet d'accéder à n'importe quelle partie de la mémoire de masse 1 en un temps très largement inférieur à celui que permettent les systèmes classiques, 30 comprenant une mémoire à disques et une mémoire à tores dont les temps d'accès de base sont comparables à ceux du système de l'invention. Dans l'exemple décrit, on utilise une mémoire à disques 1 coane mémoire de masse et une mémoire à tores 2 comme mémoire à accès immédiat. Cependant, d'autres formes de mémoires peuvent être utilisées avec les ^5 mêmes résultats. La mémoire de masse 1 peutspar exemple,être une mémoire à BAD ORIGINAL 70 31112 6 2059687 tambouxsou une grosse mémoire à tores à accès relativement lent, alors que la mémoire à accès immédiat peut être à film magnétique mince ou à semiconducteurs^ La.mémoire associative 9 peut être partagée par plusieurs unités de traitement en mode multiplex pour commander l'accès à une mémoire de masse dans un système de multitraitement... De plus, le circuit de soustraction 14 et le circuit d'addition 15 peuvent être réalisés de n'importe quelle manière connue. 70 31112 7 2059687 REVENDICATIONS 1. Système de mémorisation d«enregistrement de données comprenant une mémoire de masse à plusieurs emplacements d'enregistrements et un circuit d'introduction initial d'enregistrements de données dans la mémoire de masse, ainsi qu'une mémoire associative qui peut être interrogée au moyen d'une demande d'accès^ ledit système étant caractérisé en ce qu'une information d'adresse comprenant une indication de référence pour chaque enregistrement de données contenu dans la mémoire et une information spécifiant l'adresse de l'enregistrement correspondant dans la mémoire de masse est lue dans la mémoire associative à la suite de l'interrogation par une demande d'accès et est transmise à un circuit de test qui fournit une adresse d'article dans la mémoire de masse correspondant à la demande d'accès. 2. * Système selon la revendication 1, caractérisé en ce qu'une entrée du circuit de test reçoit l'information d'adresse et en ce que sa sortie commande un circuit sélecteur d'adresse pour choisir un emplacement de la mémoire de masse. x 3. Système selon la revendication 2, caractérisé en ce que la sortie du circuit de test est l'adresse d'un emplacement de la mémoire de masse correspondant à l'information d'adresse. 4. Système selon la revendication 3, caractérisé en ce que l'introduction initiale des enregistrements de données dans la mémoire de masse se fait par une mémoire intermédiaire d'accès et un dispositif d'entrée/ sortie. 5. Système selon la revendication 3» caractérisé en ce que l'unité de test comprend des circuits de calcul d'une adresse de la mémoire de masse à partir de l'information d'adresse lue dans la mémoire associative,,