Cours 3 PP FR

Programmation parallèle
Dr El Hadji Bassirou TOURE

2021 - 2022
1
Hiérarchies de mémoire
▪ La mémoire vive ou RAM(Random Access Memory) est une partie de la
mémoire principale directement accessible par le CPU.
▪ Utilisée pour lire et écrire des données accessibles par le CPU de manière randomisée
▪ Les caractéristiques actuelles de cette mémoire sont :
▪ Sa fabrication à base de circuits intégrés ; accès direct, volatilité
▪ Différents types de RAM
▪ Static Random Access Memory (SRAM)
▪ Dynamic Random Access Memory (DRAM)
Dr. E_H_B. TOURE / programmation parallèle 2

▪ Static Random Access Memory (SRAM)
▪ Données stockées dans des transistors et nécessitent une constante alimentation
▪ Donc pas besoin de rafraichissement pour récupérer les données “récentes”. D’où le terme statique.
▪ Utilisée dans les mémoires caches.
▪ + : Faible consommation et rapide d’accès
▪ - : Faible capacité mémoire et gros coûts de fabrication.
▪ Dynamic Random Access Memory (DRAM)
▪ Données stockées dans des condensateurs qui se déchargent de toute énergie.
▪ Donc perte de données d’où un rafraichissement périodique est nécessaire.
▪ Utilisée pour implémenter la mémoire principale.
▪ + : Faibles coûts de fabrication et grosse capacité mémoire.
▪ - : Lent d’accès et grosse consommation d’électricité.

▪ La mémoire principale est construite en se basant sur la DRAM.
▪ Pour un processeur avec une fréquence d’horloge de 3 GhZ, correspondant à un temps
de cycle de 0.33ns, un accès mémoire prend entre 60 et 120 cycles machines.
▪ L’utilisation de caches peut réduire ce temps d’accès significativement.
▪ Les caches sont construits sur les puces des SRAMs qui sont plus rapides que celles des
DRAMs mais ont une plus petite capacité par zone d’unité et sont plus coûteux.
▪ Pour un système multiprocesseur dont chaque processeur dispose de son
propre cache en local, il y a un problème supplémentaire consistant à garder
une vue consistante de l’espace d’adressage pour tous les processeurs.
▪ Cohérence de cache
▪ Si un ou plusieurs processeurs modifient une copie d’un bloc mémoire dans leur cache locale, les
autres copies deviennent invalides et contiennent donc des valeurs incohérentes.

Caches
▪ Un cache est petit mais rapide
▪ Se situe entre le processeur et la mémoire principale.
▪ Construit avec la SRAM.
▪ Contient une copie d’un sous-ensemble de la mémoire principale.
▪ Les données sont déplacées en bloc entre le cache et la mémoire principale.
▪ Ces blocs de données sont appelées des blocs ou lignes de cache (cache blocks ou cache lines).
▪ Un bloc contient un petit nombre de mots
▪ La taille d’un bloc est fixe pour une architecture donnée

Gestionnaire de cache (cache controller)
▪ La gestion du cache est assurée par un gestionnaire de cache spécifique.
▪ Pendant l’exécution du programme,
▪ Le processeur définit les adresses mémoires à lire ou à écrire (spécifiées par les opérations load et
store) du programme machine.
▪ Le processeur transfère les adresses mémoires à la mémoire principale et attend jusqu’à ce que les
valeurs correspondantes soient retournées ou écrites.
▪ Après réception d’une requête d’accès mémoire du processeur, le gestionnaire de cache vérifie si
l’adresse mémoire spécifiée dans la requête appartient à un bloc du cache.
▪ Si c’est le cas, le cache a une réponse pertinente (cache hit) :
▪ Le mot demandé est envoyé au processeur depuis le cache.
▪ Si la ligne de cache n’existe pas dans le cache, alors échec du cache (cache miss) :
▪ La ligne de cache est copiée en premier à partir de la mémoire principale vers le cache avant que le
mot demandé ne soit envoyé au processeur.
▪ Le temps correspondant est appelé temps de pénalité d’échec du cache (cache miss penalty).

