Brevet FR2072038A1 — publié le 19710924

La présente invention concerne les mémoires associatives et non-associa-tives. Il n'a pas inutile de rappeler ici quelques-unes des caractéristiques de ces mémoires, ainsi que la terminologie afférente à ces dernières. L'unité élémentaire d'emmagasinage dans une mémoire est appelée une ''"cellule de mémoi-S re". Par exemple, une paire de transistors peuvent §tre interconnectés de manière à constituer un circuit bistable qui emmagasine un "1" ou un "0" selon que l'un ou l'autre des transistors est rendu conducteur. Il est commode d'appeler le transistor qui est rendu conducteur pour emmagasiner un "1", le transistor "un" et le transistor qui est rendu conducteur pour emmagasiner 10 un "0", le transistor "zéro". Au cours d'une opération de lecture^ le transistor "un" ou le transistor "zéro" est rendu conducteur pour représenter le bit qui doit être emmagasiné dans la cellule. Au cours d'une opération de lecture, les états conducteurs des transistors sont détectés, par exemple, en détectant la différence de tension entre les bornes collecteur des transis=» 15 tors. Au cours d'une opération de recherche associative, la cellule est lue de manière à obtenir une comparaison avec un bit quë l'on appelera un "bit de recherche". Par exemple, un 0 peut être recherché en déterminant l'état du transistor "un" et en interprétant son état conducteur comme un désaccord» □ans une mémoire associative, une cellule de mémoire fournissant quatre 20 états d'emmagasinage est particulièrement utile. Ces cellules de mémoire peuvent Être constituées par deux circuits binaires a'emmagasinage et l'état de la cellule de mémoire peut être représenté par les états individuels des deux circuits binaires. De la sorte, un état 10 de la cellule représente un "1" binaire, et.un état 01 de la cellule représente un "0" binaire. Etant 25 donné qu'une opération de recherche est effectués en lisant les "1" éventuellement en désaccord, une cellule de mémoire se trouvant dans l'état 00 ne peut pas produire de désaccord et cet état est appelé ci-après l'état "indifférent". De façon similaire, l'état 11 de la cellule représente un désaccord permanent. 30 Dans le cas d'une mémoire non-associative, plusieurs cellules rie mémoire à transistors neuvent être réalisées dans une matrice ù rangeas et ?i colonnes sur un même bloc de silicium. Les celluli.s sont interconnectées au moyen de fils de rangées et rie colonnes qui permettent de sélectionner une unique cellule en vue d'un oDération de mémoire. D'ordinaire, une cellule de mémoire 35 est conditionnée en vue d'une opération ds mémoire en appliquant des tensions coïnciccntns aux filrj correspondants de rangée et rc colonne. Un ril supplémentaire appel;} "fil de détection ce bits" permet do recevoir le signal produit au cours g'uns opération de lactura et d'acheminer un signal pour commander celui des transistors nui est rendu conducteur au cours d'une opération 40 c'écriture. Les fils rie rangée et de colonne da la cellule rie mémoire que n ~BAD ORIGINAL 70 44220 2072038 l'on adresse sont dé-finis par uns adresse fournie à la mémoire en vue d'une opération de mémoire. Des circuits appelas "décodeurs" excitent le fil de rangée et le fil de colonne appropriés,, Cette disposition dos cellules de mémoire est appelée "tridimensionnelle" parce que les cellules sont rangées dans deux dimensions sur chaque bloc et que les blocs, qui représentent différentes positios de bit d'un mot de mCnoire, constituent une troisième dimension d'adressage. Les mémoires associatives sont généralement employées dans une disposi» tion bidimensionnelle. Les rangées de cellules de mémoire représentent des mots de données et les sorties des cellules peuvent Être interconnectées le long de la cimension de mot de l'ensemble pour détecter un signal de désaccord provenant de n'importe quelle cellule du mat. Les cellules sont interconnectées dans la dimension des colonnes avec les circuits relatifs à une position de bit associée. L'inconvénient de cette disposition bidimensionnelle est que le bloc sur lequel la mémoire est formée doit posséder une connexion externe pour chaque rangée et pour chaque colonnade 1'ensemble. Etant donné que le nombre de connexions qui peuvent être réalisées avec un bloc est restreint, cette disposition bidimensionnelle n'utilise pas de façon, efficace la capacité d'un bloc de contenir un grand nombre de cellules de mémoire. Au contraire, dans le cas de l'adressage tridimensionnel de mémoires non associatives, un petit nombre de connexions au bloc suffisent pour acheminer les signaux d'adressage qui sont décodés pour sélectionner une cellule de mémoire parmi un grand nombre de cellules. L'un des objets de la présente invention est de fournir une nouvftlîe mémoire associative améliorée dans laquelle les blocs qui sont disposés en vue d'un adressage non associatif sont utilisés de façon associative. Dans la mémoire associative de la présente invention, un nombre choisi de blocs, chacun desquels possède un ensemble de circuits de mémoire binaire pouvant.Stre adressés de façon non associative, sont disposés dans une matrice à rangées et à colonnes. Chaque colonne représente une position de bit de mots emmagasinés dans la mémoire0 Les rangées fournissent une capacité supplé*» mentaire d'emmagasinage de mots» Les mots emmagasinés dans la mémoire sont disposés en catégories identifiées par une adresse classique non-associative. Dans un exemple utilisé ci»après, chaque catégorie est une table qui peut être consultée pour rechercher une fonction particulière logique ou arithmétique. La partie non associative de l'adresse est fonction de l'opération particulière qui doit Stre effectuée, et permet d'identifier un ensemble de cellules de mémoire pouvant être recherchées de façon associative pour exécuter la fonction requise. La mémoire comprend un registre appelé "registre de recherche" qui emmaBAD ORIGINAL 70 44220 3 2072038 gasine un mot qui doit Être recherché dans la mémoire. Chaque position de bit du registre de recherche est associée à une position de bit particulière -de la mémoire et à la colonne correspondante de la matrice d'ensembles de mémoire. La mémoire comprend également de préférence un registre de masque 5 qui contient un mot définissant les positions de bit de la mémoire qui ne doivent pâs être recherchées. Un ensemble de circuits binaires est adressable de façon non-associative en fonction d'une adresse comportant n bits. Dans la mémoire de la présente invention, des paires de circuits binaires constituant une cellule de mémoire 10 sont adressées par n-1 des bits de l'adresse. Le bit de l'adresse restant permet d'adresser l'un ou l'autre des circuits binaires aux fins d'opérations d'écriture, de lecture et de recherche associative. Plusieurs circuits logiques et dispositions de mémoire permettant d'utiliser le bit associatif sont décrits ci-après. 15 D'autres objets, caractéristiques et avantages de la présente invention rassortiront mieux de l'exposé qui suit, fait en référence au dessin annexé à ce texte, qui représentent un mode de réalisation préféré de celle-ci. La mémoire représentée sur le dessin comprend quatre ensembles de mémoires 12, 13, 14 et 15 disposés de façon à représenter une mémoire comportant un 20 nombre choisi quelconque d'ensembles. Un ensemble de mémoire se compose de préférence de B4 circuits bistablss à transistors disposés en huit rangées et huit colonnes. Une cellule de mémoire peut être adressée en vue d'une opération de mémoire en appliquant des tensions coïncidentes à un fil de rangée et à un fil de colonne. Les fils de colonnes, ou fils x, sont identifiés 25 de façon classique au moyen des lettres xQ à x7 et xfl à x15, et les fils de rangée ou fils y, sont identifiés à l'aide des lettres yO à Y7. Chaque ensemble de mémoires possède une paire de fils de détection de bits 17 et 18. Un ampli® ficateur de détection 20 est connecté aux fils 17 et 18 afin de recevoir les signaux produits par une cellule adressée pendant une opération de lecture 30 ou de recherche. Un circuit 21 de commande de bits est connecté aux fils 17 et 18 pour produire un signal servant à contrôler si la cellule adressée se trouve dans son état "1" ou dans son état "0" pendant une opération d'écriture. Ces caractéristiques de la mémoire sont classiques dans les mémoires non-associatives. Les composants du circuit décrit ci-après font fonctionner 35 ces ensembles non-associatifs en vue d'opérations de recherche associative et d'opérations de lecture et d'écriture non-associatives. Un mot devant faire l'objet d'une recherche dans la mémoire est emmagasiné dans un registre 25., les positions de bit x et y définissant une catégorie générale devant faire l'objet de la recherche, et les positions de 40 bit S définissant une recherche associative dans cette catégorie générale. 70 44220 4 2072038 (Des exemples seront donnés ci-après). Dans le registre de masque 27, chaque position de bit détermine si la position de bit correspondante de la mémoire doit ou non faire l'objet d'une recherche. De façon classique, le masquage permet de limiter la recherche à une partie choisie de chaque mot de la mémoi» 5 re. Un décodeur 28 est connecté de façon à recevoir les bits yO, y1 et y2 de l'adresse et exciter celle des huit lignes y, yO à y7, qui leur correspond. La sortie du décodeur 23 est fournie à chaque ensemble de mémoire coirme indiqué sur la figure. 10 Un décodeur 29 est connecté de façon à recevoir les deux bits x du regis tre 25 et de fournir quatre sorties décodées 30, 31, 32 et 33. Un ensemble . de circuits logiques CET) 33 autorise la transmission de chacune des quatre sorties du décodeur 29 à l'un ou l'autre des fils de la paire associée de fils x des ensembles de mémoires 12 et 14. Par exemple, la sortie 30 peut 15 Être connectée aux fils x7 ou xB selon l'état des portes logiques associées 39 et 40. Un ensemble similaire de circuits logiques 48 est disposé de manière à coupler les sorties 30 à 33 de décodage x aux huit fils de colonnes, x8 à x15, des ensembles de mémoire 13 et 14. 20 Les bits x et y du registre 25 définissent ainsi dans la position corres pondante dans chaque ensemble de mémoire, une cellule de mémoire composée de deux circuits binaires de mémoire. Comme expliqué ci-après, les portes 38 et 48 sont commandées de manière à sélectionner l'un des"circuits binaires dans la cellule de mémoire adressée en vue d'opérations dB lecture, d'écriture 25 et de recherche. Un circuit logique 50 reçoit le bit S1 du registre 25 et le bit M1 du registre de masque 27, et produit les sorties 51 et 52. Un "1" dans le registre de masque 27 signifie que la position de bit correspondante de l'ensemble de mémoire est masquée et que l'opération de recherche ne doit pas avoir 30 lieu. Un "0" dans le registre 27 signifie que la position de bits est démasquée et qu'une opération de recherche doit avoit lieu. La sortie 51 est la fonction logique S1M1 et la sortie 52 la fonction logique S1M1, De la sorte, lorsque la position S1 est masquée, les sorties 51 et 52 ont toutes deux la valeur logique "0". Lorsque la position de bit S1 est démasquée, la sortie 52 a 35 la valeur de la position de bit S1 et la sortie 51 a la valeur complémentaire. De façon similaire, un circuit logique 54 est connecté de manière à recevoir les bits S0 et MO et è produire la fonction S0M0 à une sortie 55. et la fonction SOMO à une sortie 56. Les sorties 55 et 56 sont connectées de manière à commander les portes 48 de la façon décrite ci-dessus relative-40 ment au circuit logique 50 et aux portes 38. 70 44220 5 2072038 D'autres composants de la mémoire sent successivement décrits ci-après à propos des opérations d'écriture, de lecture et de recherche. Dans le cas d'une opération d'écriture, la mémoire est adressée de façon non-associative en fonction de la partie x et y de l'adresse dans le registre 5 25. L'opération d'écriture nécessite deux cycles de mémoire, un cycle pour écrire dans un circuit binaire de la cellule de mémoire adressée,, et un second cycle pour écrire dans l'autre circuit binaire de la cellule adressée. Tous les H1" et tous les "0M des deux parties de l'opération d'écriture peuvent être chargés dans la partie S du registre 25, et les "O" peuvent être chargés 10 dans le registre 27t ou bien, les portes 33 et 48 peuvent Stre conmandées de façon à sélectionner individuellement les deux circuits binaires de la cellule adressée. Le mot adressé est de plus défini en ce qui concerne sa position dans les ensembles 12 et 13 ou dans les ensembles 14 et 15. Les circuits de commande des ensembles 12 et 13 sont rendus actifs aux fins d'une 15 opération d'écriture par une ligne commune de sélection 82£ et les circuits de commande des ensembles 14 et 15 sont ds même rendus actifs par une ligne commune 63. (Les interconnexions entre les lignes 62 et entre les lignes 63 ne sont pas représentées sur la figure). Les circuits de commande de la position de bit "1H sont commandés par une ligne commune 64 de façon à écrire 20 un "1" ou un "0", et les circuits de commande de la position de bit "0" sont de même interconnectés à une ligne commune 65 pour commander une opération d'écriture. Par exemple, dans le cas d'une opération d'écriture en deux parties concernant un mot dans les ensembles 12 et 13, les positions de bit S1 et S0 reçoivent chacune un "1" pour sélectionner les cellules de mémoire associées 25 aux lignes 52 et 56. Les lignes 64 et 65 sont excitées individuellement en fonction des données à écrire, et les lignes 62 sont commandées de façon à rendre actifs les circuits de commande correspondants. Les cellules de mémoire dans les ensembles 14 et 15 sont également conditionnées en vue d'une opération d'écriture. 30 Pendant l'opération décrite ci-dessus les cellules de mémoire dans les ensembles 14 et 15 sont également rendues actives par leurs fils x et y pour une opération d'écriture. La ligne commune 63 des circuits de commande associés est commandées soit de façon à empêcher une opération d'écriture dans les ensembles 14 et 15,s oit de façon à permettre à l'un ou l'autre de ces deux 35 ensembles de subir l'opération d'écriture qui vient d'être décrite dans le cas des ensembles 12 et 13. Des "0" sont ensuite chargés dans les positions de bit S du registre 25 pour corrmencer la partie suivante de l'opération d'écriture. Chaque circuit binaire de la cellule adressée peut ainsi être placé dans l'un ou l'autre 40 de ses états et chaque cellule peut Stre placée dans l'un quelconque de ses 70 44220 6 2072038 quatre états possibles. Dans le cas d^une -opération de lecture, est chargée dans la partie x et y du registre 25 l'adresse des cellules de mémoire devant être lue, et des "0" (ou des "1" pour lire l'autre circuit binaire du mot en mémoire) 5 sont chargées dans la partie S du registre 25» En réponse à ces signaux, la cellule de mémoire adressée dans chaque ensemble produit un signal sur les lignes 17 et 18 à l'entrée de son amplificateur de détection 20. Des portes B7 sont fournies pour sélectionner l'ensemble devant Stre lu.Chaque porte 67 reçoit une entrés de l'amplificateur de détection associatif. Les 10 portes 67 des ensembles 12 et 13 reçoivent un signal commun de commande 66, et les portes des ensembles 14 et 15 reçoivent un signal commun de commande 69. Les portes dîune position de bit commune ont une ligne de sortie commune 70 qui achemine le signal aux ensembles sélectionnés pendant une opération de lecture. 15 Pour lire un mot adressé de la mémoire, la ligne de contrôle choisie 68 ou 69 est excitée. Si plus d'une ligne 68 ou 69 est excitée aux fins d8opé«* rations de lecture, la fonction logique OU des deux mots adressés apparaît sur les lignes 70. Dans le cas d'une opération de recherche, le mot contenu dans le registre 20 25 est disposé de telle sorte que les parties x et y du mot définissent une catégorie générale et que les bits S définissent les caractéristiques devant faire l'objet d'une recherche associative dans la catégorie adressée. Par exemple, lorsque des tables de fonctions logiques et arithmétiques sont emmagasinées dans la mémoire, la partie x et y du mot contenu dans le registre 25 25 définit un type particulier d'opération à effectuer, une addition, par exemple, et les cellules de mémoire correspondantes qui contiennent la table relative à cette fonction. Les bits S du registre 25 sont des entrées logiques de la table relative à cette opération. Chèque amplificateur de détection 20 des ensembles 12 et 13 est connecté 30 de manière à enclencher une bascule 73. L'entrée d'enclenchement de cette bascule se présente sous la forme d'une fonction logique OU qui maintient un isolement entre les différentes lignes de lecture 70, Chaque amplificateur de détection 20 des ensembles 14 et 15 est connecté de façon similaire pour enclencher une bascule 74. Les entrées de restauration des bascules 73 et 35 74 sont connectées à une ligne commune de restauration 75 afin de restaurer lss bascules au début de l'opération de recherche. Lorsque la position de bit SI dans le registre 25 contient un "1", un 10 indiquant un désaccord ou un 00 indiquant un état d'"indifférence" doit être recherché dans les cellules de mémoire adressées des ensembles 12 et 14. 40 Lorsqu'un "0" est emmagasiné dans la position de bit S1, un 01 (désaccord) 70 44220 7 2072038 ou un 00 ""indifférence" doit être recherché dans les ensembles 12 et 14. Un 11 dans une cellule de mémoire adressée constitue un désaccord Cà moins que la position correspondante du registre de masque 27 ne soit mis sur un "1" afin de masquer cette position de bit). 5 Dans la demande de brevet n° 6920454 déposée en France par la demanderes se le 19 Juin 1969, est décrite une mémoire permettant à la fois un adressage associatif et non-associatif, et plus particulièrement le circuit de. mémoire binaire préféré de la présente invention. D'autres circuits de mémoire binaire appropriés sont bien connus dans l'art antérieur. 10 L'ensemble peut ne posséder que des circuits de mémoire ou peut comprendre également les circuits de décodage d'adresses x et y. Lorsque les circuits de décodage se trouvent sur le bloc d'un ensemble, un bit d'adresse qui est appliqué à l'ensemble est développé à partir du bit S correspondant du mot de recherche. Le bit M est appliqué par l'intermédiaire de circuits dechrono-15 logie classiques ou autres moyens disponibles pour inhiber ou permettre de façon sélective une opération de lecture non associative. Le rapport existant entre ces deux réalisations sera mieux compris si l'on admet que le décodeur x 29 à trois bits, les blocs logiques 50 et 54, et les portes 38 et 48, constituent pour chaque position de bit de mémoire un décodeur à quatre bits dont 20 le passage est autorisé en fonction du bit M. Dans la description qui précède, on a souligné les avantages que présente l'utilisation d'ensembles standard non-associatifs. En fait, la disposition hybride mentionnée ci-dessus possède un avantage significatif par rapport à une mémoire complètement associative en ce qu'elle permet de diminuer le 25 nombre de connexions à un bloc qui sont indispensables pour un ensemble de n'importe quelle dimension. De plus, la plupart des données peuvent être disposées sous une forme hybride et le rendement d'une mémoire hybride peut Stre substantiellement égal à celui d'une mémoire complètement associative. La disposition hybride est donc utile dans le cas d'ensembles spécifiquement 30 conçus en vue de son utilisation aussi bien que dans le cas d'ensembles conçus en vue d'une utilisation non associative. Les bits x et y de l'adresse peuvent également Stre développés de façon associative ou partiellement associative. Par exemple, une adresse non-asso-ciative spécifique peut contenir des adresses qui doivent faire l'objet d'une 35 recherche de façon associative, puis Être utilisées au cours d'une opération de recherche suivante de la façon non associative décrite ci-dessus. L'article écrit par A. Wein berger dans la publication intitulée "IBM Technical Disclosure Bulletin" datée de Mai 1969, page 1744, comporte plusieurs exemples d'applications éventuelles de la méthode de recherche dybride. D'autres 40 exemples seront évidents pour l'homme de l'art. 70 44220 8 2072038 Bien que l'on ait décrit dans ce qui précède et représenté sur le dessin, les caractéristiques essentielles de l'invention appliquées à un mode de réalisation préféré de celle-ci, il est évident que l'homme de l'art peut y apporter toutes modifications dB forme ou de détail qu'il juge utiles, sans pour autant sortir du cadre de ladite invention. 70 44220 9 2072038 REVENDICATIONS 1.- Mémoire associative caractérisée en ce qu'elle comprends une pluralité d'ensembles de circuits ds mémoires binaires chacun d'eux étant adressable non associativement car une adresse de n bits et chaque en*» 5 semble définissant une position de bit dans la mémoire., des premiers moyens fournissant une adresse de r=»1 faits qui. représente une catégorie prédéterminée de données dans laquelle uns rechsrche doit s'effectuer et définit une cellule de mâmoirs formée ds deux circuits de mé» moire binaires dans une position correspondants, 10 des seconds moyens fournissant un bit supplémsntaira pour ors adressage associatif pour chaque position ds bit ds mémoire,, des troisièmes moyens sensibles auxdits bits et au bit supplémentaire pour chaque position de bit pour adresser l'un des circuits binaires sélectionné de chaque cellule peur une opération ds recherche,, s£ 15 des quatrièmes moyens connectant les ensembles de mémoire pour détecter les conditions d'accord et de désaccord des mots adressés pendant une opération de recherche. 2.~ Mémoire associative selon la revendication 1, caractérisée en es qu'elle comprend un registre de masque» et en ce que las troisièmes moyens comprennent 20 des moyens sensibles au contenu du registre ds masque pour annuler une opéra® tion de recherche dans l'ensemble correspondant. 3.- Mémoire associative selon la revendication 2, caractérisée en ce que les troisièmes moyens comprennent: un premier et un second décodeurs communs à tous les ensembles et connec~ 25 tés pour décoder les n-1 bits fournis par les premiers moyens, des moyens pour connecter les sorties du premier décodeur aux points correspondant dans chaque ensemble, et des moyens pour chaque ensemble sensibles aux seconds moyens et au contenu du registre de masque pour aiguiller la sortie du second décodeur vers l'un 30 ou l'autre, ou aucun, d'une paire de circuits d'emmagasinage binaires définis par les n-1 bits. 4.- Mémoire associative selon la revendication 3, caractérisée en ce qus les premiers et seconds moyens comprennent un registre commun pour recevoir un mot devant faire l'objet d'une recherche. 35 5.- Mémoire associative selon la revendication 2, caractérisée en ce que les 1 BAD ORIGINAL 70 44220 10 2072038 troisièmes moyens comprennent un décodeur a n bits formé intégralement avec l'ensemble associé, 6.» Mémoire associative secson la revendication 5, caractérisée en ce qu'elle comprend plusieurs ensembles pour chaque position de bit èt plusieurs quatrièmes moyens pour des groupas d'ensembles formant un mot-, 7a- Méthode d'exploitation d'une mémoire ayant à la fois un adressage associatif at un adressage non^asaociatif„ caractérisée en ce qu'aile oompï-end uns recherche associative dans uns caté~tiru.3 définie par la partis non^asso® ciative d'une adresse fournie à la mémoire et la lecture du mot identifié par la recherche, puis une recherche cfssooi&iive dang la ù^tégoris difinie par la mot lu= ô„- Méthode d'exploitation d'une pluralité d"ensembles nan^asaoeistifs d'éléments dfEmmagasinage binaires, chèque ensesttîls ayant un décodeur pour uns adresse de n bits pour représenta? une p^sicion de bit prédéterminée rierts un mot de mémoire, caractérisée en ce qu'aï le comprend la fourniture à chaque décodeur de n**1 bits d'adresse cofamuns définissant dans chaque fcussmble -une cellule de mémoire constitués sur dsyK à'ensnagasinaga binaires et définissant une catégorie de données è chercher dans is 'mémoires et la constitution d'un bit d'adresse supplfesntsire prédéterminé pour chèque position de bit a partir du bit correspondant du sot de recherche at la fourniture de ces bits supplémentaires su* décodeurs avec las bits d'adresse communs. bad original