BE902987R - Calculateur associatif permettant une multiplication rapide - Google Patents

Abstract

Méthode pour rechercher des relations entre un objet sélectionné et d'autres objets réalisée sur un processeur à ensemble associatif utilisant des techniques de recherche associatives et comprenant les étapes consistant à : identifier la position de rangée et de colonne d'un objet sélectionné devant etre recherché dans la matrice associative; et rechercher en parallèle chaque rangée sous la colonne identifiée avec l'objet sélectionné ou rechercher chaque colonne dans une rangée identifiée par l'objet sélectionné pour identifier une des dites relations prédéterminées entre l'objet sélectionné et les autres.

Description

  CALCULATEUR ASSOCIATIF PERMETTANT UNE MULTIPLICATION RAPIDE 

  
La présente invention se rapporte en général à des recherches dans des bases de données et plus particulièrement à une méthode pour effectuer une recherche dans une matrice associative.

  
La plupart des applications impliquant des ordinateurs comportent des recherches parmi une collection de données pour des éléments qui ont une caractéristique particulière, telle qu'une adaptation à un champ clé particulier, ou ayant une configuration spécifique de valeur de données. Des exemples de cette sorte d'opération comportent des recherches dans une base de données constituée par des numéros de cartes de crédit pour trouver le statut d'une carte particulière, des recherches parmi une image encodée numériquement pour trouver des éléments de la figure qui sont correspondent à une configuration, des recherches parmi une base de données de composants et de connexions dans un dispositif électronique pour trouver s'il y a un circuit entre deux composants, et des recherches dans un document de traitement de texte pour trouver une suite particulière de texte.

   Puisque les recherches font partie de la plupart des applications impliquant des ordinateurs, la vitesse à laquelle ceci peut être accompli a un effet majeur sur celle à laquelle les applications peuvent être accomplies.

  
Les matrices associatives sont des structures de données consistant en des noeuds et des liaisons reliant les noeuds ensemble. Les liaisons sont unidirectionelles mais deux noeuds peuvent avoir deux liaisons, une dans chaque sens. Toutes les liaisons sont supposées avoir le même coût ou poids. En général, une matrice associative peut être utilisée pour enmagasiner des relations entre des instances ou des composants, avec les axes de la matrice représentant des relations prédéterminées. 

  
Un exemple spécifique d'une utilisation possible d'une telle matrice associative serait de représenter les connexions entre les composants d'un dispositif électronique numérique. Une matrice associative différente serait utilisée pour chaque type de signal du système.

  
D'autres utilisations possibles des matrices associatives seraient de représenter les composants hiérarchiquement, avec chaque composant réalisés par plusieurs autres, les réseaux à héritage de sujet dans une programmation d'ordinateurs orientés par sujet et des représentations de coupes planes à travers des objets à trois dimensions dans lesquels toutes les parties de l'objet dans le même plan sont considérées comme reliées entre elles.

  
Des opérations majeures de recherche qui sont fréquemment accomplies dans ces matrices associatives consistent à trouver :

  
tous les composants connectés à un composant donné;

  
un chemin, s'il existe, entre deux composants;

  
quels sont les composants qui peuvent être atteints à partir d'un composant donné, par un nombre spécifié de liaisons;

  
tous les composants qui constituent un autre; et

  
tous les composants dont un autre est une partie.

  
Pour des architectures conventionnelles, ce problème est résolu de deux manières possibles. Suivant la première, toutes les liaisons vers un noeud donné peuvent être enmagasinées comme liste reliée commençant à ce noeud. Ceci donne une bonne performance pour trouver tous les noeuds connectés à un noeud donné mais au détriment d'un coût élevé pour l'espace d'enmagasinage si le nombre d'interconnexions est relativement élevé. Par exemple, si chacun de
1000 noeuds est connecté à 100 autres noeuds et qu'un indicateur à 32 bits est utilisé pour chaque connection, 3,2 megabits de mémoire seront nécessaires pour les interconnexions. En outre, la tâche de trouver tous les composants pouvant être atteints à partir d'un composant donné, pour un nombre fixe de liaisons, est très lente, nécessitant de fréquentes opérations d'empilage. 

  
En second lieu, les interconnexions entre les composants ou les noeuds peuvent être enmagasinées dans une matrice rectangulaire de bits, où les axes de la matrice représentent les composants ou noeuds et un bit établi sur 1 à une intersection rangée/colonne indique que les deux noeuds ou composants correspondants sont connectés. Cette approche économise l'espace de mémoire, mais est habituellement très lente sur des processeurs conventionnels puisque l'extraction ou le test de bits isolés hors d'un mot requiert fréquemment plusieurs instructions et plusieurs de ces opérations sont requises pour effectuer desrecherches dans la matrice.

  
La présente invention envisage une méthode de recherche dans une matrice associative utilisant des techniques de recherche associative pour améliorer la vitesse de recherche. Cette méthode est adaptée pour être utilisée dans un processeur à ensemble associatif, qui sera dénommé ci-après AAP et qui permet une recherche de noeuds simultanée dans une matrice, augmentant par là la rapidité de la recherche.

  
La méthode envisage l'utilisation de deux types de structure de données. En premier lieu, une structure de données pour localiser une instance particulière ou un composant dans une matrice. En second lieu, une matrice associative qui représente les relations entre les instances ou les composants. L'utilisation de ces

  
 <EMI ID=1.1> 

  
