Gei 431 Architecture des ordinateurs II – Frédéric Mailhot Les multiprocesseurs Jusquà maintenant, nous avons parlé longuement des microprocesseurs. Nous

Gei

431

Architecture des ordinateurs II – Frédéric Mailhot

Les multiprocesseurs

Jusqu’à maintenant, nous avons parlé longuement des microprocesseurs.

Nous allons maintenant étudier les multiprocesseurs, comment ils fonctionnent, quels sont les problèmes particuliers qui apparaissent.

© 2001 Frédéric Mailhot Université de Sherbrooke

Les

mu

ltip

rocs

seu

rs

Les multiprocesseurs

• Périodiquement, depuis les années ’60, on a prédit la fin des uniprocesseurs, au profit des multiprocesseurs

• On parle souvent de la vitesse de la lumière comme d’une limite proche d’être atteinte: C = 3 X 10 ^ 8 m/s – » 15 cm / 0,5 ns (2 GHz)

On dit que des architectures nouvelles (multiprocesseurs) devront être utilisées pour continuer d’améliorer la performance

• Mais… depuis 1985, l’augmentation de performance des processeurs est la plus importante depuis la fin des années ’50!


Les

mu

ltip

rocs

seu

rs

Les multiprocesseurs – pourquoi

• En supposant que les microprocesseurs demeurent la technologie dominante pour les uniprocesseurs, il semble naturel d’imaginer en connecter plusieurs ensemble pour augmenter la performance

• Il n’est pas clair que le taux d’innovation au niveau de l’architecture pourra se continuer longtemps

• Il semble qu’il y ait des progrès constants dans les 2 domaines où les machines parallèles ont le plus de difficulté: le logiciel et les interconnexions


Les

mu

ltip

rocs

seu

rs

Les types de multiprocesseurs

• Taxonomie proposée par Flynn dans les années ’60: SISD (Single Instruction Single Data): uniprocesseur

SIMD (Single Instruction Multiple Data): plusieurs processeurs, qui exécutent en parallèle les mêmes instructions sur plusieurs données

MISD (Multiple Instruction Single Data): pas d’exemple connu

MIMD (Multiple Instruction Multiple Data): plusieurs processeurs qui opèrent de façon indépendantes ou semi-indépendantes sur leurs données


Les

mu

ltip

rocs

seu

rs

Types de multiprocesseurs utilisés

• Les premiers multiprocesseurs étaient du type SIMD, et cette architecture est encore utilisée pour certaines machines spécialisées

• Le type MIMD semble être la cible de choix de nos jours pour des ordinateurs d’application courante: Les MIMD sont flexibles: on peut les utiliser comme

machines à un seul utilisateur, ou comme machines multi-programmées

Les MIMD peuvent être bâties à partir de processeurs existants


Les

mu

ltip

rocs

seu

rsAu centre des processeurs MIMD: la mémoire

• On peut classifier les processeurs MIMD en deux classes, dépendant du nombre de processeurs dans la machine. Ultimement, c’est l’organisation de la mémoire qui est affectée: Mémoire partagée centralisée (centralized shared

memory)

Mémoire distribuée


Les

mu

ltip

rocs

seu

rs

Cohérencede lamémoirecache

Architecture possible des multiprocesseurs

Multiprocesseur

Mémoire partagée centralisée(UMA)


Basée surl’espionnage

(bus)

Espace d’adressageunique (NUMA)

Espace d’adressageprivé (multi-ordinateurs)

Write invalidateprotocol

Write updateprotocol

Write-through(mémoire centrale)

Write-back(mémoire centrale)

Basée surun répertoire


Les

mu

ltip

rocs

seu

rs

Mémoire partagée centralisée


Les

mu

ltip

rocs

seu

rs

Mémoire partagée centralisée

• La mémoire partagée centralisée (centralized shared memory) est utilisée par des machines d’au plus une douzaine de processeurs en 1995

• On utilise un bus qui connecte les processeurs et la mémoire, avec l’aide de mémoire cache locale.

• On appelle ce type de structure de mémoire le Uniform Memory Access (UMA).


Les

mu

ltip

rocs

seu

rs



Les

mu

ltip

rocs

seu

rs


Multiprocesseur




Les

mu

ltip

rocs

seu

rs


• La mémoire distribuée est utilisée dans des machines utilisant « beaucoup » de processeurs, qui requièrent une bande passante trop grande pour une mémoire unique

• « Beaucoup » tend à diminuer avec le temps, puisque la performance des processeurs continue d’augmenter plus rapidement que celle de la mémoire

• Avantages de la mémoire distribuée: il est plus facile d’augmenter la bande passante de la mémoire si la plupart des accès mémoire sont locaux. La latence est aussi améliorée lorsqu’on utilise la mémoire locale


