ORGANISATION ET ARCHITECTURE DES ORDINATEURS deuxième

partie
(SWENG 213)

Génie Logiciel 2 (10h CM, 4h TD)

vendredi 8H-12H
Par Yves EYENGA
 CHAPITRE 1 : Mémoire cache

Objectif du cours : Présenter la mémoire cache et son fonctionnement.

Durée du chapitre : 01 séance de 05h

CHAPITRE 1 : LA MÉMOIRE CACHE

I. DEFINITION
Plusieurs niveaux de mémoire dans un ordinateur
CHAPITRE 1 : LA MÉMOIRE CACHE

LES MEMOIRES
On rappelle que:

Une mémoire est:

 Dispositif capable d’enregistrer, de conserver et de restituer des informations
 Informations binaires pour un ordinateur

On classe les mémoires selon

 Caractéristiques : capacité, débit ...
 Type d’accès : séquentiel, direct ...
CHAPITRE 1 : LA MÉMOIRE CACHE

Caractéristiques et méthodes d’accès des mémoires

 Temps d’accès: Temps s’écoulant entre le lancement d’une opération de lecture/écriture et son accomplissement
 Cycle mémoire: Temps minimal entre 2 accès successifs à la mémoire. Il est supérieur au temps d’accès Car besoin
d’opérations supplémentaires entre 2 accès (stabilisation des signaux, synchronisation ...)
 Débit: Nombre d’informations lues ou écrites par seconde. Ex: 300 Mo/s
 Volatilité: Conservation ou disparition de l’information dans la mémoire hors alimentation électrique de la mémoire
 Accès séquentiel: Une information n’est accessible que si on a d’abord parcouru toutes les informations précédentes
 Accès direct: parce que chaque information a une adresse propre, on y accède directement à partir de cette dernière
(Ex: mémoire centrale )
 Accès semi-séquentiel: Intermédiaire entre séquentiel et direct. (Ex: DD on a un accès direct au cylindre et un accès
séquentiel au secteur sur le cylindre)
 Accès associatif/par le contenu: Parce que l’information est identifiée par une clé, On y accède via cette dernière.
Ex: Mémoire cache
CHAPITRE 1 : LA MÉMOIRE CACHE

LA MÉMOIRE CACHE
 Pour la lecture d’instructions et des données, le processeur a besoin d'un débit permanent
→ Ne pas être inactif pendant l’attente

Problème
 La Mémoire centrale où se trouvent ces données et instruction est beaucoup trop lente pour assurer ce débit

Solution: Se server d’une mémoire intermédiaire entre la mémoire centrale et le processeur qui soit très rapide
→ Mémoire cache (ou cache tout court)
La mémoire cache (également appelée antémémoire ou mémoire tampon) est une mémoire rapide permettant de
réduire les délais d'attente des informations stockées en mémoire vive.
En effet, la mémoire centrale de l'ordinateur possède une vitesse bien moins importante que le processeur. Il existe
néanmoins des mémoires beaucoup plus rapides, mais dont le coût est très élevé. La solution consiste donc à inclure ce
type de mémoire rapide à proximité du processeur et d'y stocker temporairement les principales données devant être
traitées par le processeur
CHAPITRE 1 : LA MÉMOIRE CACHE

LA MÉMOIRE CACHE
CHAPITRE 1 : LA MÉMOIRE CACHE

LA MÉMOIRE CACHE
Le choix de cette approche ne peut se faire sans compromis

Problème
 Pour être efficace en terme de débit, la mémoire cache doit être petite (quelques centaines de Ko à quelques dizaines
de Mo).
→ Elle ne peut par conséquent pas stocker tous les programmes en cours d’exécution, ainsi que les données y
afférentes

Solution
 Mise en place d’algorithmes pour « anticiper » et mettre dans le cache les données/instructions avant que le CPU en
ait besoin
 Rechercher le bon compromis entre tailles, types de cache (données/instructions), niveaux de cache, techniques
d'accès au cache ... pour de meilleures performances
CHAPITRE 1 : LA MÉMOIRE CACHE

ORGANISATION DU CACHE EN NIVEAUX

Plusieurs niveaux d’organisation possibles du cache

 On dénombre en général jusqu'à 3 niveaux (L1, L2 et L3)

 Toutefois, même si cela est rare, certains processeurs ont un quatrième niveaux (L4)

 La mémoire cache de premier niveau (appelée L1 Cache, pour Level 1 Cache) est directement intégrée dans le