de part et d'autre dans les deux sens une structure "reliée" pour localiser tout point de noeud arbitraire dans la matrice. L'extraction des relations de la matrice peut être accomplie rapidement et facilement sur l'AAP par la manipulation de masques qui commandent le mécanisme de recherche.

  
C'est un but de la présente invention que de prévoir une méthode de recherche dans des matrices associatives avec une vitesse accrue.

  
C'est un autre but de la présente invention que de prévoir une méthode de recherche dans une matrice associative où un appareillage de recherche associatif effectue des recherches en parallèle sur les noeuds de la matrice. 

  
La Figure 1 représente un processeur à ensemble associatif sous forme de diagramme. La Figure 2 est un processeur à ensemble associatif sous forme de blocs. La Figure 3 montre l'interconnexion des cellules dans un ensemble. La Figure 4 montre une distribution pour un fichier d'indexage. La Figure 5 montre la condition d'un processeur à ensemble associatif en un point donné d'une recherche. La Figure 6 montre la condition d'un processeur à ensemble associatif en un point donné d'une recherche. La Figure 7 montre une matrice associative simplifiée. La Figure 8 montre un annuaire et une matrice associative pour un ensemble à 16 x 16 bits avec un annuaire de 10 pages.

  
 <EMI ID=2.1> 

  
différentes conditions d'un processeur à matrice associative à différents instants pendant l'accomplissement de la recherche.

  
La présente invention se rapporte à une méthode pour effectuer des recherches dans une matrice associative en utilisant une technique de recherche associative. La méthode est destinée à être utilisée avec un processeur d'un type particulier, connu comme processeur associatif. Le processeur du type associatif fournit les caractéristiques nécessaires pour accomplir la technique de recherche associative décrite dans la présente invention. Un Processeur Associatif sur lequel la présente méthode peut être utilisée est décrit dans le Brevet Belge 897441. Il y a plusieurs caractéristiques essentielles qu'un processeur associatif doit avoir afin que l'on puisse pratiquer la méthode de la présente invention.

   Il doit être formé d'un ensemble qui est généralement connu comme processeur à ensemble associatif ou AAP dont un exemple est montré schématiquement à la Figure 1. L'AAP 28 offre une forme de traitement séquentiel durant lequel une seule instruction de commande séquentielle 30 accomplit mêmes opérations simultanément sur de nombreux éléments de données. 

  
L'AAP est formé d'une matrice rectangulaire de cellules de processeur séparées, à un seul bit 34. Chaque cellule de processeur 34 comporte

  
 <EMI ID=3.1> 

  
registres à un seul bit, et une mémoire de données 36 pour enmagasiner de nombreux bits d'information tels que par exemple 64K bits. Les registres à un seul bit correspondant pour les différentes cellules forment des registres pour l'AAP.

  
Les cellules de l'ensemble sont interconnectées en rangées et colonnes de telle sorte que les cellules d'une rangée peuvent manipuler des éléments de données à bits multiples et des données peuvent être transférées verticalement entre les rangées. Des moyens doivent être fournis pour identifier les limites des éléments de données et ceci peut être fait en identifiant des bits particuliers dans une rangée comme étant le bit le plus significatif et le bit le moins significatif. La taille des éléments de données dans chaque rangée ne doit pas être uniforme pour toute la matrice, en particulier quand celle-ci doit être utilisée pour des applications à base de données, les différents éléments de données dans un fichier nécessiteront différentes plages de valeur et par conséquent de dimensions.

   Comme mentionné précédemment, toutes les cellules dans la matrice obéissent simultanément à la même instruction; cependant, il doit être possible d'inhiber ou de masquer tant les rangées que les colonnes des cellules, de telle sorte qu'elles n'obéiront pas aux instructions.

  
