Brevet FR2902208A1 — publié le 20071214

La présente invention concerne un gestionnaire de mémoire associative. L'invention permettant d'améliorer la gestion de la mémoire associative, avec une application notamment pour les ordinateurs ou les téléphones portables. Les applications particulières interviendront par exemple dans le domaine de l'intelligence artificielle ou dans l'exploitation des réseaux. La mémoire associative est un dispositif de stockage des données, dans lequel la recherche des dites données se fait directement sur le contenu de la mémoire et non sur les adresses de données stockées dans la mémoire. La mémoire associative peut être utilisée dans la plupart des domaines informatiques. Elle est utilisée pour stocker une donnée très particulière et précieuse qui est dorénavant appelée résultat. Il sera possible de retrouver ce résultat au moyen d'une clé. La mémoire associative associe donc une clé à un résultat. La clé est une chaîne de données. La chaîne de données est une suite de caractères. Il existe plusieurs normes informatiques d'encodage qui comprennent plusieurs caractères de base. Selon chaque norme informatique, les caractères sont codés avec une valeur précise correspondante. On appelle taille de la norme, le nombre de caractères possibles qui peut être défini dans une norme. Avec pour illustrer, à titre d'exemple, la norme ASCII étendue définie sur 8 bits, avec des caractères définis chacun par un chiffre entier entre 1 et 256. La taille de la norme ASCII étant de 256. Pour la nonne ASCII, certains caractères sont lisibles comme les caractères de l'alphabet ou les chiffres, d'autres sont non lisibles comme les instructions de flèches ou d'entrée. Les nouvelles normes pouvant encoder les caractères sur un nombre inférieur ou supérieur de bits. De façon distincte, on parle de profondeur de la mémoire associative pour décrire la taille de la chaîne de données correspondant au nombre de caractères composant cette chaîne de données également appelée clé ou chaîne de données clé. La vitesse de calcul du processeur sur la mémoire associative étant fonction de la profondeur de la mémoire associative. Lorsque le processeur traite la mémoire associative, il débute par le premier caractère de la chaîne de données. Il transcrit la valeur du caractère en une position dans un tableau d'une seule colonne et d'autant de lignes que la taille de la norme. On parle du tableau de caractères. Par exemple, si la valeur du caractère est 12 en ASCII étendu, il positionne le curseur de ligne dans la douzième ligne du tableau à 256 lignes. Il en va de même pour tous les caractères suivants de la chaîne de données. Pour lire la chaîne de données, le processeur va donc sauter de tableau de caractères en tableau de caractères. La taille de chaque tableau de caractère selon l'art antérieur étant égale à la taille de la norme. Le positionnement du curseur (P) s'effectue par des mouvements de mémoire. Le tableau à 256 lignes possède une base (B). La valeur du caractère (C) est utilisée comme entier relatif par rapport à cette base. Ainsi (B) + (C) = (P). La succession des positions du curseur est appelée route. Il existe deux familles de techniques de l'art antérieur pour gérer une mémoire associative. La première famille, dite famille à mémoire associative à profondeur limitée et à taille de tableau de caractères invariable, consiste à utiliser un algorithme de condensât, nommé hash en langue anglaise, afin de réduire la profondeur par différents algorithmes, comme par exemple MD5 ou SHA, qui proposent une signature simplifiée de la chaîne de données. L'avantage de cette technique est d'augmenter les performances de recherche. Un défaut avec cette technique est que plusieurs chaînes de données peuvent avoir la même signature, on parle de collision. Il est alors nécessaire de disposer d'un gestionnaire de collision. La seconde famille, dite à mémoire associative à profondeur illimitée et à taille de tableau de caractère invariable, utilise la totalité de la chaîne de données pour la recherche de résultat dans la mémoire associative. Cette famille est très consommatrice en mémoire de l'ordinateur mais est très précise dans ses résultats. Il n'est pas nécessaire avec cette seconde famille de disposer de gestionnaire de collision. Un objet principal de l'invention est d'améliorer la gestion de la mémoire associative en conjuguant des qualités de précision de recherche et des qualités de rapidité et de puissance de calcul. Un objet de l'invention est de pouvoir facilement arbitrer entre le parti pris de la puissance de calcul et celui de la consommation mémoire. Un objet de l'invention est de pouvoir capitaliser l'expérience dans une mémoire associative notamment pour de l'intelligence artificielle Un objet de l'invention est d'ouvrir de nouveaux usages, comme par exemple la sécurisation d'application par capitalisation d'expérience. Un objet de l'invention est de perfectionner la gestion d'autorisation et de permission. L'allocation de permission étant beaucoup plus fine et précise. L'invention permettant notamment de s'affranchir de la méthode de pagination. Un objet de l'invention est d'améliorer les performances de gestion de bases de données à caractère historique, dites par exemple en langue anglaise de data mining. Un objet de l'invention est d'améliorer les performances de calcul avec des applications par exemple pour les calculs en recherche génétique, analyse boursière ou météorologique. Un objet de l'invention est de permettre une création physique de nouvelles cartes utilisant une ou plusieurs puces spécifiques associées notamment à une mémoire statique permettant de faire cohabiter plusieurs familles de gestion de mémoire associative. Un objet de l'invention est d'améliorer la recherche de symboles ou données ou caractères dans un programme. Un objet de l'invention est de répartir la mémoire associative sur plusieurs machines pour une gestion de grandes quantités de données pouvant 5 éventuellement nécessiter de la répartition de charge. Un objet de l'invention est de permettre l'automatisation de la gestion des flux par observation du trafic et capitalisation d'expérience du trafic réel. A titre illustratif, cette invention peut être utilisée pour réguler le trafic routier en automatisant les changements d'état des feux de circulation. En outre, cet objet 10 de l'invention a pour but de donner des indications et prévisions de trafic. Dans un aspect principal, l'invention propose une nouvelle famille de gestion de mémoire associative, dite famille à mémoire associative à profondeur illimitée à taille d'encodage variable à structure systémique et polymorphe. Par structure systémique, il est compris une structure qui contient un grand nombre 15 de variables en inter relation. Par structure polymorphe, il est compris une structure mémoire qui peut être modifiée soit par un opérateur soit par une fonction embarquée dans cette structure mémoire, cette fonction embarquée portant elle-même la fonction de polymorphisme. Dans un aspect principal, l'invention permet à un opérateur de restructurer 20 la mémoire associative selon ses besoins. Les restructurations ouvrant des nouveaux champs de possibilité de gestion de la mémoire associative. Dans un aspect l'invention restructure la mémoire associative, caractère par caractère en affectant à chaque caractère un espace mémoire structuré capsule qui comporte à la fois un pointeur et un tableau de caractères modifié. Dans un aspect, le gestionnaire comprend une gestion d'une mémoire traçante qui stocke les données afférentes au passage du curseur sur un caractère d'une chaîne de caractères dans une mémoire associative. Ce traceur est polymorphe, c'est-à-dire qu'il peut avoir une structure de nature et de taille différente, caractère par caractère, définie ou pas par l'opérateur. Dans un aspect, le gestionnaire comprend une structure de gestion des données de résultat. Cette structure de gestion des résultats est polymorphe, c'est-à-dire qu'elle peut avoir une structure de nature et de taille différente, caractère par caractère, définie ou pas par l'opérateur. Dans un aspect particulier, les structures de gestion de traceur et de données de résultat peuvent être utilisées simultanément et en association pour des applications dans l'intelligence artificielle. Dans ce cas, chaque passage dans un élément du tableau de caractères incrémente la mémoire traceur. Cette information de comptage ou de traçage est enregistrée dans la mémoire traceur qui permet par la suite d'en déduire un taux de passage assimilable à une capitalisation de l'expérience. Le résultat est utilisé pour stocker des informations résultant d'un traitement, quel que soit ce traitement. Par exemple donner le nombre de caractères connus lors de la coupure de la chaîne de données si la route n'a pas été entièrement trouvée. Dans le cas où la route n'a pas été entièrement trouvée, cela signifie que la chaîne de données demandée est potentiellement anormale. C'est la combinaison des informations de traçage et de résultat qui permet de concrétiser les applications d'intelligence artificielle. Ce procédé pouvant être réalisé sous une forme matérielle, un circuit électronique pouvant être dédié à ces opérations. Dans un aspect particulier, la structure de gestion de traceur peut être utilisée seule. L'utilisation du traceur seul peut permettre d'effectuer des comptages par route ou chemin emprunté. L'utilisation seule du traceur permettra de connaître le nombre de passages sur chacune des routes possibles. 1 o Dans un aspect particulier, la structure de gestion de résultat peut être utilisée seule. L'utilisation de la structure résultat seule peut permettre d'associer une donnée résultat à une chaîne de données clé. Dans un aspect particulier, l'invention propose d' embarquer sur une puce matérielle ou un programme logiciel, au moins 3 familles de mémoires 15 associatives qui seront choisies et utilisées en fonction des besoins du programme informatique et du programmeur informatique. Ces trois familles étant la mémoire associative à profondeur illimitée et à taille d'encodage variable, la mémoire associative à profondeur limitée et à taille invariable et la mémoire associative à profondeur illimitée et à taille invariable. 20 Les figures annexées représentent un mode particulier de l'invention sur lesquelles : La figure la représente la gestion d'une mémoire associative selon l'art antérieur, les caractères présentés sous forme de tableau La figure lb représente la gestion d'une mémoire associative selon l'art antérieur présentée schématiquement sous forme d'arbre - La figure 2 représente la structure de la génération d'un espace mémoire structuré selon l'invention La figure 3a représente la gestion d'une mémoire associative selon le gestionnaire de la présente invention La figure 3b représente la gestion d'une mémoire associative selon le gestionnaire de la présente invention et présenté sous forme d'arbre La figure 4 décrit une carte d'extension d'ordinateur selon un aspect particulier de l'invention La figure la représente la gestion d'une mémoire associative selon l'art antérieur, les caractères sous forme de tableau de caractères (10), avec dans le cas de la figure la, une taille de norme (11) qui vaut seize. Avec en cinquième tableau de caractères une valeur de caractère (12) qui vaut deux, et qui occupe donc la deuxième case du tableau de caractères (10). La figure lb représente la gestion d'une mémoire associative selon l'art antérieur présentée schématiquement sous forme d'arbre. Avec cette figure lb, il est compris comment rapidement l'arborescence des choix à chaque gestion de caractère multiplie l'ensemble des combinaisons pour retrouver la clé d'une mémoire associative, à un rythme (taille de la norme)exposant(nombre de caractères traités). Couramment l'ensemble des étages de traitement des caractères étant dénommé pipeline en langage informatique. La figure 2 représente la structure de la génération d'un espace mémoire structuré capsule (20) selon l'invention. Il est constitué un espace mémoire capsule (20) qui comprend un espace mémoire pointeur (21) ouvrant sur une structure polymorphe (26) composée dans le cas présent de deux sous structures dont une première sous structure de données de traçage (28) et d'une seconde sous structure de données de résultat (29). La première sous structure de données de traçage (28) permet de donner des informations sur le chemin de passage menant au résultat. Ces informations to comprennent par exemple, un compteur de passage. Elle peut également contenir des fonctions plus complexes comme des attributions de permission ce qui sous entend de pouvoir aussi créer des héritages de permission par étage de profondeur de la mémoire associative. Ces fonctions étant alors assimilables à une gestion des permissions en pipeline. La seconde sous structure de données 15 peut comprendre un pointeur simple qui pointe sur une autre structure qui est un résultat. Elle peut également contenir des fonctions plus complexes comme pour l'association d'une taille à une chaîne de caractères grâce à une sous structure composée d'un pointeur sur la dite chaîne de caractères (char *ptr) et d'un entier de taille (int size). Ces deux sous structures de données cohabitent sans 20 interaction particulière. Toutefois, leur partie commune est d'appartenir à la même structure polymorphe et la lecture des deux sous structures pouvant s'effectuer pour certaines comparaisons. L'espace mémoire structuré capsule (20) comprend également un tableau de caractère modifié (25). La taille du tableau de caractère modifié (25) étant égale à la valeur du caractère (12). Cette réduction de taille permettant d'optimiser la mémoire. A titre d'exemple, l'espace mémoire capsule peut être réalisé au moyen d'un algorithme de structuration par un code informatique C++ ci-après : class Poly { } ; class Poly_result : public Poly { public : void *result ; }; class Poly trace : public Poly { public : void *trace ; }; class Poly_dual : public Poly { public: void *result; public: void *trace; }; class Capsule { public : void *base ; public : int tab_size ; public : Poly *pointeur ; La figure 3a représente la gestion d'une mémoire associative selon l'invention avec une navigation qui passe itérativement d'espace mémoire structuré capsule (20) en espace mémoire structuré capsule (20). Chaque espace mémoire structuré capsule (20) étant de structure et de taille spécifique fonction notamment du caractère (12) dont il est l'émanation. La figure 3b représente la gestion d'une mémoire associative selon l'invention présentée sous forme d'arbre. Il est immédiatement visible comment le nombre des combinaisons possibles de chemin se trouve diminué avec une valeur totale égale à fJ(i=1 à i=n) ( 12i) , (12i) étant la valeur du ième caractère de la chaîne de caractères. Par ailleurs, les informations supportées lors de la gestion de cette mémoire associative sont enrichies de nouvelles informations attachées comportant notamment par exemple, des informations de chemin et/ou des informations de résultat. La figure 4 représente un schéma électronique d'implémentation matérielle sur une carte à circuit imprimé alimentée électriquement par une pile (200). Elle comprend un processeur gestionnaire de mémoire associative (102) qui permet de gérer plusieurs familles de mémoire associative. L'une de ces familles nécessite des mécanismes de condensât que la mémoire de type ROM (100) liée par un bus au processeur gestionnaire de mémoire associative (102) permet de stocker. Une interface optionnelle (401) permet de reprogrammer cette mémoire de type ROM (100). Le processeur gestionnaire de mémoire associative (102) stockera toutes les données relatives de mémoire associative dans une mémoire de type RAM (103), comme par exemple une SRAM ù Static RAM, au moyen de bus (403). Le nombre d'unités de mémoire RAM (103) pouvant être multiple. Une interface de types bus (404) connecté au processeur gestionnaire de mémoire associative (102) permet d'interfacer n'importe quel type de circuit, ordinateur, téléphone portable. Cette interface (404) permet d'accéder aux données de la mémoire RAM (103) par le biais du processeur gestionnaire de mémoire associative (102). L'invention concerne donc un gestionnaire de mémoire associative (102), la mémoire associative étant une chaîne de caractères tous encodés selon une norme commune, à la fin de la chaîne de caractères sont positionnés des résultats, chaque caractère étant transcrit par une position correspondant à la valeur du caractère (12) dans un tableau de caractères (10) d'une seule colonne et d'un nombre de lignes égal à la taille (11) de la norme, le gestionnaire lisant la chaîne de caractères, caractère par caractère depuis le début jusqu'à la fin de la chaîne de caractères caractérisé en ce que le gestionnaire de mémoire associative (102) génère pour chaque caractère un espace mémoire structuré capsule (20) qui loge au moins un espace mémoire pointeur (21) ouvrant sur une structure polymorphe systémique (26) de gestion de données relatives à la mémoire associative, et un tableau de caractères modifié (24) à taille fonction de la valeur du caractère. L'invention concerne donc un gestionnaire de mémoire associative caractérisé en ce que la structure polymorphe de gestion de données est composée d'au moins une sous structure qui est soit une première sous structure de données de traçage, soit une seconde sous structure de données de résultat, les données de traçage étant les données du chemin de navigation de lecture dans le tableau de caractères modifié à taille variable L'invention concerne donc un procédé de gestion d'une mémoire associative comportant une chaîne de caractères tous encodés selon une norme commune caractérisé en ce qu'il comprend pour chaque caractère traité successivement au moins, une étape de génération d'espace mémoire structuré capsule, une réservation d'espace mémoire dans cet espace mémoire structuré capsule destiné à loger un pointeur, une génération d'une extension structure polymorphe systémique de l'espace mémoire structuré capsule accessible par le pointeur On voit bien que de nombreuses variantes éventuellement susceptibles de se combiner peuvent ici être apportées sans jamais sortir du cadre de l'invention tel qu'il est défini ci-après. REVENDICATIONS 1 - Gestionnaire de mémoire associative (102), la mémoire associative étant une chaîne de caractères tous encodés selon une nonne commune, à la fin de la chaîne de caractères sont positionnés des résultats, chaque caractère étant transcrit par une position correspondant à la valeur du caractère (12) dans un tableau de caractères (10) d'une seule colonne et d'un nombre de lignes égal à la taille (11) de la norme, le gestionnaire lisant la chaîne de caractères, caractère par caractère depuis le début jusqu'à la fin de la chaîne de caractères caractérisé en ce que le gestionnaire de mémoire associative (102) génère pour chaque caractère un espace mémoire structuré capsule (20) qui loge au moins un espace mémoire pointeur (21) ouvrant sur une structure polymorphe systémique (26) de gestion de données relatives à la mémoire associative, et un tableau de caractères modifié (24) à taille fonction de la valeur du caractère. 2 - Gestionnaire de mémoire associative selon la revendication 1 caractérisé en ce que la structure polymorphe de gestion de données est composée d'au moins une sous structure qui est soit une première sous structure de données de traçage, soit une seconde sous structure de données de résultat, les données de traçage étant les données du chemin de navigation de lecture dans le tableau de caractères modifié à taille variable 3 û Procédé de gestion d'une mémoire associative comportant une chaîne de caractères tous encodés selon une nonne commune caractérisé en ce qu'il 25 comprend pour chaque caractère traité successivement au moins - une étape de génération d'espace mémoire structuré capsule - une réservation d'espace mémoire dans cet espace mémoire structuré capsule destiné à loger un pointeur- une génération d'une extension structure polymorphe systémique de l'espace mémoire structuré capsule accessible par le pointeur