processeur. Elle se subdivise en 2 parties :
• La première est le cache d'instructions, qui contient les instructions issues de la mémoire vive décodées lors du
passage dans les pipelines.
• La seconde est le cache de données, qui contient des données issues de la mémoire vive et les données
récemment utilisées lors des opérations du processeur.
 Les caches du premier niveau sont très rapides d'accès. Leur délai d'accès tend à s'approcher de celui des registres
internes aux processeurs.
CHAPITRE 1 : LA MÉMOIRE CACHE

ORGANISATION DU CACHE EN NIVEAUX

 La mémoire cache de second niveau (appelée L2 Cache, pour Level 2 Cache) est une extension du cache L1.
 Tous les processeurs récents disposent d'un cache L2 intégré. Sa taille est actuellement comprise entre 128 Ko et
512 Ko en fonction du microprocesseur.
 La mémoire cache de troisième niveau (appelée L3 Cache, pour Level 3 Cache) précédemment située au niveau
de la carte mère a récemment aussi été intégrée dans la puce..
 Le niveau L3 est très souvent utilisé pour l'échange de données entre cores dans un processeur multi-core

 L1 et L2 généralement spécifique à un core

 Cache L1 généralement scindé en 2 parties : un dédié aux instructions et l'autre aux données
CHAPITRE 1 : LA MÉMOIRE CACHE

ORGANISATION DU CACHE EN NIVEAUX

De façon générale,
 Cache Li+1 joue le rôle de cache pour le niveau Li
 Cache Li+1 plus grand que Li mais moins rapide en temps d'accès aux données

Tous ces niveaux de cache permettent de réduire les temps de latence des différentes mémoires lors du traitement et
du transfert des informations. Pendant que le processeur travaille, le contrôleur de cache de premier niveau peut
s'interfacer avec celui de second niveau pour faire des transferts d'informations sans bloquer le processeur. De même,
le cache de second niveau est interfacé avec celui du troisième niveau, pour permettre des transferts sans bloquer le
fonctionnement normal du processeur
CHAPITRE 1 : LA MÉMOIRE CACHE

ORGANISATION DU CACHE EN NIVEAUX

Relations entre les niveaux de cache
 Cache inclusif : Le contenu du niveau L1 se trouve aussi dans L2
 Cache exclusif : Le contenu des niveaux L1 et L2 sont différents
Comment dans ce cas déterminer la taille globale?
 Cache inclusif : Taille globale du cache : celle du cache L2
 Cache exclusif : Taille globale du cache : taille L1 + taille L2
Quelles sont les avantages et les inconvénients de chaque approche?
 Cache inclusif (historiquement le plus utilisé)
• Cache L2 plus performant
• Mais taille totale plus faible
• Et contraintes sur la taille de L2 (ne doit pas être trop petit par rapport à L1)
 Cache exclusif
• Cache plus grand au total
• L2 de taille quelconque
• Mais doit gérer la non duplication des données : prend du temps, L2 moins performant
CHAPITRE 1 : LA MÉMOIRE CACHE

PERFORMANCE
Lorsque l’on veut évaluer la performance d’une mémoire cache, l’on peut évaluer:

 Taux de succès le plus élevé possible

 Succès : la donnée voulue par le CPU est dans le cache L1
• Ou la donnée voulue par le cache L1 est dans le cache L2 ...
 Échec : la donnée voulue n'y est pas
• Doit la charger à partir du niveau de cache suivant ou de la mémoire centrale

 Temps d'accès à la mémoire, latences : nombre de cycle d'horloges requis pour

 Lire une donnée dans le cache en cas de succès
 Aller la récupérer en cas d'échec au niveau supérieur

NB: Latences dépendent de la taille des niveaux et de l'organisation des données dans les niveaux
CHAPITRE 1 : LA MÉMOIRE CACHE

PERFORMANCE
La performance peut aussi être évaluée à partir de la taille du cache et du nombre de niveaux

 Augmentation de la taille de la mémoire cache

• Augmente le taux de succès
• Mais ne gagne pas forcément en performance car augmentation du temps d'accès proportionnellement à la taille
 Augmentation du nombre de niveaux (plus de 3)
• Pas de gain supplémentaire vraiment significatif
 Cache inclusif
• Le cache L2 doit être bien plus grand que le cache de niveau L1 car sinon on stocke peu de données
supplémentaires dans L2 par rapport à L1 et donc taux de succès de L2 faible
 Ne pas oublier le coût élevé de ce type de RAM