Quand un élément de données a été défini, tant en ce qui concerne la position que la dimension, tous les contenus des registres à un seul bit, associés avec chaque cellule de processeur à un seul bit dans cette position d'éléments de données particulière, peuvent être sujets à des instructions arithmétiques, de décalage ou booleienne entre eux. Le résultat de telles instructions comportera non seulement le résultat arithmétique ou logique mais aussi un indicateur de statut approprié tel qu'un dépassement pour une addition ou une soustraction, un zéro pour une correspondance, un plus pour une comparaison plus grande que et un moins pour une comparaison moindre que, etc. Tant le résultat que l'indicateur approprié peuvent être rendus disponibles pour être utilisés comme masque pour des instructions subséquentes. 

  
Il doit y avoir un bus vertical pour chaque colonne fournissant une communication entre toutes les cellules de la colonne et une cellule de registre de sortie externe. Le bus vertical doit être établi de telle sorte que seulement une cellule peut transmettre à tout moment donné. La sélection de cette cellule doit être accomplie au moyen du mécanisme de masquage décrit ci-dessus.

  
Des adresses pour chercher des données des bits de mémoire sont générées dans un registre d'adressage, de mémoire. Il doit être possible de transférer des données du registre de sortie au registre d'adressage. Il doit aussi y avoir un registre d'entrée pour contenir des valeurs devant être chargées dans la matrice ou contenir des valeurs devant être utilisées pour des recherches ou une comparaison. Les valeurs enmagasinées dans ce registre d'entrée peuvent être rendues disponibles à toutes les rangées, simultanément dans les colonnes appropriées, de telle sorte qu'une recherche ou une comparaison simultanée peut avoir lieu dans toutes les rangées, ou le contenu du registre d'entrée peut être transféré à toutes les rangées autorisées.

  
Une configuration qui fournit les caractéristiques ci-dessus est montrée à la Figure 2. Une matrice de cellules est montrée par 202 et on lui a associé une mémoire pour chaque cellule comme illustré précédemment à la Figure 1.

  
Les interconnexions entre une cellule et ses cellules voisines sont montrées à la Figure 3. Les interconnexions entre les cellules d'une colonne sont montrées par 302 et 304 tandis que les interconnexion entre des cellules d'une rangée sont montrées par 321 à
326. Les fonctions des connexions horizontales 321 à 326 entre les cellules d'une rangée sont clairement décrites dans le brevet belge précédemment mentionné. Chaque cellule a une connexion 312 vers un masque vertical et une connexion 314 vers un masque horizontal.

   Un bus vertical 316 est aussi prévu pour transférer des données verticalement entre les cellules et le registre de sortie 214 et du registre d'entrée 206 vers les cellules d'une colonne tandis que des données peuvent être transférées horizontalement entre les cellules d'une rangée et le registre de données/statut horizontal 208 en utilisant un bus horizontal 318. 

  
En se référant à nouveau à la Figure 2, on y a montré un registre de masquage vertical 204 suivant lequel chaque position de bit du registre est connectée à la connexion de masque vertical 312 de chaque cellule de la colonne correspondante de la matrice. Le registre de masquage vertical 204 fournit la fonction de masquage verticale précédemment discutéé et en outre fournit des moyens pour identifier les limites des éléments de données d'une manière telle que décrite dans le brevet belge précédemment mentionné. Un registre de masquage horizontal 210 fournit la fonction de masquage horizontal et a une pluralité de positions de bit chacune connectée à la ligne
314 de chaque cellule de la rangée correspondante de la matrice 202.

   Quand les instructions arithmétiques précédemment mentionnées sont accomplies, les indications de statut se rapportant aux résultats de telles instructions sur les données de chaque rangée doivent être obtenues, transférées et emmagasinées. Ceci est accompli en utilisant le bus horizontal 318 pour transférer les indicateurs de statut vers la position de bit correspondante d'un registre de données horizontal 208 où ils peuvent être enmagasinés. Le registre de données horizontal peut aussi être appelé le registre de statut. Le registre de données horizontal 208 est alors connecté par la connexion 212 au registre de masquage horizontal 210, rendant les indicateurs de statut des instructions arithmétiques disponible comme masque horizontal.

   Le bus vertical 316 connecte les bits correspondants d'un registre d'entrée de données vertical 206 à toutes les cellules d'une colonne et connecte aussi toutes les cellules de la colonne aux bits correspondants d'un registre de données de sortie 214. Les données de ce dernier peuvent être transférées à un registre d'adressage 216 au moyen de la connexion