▪ Cache hit

▪ Cache miss

Politiques d’écriture
▪ Les lectures dominent les accès cache (25% pour les écritures).
▪ Il faut donc que celles-ci soit optimisées à fin de diminuer l’attente des processeurs.
▪ Lorsque le processeur effectue une requête d’accès en écriture sur un bloc de
mémoire stocké dans le cache,
▪ Le bloc correspondant est mis-à-jour
▪ La prochaine requête d’accès en lecture va accéder à la plus récente valeur.
▪ Quand le bloc correspondant est-il modifié dans la mémoire principale ?
▪ L’écriture simultanée (write through):
▪ L’information est écrite à la fois dans le bloc du cache et dans le bloc de la mémoire.
▪ La réécriture (write/copy back):
▪ L’information est écrite uniquement dans le bloc du cache.
▪ Le bloc modifié du cache est recopié en mémoire principale uniquement quand il est remplacé.

Write-through
▪ + : Les modules ayant un accès direct à la mémoire principale obtiennent
toujours la plus récente valeur de la mémoire.
▪ - : Chaque écriture dans le cache cause une écriture dans la mémoire
principale ce qui prend minimun 100 cycles processeurs pour finir.
▪ Pour éviter l’attente du processeur un tampon (buffer) d’écriture peut être utilisé pour
stocker les opérations d’écriture pendante dans la mémoire principale.
▪ Après cela le processeur peut continuer son exécution sans attendre que l’écriture dans la mémoire
principale finisse.

Write-back
▪ Le cache peut contenir des valeurs plus récentes que la mémoire principale.
▪ Un bloc mémoire modifié nest ’écrit dans la mémoire principale que lorsque le bloc dans
le cache est remplacé par un autre bloc mémoire.
▪ Pour cela, un bit (dirty bit) spécial est utilisé pour chaque bloc de cache.
▪ Ce bit indique si le bloc de cache a été modifié (1) ou non (0).
▪ + : Moins d’opérations d’écriture sur la mémoire principale.

▪ - : La mémoire principale peut contenir des valeurs invalides.

Write-back
▪ Si on un cahe miss pour une opération d’écriture, le processeur peut utiliser :
▪ Soit la méthode de l’écriture par allocation (write-allocate)
▪ Le bloc mémoire est d’abord mis dans le cache,
▪ La modification est effectuée comme spécifiée précédemment.
▪ Ou la méthode de l’écriture sans allocation(write no-allocate)
▪ Modifier la mémoire principale sans chargement dans le cache.
▪ Beaucoup moins utilisé.

Cohérence du cache
▪ Un système multiprocesseur est cache cohérent si elle assure une :
▪ Ecriture propagée (write propagation)
▪ Une valeur écrite par un processeur est visible en lecture par les autres processeurs
▪ Ecriture en série (write serialization)
▪ Deux écritures dans un même emplacement par deux processeurs sont vues dans un même ordre par
tous les processeurs
▪ Cohérence de la mémoire vs. consistance de la mémoire

▪ La cohérence ne s’occupe que du résultat des opérations de lecture et d’écriture sur un
même emplacement mémoire
▪ La consitance de la mémoire s’intéresse du résultat des opérations de lecture et
d’écriture dans différents emplacements mémoire
▪ La consistance s’intéresse à l’aspect “quand”de l’écriture propagée
▪ La cohérence ne s’intéresse que si l’écriture est éventuellement propagée