CHAPITRE 1 : LA MÉMOIRE CACHE

LOCALITE ET PRE-FETCHING
 Localité temporelle
• Une donnée référencée à un temps t aura de très fortes chances d'être référencée dans un futur proche

 Localité spatiale
• Si une donnée est référencée à un temps t, alors il y a de très fortes chances que les données voisines le soient
dans un futur proche

Ex: for (i=0; i < N; i++)

somme += A[i];
 Localité spatiale : A[i] (A[i+1], A[i+2]...)
 Localité temporelle : N, A, i
CHAPITRE 1 : LA MÉMOIRE CACHE

LOCALITE ET PRE-FETCHING

 Pour améliorer le taux de succès du cache

→ Pre-fetching : chargement en avance des données dont le CPU devrait avoir besoin

 Algorithmes de pre-fetching sont basés sur les principes de localité

 Localité temporelle
• Garder en mémoire cache les dernières données référencées par le programme
 Localité spatiale
• Charger en avance les données/instructions contiguës à une donnée/instruction référencée
CHAPITRE 1 : LA MÉMOIRE CACHE

COHERENCE DONNEES CACHE/MEMOIRE

 Lecture/écriture en mémoire centrale via cache
 Le cache contient une copie d'une partie de la mémoire centrale : nécessité de cohérence mutuelle
 Opérations de lecture/écriture sont effectuées dans le cache avec répercussion sur la mémoire centrale
 Opération de lecture
 Pas de modification de valeurs : toujours cohérent
 Opération d'écriture
 Modification du contenu du cache : la partie équivalente en mémoire centrale n'est plus cohérente
 Cohérence cache/mémoire en écriture, 2 techniques:
 Écriture simultanée (write-through)
• Quand on écrit un mot d'une ligne du cache, on écrit simultanément le mot de la même ligne en mémoire
centrale
• Écriture plus longue car accès mémoire centrale
 Écriture différée ou réécriture (write-back)
• On n'écrit le mot que dans la ligne du cache
• Quand cette ligne est supprimée du cache, on l'écrit en mémoire centrale
CHAPITRE 1 : LA MÉMOIRE CACHE

COHERENCE DONNEES CACHE/MEMOIRE

 Intérêt du write-back
 Limitation des écritures en mémoire centrale

 Inconvénient du write-back
 Problème si d'autres éléments accèdent à la mémoire en écriture
• Périphériques en mode DMA (Direct Memory Access)
• Multi-processeurs avec mémoire commune
• Processeurs multi-cores
 Nécessite alors des algorithmes supplémentaires pour gérer la cohérence
CHAPITRE 1 : LA MÉMOIRE CACHE

CORRESPONDANCE LIGNES CACHE/MEMOIRE

 Mémoire cache
 Contient des lignes de mots de la mémoire centrale

 Trois méthodes pour gérer la correspondance entre une ligne dans le cache et une ligne de la mémoire centrale
 Correspondance directe
 Correspondance associative totale
 Correspondance associative par ensemble
 Exemples avec
 Lignes de 32 octets
 Mémoire cache de 512 Ko : 16384 lignes
 Mémoire centrale de 128 Mo : doit être gérée via les 512 Ko de cache et ses 16384 lignes
CHAPITRE 1 : LA MÉMOIRE CACHE

CORRESPONDANCE LIGNES CACHE/MEMOIRE

 Correspondance directe (direct mapped)
 L lignes en cache
 La ligne d'adresse j en mémoire centrale sera gérée par la ligne i en cache avec
 i = j mod L
 A partir de l'adresse d'une ligne en mémoire on sait directement dans quelle ligne du cache elle doit se trouver
 Exemple (on reprend l’exemple précédent)
 Chaque ligne du cache correspond à 128 x 1024 x 1024 / 16384 = 8192 octets = 256 lignes
 Une ligne i du cache contiendra à un instant donné une des
 256 lignes j de la mémoire tel que i = j mod 16384
 Trouver la ligne du cache où sera placée la ligne 56871 de la mémoire centrale dans le cache ?
CHAPITRE 1 : LA MÉMOIRE CACHE

CORRESPONDANCE LIGNES CACHE/MEMOIRE

 Avantage
 On sait immédiatement où aller chercher la ligne
• Accès très rapide à la ligne (latence d'1 cycle d'horloge)
 Inconvénient
 Devra parfois décharger et charger les mêmes lignes alors que d'autres lignes sont peu accédées
 Peu efficace en pratique
