Brevet FR2421422A1 — publié le 19791026

~ La présente invention est du domaine du traitement de l'information. Elle est relative à la sélection d'informations dans une base de données selon la technique dite de recherche associative ou de recherche du contenu adressable qui consiste à extraire d'un ensemble d'informations, des parties sélectionnées par leur contenu. Elle s'applique notamment à la gestion d'une mémoire de masse d'ordinateur. Les dispositifs d'adressage connus fonctionnant selon cette technique de recherche associative présentent l'intérêt de ne pas utiliser de dictionnaires d'adresses qui occupent une place importante en mémoire au détriment des informations. Ils ont par.contre l'inconvénient soit de présenter une structure complexe en logique câblée soit de nécessiter l'assistance d'un ordinateur central avec un logiciel élaboré pour commander l'enchaînement des comparaisons requises par cette technique, ce qui réduit notablement leur domaine d'application. La présente invention a pour but des processeurs à recherche associative qui ne nécessitent pas l'assistance d'un calculateur et qui présentent une structure suffisamment simple, compacte et économique pour pouvoir être utilisés à plusieurs, pour l'adressage, å l'intérieur de sous ensembles d'une mémoire de très grande capacité Elle a pour objet un processeur à recherche associative pour extraire au moins une inscription d'un domaine de recherche formé d'un ensemble d'inscriptions chacune constituée par un groupe d'mformations, ladite extraction s'effectuant par comparaison du contenu du domaine de recherche avec au moins une information définissant une clé de recherche.Ce processeur comporte - une mémoire de clé de recherche, - un comparateur recevant sur une première entrée les informations contenues dans le domaine de recherche et lues successivement, et sur une deuxième entrée les informations contenues dans la mémoire clé de recherche et lues de manière répétitive, à la même vitesse que celles contenues dans le domaine de recherche, - une mémoire tampon recevant les informations appliquées à la première entrée du comparateur et délivrant, à ia sortie du processeur et sur ordre, la ou les inscriptions sélectionnées - et un automate séquentiel comportant au moins un circuit de logique combinatoire programmable (Field Programmable Logic Array) associé à un registre d'états, régissant l'enchaînement des #comparaisons requises par la technique de recherche associative par l'intermédiaire de l'adressage de la mémoire de clé de recherche, en fonction du rythme d'application des informations sur la première entrée du comparateur, et validant l'écriture de la mémoire tampon pour la ou les inscriptions sélectionnées. Selon un mode préféré de réalisation chaque inscription est formée par un groupe dtinformations indexées L'automate séquentiel comporte un premier circuit de logique combinatoire programmable assurant le décodage des index accompagnant les informations contenues dans une inscription du domaine de recherche ou dans la clé de recherche et appliquées sur les entrées du comparateur, et un deuxième circuit de logique combinatoire programmable associé à un registre d'états cadencé par le rythme d'application des informations à la première entrée du comparateur, ledit deuxième circuit de logique combinatoire programmable recevant des informations provenant du comparateur, du premier circuit de logique combinatoire programmable et du registre d'état, et assurant la gestion de l'adressage de la mémoire de clé de recherche, la commande du registre d'états à l'exception du cadencement de ce dernier et la validation d'écriture de la mémoire tampon. D'autres caractéristiques et avantages de l'invention ressortiront de la description ci-après d'un mode-de réalisation donné à titre d'exemple. Cette description sera faite en regard du dessin dans lequel la figure 1 est un schéma d'un processeur à recherche associative selon l'invention et la figure 2 un réseau de Pétri définissant le processus de fonctionnement de l'automate séquentiel utilisé dans le processeur à recherche associative représenté à la figure 1. On a représenté sur la figure 1 un processeur à recherche associative i interconnecté entre une source de données 2 et un ordinateur 3. La source de données 2 est une mémoire de très grande capacité, par exemple à disques magnétiques. Pour des raisons de simplicité et d'économie d'emplacements de mémoire, elle est partagée en domaines de recherche qui se décomposent en groupes d'informations ou inscriptions, non ordonnés entre eux, chaque inscription étant formée de mots décomposables en lettres et de repères ou index précisant le début DC et la fin FC d'une inscription, la séparation entre les mots LJ , l'indétermination d'une lettre * et la nature des mots.Le repère r précisant l'indétermination. d'une lettre est appelé dans la suite 'joker et ceux précisant la nature des mots dans une inscription : drapeaux On peut admettre par exemple que la source de données 2 est un fichier renfermant un annuaire téléphonique. Un domaine de recherche est alors constitué par une partie de cet annuaire et chacune de ses inscriptions regroupe les informations relatives à un abonné avec en outre des drapeaux précisant la nature (nom, adresse, profession, numéro de téléphone...) des informations, des index DC,FC repérant le début et la fin de l'inscription, des index de vide ou d'espace LJ repérant la séparation entre les mots et éventuellement des jokers remplaçant certaines lettres des mots. L'ordinateur 3 adresse la source de données 2 en deux étapes. Il sélectionne d'abord le domaine de recherche puis une inscription dans le domaine de recherche. Pour la sélection du domaine de recherche il procède directement par la liaison 4 par exemple par une technique d'indexation. Pour la sélection à l'intérieur du domaine de recherche, il procèdeP intermédiaire du proces- seur à recherche associative 3.Pour cela, après avoir sélectionné le domaine de recherche, il inscrit dans le processeur à recherche associative 3 une clé de recherche, c'est-à-dire une partie des informations contenues dans la ou les inscriptions recherchées, il commande la source de données ? pour qu'elle fournisse au processeur à recherche associative 1, sous forme série, 1' ensemble des données contenues dans le domaine de recherche sélectionné et il extrait du processeur à recherche associative 1 la ou les inscriptions sélectionnées pour les exploiter. Les structures de la source de données 2 et de l'ordinateur 3 permettant d'effectuer ces opérations ne seront pas détaillées car elles ne font pas partie de l'invention et sont du domaine de la technique courante des ordinateurs. Le processeur à recherche associative 1 comporte principalement une mémoire de clé de recherche L'o, un comparateur 50, une mémoire tampon 60 et un automate séquentiel 70. La mémoire de clé de recherche 40 est une mémoire à accès aléatoire (RAM-). L'ordinateur 3 la commande à écriture par la liaison 11 et lui fournit les données à inscrire par l'intermédiaire de l'entrée de données 12. Lorsqu'elle n'est pas en écriture, elle est en lecture. Elle est alors adressée par le générateur d'adresses 41 qui est incrémenté par l'automate séquentiel 70. Sa sortie-lecture de données est connectée par l'intermédiaire d'un bus de données à une entrée du comparateur 50 et à une entrée de l'automate séquentiel 70. Le générateur d'adresses 41 comporte un compteur et un registre de sauvegarde non représentés. Le registre de sauvegarde, permet de conserver certaines valeurs du compteur d'adresses pour des retours en arrière de l'adressage. Le comparateur 50 est un comparateur de nombre binaires à deux entrées. Il a une première entrée connectée à l'entrée de données 13 du processeur 1 qui est reliée à la source de données 2 et une deuxième entrée connectée à la sortie lecture de la mémoire de clé de recherche 40. La mémoire tampon 60 est intercalée entre 1' entrée de données 13 et la sortie de données 14 du processeur 1 c'est-à-dire entre la source de données 2 et l'ordinateur 3. Elle est commandée à l'écriture par l'automate séquentiel 70 par l'intermédiaire de la liaison 61 et à la lecture par l'or- dinateur 3 au moyen de la commande 15. Elle est avantageusement à lecture et écriture simultanées et asynchrones. C'est pourquoi elle est représentée par deux mémoires indépendantes connectées en parallèle, l'une fonctionnant à l'écriture et l'autre en lecture et inversement. L'automate séquentiel 70 comporte un circuit de décodage 71 et un circuit de logique séquentielle constitué par un circuit de logique combinatoire programmable 72 F.P.L.A(Field Programmable Logic Array) associé à un registre d'états 73. Le circuit de décodage 71 est connecté en entrée d'une part à la sortie lecture de données de la mémoire de clé de recherche 40 et d'autre part à l'entrée de données 13 du processeur 1.Le circuit de logique combinatoire 72 est connecté en entrée aux sorties du circuit de décodage 71, à celle du comparateur 50, à celles du registre d'états 73 et à une commande de mise en route 16 provenant de l'ordinateur 3 Il est connecté en sortie aux entrées de prépositionnement des étages du registre d'états 73, au générateur d'adresses lecture 41 de la mémoire de clé de recherche 40, à la mémoire tampon 60 et à l'ordinateur 3 par l'intermédiaire d'une sortie 17 de validation d'écriture du processeur 1. Le registre d'états 73 a en outre une entrée de cadencement connectée par l'intermédiaire d'une liaison 18 à une sortie de la source de données 2 où est disponible le rythme auquel les données sont lues et appliquées sur l'entrée données 13 du processeur à recherche associative 1. Le fonctionnement du processeur à recherche associative t sous le contrôle de L'ordinateur 3 peut se décomposer en deux étapes. Lors d'une première étape de préparation se situant pendant ou après la présélection du domaine de recherche dans la source de données 2, ltordi- nateur 3 met la mémoire de clé de recherche 40 en état d'inscription, la charge avec une clé de recherche et la replace en position de lecture. La recherche associative a lieu au cours d'une deuxième étape pendant laquelle l'ordinateur 3 débloque l'automate séquentiel 70 et commande la lecture du domaine de recherche sélectionné dans la source de données 2. Les données reçues sur l'entrée 13 du processeur 1 sont appliquées au comparateur et inscrites dans l'une des deux mémoires constituant la mémoire tampon 60. La mémoire en inscription a sa capacité limitée, par exemple, à la longueur maximale d'une inscription. Elle fonctionne à la manière d'une pile FIFO (first in first out). En l'absence d'un aboutissement favorable des comparaisons commandées par llautomate séquentiel 70 les données åpparaissant à sa sortie sont perdues.Des l'aboutissement favorable des comparaisons et la parution des index de fin d'inscription FC de l'inscription lue et de la clé de recherche, l'automate programmable échange les états de fonctionnement des deux mémoires constituant la mémoire tampon 60 et envoie un signal de validation d'inscription à l'ordinateur 3 qui explore le contenu de la mémoire en lecture. La figure 2 est un réseau de Pétri qui illustre le processus de fonctionnement de l'automate séquentiel 70, pour la commande du déroulement des comparaisons par lesquelles s'effectue la recherche associative. Ce réseau est un graphe orienté comportant deux types de noeuds : des places PO à P5 qui sont représentées par des ronds et correspondent à des états distincts de l'automate programmable 70, et des transitions qui sont représentées par des traits et correspondent à des changement d'états. Il comporte également des arcs orientés réunissant des noeuds de types différents et un marqueur représenté par un point situé dans la place PO. Le fonctionnement séquentiel de l'automate 70 est représenté sur ce réseau par l'évolution du marquage qui elle-même est fonction du franchissement des transitions. Dans un réseau de Pétri un franchissement d'une transition consiste à enlever un marqueur de chaque place reliée à la transition considérée par un arc orienté y aboutissant et à mettre un marqueur dans chaque place reliée à la transition considérée par un arc orienté en provenant. Il n'est possible que si un marqueur se trouve déjà dans chaque place reliée à la transition considérée par un arc orienté y aboutissant et si la condition logique définissant la transition considérée est vérifiée. Pour de plus amples détails sur les réseaux de Petri on se reportera utilement à l'article intitulé Pétri Nets" écrit par Peterson paru dans la revue Computing Surveys "septembre 1977 - ACM. Le réseau de Pétri de la figure 2 comporte sept places - la place PO dans laquelle se trouve l'automate séquentiel 70 lorsqu'il vient d'être débloqué par l'ordinateur 3 ou lorsqu'il vient d'effectuer un cycle de comparaisons infructueux entre une inscription délivrée par la source de données 2 et la clé de recherche et qu'un index de début d'inscription DC n'est pas encore- apparu à la sortie de la source de données 2. Dans cette place PO il repositionne l'adressage de la mémoire de la clé de recherche 40 au début de la clé de recherche. Cette opération est repérée par Vo 3V inscrit dans la place PO. - la place Pi dans laquelle --se trouve l'automate séquentiel 70 lorsque, à la suite de comparaisons positives il incrémente le compteur d'adresses de la mémoire de clé de recherche 40 au rythme de-lecturede la source de données 2. Une comparaison positiye C résulte soit de l'identité des deux caractères comparés soit du fait que-l'un d'eux est unjoker,Elle est représentée sur le diagramme de la figure 2 par deux#oucles fermées, orientée; tracées en pointillés à partir de la place Pi et répérées l'une par V+ 1 - > V (C), l'autre par V + V (x)} - la place P2 dans laquelle se trouve l'automate séquentiel 70 lorsqu'à la suite d'une comparation négative C il commande le repositionnement de l'adressage de la mémoire de clé de recherche 40 au début du mot en cours de lecture (RGV~d > V) et attend soit la disparition d'un index d'espacement LJ en sortie de la source de données 2 pour basculer dans la place Pi et reprendre les comparaisoris entre le même mot de la clé de recherche et le mot suivant de l'inscription délivrée par la source de-données 2 soit l'apparition d'un index de fin d'inscription FC délivré par la source de données 2 pour basculer dans la place PO et reprendre la comparaison entre le début de la clé de recherche et le début de l'inscription suivante délivrée par la source de données 2, - la place P3 dans laquelle se trouve l'automate séquentiel 70 lorsqu'après lecture d'un drapeau dans la mémoire de clé de recherche L'O, il bloque l'adressage de cette dernière et attend soit l'apparition d'un drapeau identique en sortie de la source de données 2 pour rebasculer dans la place Pi soit celle d'un index de fin d'inscription FC, en sortie de la source de données 2 pour basculer dans la place P01 - la place P5 dans laquelle se trouve l'automate séquentiel 70 lorsqu'après lecture d'un index d'espacement X I dans la mémoire de la clé de recherche 40 il incrémente l'adressage de cette dernière, range la valeur obtenue dans un registre de sauvegarde (V~j,RGV) et bascule soit dans la place Pi si la comparaison est positive soit dans la place P2 si la comparaison est négative, - la place P6 dans laquelle bascule l'automate séquentiel 70 lorsqutétant dans la place Pi il reçoit un index de fin d'écriture FC en provenance de la mémoire de clé de recherche 40. Dans cette place il bloque l'adressage de la mémoire de clé de recherche - et la place P4 dans laquelle bascule l'automate séquentiel 70 lorsqu'étant dans la place P6 il apparaît une comparaison positive C consécutive à la lecture d'un index de fin d'écriture FC à la sortie de la source de données 2. Dans cette place l'automatisme séquentiel 70 envoie un signal de validation d'inscription à l'ordinateur 3, échange les rôles : écriture, lecture des deux parties de la mémoire tampon 60 et, comme dans la place PO, repositionne l'adressage de la mémoire de clé de recherche 40 au début d'une clé de recherche. L'automate séquentiel 70 bascule dans la place Pi dès réception d'un index de début d'inscription DC délivré par la source de données2. Soit par exemple une clé de recherche de la forme BANQ PAYS et une information extraite de la source de données 2 de la forme DC BANQUE ~~ DE ~~ PARIS ~~ ET ~~ DES ~~ PAYS ~~ BAS FC En supposant que l'automate séquentiel 70 est au départ à la place PO, celui-ci bascule vers la place Pi à l'apparition de l'index de début d'inscriptions DC provenant de la source de données 2 et incrémente (V + 1-:> V) l'adresse de la mémoire de clé de recherche 40 afin de permettre la comparaison entre le-premier caractère de la source de données 2 (caractère B) avec le premier caractère lu dans la mémoire de clé dé recherche 40 (caractère B). La comparaison est positive, l'automate séquentiel 70 reste dans la place Pi et incrémente (V + 1 A l'apparition de l'index d'espacement LI à la sortie de la mémoire de clé de recherche 40 l'automate séquentiel 70 évolue vers la place P5. Il incrémente le compteur d'adresses de la mémoire de clé de recherche 40 et range son contenu dans un registre de sauvegarde (V#RGv). Cela provoque la comparaison entre le caractère P du mot PAYS lu dans la mémoire de clé avec le caractère D du mot DE délivré par la source de données 2. Cette comparaison qui est négative oriente l'automate séquentiel 70 vers la place P2. Une fois dans la place P2 l'automate séquentiel 70 charge le compteur d'adresses de la mémoire de clé rde recherche 40 avec la valeur mémorisée dans le registre de sauvegarde (RGV- > V) et n'incrémente plus ce compteur jusqu'à l'apparition, à la sortie de la source de données 2, de l'index d'espacement ~~ entre les mots DE et PARIS. Cet index fait basculer l'automate séquentiel 70 vers la place P1. Le caractère P de PAYS extrait de la mémoire de clé de recherche est comparé avec le caractère P de Paris. La comparaison est positive et maintient l'automate séquentiel dans la place Pi qui commande les deux comparaisons suivantes (A de PAYS avec A de PARIS ; Y de PAYS avec R de PARIS). La dernière comparaison est négative et fait repasser automate séquentiel 70 dans la place P2. Dans cette place P2, l'automate séquentiel 70 charge à nouveau le compteur d'adresses de la mémoire de clé de recherche 40 avec la valeur mémorisée dans le registre de sauvegarde (RGV + V) de sorte que le caractère P de PAYS est à nouveau pointé dans la mémoire de clé de recherche 40. L'automate séquentiel 70 reste dans cette place P2 jusqu'à l'apparition et la disparition de l'index d'espacement LJ entre les mots PARIS et ET puis revient dans la place P1. Le résultat négatif de la comparaison entre le P de PAYS et le E de ET fait repasser l'automate séquentiel dans la place P2. La place Pi est à nouveau rejointe pour la comparaison du P du mot PAYS de la clé de recherche avec le D du mot DES fourni par la source de données 2 et à nouveau quittée pour la place P2. L'automate séquentiel 70 rejoint la place Pi pour la comparaison de la lettre P de PAYS de la clé de recherche avec la lettre P de PAYS de l'inscription provenant de la source de données 2. Il reste à cette place Fi pendant les comparaisons des caractères suivants de ces mots qui sont identiques. A l'apparition de l'index de fin d'inscription FC à la sortie de la mémoire de clé de recherche 40, l'automate séquentiel 70 bascule de la placez Pi à la place P6 qu'il quitte pour la place P4 à la première comparaison positive c'est-à-dire à l'apparition, en sortie de la source de données 2, de l'index de fin d'inscription FC suivant le mot BAS. Dans la place FL', il envoie un ordre de validation dtinscription à l'ordinateur 3. Il échange les rôles lecture écriture des deux parties de la mémoire tampon 60 et il repositionne l'adressage de la mémoire de clé de recherche 40 au début de la clé de recherche. Si l'index de fin d'inscription FC apparaît en sortie de la source de données alors que l'automate séquentiel 70 est dans la place Pi ou P5 il donne lieu par une comparaison négative au basculement de l'automate séquentiel 70 vers la place P2 puis vers la place PO. Si ce meme index apçaralt alors que automate séquentiel 70 est dans la place F3 il bascule directement dans la place PO. Dans tous les cas le processus de comparaison est arreté pour être repris avec l'inscription suivante délivrée par la source de données 2. Le décodage d'un drapeau à la sortie de la mémoire de clé de recherche provoque I'arrêt de la comparaison par évolution de l'automate séquentiel 70 vers la place P3. Le retour à la place Pi s'effectue sur le décodage d'un drapeau identique à la sortie de la source de données 2. Le décodage d'un joker donne lieu à une comparaison positive. L'utilisation de circuits de type FPLA (Field Programmable Logic Array) aussi bien pour la partie décodage des index et drapeaux que pour la partie séquencement de l'automate permet de concevoir une logique entièrement structurée et programmable apportant les avantages suivants - souplesse et facilité dtutilisation. On sait implementer facilement un réseau de Petri dans des circuits FPLA, -compacité, consommation réduite, - haute fiabilité due au fait que les FPLA autorisent des compressions logiques à l'inverse des circuits PROM. La grande simplicité de la structure du processeur qui vient d'être décrit rend possible l'emploi de plusieurs exemplaires en parallèle par exemple avec une source de données formée d'une unité de mémoire à disques magnétiques comportant plusieurs têtes de lecture actives. Bien évidemment on peut, sans sortir du cadre de l'invention, modifier certaines dispositions ou remplacer certains moyens par des moyens équivalents. REVENDICATIONS 1/ Processeur à recherche associative pour extraire au moins une inscription d'un domaine de recherche formé d'un ensemble d'inscriptions non ordonnées entre elles et constituées chacune par un groupe d'informations, par comparaison du contenu du domaine de recherche avec au moins une information définissant une clé de recherche, ledit processeur étant caractérisé en ce qu'il comporte - une mémoire de clé de recherche (40), - un comparateur(50) recevant sur une première entrée les informations contenues dans le domaine de recherche et lues successivement, et sur une deuxième entrée les informations contenues dans la mémoire de clé de recherche (40) et lues de manière répétitive à la même vitesse que celles contenues dans le domaine de recherche, - une mémoire tampon (60) recevant les informations appliquées à la première entrée du comparateur (50) et délivrant, à la sortie du processeur et sur ordre, la ou les inscriptions sélectionnées - et un automate séquentiel (70) comportant au moins un circuit de logique combinatoire programmable F.P.L.A. (Field Programmable Logic Array) associé à un registre d'états régissant l'enchainement des comparaisons requises par la technique de recherche associative par ltintermédiaire de l'adressage de la mémoire de clé de recherche (40) en fonction du rythme d'application des informations sur la première entrée du comparateur et validant 1' écriture de la mémoire tampon (60) pour la ou les inscriptions sélectionnées. 2/ Processeur à recherche associative selon la revendication 1 pour extraire au moins une inscription d'un domaine de recherche formé d'un ensemble d'inscriptions non ordonnées entre elles et constituées chacune par un groupe d'informations indexées, par comparaison du domaine de recherche avec au moins une information définissant une clé de recherche, ledit processeur étant caractérisé en ce que l'automate séquentiel (70) comporte un premier circuit de logique combinatoire programmable FP L A. (71) assurant le décodage des index accompagnant les informations contenues dans une inscription du domaine de recherche ou dans la clé de recherche et appliquées aux entrées du comparateur (50), et un deuxième circuit de logique combinatoire programmable F.P.L.A. (72) associé à un registre d'états (73) cadencé par le rythme d'application des informations à la première entrée du comparateur (50), ledit deuxième cireuit de logique combinatoire programmable (72) recevant les informations provenant du premier (72), du comparateur (50) et du registre d'états (73) et assurant la gestion de la mémoire de clé de recherche (40), du registre d'états (73) du cadencement et de la validation d'écriture de la mémoire tampon (60).