218. La fonction du registre d'entrée et de sortie peut être combinée dans un seul registre entrée/sortie. 

  
L'opération de 1 'AAP décrite précédemment et montrée aux Figures 2 et 3 peut être mieux comprise au moyen d'un exemple simple. On supposera qu'on a un fichier d'indexage et que chaque enregistrement ou rangée contient les éléments de données A, B, C dont n'importe lesquels ou tous les trois peuvent être utilisés pour identifier un bloc de données emmagasiné particulier, et un indicateur de la position du bloc de données emmagasiné indexé dans le fichier. Un format suggéré pour le fichier d'indexage est montré à la Figure 4. En suppposant q'une matrice de 16 x 16 est utilisée, alors 3 pages de la mémoire de matrice contiendront 16 enregistrements avec le format montré.

   La page 1 identifiée par 38 comporte les éléments de données A, chacun ayant 16 bits pour 16 enregistrements, avec une rangée pour chaque enregistrement et une colonne pour chacun des 16 bits d'information dans les éléments de données A. La page 2 identifiée par 40 contient les éléments de données B et C pour chacun des 16 enregistrements, avec les éléments de données B comprenant 10 bits et les éléments de données C comprenant 6 bits.

  
La page 3 identifiée par 42 contiendra 16 indicateurs, un pour chacun des 16 enregistrements, pour les blocs de données emmagasinés.

  
On supposera que l'on doit effectuer une recherche dans une page de l'index pour une valeur 25 dans l'élément de données ou champ B montré comme une partie de la page 2 et que seulement un enregistrement dans la page contient cette valeur. On notera que les valeurs devant être recherchées (Champ B) ne doivent pas être dans un ordre particulier. La séquence des événements, décrite en relation avec les Figures 5 et 6, est comme suit :

  
1. L'adresse de la page 2 est chargée dans le registre d'adressage 216 et les champs B et C des 16 enregistrements enmagasinés à la page 2 sont amenés pour enmagasinage dans un registre, par exemple le registre 1 du jeu de registres associé avec chaque cellule de la matrice 202, comme montré à la Figure 5.

  
2. La valeur devant être recherchée, c'est-à-dire 25, est chargée dans les 10 bits les plus significatifs du registre d'entrée de données 206 et un masque autorisant les 10 bits les plus significatifs de la matrice, c'est-à-dire correspondant au champ B, est chargé dans le registre de masquage vertical 204. 

  
3. Une recherche est accomplie dans les 16 valeurs de données du champ B pour la valeur de données d'entrée 25. Pour l'exemple donné, la rangée 9 contient la valeur 25 correspondant à la valeur de recherche 25 et ceci est indiqué par un résultat 1 dans la position de bit correspondante du registre de données horizontal 208 qui est aussi appelé le registre de statut.

  
4. Le registre d'adressage 216 est changé pour indiquer l'adresse de la page 3 contenant les indicateurs, les indicateurs de la page 3 sont amenés et emmagasinés dans un registre, par exemple le registre 2 du jeu de registres.

  
5. Un masque n'ayant que des 1 est chargé dans le registre de masquage vertical 204 pour autoriser toutes les colonnes de la matrice et les contenus du registre de statut 208 sont transférés au registre de masquage horizontal 210. La situation à cette étape du processus est montrée à la Figure 6.

  
6. L'indicateur particulier P9 trouvé dans la rangée 9 est autorisé par le registre de masquage horizontal 210 et est transféré par le bus vertical 316 au registre de sortie 214 et de là au registre d'adressage 216. Cette adresse peut maintenant être utilisée pour amener la première page du bloc de données enmagasiné correspondant au contenu 25 trouvé dans l'index.

  
La méthode de la présente invention tire parti des caractéristiques de recherche associative de l'AAP décrit ci-dessus.

  
Comme mentionné précédemment, cette méthode utilise deux types de structures de données. Afin de situer la position de l'information relative désirée dans la matrice associative, différents types de mécanisme d'indexage pourraient être utilisés.

  
On a choisi d'utiliser un annuaire qui est simplement une liste d'instances ou de composants qui sont représentés par les rangées et les colonnes de la matrice. L'ordre dans lequel ces instances ou composants sont emmagasinés et les méthodes par lesquelles une instance particulière est trouvée, ou de nouvelles instances sont ajoutées, ne sont pas pertinents en ce qui concerne ce brevet. Toute méthode connue de la technique pourrait être utilisée. 

  
Aucune information liant les instances ou les composants l'un par rapport à l'autre n'est contenue dans l'annuaire, mais le contenu de l'annuaire peut incorporer des informations telles que l'identité des composants ou des instances. En guise d'exemple, l'annuaire peut simplement être une liste de composants numérotés. Ces composants peuvent être trouvés dans la matrice en recherchant la rangée et la colonne avec le même numéro.

  
La définition du type de relation qui existe entre les composants ou les instances et comment ces relations devraient être emmagasinées peut être défini au préalable. La Figure 7 représente une matrice pour un annuaire ayant 8 composants ou instances. La matrice associative montrée à la Figure 7 illustre comment une information relative peut être emmagasinée. Deux types d'associations, liaisons ou relations peuvent être enmagasinés. L'un est constitué par les relations en colonne et l'autre celles en rangée. Ces relations sont définies au préalable avant d'établir la matrice.

  
En guise d'exemple, la matrice peut être établie pour contenir la relation hiérarchique des composants suivant laquelle un composant est composé d'autres et est une partie d'autres composants. Les relations sont représentées par les axes de la matrice. La relation en colonne peut être définie comme : tous les composants qui "composent ou constituent" le composant Identifié par la colonne. Si l'on désirait retrouver tous les composants qui forment une partie du composant C3, on devrait chercher tous les bits établis au niveau 1 dans la troisième colonne sous C3 et on découvrirait que C3 est constitué par les composants C2 et C7. De même, Cl est constitué de C3 et C6, C5 est constitué de C2 et C8, C6 est constitué de C2, et C8 est constitué de C7.

   Les composants C2, C4 et C7 sont considérés comme des parties primitives, car ils ne sont pas faits à partir d'autres composants, comme illustré par le fait que les colonnes C2, C4 et C7 ont uniquement des zéros. 

  