• Taux de succès entre 60 et 80%
CHAPITRE 1 : LA MÉMOIRE CACHE

CORRESPONDANCE LIGNES CACHE/MEMOIRE

 Correspondance associative totale (fully associative)
 Une ligne de la mémoire centrale peut être placée dans n'importe quelle ligne de la mémoire cache
 Avantages
• Très souple et efficace pour gérer les lignes de manière optimale en terme de succès d'accès
 Inconvénient
• Doit au pire parcourir toutes les lignes du cache pour savoir si la ligne cherchée s'y trouve ou pas
 Au final
• Taux de succès de l'ordre de 90 à 95%
• Mais temps d'accès de l'ordre de (L / 2) cycles d'horloge
CHAPITRE 1 : LA MÉMOIRE CACHE

CORRESPONDANCE LIGNES CACHE/MEMOIRE

 Correspondance associative par ensemble (N-way associative)
 Solution intermédiaire aux 2 précédentes
 On regroupe les lignes du cache en ensembles de N lignes
 On applique le modulo pour trouver la ligne cible dans le cache mais peut placer la ligne dans n'importe quelle
ligne de l'ensemble contenant cette ligne cible
 Avantages
 Plus souple et efficace que la correspondance directe
 Temps d'accès court = 2.5 cycles pour N = 4
 Taux de succès : 80% à 90%
 Méthode utilisée en pratique car meilleur compromis
CHAPITRE 1 : LA MÉMOIRE CACHE

REMPLACEMENT DES LIGNES

 Le cache contient une partie des lignes de la mémoire centrale
 Si lecture ou écriture par le CPU dans une ligne qui n'est pas dans le cache
• On doit charger en cache cette ligne
 Nécessité d'enlever des lignes pour y mettre d'autres lignes
 3 méthodes pour choisir la ligne à remplacer
 Aléatoire
 La plus ancienne
 La moins utilisée
CHAPITRE 1 : LA MÉMOIRE CACHE

REMPLACEMENT DES LIGNES

 Remplacement aléatoire : une ligne choisie au hasard
 Simple à mettre en œuvre
 Peu efficace car peut supprimer des lignes très accédées
 Remplacement de la plus ancienne
 LRU : Last Recently Used
 Nécessite des compteurs associés aux lignes
 Remplacement de la moins utilisée
 LFU : Least Frequently Used
 Nécessite également des compteurs
CHAPITRE 1 : LA MÉMOIRE CACHE

REMPLACEMENT DES LIGNES

 Avec correspondance directe
 Pas besoin de choisir : on ne peut forcément remplacer qu'une seule ligne
 Avec les 2 autres types de correspondance
 Possibilité d’utiliser une des 3 méthodes de remplacement
 Avec une associativité par ensemble, on peut avoir une approche intermédiaire simple (si N > 2) souvent utilisée
en pratique
 Entre remplacement aléatoire et LRU : pseudo-LRU
 Dans chaque ensemble de N lignes du cache, on marque la ligne dernièrement accédée
• Un bit suffit au lieu de compteurs
 Quand besoin de remplacer une ligne dans l'ensemble, on prend au hasard une des N – 1 lignes non marquées
 CHAPITRE 2 : LES ARCHITECTURES MODERNES

Objectif du cours : Présenter à l’étudiant les architectures récentes en matière de processeurs

Durée du chapitre : 01 séance de 05h

CHAPITRE 2 : LES ARCHITECTURES MODERNES

INTRODUCTION
 Fort impact des architectures multicœurs
→ de nombreux programmeurs cherchent à utiliser au mieux la puissance fournie par les processeurs modernes
• Ils possèdent des processeurs contenant plusieurs cœurs .
 Architecture disponible sur le marché depuis quelques temps
→ Objectif: la performance
→ But: Exécuter des instructions indépendantes dans des processeurs séparés
→ Toutefois, coût relativement élevé
 Le parallélisme est le mécanisme par lequel l’on repart des calculs sur plusieurs processeurs.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

NOTION DE PARALLELISME
Il existe plusieurs types de parallélisme.

 Parallélisme de threads
 exécuter des calculs indépendants en parallèle.
• découper le programme en plusieurs sous -programmes indépendants qu'on peut faire exécuter en
parallèle.
• Ces sous programmes sont les Threads
 Chaque thread est exécuté sur un processeur séparé.
 Comment découper le programme? C’est du ressort du compilateur ou du programmeur.
 Attention: il est possible que le découpage se fasse au moment de l’exécution.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

