Fonctionnement d'un ordinateur/Architectures distribuées, NUMA et COMA

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Les architectures distribuées sont des architectures qui utilisent non pas une mémoire partagée entre plusieurs processeurs, mais des mémoires séparées pour chaque processeur. Tous les processeurs sont reliés entre eux via un réseau, qui leur sert à échanger des données ou des ordres un peu particuliers. Il existe plusieurs types d'architectures distribuées et diverses manières de les classer. Par exemple, on peut les classer par rapport au réseau d'interconnexion qui connecte entre eux les ordinateurs/processeurs. De même, toutes les architectures distribuées ne gèrent pas la mémoire de la même manière et on peut distinguer diverses architectures selon leur manière de faire. Dans ce chapitre, nous allons parler plus en détail de ces architectures distribuées.

L'architecture du réseau d'interconnexion[modifier | modifier le wikicode]

Dans la plupart des cas, les processeurs et mémoires sont localisées dans des ordinateurs séparés, reliés entre eux par un réseau local : on parle alors de clusters. De tels clusters sont monnaie courante dans les serveurs.

Exemple de cluster.

Le cloud computing permet de relier entre des ordinateurs via internet, de manière à paralléliser les calculs dessus.

Mais il est aussi possible de placer les processeurs et mémoires dans un même boitier, sur la même puce de silicium. On parle alors de d'architectures à tiles. Ce nom vient du fait que chaque groupe processeur + RAM + connexions réseau est appelé une tile. Un bon exemple serait l'architecture Tilera.

La gestion des communications entre mémoires locales[modifier | modifier le wikicode]

On peut aussi classer les architectures distribuées selon la manière dont elles gèrent les communications entre mémoires locales. On distingue ainsi :

  • les architectures à passage de mémoire ;
  • les architectures Non Uniform Memory Access ;
  • les architectures Cache Only Memory Access.

Architectures à passage de messages[modifier | modifier le wikicode]

Sur les architectures à passage de messages, chaque mémoire est dédiée à un processeur. Les processeurs peuvent accéder à la mémoire d'un autre via le réseau local. Il va de soit que les communications entre les différents processeurs peuvent prendre un temps relativement long, et que ceux-ci sont loin d'être négligeables. Avec une organisation de ce genre, la qualité et les performances du réseau reliant les ordinateurs est très important pour les performances.

Architectures NUMA[modifier | modifier le wikicode]

La seconde classe d'architectures est celle des architectures NUMA. Comme avec les architectures distribuées, les processeurs possèdent chacun une mémoire locale réservée. Mais il y a une différence : chaque processeur voit toutes les mémoires locales rassemblées dans une seule grosse mémoire unique, un espace d'adressage global.

Espace d'adressage d'une architecture NUMA

Lors des lectures ou écritures, les adresses utilisées seront des adresses dans l'espace d'adressage global, dans la grosse mémoire. Si l'adresse est dans la mémoire locale du processeur, l'accès est direct. Dans le cas contraire, le système d'exploitation prend la relève et prépare une communication sur le réseau. Bien tirer partie de ces architectures demande de placer le plus possible les données en mémoire locale : l'idée est d'éviter les accès au réseau, qui sont lents.

Architectures COMA[modifier | modifier le wikicode]