La relation par rangée peut être définie pour signifier : tous les composants qui "font partie de" composants d'ordre plus élevé. Une question pour établir cette relation peut se dérouler dans la direction des rangées. Une recherche dans la seconde rangée montre que C2 est utilisé dans les composants C3, C5 et C6. En outre, en accomplissant les recherches par rangée sur ces composants, on voit que C3 et C6 sont utilisés dans Cl, tandis que C7 fait partie de C3 et C8, et que ce dernier fait partie de C5.

  
Ce mécanisme de recherche itératif peut être accompli n'importe quel nombre de fois dans l'une ou l'autre direction et le mécanisme est orchestré par la manipulation de masques pour.les rangées et les colonnes. L'identification des valeurs de colonnes et de rangées est un exercice qui sera discuté subséquemment, mais son importance devra être comprise sur un plan beaucoup plus élevé car elle joue un rôle important dans la recherche parmi de très grandes bases de données.

  
Un exemple d'une recherche à une plus grande échelle peut être expliqué en utilisant le diagramme de la Figure 8. Ici, on a arbitrairement choisi d'utiliser une matrice de 16 x 16 bits; cependant, toute configuration de bits pourrait être utilisée. En supposant cette configuration, la disposition physique d'un annuaire d'instances et l'établissement des relations entre ces instances sont montrés. Dans un but de simplification, une taille de mot de 16 bits sera supposée et le nombre de pages de l'annuaire sera de 10. En guise d'exemple, une méthode de recherche linéaire sera employée.

  
Les caractéristiques associatives de l'AAP permettent aux contenus d'être placés dans tout ordre souhaité. S'il on suppose que l'action requise est de trouver la relation d'un composant appelé C20 vis-à-vis de tous les autres, alors la séquence des événements comportera

  
1) recherche dans l'annuaire pour la position du composant qui sera représentée par un noeud dans la matrice associative,

  
2) l'établissement des masques appropriés pour le traitement des données emmagasinées dans la matrice associative et

  
3) la traversée de la matrice associative à la recherche de ces relations. 

  
Si l'on trouve que C20 est à la cinquième rangée de la cinquième page de l'annuaire, pour trouver tous les composants qui constituent C20, une recherche de la colonne 5 dans les pages 5, 15, 25, 35, 45,
55, 65, 75, 85 et 95 de la matrice associative doit être accomplie. De même, pour trouver tous les composants dont C20 fait partie, alors la recherche doit être accomplie dans la cinquième rangée des pages
51 à 60. Si des niveaux d'information plus poussés sont requis, la traversée de la matrice est accomplie.par des manipulations ultérieures de masques établis par des bits trouvés actifs pendant la première traversée.

  
Dans un but de simplification, on décrira les étapes pour réaliser les mécanismes de recherche décrits ci-dessus, seulement pour une

  
 <EMI ID=4.1> 

  