NOTION DE PARALLELISME
 Parallélisme d’instruction
 Plutôt que de paralléliser le programme…
• On parallélise les instructions.
• Un exemple où cette technique est appliquée: dataflow
 Un processeur seul peut exécuter plusieurs instructions simultanément pour peu qu’elle appartiennent au même
programme.

 Parallélisme de données
 Un programme est exécuté sur des données différentes et indépendante.
 tous les processeurs exécutent un seul et unique programme ou une suite d'instructions , mais chacun de ces
processeurs va travailler sur une donnée différente.

Flynn classe les architectures parallèles en 4 catégories : SISD, SIMD, MISD, et MIMD.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

SSID (Single Instruction Single Data).
 Processeurs purement séquentiels
 incapables de toute forme de parallélisme
• Une instruction sur un seul ensemble de données , et rien d'autre.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

SIMD (Single Instruction Multiple Data).
 Parallélisme exploitable
 exécution d’une instruction sur plusieurs données à la fois
 Disponible sur les processeurs récents réalisant des calculs sur plusieurs données différentes à la fois.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

MISD (Multiple Instruction Single Data).
 Exécution d’instructions différentes en parallèle sur une donnée identique.
 Cette catégorie d’architectures est vraiment très rare. On peut citer comme exemples d'architectures MISD les
architectures systoliques et cellulaires
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

MIMD (Multiple Instruction Multiple Data).
 Plusieurs instructions exécutables sur des données différentes
 Disponible sur les processeurs multicoeurs et multiprocesseurs
 Découpable en deux sous catégories:
 le Single Program Multiple Data (SPMD) : exécution d’un seul programme sur plusieurs données à la fois
• Différence avec le SIMD qui exécute la même instruction sur plusieurs données quand SPMD exécute des
morceaux de programmes.
 le Multiple Program Multiple Data (MPMD) : exécution des programmes en parallèle sur des données
différentes
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

In fine,
 Cette classification peut sembler simple, mais est tout de même redoutablement efficace. Elle marche pour la grosse
majorité des architectures parallèles

ATTENTION: La capacité à traiter des données ou des instructions différentes simultanément n'est pas la seule
différence entre les
architectures parallèles : la façon dont les processeurs doivent se partager la mémoire est aussi très importante.
Suivant la façon dont est partagée la mémoire, de nombreux problèmes peuvent apparaitre.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

SASM (Single Address space, Shared Memory)
 Une seule et unique mémoire partagée entre tous les processeurs
 Durée de temps d’accès à la mémoire identique pour tous les processeurs: on parle d'Unifed Memory Access (UMA)

PROBLEME: Que se passe-t-il en cas d’accès concurrent?

 Accès en lecture d’une information en écriture (synchronisation)
SOLUTION: Utilisation des mémoire cache (voir figure ci contre)
On ajoute ces mémoire à la SASM. On accélère ainsi l’accès à la
mémoire partagée. Il va tout de même demeurer un problème de
cohérence des caches des copies du cache si l’un des processeurs
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

DADM (Distributed Address space, Distributed Memory)
 Appelées aussi architectures distribuées.
 Avec elle, chaque processeur possède sa propre mémoire,
 Aucune mémoire partagée entre les processeurs .
 Processeurs reliés entre eux via un réseau local, permettant l’échange des données ou des ordres un peu
particuliers .

 Grâce au réseau, un processeur accède à la mémoire d’un autre processeur via

une demande sur le réseau local au processeur concerné.
 La donnée sollicitée parcourt le réseau pour être copiée dans la mémoire de
l’ordinateur demandeur.
PROBLEME: le temps nécessaire pour les communications entre les processeurs
peut être important. La performance du réseau est un challenge permanent dans ce
type d’architecture.

Quelle solution? Encore les caches

CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

DADM (Suite)
SOLUTION: Placer entre chaque processeur et sa mémoire, une mémoire cache
Le problème de cohérence des caches ne se pose plus ici car chaque ordinateur a sa mémoire. Celle-ci n’étant plus
partagée.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

SADM (Single Address space, Distributed Memory)
 les processeurs possèdent une mémoire locale, qui leur est réservée et dans laquelle ils peuvent faire ce que bon
leur semble.
 Possibilité d’accéder aux autres mémoires
PROBLEME: le temps d’accès aux autres mémoire peut être coûteux
SOLUTION: Les caches

DSM: DiskStation Management

CHAPITRE 2 : LES ARCHITECTURES MODERNES

CATEGORIES D’ARCHITECTURES PARALLELES