Les

mu

ltip

rocs

seu

rs

Modèles de mémoire distribuée

• Il existe deux modèles de mémoire distribuée: Espace d’adressage unique, accessible par tous les processeurs,

mais distribué parmi les processeurs. On dit de ce système qu’il est Non-Uniform Memory Access (NUMA), parce que le temps d’accès à la mémoire dépend de l’endroit où se trouve la région qui est adressée (locale ou distante)

Espace d’adressage privé, où chaque processeur a un accès exclusif à la mémoire locale. On appelle parfois ces systèmes des systèmes multi-ordinateurs (multi-computers)

• Pour ces deux modèles, le mode de communication diffère: Pour la mémoire partagée, la communication se fait de façon

implicite, en écrivant/lisant la mémoire. Pour la mémoire privée, on doit utiliser des messages explicites

entre les processeurs pour passer l’information de l’un à l’autre, d’où leur nom de machines à passage de message (Message Passing Machines)


Les

mu

ltip

rocs

seu

rs


Multiprocesseur






Les

mu

ltip

rocs

seu

rsAvantages et inconvénients des mécanismes de communication

• Mémoire partagée: Mécanisme bien connu Facile à programmer (et facile de bâtir des compilateurs) Meilleure utilisation de la bande passante (protection de

la mémoire au niveau du matériel, et non au niveau du système d’exploitation

Possibilité d’utiliser des techniques de caching

• Message-passing: Matériel simplifié Communication explicite, exigeant l’intervention du

programmeur


Les

mu

ltip

rocs

seu

rs

Paramètres de communication

• Bande passante: Limitée par l’interconnection ou par les processeurs eux-

mêmes?

• Temps de latence Temps de préparation de l’envoyeur + temps de vol + (taille du

message) / (bande passante) + temps de réception.

• Élimination apparente de la latence (latency hiding) Comment minimiser l’impact de la latence?

Impact au niveau du logiciel


Les

mu

ltip

rocs

seu

rs

Limites de la programmation parallèle

• Loi de Amdahl:

Speedup = 1_____________

Fraction(améliorée) + (1 - Fraction(améliorée)

Speedup(amélioré)

• Soit un speedup désiré de 80 avec 100 processeurs. Quelle portion de l’application peut être séquentielle? Fraction(parallèle) = 0.9975 --> 0,25% maximum peut être

séquentielle


Les

mu

ltip

rocs

seu

rs

Limites de la programmation parallèle (II)

• Importance de la latence: Dans les machines parallèles d’aujourd’hui, l’accès à de

l’information sur un autre processeur peut prendre entre 50 et 10,000 coups d’horloge.

• Soit une machine qui prend 2,000 ns pour un accès mémoire à distance, une horloge de 10 ns, et un CPI de base de 1.0. Quelle est l’impact sur le CPI si 0,5% des instructions font un accès mémoire à distance? Accès à distance = 2,000 / 10 = 200 coups d’horloge

CPI = 1.0 + 0,5% X 200 = 2.0


Les

mu

ltip

rocs

seu

rsLes systèmes à mémoire partagée centralisée

• Dans ce qui suit, nous allons maintenant étudier comment faire un système parallèle MIMD qui utilise de la mémoire partagée centralisée


Les

mu

ltip

rocs

seu

rsLa cohérence de la mémoire – qu’est-ce que c’est?

• Comme pour les uniprocesseurs, il est essentiel pour la performance des multiprocesseurs que le temps d’accès à la mémoire soit raisonnable

• L’utilisation de mémoire cache est donc encore de première importance

• Puisqu’on est en présence de plusieurs machines, il se peut qu’une adresse mémoire utilisée par une machine « A » soit modifiée par une machine « B ». Il faut s’assurer que les données gardées dans les mémoires caches soient les mêmes pour tous les processeurs. C’est ce qu’on appelle la « cohérence » de la mémoire


Les

mu

ltip

rocs

seu

rsExemple du problème de cohérence de cache

Temps Événement Cache du CPU A

Cache du CPU B

Contenu de la mémoire, adresse « X »

0 1

1 CPU A lit X 1 1

2 CPU B lit X 1 1 1

3 CPU A écrit 0 dans X

0 1 0


Les

mu

ltip

rocs

seu

rs

Définition de la cohérence de la mémoire

• Définition 1: Chaque lecture de la mémoire retourne la valeur écrite le plus récemment Cette définition traite de 2 concepts:

• La cohérence (est-ce que la lecture retourne la bonne valeur)

• La consistence (quand est-ce qu’une valeur écrite devient visible?)


Les

mu

ltip

rocs

seu

rs

Définition de la cohérence

• La mémoire est cohérente si: Un read par le processeur P à l’adresse X qui suit un

write à l’adresse X par le processeur P, sans qu’il n’y ait eu d’écriture par d’autres processeurs, retourne toujours la valeur écrite par P

Un read par P à l’adresse X qui suit un write par Q à l’adresse X retourne la valeur écrite par Q si les 2 événements sont assez distants dans le temps

Les écritures au même endroit sont sérialisées• Les écritures par deux processeurs P et Q à l’adresse X

sont vues dans le même ordre par tout processeur du système


Les

mu

ltip

rocs

seu

rs

Fonction de la mémoire cache

• La mémoire cache a deux fonctions: La migration: On transporte les valeurs dans la mémoire

cache locale pour diminuer le temps d’accès

La réplication: Lorsqu’une donnée est modifiée, toutes les caches qui la détiennent doivent être infformées


Les

mu

ltip

rocs

seu

rs Dans un système à multiprocesseur, comment connaître l’état des différentes caches?

• Il existe deux classes de protocoles de cohérence de cache: Basé sur un répertoire (directory based): l’état de

partage des adresses de la mémoire est conservé dans un endroit unique, le directory

Basé sur l’espionnage (snooping): chaque mémoire cache est branchée sur un bus de mémoire commun, et écoute continuellement ce qui se passe


Les

mu

ltip

rocs

seu

rs



Multiprocesseur




(bus)




Les

mu

ltip

rocs

seu

rs

Méthodes de maintient de la cohérence

• Il y a deux façons de s’assurer de la cohérence des caches: Obtenir l’accès exclusif de l’adresse mémoire visée Mettre à jour les autres copies

• L’usage exclusif de la mémoire est appelé le protocole d’écriture invalidante (write invalidate protocol). Le principe est le suivant: suivant l’écriture d’une donnée, toutes les autres copies de cette donnée sont marquées comme étant invalides.

• La mise à jour des autres copies est appelée le protocole d’écriture et mise à jour (write update protocol, aussi appellé write broadcast protocol). Ici, chaque écriture est suivie de messages de mises à jour pour les autres versions de la même donnée.


Les

mu

ltip

rocs

seu

rs



Multiprocesseur



(bus)




Les

mu

ltip

rocs

seu

rs

Méthodes de maintient de la cohérence (II)

• Les deux protocoles d’opération ont des caractéristiques différentes qui infuencent leur performance: Dans le cas d’écritures multiples au même espace mémoire,

sans lecture intermédiaire:• Le protocole de mise à jour utilisera de multiples appels aux

autres machines• Le protocole d’usage exclusif n’utilisera qu’un seul accès

d’invalidation.

Il est possible de regrouper les mots mémoire pour le protocole d’usage exclusif, et ainsi diminuer le nombre d’invalidations nécessaires lors d’écriture à des adresses adjacentes (on invalide toute un bloc de mémoire)

Cette possibilités n’existe pas pour le protocole de mise à jour.


Les

mu

ltip

rocs

seu

rs

Méthodes de maintient de la cohérence (III)

• Le délai nécessaire entre l’écriture d’une donnée et sa lecture sur une autre machine est habituellement plus petit avec un protocole de mise à jour

• Le protocole d’usage exclusif est maintenant le plus utilisé dans les machines multiprocesseurs


Les

mu

ltip

rocs

seu

rsImplémentation du protocole d’usage exclusif

• Comment réaliser ce protocole? Sur un multiprocesseur à petite échelle, on utilise le bus comme moyen privilégié de synchronisation. Pour pouvoir écrire dans la mémoire, un processeur

doit d’abord obtenir le contrôle du bus.

Ensuite, l’adresse de la mémoire modifiée est envoyée sur le bus.

Tous les autres processeurs sont continuellement à l’écoute. Si une écriture est faite à une adresse mémoire qui est dans leur cache, cette adresse est invalidée.


Les

mu

ltip

rocs

seu

rsImplémentation du protocole d’usage exclusif (II)

• Pour la lecture, s’il y a un “cache miss”, le processeur va demander la donnée sur le bus. Ici, il y a 2 possibilités: Si la mémoire centrale est continuellement mise à jour

(write-through), alors elle peut fournir la valeur demandée.

Si au contraire on utilise l’écriture avec délai (write-back), il se peut que ce soit un processeur qui détienne la valeur la plus récente. Pour ce type de machine, les processeurs doivent écouter le bus pour la lecture aussi, et fournir la valeur demandée en interrompant la lecture de la mémoire centrale.


Les

mu

ltip

rocs

seu

rs



Multiprocesseur



(bus)






Les

mu

ltip

rocs

seu

rsImplémentation du protocole d’usage exclusif (III)

• On peut ajouter de l’information dans la mémoire cache locale pour améliorer le rendement du système (write-back). On utilise alors un bit de partage: Lors de l’écriture d’une adresse mémoire, on met le bit de

partage à 0. Lors d’écritures subséquentes, on n’informe personne de

l’écriture si le bit de partage est toujours à 0. Si un autre processeur lit cette adresse mémoire, le bit de

partage est mis à 1, et une écriture subséquente va donc générer une invalidation.

• Note: comment permettre l’accès efficace de la mémoire cache à la fois par le processeur et par le système de surveillance du bus? On peut tout simplement dédoubler l’information de partage. Une façon de faire est d’utiliser des caches multi-niveaux.


Les

mu

ltip

rocs

seu

rs

Protocole « write-invalidate »


Les

mu

ltip

rocs

seu

rs

Protocole « write – invalidate » unifié


Les

mu

ltip

rocs

seu

rs



Multiprocesseur




(bus)









Les

mu

ltip

rocs

seu

rsGestion de la mémoire pour des machines à beaucoup de processeurs

• Lorsqu’on désire utiliser beaucoup de processeurs, la méthode de mémoire partagée centralisée ne fonctionne plus: les délais deviennent trop importants Solution: utiliser de la mémoire partagée distribuée

• Problème (toujours le même): cohérence des mémoires cache. Solution possible: on défend d’utiliser de la mémoire

cache pour les données partagées!• C’est la solution adoptée entres autres par le Cray T3D.

Chaque nœud possède une mémoire cache uniquement pour ses données privées (locales).


Les

mu

ltip

rocs

seu

rsProblème de cohérence de cache pour des machines à beaucoup de processeurs

• Solution possible: gestion logicielle (simplifie le matériel), mais… Pas de mécanismes efficaces pour « passer » le

problème au compilateur, et faire gérer le problème de cohérence sans l’intervention du programmeur

On ne peut accéder à des adresses adjacentes de façon efficace.

• Meilleure solution: utiliser un système matériel qui assure la cohérence des caches


Les

mu

ltip

rocs

seu

rsMémoire partagée distribuée: le répertoire, un protocole plus efficace que l’espionnage

• Au lieu de faire de l’espionnage (snooping), du bus de connexion des processeurs, on peut utiliser un répertoire qui indique l’état de la mémoire.

• En particulier, le répertoire peut indiquer l’état de chaque bloc de mémoire qui peut se retrouver dans la mémoire cache. On y indique par exemple quelles mémoires cache ont

des copies de quels blocs de mémoire, et si la mémoire a été modifiée (dirty bit) ou non.


Les

mu

ltip

rocs

seu

rs

Mémoire partagée distribuée: le répertoire

• Problème avec le répertoire: La quantité d’information à emmagasiner est

proportionnelle au nombre de blocs de mémoire multiplié par le nombre de processeurs. Pour plus de 100 processeurs, on peut avoir un problème d’espace requis pour le répertoire…

• Autre problème: le répertoire lui-même peut devenir le goulot d’étranglement (trop de requêtes).

• Solution: Le répertoire lui-même peut être distribué de concert avec la mémoire


Les

mu

ltip

rocs

seu

rsSystème multiprocesseur à répertoire distribué


Les

mu

ltip

rocs

seu

rs

Protocole de répertoire simple

• Pour fonctionner correctement, le système doit pouvoir gérer 2 types d’opérations: Les lectures manquées (« read miss ») Les écritures dans un bloc de mémoire partagée

• Pour ce faire, le répertoire doit contenir l’information suivante pour chaque bloc de mémoire: Mémoire partagée (un ou plusieurs processeurs utilisent ce bloc

mémoire, qui est à jour) Mémoire non en cache (aucun processeur n’utilise une copie de ce

bloc mémoire) Mémoire exclusive ( un et un seul processeur utilise ce bloc, qui a été

écrit et donc qui n’est plus à jour)

• Il faut savoir quels processeurs utilisent le bloc mémoire s’il est partagé. On peut utiliser un vecteur de bits par bloc mémoire pour gérer cette information


Les

mu

ltip

rocs

seu

rs

Protocole de répertoire simple (2)

• On suppose que la machine contient un grand nombre de processeurs.

• Il n’est plus possible d’utiliser le bus pour résoudre les problèmes d’accès simultanés.

• De plus, on suppose que la communication se fait de point à point (pourquoi?)


Les

mu

ltip

rocs

seu

rs

Protocole d’utilisation de répertoire


Les

mu

ltip

rocs

seu

rs

Protocole d’utilisation de répertoire

Documents

Gei 431 Architecture des ordinateurs II – Frédéric Mailhot Les multiprocesseurs Jusquà maintenant, nous avons parlé longuement des microprocesseurs. Nous