Sur les architectures NUMA, migrer les données à la main peut nuire aux performances : il se peut que des migrations inutiles soient faites, le processeur n'ayant pas besoin des données transférées. Pour éviter ces copies inutiles, le meilleur moyen est de les faire à la demande : quand un processeur a besoin d'un bloc de mémoire (d'une donnée), celui-ci est migré dans sa mémoire locale. En faisant ainsi, chaque mémoire locale se comporte comme un cache, mais sans qu'il y aie de mémoire principale. On obtient alors une architecture COMA.

Ces architectures font cependant face à quelques problèmes. Premièrement, il faut pouvoir localiser la mémoire qui contient le bloc demandé à partir de l'adresse de ce bloc. Ensuite, on doit gérer la migration de blocs dans une mémoire locale pleine. Sur les architectures Simple-COMA, ces opérations sont déléguées au système d'exploitation. Seules les architectures Flat-COMA et Hierarchical-COMA effectuent ces opérations en matériel, en modifiant les circuits de cohérence des caches. La différence entre ces deux architectures tient dans le réseau d'interconnexion utilisé pour relier les processeurs.

Cohérence des caches à base de répertoires[modifier | modifier le wikicode]

Sur ces architectures, les protocoles à base d'espionnage de bus deviennent inefficaces : on doit utiliser d'autres méthodes. Une première méthode, qui fonctionne assez mal, est d'utiliser une hiérarchie de bus : certains bus connectent un nombre limité de processeurs entre eux, ces bus étant reliés par d'autres bus, et ainsi de suite. Mais la méthode la plus simple est d'utiliser un protocole de cohérence des caches à base de répertoires. Pour rappel, un répertoire est simplement une table de correspondance qui mémorise, pour chaque ligne de cache, toutes les informations nécessaires pour maintenir sa cohérence. Ce répertoire mémorise :

  • l'état de la ligne de cache (exclusive, shared, invalid, empty, etc) ;
  • la liste des processeurs dont le cache contient une copie de la ligne de cache.
Architecture distribuée avec cohérence des caches. On voit que chaque ordinateur contient plusieurs processeurs reliés avec mémoire partagée. Mais les ordinateurs eux-même sont reliés par un réseau local, la cohérence des caches entre ordinateurs étant alors gérée par un répertoire.

Localisation du nœud maison[modifier | modifier le wikicode]

Localiser les copies valides d'une ligne peut être assez compliqué : soit celle-ci est en mémoire locale, soit celle-ci est dans le cache d'un autre processeur (en état modified). On peut classer la méthode de localisation de la ligne de cache en trois grands catégories :

  • Dans le cas hiérarchique, le répertoire est répartit dans un arbre. Chaque répertoire (nœud) indique quel sous-arbre il faut vérifier pour obtenir la donnée demandée. Avec cette méthode, le répertoire utilise peu de bits (de mémoire) pour mémoriser les informations nécessaires. Mais le nombre d'accès mémoire peut rapidement augmenter et dépasser celui obtenu avec les autres solutions.
  • Dans le cas centralisé, on a un répertoire unique pour tous les processeurs. A chaque cache miss, le répertoire est consulté pour localiser la copie valide, afin de la charger dans le cache. Dans ces conditions, le répertoire doit répondre aux demandes de tous les processeurs, et devient rapidement un goulot d'étranglement quand les cache miss sont nombreux. En contrepartie, le nombre d'accès réseau nécessaire pour localiser une donnée est minimal : il suffit d'un seul accès réseau.
  • Dans le cas plat, on a un répertoire pour chaque processeur. Le répertoire à interroger est celui lié à la mémoire locale qui contient une copie valide ou invalide de la donnée. Ce répertoire peut alors indiquer où se situe la copie valide de la donnée.
Cohérence des caches à répertoire hiérarchique.
Cohérence des caches avec un répertoire centralisé.
Cohérence des caches - Répertoire étalé.

Listes des copies valides[modifier | modifier le wikicode]

Avec les répertoires plats, le répertoire doit mémoriser la liste des processeurs qui contiennent la donnée invalide : il faut que ces processeurs soient prévenus qu'ils doivent invalider la ligne de cache. Dans le cas le plus simple, le répertoire est une mémoire RAM, dont chaque entrée (chaque byte) mémorise les informations pour une ligne de cache : on parle de répertoire basé sur une mémoire. Une autre solution consiste à utiliser des bits de présence : le énième bit de présence indique si le énième processeur a une copie de la donnée dans son cache. Une autre solution consiste à numéroter les processeurs et à mémoriser la liste des numéros des processeurs dans le répertoire.

Toutes ces méthodes posent problème quand le nombre de processeur augmente trop. Ce problème peut être résolu en n'autorisant qu'un nombre maximal de copies d'une ligne de cache : soit un invalide automatiquement une copie quand ce nombre est dépassé, soit on interdit toute copie une fois ce maximum atteint. Une autre solution consiste à autoriser les copies en trop, mais toute invalidation de ces copies sera envoyée à tous les processeurs, même s'ils n'ont pas de copie de la donnée invalide.

Ces solutions sont cependant assez lourdes, et des alternatives existent. Ces alternatives consistent à mémoriser la liste des copies dans les caches eux-mêmes. Le répertoire n'identifie, pour chaque ligne de cache, qu'un seul processeur : plus précisément, il identifie la ligne de cache du processeur qui contient la copie. A l'intérieur d'une ligne de cache, la copie suivante (si elle existe) est indiquée dans les bits de contrôle. On parle de répertoires à base de caches.

Répertoire à base de caches