SADM (Single Address space, Distributed Memory)-Suite
 Avec cette méthode, chaque processeur voit toutes les mémoires virtuellement rassemblées dans une seule grosse
mémoire unique.
 L’accès à la portion de cette mémoire unique qui correspond à sa mémoire locale est rapide,
 L’accès à la portion de cette mémoire unique qui correspondant à la mémoire d'un autre processeur est
redoutablement plus lent.
 Bien gérer les temps d'accès aux différentes mémoires est donc un plus bien agréable

L’utilisation des mémoires caches peut être une solution pour réduire le temps d’accès à la mémoire unique, mais
on retombe sur un problème : la cohérence des caches n'est pas assurée et on doit se débrouiller pour qu'elle le
soit, comme pour les architectures SASM
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

On retient de ce qui a précédé que: plusieurs processeurs peuvent servir au traitement des tâches ou des données

Quelles sont les limites possibles à l’utilisation de plusieurs processeurs?

 Tout dépend vraiment.
→ A certains moments, il n’y a pas de valeur ajoutée.
→ Dans d'autres, il n'y a pas vraiment de limites théoriques aux gains de performances que l'on peut obtenir en
ajoutant des processeurs

Deux approches:

 Loi d'Amdhal
Loi de Gustafson
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE AMDHAL
Elle permet d’évaluer le gain maximal théorique que l’on pourrait tirer de l’exploitation de plusieurs processeurs
pour l’exécution d’un programme
Principe: on prend un programme et on regarde ce qui se passe en fonction du nombre de processeurs
Hypothèses: on fait les hypothèses suivantes pour la suite
 Un ordinateur contient un nombre N de processeurs,
Une portion plus ou moins importante de notre programme peut utiliser plusieurs processeurs,
Cette utilisation est la plus efficace possible quel que soit le nombre de processeurs,
On néglige les coûts induits par la gestion du code s’exécutant sur plusieurs processeurs, le système d’exploitation,
la façon dont est conçu le matériel, et on passe tous ces détails sous le tapis.
Expliquons un peu plus en détail la deuxième hypothèse.
 Une portion de notre programme peut exploiter plusieurs CPU : on l'appelle le code parallèle.
 Mettre plusieurs CPU n'accélérera que cette portion du programme et pas le reste.
 Intuitivement, on se doute que plus la quantité de ce code parallèle est importante, plus notre programme profitera de
la présence de plusieurs processeurs
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE AMDHAL

 On va appeler le reste du programme, incapable d'exploiter plusieurs CPU, le code série.

 Plus le programme contient de code série, moins notre programme gagnera en performances si l'on augmente le
nombre de processeurs.
Autres hypothèses
 Le code parallèle est quasiment parfait, il peut exploiter n’importe quel nombre de processeurs
 Le gain est le fonction du nombre de processeurs et respecte cette règle. On ne peut donc pas avoir une situation de
gain important pour 2 et 3 processeurs mais pas au-delà.
 La quantité et la taille de données est la même pour le programme.
 On ne rajoute pas les données en même temps que les processeurs question d’apprécier l’impact effectif du nombre
de processeurs sur le programme.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE AMDHAL

 Situation de référence

 Elle est définie par le comportement du programme lorsqu’il s’exécute sur un seul processeur
 Elle permet d’apprécier les gains provenant de l’ajout de processeurs.
 
 On note T le temps mis par le programme lorsqu’il s’exécute sur un seul processeur
 Ce temps se décompose comme somme du:
→ Temps d’exécution du code série, noté
→ Temps d’exécution du code parallèle sur un seul processeur, noté
 On peut alors écrire:
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE AMDHAL

 Plusieurs processeurs
 On suppose que l’on dispose de N processeurs
 Les calculs du code parallèle s’exécutent de façon simultanée sur les N processeurs.
 Il y a gain de temps car on n’attend pas qu’une portion soit terminée avant de lancer une autre

  Calcul du temps d’exécution du code parallèle sur N processeurs

 On se sert de l’hypothèse portant sur la répartition au mieux des instructions sur les N processeurs.
 Le temps d’exécution du code parallèle sera alors divisé par le nombre de processeurs
 Le code série n’est pas affecté par le nombre de processeurs. Il s’exécute sur un seul processeur. Son temps
d’exécution est le même et ne change pas.
 On désigne par T(N) le temps mis par le code pour s’exécuter sur N processeurs.
 On peut alors écrire:
 représente le temps mis pour exécuter le code parallèle sur un processeur pas sur N
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE AMDHAL

 Calcul du gain
 Comment comparer le temps d’exécution du programme sur la machine avec un processeur et celui mesuré sur une
