Brevet FR2320601A1 — publié le 19770304

La présente invention est relative au traitement de données. Il arrive fréquemment que des éléments d'information soient organisés en catégories ou classes. On peut avoir besoin de déterminer dans toute liste de données divisées successivement en catégories ou classes, la catégorie ou la classe d'un élément Lorsque des instructions et/ou des données ont des priorités différentes, et/ou des classifications relatives à la sécurité, différentes, des situations semblables peuvent apparaître.Ce type de besoin peut encore se rencontrer dans des processus de données conçus pour fonctionner directement à l'aide d'un langage évolué tel que l'ALGOL, où entrent en jeu des scus-programmes imbriqués dont chacun est susceptible d'établir la mise en mémoire de catégories de données, et qui, dans le but de réaliser une organisation efficace de la mémoire seraient réécrits et/ou replacés en séquence à la fin de chaque sous-programme, d'autres sous-programmes nécessitant une mise en mémoire. De préférence, les catégories de données relatives à chaque sous-programme apparaissent séquentiellement et avec des scus-programmes "actifs" apparaissant dans la séquence dans laquelle ils ont été mis en oeuvre. Suivant la présente invention, le dispositif de traitement de données comporte une mémoire pouvant emmagasiner un ensemble de mots de plusieurs bits, chacun de ces '#mots-frontière" représentant un caractère de différentiation d'une catégorie ou d'une classe d'éléments d'information faisant partie d'une liste de tels éléments organisés en catégories ou en classes, des moyens destinés à introduire lesdits mots de plusieurs bits dans la mémoire, dans un ordre relié à leur succession dans ladite liste mais dans un autre ordre d'adressage de la mémoire prédéterminé, et des moyens destinés à lire le contenu des adresses de la mémoire dans un ordre déterminé par des moyens permettant de comparer successivement un élément d'information à identifier aux mots à plusieurs bits lus dans la mémoire, les moyens de comparaison étant conçus pour disposer les chiffres successifs des adresses de mémoire chacun suivant le résultat de la comparaison qui précède immédiatement. Les moyens de lecture peuvent comprendre un registre à décalage destiné à assurer l'adressage de la mémoire en utilisant un réglage initial de la première adresse de la mémoire et en utilisant des décalages avec les entrées des chiffres suivants sous la dépendance des moyens de comparaison. Des modes de réalisation de l'invention peuvent ainsi identifier la catégorie d'un élément d'information en un nombre de cycles de fonctionnements égal au nombre des chiffres contenus dans l'adresse de la mémoire. Si un "1" binaire, placé dans la position du-chiffre le moins significatif, correspond au réglage initial du registre à décalage, le contenu de ce registre à la fin du cycle d'identification de la dernière catégorie est une adresse de mémoire unique avec en plus un "l"binaire dans la position voisine correspondant au chiffre plus significatif, en supposant que le registre à décalage comporte un tel étage supplémentaire. Un tel registre serait capable de faire l'adressage d'une mémoire dont la capacité serait double de la capacité nécessaire pour ne contenir que les mots-frontière de catégories.Si on utilise la moitié d'une telle mémoire pour emmagasiner les mots-frontière de catégories, on peut utiliserl'autre moitié pour emmagasiner d'autres informations relatives aux catégories, à des adresses existant dans le registre à décalage, à la fin de l'identification des catégories respectives. Les moyens de comparaison peuvent être formés d'un soustracteur fournissant une indication qualitative, par exemple négatif/non- négatif, relative à la position du chiffre, et une indication quantitative, c'est à dire un nombre binaire, du rang de l'élément individuel relatif à un mot-frontière de catégories. Au moment où le mot-frontière de catégories pertinent est trouvé, la sortie du soustracteur peut être de préférence dirigée sur un registre de façon à donner le rang de l'élément dans sa propre catégorie. La première comparaison identifie la moitié de la mémoire relative aux frontières de catégories dans laquelle se trouve la catégorie de l'élément, et des comparaisons successives identifient des quarts, des huitièmes etc, jusqu'à définition complète de la catégorie. Ce procédé est très efficace lorsque le nombre des ca tégories correspond à une puissance de deux. Dans le cas contraire, le comparateur est forcé de donner un résultat, quel que soit le contenu réel existant à l'adresse, qui peut en fait être utilisée dans d'autres buts, par exemple comme registre temporaire. Ceci peut être réalisé simplement à l'aide d'une bit de marquage supplémentaire pour chacune des positions de mémorisation. Un mode de réalisation de l'invention va être maintenant décrit, à titre d'exemple, avec référence aux dessins joints dans lesquels : la figure 1 donne un schéma synoptique montrant la mémoire des mots-frontière d'une catégorie et les commandes associées ; et la figure 2 donne une liste de catégories d'éléments d'information et corrèle les mots-frontière de catégories avec les adresses de la mémoire. Dans la figure 1, une mémoire 10 est utilisée pour emmagasiner un ensemble de mots de plusieurs bits, chacun représentant un caractère de différentiation entre des catégories ou classes d'éléments d'information d'une liste de tels éléments dont la forme générale est indiquée sur la figure 2. La figure 2 représente une liste d'éléments d'information correspondant à des mots de plusieurs bits, c'est à dire des chiffres binaires, allant de 0 à x. Ces mots peuvent constituer une information directe ou, peut-être plus vraisemblablement, constituer les adresses de positions consécutives dans la mémoire principale d'un système en traitement de données dont le dispositif étudié forme un sous-ensemble.Il n'est pas strictement nécessaire que les positions de la mémoire principale soient placées consécutivement pour autant que toute interruption de séquence concerne des données dont l'accès est interdit chaque fois que peut être utilisée l'information mise sous forme de listes ; de sorte que tout mot qui lui correspond peut être détecté comme non-valide et qu'il n'est pas, par conséquent, présenté au dispositif de la figure 1 pour être classé dans l'une des catégories. La figure 2 montre une répartition des nombres 0 à x en catégories numérotées de 0 à 7 par des frontières BO à B6, chacune d'elles représentant le premier ou le dernier nombre du segment correspondant. Les segments 0 à 7 correspondent à des catégories ou à des classes d'éléments d'information représentées par les nombres allant de O à x. On doit noter que les mots-frontière 30 à B6 sont également associés aux désignations SL I à SL 7 mais dans un ordre différent. Ces désignations SL 1 à SL 7 se rapportent à des adresses de positions dans la mémoire 10 et la relation entre la séquence des mots-frontière et 1'ordre dans lequel elles sont emmagasinées dans la mémoire 10 doit être vue comme liée à la manière dont un élément d'information d'entrée Y des lignes 11 de la figure 1 est traitée pour en déterminer la catégorie. La figure présente l'adressage de la mémoire 10 sur les lignes 12 comme se faisant à partir des étages d'un registre à décalage 13 comportant une entrée sur son chiffre le moins significatif et un ensemble d'entrées 14 sur tous ses étages en parallèle. Les entrées en parallèle sont utilisées pour charger la mémoire 10 avec les mots-frontière BO à B6. Pour obtenir-ce résultat, il existe une mémoire morte (ROM) 15, par exemple une matrice de diodes organisées en mots dont l'adressage se fait sur des lignes 16 grâce à un circuit de séquence 17 actionné par des signaux d'horloge, dont le rôle est de lire séquentiellement le contenu des positions des mots de la mémoire ROM 15.Cet adressage séquentiel se fait en simultanéité avec la présentation séquentielle sur les lignes 18 des mots B0 à B6 devant être introduits dans la mémoire 10 pendant une phase d'écriture. La mémoire ROM 15 joue le rle d'un traducteur d'adresses, et puisque ses entrées 16 sont excitées séquentiellement fournit sur les lignes 14 les adresses de la mémoire 10 qui corrèlent B0 à B6 et SL 1 à SL 7 comme le montre la figure 2. A la fin de ce cyle d'écriture en mémoire, les positions de mémorisation SL 1 à SL 7 contiennent les mots-frontière B3, Bi, B5, BO, B2, B4, et B6 respectivement. La sortie de la mémoire 10, lorsque se fait l'adressage d'une position pendant un cycle de lecture, est appliquée, à travers les lignes 19 , les portes ET 20 si elles sont excitées par 21, et les lignes 22, à un soustracteur 23 qui sert à comparer la sortie de la mémoire à un nombre binaire représentant un élément d'information appliqué sur les lignes 11. Le soustracteur 23 est représenté comme comportant un ensemble de lignes de sortie 24 qui fournissent la différence numérique entre les entrées 22 et 11, et comme comportant en outre une sortie 25 qui donne une valeur binaire indiquant si les entrées 11 sont inférieures ou non aux sorties 22, c'est à dire si Y est plus grand que le contenu des positions de la mémoire sur lesquelles se font l'adressage , ou s'il est égal à ce contenu.On suppose ici, que pour le contenu de la mémoire Y, la ligne 25 est excitée de façon à représenter un "1" binaire et qu'elle représente un "0"binaire dans le cas contraire. La figure montre la ligne 25 comme connectée sous forme d'entrée à l'étage le moins significatif du registre à décalage 13 et à travers un branchement 26 à un registre 27 connecté de façon à recevoir les signaux de sortie numériques 24 du soustracteur et à emmagasiner ces signaux sous l'action d'une impulsion appliquée sur la ligne 26 Le registre 27 sert à fournir le rang d'un élément individuel d'information Y dans sa catégorie ou classe. La ligne 21, destinée à commander l'excitation des portes ET 20 de façon à leur permettre d'alimenter les lignes d'entrée 22 du soustracteur, est munie d'un branchement 30 suivi d'un inverseur 31 sur la ligne 21. Le branchement 30 commande l'excitation d'un autre ensemble de portes ET 32 connectées de façon à recevoir un état binaire formé entièrement de zéros sur les lignes 33 et å le transmettre aux lignes d'entrée 22 du soustracteur lorsqu'il est excité Cette disposition convient particulièrement lorsque l'unité arithmétique et logique d'un processeur de données comporte normalement un code zéro sur toute la longueur du mot, auquel cas le soustracteur 23 peut faire partie de cette unité. En fonctionnement, une opération d'identification de catégorie relative à un élément d'information Y sur les lignes 11 est mise en route par une impulsion I appliquée sur la ligne 21. Cette impul sion rend inactives les portes ET 20 à travers l1inverseur 31, ce qui empêche d'appliquer le signal de sortie de mémoire aux entrées 22 du soustracteur, et ouvre les portes ET 32, ce qui applique tous les zéros aux entrées 22 du soustracteur.La valeur apparaissant sur les lignes 11, quelle qu'elle soit, est plus grande que celle, formée uniquement de zéros, appliquée aux lignes 22 ; les lignes 25 sont donc excitées par une impulsion de manière à représenter un "1" binaire,prêt par conséquent à être introduit dans l'étage le moins significatif du registre à décalage Ceci se produit lorsque le registre à décalage reçoit le signal d'horloge suivant, et il peut être nécessaire de garder cet état en mémoire dans un circuit bistable disposé sur la ligne 25. L'état "1" binaire appliqué à la ligne 25 permet également d'introduire l'élément Y de la sortie 24 du soustracteur dans le registre de rang 27. Au lieu d'utiliser les portes 22 et 32 et une impulsion I de mise en route, on peut utiliser un registre à décalage pourvu normalement d'une remise à zéro, grâce à quoi, tous les étages se trouvent dans un état binaire "0", ce qui provoque l'adressage de la positionS1 o de la mémoire 10, position où peut être emmagasiné un état formé entièrernenc de zéros. De cette façon, le soustracteur 23 reçoit l'élément Y et l'ensemble des zéros, et transmet un "1" binaire sur la ligne 25 et l'élément Y au registre du rang 27, comme précédemment. Lorsque l'étage du chiffre le moins significatif du registre à décalage contient un simple "1" binaire, l'adressage se fait sur la position SL 1 de la mémoire et le motfrontière B3 est fourni aux lignes d'entrées 22 du soustracteur. L'état de la ligne 25 correspond un "1" ou a un "0" binaire suivant que l'élément Y est plus grand que le mot-frontière B3 ou lui est égal, et l'état correspondant est transmis dans le registre à décalage au signal d'horloqe suivant, ce qui provoque l'adresse sage sur les positions de mémoire SL 3 ou SL 2. Ce n'est que lorsque la ligne 25 transporte un binaire que le contenu du registre de rang est réécrit par la sortie du soustracteur. Par suite dans le cycle suivant, l'élément Y est comparé au mot-frontière B1 ou B5 suivant le contenu du registre à décalage 13.Pour le mot-frontière B1, l'état binaire "1" ou "0" de la ligne 25 qui en résulte provoque la remise à jour du contenu de registre à décalage pour le cycle suivant de manière a faire l'adressage de la position de mémoire SL 5 ou SL 4 avec réécriture du contenu du registre de rang dans le cas seulement où un 1 binaire se trouve sur la ligne 25. Le cycle suivant est relatif ensuite au mot-frontière BO ou B2. Pour le mot-frontière B5 le registre à décalage fait ensuite l'adressage sur les positions SL 6 et SL 7 avec remise à jour du registre de rang 27, comme dans le cas précédent. Pour huit catégories ou classes, la description précédente termine le processus d'identification de la catégorie. Clairement, il faut davantage de cycles pour un nombre plus grand de catégories, chaque cycle supplémentaire permettant de considérer deux fois plus de catégories. En général l'identification d'une catégorie demande autant de cycles qu'il y a de chiffres dans le nombre binaire corresponant au nombre total de catégories. Si le registre de rang 27 doit toujours représenter la position de l'élément Y dans sa catégorie même lorsque cette catégorie est 0, il peut falloir encore un autre cycle comme ila été décrit précédemment pour l'introduction initiale de l'élément Y dans le registre 27. Si le nombre total de catégories n'est pas une puissance de deux, le registre à décalage 13 doit pouvoir faire l'adressage sur la puissance de deux supérieure, mais les positions de mémoire auxquelles il est possible de s'adresser ne contiennent pas toutes des mots-frontière. Le processus de catégorisation se fait encore par moitiés, quarts, huitièmes, etc... du nombre total de positions de la mémoire auxquelles le registre à décalage peut faire l'adressage, mais il faut pouvoir faire l'identification des vrais motsfrontière de façon à éviter une réécriture parasite du registre de rang 27 et une remise à jour incorrecte du registre à décalage 13, en particulier lorsque les positions libres de la mémoire sont utilisées dans d'autres buts, par exemple comme registre de travail ou pour d'autres mises en mémoire temporaires de données. Une façon d r atteìndre ce résultat est indiqué par la ligne en pointillé de la figure 1. La figure 1 représente en 40 la mémoire 10 comme comportant un bit de plus qu'il n'est nécessaire pour spécifier les motsfrontière. Ce bit supplémentaire de mot d'adressage s'utilise comme indicateur permettant d'identifier s'il s'agit d'un mot-frontière ; par exemple un "l"binaire pour un mot-frontière, ou un "0" binaire dans le cas contraire. La figure montre que ce bit est appliqué sur la ligne 41 à un circuit bistable 42 dont la sortie 43 est utilisée pour commander une porte ET 44 placée sur la ligne de sortie 25 du soustracteur.Le bistable 42 comprend une entrée 45 de remise à zéro qui est excitée au commencement de chaque cycle d'adress#age de la mémoire de façon à mettre la sortie du bistable dans un état tel que la porte ET 44 n'est plus active et ceci pour réaliser un "0"binaire sur sa sortie appliquée à la ligne 25. Par suite, ce n'est qu'à la lecture d'un mot-frontière contenu dans la mémoire 10 que le circuit bistable 42 est mis en état d'exciter la porte ET 44 et de provoquer ainsi le fonctionnement décrit plus haut du registre de rang 27 et du registre à décalage 13 selon la nature des signaux de sortie de soustracteur.En pratique le circuit 42 peut être un circuit monostable qui rend inactive la porte ET 44 Si le registre à décalage 13 comporte un étage correspondant à un chiffre de plus que le nombre nécessaire pour réaliser l'adressage de tous les mots-frontière, on peut faire l'adressage sur une mémoire 10 deux fois plus grande. En outre, à la fin du processus de catégorisation, si le résultat de la comparaison finale du soustracteur est introduit dans le registre à décalage 13r l'étage correspondant au chiffre le plus significatif contient le "1" binaire introduit au début du processus de catégorisation, c'est à dire après la comparaison de Y au chiffre formé uniquement de zéros, et les étages restants contiennent l'identification des mots-frontière correspondant à la catégorie de l'élément Y.Cela signifie que le registre à décalage contient l'adresse d'une position dans une partie de la mémoire qui n'est pas associée aux mots-frontière et que cette adresse est particulière au mot-frontière concerné. Cette adresse peut donc être utilisée pour emmagasiner une information supplémentaire sur la catégorie ou la classe correspondante, et cette information est disponible sur les sorties 19 de la mémoire en même temps que l'identité de la catégorie et l'information de rang relatives à l'élément Y La figure 1 montre que la sortie de la mémoire correspondant au chiffre le plus significatif du registre à décalage est connectée sur la ligne 46 de manière à exciter les portes ET 47 et à coupler ainsi les branchements 48 et les lignes 19 de sortie de la mémoire La figure montre que les sorties. 49 des portes ET 47 sont connectées de façon à introduire des données dans un registre 50 d'information de catégories 50. REVENDICATIONS 1. Appareil de traitement de données, caractérisé en ce qu T il est formé d'une mémoire destinée à emmagasiner un ensemble de mots mots de plusieurs bits, chacun de ces/représentant un caractère de différentiation entre des catégories ou des classes d'éléments d'information faisant partie d'une liste de tels éléments ordonnée en catégories ou en classes, de moyens destinés à introduire lesdits mots de plusieurs bits dans la mémoire dans un ordre lié à leur succession dans ladite liste mais dans un autre ordre prédéterminé d'adressage dans la mémoire, de moyens de comparaison destinés à comparer successivement un élément d'information à identifier à des mots de plusieurs bits lus dans la mémoire et capables de disposer des chiffres successifs d'adresses de mémoire chacun d'après le résultat de la comparaison précédant immédiatement et de moyens destinés à lire le contenu des adresses de mémoire dans un ordre déterminé par les moyens de comparaison. 2. Appareil selon la revendication 1, caractérisé en ce que les moyens de lectrure qu'il contient, comprennent un registre à décalage destiné à faire l'adressage de la mémoire en utilisant un réglage initial pour la première adresse de mémoire et des décalages pour chacune des entrées successives des chiffres suiantr sous la dépendance des moyens de comparaison. 3. Appareil selon l'une des revendications 1 ou 2, caractérisé en ce que les moyens de comparaison qu'il contient sont formés d'un soustracteur capable de fournir une indication du rang d'un élément d'information relative à un caractère de différentiation. 4. Appareil selon l'une quelconque des revendications 1 à 3, caractérisé en ce que les moyens d'introduction de données qu'il contient comprennent une mémoire morte dont la conception permet l'adressage par un circuit de mise en séquence.