Brevet FR2584212A1 — publié le 19870102

La présente invention concerne des ensembles à cache-mémoire et plus pr6cisément un ensemble hiérarchique de caches qui peut être utilisé avec des multiprocesseurs à lignes communes partagées. Au cours des quelques dernières années, on a mis au point de nombreux proc6d6s d'interconnexion des proces- seurs et des ensembles de mémoires dans un ensemble de multi- traitement à couplage serré. Une telle solution a 6té l'orga- nisation d'un premier groupe de processeurs d'un côté de l'ensemble et d'un groupe de m6moires de l'autre côté de l'ensemble, avec un circuit central de commutation reliant les processeurs aux mémoires. On a aussi construit ou proposé des machines à plage partagée d'adressage, qui répartissent les mémoires entre les processeurs à l'aide d'un circuit hi6- rarchique d'interconnexion. Comme les circuits de commutation imposent un retard supplémentaire et comme la m6moire princi- pale, dans de nombreux cas, n'est pas suffisamment rapide pour qu'elle suive le rythme des processeurs, il devient n6cessaire d'ajouter des caches privés à chacun des proces- seurs afin qu'ils puissent fonctionner a pleine vitesse. L'addition de ces caches privés augmente les problèmes de t^. ion, présentent des difficultés de résolution. En fait, les ensembles proposés actuellement pour la conservation de la cohérence deviennent souvent des goulots d'étrangle- ment pour l'ensemble. Un autre proc6dé d'interconnexion d'un groupe de processeurs d'un ensemble de multitraitement est la connexion par l'intermédiaire d'une ligne commune partagée. Comme tout le trafic entre les caches et la mémoire principale se dérou- le sur la ligne commune partagée, chaque cache peut contenir d'une manière sûre uniquement des copies actuelles des empla- cements de la mémoire principale par contrôle des transferts dans la ligne commune, pouvant provoquer une péremption des emplacements de mémoire. Bien que les lignes communes parta- gées aient souvent pr6sent6 des défauts dus à une largeur de bande inadéquate, l'utilisation de caches privés importants réduit considérablement la largeur de bande nécessaire tout en donnant aux processeurs de courts temps efficaces d'accès. En outre, le trafic supplémentaire de la ligne commune créé par les algorithmes de cohérence est négligeable si bien que la totalité pratiquement de la largeur de bande de la ligne commune est disponible pour la gestion des données réelles. Comme dans le cas des monoprocesseurs, les caches privés peuvent être à écriture directe ou à écriture diffé- rée, avec des schémas correspondants de cohérence d'écri- ture directe ou d'écriture différée. Comme la largeur de bande de la ligne commune est le facteur principal de res- triction à l'expansion de ces ensembles, des schémas à écri- ture différée sont en général préférés, mais les schémas à écriture directe sont de réalisation plus simple. Des problèmes de cohérence entre plusieurs caches privés, dans un ensemble de multitraitement, apparaissent lorsque plusieurs caches privés ont des copies du contenu d'un emplacement particulier de la mémoire. Evidemment, il est essentiel que ces copies soient identiques. Lorsqu'un processeur modifie une copie de l'emplacement de mémoire dans son cache, la modification doit progresser, ou bien vers la mémoire principale, ou bien vers tous les autres caches privés ayant une copie de cet emplacement. Dans une variante, tous les autres caches peuvent être invalidés. En pratique, le procédé d'invalidation est habituellement nécessaire car il élimine un certain nombre de conditions de compétition qui peuvent apparaître lors d'une tentative de remise à jour de copies de l'emplacement mémoire dans les autres caches. Dans les schémas de commutation de lignes communes non parta- gées, le trafic dû aux messages d'invalidation peut devenir très important. Les lignes communes partagées cependant peuvent transmettre implicitement ces messages. Dans le cas d'un schéma de caches à écriture di- recte, chaque fois qu'une copie d'un emplacement d'un cache privé est écrite par son processeur, cette écriture est trans- mise à la mémoire principale par la ligne commune partagée. Comme l'indique le schéma des états d'un emplacement d'un cache dans l'ensemble de multitraitement à cache à écriture directe représenté sur la figure 1, tous les autres caches de l'ensemble contrôlent les écritures dans la ligne commune partagée et, lorsque d'autres caches contiennent une copie de l'emplacement de mémoire, ils invalident cette copie. Lorsqu'aucun des autres caches n'utilise en réalité cet em- placement à nouveau, le schéma de cohérence ne crée aucun trafic supplémentaire dans la ligne commune. Lorsqu'un ou plusieurs des processeurs demande cet emplacement à un moment ultérieur, des lectures supplémentaires sont réalisées dans la mémoire principale. Des expériences de simulation ont mon- tré que ces lectures supplémentaires sont peu fréquentes et contribuent peu à un trafic supplémentaire dans la ligne commune. Comme les caches sont du type à écriture directe, l'importance du trafic dans la ligne commune n'est jamais inférieure à la somme de toutes les écritures mémoires créées par les processeurs, correspondant par exemple à 15-20 % des demandes de mémoire. Un cache à écriture directe est très efficace lorsqu'un parallélisme limité (de l'ordre de 20 processeurs à vitesse moyenne) est nécessaire et il peut être réalisé simplement. Les schémas des caches à écriture différée ont été utilisés avec succès par les concepteurs de monoproces- seurs qui ont constaté que les caches à écriture différée réduisaient notablement l'importance du trafic de la mémoire principale par rapport aux caches à écriture directe. En théorie, lorsque la taille du cache se rapproche de l'infini, le trafic de la mémoire se rapproche d'une valeur nulle. Les tailles actuelles de caches utilisables en pratique permettent une réduction du trafic dans la ligne commune dans un ensem- ble de multitraitement à l'aide d'un cache à écriture diffé- rée de taille pouvant atteindre une dizaine de fois celle des caches à écriture directe, si bien que dix fois plus de processeurs environ peuvent être ajoutés potentiellement à un ensemble de multitraitement à lignes communes partagées. La nécessité de la conservation d'une cohérence complique la situation, et plusieurs additions au schéma fondamental à écriture différée sont habituellement nécessaires. Un en- semble plus compliqué ayant des fréquences d'utilisation de lignes communes plus élevées que celles d'un ensemble à pure écriture différée, est alors obtenu, mais l'utilisation par processeurs est encore bien inférieure à celle d'un schéma à écriture directe. Plusieurs variantes d'ensembles à caches à écri- ture différée et à orientation sur la ligne commune parta- gée existent et conservent la cohérence des caches. L'arti- cle "Using Cache Memory to Reduce Processor Memory Traffic" (lOth International Symposium on Computer Architecture) de Dr. James R. Goodman décrit un ensemble à caches (appelé dans la suite "ensemble Goodman") qui utilise un mode initial d'écriture directe pour les données récemment acquises afin que d'autres caches soient invalidés dans le cas d'une modi- fication locale des données. Comme l'indique le diagramme des états de la figure 2, dans l'ensemble Goodman, lorsqu'un emplacement de la mémoire principale est atteint initiale- ment, il pénètre dans le cache soit à l'état valable (en cas de lecture) soit à un état réservé (en cas d'écriture). Un emplacement se trouvant déjà à l'état valable passe à l'état réservé lorsqu'un accès d'écriture d'un processeur apparaît. L'écriture qui a provoqué la transition à l'état réservé est transmise par le cache et à la ligne commune partagée. les écritures ultérieures des processeurs à cet emplacement le placent à un état spécial indiquant que le cache dans lequel il se trouve a la seule copie convenable de l'emplacement. Cet état est appelé "état mauvais". Dans le cas d'un cache à écriture directe, tous les caches de l'ensemble Goodman contrôlent la ligne commune et déterminent les écritures qui affectent leurs propres données et l'invalident lorsqu'une telle écriture est notée. Ainsi, après transmission de l'écriture directe initiale: un cache a en toute sécurité la seule copie d'un emplacement de mémoire et peut écrire à volonté sans avoir à transmettre d'autres écritures par la ligne commune partagée. Cependant, le cache doit contrôler la ligne commune partagée afin qu'il détermine des lectures éventuelles aux emplacements de mémoire dont il a modifié les copies, afin qu'après une telle lec- ture, il ne possède plus une copie exclusive de cet empla- cement. Lorsque seule une 6criture directe initiale a eu lieu, la seule action nécessaire, pour le cache qui a réa- lisé l'écriture, est d'oublier qu'il a une copie exclusive de l'emplacement de m6moire. Lorsque deux 6critures au moins ont 6té réalisées par le processeur associé au cache, il a la seule copie convenable et doit donc remettre à jour la mémoire principale avant la demande de lecture de la mémoire principale par les autres caches. Il existe plusieurs ensembles connus pour la re- mise à jour d'une m6moire principale avant que celle-ci ne réponde à une demande de lecture des autres caches, as- surant la réception de la copie la plus r6cente de l'empla- cement de mémoire à la suite de la demande de lecture qui a déclenché la remise à jour. Ces ensembles nécessitent en général que le cache contenant la copie modifi6e empêche la réalisation complète de la transaction de lecture par l'unité de mémoire jusqu'au retour de la copie modifiée. Une autre possibilité est la transmission d'une demande spé- ciale de ligne commune qui prend le pas sur la réponse de la m6émoire. L'ensemble de Goodman peut aussi être modifié afin qu'il évite l'écriture directe initiale lorsqu'on sait qu'il n'existe pas d'autre copie lorsque les données sont attein- tes pour la première fois. Il existe certaines conditions de compétition impliquant une modification simultanée de sous-éléments d'un bloc sans recouvrement par diff6rents processeurs et par la réalisation de verrous du type lecture- modification-écriture, mais ils peuvent être résolus par une réalisation soigneuse. Un autre ensemble connu qui évite le problème de léclipse du renvoi de donn6es mauvaises dans la mémoire prin- cipale ajoute un bit de "v6rification réalis6e" à chaque bloc dans la mémoire principale. Lorsqu'un cache privé décrouvre qu'il doit avoir un accès exclusif à un emplacement, il lit celui-ci dans la m6moire principale avec une lecture d'accès exclusive qui met le bit de vérification à l'état un et transfère la propriété de l'emplacement au cache privé. Les autres caches qui ont des copies des données rendent invalides ces copies après détection de la lecture exclusive dans la ligne commune. Ainsi, le schéma remplace l'écriture directe initiale de l'ensemble de Goodman par une seconde écriture spéciale. Bien que ce schéma évite la nécessité de l'écriture directe initiale, l'importance totale du tra- fic transmis à la ligne commune selon ce schéma est compara- ble à celle de l'ensemble de Goodman. Ce schéma donne des solutions simples aux problèmes précités de verrouillage de lecture-modificationécriture. Malgré l'augmentation de complexité, tous les schémas à écriture différée indiqués précédemment utilisent de préférence des caches à écriture directe. La réduction de trafic dans la ligne commune donnée par les caches à écriture différée les rend très souhaitables dans le cas d'un ensemble de multitraitement à ligne commune partagée, bien que la saturation de la ligne commune limite la taille des calculateurs. La présente invention a donc pour objet principal un ensemble à caches destiné à un multiprocesseur à lignes communes partagées ayant plusieurs lignes communes partagées à organisation hiérarchique qui conservent de manière fia- ble la cohérence des caches. Un autre objet de la présente invention est la réalisation d'un ensemble à caches qui permet la subdivision d'un ensemble de multitraitement en plusieurs ensembles de multitraitement ayant plusieurs lignes communes partagées à organisation hiérarchique. L'invention concerne aussi un ensemble à caches destiné à un multiprocesseur, ayant des lignes communes parta- gées multiples, organisées hiérarchiquement et qui nécessi- te une utilisation minimale de la ligne commune partagée. Elle concerne aussi un ensemble à caches de multi- processeur ayant plusieurs lignes communes partagées et orga- nisées hiérarchiquement, permettant l'utilisation de caches à écriture directe ou différée. Un ensemble à caches destiné à un ensemble de multi- traitement à ligne commune partagée comporte plusieurs proces- seurs ayant chacun son propre cache-mémoire privé. Chaque cache privé est connecté à une première ligne commune à la- quelle est aussi connecté un second cache-mémoire de niveau supérieur. Le second cache de niveau supérieur est lui-même connecté soit à une autre ligne commune et à un cache-mémoire de niveau supérieur, soit à une mémoire principale de l'en- semble par l'intermédiaire d'une ligne commune globale. Cha- que cache de niveau supérieur contient suffisamment d'espaces- mémoires pour qu'il permette aux caches de niveau supérieur d'avoir une copie de tous les emplacements de mémoire se trou- vant dans les caches au niveau immédiatement inférieur. La mémoire principale comprend à son tour suffisamment d'espaces pour qu'elle contienne une copie de chaque emplacement de mé- moire du niveau le plus élevé des cache-mémoire. L'ensemble à caches selon la présente invention peut être utilisé soit avec des schémas de gestion de cohérence à caches-à écriture directe, soit des schémas à écriture différée. Les mémoires à plusieurs voies d'accès peuvent aussi remplacer la mémoire principale. D'autres caractéristiques et avantages de l'inven- tion ressortiront mieux de la description qui va suivre, faite en référence aux dessins annexés sur lesquels: la figure 1 est un schéma des états d'un emplace- ment de cache dans un multiprocesseur à caches à écriture directe; la figure 2 est un schéma des états d'un emplace- ment de cache dans un multiprocesseur à caches à écriture différée; - la figure 3 est un schéma d'un multiprocesseur hiérarchique comprenant deux niveaux de caches et de lignes communes partagées; la figure 4 est un schéma des états d'un cache de niveau deux mettant en oeuvre un algorythme de cohérence de plusieurs caches selon la présente invention; la figure 5 représente un mode de réalisation ex- tensible de l'ensemble de multitraitement représenté sur la figure 1, mettant en oeuvre un schéma à caches à écriture directe; la figure 6 est un schéma d'un autre mode de réa- lisation d'ensemble de multitraitement de la figure 1 mettant en oeuvre l'ensemble hiérarchique à caches mettant en oeuvre un schéma de caches à écriture différée; la figure 7 est un schéma d'un ensemble de multrai- tement à base d'une mémoire à deux voies d'accès; la figure 8 est un diagramme des états d'un en- semble à mémoire à deux voies d'accès mettant en oeuvre un schéma de cohérence de plusieurs caches selon la pré- sente invention; la figure 9 est un schéma d'un multiprocesseur mettant en oeuvre des memoires à plusieurs voies d'accès et un ensemble à caches hiérarchiques selon la présente in- vention; la figure 10 est un schéma d'une variante d'en- semble de multitraitement représenté sur la figure 5; et la figure 11 est un diagramme des états d'un adaptateur de groupe mettant en oeuvre un schéma de cohérence à plusieurs caches, selon l'invention. On considère d'abord les légendes indiquées -sur les figures 1 et 2. Sur ces figures, "élimination" désigne l'extraction d'une copie du cache Gtant donné leur empla- cement dans le cache. "Lecture processeur" est une demande de lectur provenant du processeur associé nu cache. "Ecriture- processeur" est une demande d'écriture provenant du proces- seur associé au cache. "Lecture ligne commune" est une demande de lecture transmise par la ligne commune. "Ecriture ligne commune" est une demande d'écriture transmise par la ligne commune. "Ecriture de chasse" est une écriture spéciale dans la mémoire principale dont les données sont aussi trans- mises à la site d'une demande de lecture de ligne commune. On considère maintenant la figure 3 qui est un mode de réalisation simplifié d'ensemble à cache destiné à un multiprocesseur 10 à ligne commune partagée selon l'in- vention, ce mode de réalisation comprenant plusieurs cache- mémoire disposés hiérarchiquement. Le terme "hiérarchique" indique que les cache-mémoire sont à des niveaux différents les uns par rapport aux autres, un ou plusieurs caches de niveau inférieur étant relié à un cache de niveau supérieur par une ligne commune partagée. De tels caches de niveau supérieur peuvent aussi être raccordés, avec un ou plusieurs autres caches de même niveau à la mémoire principale ou à un cache ayant un niveau encore supérieur. Dans le mode de réalisation ayant deux niveaux de caches et de lignes communes partagées représenté sur la figure 3, chaque processeur 12 a un cache-mémoire associé 14 et chaque cache-mémoire 14 est connecté à une première ligne commune partagée 16. Cette dernière est aussi connectée à un second cache 18 de niveau plus élevé qui est lui-même connecté à une seconde ligne commune 20 de niveau plus élevé partagé avec tous les autres caches 18 du second niveau plus élevé. La ligne commune 20 connecte les modules 22 de la mémoire principale au second cache 18 de niveau plus élevé. La figure 3 représente donc un ensemble hiérarchique à ca- ches dans lequel un ensemble cache privé-ligne commune par- tagée est appliqué par récurrence à des niveaux supplémen- taires de caches. Dans la structure arborescente résultante les caches de niveau plus élevé forment les liens avec les branches inférieures de l'arbre. Les caches de niveau supé- rieur tels que les caches 18 jouent le rôle de filtres réduisant le trafic transmis aux niveaux supérieurs de l'ar- bre. Ces caches de niveau supérieur étendent la maîtrise de la cohérence entre les niveaux et permettant des possi- bilités très larges d'adressage dans l'ensemble. Comme la plus grande partie de l'accélération des processeurs est obtenue à l'aide des caches 14 de ni- veau inférieur, les caches 18 de niveau plus élevé ou supé- rieur peuvent être sous forme de mémoires dynamiques à accès direct relativement lentes et denses, identiques à celles qui sont utilisées par les modules 22 de la mémoire princi- pale. Le temps moyen de latence est encore réduit car les retards de commutation à un niveau supérieur sont évités lorsque les données voulues sont atteintes (c'est-à-dire une demande d'accès à la mémoire à un emplacement conservé dans le cache du processeur). Ces caches, pour donner les avantages maximaux, doivent être importants, supérieurs d'un facteur à la somme de tous les caches du niveau inférieur suivant qui les alimente. Comme de tels caches peuvent être des mé- moires à accès direct dynamique, ils ne posent pas de problèmes. Les caches du second niveau et des niveaux supé- rieurs (18 dans le mode de réalisation de la figure 3) de l'ensemble hiérarchique nécessitent certaines extensions afin que l'ensemble garde une cohérence très large entre les caches. L'extension la plus importante est le fait que tout emplacement de mémoire pour lequel il existe des copies dans les caches de niveau inférieur a aussi des copies dans le cache de niveau supérieur. Comme l'indique le diagramme des états de la figure 4, l'ensemble réalise cette opération par création d'un signal d'"invalidation" transmis aux caches de niveau inférieur chaque fois qu'un emplacement est retiré du cache de niveau supérieur. Comme toutes les copies des em- placements de mémoire contenues dans les caches de niveau inférieur se trouvent aussi dans le cache de niveau supé- rieur, le cache de niveau supérieur joue le rôle d'un con- trôleur de cohérence entre caches pour tous les caches de niveau inférieur qui lui sont connectés. Le schéma des caches à écriture différée qui est utilisé selon la présente invention est analogue à l'ensem- ble de Goodman dans la mesure o chaque emplacement de cache a quatre états dans les deux ensembles. Les caches de niveau élevé selon la présente invention ont cependant transmis des demandes de chasse ou d'invalidation vers les caches de niveau inférieur lorsque la conservation de la cohérence entre les caches le nécessite. Une demande d'invalidation est traitée de la même manière qu'une écriture dans la ligne commune par le cache de niveau inférieur et une demande de chasse est traitée de la même manière qu'une lecture de ligne commune. Sur la figure 4, L1BR désigne une lecture dans la 1 1 ligne commune de groupe, L1BW désigne une 6criture dans la ligne commune de groupe, LIB1 d6signe une invalidation de ligne commune de groupe, LIBF désigne une chasse dans la ligne commune de groupe, L2BR désigne une lecture globale dans la ligne commune et L2BW une écriture globale dans la ligne commune alors que "LIMINATION" désigne le remplacement d'un emplacement d'un cache par un emplacement différent de la mémoire. La maîtrise de la cohérence entre les caches peut être réalisée dans un multiprocesseur hiérarchique à. lignes communes partagées selon l'invention à l'aide soit de caches à écriture directe, soit de caches à écriture diff6r6e. Dans l'ensemble à plusieurs caches mettant en oeuvre des caches à écriture directe représenté sur la figure 5, lorsqu'un pro- cesseur 12 transmet une 6criture à la mémoire, l'accès d'écri- ture est filtré dans la hiérarchie des caches, apparaissant à chaque niveau dans sa ligne commune partagée associée. Par exemple, une écriture provenant du processeur 12b est fil- trée du cache 14b à la ligne commune 16a, vers le cache 18a et enfin, dans la ligne commune 20 (Dans cet exemple la ligne horizontale 15 des diverses unités de mémoire représente un emplacement commun de mémoire). Dans les parties de l'ensemble auxquelles le cache 12b est directement connecté, l'invalida- tion est réalisée comme décrit précédemment pour le cas d'un seul niveau. En outre, chaque cache ayant une copie de l'em- 2; placement ex6cuté 15 de mémoire (par exemple le cache 14c) invalide simplement cet emp]scement. Dans les caches des niveaux plus élev6s de la hiérarchie, l'existence d'un em- placement particulier de mémoire implique que des copies de cet emplacement peuvent être conservées à des niveaux se trouvant juste audessous du cache. Par exemple, lorsqu'un cache 18c du second niveau de la figure 5 détecte l'accès d'écriture dans la ligne commune 20, non seulement il doit in- valider son propre cache, mais encore, une demande d'invali- dation doit être transmise auxcaches d'ordre inférieur qui lui sont reliées et qui contiennent l'emplacement de mémoire. Dans l'exemple de la figure 5, les signaux d'invalidation sont transmis aux caches 14g, 14i. Lorsque l'invalidation est réalisée, une demande correspondante est placée dans la ligne commune 16c et elle est interprétée par les ca- ches 14g, 14h, 14i comme une transaction d'écriture pour cet emplacement de mémoire. Ces caches invalident alors leurs propres copies, lorsqu'elles sont présentes, comme si la de- mande d'invalidation était une écriture provenant d'un autre cache de la ligne commune partagée. Un tel ensemble suppose que les copies des emplacements de mémoire qui existent au niveau inférieur existent aussi dans les caches associés des niveaux supérieurs. La garantie de ce comportement nécessite la transmission des demandes d'invalidation aux caches de niveau inférieur chaque fois qu'un emplacement d'un niveau supérieur est remplacé à la suite d'une omission. Ainsi, il est important que les faibles rapports d'omission dans les caches de niveau supérieur soient obtenus et, à cet ef- fet, de tels caches doivent être importants. Dans un ensemble hiérarchique à caches selon la présente invention, mettant en oeuvre des caches à écriture différée, l'opération d'invalidation est très semblable à celle qui est utilisée avec les ensembles à écriture directe. Dans le cas d'un ensemble à caches hièrarcniques à écriture différée, l'écriture dirocte de l'ensemble de Goodman ou la lecture à accès exclusif à l'aide du bit supplémentaire dans la mémoire principale des autres ensembles a pour rôle de dé- clencher les invalidations de la même manière que les écri- tures dans tout le cache à écriture directe. En particulier, dans le mode de réalisation de la présente invention mettant en oeuvre un ensemble à caches hiérarchiques à écriture dif- férée du type de Goodman, l'écriture directe initiale est utilisée pour l'invalidation d'emplacement dans d'autres caches. Dans le mode de réalisation utilisant la lecture à accès exclusif et le bit supplémentaire, la lecture à accès exclusif non seulement invalide les autres caches mais aus- si lève un bit dans la mémoire, indiquant qu'une copie privée de l'emplacement de mémoire existe dans un cache particulier. Cependant, des problèmes se posent après l'invali- dation initiale lorsque d'autres processeurs demandent un accès renouvelé aux donn6es. Comme dans le cas des schémas à caches à un seul niveau, tous les caches doivent contrôler les demandes de lecture provenant d'autres caches et trans- mises par les lignes communes partagées correspondantes, et ils doivent effectuer les changements d'6tat lorsque des de- mandes d'emplacement dans lesquelles ils ont des copies exclu- sives sont transmises. A une lecture suivante provenant d'un autre cache privé dans le mode de réalisation utilisant l'en- semble à cache de Goodman, le cache ayant la copie valable, signale à la mémoire principale 24 qu'elle ne doit pas répon- dre et transmet par sa propre copie de l'emplacement. Lors d'une lecture suivante provenant d'un autre processeur dans le mode de réalisation à lecture à accès exclusif, le bit levé dans la mémoire principale 24 inhibe la réponse par la mémoire prin- cipale et le cache ayant la copie valable de l'emplacement de la mémoire répond à sa place. En outre, lorsque l'6tat d'un cache indique qu'il peut exister une mauvaise copie d'un emplacement de mémoire dans un cache se trouvant au- dessous dans la hiérarchie, une demande de "chasse" doit être transmise plus bas. Ces demandes de chasse doivent progresser vers le bas jusqu'au niveau inférieur de la hi6rarchie et doivent provoquer la modification des caches du niveau inf6- rieur à un état "valable" dès qu'une lecture réelle de cet emplacement a été effectuée dans les lignes communes partagées. * La figure 6 repr6sente un exemple mettant en oeuvre un ensemble hiérarchique à caches à écriture différée. Sur la figure 6, on suppose que les caches 14b et 18a donnent un accès exclusif à un emplacement 15 à la suite de la s6quence d'écri- ture d'une écriture antérieure, et que le processeur 12h souhaite alors lire cet emplacement; la demande progresse dans la hiérarchie (c'est-àdire qu'il n'existe pas de copie dans les caches se trouvant juste audessus du processeur 12h) si bien que la demande "saute" tous les niveaux. Lorsque la demande atteint la ligne commune 20, le cache 18a détecte la nécessité de l'abandon de l'accès exclusif et chasse éventuel- lement une copie mauvaise de l'emplacement. Le cache 18a transmet une demande de chasse vers la ligne commune 16a 1 4 et le cache 14b abandonne l'accès exclusif et transmet la copie modifiée de l'emplacement 15 de mémoire dans la hiérar- chie. Suivant le schéma à écriture différée qui est utilisé, les donn6es ou bien reviennent d'abord à la mémoire princi- pale 22 ou bien vont directement dans le cache 18c puis dans le cache 14h et le processeur 12h. Les copies se trou- vant dans le cache 18a et dans le cache 14b restent, mais ne sont plus marquées comme étant exclusives. Dans l'ensemble de multitraitement selon l'in- vention, seules les branches inférieures de la hi6rarchie qui ont réellement des copies de ltemplacement affecté de mémoire sont impliquées dans le trafic de coh6rence. Dans l'exemple décrit précédemment, le processeur et les unités de cache-mémoire associés au cache 18b ne voient pas d'inva- lidation ou de chasse et ainsi, la ligne commune 16b n'a pas de charge supplémentaire. En conséquence, la cohérence du ca- che est entretenue dans tout l'ensemble sans augmentation no- table du trafic dans les lignes communes, et les parties de niveau inférieur de l'ensemble de multitraitement sont isolées mutuellement dans la mesure du possible. L'effet combiné de l'isolement du trafic à des niveaux inférieurs à l'aide de plusieurs lignes communes, la réduction du trafic au niveau élevé par les caches hiérarchiques et la limitation de la mai- trise de coh6rence aux sections dans lesquelles elle est né- cessaire provoquent une multiplication importante de la lar- geur de bande avec une mémoire pleinement partagée et une maîtrise automatique de la coh6rence. Bien que l'utilisation des caches à 6criture directe provoque une saturation des lignes communes aux niveaux supérieurs, l'utilisation des caches à écriture diff6rée permet une expansion presque illimit6e de l'ensemble par addition de couches à la hiérarchie. La partie de l'ensemble de multitraitement repr6- senté sur les figures 5 et 6, comprenant le cache 18a, la li- gne commune 16a, les caches privés 14a, 14b, 14c et les proces- seurs 12a, 12b, 12c est appelée "groupe". De tels groupes sont en réalité des ensembles indépendants à ordinateur de multitraitement dont le cachemémoire 18 est en réalit6 la mémoire principale du système. L'ensemble hiérarchique à caches selon la présente invention permet l'association de plusieurs de ces groupes en un ensemble plus important à ordinateur de multitraitement qui comprend une mémoire cen- trale principale 22 ayant une copie de toutes les données se trouvant dans les caches 18. Comme la cohérence est con- servée entre les caches 18, des données peuvent être trans- férées entre les divers groupes. L'ensemble hiérarchique à caches selon l'inven- tion peut aussi être utilisé avec des mémoires à plusieurs voiles d'accès qui peuvent avoir plusieurs lignes communes par- tagées qui les alimentent. Comme l'indique la figure 7, les mémoires à plusieurs voies d'accès peuvent être utilisées par addition d'une paire de bits à chaque bloc dans les mé- moires afin que les dessins d'accès soient suivis et que la nécessité de la transmission d'invalidation ou de chasse vers les lignes communes partagées associées 16 soient déterminées. La mémoire 24 à plusieurs voies d'accès peut être gérée de diverses manières suivant l'utilisation d'un cache à écriture directe ou à écriture différée, Les deux types de cache mettent en oeuvre le fait que la quantité de données partagées activement dans la plupart des ensembles de multi- traitement est très faible et en conséquence, une certaine inefficacité peut être tolérée dans le cas partagé. Le schéma le plus simple comprend la conservation de la voie d'accès , 26 qui a éventuellement l'accès exclusif à un emplace- ment de mémoire, afin que les demandes convenables d'invali- dation ou de chasse soient transmises chaque fois qu'un état de voie d'accès change. Comme l'indique le diagramme des états de la figure 8, l'opération peut être réalisée par utilisation d'un état pour chaque voie d'accès, indiquant qu'il s'agissait de la dernière voie d'accès à recevoir d'un accès d'écriture et qu'aucune lecture à partir des au- tres voies d'accès n'a eu lieu depuis. Un état supplémentaire est introduit lorsqu'il y a eu des lectures à plusieurs voies d'accès depuis la dernière écriture, indiquant que des copies d'un emplacement se trouvent dans plusieurs groupes. Ces états permettent l'extension des schémas de cohérence à plusieurs caches à écriture directe et à écriture différée entre les diverses voies d'accès. Sur la figure 8, PO désigne la voie d'accès zéro, P1 la voie d'accès un, BR la lecture reçue sur la ligne commune, BW, l'écriture reçue sur la li- gne commune, GENBI une invalidation créée de lignes communes et GENBF une chasse de lignes communes ainsi créée. Le fonctionnement des mémoires à deux voies d'accès est semblable pour les schémas à écriture directe et à écri- ture différée. Lorsqu;un accès convenable est reçu dans une voie d'accès déjà mise à l'état réservé, les invalidations sont transmises à toutes les autres voies d'accès puisqu'el- les peuvent posséder une copie de l'emplacement. L'emplacement de mémoire est alors réservé pour cette voie d'accès par attribution d'un accès exclusif à la voie d'accès. Les lec- tures et écritures suivantes à partir de la voie d'accès de réserve ne créent pas d'invalidation supplémentaire (et en conséquence, aucun trafic supplémentaire dans la ligne com- wure), mais les acceès à partir des autres lignes communes sup- priment l'affectation d:accès exclusif à la voie Griginale d'accès. Comme les demandes d'invalidation sont transmises uniquement lorsque les écritures apparaissent aux voies d'accès non réservées, le cas normal dans lequel les emplace- ments de mémoire ne sont pas partagés entre les groupes ou sont partagés comme des mémoires passives, ne créent pas d'invalidation supplémentaire. Les demandes d'invalidation apparaissent seulement aux quelques emplacements partagés activement et modifiés entre les deux lignes communes, si bien qu'ils provoquent une très faible servitude supplémen- taire pour le trafic de la ligne commune. Comme dans les sché- mas à écriture différée, les demandes de chasse doivent être transmises aux groupes qui perdent l'état d'accès exclusif étant donné un accès de lecture par une autre voie d'accès. ceci assure la réception de la copie la plus récente de l'em- placement de mémoire par la demande de lecture. Dans le cas o une demande de chasse est nécessaire, l'accès de lecture qui l'a provoquée n'est pas terminé tant que la demande de chasse n'a pas été satisfaite. L'ensemble à caches hiérarchiques selon la pré- sente invention peut être raccordé au niveau inférieur à des mémoires à deux accès destinées à former une structure ayant des interconnexions hiérarchiques et une mémoire prin- cipale répartie physiquement comme représenté sur la figure 9. Les demanaes demémoire locale provenant de dispositifs éloignés sont acheminées par la ligne commune partagée locale à l'aide d'une plaquette spéciale à adaptateur afin que la maîtrise de la cohérence entre plusieurs voies d'accès soit obtenue avec utilisation de mémoires classiques à une seule voie d'accès. Dans un tel ensemble à groupes, chaque ligne commune de niveau inférieur forme un groupe complet de multi- traitement avec accès direct à une série de mémoires locales i5 de groupes. Sur la figure 9, la ligne commune supérieure est la ligne commune globale et la ligne commune inférieure la ligne commune de groupe. On se réfère maintenant à la figure 10; l'accès à des données conservées dans des groupes éloignés progresse d'une manière analogue à celle d'un ensemble à caches hiéra- chiques direct. Les caches des groupes forment le second ni- veau de caches et assure les mêmes fonctions de filtrage et de maîtrise de cohérence pour les références distantes que les caches du second niveau du schéma hiérarchique représenté sur les figures 3 et 5 et 6. Les demandes, lorsqu'elles ont atteint le niveau global ou supérieur de la hiérachie, sont acheminées vers le bas vers le groupe qui contient l'empla- cement voulu de mémoires, et sont transmies par la ligne partagé du groupe. Comme les caches privés de cette ligne comune du groupe voient aussi cet accès, aucune action spé- ciale de cohérence entre les voies d'accès n'est nécessaire comme cela le serait si la mémoire locale était implantée sous forme d'une véritable mémoire à plusieurs accès. Dans le cas des accès qui parviennent directement à la mémoire du même groupe que le processeur d'origine, une maîtrise supplémentaire de la cohérence est nécessaire suivant les mêmes directives que dans le cas de la mémoire à deux voies d'accès. Cette maîtrise de la cohérence est réalisée à l'aide d'une carte spéciale d'adaptation qui garde trace des copies distantes possibles et, dans le cas des caches à écriture différée, du fait qu'une copie distante a un accès exclusif ou non. Dans ce cas, lorsqu'une écriture locale est réalisée et lorsqu'une carte d'adaptation (voir la figure 11 qui in- dique les états de la carte d'adaptation) détermine qu'une copie distante peut exister, une demande d'invalidation est transmise à la hiérarchie afin que la fonction que rem- plirait la demande d'écriture dans une hiérarchie pure soit exécutée. Lorsqu'une lecture locale est détectée pour un em- placement pour lequel l'existence d'une copie à utilisation exclusive distante est enregistrée, une demande de chasse doit remonter dans la hiérarchie. Avec ces extensions, le schéma de cohérence des caches créé pour des structures hié- rarchiques peut être utilisé aussi pour la réalisation d'une cohérence entre groupes. L'architecture des groupes présente plusieurs avantages. Par exemple, elle permet la conservation locale des codes et des piles pour un groupe de données, laissant ainsi aux niveaux supérieurs du système le trafic global. En conséquence, l'architecture de groupe permet à des multi- processeurs même de taille modérée, l'utilisation du schéma le plus simple de caches à écriture directe. Chaque processus peut être mis en oeuvre dans l'un quelconque des processeurs des groupes locaux avec une même facilité, donnant la plupart des avantages d'un équilibrage automatique des charges d'un multiprocesseur à couplage serré. Ces processus peuvent aussi cependant être exécutés dans un groupe distant lorsque cela est nécessaire. Etant donné les cache-mémoire locaux, même une opération provenant d'un groupe distant donne des carac- téristiques proches des valeurs maximales. En l'absence de localisation cependant, le trafic des lignes communes dis- posées entre les groupes augmente surtout lors de l'utilisa- tion de caches à écriture directe. L'architecture des groupes peut aussi faciliter la gestion des accès partagés globaux. La nature itérative de nombreux algorithmesscientifiques est telle que les accès globaux donnent un mauvais comportement des caches. Cependant, comme les dessins d'accès sont très prévisibles, il arrive souvent que les éléments globaux puissent être subdivisés afin qu'ils soient placés dans les groupes dans lesquels existe leur plus grande fréquence d'utilisation. Dans d'autres cas, les données globales peuvent devoir être déplacées entre plusieurs groupes. Des circuits de transfert de blocs peuvent -tre utilisés afin qu'ils exécutent ce déplacement avant que les données soient nécessaires au groupe distant. Ainsi, l'architecture des groupes peut tirer avantage d'une localisation granulaire importante pour la compensation du mauvais comportement des caches des données globales, donnant des latences à accès plus court et un moindre trafic de la ligne commune globale que dans le cas d'un schéma à cache hiérarchique direct. Il est bien entendu que l'invention n'a été dé- crite et représentée qu'à titre d'exemple préférentiel et qu'on pourra apporter toute équivalence technique dans ses éléments constitutif sans pour autant sortir de son cadre. Par exemple, bien qu'on ait décrit l'invention avec deux niveaux de caches (les caches privé- et les caches placés entre les caches privés et la mémoire principale), un nom- bre quelconque de niveaux de caches peut être placé entre les caches privés et la mémoire principale dans la mesure o chaque cache de niveau supérieur contient suffisamment de mémoires pour qu'il loge une copie de tous les emplace- ments de mémoire des caches du niveau immédiatement inférieur auquel il est connecté. En outre, d'autres schémas à écriture différée peuvent être utilisés pour la conservation de la cohérence entre les caches. REVENDICATIONS 1. Ensemble hiérarchique à cache-mémoire destiné à un ensemble à ordinateur de multitraitement comprenant plusieurs processeurs et une mémoire système, l'ensemble à cache- mémoire étant caractérisé en ce qu'il comprend des cache-mémoire privés (14) formant un premier niveau inférieur, associés à chacun des processeurs (12), une première tigne commune (16) reliant au moins deux cache-mémoire privés l'un à l'autre, des cache-mémoire (18) d'un second niveau plus élevé raccordés à la première ligne commune (16) 5 ces cache- mémoire contenant une copie du contenu de tous les emplace- ments de mémoire des cache-mémoire privés raccordés à la première ligne commune à laquelle est aussi raccordé le cache-mémoire du second niveau plus élevé, et une seconde ligne commune (20) raccordée à un cachemémoire de niveau plus élevé et à la mémoire (22) de l'ensemble, cette dernière contenant une copie du contenu de tous les emplacements de mémorisation des cache-mémoire de niveau élevé raccordés à la seconde ligne commune à la- quelle la mémoire de l'ensemble est raccordée. - 2. Ersemble selon la revendication 1, caractérisé en ce qu'il comporte un dispositif destiné à permettre l'écriture du contenu d'un emplacement d'un cache-mémoire privé (14), qui a été écrit par son processeur associé (12), à l'emplace- ment correspondant du cache-mémoire (18) de niveau plus élevé placé directement entre le cache-mémoire privé et la mémoire de l'ensemble et à l'emplacement correspondant de la mémoire de l'ensemble. 3. Ensemble selon la revendication 2, caractérisé en ce qu'il comprend un dispositif d'invalidation du contenu d'un emplacement d'un cache-mémoire privé ou d'un cache-mémoire de niveau plus élevé, contenant un emplacement de mémoire cor- respondant à un emplacement d'un autre cache privé dans lequel une opération d'écriture a été réalisée. 4. Ensemble selon la revendication 1, caractérisé en ce qu'il comprend un dispositif destiné à placer un emplacement d'un cache-mémoire privé (14) à un état réservé lorsque le processeur associé à ce cache privé exécute une opération d'écriture à l'emplacement de la mémoire, l'état réservé indiquant que le cache privé contenant l'emplacement réser- vé est le seul cache privé ayant une copie valable de l'em- placement de mémoire, et un dispositif destiné à copier le contenu de l'em- placement réservé dans le cache-mémoire (18) de niveau plus élevé relié au cache-mémoire privé (14) entre celui-ci et la mémoire de l'ensemble et contenant l'emplacement réservé, et dans la mémoire de l'ensemble. 5. Ensemble selon la revendication 4, caractérisé en ce qu'il comprend en outre un dispositif destiné à inva- lider le contenu d'un emplacement de mémoire d'un cache- mémoire privé (14) ou d'un cache-mémoire de niveau plus éle- vé qui contient un emplacement de mémoire correspondant à un emplacement d'un autre cache privé dans lequel une opération d'écriture a été-réalisée. 6. Ensemble selon la revendication 5, caractérisé en ce qu'il comprend un dispositif destiné à permettre à un processeur (12) ayant un cachemémoire privé (14) associé avec un emplacement de mémoire à l'état réservé, d'effectuer des opérations supplémentaires d'écriture uniquement dans le cache-mémoire privé associé, le cache-mémoire (18) de ni- veau plus élevé, raccordé à la première ligne commune à la- quelle le cache-mémoire privé contenant l'emplacement ré- servé est aussi raccordé, et la mémoire (22) de l'ensemble retenant le contenu de l'emplacement réservé tel qu'il exis- tait avant les opérations supplémentaires d'écriture. 7. Ensemble selon la revendication 4, caractérisé en ce qu'il comprend en outre un dispositif destiné à permet- tre à un cache-mémoire (18) de niveau élevé de reconnaître un emplacement de mémoire à l'état réservé dans un cache- mémoire (14) d'un niveau inférieur relié au cache-mémoire de niveau élevé qui a reconnu cet état réservé, par l'inter- médiaire d'une ligne commune à laquelle sont raccordés à la fois les cache-mémoire de niveau élevé et de niveau inférieur. 8. Ensemble selon la revendication 7, caract6risé en ce qu'il comporte en outre un dispositif destiné à permet- tre la reconnaissance, par le cache-mémoire (18) de niveau élevé, de l'emplacement de mémoire à l'état réservé afin que le contenu de l'emplacement de mémoire soit déplacé à l'6tat réservé. 9. Ensemble selon la revendication 1, caractérisé en ce que la seconde ligne commune (20) est raccordée au cache-mémoire (18) de niveau plus élevé. 10. Ensemble selon la revendication 1, caractérisé en ce que la mémoire (22) de l'ensemble est une mémoire à plusieurs voies d'accès, une voie d'accès étant reliée à une ligne commune globale (20) et une autre voie d'accès étant reliée à une ligne commune (16) à laquelle les caches de niveau 1élevé sont aussi reliés. 11. Ensemble selon la revendication 1, caract6risé en ce qu'il comprend au moins un jeu d'au moins un cache- mémoire (18) de niveau 1élevé et d'une ligne commune associ6e, mont6 entre le cache-mémoire (18) de niveau élevé et la se- conde ligne commune, l'une des lignes communes associ6es 6tant connect6e au cache-mémoire de niveau élevé et à un cache- m6moire de niveau élev6 de l'un au moins des jeux connectés à la seconde ligne commune. 12. Ensemble de multitraitement, caractéris6 en ce qu'il comprend un premier ensemble de multitraitement comprenant au moins un processeur (12) , chacun des processeurs 6tant connecté à un cache-mémoire privé associé (14) destiné à contenir les emplacements de la mémoire qui sont souvent atteints, chacun des cache-mémoire priv6s étant connecté aux autres par une première ligne commune (16), un premier cache-mémoire partagé (18) connecté à la première ligne commune, le premier cache-mémoire compre- nant une copie du contenu de chaque emplacement des cache- mémoire privés connectés à la première ligne commune (16), un second ensemble de multitraitement comprenant au moins un processeur (12), chaque processeur étant connecté à un cache-mémoire privé associé (14) destiné à contenir les emplacements de mémoire souvent atteints, chacun des caches privés étant connecté aux autres cache-mémoire privés par une seconde ligne commune (16), un second cache-mémoire (18) partagé connecté à la seconde ligne commune, le second cache-mémoire contenant une copie du contenu de chaque emplacement de mémoire des caches privés connectés à la seconde ligne commune, et une mémoire (24) de l'ensemble, connectée à une ligne commune globale (20) à laquelle sont aussi connectés les premier et second cache-mémoire, la mémoire de l'ensem- ble contenant une copie du contenu de chaque emplacement de mémoire des premier et second cache-mémoire. 13. Procédé de conservation de la cohérence d'un cache dans un ensemble hiérarchique à cache-ménoire destiné à être utilisé avec un ensemble à ordinateur de multitraitement comprenant plusieurs processeurs (12) ayant chacun un cache- mémoire privé associé (14), et une mémoire principale de l'ensemble, ledit procédé étant caractérisé en ce qu'il comprend la disposition d'un second cache-mémoire (18) de niveau plus élevé relié aux cache-mémoire privés par une pre- mière ligne commune partagée par au moins deux des proues- seurs, et à la mémoire principale de l'ensemble par l'inter- Inédiaire d'une seconde ligne commune globale, lorsquun processeur (12) exécute une opération d'écriture à un emplacement de mémoire de son cachemémoire privé associé, la copie du contenu de l'emplacement de me- moire dans le second cache-mémoire de niveau plus élevé con- necté à la première ligne commune et dans la mémoire princi- pale de l'ensemble connectée à la seconde ligne commune glo- bale, et l'invalidation des emplacements de cache-mémoire autres que le cache-mémoire privé dans lequel l'opération d'écriture est réalisée et du cache-mémoire dans lequel l'emplacement a été copié et qui contient une copie de l'em- placement écrit. 14. Procédé de conservation de la cohérence des caches dans un ensemble hiérarchique à cache-mémoire destiné à être utilisé avec un ensemble à ordinateur de multitraitement comprenant plusieurs processeurs (12) ayant chacun un cache- mémoire privé associé (14) de niveau inférieur et une mémoire principale (22), ledit procédé étant caractérisé en ce qu'il comprend la disposition d'un second cache-mémoire (18) de niveau élevé connecté aux cache-mémoire privés par une pre- mière ligne commune partagée par au moins deux processeurs, et à la mémoire principalc de l'ensemble par une seconde ligne commune globale, lorsqu'un processeur (12) exécute une opération d'écriture à un emplacement de mémoire de son cache-mémoire privé associé, la copie du contenu de l'emplacement de mé- moire dans le second cache-mémoire de niveau plus élevé con- necté à la première ligne commune et dans la mémoire princi- pale de l'ensemble connectée à la seconde ligne commune glo- bale, l'invalidation d'emplacements de cache-mémoire autres que le cache-mémoire privé (14) dans lequel l'opéra- tion d'écriture est réalisée et du cache-mémoire dans le- quel l'emplacement a été copié, contenant une copie de l'em- placement écrit, la disposition de l'emplacement du cache-mémoire privé dans lequel l'opération d'écriture est réalisée, à un état réservé indiquant que le cache privé contenant l'empla- cement réservé est le seul cache privé ayant une copie vala- ble de l'emplacement de mémoire, la copie du contenu de l'emplacement réservé dans le second cache-mémoire (18) de niveau plus élevé, connecté au cache-mémoire privé, entre le cache-mémoire privé et la mémoire de l'ensemble et contenant l'emplacement réservé, et dans la mémoire (22) de l'ensemble, et l'autorisation du processeur (12), ayant un cache- mémoire privé associé ayant un emplacement de mémoire à un état réservé, de manière qu'il exécute des opérations supplé- mentaires d'écriture uniquement dans le cache-mémoire privé associé, le cache-mémoire de niveau plus élevé et la mémoire de l'ensemble conservant le contenu de l'emplacement réser- vé tel qu'il existait avant les opérations supplémentaires d'écriture. 15. Procédé selon la revendication 14, caractérisé en ce qu'il comprend en outre l'autorisation de la reconnaissance par un cache- mémoire (18) de niveau plus élevé d'un emplacement de mémoire à un état réservé dans un cache-mémoire de niveau plus fai- ble connecté au cache-mémoire qui effectue la reconnaissance par une ligne commune à laquelle sont connectés les cache- mémoire de niveau plus élevé et de niveau plus faible, et l'autorisation du déplacement du contenu de l'em- placement de mémoire à l'état réservé par le cache-mémoire (18) de niveau élevé qui reconnaît l'emplacement de mémoire à l'état réservé.