Recherche dans l'annuaire

  
Une méthode de recherche linéaire peut être utilisée pour des recherches dans un annuaire non-ordonné où une identification arbitraire des composants est emmagasinées. Avec les paramètres donnés, la séquence des événements pour rechercher un composant C20 dans l'annuaire se déroule comme suit :

  
1. Une valeur représentant le composant C20 devant être recherchée dans l'annuaire est chargée dans le registre d'entrée 206. Les registres de masquage horizontal et vertical 210 et 204 sont établis pour autoriser toutes les rangées et toutes les colonnes. L'adressage de la première page en mémoire est envoyé dans le registre d'adressage de mémoire 216 et la page 1 de l'annuaire est amenée dans la matrice et emmagasinée dans un registre, comme par exemple le registre 1 montré à la Figure 9.

  
2. Une comparaison parallèle ou une soustraction entre le registre d'entrée 206 et le registre 1 est accomplie avec indication de statut résultant pour chaque rangée enmagasinée dans le bit correspondant du registre de statut 208. Un 1 dans le registre de statut signifie qu'une correspondance a été trouvée tandis qu'un 0 signifie qu'elle ne l'a pas été. 

  
3. Les contenus du registre de statut 208 sont alors testés pour voir si l'un ou l'autre bit sont actifs, c'est-à-dire 1. Dans la négative, alors l'adressage de la page suivante est généré et la séquence ci-dessus est répétée. Les états du registre des fonctions ci-dessus sont montrés à la Figure 9, indiquant une correspondance dans le registre de statut 208 dans la rangée 5.

  
La position de l'instance correspondante dans l'annuaire est la clef principale pour la manipulation de la matrice associative qui emmagasine les relations entre les composants. Si par exemple, le cinquième enregistrement sur la cinquième page correspondait à C20, le bit du registre de statut correspondant à la cinquième rangée contiendrait un 1 lorsqu'on effectue une recherche dans la cinquième page.

  
Quoique les contenus des registres de masquage sont normalement utilisés pour autoriser les rangées ou les colonnes de la matrice à accomplir la recherche dans la matrice, une alternative consiste à accomplir une opération logique ET entre un plan de données contenant une rangée de l's (ou une colonne, dépendant du type de recherche) correspondant à la rangée (colonne) autorisée par le masque. L'avantage de cette alternative est que cette configuration peut être conservée dans une page de la mémoire principale pour être utilisée dans des opérations ultérieures.

  
Le masque horizontal peut être établi comme suit. Les contenus du registre du statut 208 sont déplacés vers le registre de masquage horizontal 210 permettant seulement à la cinquième rangée de réagir à l'instruction suivante. Une rangée ne comprenant que des l's est chargée dans le registre d'entrée 206 et est transférée à l'un des registres du jeu de registre tel que le registre 2 comme montré à la Figure 10, de telle sorte que des l's sont chargés dans la rangée activée 5. Cette configuration peut être emmagasinée pour usage ultérieur. 

  
L'établissement du masque vertical se déroule comme suit. Un plan de données ayant une diagonale de l's comme montré à la <EMI ID=5.1>  que par exemple le registre 4. Seule la rangée autorisée sera chargée de telle sorte que dans ce cas, le cinquième bit sera établi cette information est alors transférée au registre entrée/sortie 206. Les deux registres de masque 204 et 210 sont établis pour autoriser toutes les rangées et toutes les colonnes et la configuration dans le registre entrée/sortie est transférée à toutes les rangées, ce qui résulte en la configuration montrée à la Figure llb.

  
Traversée de la Matrice Associative

  
La traversée de la matrice associative est une procédure itérative. L'approfondissement de la recherche peut se terminer quand il n'existe plus de relations additionelles ou après qu'un nombre préétabli de relations a été trouvé, ou lorsqu'une certaine valeur est déterminée.

  
Un exemple de la matrice associative qui pourrait exister pour l'annuaire de la Figure 9 est montré à la Figure 12. Une correspondance pour C20 a été trouvée dans la position 5 de l'annuaire et les masques horizontal et vertical ont respectivement été enregistrés dans les registres 2 et 4. Pour trouver toutes les parties dont C20 est constitué, on devrait regarder tous les bits autorisés dans la cinquième colonne et ceci continuerait jusqu'à ce qu'on ne trouve plus de bits actifs. Ceci peut être accompli par ce qui suit :

  
1. Autorisation de toutes les rangées et de toutes les colonnes.

  
2. Chargement des données de la matrice associative dans le registre 8. Accomplissement d'une opération ET entre le registre 4, montré à la Figure llb et y ayant le masque vertical enmagasiné, et le registre 8. Le résultat de cette opération ET est établi dans le registre de statut 208, comme montré dans la Figure 12 indiquant qu'il y a une concordance dans les seconde, quatrième et treizième positions se rapportant à C10, C30 et T07, comme montré à la Figure 9, qui sont les parties qui constituent C20.

  
Les résultats peuvent être débités en rapportant ces positions de bits de statut à l'annuaire en : 

  
1. Déplaçant les bits de statut vers le masque horizontal 210, autorisant tous les bits dans le masque vertical 204, chargeant la page de l'annuaire, transférant alors les contenus des rangées actives du registre dé sortie 206, un à la fois, pour être imprimés comme à la Figure 13.

  
Ce simple exemple a montré comment traverser un niveau vers le bas. Afin d'accomplir des traversées à multi-niveaux, c'est-à-dire identifier les composants qui constituent aussi C10, C30 et T07, les opérations suivantes sont accomplies itérativement. A cause de cette recherche itérative, les bits de statut doivent être conservés dans un registre et chargés dans le masque horizontal 210 chaque fois que l'on recherche les composants d'un sous-composant.

  
1. On crée un nouveau masque vertical pour chacun des bits de statut en chargeant les bits de statut ci-dessus dans le registre de masquage horizontal 210. Ceci autorise les bits précédemment établis pour activer leur rangées associées. On charge une nouvelle rangée de l's en diagonale vers le registre 9 et on transfère vers le registre de sortie 206 les rangées actives de bits, une rangée à la fois. A partir du registre de sortie, chaque rangée est déplacée une par une vers le masque vertical 204, comme montré à la Figure 14a qui illustre l'action appliquée aux bits se rapportant à C10.

  
2. On établit le registre de masquage horizontal et le registre d'entrée uniquement sur des l's.

  
3. On compare tous les bits dans la colonne active de la matrice associative. La Figure 14b montre qu'il n'y a pas d'autres

  
 <EMI ID=6.1> 

  