Système de cohérence de la mémoire
▪ Pour un système multiprocesseur où chaque processeur utilise un cache local,
▪ Il y a un problème pour garder une vue uniforme de l’espace d’adressage partagé.
▪ Si un processeur modifie sa copie d’un bloc mémoire dans son cache, alors les autres
copies deviennnent invalides et contiennent des valeurs inconsistantes.
▪ Exemple
▪ Soient trois processeurs P1, P2 et P3, tels que chaque processeur Pi ait son propre cache.
▪ P1, P2 et P3 sont connectés à une mémoire partagée M via un bus central.
▪ Les caches Ci utilisent la stratégie de l’écriture simultanée.
▪ Soit une variable u = 5 qui est dans M avant les efféctuées aux temps t1, t2, t3, t4
▪ t1 : P1 lit la variable u : Le bloc mémoire contenant u est chargé dans le cache C1 de P1.
▪ t2 : P3 lit la variable u : Le bloc mémoire contenant u est également chargé dans le cache C3 de P3.
▪ t3 : P3 écrit la valeur 7 dans u : La nouvelle valeur est aussi écrite dans la mémoire principale
▪ t4 : P1 lit la variable u, en accédant à une copie dans son cache.

▪ Exemple (suite)
▪ Problème : Au temps t4, P1 lit l’ancienne valeur (5) de u
▪ Pour une écriture simultanée :
▪ A t3, la nouvelle valeur 7 est écrite directement écrite dans la mémoire principale par P3
▪ Mais le cache de P1 n’a pas été modifié.
▪ Pour une réécriture :
▪ LA nouvelle valeur 7 n’est pas modifiée dans la mémoire principale.
▪ Si P2 lit la valeur après t3, il obtient 5 même si u n’est pas dans son cache.
▪ Le comportement du système pour des accès en lecture/écriture,
▪ Effectués par différents processeurs, sur le même emplacement mémoire,
▪ Est défini par le système de cohérence de la mémoire.

▪ Informellement, un mémoire est cohérent si pour chaque emplacement
mémoire, chaque lecture renvoie plus récente valeur écrite dans cet
emplacement.
▪ En utilisant l’ordre du programme, un mémoire est cohérent si :
▪ (1) Si un processeur écrit dans un emplacement x au temps t1
▪ Et lit dans x à un temps t2 > t1 , et si entre t1 et t2 aucun autre processus n’a écrit dans x,
▪ Alors P aura à t2 la valeur qu’il a écrite au temps t1.
▪ (2) Si P1 écrit dans x à t2, et P2 lit x à t2 > t1 alors
▪ P2 obtient la valeur écrite par P1 si entre t1 et t2 aucun processeur n’a écrit dans x
▪ Et si la période t2 – t1 > epsilon (La valeur écrite par un processeur ne sera visible qu’après un certain
temps).
▪ (3) Si P1 et P2 écrivent dans x, ces opérations sont sérialisées,
▪ Tous les processeurs verront les écritures dans le même ordre.
▪ Donc une écriture sérialisée globale est effectuée

Protocoles de cohérence du cache
▪ Pour un système de mémoire où une même copie d’un bloc du mémoire peut
être stocké dans plusieurs caches
▪ Donc chaque processeur doit avoir cohérente de la mémoire à travers son cache.
▪ Pour cela un protocole de cohérence du cache basé sur le matériel est utilisé.
▪ On distingue les protocoles basés sur
▪ La surveillance (snooping)
▪ Lorsqu’une opération sur un cache se produit et pouvant affecter la cohérence, le gestionnaire de cache
envoie une notification aux autres gestionnaires de cache :
▪ Ecriture-invalidation :
▪ Un processeur a l’exclusivité de ce bloc avant d’écrire en invalidant les autres copies.
▪ Ecriture-modification :
▪ Lorsque le processeur écrit : les autres copies de ce bloc partagé sont modifiés.
▪ L’utilisation d’un répertoire (directory-based)
▪ Un unique emplacement (répertoire) suit les copies partagés d’un bloc mémoire