machine avec plusieurs processeurs ?
 Le gain permet d’y répondre

  On peut écrire:

 Le gain représente le nombre de fois que le programme exécuté sur N processeurs est plus rapide que s’il est utilisé
sur un seul processeur.
 Ainsi, plus le gain est important, plus il y a gain de performance.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE AMDHAL

 La loi de Amdhal
  On va évaluer (1)
 Exprimer (1) en fonction de et
 On pose :
 S représente le pourcentage de temps mis pour l’exécution du code série
 P représente le pourcentage de temps mis pour l’exécution du code parallèle
 Exprimer (1) en fonction de S et P
 Donner l’expression du gain en fonction de S et P
 Quelle relation existe-t-il entre S et P?
 Exprimer le gain en fonction de P

 La relation précédente est la loi de Amdhal. Elle représente le gain maximal théorique que l’on peut obtenir avec un
code passant un pourcentage P de son temps à exécuter du code parallèle avec N processeurs.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LIMITES DE LA LOI DE AMDHAL
  1
𝐺𝑎𝑖𝑛=
 La loi de Amdhal 𝑃
1 − 𝑃+
𝑁

  Que se passe-t-il si ? Si on a trop de processeurs,
 Dans ce cas,

Quand N tend vers l’infini, le code parallélisé est exécuté en un temps qui temps vers 0. Seul reste le code série sur
lequel la présence de plusieurs n’a aucun effet. Le temps d’exécution du code restant le même, le temps d’exécution du
programme ne peut pas descendre en dessous du temps d’exécution du code série. C’est la première limite imposée la loi
d’Amdhal.
Solution: paralléliser le plus possible le code du programme, pour diminuer S et augmenter P le plus possible. C'est
cela qui est le plus recherché à l'heure actuelle.
Seul problème : tous les programmes ne se laissent pas aisément paralléliser
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LIMITES DE LA LOI DE AMDHAL
  1
𝐺𝑎𝑖𝑛=
 La loi de Amdhal 𝑃
1 − 𝑃+
𝑁
L’augmentation du nombre de processeurs, n’est pas la solution car à partir d’un certain niveau le gain est minisée.
C’est la seconde limite. La solution consisterait à avoir une part de code parallélisable suffisante pour que cela ait un
impact suffisant
Exemple, à partir de combien de processeurs pour P= 20%, le gain est-il négligeable?

Enfin, une dernière remarque : la loi d'Amdhal est optimiste : elle a été démontrée en postulant que le code parallèle peut
être réparti sur autant de processeurs qu'on veut et peut profiter d'un grand nombre de processeurs . Dans la réalité, rares
sont les programmes de ce genre : certains programmes peuvent à la rigueur exploiter efficacement 2, 4 , voir 8
processeurs mais pas au-delà. Elle ne tient pas compte des nombreux problèmes techniques, aussi bien logiciels que
matériels qui limitent les performances des programmes conçus pour exploiter plusieurs processeurs . La loi d'Amdhal
donne une borne théorique maximale au gain apporté par la présence de plusieurs processeurs , mais le gain réel sera
quasiment toujours inférieur au gain calculé par la loi d'Amdhal
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE GUSTAFSON: Parallélisme des données
Elle vise à utiliser plusieurs processeurs de façon différente.
 Les données fixes chez Amdhal, ne le sont plus ici.
 On se sert ici du parallélisme de données, qui consiste à exécuter le même programme sur des données
différentes et indépendantes.
 On peut ainsi traiter N données sur N processeurs en même temps.
Principe: tous les processeurs exécutent un seul et unique programme ou une suite d'instructions, mais chacun de ces
processeurs va travailler sur une donnée différente
 Hypothèses de base: on considère un programme s’exécutant sur un seul processeur.
 : Temps d’exécution du code série
 : Temps d’exécution du code parallèle. On précise que ce code s’exécute sur une donnée (image, fichier son, ou
autre). En outre, il sera exécuté simultanément sur plusieurs données. Ainsi, pour N données, on pourra prendre N
processeurs et exécuter sur chacun d'eux le code parallèle sur une des N données .
 En prenant 1 ou N processeurs, la partie série restera la même et sera exécutée sur un seul processeur durant un temps
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE GUSTAFSON: Parallélisme des données

Cas
  d’une seule donnée.
 Le temps d’exécution T du programme est tel que: .

 