uniquement dans la seconde colonne. Le processus pour C30 et T07 est accompli de la même manière et indique qu'il n'y a pas d'autres composants qui constituent ces composants, comme indiqué par la

  
 <EMI ID=7.1> 

  
Quoique les principes de l'invention aient été décrits ci-dessus en se référant à des exemples particuliers, il est bien entendu que cette description est faite seulement à titre d'exemple et ne constitue aucunement une limitation de la portée de l'invention.

Claims (13)

1. REVENDICATIONS <EMI ID=8.1>

   sélectionné et d'autres objets dans une matrice associative du type qui enmagasine des relations entre les objets, chaque-objet étant représenté tant par une rangée que par une colonne de la matrice, chacune des dites relations étant définie au préalable et associée avec un des axes de la matrice, l'existence d'une relation entre les

   <EMI ID=9.1>

   objet et-.de la colonne d'un autre objet, ladite méthode étant réalisée sur un processeur à ensemble associatif utilisant des techniques de recherche associatives et comprenant les étapes consistant à :

   identifier la position de rangée et de colonne d'un objet sélectionné devant être recherché dans la matrice associative; et

   rechercher en parallèle chaque rangée sous la colonne identifiée avec l'objet sélectionné ou rechercher chaque colonne dans une rangée identifiée par l'objet sélectionné pour identifier une des dites relations prédéterminées entre l'objet sélectionné et les autres.