Cohérence basée sur l’espionnage (Snooping-based coherence)
▪ Cohérence de caches avec une écriture simultanée
▪ Avant écriture, le gestionnaire de cache envoie un message d’invalidation
▪ Les prochaines lectures des autres processeurs vont déclencher un cache miss
▪ L’écriture simultanée est inefficiente

▪ Chaque opération d’écriture est reproduite dans la mémoire
▪ Exigence d’une très grande bande passante

▪ Cohérence de cache avec la réécriture
▪ Le dirty bit indique maintenant une propriété exclusive
▪ Exclusivité : Le cache contient à chaque fois une copie valide du bloc (il peut y écrire sans soucis)
▪ Les autres caches ont supprimé leurs lignes pour ce bloc
▪ Propriétaire : Le cache est chargé de répondre aux requêtes
▪ Sinon un load d’un autre processeur peut obtenir une donnée périmée)

▪ Protocole d’invalidation pour la récriture
▪ Un bloc peut être dans l’un de ces quatre états :
▪ M (modified) :
▪ Le cache contient la valeur actuelle du bloc mémoire et toutes les autres copies de bloc mémoire (dans les
autres caches ou dans la mémoire principale sont invalides) : Le bloc a été modifié dans le cache.
▪ Si le processeur veut modifier à nouveau le bloc, pas besoin d’envoyer une notification aux autres
▪ S (shared) :
▪ Le bloc dans la mémoire principale contient la valeur actuelle de même que tous les caches ayant des
copies valides pour ce cache.
▪ I (invalid) :
▪ Le cache contient une donnée invalide pour ce bloc.
▪ S’il veut effectuer une opration sur ce bloc de données, il doit envoyer une requête propriétaire de ce bloc.
▪ E (Exclusive):
▪ Un processeur qui veut modifier un bloc de données dans son cache, envoie une notification d’invalidation.
▪ Le bloc de données à modifier ne se trouve que dans le processeur qui veut la modifier (owner)
▪ Et dans la mémoire principale.
▪ Protocole d’invalidation pour la récriture
▪ Un processeur ne peut modifier un bloc que s’il en est le propriétaire
▪ Etapes pour devenir propriétaire :
▪ 1. Initialement, le processeur est le propriétaire de tous les blocs,
▪ Garde ce statut lorsqu’un processeur charge ses données dans son cache.
▪ 2. Si un processeur souhaite modifier le bloc dans son cache, il envoie une notification d’invalidation
▪ Après cela il devient le propriétaire exclusif de ce bloc
▪ 3. Si un autre processeur souhaite lire cette donnée, il envoie une requête au propriétaire
▪ 4. Le propriétaire lui envoie les données ainsi qu’à la mémoire principale
▪ 5. La mémoire principale met à jour le bloc modifié et récupère la propriété de ce bloc
▪ Si un processeur a besoin de ce bloc, il envoie une requête à la mémoire principale

▪ Opérations du protocole MESI
▪ Bus Read (BusRd):
▪ Résulte d’une opération de lecture du processeur (PrRd) dont le bloc de mémoire n’est pas stocké
dans son cache.
▪ La plus récente valeur de ce bloc mémoire lui est fourni par la mémoire principale ou un autre cache.
▪ Bus Read Exclusive (BusRdEx):
▪ Résulte d’une opération d’écriture (PrWr) d’un processeur dont le bloc de mémoire n’est pas stocké
dans son cache ou qui n’est pas dans le statut M dans son cache.
▪ Le système de mémoire fournit la plus récente valeur de ce bloc.
▪ Toutes les autres copies de ce bloc dans les autres caches deviennent invalides (I).
▪ Write Back (BusWr):
▪ Le contrôleur du cache écrit le bloc (dans son cache marqué M) dans la mémoire principale.
▪ Cette opération a lieu lorsque ce bloc est remplacé par un autre bloc dans le cache.
▪ Après cette opération, la mémoire principale contient la plus récente valeur de ce bloc.


