Brevet FR2500659A1 — publié le 19820827

"Dispositif pour l'allocation dynamique des taches d'un or- dinateur multiprocesseur." La présente invention concerne un dispositif de traitement de l'information capable de traiter un ou plu- sieurs programmes numérotés 0, 1,... j, n, chaque pro- gramme comprenant un ou plusieurs segments, ledit dispositif comportant au moins une mémoire contenant le ou les programmea susdits et au moins un processeur d'instructions, aussi appelé unité de traitement, lesdites instructions, que ledit processeur d'instructions sait traiter, comprenant entre autres une ou plusieurs instructions de branchement dites du premier type lorsque le branchement à effectuer conduit à une adresse contenue dans le même segment que le segment en cours de traitement d'une part, et, une ou plusieurs instructions de branchement dites du deuxième type lorsque le branchement à *effectuer conduit à une adresse contenue dans un autre segment que le segment en cours de traitement d'autre part. Ledit dispositif de traitement, aussi appelé ordinateur est aujourd'hui bien connu, son fonctionnement est géré par un système d'exploitation. C'est un produit de l'industrie informatique. Parmi les ordinateurs connus, une première catégorie ne comporte qu'un seul-processeur d'instructions; s'il traite plusieurs programmes, cas de la multiprogram- mation, ceux-ci sont traités de front, exécution imbriquée, la règle d'imbrication est définie par un algorithme-de répartition du temps de traitement du processeur d'instruc- tions, ledit algorithme étant basé par exemple sur des priorités de traitement affectées à chaque programme par l'utilisateur, priorité externe, ou par le système d'exploi- tation, priorité interne, ou bien encore étant basé sur des - tranches de temps affectées successivement au traitement des différents programmes sans notidn de priorité, dans ce dernier cas l'ordinateur ou le processeur d'instructions comporte une horloge capable de générer une trappe ou inter- ruption d'horloge, qui indique au système d'exploitation qu'il faut maintenant traiter. un autre programme; il existe bien sur d'autres algorithmes et d'autres types de- trappe qui donnent plus ou moins satisfaction. Parmi les ordinateurs connus, une deuxième caté- gorie comporte plusieurs processeurs d'instructions numé- rotés 0, 1,... i,... m; dans ce cas l'algorithme de ré- partition du temps de traitement d'un processeur d'instruc- tions, dont nous venons de parler, a encore son rôle à jouer mais, préalablement, il faut procéder à l'affectation de chaque programme à traiter à l'un ou l'autre des processeurs d'instructions; à cet effet dans les ordinateurs connus, on utilise divers algorithmes faisant éventuellement appel à diverses trappes dans le but, d'une part, d'affecter un programme à un processeur d'instructions ou à un autre, étant entendu qu'il y a généralement plus de programmes à traiter 3 2500659 qu'il n'y a de processeurs d'instructions pour ce faire et, d'autre part, une fois cette affectation réalisée, de répar- tir le temps de traitement de chaque processeur entre les différents programmes qui lui ont été affectés. Les algo- rithmes d'affectation connus ont essentiellement deux carac- téristiques 1) ils sont le plus souvent statiques c'est-à-dire qu'un programme est attaché à un processeur jusqu'à la fin de son exécution. 2) quand ils sont dynamiques, le dynamisme est obtenu par logiciel, c'est-à-dire qu'aucun dispositif électronioue n'a été spécialement mis en place pour obtenir ce dynamisme. Un dispositif électronique permettant l'affectation dynamique est particulièrement souhaitable lorsque l'archi- tecte de l'ordinateur a choisi de découper la mémoire dis- ponible en un certain nombre de tranches de mémoire d'égales ou d'inégales longueurs et que chaque processeur d'instruc- tion dispose,d'une part d'un accès privilégié via un bus local à -l'une dés dites tranches de mémoire et, d'autre part, d'un accès banalisé via le bus standard à toutes les autres tranches de mémoire. Il est alors très performant d'affecter le traitement d'un programme à celui des processeurs qui a un accès privilégié à la tranche de mémoire o se trouve mémorisé l'instruction en cours du programme en question; en effet dans ce cas étant donné que ladite architecture est définie une fois pour toutes pour-une machine déterminée, un programme peut très bien se trouver chargé dans plusieurs tranches de mémoires, les dites tranches de mémoire étant rattachées par des bus locaux à différents processeurs, il faut alors pour rester performant pouvoir changer l'af- fectation d'un programme d'un processeur à un autre au fur et à mesure de l'exécution de ce programme; il est évi- dent qu'un algorithme d'affectation statique ne peut satis- faire cette exigence; dans les machines connues divers dispositifs coopérant avec divers algorithmes permettent plus ou moins de satisfaire les objectifs de l'utilisateur. Le dispositif conforme à!'invention a pour but de générer une trappe dite "trappe de changement de portion" qui permet la mise en oeuvre d'un algorithme dynamique d'affectation des programmes. Il s'agit ici non seulement de programmes à traiter mais encore et surtout de program- mes en cours de traitement. La coopération entre le dis- positif et l'algorithme permettra d'obtenir une utilisation optimale des possibilités voulues par l'architecte puisqu'il ne s'agit plus seulement d'effectuer une affectation sta- tique des programmes à traiter mais qu'il s'agit, grâce à un dispositif électronique conforme à l'invention, de pro- voquer au bon moment l'interruption du programme en cours pour changer, dynamiquement et efficacement, son affecta- tion d'un processeur à un autre. En effet selon la présente invention, un dispo- sitif de traitement de l'information est notamment remar- quable en ce que, l'utilisateur ayant affecté à chaque seg- ment de chaque programme un numéro de portion, chaque por- tion étant numérotée 0, 1,... k,... p, et chaque portion pouvant contenir un ou plusieurs segments, ledit dispositif e comporte des moyens pour générer une trappe dite "trappe de changement de portion", ladite trappe étant mise en oeuvre par les dits moyens lors de l'exécution d'une ins- truction de branchement du deuxième type, ladite instruction se trouvant dans un segment affecté du numéro de portion "k" lorsque l'adresse de branchement à laquelle elle conduit se trouve dans un segment affecté du numéro de portion "1", "1" étant différent de "k". Un avantage qui découle du dispositif, objet de l'invention, est que, par exemple dans le cas d'un multi- processeur, fonctionnant en multitraitement et en multi- programmation, au moment o se produit la trappe de chan- gement de portion du processeur d'instructions "i", par exemple en train de traiter la portion "k" du programme "j", l'on peut analyser la situation et décider, qu'à partir de l'exécution dans le programme "j" de l'instruction de bran- chement qui conduit de la portion "k" à la portion "1", exécution qui a provoqué ladite trappe de changement de portion, il y a lieu de changer l'affectation du programme "j" pour que son traitement se poursuive plus efficacement avec le processeur d'instructions qui a un accès privilégié via son bus local, à la tranche de mémoire qui contient la portion "l". Il faut préciser que ce dispositif de trappe de changement de portion ne fonctionnera de façon satisfaisante que si la distribution géographique dans la mémoire du code des programmes à exécuter est effectuée de telle sorte que les segments d'un même programme affectés d'un même numéro de portion ne sont pas chargés dans des tranches de mémoire différentes. A partir du moment o un segment de la portion "k" aura été chargé dans une tranche de mémoire, les autres segments de la même portion "k" devront, le moment venu, être chargé dans la même tranche de mémoire: la portion doit être le quantum de distribution du code dans les tran- ches de mémoire pour pouvoir profiter pleinement du dispo- sitif selon l'invention. La coopération entre le dispositif objet de l'invention dite "trappe de changement de portion", ladite architecture et le système d'exploitation est particuliè- rement remarquable par les performances que l'on peut en attendre et par la souplesse de son utilisation: - la notion de portion peut être ignorée au moment de l'écri- ture du programme source; elle ne complique donc pas la tâche du programmeur. - la portabilité d'un programme d'une machine complexe sur une machine simple ne pose pas de problème particulier car on peut très bien concevoir que le système d'exploitation de la machine simple va purement et simplement ignorer la notion de portion. On peut dire que la notion de portion peut être complètement transparente tant pour la machine' que pour le programmeur si l'utilisateur ne souhaite pas faire usage des nouvelles possibilités qu'elle offre. Cette transparence est un avantage dans le cas o un même programme doit pouvoir être traité soit par un monoprocesseur, soit par un multi- processeur. Le dispositif selon l'invention est avantageu- sement réalisé lorsque le système d'exploitation a mémori- sé le numéro "k" de la portion en cours de traitement dans le contexte de l'ordinateur et lorsque cette mémorisation est mise à jour au fur et à mesure de l'exécution du pro- gramme à l'occasion de chaque changement de portion, par exemple, lors de l'exécution d'instructions de branchement du deuxième type si le segment cible n'a pas le même numéro de portion que le segment origine; on peut alors distinguer trois numéros de portion interessant le dispositif de trappe de changement de portion - le numéro de portion en cours de traitement. - le numéro de portion mémorisé dans le contexte. - le numéro de la portion cible. Dans le cas général, les deux premiers de ces trois numéros de portion seront identiques; mais dans un mode préféré de réalisation de l'invention, le dispositif ne générera pas de trappe de changement de portion pour une ou plusieurs portions privilégiées et ceci tant à l'aller qu'au retour; en effet dans le cas, par exemple, de sous- routine de service fréquemment utilisées, il peut être globalement plus performant de ne pas générer la dite trappe de changement de portion; à cet effet, le système d'exploi- tation ne modifiera pas le numéro de portion mémorisé dans le contexte lors de l'exécution par exemple d'une sous-rou- tine de service située dans une portion privilégiée de telle sorte que le dispositif de trappe ne fonctionne ni à l'aller car la portion cible a un numéro privilégié, ni au retour car la portion cible aura le même numéro que le numéro de portion mémorisé dans le contexte qui n'aura pas été modifié par le système d'exploitation. Il convient de souligner ici la différence entre la présente invention dite "trappe de changement de portion" et un dispositif déjà bien connu que l'çn peut appeler "trappe de segment non chargé en mémoire";la "trappe de segment non chargé en mémoire" est actionnée lorsqu'une instruction de branchement du deuxième type mène à un seg- ment qui n'est pas présent en mémoire, il faut donc déclen- cher une opération de chargement du segment manquant, ce qui implique peut-être le déchargement d'un autre segment d'o la mise en oeuvre d'un algorithme de remplacement des segments par exemple: LRU ou FIFO; par contre la "trappe de changement de portion" est actionnée lors d'un change- ment de portion, même si le segment cible, dans lequel on désire exécuter la prochaine instruction, est-présent en mémoire. Nous allons maintenant décrire un mode de réali- sation d'un dispositif conforme à l'invention; pour faci- liter la compréhension, nous nous appuierons sur les figures suivantes Figure 1. Architecture générale d'un multi- processeur. Figure 2. Architecture particulière d'un processeur. Figure 3. Schéma du dispositif de trappe - Cycle Exec. 9 2500659 Figure 4. Schéma du dispositif de trappe - Cycle d'extraction ou Cycle Fetch. Figure 4a - Variante du schéma de la figure4. La figure 1 montre l'architecture générale d'une machine multiprocesseur avec en particulier les processeurs Pi et Px, reliés au bus standard. La mémoire M connectée au bus standard via BSM est découpée en tranche dont en particulier la tranche Mi qui est accoédée d'une manière privilégiée via le bus local BLi par le processeur Pi, et la tranche Mx qui est accédée d'une manière privilégiée via le bus local BLx par le pro- cesseur Px; chaque processeur peut traiter consécutivement les instructions d'un programme quelconque se trouvant char- gé n'importe o dans la mémoire, dans la mesure o l'algori- thme d'affectation lui en a confié le traitement.; l'al- gorithme d'affectation est lui-même un programme dont le traitement est confié par exemple au processeur PI qui a, de ce fai't, un rôle privilégié de processeur central, mais le mode de fonctionnement de Pi n'a pas d'incidence'sur le dispositif selon l'invention, c'est pourquoi il n'est pas décrit plus en détail. Nous noterons seulement que l'algo- rithme construit, pour chaque processeur, une file d'attente des programmes qui lui sont affectés, chaque élément de chaque file d'attente comportant les indications nécessaires et suffisantes pour que le processeur puisse démarrer l'exé- cution du programme, par exemple, NI du programmeladresse de l'instruction de départ, valeur initiale d'un certain nombre de registres; ces divers éléments sont évidemment variables d'une machine à l'autre et leur description détaillée n'a pas d'intérêt ici car ils sont bien connus ajoutons seulement que les instructions chargées dans la tranche de mémoire Mi sont traitées d'une manière plus performante par le processeur Pi qui peut travailler via son bus local BLi alors que tous les autres processeurs seront plus lents à traiter les mêmes instructions car ils devront passer par le BSM et le bus standard qui sera, de ce fait, plus encombré ce qui n'est pas souhaitable car bien d'autres dispositifs (AD), ici non décrits, sont con- nectés sur le bus standard: périphériques, controleurs, lignes, terminaux,... La figure 2 représente l'architecture d'un des processeurs; dans l'exemple représenté et décrit, qui correspond à l'état actuel de la technique, un processeur est essentiellement composé de deux puces microprogrammées interconnectées, l'une LSI1 comporte plus spécialement la structure de traitement *des instructions, l'autre LS12 comporte plus spécialement la structure de translation d'adresse; LSII comporte en particulier un registre d'ins- truction RI dans lequel est stockée l'instruction en cours avec ses deux parties: code opération (COP) et l'opé- rande (OP), LSI1 comporte aussi une bascule.TCP et un registre Dl et LSI2 comporte un registre RT, dont nous ver- rons tout à l'heure le mode de fonctionnement. Les figures 3 et 4 décrivent un exemple de réalisation d'un dispositif.de trappe de changement de portion conforme à l'invention. Pour faciliter la compréhension du dispositif, nous allons d'abord nous reporter à la figure 1 et dé- crire la situation à l'instant te, l'instruction en cours du processeur Pi se trouve à l'adresse Al, code opération COP; cette instruction appartient au programme "j"; le programme "j", qui était dans la file d'attente du processeur "i" par suite d'une affectation antérieurement effectuée par l'algorithme d'af- fectation a été sélecté per le processeur "i" et est en cours d'exécution A l'instant tA;.le programme "j" est constitué, par exemple, de trois segments Sl,.S2, S3; SI et 52 ont été mis dans la même portion "k" alors que S3 se trouve dans la portion "1"; la portion "k" a été chargée dans la tranche de mémoire Mli, la portion "1" a été chargée dans la tranche de mémoire Mx; au moment td l'instruction - COP, code opération en cours indice c, située à l'adresse A1 est l'instruction en cours du processeur "i"'. Cette ins- truction se trouve donc dans le registre d'instruction Ri du LSI1 du processeur Pi et son code opération est alors analysé par les microprogrammes de sorte que les opérations des figures 3 et 4 sont alors effectuées; ces opérations sont des opérations logiques effectuées par des circuits logiques dont la description détaillée, combinaisons de portesOU,ET,NON-ET,NON-OU, etc, n'apporterait rien à la description de l'invention; tout homme de l'art est en effet capable de produire un dispositif selon l'invention à l'aide de la présente description. L'insruction COPc est donc analysée par le LSI1 du processeur Pi qui détecte -repère 10- que le code opé- ration de cette instruction est un branchement du deuxième type; cette détection provoque alors l'opération Il o la bascule TCP est positionnée à "1", et dans l'opération 12, qui consiste à charger l'adresse logique A2 du branchement désiré dans le compteur ordinal du processeur, A2 étant l'opérande de l'instruction, le numéro du segment cible, ici S3, est sauvegardé dans le registre temporaire RT; lors du cycle Fetch de l'instruction suivante à exécuter (adresse A2, COP,+4) le LSI2 de Pi doit traduire -opération 13- cette adresse logique en une adresse physique selon un des procédés connus de translation d'adresse. Il exécute ensuite un test de l'état de la bascule TCP -opération 14- qui,-en cas de jrponse positive, provoque la sauvegarde -opération 15- du numéro de la portion courante, ici "k", dans le registre d'entrée REl de l'unité arithmétique du LSI1 du processeur Pi; la translation de l'adresse A2 fournit le numéro de portion, ici 'il", contenant le segment S3 qui contient l'instruction COP,,, maintenant en début d'exécution, numéro de portion qui est sauvegardé dans le registre d'entrée RE2 de l'unité arithmétique du LSI1 -opé- ration 16-; il reste alors au LSII à tester si les contenus de RE1 et RE2 sont identiques -opération 17-; comme ce n'est pas le cas, puique 1i k, un certain nombre de sauvegardes sont effectuées -opération 19- et l'exécution du programme "ijl' est interrompue; à ce moment, d'une part le processeur Pi abandonne le programme lôl et exécute sa propre routine de sélection d'un autre programme parmi ceux situés dans sa propre file d'attente, d'autre part le processeur centrale celui qui traite l'algorithme d'affectation, dispose d'une tâche de plus dans sa propre file d'attente, tâche qui con- sistera à affecter à nouveau le programme "j" au processeur le mieux placé pour le traiter, ici normalement le proces- seur "x"; le processeur central effectuera cette tâche en fonction des priorités que l'utilisateur lui aura donné1 domaine connu et non décrit; de même le processeur "x", si c'est bien dans sa propre file d'attente que le program- me "I" a été affecté de nouveau, commencera l'exécution du programme "j" en fonction des priorités que l'utilisateur lui aura donné. Nous allons maintenant montrer une particularité de la "trappe de changement de portion" en supposant, ce qui normalement n'est pas favorable au rendement global, que le programme "j" comporte un autre segment S4 affecté du numéro de portion "1 + 1", la portion "1 + 1" étant chargée dans la tranche de mémoire Mx; si'le processeur Px traite le segment S3 du programme "j" et qu'il rencontre un bran- chement du deuxième type qui mène à l'adresse A3 dans le segment S4, conformément à l'invention la trappe de chan- gement de portion va fonctionner et le mécanisme décrit précédemment va se dérouler entièrement; comme l'algorithme d'affectation va sans doute affecter à nouveau à la file d'attente du processeur Px le programme "j", puisque S4 est chargé dans Mx, le bilan global de l'opération sera sûrement une perte d'efficience; l'utilisateur doit donc être atten- tif lorsqu'il attribue à chaque segment un numéro de portion; dans le cas présent il aurait été préférable que S3 et S4 aient le même numéro de portion. Nous allons maintenant décrire une autre parti- cularité de la "trappe de changement de portion" lorsque celle-ci n'est pas générée pour un ou plusieurs numéros de portions privilégiés. Un exemple avec un seul numéro privilégié, le numéro 0, suffira à faire comprendre l'in- térêt de ce mode de réalisation préféré. Admettons que les différents segments Si, S2, S3, S4, du programme "j" uti- lisent tous, et fréquemment, une routine de service, par exemple une routine de conversion ou une routine d'encryp- tage, et que cette routine de service se trouve dans un segment So que l'on peut appeler "segment racine" pour évoquer des types de routine de service bien connus de l'homme de l'art; admettons encore que le segment So soit dans la portion "0" privilégiée et que son chargement ait été effectué dans une tranche de mémoire My différente de Mi et Mx; si le déroulement de la-routine de service n'est pas trop long, il peut être préférable de ne pas générer de trappe de changement de portion ni à l'appel, ni au retour de la routine, bien que "0" soit différent de "1", "k" ou "l + 1", car la double exécution du processus décrit aux figures 3 et 4 l'aller et retour à la routine avec double changement de processeur, serait plus désavantageux que le faible encombrement du bus standard qui résultera du non- changement de processeur pour traiter cette routine; compte- tenu de ces considérations, un dispositif supplémentaire doit être prévu figure 4A- qui va inhiber la génération de la trappe si le numéro de; ortion cible est égal à un numéro privilégié, ici uniquement le numéro "0" dans notre descrip- tion d'un mode particulier de réalisation. La figure 4A diffère de la figure 4 en deux en- droits: d'une part pour ne pas générer de trappe lorsque l'on va de la portion "1" à la portion "0", le test 18 a été ajouté, si la portion cible a le numéro "O" la trappe n'est pas générée, d'autre part pour ne pas générer de trappe lorsque l'on revient de la portion "O" à la portion "1", l'opération 155 qui remplace l'opération 15 ne charge plus dans REI le numéro de portion courante, ici "O", mais le numéro de portion mémorisé par le système d'exploitation à une adresse PC qui fait partie du contexte de la machine bien évidemment, lors de l'appel de la sous- routine le système d'exploitation n'a pas effectué la mise à jour du contenu de l'adresse PC du contexte, mise à jour qui aurait- consisté à remplacer "l" par "0", ce qui fait que la valeur "1" est toujours mémorisée à l'adresse PC et le test 17 va donner une réponse positive 1=1 (RE1 = RE2) de telle sorte que la trappe ne sera pas générée au retour de la routine. REVENDICATIONS 1. Dispositif de traitement de l'information com- portant au moins un processeur (Pi) d'instructions, capa- ble d'exécuter un ou plusieurs programmes, chaque programme étant découpé en un ou plusieurs segments.(SlS2), lesdites instructions comprenant entre autres d'une part une ou des instructions de branchement dites du premier type lorsque le branchement à effectuer conduit à une instruction con- tenue dans le même segment que l'instruction de branchement qui-y mène, et d'autre part une ou des instructions de bran- chement dites du deuxième type (Al) lorsque le branchement à effectuer conduit à une instruction qui n'est pas contenue dans le même segment que l'instruction de branchement qui y mène, caractérisé en ce que, ayant affecté à chaque segment de chaque programme un numéro de portion (k), chaque portion pouvant contenir un ou- plusieurs segments d'un programme, il comporte des moyens pour générer une trappe dite "trappe de changement de portion" lorsque l'exécution d'une instruc- tion de branchement du deuxième type (AI), provoque un chan- gement de portion lors du passage de l'instruction en cours c'est-à-dire, ledit branchement, à l'instruction suivante (A2). 2. Dispositif suivant la revendication 1, implé- menté dans chacun des processeurs d'un multiprocesseur fonc- tionnant en multitraitement et en multiprogrammation, cha- que processeur ayant un accès privilégié via un bus local (BLi) ê une tranche de mémoire (Mi), caractérisé en ce que le dit dispositif coopère avec le système pour provoquer} en temps opportun une affectation dynamique de chaqueprogramme à celui des processeurs (Px) le mieux placé pour traiter ce programme c'est-à-dire dont la tranche de mémoire d'ac- cès privilégié (Mx) contient la portion (1) o se trouve les prochaines instructions à traiter des programmes qui lui sont affectés. 3. Dispositif selon l'une des revendications 1 et 2, le système d'exploitation ayant mémorisé le numéro de la portion en cours dans le contexte de l'ordinateur, caractérisé en ce qu'il est pourvu de moyens (18) tels que la trappe de portion n'est mise en oeuvre ni à l'aller ni au retour d'une portion cible (So) ayant un numéro pri- vilégié, par exemple le numéro zéro.