Brevet FR2325985A1 — publié le 19770422

La présente invention concerne une machine informatique électronique destinée à l'exécution parallèle d'un langage postfixé. On sait que les instructions post-fixées sont particulièrement intéressantes pour l'exécution des langages évolués. Ces instructions post-fixées présentent la caractéristique fondamentale de désigner uniquementsoitun opérande, soit un opérateur. Une expression sous forme post-fixée,appelée encore "polonaise"peutêtre ainsi décomposée en groupes opérandes-opérateurs adjacents. Dans les machines de traitement de l'information connues actuellement et utilisant des instructions post-fixées, une expression de ce genre est obligatoirement évaluée sur une pile. Si ce mécanisme présente l'avantage d'être simple à mettre en oeuvre, il ne permet toutefois aucune désynchronisation entre l'accès aux opérandes et l'exécution des opérations sur ces opérandes :on ne peut, en particulier, accéder aux opérandes d'un groupe i que si tous les opérateurs du groupe i - 1 ont été exécutés Autrement dit, l'emploi d'une pile interdit le parallèlisme, c'est-à-dire la simultanéité d'un accès aux opérandes et une exécution des opérateurs. Ces machines comportent généralement un processeur unique ayant accès à une mémoire de programme et à une mémoire de données. La présente invention vise essentiellement à remédier à cet inconvénient du non parallèlisme en procurant une machine d'une structure nouvelle permettant d'utiliser des instructions postfixées et de gagner un temps appréciable dans leur exécution. A cet effet, cette machine informatique électronique, destinée à l'exécution parallèle d'un langage post-fixé, comprenant au moins une mémoire destinée à contenir un programme de forme postfixée et des données, est caractérisée en ce qu'elle comporte trois processeurs indépendants, à savoir un processeur de contrôle, un processeur d'accès et un processeur d'exécution, et une file d'éva- adressables luation constituée par une mémoire à décalage ou / irculairement le processeur de contrôle ayant accès aux instructions du type postfixé du programme et les distribuant aux deux autres processeurs suivant la nature des instructions, le processeur d'accès ayant accès aux données du programme et les rangeant dans la file d'évaluation ou d'attente tandis que le processeur d'exécution extrait les données de la file d'attente, exécute les opérations arithmétiques et logiques sur les données et range les résultats dans la mémoire de données. On décrira ci-après, à titre d'exemple non limitatif, une forme d'exécution de la présente invention, en référence au dessin annexé qui est un schéma synoptique d'une machine exécutant en par lèle un langage post-fixé. La machine suivant l'invention comporte essentiellement une mémoire de programme 1, dans laquelle sont enregistrées les instructions du programme sous forme post-fixée, une mémoire des données 2, contenant les divers opérandes, et trois processeurs à savoir un processeur de contrôle 3, un processeur d'accès 4 et un processeur d'exécution 5. L'entrée du processeur de contrôle 3 est reliée à la mémoire de programme et ses sorties sont respectivement dirigées vers le processeur d'accès 4 et vers le processeur d'exécution 5, par l'intermédiaire de registres tampons 6 et 7.Le processeur de contrôle 3 effectue une sélection parmi les instructions du programme et il dirige d'une part les instructions d'accès aux opérandes, sous forme post-fixée, vers le registre tampon 6 qui est relié au processeur d'accès 4, et , d'autre part, les instructions opératives , sous forme post-fixée, vers l'autre registre tampon 7 qui est relié au processeur d'exécution 5. La machine suivant l'invention comporte également une file d'attente ou d'évaluation 8 à laquelle sont reliés les processeurs d'accès 4 et d'exécution 5. Le processeur d'accès 4 est connecté à la mémoire des donnéesipour en extraire les opérandes, tandis que le processeur d'exécution 5 est également relié à la mémoire des données 2 pour y enregistrer les résultats des diverses opérations. La machine suivant l'invention comporte également une file des affectations 9 dont le rôle sera précisé plus loin et qui est connectée au processeur d'accès 4 et au processeur d'exécution 5. La structure de la machine qui vient d'entre décrite permet une désynchronisation entre l'accès aux opérandes et l'exécution des opérations sur ces opérandes. Il existe donc un certain parallèlisme entre l'accès et l'exécution, autrement dit, le processeur d'accès 4 peut ranger dans la file d'évaluation 8 les opérandes tandis que le processeur d'exécution 5 effectue une évaluation proprement dite. Pour mieux faire comprendre le fonctionnement de la machine, on considèrera, à titre d'exemple, l'exécution de l'expression A ( > 1 ( 4 x D+E) qui s'écrit en notation post-fixée ou polonaise A, B, C, +, 4, D, f, E, +, ZI /, soit trois groupes (ABC+) (4du) (E+t/) Les instructions post-fixées sont extraites de la mémoire de programme 1 par le processeur de contrôle 3 qui range les instructions d'accès aux opérandes (ABC4DE) dans le registre tampon 6 et les instructions d'opérateur (+, *, +, *, /) dans l'autre registre tampon 7.Le processeur d'accès 4 range alors, sous la commande des instructions d'accès aux opérandes contenues dans le registre tampon 6, les divers opérandes dans la file d'évaluation 8, selon leur ordre d'apparition dans la chaîne post-fixée. L'évaluation proprement dite est faite par le processeur d'exécution 5. Ce dernier extrait de la file 8 les opérandes nécessaires, exécute l'opé- ration prévue, et range le résultat dans la case qu'occupait le second opérande (une file devant se vider par le bas), celle qui était occupée par le premier devenant vide. Chaque opérateur crée ainsi un "trou" dans la file. Dans le cas de l'exemple précité, on peut avoir, en supposant des temps d'accès et d'exécution identiques, les images successives de la file suivante A tO : les accès aux trois premiers opérandes ont été faits. A B+C 4 ti : parallèlement à l'exécution (+) le proces seur d'accès a rangé la valeur immédiate (4'. A 4 D t2 : rangement de D : aucune opération possible (*) n'a pas ses opérandes . - A A B+C 4D E t3 : exécution de (*) rangement de E, A B+C t4 : exécution de (+# accès éventuel au premier opérande de l'expression suivante. a i A #II t5 : exécution de (+' accès éventuel à l'opé- rande suivant Ti t6 : exécution de (/# accès éventuel à l'opérande suivant. Dans 11 exemple décrit ci-dessus, il convient de remarquer qu'à l'instant t6 la file a été vidée par le bas : il n'y subsiste que le résultat de I'évaluation suivi des premiers opérandes de l'expression suivante. Ce résultat est alors rangé par le processeur d'exécution 5 dans la mémoire de données 2. L'instant t2 met en évidence une limitation au parallé- lisme : en effet, pour que l'exécution d'un opérateur d'un groupe soit possible, il faut que tous les opérandes de ce groupe aient été préalablement rangés dans la file 8. Par ailleurs, si on considère un opérateur quelconque d'un groupe, il trouve son deuxième opérande dans la case dans laquelle le processeur d'accès 4 a rangé le dernier opérande du groupe et son premier opérande dans la première case non vide, en aval de celle-ci. Dans la machine suivant l'invention, qui utilise la file d'attente ou d'évaluation 8, la position des opérandes sur lesquels doit agir un opérateur donné n'est pas évidente, surtout du fait de la désynchronisation entre l'accès et l'exécution. Il a donc été nécessaire de définir deux pointeurs 01 et 02 donnant au processeur d'exécution 5 l'adresse des opérandes nécessaires à I'éva- luation du résultat de chaque opérateur. Pendant l'exécution des opérateurs appartenant à un même groupe, le pointeur 02 ne bouge pas et pointe sur le dernier opérande du groupe rangé par le processeur d'accès. Avant l'exécution du premier opérateur d'un groupe, il faut le réinitialiser en le faisant avancer d'un nombre de cases égal au nombre d'opérandes du groupe : ainsi il donnera l'adresse du deuxième opérande nécessaire à l'évaluation de tous les opérateurs du groupe. L'autre pointeur 01 doit donner l'adresse de la première case non vide en aval de 02. Pour le premier opérateur- d'un groupe c'est nécessairement la case d'adresse 02 - I. Donc le fait de faire avancer 02 implique 01 := 02 - I. Après l'exécution d'une opération, la case pointée par 01 devient vide et 01 doit aller chercher la première case occupée en aval pour qu'elle serve d'opérande à l'opérateur suivant. En général, cette case est celle d'adresse On - 1. On décrémente donc systématiquement 01 après l'exécution d'une opération. Si 01 pointe alors sur un trou il faut le faire reculer jusqu'à ce qu'il donne l'adresse de la première case non vide en aval. La mise en position des pointeurs 01 et 02 est déterminée dans une phase d'analyse de la chaine post-fixée par le processeur de contrôle 3.Ce dernier a accès, comme on l'a vu, aux instructions du programme et ce, séquentiellement, et il aiguille les instructions d'accès vers le processeur d'accès 4 et les instructions opératives vers le processeur d'exécution 5. Le processeur de contrôle 3 donne également au processeur d'exécution 5 des ordres de gestion des pointeurs 01 et 02. On décrira maintenant le rôle de la file des affectations 9, qui est reliée aux processeurs d'accès 4 et d'exécution 5. Si on évalue le résultat d'une expression, c'est en général pour l'affecter à une variable. Par exemple X: = #expression > se traduit par : La désynchronisation entre les deux processeurs 4 et 5 peut amener une ambiguïté. En effet, soit par exemple deux expres sions à évaluer : I := J : = 2; on supposera que utilise la variable I. Si le processeur d'accès 4 range dans la file la valeur de I pour l'évaluation de la deuxième expression, avant que l'affectation I:= 'ait été exécutée, le résultat deux 2)sera erroné. On dit qu'il y a alors dépendance sur la valeur de I tant que l'affectation n'a pas été faite. I1 faut donc empecher le processeur d'accès 4 de ranger dans la file d'évaluation 8 la valeur d'une variable sous dépendance. C'est à cette fin qu'est utilisée la file des affectations 9. Pour toute instruction du type AFFECT X, le processeur d'accès 4 construit dans la file d'évaluation 8 un descripteur de dépendance, range le nom de la variable X dans la file des affectations 9 et détermine la position du descripteur de dépendance dans la file d'évaluation 8. Ensuite, lors de toute apparition du nom d'un opérande (par exemple X ), le processeur d'accès 4 cherche de manière assez ciative dans la file des affectations si ce nom existe. Si le nom X n'existe pas, le processeur d'accès 4 va chercher l'opérande en mémoire centrale et le range dans la file d'évaluation. Par contre si le nom existe, le processeur d'accès 4 range alors dans la file d'évaluation 8 un descripteur de dépendance qu'il doit chaîner à celui dont l'adresse se trouve dans l'élément trouvé dans la file des affectations 9, puis il modifie cette adresse de façon à pointer sur le dernier maillon de la chaine de reprise, Les dépendances sur une variable sont résolues par le processeur d'exécution 5 au moment de l'affectation. Quand celui-ci décode une instruction AFFECT X, son pointeur 02 donne l'adresse dans la file d'évaluation de la nouvelle valeur de la variable dont le nom est donné par le premier élément de la file des affectations 9. Après avoir rangé en mémoire centrale 2 la nouvelle valeur de variable, il remplace tous les descripteurs de dépendance chainés à partir de la case d'adresse 02 + 1 (premier maillon de la chatne de reprise) résolvant ainsi toutes les dépendances sur cette variable. REVEND I CAT IONS 1.- Machine informatique électronique, destinée à l'exécution parallèle d'un langage post-fixé, comprenant au moins une mémoire destinée à contenir un programme de forme post-fixée et des données, caractérisée en ce qu'elle comporte trois processeurs indépendants, à savoir un processeur de contrôle ,un proces seur d'accès 4 et un processeur d'exécutipn 5, et une file d'éva- luation 8 constituée par une mémoire à décalage ou adressable efrcu- clairement le processeur de oentrôle 3 ayant accès aux instructions du type post fixé du programme et les distribuant aux deux autres processeurs suivant la nature des instructions, le processeur d'accès 4 ayant accès aux données du programme et les rangeant dans la file d'évaluation ou d'attente 8 tandis que le processeur d'exécution 5 extrait les données de la file d'attente, exécute les opérations arithmétiques et logiques sur les données et range les résultats dans la mémoire des données. 2.- Machine suivant la revendication 1, caractérisée en ce qu'elle comprend une file des affectations associative 9 couplée au processeur d'accès 4 et au processeur d'exécution 5, inter rogée par le processeur d'accès 4 et mise à jour par le processeur d'exécution