▪ Opérations du protocole MESI : inconvénients
▪ Nécessite deux transactions réseau pour une opération de lecture suivie d’écriture sur
une même adresse :
▪ Transaction 1: BusRd pour passer de l’état I l’état S
▪ Transaction 2: BusRdX pour passer de l’état S à l’état M
▪ Cette inefficience existe même si le bloc mémoire n’est pas partagé par d’autres caches


Cohérence basée sur un répertoire (Directory-based
cache coherence)
▪ Soit une machine parallèle avec une mémoire distribuée.
▪ On assume que pour chaque mémoire locale un répertoire est défini
▪ Ce dernier spécifie pour chaque bloc dans la mémoire locale, quels autres processeurs
stockent actuellement une copie de ce bloc.
▪ Pour une machine avec p processeurs, le répertoire pourra utiliser un un vecteur de bit avec p bits de
présences et un nombre de bits d’état pour chaque bloc.
▪ Chaque bit de présence indique si un processeur particulier a une copie valide (1) ou pas (0) de ce bloc
de mémoire dans son cache.
▪ Un bit (dirty bit) additionnel est utilisé pour indiquer si la mémoire locale a une copie valide de ce bloc
mémoire (0) ou pas (1).
▪ Chaque répertoire est géré par un gestionnaire de répertoire qui met à jour le répertoire suivant les
requêtes observées dans le réseau.

cache coherence)
▪ Noeud home d’un bloc (node home) :

▪ Le noeud 0 est le noeud home du bloc orange et le noeud 1 celui du bloc bleu.
▪ Noeud demandé (Requesting node) :
▪ Noeud contenant le bloc demandé par le processeur

cache coherence)
▪ On suppose un espace d’adressage global :
▪ Chaque bloc mémoire a une adresse unique dans le système.
▪ Lorsqu’un échec de lecture (read miss) ou d’écriture (write miss) survient au
niveau du processeur i:
▪ Le gestionnaire du cache correspondant contacte le gestionnaire de répertoire pour
obtenir des informations sur le bloc mémoire auquel on essaie d’accéder :
▪ Si le bloc mémoire appartient à la mémoire locale et que cette dernière contient une copie valide
(dirty bit = 0) de ce bloc :
▪ Alors le bloc mémoire peut être chargé dans le cache avec un accès mémoire local.
▪ Sinon un accès distant doit être effectué :
▪ Une requête est envoyé au gestionnaire de répertoire du processeur propriétaire du bloc mémoire (node
home).

Cohérence basée sur un répertoire (Directory-based cache coherence)
▪ Example 1: read miss sur un bloc propre (dirty bit = 0)
▪ Lecture à partir de la mémoire principale du bloc bleu par le processeur 0 : (bloc propre)
▪ Un message de read miss est envoyé au noeud home du bloc demandé.

▪ Le répertoire home effectue les vérifications pour ce bloc.

▪ Example 1: read miss sur un bloc propre (dirty bit = 0)
▪ Lecture à partir de la mémoire principale du bloc bleu par le processeur 0 : (bloc propre)
▪ Un message de read miss est envoyé au noeud home du bloc demandé.

▪ Le répertoire home effectue les vérifications pour ce bloc :
▪ Si le sirty bit du bloc est 0, il répond avec le contenu de la mémoire,
▪ met presence[0] = 1 : qui signifie que le bloc est dans le cache du processeur 0

▪ Example 2: read miss sur un bloc sale (dirty bit = 1)
▪ Lecture à partir de la mémoire principale du bloc bleu par le processeur 0 :
▪ Bloc sale : la valeur actuelle est dans le cache de P2
▪ Si le dirty bit = 1, les données sont contenues par un unique autre processeur
▪ Le noeud home doit dire au noeud demandeur où trouver ces données
▪ Répondre en donnant l’idendité du processeur qui a les données dans son cache (“get it from P2”)

