Brevet FR2653577A1 — publié le 19910426

La présente invention se rapporte aux procédés et aux dispositifs qui permettent de traiter des données pour obtenir rapidement et à moindre coût des caractéristiques en nombre réduit à partir d'un ensemble de données dont la taille peut être considérable. li est fréquemment nécessaire de pouvoir analyser un volume très important de données pour en tirer des informations en nombre réduit pouvant porter sur des points qui n'ont pas été déterminés lors de l'enregistrement de ces données. Ainsi dans les études linguistiques on est souvent amené à analyser des textes disponibles dans la littérature pour déterminer ltoccurrence de certains mots ou de certaines structures verbales. Ce travail présente essentiellement de l'intérêt lorsqu'il s'agit d'analyser par exemple toute ltoeuvre d'un auteur voire toute une période historique. Comme autre exemple, on peut aussi citer les satellites artificiels sur lesquels on enregistre en permanence la totalité des paramètres délivrés par les capteurs, de manière à pouvoir analyser l'évolution de phénomènes se produisant sur des périodes extrêmement longues ou à repérer un évènement unique se produisant de manière aléatoire à l'intérieur d'une période de temps très grande. On conçoit que dans ces deux cas le volume des données à traiter est particulièrement considérable. On sait procéder à une telle analyse en utilisant un ordinateur de type courant convenablement programme. Toutefois cette analyse consiste à prendre chaque donnée et à la traiter par un programme qui se déroule selon un nombre important de cyles machines ce qui, compte tenu du volume des données, conduit à des durées de traitement prohibitives. On sait aussi utiliser des machines dédiées, telles que des automates, qui fonctionnent par simple analyse combinatoire et sont donc nettement plus rapides. Toutefois ces appareils sont compliqués et chers et doivent être restructurés d'une manière compliquée à chaque changement de type d'analyse. La solution consistant à émuler un tel automate sur un ordinateur standard ne présente pas non plus d'intérêt puisque l'on retombe dans le problème de la consommation de cycle machine qui n'est nullement résolu par une telle émulation. Pour résoudre ce problème l'invention propose un procédé selon la revendication 1. D'autres particularités et avantages apparaîtront clairement dans la description suivante présentée à titre d'exemple non limitatif et faite en regard de la figure unique annexée qui représente le schéma de principe simplifié d'un dispositif selon l'invention. Le procédé selon l'invention consiste à traiter en séquence les caractères d'un texte, à l'aide d'un programme d'ordinateur de type automate, dont l'état courant est en fait l'adresse de l'instruction en cours d'exécution. Chaque instruction compare le caractère courant du texte (en fait sa classe) à une valeur fixe, figurant dans le code de l'instruction. Suivant que le caractère courant est inférieur, égal ou supérieur à cette valeur fixe, l'état de l'automate peut être modifié, par saut à une adresse fournie en paramètre de l'instruction. Il suffit d'un petit nombre dtinstructions (inférieur à 10) pour identifier un caractère, avant de passer au caractère suivant. Le dispositif selon l'invention est caractérisé en ce que le programme de type automate réside dans la mémoire principale 41 d'un ordinateur, et que l'exécution de ce programme est assurée par les mécanismes natifs du processeur 40. En particulier, c'est le compteur ordinal du processeur 40 qui maintient l'adresse de l'instruction courante, donc l'état courant de l'automate Ce dispositif permet par exemple de traiter 100 pages de 3000 caractères à la seconde avec un processeur de 3 MIPS (million d'instructions par seconde). Sur la figure la partie correspondant aux éléments connus d'un ordinateur a été simplifiée à 11 extrême en ne représentant que le processeur 40 relié à la mémoire principale 41 par un bus 20 - 24. Selon l'invention ce bus est coupé en deux par l'intermédiaire d'un circuit d'isolation 8 qui permet de relier ou non ces parties 20 et 24 sous la commande d'un signal provenant des autres circuits caractéristiques de l'invention. Un interpréteur externe prend alors le relais entre ces parties 20 et 24. La solution décrite ci-après suppose, pour la commodité de la description, que le code opération et les paramètres d'une instruction circulent en séquence, ce qui est par exemple le cas d'un circuit 20-24 de largeur 8 bits. Le principe général est que l'isolation par le circuit 8 et le code opération de remplacement généré par le circuit 7 ne concernent que les codes opération circulant sur le circuit 20-24, pas les paramètres ni les transferts résultant de 11 exécution des instructions. Un détecteur de code-opération 9 est relié par un circuit 42 au processeur 40 et permet de savoir lorsque un signal circulant sur le bus 20 est un code opération du processeur. ll émet alors un signal indiquant cette détection sur le circuit 25. Ce circuit 25 met en route un analyseur de code 10 relié au bus 20, lequel détermine si le code-opération alors présent sur le bus 20 correspond à une instruction à laquelle il a été attribué la propriété de basculer l'interpréteur externe en condition marche. Lorsqu'il s'agit d'une telle instruction externe, l'analyseur 10 émet un signal sur un circuit 26. Un détecteur d'interruption 11 relié au processeur par un circuit 43 permet d'identifier les périodes pendant lesquelles le processeur exécute un sous-programme déclenché par une interruption. A ce moment ce détecteur émet un signal sur un circuit 27. Un inter#rupteur marche-arrêt 12 contient une bascule qui délivre sur un circuit de sortie 28 un signal de commande de l'interpréteur externe. Cette bascule passe en condition marche sous la commande des signaux provenant des circuits 25 et 26. Elle passe en condition arrêt sous la commande des signaux provenant du circuit 27 ou d'un circuit 29 décrit plus loin. La partie 20 du bus est reliée à un registre 1 qui permet de mémoriser le caractère courant des données traitées. La partie 20 du bus est également reliée à une mémoire 2 qui permet de mémoriser, dans une phase de programmation préalable à l'exploitation des données proprements dites, une table de transcodage déterminée par le processeur 40. Cette mémoire 2 est reliée par un circuit 21 au registre 1. En phase d'exploitation le caractère courant contenu dans le registre 1 est utilisé comme adresse d'une table de transcodage, qui détermine pour chaque caractère deux caractéristiques, un type et une classe, disponibles respectivement sur les circuits de sortie 22 et 23 de cette mémoire 2. Selon l'invention, dans la phase de programmation préalable on a chargé dans la mémoire 41 un ensemble de codes-opération correspondant à des instructions supplémentaires qui viennent enrichir le jeu d'instructions du processeur 40. Chacun de ces codes-opération comprend lui aussi un type et une classe, de même nature que le type et la classe du caractère courant. Lorsque le code opération est lu en mémoire sous la commande du processeur, le type et la classe sont disponibles sur respectivement deux dérivations 31 et 33 du bus 24. Le circuit 22 est connecté à un comparateur 3 qui permet d'indiquer sur un circuit 32 si la classe de l'instruction 30 est inférieure, égale ou supérieure à celle de l'instruction. Une mémoire programmable 6 contient un ou plusieurs jeux d'instructions externes supplémentaires. Dans le cas correspondant à l'exemple décrit il y a plusieurs jeux, et le jeu à utiliser est sélectionné par un sélecteur de type de jeux 5, qui fonctionne à partir d'une commande provenant, soit directement de l'opérateur, par exemple par un jeu de clefs, soit indirectement du processeur 40, lui-même actionné à partir du clavier de commande normal. Cette sélection est appliquée à la mémoire 6 par un circuit 34. La lecture de cette mémoire se fait donc sous la commande de ce circuit 34, du circuit 23 qui donne le type de caractère courant, du circuit 32 qui donne le résultat de la comparaison de la classe du caractère courant et de celle de l'instruction courante, et du circuit 33 qui donne le type de l'instruction courante. Le signal numérique résultat de cette lecture est appliqué aux circuits 35, 29 et 30 qui commandent selon le cas l'une des actions suivantes - Le circuit 35 active un dispositif 4 qui, par un circuit 36, autorise le chargement dans le registre 1 du caractère courant suivant. Dans l'exemple décrit, le caractère suivant provint du bus 20 et était donc contenu dans le processeur 40, par exemple dans une mémoire vive intermédiaire chargée pendant une interruption de l'interpréteur externe. Cette solution est décrite ici pour ne pas alourdir la description mais, dans une version préférée, on chargera directement le caractère courant à partir de la mémoire. 41 en utilisant un circuit d'accès direct à la mémoire connu dans l'art sous le nom de DMA. - Le circuit 29 est connecté à l'interrupteur 12 pour commander l'arrêt de l'interpréteur externe par l'intermédiaire du circuit 28. - Le circuit 30 délivre un code opération réel du processeur correspondant à une instruction externe à exécuter. Cette instruction est reprise par une porte monodirectionnelle 7 qui connecte le circuit 30 au bus 20. Le circuit 28 provenant de l'interrupteur 12 autorise donc le fonctionnement du dispositif 4 et de la porte 7. Il commande également le fonctionnement du circuit d'isolation de bus 8 qui isole la mémoire 41 du processeur 40 quand l'interpréteur externe est en fonctionnement.On constate donc que, même si certains organes tels que les dispositifs 2, 3 et 6 sont purement combinatoires et fonctionnent en permanence, par contre les informations provenant de ces dispositifs sur les circuits 29, 30 et 35 ne sont pris en compte que lorsque l'interpréteur externe est actif, sous la commande du circuit 28, et qu'une instruction du jeu d'instructions supplémentaire est présente sur le bus 24. Le traitement d'un ensemble de données ##effectue en deux étapes principales, une étape de préparation et une étape d'exécution . Dans étape de préparation on commence d'abord par déterminer le contenu de la table de transcodage. Ce contenu peut être fixe, dépendre de la nature du texte, ou de la nature ou du contenu de l'analyse à effectuer. On traduit ensuite l'analyse à effectuer en un programme composé d'instructions du jeu d'instructions supplémentaires de l'interpréteur externe. Ce programme peut appeler des sous-programmes écrits avec les instructions du jeu d'instructions réelles. ll suffit pour cela que l'instruction supplémentaire d'appel d'un tel sous-programme, contenue dans le circuit .6, provoque l'arrêt de l'interpréteur externe et que l'instruction réelle de sortie du sous-programme soit reconnue par le circuit 10 pour provoquer la remise en route de l'interpréteur externe. Enfin l'étape de préparation se termine par le chargement dans le circuit 2 de la table de transcodage. Cette table a été déterminée dans la phase précédente et est alors contenue dans le processeur sous forme d'une suite de caractère correspondant aux codes 0, 1, 2 etc. des instructions 0, 1, 2 etc. Le processeur, par l'intermédiaire d'un circuit de contrôle 44, actionne le circuit 4 qui fait charger dans le registre 1 le caractère de code 0 présent sur le bus 20. La classe et le type de ce caractère sont ensuite chargés dans la table 2 et ce processus se recommence jusqu'à ce que tous les caractères soient chargés dans la mémoire 2. Cette étape de préparation est, dans le cas général, programmée à partir des instructions réelles du processeur, l'interrupteur 12 maintenant l'interpréteur externe hors de fonctionnement. Dans certains cas particuliers par contre il peut être utile d'utiliser des programmes d'analyse existant déjà dans la mémoire morte 6. Pendant l'étape d'exécution le signal présent sur le circuit 28 provoque l'isolation par le circuit d'isolation 8 des parties 20 et 24 du bus reliant le processeur 40 à la mémoire 41. Ce signal commande également le remplacement du code opération d'une instruction supplémentaire par le code d'une instruction réelle provenant de la mémoire morte 6. Lorsqu'un sous-programme d'interruption, composé d'instructions réelles, est activé, ou lorsque la donnée présente sur le bus 20 n'est pas un code opération, l'interrupteur 12 passe en position arrêt et le circuit 28 ouvre le circuit d'isolation 8 en permettant la circulation des données entre la mémoire 41 et le processeur 40 et interrompt le fonctionnement de l'interpréteur externe. A titre d'exemple, on va décrire une analyse simple dans laquelle on désire compter le nombre d'occurrences de la lettre "E" dans un texte contenu en mémoire. Le processeur 40 utilisé dans cet exemple comprend dans son jeu d'instructions réelles les instructions définies dans le tableau suivant ode Argument Description RESTART - Saut à l'adresse fixe ADRRST SAUT adresse Saut à l'adresse indiquée NOP adresse Instruction ineffective à 1 argument APPEL adresse Saut à l'adresse indiquée avec mémorisation de l'adresse de l'ins truction qui suit le "APPEL" RETOUR - Saut à l'adresse mémorisée par : "APPEL" Le circuit d'analyse 10 détecte l'instruction RETOUR comme un ordre d'activation de l'interpréteur externe. La mémoire morte 6 contient les instructions listées sur le tableau suivant rype car. Résultat Type ins. Passer au Inactivation Instruction courant compar. courante caractère interpréteur réelle classes suivant externe générée O indif. indif. NON OUI RESTART autre non ég. 0 OUI NON SAUT adresse outre égales 0 NON NON NOP adresse autre indif. 1 NON OUI APPEL adresse Dans ces instructions contenues dans la mémoire 6, pour tous caractères de type 0, l'instruction réelle générée, indépendante de l'instruction supplémentaire, est "RESTART" et les signaux complémentaires arrêtent l'interpréteur externe. Pour les autres types de caractères, l'instruction réelle générée dépend de l'instruction supplémentaire. L'instruction supplémentaire de type 0 est suivie d'une adresse de saut. Si la classe du caractère courant est différente de la classe de l'instruction, l'instruction réelle est "SAUT adresse" avec indication de passer au caractère suivant. Sinon l'instruction réelle est "NOP adresse". L'instruction supplémentaire de type 1 est suivie d'une adresse de saut. Elle génère l'instruction réelle "APPEL adresse" et arrête l'interpréteur externe. La table de transcodage contenue dans la mémoire 2 est décrite dans le tableau suivant Caractère Type Classe caractère de fin de texte 0 0 "E" 1 0 autres 1 1 Le programme d'analyse est compris dans le tableau suivant ADR. programme Instructi#n Argument Commentaires ... instructions réel2es APPEL ACTIV pour activer l'interpr. DEBUT : Type 0, classe 0 DEBUT attendre lettre "E" Type 1, classe 0 COMPT exécuter le comptage Type 0, classe 1 DEBUT "consommer" le "E" COMPT: Sous-programme de comptage instructions réelles ACTIV: RETOUR active l'interpréteur ADRRST: Fin d'analyse du Interpréteur desactivé Instructions réelles Une fois la table de transcodage chargée dans le circuit 2, le premier caractère du texte est chargé dans le circuit 1 et l'interpréteur externe est activé par appel à une instruction réelle "RETOUR". L'instruction "Type 0, classe 0" à l'adresse programme DEBUT est exécutée répétitivement jusqu'à l'apparition d'un "E" dans le texte. Le registre 12 est actif en permanence, le circuit 28 est actif pour la lecture du code, inactif pour la lecture de l'adresse. L'interpréteur, compte tenu du type de cette instruction, du type et de la classe des caractères successifs du texte, remplace le code de l'instruction par l'instruction réelle "SAUT" ; donc le processeur exécute en réalité plusieurs fois l'instruction DEBUT:SAUT DEBUT A chaque ttEtt du texte, la classe du caractère courant devint 0, et l'interpréteur génère non plus l'instruction "SAUT", mais l'instruction "NOP1,. L'interpréteur reste actif, le contenu du circuit 1 (lettre "E") ) reste inchangé. L'instruction suivante est remplacée par l'interpréteur par le code "APPEL", et l'interpréteur est désactivé. Le processeur exécute le sous-programme de comptage, écrit en instructions réelles et se terminant par l'instruction "RETOUR". Celle-ci réactive l'interpréteur. L'instruction de l'adresse mémoire DEBUT+2 est alors exécutée, son code est remplacé par "SAUT", puisqu'on a toujours la lettre "E", de classe 0, dans le circuit 1. ll y a passage au caractère suivant du texte, et la recherche du prochain "E" reprend à l'adresse mémoire DEBUT. A la fin du texte, l'instruction supplémentaire courante est remplacée par l'instruction réelle RESTART. l'interpréteur externe est désactivé et l'exécution reprend, en instructions réelles, à l'adresse mémoire ADRRST. On a bien trouvé à ce moment le nombre d'occurrences de la lettre "E" dans le texte, et d'une manière beaucoup plus rapide que par les méthodes traditionnelles, puisqu'il a suffit en moyenne d'une instruction "SAUT" et d'un chargement en accès direct mémoire du circuit 1 par caractère du texte. REVENDICATIONS 1. Procédé de traitement d'un ensemble de données représentées par un ensemble de caractères, caractérisé en ce que, chaque caractère appartenant à un type et à une classe déterminés parmi un ensemble de types et un ensemble de classes, on analyse le type et la classe de chaque caractère pour effectuer sur celui-ci des traitements, notamment des décomptes . 2. Procédé selon la revendication 1, caractérisé en ce que le déroulement du programme d'analyse est déterminé par les combinaisons classe/type de l'ensemble de caractères. 3. Procédé selon l'une quelconque des revendications 1 et 2, caractérisé en ce que, chaque instruction d'analyse comportant une classe de même nature que les classes des caractères de données, on compare cette classe avec celle du caractère courant analysé et on détermine le déroulement du programme d'analyse selon le résultat (inférieur, égal ou supérieur) de cette comparaison. 4. Dispositif de traitement de données pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 3, du type comprenant un processeur (40) relié à une mémoire principale (41) par un bus (20-24), caractérisé en ce qu'il comprend un interpréteur externe (1-12) comportant des moyens (8) placés sur le bus pour isoler la mémoire du processeur et des moyens (1-7) pour adresser au processeur des codes-opération réels particuliers correspondant à des instructions supplémentaires, exploitées par cet interpréteur externe, lorsque celui-ci reconnaît certaines instructions en provenance de la mémoire principale. 5. Dispositif selon la revendication 4, caractérisé en ce qu'il comprend des moyens (9, 10) pour reconnaître sur le bus (20) certains codes-d'instruction réels et des moyens (12) pour mettre en route pour arrêter l'interpréteur externe et déclencher l'isolement entre la mémoire principale et le processeur. 6. Dispositif selon la revendication 5, caractérisé en ce qu'il comprend en outre des moyens (11) pour déterminer les phases d'interruption du processeur (40) et faire basculer dans le mode arrêt les moyens de mise en route de l'interpréteur externe. 7. Dispositif selon l'une quelconque des revendications 4 à 6, caractérisé en ce que l'interpréteur externe comprend un registre (1) permettant de recevoir le caractère courant lu dans la mémoire principale, des moyens (2) pour déterminer le type et la classe du caractère courant contenus dans ce registre, des moyens (3) pour comparer la classe du caractère courant ainsi déterminé avec la classe de l'instruction courante provenant de la mémoire principale (41) et une mémoire morte (6) comprenant au moins un jeu d'instructions supplémentaires, cette mémoire morte délivrant, à partir du type du caractère courant, du type de l'opération courante provenant de la mémoire principale et du résultat de la comparaison entre les classes du caractère courant et de l'instruction courante, un signal permettant de charger le caractère courant dans le registre d'entrée (1), un signal permettant le cas échéant de basculer dans le mode arrêt et un code-opération réel du processeur (40) qui est envoyé sur la partie du bus (20) qui reste reliée au processeur. 8. Dispositif selon la revendication 7, caractérisé en ce que la mémoire morte (6) permet de transcoder en codeopération réel utilisable par le processeur (40) des instructions supplémentaires au jeu d'instructions de ce processeur inscrites dans la mémoire principale (41) et qui permettent d'enrichir le jeu d'instruction disponible et d'obtenir un programme analyse des données plus efficaces. 9. Dispositif selon l'une quelconque des revendications 7 et 8, caractérisé en ce que la mémoire morte (6) permet de mémoriser plusieurs jeux d'instructions supplémentaires, et qu'il comprend des moyens (5) permettant de sélectionner l'un de ces jeux.