INPI-France/Brevets-Francais-2024-Chunked huggingface dataset:
Sur les annexes de la description - l'annexe 1 constitue une spécification générale de la machine, comportant un certain nombre de définitions de base, la définition de l'état courant de la machine, ainsi que de son jeu de commandes de base, dans un exemple particulier - l'annexe 2 définit de manière détaillee le contenu de la mémoire des cellules, dans l'exemple où les mêmes cellules sont utilisées pour la mémoire de désignation et pour la mémoire formant pile de géniteurs, avec les conséquences qui en découlent pour la représentation de l'état de la machine; - l'annexe 3 illustre le fonctionnement du processeur d'exe- cution, et du jeu de commandes de base incorporé à celui-ci, à l'aide d'exemples ; et - l'annexe 4 illustre les synchronisations entre les deux processeurs, ainsI que le fonctionnement du processeur de gestion de mémoire, à l'aide d'exemples et de diagrammesO Les figures relevant des annexes sont asoucees comme figures 6 à 27, aux figures 1 à 5 associées à la présente description Le contenu de l'ensemble des documents annexes, y compris les dessins, est constitué pour l'essentiel d'informations dé caractère certain. A ce titre, il est incorporé à la présente description, pour contribuer avec cellesci à la définition de l'invention.
Par ailleurs, il a été nécessaire d'utiliser, en particulier dans les annexes, des graphismes particuliers destinés à préserver la cohérence et la clarté des explications données, compte tenu de l'intervention d'un nombre important de"mots réservés" (ce qui s'entend également de groupes verbaux).
Lorsque cela est nécessaire pour une bonne compréhension, les mots réservés sont écrits entre apostrophes ('), dans le reste de la description et dans les revendications.
Il est maintenant fait référence à la figure 1. Celle-ci montre que la machine selon l'invention possède les dispositifs suivants -une mémoire des cellules 14, utilisée essentiellement pour la représentation des termes. Cette mémoire, de grande capacité, peut être construite à l'aide de circuits 4164 de la Société Intel Corp. Ce sont des mémoires à temps d'accès moyennement rapide, typiquement 150 nanosecondes.
- un processeur d'exécution 10, qui réalise les instructions de base de la machine, à savoir la construction et l'accès aux termes conservés dans la mémoire des cellules. Il comporte un organe programmable, ou plus précisément microprogrammable, 16, qui permet de définir diverses utilisations de la machine, comme un interpréteur du langage PROLOG. Ce processeur peut être construit à l'aide des circuits de la famille 2900 de la société Advanced Micro Devices. Cette famille de circuits permet de constuire par tranches" des processeursmicroprogrammables dont la fréquence de l'horloge de base est motennement rapide, typiquement 150 nanosecondes.
- un processeur de gestion de mémoire 12, qui réalise essentiellement le mécanisme de récupération de mémoire, et aussi l'allocation de cellules de mémoire libre sur requête du processeur d'exécution. Le processeur de gestion de mémoire fonctionne en parallèle avec le processeur d'exécution. Il peut également être construit à l'aide des circuits de la famille 2900 de Advanced Micro Ceïirns.
- une mémoire des statuts d'allocation 15,- qui conserve l'information nécessaire au processeur de gestion de mémoire.
Dans l'exemple détaillé décrit, cette mémoire comporte autant d'éléments que la mémoire de cellules. Mais les éléments de la mémoire des statuts d'allocation ont une largeur limitée à deux bits. Cette mémoire est construite en technologie rapide, par exemple à l'aide de boîtiers Am 9128-10 de la Société AMD (temps d'accès de l'ordre de 100 ns), - un bus mémoire 13 qui réalise et arbitre les accès concurrentiels à la mémoire des cellules de la part du processeur d'exécution et du processeur de gestion de mémoire e Le mécanisme d'arbitrage peut être classique, et réalisé à partir de circuits existant sur le marché, comme les circuits produits par la Société INTEL Corps pour la gestion de 1'arbi- trage de son bus MULTIBUS.
Ur 3organe de communication et de synchronisation ou bus de rr-quetes lle qui assure entre les aeuat processeurs l'échange d'informations et la synchronisation macroscopique ayant trait à la gestion de mémoire. Cela se produit essentielle- ment par requête et acquittement de requête, ou mise en attend te de celle-ci. Le bus de requêtes ll peut consister en des liaisons entre les processeurs mentionnés plus haut, qui possèdent des moyens d'intercommunication entre processeurs.
La mémoire des cellules 14 constitue les moyens de mémoire vive précitée. Elle pourrait être réalisée en deux parties physiquement séparées, éventuellement de structure différente, correspondant respectivement à la mémoire de désignation et à la mémoire formant pile de géniteurs, telles que définies plus haut. Il est préféré que cette mémoire de cellules comporte une structure unique, à partir de cellules élémentaires de taille identique, permettant aussi bien la réalisation de la mémoire de désignation que celle de la mémoire formant pile de géniteurs. Il sera indiqué plus loin comment ceci est réalisé. Dans ce cas, la mémoire des statuts d'allocation comporte des éléments qui correspondent non seulement à la mémoire de désignation, mais aussi à la mémoire formant pile de géniteurs.Une variante de l'invention consisterait à ne prévoir, dans cette mémoire des statuts d'allocation, que des éléments en nombre limité à celui des cellules de la mémoire de désignation.
Il sera utile de se référer maintenant à l'Annexe 1, afin d'acquérir les notions de base et définitions utiles à la compréhension de l'invention. L'Annexe 1 précise aussi l'état de la machine, et les caractéristiques abstraites du jeu de commandes de base de son processeur d'exécution, avec là encore les définitions nécessaires.
L'annexe 2 définit plus en détail la structure de la mémoire des cellules, d'abord pour la mémoire de désignation, puis pour la mémoire formant pile de géniteurs. S'y trouve également définie la notion de confJguration cohérente dans la mémoire de représentation. Cette notion de cohérence est ensuite étendue après intervention de la mémoire formant pile de géniteurs. Enfin est défini l'état de la machine, avec le registre d'affectation permanente que comporte le processeur d'exécution, la représentation de l'état de la machine par le contenu de ce registre, et par le contenu de la mémoire des cellules. Est alors brièvement notée la concordance entre la réalisation ainsi définie de la machine proposée et la spécification qui en est faite dans l'Annexe 1.
L'agencement de la mémoire de cellules selon ce qui est proposé en Annexe 2 est considéré comme accessible à l'homme de l'art, sur la base des enseignements donnés. Il en est de meme pour le registre incorporé au processeur d'exécution.
Les langages de programmation logique, telsPROLOG, ont été jusqu'à présent expérimentés sous une forme purement logicielle, dans laquelle un programme spécial est implanté dans une machine de traitement de l'information de type traditionnel. Sans relever ici les problèmes et imperfections apparus lors de ces expérimentations, il convient de noter qu'une telle mise en oeuvre purement logicielle est peu efficace, au sens du rendement et de la vitesse de travail.
La présente invention a essentiellement pour objet d'aboutir au développement industriel d'une machine spécialisée, capable de supporter efficacement la mise en oeuvre, par une programmation plus simple, des langages de programmation logique.
L'un des buts de l'invention est de dégager une structure de mémoire, ainsi qu'un processeur d'exécution, munie d'un jeu de commandes pour la faire évoluer, l'ensemble présentant un intérêt général pour la rédaction d'interpréteurs de langages de programmation logique. Ceux-ci seront contenus dans un organe programmable du processeur d'exécution. Il ne s'agit pas, cependant, de définir un logiciel qui réalise rait directement l'interprétation d'un langage de programmation logique particulier (dont PROLOG est un exemple).
Il convient de noter que, dans le présent texte, ce qu'on appelle "l'utilisateur" n'est pas directement un utilisateur humain, mais un programme particulier destiné à se dérouler dans l'organe programmable, et qui émettra des commandes appartenant au jeu de commandes précité.
Un autre but important de l'invention est de fournir, dans une telle machine, un mécanisme permanent, automatique et optimal de récupération de tout élément de mémoire qui ne participe pas à la représentation de l'information accessible à l'uti- lisateur.
De manière connue, la machine de traitement de l'information proposée comprend des moyens de traitement et des moyens de mémoire vive interconnectée par un bus.
Selon un premier aspect général de l'invention, cette machine est remarquable : - en ce que les moyens de mémoire vive comprennent une mémoire formant pile de géniteurs, ordonnée en fonction d'un nombre entier ou niveau, et une mémoire de désignation, constituée de cellules adressables individuellement, à deux champs au moins chacune, chaque champ étant destiné à contenir une information qui est soit un atome ou donnée, soit une référence à une autre cellule, soit une référence à l'un des géniteurs, - un géniteur constituant le point de départ d'un treillis de termes, en contenant lui-meme l'une au moins desdites informations, le treillis de termes pouvant se prolonger par des références successives entre cellules de la mémoire de dés i- gnation, - les cellules ainsi référencées étant soit de type constructeur, leurs champs contenant alors immédiatement chacun l'une desdites informations, soit de type variable, étant mises en attente d'une liaison ultérieure, lors de laquelle les deux champs d'une cellule serviront l'un à associer la variable à l'un des géniteurs, et l'autre à contenir l'une desdites informations, et - en ce que les moyens de traitement comprennent un processeur d'exécution microprogrammé, susceptible d'être associé directement ou indirectement à un organe programmable destiné à recevoir le logiciel d'interprétation, ce processeur d'exécution comprenant en outre un registre de géniteur courant, qui fait référence à l'un des géniteurs de la mémoire formant pile, l'état courant de la machine étant ainsi défini par le contenu de ce registre ainsi que par le contenu de la mémoire de désignation et de la mémoire formant pile de géniteurs.
Une définition plus détaillée du jeu de commandes de base suivant lequel le processeur d'exécution est microprogrammé sera donnée plus loin. Il sera également indiqué plus loin comment peuvent être structurées d'une part la mémoire de désignation, d'autre part la mémoire formant pile de géniteurs Un avantage de l'invention réside en ce que ces deux parties des moyens de mémoire vive peuvent être construites à partir de cellules de taille identique, comprenant dans un exemple préférentiel deux parties de vingt-quatre bits chacune, séparables chacune à leur tour en un champ de quatre bits et un champ de vingt bits.
Selon un autre aspect de l'invention, les moyens de traitement sont aussi agencés pour d'une part répondre à des demandes d'allocation de cellules de mémoire, en allouant des cellules de mémoire disponibles et, d'autre part, répondre à une deman de spécifique en effectuant une récupération automatique des cellules contenant des informations devenues inutiles.
En pratique, ceci peut être réalisé à laide d'un processeur de gestion de mémoire séparé qui dialogue par requêtes avec le processeur d'exécution à travers un organe de communication et de synchronisation.
Pour son fonctionnement, il est utile que le processeur de gestion de mémoire comprenne un certain nombre de registres affectés en permanence à des tâches particulières. Ces registres seront indiqués plus loin. Il est encore souhaitable de prévoir un mécanisme de verrou entre les deux processeurs, ce qui leur permet une exclusion mutuelle pour l'accès aux moyens de mémoire qu'ils partagent.
Selon un autre aspect de liinvention, le processeur de ges tion de mémoire, (séparé ou non),efectue la recupération auto mastique de la manière suivante - exploration d'une partie au moins des treillis de cellules définis par le contenu des moyens de mémoire vive, et utiles par le processeur d'exécution3 en y marquant les cellules en fonction de conditions prédé- terminées, et - ensuite, ramassage des cellules non marquées, qui sont maintenant considérées comme libres.
Selon un autre aspect particulièrement intéressant de l'invention, une mémoire de statuts d'allocation est associée au processeur de gestion de mémoire. Cette mémoire de statuts d'allocation comprend un nombre d'éléments au moins égal à celui des cellules de la mémoire de désignation, de préférence autant d'éléments qu'il y a de cellules en tout dans les moyens de mémoire vive.
Chacun de ces éléments de la mémoire de statuts d'allocation est susceptible d'états différents comprenant l'état libre, et un état marqué au moins. De préférence, au lieu d'un état marqué, on prévoit un premier et un second état non libres, définissant respectivement l'affectation de la cellule correspondante des moyens de mémoire vive dans une première et une seconde fournée.
Le processeur de gestion de mémoire effectue alors le marquage des cellules de la mémoire vive par une inscription dans l'élément correspondant de la mémoire de statuts d'allocation.
Le ramassage peut alors consister simplement en une exploration complète de cette mémoire de statuts d'allocation, tout en faisant passer ces éléments non marqués à l'état libre.
Il est suivi du mécanisme de ramassage 500 illustré sur la figure 5.
Ce mécanisme recombine deux éléments qui sont séparés dans l'annexe 4. L'un, le ramassage proprement dit, est décrit à la page 7 de l'annexe 4, tandis que l'autre, la 'révisionstatut-cellule' est décrit à la page il de l'annexe 4.
Ce ramassage consiste en une exploration de l'ensemble des cellules de la mémoire des statuts d'allocation, avec un indice i qui va explorer toutes les adresses possibles danscette mémoire (de même que dans la mémoire de désignation).
A l'étape 501, lFindice i est initialement mise zéro. Le test 503 détermine ensuite si i a atteint l'adresse maximale possible en mémoire. Si oui, c'est la fin en 504.
Sinon, l'étape 505 réalise une invalidation, des requêtes.
Le test 507 détermine alors si le-statut d'allocation de la cellule d'adresse i est la marque de la fournée précédente. Si oui, on met cette cellule à 'disponible', à l'étape 509.
A ce niveau intervient un perfectionnement de l'invention, qui consiste à allouer immédiatement la cellule qui vient d'être libérée. Pour cela, le test 511 détermine s'il y a attente d'une allocation de cellule. Si oui, l'étape 513 alloue immédiatement la cellule qui vient d'être libérée et acquitte la requête correspondante.
Dans tous les autres cas, y compris celui où la sortie du test 507 était non, on passe à l'étape 515, consistant à revalider les requêtes, et suivie d'une étape 517 incrémentant l'indice i d'une unité. On boucle alors sur l'étape 503, jusqu'à exploration de toutes les adresses de mémoire.
Intervenant uniquement sur le contenu de la mémoire de statuts d'allocation, le mécanisme 500 se déroulera de façon tros rapide, puisqu'il s'agit d'une mémoire rapide dont chaque élément ne possède que deux bits.
Après tout cela, le processeur de gestion de mémoire se place en situation d'attente de fournée, jusqu'à nouvelle exécution du mécanisme de récupération.
On notera maintenant qu'avec ces deux bits par élément, la mémoire de statuts d'allocation 15 possède un quatrième état, non encore utilisé jusqu'à présent. Ce quatrième état peut servir à soustraire certaines cellules de la mémoire 14 à l'action de récupération du processeur de gestion de mémoire 12. Cela est utile notamment si l'on désire stocker des informations de programme du processeur d'exécution 10 dans cette mémoire. Dans la variante simplifiée où la récupération de cellules ne se fait que dans la partie mémoire de désignation de la mémoire 14, les cellules définissant la pile des géniteurs sont alors mises elles aussi dans ce quatrième état, de façon à échapper à la récupération et au nettoyage qui sont effectués périodiquement par le processeur de gestion de mémoire 12.
Seul le processeur d'exécution 10 peut alors libérer ces cellules, sur une requête explicite à cet effet, qui s'adresse au processeur de gestion de mémoire 12.
Dans ce-qui précède, le mécanisme de récupération de mémoire est mis en fonction par la commande 'réduire1. Il est avantageux,comme cela est décrit dans l'annexe 4, qu'il soit également initié par l'instruction 'reprendre'.
A la fin de l'annexe 4 se trouve encore décrit le détail des synchronisations par requête intervenant dans le mode de réalisation à deux processeurs de la présente invention.
De cette manière, avec un processeur d'exécution et un processeur de gestion de mémoire susoeptibles de fonctionner de manière totalement parallèle, on assure que la gestion de mémoire s'effectue non seulement de manière optimale, mais aussi de manière très rapide.
Une variante de l'invention consisterait à utiliser un seul processeur qui fut spécialement microprogrammé, et ce processeur constituerait à lui seul les moyens de traitement de l'invention. Il n'y a bien sûr plus de problèmes d'intercommunication comme précédemment. En revanche, ce processeur microprogrammé unique devra fonctionner en temps partagé, d'une part pour l'exécution, d'autre part pour la gestion de mémoire. Le Demandeur estime qu'il conviendra alors d'implanter le logiciel d'interprétation (prolog ou autre) dans un processeur classique, séparé, qui sera connecté de manière habituelle au processeur unique microprogrammé constituant à lui seul les moyens de traitement.
Le processeur d'exécution possède tout d'abord un mécanisme dé "traversée des liaisons". La réalisation de ce mécanisme est là encore considérée comme accessible à l'homme de l'art, sans qu'il soit nécessaire d'en donner une représentation algorithmique figurative. On note d'ailleurs qu'un tel mécanisme est réalisé sous forme logicielle dans les expérimen- tations d'interpréteùrs PROLOG qui ont été mentionnés plus haut. Le processeur d'exécution le réalise sous forme maté- rielle.
Suivent alors les commandes également implantées sous forme matérielle, c'est-à-dire microprogrammées, dans le processeur d'exdeution. Le mécanisme de chacune de ces commandes est exposé dans l'Annexe 3 Il est, dans la plupart des cas, accompagné d'un exemple associé. Sur la base des enseignements donnés a propos de ces mécanismes dans l'Annexe 3,il est considéré comme accessible à l'homme de l'art de construire le processeur d'exécoution équipé d'un tel jeu de commandes de base, à partir des circuits inté- grés cités plus haut.
Il est à noter que certaines de ces commandes sont appa- rentées à des instructions connues du langage LISP. Ainsi -'Construire'existe telle quelle dans LISP (CONS), -'accéder gauche' correspond à'CAR'de LISP, -'accéder droite'correspond à'CDR'de LISP, - les trois commandes de tests ont également leurs éoui- valents dans LISP, - il en est encore de meme pour l'instruction de 'comparaison'.
Les autres commandes proposées n'ont pas leur équivalent dans LISP, elles sont particulièrement adaptées à l'interprétation des langages relationnels et sont un des traits originaux de la machine.
Le fait que certaines commandes ici proposées aient pu être réalisées sous forme matérielle dans certaines machines, -"LISP Machine Progress Report", R. Greenblatt. memo 444AI, lab MIT Cambridge Mass, Aug. 1977 est à souligner. La réalisation des autres commandes, de type original, dont le mécanisme est exposé dans l'annexe 3, est microprogrammable de manière analogue.
Ont été décrits pour le moment la structure de la mémoire des cellules 14 et celle du processeur d'exécution 10, leur interconnexion étant réalisée à travers le bus 13. Muni du jeu d'instructions de base qui vient d'être défini, le processeur d'exécution 10 est apte à permettre l'interprétation directe de la plupart des langages de programmation logique, sinon tous, et en particulier de celui connu sous le nom de PROLOG. Ceci constitue un premier avantage important desla présente invention.
Il convient d'observer que la représentation concrète, dans la machine, du travail effectué par le processeur d'exécution comporte trois niveaux - un niveau d- qui s'intéresse uniquement au contenu de la mémoire de désignation. Voir à cet égard les définitions de 'd-terminal' ,- 'd-ultime' et 'd-représentation' dans l'annexe xe 2.
- un second niveau noté t-. Ce niveau concerne les rapports entre les désignations contenues dans la mémoire de désigna tion et les rangs dans la pile (on se rappellera que toute variable liée contenue dans. la mémoire de désignation fait référence à un géniteur rangé dans la pile). A cela correspondent les définitions 't-terminal', 't-ultime' et 't-représentation' de l'Annexe 2.
- Le troisième niveau, noté S-, intéresse le contenu de la mémoire-pile elle-meme. Il est explicité par les définitions 'S-ultime', 'S-correspondance' et'S-représentation' dans l'Annexe 2.
Ceci permettra de mieux comprendre les enseignements donnés sur l'état courant de la machine, à la fin de l'Annexe 2.
On s'attachera maintenant à une caractéristique essentielle de la présente invention, qui concerne la mise en oeuvre (o implementation) d'une récupération automatique, et opti - maie, des' éléments de mémoire qui contiennent des informations devenues inutiles au processeur d'exécution Le point de départ du mécanisme de récupération est l'instruction "réduire" déjà mentionnée.
La plupart des concepteurs de langages de traitement formel ont prévu, généralement sous forme logicielle implémentée par le processeur d'exécution, une gestion de mémoire tendant à récupérer les parties de mémoire devenues inutiles. Ainsi, le langage LISP connait List processing in réal time on serial computer", H. Baker, communication of the ACM, April 1978, Vol. 21 Num 4 Pour ce qui est du langage PROLOG, différentes propositions ont été faites pour récupérer de la mémoire notamment "A note on garbage collection in PROLOG interpreters" Mr. Bruynoeghe, Proceedings of the first International logic programming conference, Sept. 14-t7th 1982, Marseille, France".Aucune de ces propositions n'a donné entière satisfaction, notamment aucune proposition de récupération,en parallèle de l'interprétation,n'a été faite.
Le premier pas vers la solution selon l'invention consiste à prévoir un processeur séparé de gestion-de mémoire 12, qui dialogue par requêtes avec le processeur d'exécution, à travers l'organe de communication et de synchronisation schématisé en -il.
Sauf en cas d:invalidation des requêtes, comme on le verra plus loin, le processeur de gestion de mémoire 12 répond à une requête d'allocation de cellule de mémoire formulée par le processeur d'exécufion en allouant chaque fois à ce dernier une cellule de mémoire déterminée. Le processeur d'exécution 10 va donc ainsi disposer, de façon pratiquement permanente, des cellules de mémoire dont il a besoin pour ses opérations.
Pendant l'intervalle de temps qui-va s'écouler entre une opération "invalidation des requêtes" et l'opération ulté rieure "validation des requêtes", le processeur de gestion" de mémoire 12 va se trouver alors dans le "niveau requête" décrit aussitôt après le niveau de fond. Une requête émanant du processeur d'exécution 10 est alors différée, c'est-à dire qu'elle est mémorisée et qu'elle ne sera prise en compte que lorsque le processeur de gestion de mémoire repassera au niveau de fond.
En bref, le niveau de fond consiste donc en l'exécution par le processeur de gestion de mémoire des opérations qui lui sont propres, et que l'on examinera plus loin. En présence d'une'requête',ou bien d'une'invalidation des requêtes pour une autre raison, le processeur de qestion de mémoire atinterrompt pour passer au niveau requête". En cette situation, toute nouvelle requête émanant du processeur d'exécution est différée. Pendant le traitement d'une requête, la fin de requête" ramène le processeur de gestion.
La présente invention a pour objet un dispositif pour protéger l'une des surface d'un élément lenticulaire, en particulier d'une tranche de silicium, qui permette d'obvier aux inconvénients évoqués ci-dessus.