Cas de plusieurs données.
 Durant le temps , on pourra demander à chacun des N processeurs de traiter une donnée en un temps .
→ En un temps T, on peut demander à notre processeur d’exécuter un programme sur N données
 Dans ce cas
 Si ce calcul fait sur ces N données avait été fait sur un seul processeur, on aurait dû calculer ces données unes
par une, ce qui aurait pris un temps égal à:
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE GUSTAFSON: Parallélisme des données

 Calcul du gain.

 
En remplaçant on obtient :
On pose :
 pourcentage de temps passé à exécuter le code série
 pourcentage de temps passé à exécuter le code parallèle sur N processeurs
 On peut alors écrire:
 En considérant que on déduit: (loi de Gustafson)
CHAPITRE 2 : LES ARCHITECTURES MODERNES

ETUDE DES LIMITES

LOI DE GUSTAFSON: Ce qu’on en retient!!!!!!
1. La loi de Gusatfson répond à un besoin certain : comment faire pour exploiter au mieux le parallélisme lorsque
l'on souhaite travailler sur une grande quantité de données. Cela correspond au parallélisme de données :
exécuter simultanément un même programme sur des données indépendantes
2. Il n'y a pas de limites théoriques à N: on peut mettre autant de données que l'on veut, avec N processeurs,
celles-ci sont toutes traitées par un processeur simultanément et le temps mis pour traiter N données sur
processeurs sera identique au temps mit pour traiter une donnée sur un seul processeur.
3. Aucune limite n'existe concernant la quantité de données traitables simultanément, et donc au gain que l'on
peut obtenir
4. La loi de Gustafson s'applique sur une durée déterminée : elle ne rend pas les calculs plus rapides. Si une
donnée N met un temps T à être traitée, alors on ne gagne rien en terme de temps de calcul.
CHAPITRE 2 : LES ARCHITECTURES MODERNES

CONCLUSION

1. Paralléliser un programme qui exécute de nombreux calculs en parallèle sur le même ensemble de données est
voué à montrer «rapidement ses limites». Ce parallélisme est en effet soumis à la loi d'Amdhal.
2. Par contre, le parallélisme de données , consistant à effectuer un même programme/sous programme sur un
ensemble de données différentes donne de très bons résultats
3. Dans la réalité, aucune de ces formules n'est utilisable directement: de nombreux autres paramètres
interviennent, qui dépendent de l'architecture des processeurs utilisés, du langage de programmation utilisé et
de la manière dont a été programmé le programme en question. Ce sont d’abord des formules théoriques, et ne
servent qu'a donner des indications qualitatives
 CHAPITRE 3 : MULTI-PROCESSEURS, MULTICOEURS ET
HYPERTHREADING

Objectif du cours : Présenter à l’étudiant les notions de cœur, et multiprocesseurs

Durée du chapitre : 01 séance de 05h

CHAPITRE 3 : MULTI-PROCESSEURS, MULTICOEURS ET HYPERTHREADING

HYPERTHREADING ET COMPAGNIE

 L’exécution en parallèle ne nécessite pas forcément plusieurs processeurs.

 Il est possible qu’un seul processeur exécute plusieurs programmes en même temps. On se sert dans ce cas des
ruses sioux qu’implémentent certains processeurs spéciaux.
 On peut par exemple faire du parallélisme avec un seul processeur via le circuit intégré au processeur qui réalise
les calculs: l’unité de calcul.
 Différentes méthodes existent pour ce faire.
CHAPITRE 3 : MULTI-PROCESSEURS, MULTICOEURS ET HYPERTHREADING

HYPERTHREADING ET COMPAGNIE
Fine Grained Multithreading

 Cette méthode consiste à switcher entre les programmes :

 on exécute une instruction d'un programme, puis on passe au second programme, et ainsi de suite.
 Le processeur a la charge de réaliser automatiquement ce switching, ceci sans temps d’attente.
 Avantages:
 Une instruction qui s’exécute n’a pas besoin d’attendre le résultat de l’instruction qui la précède dans
l’exécution car ce sont des instructions de programmes différents n’ayant rien en commun.
 Grande simplification du processeur, on ne gère pas ici l’attente d’un résultat par une instruction, donc des
circuit en moins.
 Meilleure utilisation de l’unité de calcul.
 Incovénient majeur:
 Nécessité d’avoir beaucoup de programmes en exécution sinon l’unité de calcul pourrait ne pas être utilisée
pendant un temps relativement long.