2. 2. Méthode comme décrite sous 1, suivant laquelle on effectue une recherche en parallèle dans la rangée sous la colonne associée avec l'objet sélectionné pour identifier la relation associée avec les colonnes et où on effectue une recherche en parallèle dans chaque colonne sous une rangée pour identifier la relation représentée par les rangées dans ladite matrice.
3. 3. Méthode comme sous 1, suivant laquelle on effectue une recherche en parallèle dans chaque rangée sous la colonne identifiée

   -par l'objet sélectionné l'aide_de l'usage d'un masque vertical qui restreint l'opération du processeur à ensemble associatif à une ou plusieures colonnes sélectionnées de la matrice.
4. 4. Méthode comme sous 1, suivant laquelle on effectue une recherche en parallèle dans chaque colonne sous la rangée identifiée par l'objet sélectionné par l'usage d'un masque horizontal qui est établi pour restreindre l'opération du processeur à ensemble associatif à une ou plusieurs rangées sélectionnées de la matrice.
5. 5. Méthode comme sous 3, suivant laquelle on effectue une recherche dans une seule colonne de la matrice pour des positions ayant des bits établis sur 1, par l'usage d'un masque vertical qui autorise seulement la seule colonne sélectionnée.
6. 6. Méthode comme sous 4, suivant laquelle on effectue une recherche dans une seule rangée de la matrice pour des positions ayant des bits établis sur 1, par l'usage d'un masque horizontal authorisant seulement la rangée sélectionnée de la matrice.
7. 7. Méthode comme sous 6, suivant laquelle les positions des bits établis sur 1 dans une rangée donnée sont utilisées pour identifier les objets associés avec ces colonnes de la matrice associative et par là pour identifier la relation associée avec les axes de rangée de la matrice comme existant entre l'objet sélectionné et ceux associés avec chacune des colonnes qui ont un 1 dans la rangée donnée.
8. 8. Méthode comme sous 5, suivant laquelle les positions des bits établis sur 1 dans une colonne donnée identifient les objets associés avec ces rangées de la matrice associative et pour identifier la relation associée avec les axes de colonne de la matrice comme existant entre l'objet sélectionné et ceux associés avec chacune des rangées qui ont un 1 dans la colonne donnée.
9. 9. Méthode comme sous 1, comprenant en outre l'étape autorisant les rangées ou colonnes identifiées dans la recherche pour conduire une seconde itération de la méthode de recherche.
10. 10. Méthode comme sous 9, où les bits trouvés sur 1 dans une rangée donnée sont utilisés pour former un masque horizontal pour autoriser les rangées qui doivent donner lieu à une recherche dans une itération suivante de la méthode de recherche.
11. 11. Méthode comme sous 9, comportant en outre l'étappe consistant à utiliser les bits que l'on trouve établis sur 1 dans une colonne donnée pour former un masque vertical pour autoriser les colonnes dans lesquelles une recherche doit être effectuée dans une itération suivante de la méthode de recherche.
12. 12. Méthode comme sous 9, comprenant les étapes consistant à : rechercher dans la matrice associative de manière répétée pour identifier un jeu de relations hiérarchiques entre les objets.
13. 13. Une méthode de recherche de relations entre un objet sélectionné et d'autres objets dans une matrice associative du type qui emmagasine des relations entre les objets, chaque objet étant représenté tant par une rangée que par une colonne de la matrice, chacune des dites relations étant définie au préalable et associée avec un des axes de la matrice, l'existence d'une relation entre les objets étant signifiée par un 1 à l'intersection de la rangée d'un objet et de la colonne d'un autre objet, ladite méthode étant réalisée sur un processeur à ensemble associatif utilisant des techniques de recherche associative et comportant les étapes consistant à :

    identifier la rangée et la colonne de l'objet sélectionné dans la matrice associative;

    établir des masques appropriés pour la rangée et la colonne identifiées afin de manipuler les données dans la matrice associative; et

    traverser la matrice associative en utilisant ledit masque pour identifier des relations entre l'objet sélectionné et les autres objets de la matrice associative.