Brevet FR2785407A1 — publié le 20000505

Titre : Procédé pour localiser des adresses physiques dans une mémoire à accès non uniforme et machine pour mettre en oeuvre ce procédé. Le domaine d'application de l'invention est celui des machines informatiques avec mémoire à accès non uniforme. Une mémoire est à accès non uniforme lorsque la durée qui sépare l'instant d'émission d'une requte d'accès à une ressource de la mémoire et l'instant de réception d'une réponse varie suivant la localisation de la ressource dans la mémoire. Cette durée est appelée latence d'accès. Un intért présenté par une machine avec mémoire à accès non uniforme est de pouvoir attribuer à des processus exécutés par cette machine, des ressources dans une mémoire physique de taille volumineuse, au moyen d'un système d'exploitation unique. Le système d'exploitation gère la mémoire physique au moyen d'adresses physiques dans un espace d'adressage physique. L'espace d'adressage physique est généralement subdivisé en pages physiques de taille déterminée. Le système d'exploitation met à disposition des processus, un espace d'adressage virtuel constitué de segments contenant des pages virtuelles de taille identique à celle des pages physiques. Le système d'exploitation se charge d'établir une correspondance de chaque page virtuelle réellement utilisée par un processus, avec une page physique de la mémoire, au moyen d'un gestionnaire de mémoire virtuel. Les gestionnaires de mémoire virtuelle sont connus dans le domaine des machines avec mémoire à accès uniforme dans laquelle la localisation d'une page physique pour établir une correspondance n'influe pas sur la latence d'accès. Un problème se pose pour utiliser un gestionnaire de mémoire virtuelle connu dans le domaine des machines informatiques avec mémoire à accès non uniforme de façon performante. En effet, il est préférable qu'une page physique mise en correspondance avec une page virtuelle pour un processus considéré, soit dans la mesure du possible, une page physique avec latence d'accès minimale pour le processus considéré. II est alors nécessaire de pouvoir localiser des numéros de page logique ou de façon plus générale des adresses physiques dans la mémoire à accès non uniforme. Avant le lancement du système d'exploitation de la machine, une plage d'adresses physiques contiguës de 1'espace d'adressage physique est attribuée à chaque ensemble de ressources de mme localisation dans la mémoire physique. Pour localiser une adresse physique, une première solution qui se présente, consiste à comparer I'adresse physique à chaque plage d'adresses jusqu'à trouver la plage d'adresse qui la contienne et d'en déduire ainsi sa localisation. Dans le meilleurs des cas, la première comparaison suffit mais dans le pire des cas, le résultat est obtenu après comparaison avec toutes les plages d'adresses. D'autre part, une comparaison avec une plage d'adresses à forte latence ralentit l'obtention du résultat. Le procédé de cette première solution n'est pas satisfaisant car le risque de durée de sa mise en oeuvre nuira aux performances de la machine. Pour localiser une adresse physique, une deuxième solution qui se présente, consiste à diviser la valeur de I'adresse physique par la taille d'un ensemble de ressource. Le résultat donne un rang d'ensemble de ressources dont il est possible de déduire la localisation. Le procédé de cette deuxième solution n'est applicable que si tous les ensembles de ressources ont la mme taille. L'invention a pour objet un procédé qui permette de localiser rapidement une adresse physique, quelque soit la taille des ensembles de ressources de mme localisation. Selon l'invention, le procédé identifie le lieu de résidence d'une ressource de mémoire physique d'adresse physique AP dans un espace d'adressage physique associé à une mémoire à accès non uniforme MP répartie dans plusieurs lieux de résidence, I'un d'entre eux étant celui de ladite ressource. Le procédé comprend : -une étape de préparation qui subdivise t'espace d'adressage physique en sous-espaces d'adressage physique de tailles identiques, de façonà associer à chaque lieu de résidence un nombre entier de sous-espaces d'adressage physique ; -une étape d'identification qui reconnaît le sous-espace d'adressage physique auquel appartient I'adresse physique et identifie le lieu de résidence de ladite ressource comme étant celui associé au sous espace d'adressage reconnu. Des caractéristiques supplémentaires d'une mise en oeuvre préférée de l'invention, ressortent de la description qui suit en référence aux figures où : -la figure 1 présente une machine informatique à plusieurs modules ; -la figure 2 présente une architecture conforme à l'invention ; -la figure 3 présente un procédé conforme à l'invention. En référence à la figure 1, une machine informatique comprend un nombre n de modules mis en oeuvre au moyen d'un système d'exploitation OS (Operating System en anglais) commun. Un module 1 comprend un ou plusieurs processeurs 10,11,12,13, de type unité centrale de traitement CPU (Control Processing Unit en anglais) et une unité mémoire 14, locale au module 1. Un module 2 comprend un ou plusieurs processeurs 20,21, 22,23, de type unité centrale de traitement CPU et une unité mémoire 24, locale au module 2. Un module 3 comprend un ou plusieurs processeurs 30, 31,32,33, de type unité centrale de traitement CPU et une unité mémoire 34, locale au module 3. Un module 4 comprend un ou plusieurs processeurs 40,41,42,43, de type unité centrale de traitement CPU et une unité mémoire 44, locale au module 4. L'exemple présenté où le nombre n est égal à quatre, n'est limitatif ni pour un nombre inférieur, ni pour un nombre supérieur de modules. Chaque module 1,2,3,4, comprend respectivement un organe d'interconnexion 6,7,8,9. Les organes d'interconnexion 6,7,8,9 communiquent entre eux de façon matérielle au moyen d'une liaison 5. Un ensemble comprenant tout ou partie de l'unité mémoire 14, tout ou partie de l'unité mémoire 24, tout ou partie de l'unité mémoire 34 et tout ou partie de l'unité mémoire 44, constitue un ensemble de ressources de mémoire physique MP pour le système d'exploitation OS de la machine. Pour accéder à une ressource dans la mémoire physique MP, un processeur 10,11,12,13, localisé dans le module 1 génère une requte d'accès sur un bus 15, local au module 1. La requte d'accès comprend une adresse physique AP de la ressource. A détection de I'adresse physique AP sur le bus 15, I'organe d'interconnexion 6 prend physiquement le contrôle du bus 15 pour analyser j'adresse physique AP. Si I'adresse physique AP est celle d'une ressource résidente dans l'unité mémoire 14 et que cette ressource est à jour, I'organe d'interconnexion 6 laisse à l'unité mémoire 14 le soin de transmettre la ressource requise sur le bus 15 pour répondre à la requte. Sinon, I'organe d'interconnexion 6 se charge de transmettre la ressource requise sur le bus 15. Si l'organe d'interconnexion 6 ne dispose pas de la ressource requise, localement au module 1, I'organe d'interconnexion 6 génère à son tour une requte d'accès sur la liaison 5. L'organe d'interconnexion 7,8,9, du module distant respectif 2,3,4, qui dispose de la ressource requise, la transmet à l'organe d'interconnexion 6. Le mécanisme matériel qui vient d'tre décrit est identique pour chacun des n modules 1,2,3,4 de la machine. Les explications relative au bus 15 qui précèdent, sont transposées à un bus 25 pour les composants du module 2, à un bus 35 pour les composants du module 3, à un bus 45 pour les composants du module 4. Ce mécanisme matériel est invisible du système d'exploitation OS qui voit 1'ensemble de ressources de mémoire physique MP au moyen de leurs adresses physique AP sans distinction a priori de localité de ces ressources à un module particulier. Cependant, le temps mis par le mécanisme matériel pour répondre 6 une requte d'accès générée par un processeur local à un module est plus court si la ressource requise est localement disponible dans ce module que si la ressource requise est disponible dans un module distant. C'est pourquoi, la mémoire physique MP est dite à accès non uniforme. En référence à la figure 2, une adresse physique AP est habituellement constituée de deux champs, un champ NP qui code un numéro de page physique sur un nombre i de bits par exemple de poids fort et un champ DEP qui code un déplacement à partir d'un début de page physique sur un nombre j de bits par exemple de poids faible. La puissance de deux du nombre j indique la taille d'une page, par exemple un nombre j égal à douze indique une taille de page de quatre kilo-octets. La puissance de deux du nombre i indique la taille de mémoire physique en nombre de pages, par exemple un nombre i égal à vingt indique un nombre de un méga-pages physiques, soit de quatre giga-octets de mémoire physique. Chaque unité mémoire 14,24,34,44, contient respectivement un nombre N1, N2, N3, N4 de pages physiques de la mémoire MP habituellement égal à une puissance de deux. Les numéros de page physique allant de zéro au nombre N1 moins un sont attribués à l'unité mémoire 14, les numéros de page physique allant du nombre N1 au nombre N2 moins un sont attribués à l'unité mémoire 24, les numéros de page physique allant du nombre N2 au nombre N3 moins un sont attribués à l'unité mémoire 34, les numéros de page physique allant du nombre N3 au nombre N4 moins un sont attribués 6 t'unité mémoire 44. Cette attribution de numéros de page est faite en configurant les unités mémoire 14,24,34,44, et les organes de connexions 6 à 9, avant de lancer le système d'exploitation OS. Ainsi, le mécanisme matériel précédemment décrit, reconnaît l'unité mémoire où réside la ressource requise en décodant le champ NP de I'adresse physique AP. Conformément à l'invention, le champ NP comprend un sous-champ G sur un nombre k de bits de poids connexe à celui du champ DEP. La puissance de deux du nombre k indique la taille d'un grain physique en nombre de pages physiques. La taille d'un grain physique est choisie de façon à ce que la mémoire MP contienne pour chaque unité mémoire 14,24,34,44, un nombre Q1, Q2, Q3, Q4 de grains physiques dont le nombre de pages physiques respectif N1, N2, N3, N4 soit un multiple. Une table 16 comprend autant de lignes que la mémoire MP contient de grains physiques. Le nombre de lignes de la table 16 est égal à la somme des n nombres Q1 à Q4. Les Q1 premières lignes de la table 16 contiennent chacune un numéro qui identifie le module 1. Les Q2 lignes suivantes de la table 16 contiennent chacune un numéro qui identifie le module 2. Les Q3 lignes suivantes de la table 16 contiennent chacune un numéro qui identifie le module 3. Les Q4 lignes suivantes de la table 16 contiennent chacune un numéro qui identifie le module 4. La valeur des i moins k bits restants du champ NP, code en binaire, un numéro de ligne de la table 16. De la sorte, une simple lecture des i moins k bits de poids fort d'une adresse AP donne directement accès à l'une des entrées de la table 16. Pour un numéro de page compris entre zéro et le nombre N1 moins un, I'une des Q1 premières lignes de la table 16 est accédée, la lecture de cette ligne donne directement le numéro qui identifie le module 1, sans autre calcul. Pour un numéro de page compris entre le nombre N1 et le nombre N2 moins un, I'une des Q2 lignes suivantes de la table 16 est accédée, la lecture de cette ligne donne directement le numéro qui identifie le module 2, sans autre calcul. Pour un numéro de page compris entre le nombre N2 et le nombre N3 moins un, I'une des Q3 lignes suivantes de la table 16 est accédée, la lecture de cette ligne donne directement le numéro qui identifie le module 3, sans autre calcul. Pour un numéro de page compris entre le nombre N3 et le nombre N4 moins un, I'une des Q4 lignes suivantes de la table 16 est accédée, la lecture de cette ligne donne directement le numéro qui identifie le module 4, sans autre calcul. En prenant pour valeur de la taille de grain physique, un nombre égal au plus grand commun diviseur PGCD des nombres N1, N2, N3, N4 de pages physiques, le nombre de lignes de la table 16 est réduit au minimum car Q1 est égal au nombre N1 divisé par le nombre PGCD, Q2 est égal au nombre N2 divisé par le nombre PGCD, Q3 est égal au nombre N3 divisé par le nombre PGCD, Q4 est égal au nombre N4 divisé par le nombre PGCD. Une duplication de la table 16 dans chacun des modules 1,2,3,4, ne réserve qu'un nombre restreint de ressources. La duplication permet d'identifier rapidement le module de résidence d'une adresse physique AP sans nécessiter d'accès distant. Ainsi, un processus s'exécutant par exemple dans le module 1, est capable d'identifier immédiatement le numéro de module auquel appartient une adresse AP, en accédant à la duplication de la table 16 résidente dans le module 1. Un procédé en deux étapes est défini en référence à la figure 3. On y distingue une étape de préparation E1 et une étape d'identification E2. Le but de l'étape E1 est de préparer une architecture de données qui est ensuite utilisée dans t'étape E2. L'étape E2 répétée à chaque fois qu'il est nécessaire d'identifier le lieu de résidence d'une adresse physique AP ou d'un numéro de page NP. Dans l'étape E1, une taille G de sous-espace d'adressage physique, en nombre de pages physiques est définie à partir des nombres de pages N1, N2, N3, N4 de chaque module. La taille G est définie de sorte que chaque module contienne un nombre entier de sous espace d'adressage physique. La taille G est donc un diviseur de chacun des nombres N1, N2, N3, N4. Ainsi chaque lieu de résidence 1,2,3,4 contient respectivement un nombre N1/G, N2/G, N3/G, N4/G de sous-espaces d'adressage physique. Ainsi, t'étape de préparation E1 subdivise l'espace d'adressage physique en sousespaces d'adressage physique de tailles identiques G, de façon à associer à chaque lieu de résidence 1,2,3,4, respectivement un nombre entier de sous-espaces d'adressage physique N1/G, N2/G, N3/G, N4/G. Un identificateur de lieu de résidence est attribué à chaque somme cumulée des nombres de sous-espaces à partir de zéro. Ainsi, à un nombre nul est attribué un identificateur du module 1, à un nombre égal à N1/G est attribué un identificateur du module 2, à un nombre égal à [N1+N2]/G est attribué un identificateur du module 3, à un nombre égal à [N1+N2+N3]/G est attribué un identificateur du module 4. A chaque fois qu'un processus a besoin d'identifier le lieu de résidence d'une adresse AP, le processus exécute l'étape E2. Dans t'étape E2, la valeur du champ NP de I'adresse AP est divisée par la taille G définie. L'identificateur du lieu de résidence est celui attribué à la plus grande somme cumulée inférieure au résultat de la division. Ainsi, un résultat compris entre zéro et N1/G identifie le module 1, un résultat compris entre N1/G et [N1+N2]/G identifie le module 2, un résultat compris entre [N1+N2]/G et [N1+N2+N3]/G identifie le module 3, un résultat compris entre [N1+N2+N3]/G et [N1+N2+N3+N4]/G identifie le module 4. Dans l'étape E1, en exprimant la taille G sous forme d'une puissance k de deux, celle-ci constitue un champ d'adresse physique AP de k bits dans le champ NP de i bits. Le champ restant de i moins k bits permet alors de numéroter chaque sous espace d'adressage physique. La table 16 est créée avec une ligne pour chaque numéro de sous-espace d'adressage physique. Dans les N1/G premières lignes est écrit l'identificateur du module 1. Dans les N2/G lignes suivantes est écrit l'identificateur du module 2. Dans les N3/G lignes suivantes est écrit l'identificateur du module 3. Dans les N4/G lignes suivantes est écrit l'identificateur du module 4. Dans l'étape E2, la division est réalisée par simple lecture du numéro de sous-espace d'adressage physique contenu dans le champ restant de i moins k bits du champ NP. Ce numéro de sous-espace d'adressage physique référence directement la ligne correspondante de la table 16 qui donne l'identificateur du lieu de résidence de la ressource adressée par I'adresse AP. Une taille G des sous-espaces d'adressage physique égale au plus grand commun diviseur PGCD des nombres de pages physiques N1, N2, N3, N4 de chaque lieu de résidence, permet d'optimiser le nombre de sous-espaces d'adressage physique pour réduire le nombre de lignes de la table 16. REVENDICATIONS : 1. Procédé pour identifier au moyen d'un processeur (10,11,12,13) un lieu de résidence (1,2,3,4) de ressource de mémoire physique d'adresse physique (AP) dans un espace d'adressage physique associé à une mémoire à accès non uniforme (MP) répartie dans plusieurs lieux de résidence, I'un d'entre eux étant celui de ladite ressource, caractérisé en ce qu'il comprend : -une étape de préparation (E1) qui subdivise 1'espace d'adressage physique en sous-espaces d'adressage physique de tailles identiques, de façonà associer à chaque lieu de résidence un nombre entier de sous-espaces d'adressage physique ; -une étape d'identification (E2) qui reconnaît le sous-espace d'adressage physique auquel appartient I'adresse physique (AP) et identifie le lieu de résidence de ladite ressource comme étant celui associé au sous espace d'adressage reconnu. 2. Procédé selon la revendication 1, caractérisé en ce que : -dans l'étape (E1), un champ d'adresse physique (AP) est défini pour numéroter chaque sous-espace d'adressage physique, une table (16) est créée avec une ligne pour chaque numéro de sous-espace d'adressage physique, sur chaque ligne correspondant à un numéro de sous-espace d'adressage physique considéré est écrit un identificateur du lieu de résidence associé au sous-espace d'adressage physique considéré, -dans l'étape (E2), une lecture de ligne de la table (16) correspondant au numéro de sous-espace d'adressage physique contenu dans le champ d'adresse physique défini, donne l'identificateur du lieu de résidence de la ressource adressée par I'adresse (AP). 3. Procédé selon la revendication 1, caractérisé en ce que : -dans l'étape (E1), une taille (G) de sous-espace d'adressage physique, un nombre de sous-espaces d'adressage physique par lieu de résidence sont définis, et un identificateur de lieu de résidence est attribué à chaque somme cumulée des nombres de sous-espaces à partir de zéro ; -dans l'étape (E2), la valeur de I'adresse (AP) est divisée par la taille (G) définie, I'identificateur du lieu de résidence étant celui attribué à la plus grande somme cumulée inférieure au résultat de la division. 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que la taille des sou-espaces d'adressage physique est égale au plus grand commun diviseur PGCD des nombres de pages physiques de chaque lieu de résidence. 5. Machine comprenant une mémoire à accès non uniforme (MP) répartie dans plusieurs lieux de résidence (1,2,3,4) et accédant à une ressource physique de la mémoire (MP) au moyen d'une adresse physique (AP), caractérisée en ce qu'elle comprend : -une table (16) comprenant un nombre de lignes égal à une puissance (i-k) de deux ; -chaque ligne étant accessible au moyen d'un champ de (i-k) bits de I'adresse physique (AP) ; -la ligne accédée au moyen du champ de (i-k) bits de I'adresse physique (AP) contenant un identificateur du lieu de résidence de ladite ressource. 6. Machine selon la revendication 5, caractérisée en ce que la table (16) contient pour chaque lieu de résidence, un nombre de lignes égal à un quotient dont le numérateur est le nombre de pages physiques du lieu de résidence et dont le dénominateur est le nombre de pages physiques qui peuvent tre référencées par un champ de (k) bits de I'adresse physique (AP).