▪ 1. Si le dirty bit = 1, les données sont contenues par un unique autre processeur
▪ 2. Répondre en donnant l’idendité du processeur qui a les données dans son cache (“get it from P2”)
▪ 3. Le noeud demandeur envoie une requête au propriétaire
▪ 4. Le propriétaire change son état (S : lecture seule), et répond au noeud demandeur
▪ 1. Si le dirty bit = 1, les données sont contenues par un unique autre processeur
▪ 2. Répondre en donnant l’idendité du processeur qui a les données dans son cache (“get it from P2”)
▪ 3. Le noeud demandeur envoie une requête au propriétaire
▪ 4. Le propriétaire change son état (S : lecture seule), et répond au noeud demandeur
▪ 5. Le propriétaire répond également au noeud home qui efface le dirty bit, met à jour les bits de présence et met à jour la
mémoire locale.
cache coherence)
▪ Example 3: write miss
▪ Ecriture du bloc bleu par le processeur 0 :
▪ Le bloc est propre mais est partagé dans les caches de P1 et P2

cache coherence)

cache coherence)

▪ Après réception des accords d’invalidation, P0 peut effectuer son opération d’écriture
Programmation parallèle
Dr El Hadji Bassirou TOURE

2021 - 2022
38

Cours 3 PP FR

Transféré par

Droits d'auteur :

Formats disponibles

Cours 3 PP FR

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours 3 PP FR

Transféré par

Droits d'auteur :

Formats disponibles

Programmation parallèle

Dr El Hadji Bassirou TOURE

Dr. E_H_B. TOURE / programmation parallèle 2

Dr. E_H_B. TOURE / programmation parallèle 3

Dr. E_H_B. TOURE / programmation parallèle 4

Dr. E_H_B. TOURE / programmation parallèle 5

Dr. E_H_B. TOURE / programmation parallèle 6

Dr. E_H_B. TOURE / programmation parallèle 7

Dr. E_H_B. TOURE / programmation parallèle 8

Dr. E_H_B. TOURE / programmation parallèle 9

Dr. E_H_B. TOURE / programmation parallèle 10

▪ + : Moins d’opérations d’écriture sur la mémoire principale.

Dr. E_H_B. TOURE / programmation parallèle 11

Dr. E_H_B. TOURE / programmation parallèle 12

▪ Cohérence de la mémoire vs. consistance de la mémoire

Dr. E_H_B. TOURE / programmation parallèle 13

Dr. E_H_B. TOURE / programmation parallèle 14

Dr. E_H_B. TOURE / programmation parallèle 15

Dr. E_H_B. TOURE / programmation parallèle 16

Dr. E_H_B. TOURE / programmation parallèle 17

▪ L’écriture simultanée est inefficiente

Dr. E_H_B. TOURE / programmation parallèle 18

Dr. E_H_B. TOURE / programmation parallèle 19

Dr. E_H_B. TOURE / programmation parallèle 21

Dr. E_H_B. TOURE / programmation parallèle 22

Dr. E_H_B. TOURE / programmation parallèle 23

Dr. E_H_B. TOURE / programmation parallèle 24

Dr. E_H_B. TOURE / programmation parallèle 25

Dr. E_H_B. TOURE / programmation parallèle 26

▪ Noeud home d’un bloc (node home) :

Dr. E_H_B. TOURE / programmation parallèle 27

Dr. E_H_B. TOURE / programmation parallèle 28

▪ Un message de read miss est envoyé au noeud home du bloc demandé.

Dr. E_H_B. TOURE / programmation parallèle 29

▪ Un message de read miss est envoyé au noeud home du bloc demandé.

Dr. E_H_B. TOURE / programmation parallèle 30

Dr. E_H_B. TOURE / programmation parallèle 31

Dr. E_H_B. TOURE / programmation parallèle 34

Dr. E_H_B. TOURE / programmation parallèle 35

Dr. E_H_B. TOURE / programmation parallèle 36

Dr El Hadji Bassirou TOURE

Vous aimerez peut-être aussi