View
110
Download
2
Category
Preview:
Citation preview
Architectures Architectures parallèlesparallèles
Source: Michael J. Quinn Parallel Programming in C with MPI and openMP
1
PlanPlan
1. Réseaux d’intercommunication2. Ordinateurs vectoriels3. Multiprocesseurs4. Multi-ordinateurs5. Taxonomie de Flynn
2
1. Réseaux 1. Réseaux dd ’’intercommunicationintercommunicationUtilités
◦Connecter les processeurs à la mémoire partagée
◦Connecter les processeurs entre eux2 modes:
◦Partagé◦Avec commutateurs (switchs)
3
Comparaison des deux Comparaison des deux modesmodes
Partagé Commutateurs
4
Mode partagéMode partagéUn seul message à la foisLes messages sont diffusés à tous les
processeurs via un busChaque processeur “écoute” tous les
messagesL’arbitrage est décentraliséUne collision nécessite la rediffusion
du messageLimite le nombre de processeurs
5
Avec commutateursAvec commutateursPermet la communication point-
à-pointAvantages:
◦Permet l’envoi de plusieurs messages simultanément
◦Permet l’utilisation d’un plus grand nombre de processeurs
6
Topologies des réseaux Topologies des réseaux dd ’’intercommunicationintercommunication
Représentation sous forme de graphe◦Noeud = processeur ou
commutateur◦Arête = lien de communication
Deux types de topologies◦Directe◦Indirecte
7
Topologie directeTopologie directeUn commutateur pour chaque
processeurChaque commutateur est
connecté à:◦1 processeur◦Au moins un autre commutateur
En général, le nombre de processeurs est identique au nombre de commutateurs
8
Topologie indirecteTopologie indirecteLe nombre de commutateurs
peut être plus grand que le nombre de processeurs
Certains commutateurs ne sont connectés qu’à d’autres commutateurs.
9
Évaluation dÉvaluation d’’une topologieune topologie
Diamètre ◦ Distance maximale entre deux noeuds◦ Borne inférieure sur le temps de communication
Largeur de coupe◦ Nombre min d’arêtes à enlever pour diviser le
graphe en deux composantes connexes de même taille (à 1 neud près).
◦ Borne supérieure sur le nombre de messages pouvant être envoyés simultanément.
Degré = Nombre d’arêtes adjacentes à un noeud
Longueur des arêtes: Une longueur constante permet plus
facilement d’augmenter le nombre de processeurs.
10
Grille 2-DGrille 2-DTopologie directeLes commutateurs sont organisés
sous la forme d’une grille 2-DCommunication permise
seulement entre les noeuds voisins
Tore: les extrémités sont reliées
11
Grille 2-DGrille 2-D Tore Tore
Les cercles représentent des commutateurs et les carré des processeurs.
12
Évaluation des grilles 2-DÉvaluation des grilles 2-DDiamètre: (n1/2)Largeur de coupe: (n1/2)Degré: 4Longueur d’arêtes constante
13
Arbre binaireArbre binaireTopologie indirecte n = 2d processeurs 2n-1 commutateurs
14
Évaluation dÉvaluation d’’un arbre un arbre binairebinaireDiamètre: 2 log n
Largeur de coupe: 1
Degré: 3
La longueur d’arête n’est pas constante
15
Hyper-arbreHyper-arbreTopologie indirecteFaible diamètrePlus grande largeur de coupe qu’un
arbreDe face, il apparaît comme un arbre
de degré k et profondeur dDe côté, il apparaît comme un arbre
binaire renversé de hauteur d
16
Hyper-arbreHyper-arbre
17
Évaluation des hyper-Évaluation des hyper-arbrearbreDiamètre: log n
Largeur de coupe: n / 2
Degré: 6
Longueur d’arêtes non constante
18
Réseau butterflyRéseau butterflyTopologie indirecten = 2d processeurs connectés à l’aide de
n(log n + 1) commutateurs.
19
Routage sur un réseau Routage sur un réseau butterflybutterfly
20
ÉvaluationÉvaluationDiamètre: log n
Largeur de coupe: n / 2
Degré: 4
Longueur d’arêtes non constante
21
HypercubeHypercubeTopologie directeLe nombre de noeuds est un
puissance de 2Adresses: 0, 1, …, 2k-1Le noeud i est connecté au noeud k si
et seulement si leurs adresses ne diffèrent que d’un seul bit.
22
Réseau hypercube de 16 Réseau hypercube de 16 processeursprocesseurs
23
ÉvaluationÉvaluationDiamètre: log n
Largeur de coupe: n / 2
Degré: log n
La longueur des arêtes n’est pas constante
24
Réseau shuffle-exchangeRéseau shuffle-exchangeTopologie directeLe nombre de noeuds est une
puissance de 2Adresses: 0, 1, …, 2k-1Deux arcs sortent de chaque
noeud i◦(i,k): où k est la rotation à gauche des
bits de i◦(i,j): où i et j ne diffèrent qu’au bit le
moins significatif25
Illustration du shuffle-Illustration du shuffle-exchangeexchange
0 1 2 3 4 5 6 7
26
Adressage du shuffle-Adressage du shuffle-exchangeexchange
27
Évaluation du shuffle-Évaluation du shuffle-exchangeexchangeDiamètre: 2log n - 1
Largeur de coupe: n / log n
Degré: 2
Longueur d’arêtes non constante
28
Comparaison des réseauxComparaison des réseauxTous ont un diamètre
logarithmique sauf la grille 2-DHyper-arbre, butterfly et
hypercube ont une largeur de coupe n / 2
Tous ont un degré constant sauf l’hypercube
Seul la grille 2-D a une longueur d’arête constante.
29
2. Ordinateurs 2. Ordinateurs vectorielsvectorielsInclut des opérations sur les vecteurs en
plus des opérations sur les scalairesDeux types d’implémentations:
◦Pipeline: Les vecteur sont déplacés de la mémoire vers le processeurs en un flux de données traités en pipeline- CRAY-I, II, Cyber 205
◦Réseau de processeurs: Un ordinateur standard contient plusieurs processeurs identiques et synchronisés (ex. GPU)
30
Réseau de processeursRéseau de processeurs
31
Réseau de processeursRéseau de processeursOrdinateur frontal
◦ Programme◦ Données manipulées séquentiellement
Réseau de processeurs◦ Mémoires locales◦ Données manipulées en parallèle
L’ordinateur frontal diffuse les instructions aux processeurs du réseau
Tous les processeurs du réseau exécutent la même instruction
32
PerformancePerformanceQuantité de travail par unité de
temps◦Ex. Nombre d’opérations par
secondeLa performance dépend de l’utilisation faite des processeurs.
La performance est au maximum lorsque les processeurs sont utilisés à 100%
33
Exemple 1Exemple 11024 processeursChacun additionne un couple d’entiers en 1 sec
On veut additionner deux vecteurs de1024-elements (un par processeur)
34
Exemple 2Exemple 2512 processeursChacun peut additionner deux
entiers en 1 secOn additionne deux vecteurs de
600 éléments.
35
Activer et désactiver un Activer et désactiver un processeurprocesseur
Si tous les processeurs exécute la même instruction simultanément, comment traiter les instruction conditionnelles???
Chaque processeur possède un bit de masquage lui permettant de ne pas exécuter la prochaine instruction.
36
if (T[i]!=0) then T[i]=1 else if (T[i]!=0) then T[i]=1 else T[i]=-1T[i]=-1
37
if (T[i]!=0) then T[i]=1 else if (T[i]!=0) then T[i]=1 else T[i]=-1T[i]=-1
38
if (T[i]!=0) then T[i]=1 else if (T[i]!=0) then T[i]=1 else T[i]=-1T[i]=-1
39
Désavantages des ordinateurs Désavantages des ordinateurs vectoriels.vectoriels.N’exploite que le parallélisme de
donnéesLa performance décroit en présence d’instructions conditionnelles
S’adapte mal à la présence de plusieurs usagers
Nécessite une bande passante très grande
Le rapport performance/coût n’est pas aussi bon que celui des processeurs standards
40
3. Multiprocesseurs3. MultiprocesseursPlusieurs processeurs utilisant
une mémoire communeMême espace d’adressageÉvitent trois problèmes des
ordinateurs vectoriels:◦Peuvent être construits avec des
processeurs standards◦Supportent plusieurs usagers◦Aucun problème avec les
instructions conditionelles
41
MultiprocesseursMultiprocesseurs
Deux types de multiprocesseurs:
◦Mémoire centralisées
◦Mémoire distribuées
42
Multiprocesseurs Multiprocesseurs centraliséscentralisésExtension directe des monoprocesseursPlusieurs processeurs conectés à un
même busTous les processeurs partagent une
mémoire communeLe temps d’accès à la mémoire est
identique pour tous les processeurs◦Uniform memory access (UMA)◦Symmetrical multiprocessor (SMP)
Chaque processeur possède sa propre mémoire cache
43
Multiprocesseurs Multiprocesseurs centraliséscentralisés
44
Données privées et Données privées et partagéespartagéesDonnées privées: Accessible à
un seul processeurDonnées partagées: Accessible à
tous les processeursLa communication entre les
processeurs se fait à l’aide des données partagées.
45
Problèmes liés aux variables Problèmes liés aux variables partagéespartagéesCohérence des caches
◦La présence de caches réduit les problèmes de bande passante
◦Comment s’assurer que différents processeurs possèdent la même valeur pour une variable partagée?
Synchronisation◦Exclusion mutuelle◦Barrière
46
Cohérence des cachesCohérence des caches
Cache
CPU A
Cache
CPU B
Memory
7X
47
Cohérence des cachesCohérence des caches
CPU A CPU B
Memory
7X
7
48
Cohérence des cachesCohérence des caches
CPU A CPU B
Memory
7X
7 7
49
Cohérence des cachesCohérence des caches
CPU A CPU B
Memory
2X
7 2
50
Protocole dProtocole d’’invalidation en invalidation en écritureécriture
CPU A CPU B
7X
7 7 Chaque cache possède un moniteur de bus
51
Protocole dProtocole d’’invalidation en invalidation en écritureécriture
CPU A CPU B
7X
7 7
Intention de modifier X
52
Protocole dProtocole d’’invalidation en invalidation en écritureécriture
CPU A CPU B
7X
7
Invalidation de X dans le cache de A
53
Protocole dProtocole d’’invalidation en invalidation en écritureécriture
CPU A CPU B
X 2
2
54
Multiprocesseurs Multiprocesseurs distribuésdistribuésLa mémoire est distribuée entre
les processeursDiminue la bande passante ainsi
que le temps moyen d’accès à la mémoire.
Permet d’utiliser un plus grand nombre de processeurs
Non-uniform memory access (NUMA)
55
Multiprocesseurs Multiprocesseurs distribuésdistribués
56
Cohérence de la mémoire Cohérence de la mémoire cachecacheImplémentation plus difficile que
pour les multiprocesseurs à mémoire partagées.
◦Pas de bus unique à monitorer
◦Méthode la plus utilisée: protocole à répertoire (Directory-based protocol)
57
Protocole à répertoireProtocole à répertoireUn répertoire contient l’information
concernant les blocs de mémoire pouvant être mis en cache
Le répertoire est distribuéUne entrée dans le répertoire pour
chaque bloc de mémoire Chaque entrée possède:
◦ Status de partage◦ Liste des processeurs possédant une copie
du bloc
58
Status de partageStatus de partagePas en cache
◦Aucun processeur n’a mis le bloc en cache
Partagé◦Dans le cache d’un ou plusieurs
processeurs◦En lecture seulement
Exclusif◦Dans le cache d’un seule processeur◦Le bloc a été modifié◦La copie en mémoire n’est plus valide
59
Protocole avec répertoireProtocole avec répertoire
Interconnection Network
Directory
Local Memory
Cache
CPU 0
Directory
Local Memory
Cache
CPU 1
Directory
Local Memory
Cache
CPU 260
Protocole avec répertoireProtocole avec répertoire
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X U 0 0 0
Vecteur de bits
61
Processeur 0 lit XProcesseur 0 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X U 0 0 0
Faute de lecture
62
Processeur 0 lit XProcesseur 0 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X S 1 0 0
63
7X
Processeur 1 lit XProcesseur 1 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X S 1 0 0
7X
Faute de lecture
64
Processeur 1 lit XProcesseur 1 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X S 1 1 0
7X
65
7X
Processeur 2 lit XProcesseur 2 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X S 1 1 0
7X
66
7X
Processeur 2 lit XProcesseur 2 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X S 1 1 1
7X
67
7X 7X
Processeur 0 écrit 6 dans Processeur 0 écrit 6 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X S 1 1 1
7X 7X
Faute d’écriture
68
7X
Processeur 0 écrit 6 dans Processeur 0 écrit 6 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X E 1 0 0
6X Invalidation
69
Invalidation
Processeur 1 lit XProcesseur 1 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X E 1 0 0
6X
Faute de lecture
70
Processeur 1 lit XProcesseur 1 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
7X
Caches
Memories
Directories X E 1 0 0
6X
Changer pour partage
71
Processeur 1 lit XProcesseur 1 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X E 1 0 0
6X
72
Processeur 1 lit XProcesseur 1 lit X
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X S 1 1 0
6X 6X
73
Processeur 2 met 5 dans Processeur 2 met 5 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X S 1 1 0
6X 6X
Faute d’écriture
74
Processeur 2 met 5 dans Processeur 2 met 5 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X S 1 1 0
6X 6X
Invalidation
75
Processeur 2 met 5 dans Processeur 2 met 5 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X E 0 0 1
5X
76
Processeur 0 met 4 dans Processeur 0 met 4 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X E 0 0 1
5X
Faute d’écriture
77
Processeur 0 met 4 dans Processeur 0 met 4 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
6X
Caches
Memories
Directories X E 0 0 1
Changement de processeur
5X
78
Processeur 0 met 4 dans Processeur 0 met 4 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
5X
Caches
Memories
Directories X E 0 0 1
5X
79
Processeur 0 met 4 dans Processeur 0 met 4 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
5X
Caches
Memories
Directories X E 1 0 0
80
Processeur 0 met 4 dans Processeur 0 met 4 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
5X
Caches
Memories
Directories X E 1 0 0
5X
81
Processeur 0 met 4 dans Processeur 0 met 4 dans XX
Interconnection Network
CPU 0 CPU 1 CPU 2
5X
Caches
Memories
Directories X E 1 0 0
4X
82
Processeur 0 libère X Processeur 0 libère X (flush)(flush)
Interconnection Network
CPU 0 CPU 1 CPU 2
5X
Caches
Memories
Directories X E 1 0 0
4X
4X
Mise à jour
83
Processeur 0 libère X Processeur 0 libère X (flush)(flush)
Interconnection Network
CPU 0 CPU 1 CPU 2
4X
Caches
Memories
Directories X U 0 0 0
84
4. Multi-ordinateurs4. Multi-ordinateursPlusieurs ordinateurs ayant chacun sa
propre mémoireChaque ordinateur possède son
propre espace d’adressageLes ordinateurs interagissent entre
eux par l’envoie de messagesPeut facilement être construit à partir
d ’ordinateurs conventionels et un réseau local.
85
Multi-ordinateurs Multi-ordinateurs asymétriquesasymétriques
86
AvantagesAvantagesLes ordinateurs du réseaux sont dédiés
au calcul parallèle et ne nécessite qu’un système d’exploitation simple
Deux types de systèmes d’exploitations:◦ Ordinateur frontal◦ Ordinateurs du réseaux
Système d’exploitation des ordinateur du réseaux:◦ sans mémoire virtuel ◦ sans entrée/sortie ◦ facile à comprendre.
87
DésavantagesDésavantagesTout le système dépend de l’ordinateur frontal
L’existence d’un unique ordinateur frontal limite le nombre d ’ordinateurs
Déboguage plus difficile◦Les ordinateurs du réseau ne peuvent
pas faire d’E/SChaque application nécessite le
développement de deux types de programes (frontal et réseau)
88
Multi-ordinateurs Multi-ordinateurs symétriquessymétriques
89
AvantagesAvantagesÉlimine le problème de goulot d ’étranglement causé par l’existence d ’un ordinateur frontal unique
Déboguage plus facileChaque ordinateur exécute le même
programme◦Lorsqu’un seul ordinateur doit exécuter
une opération, cela peut facilement être déterminé par une instruction conditionelle.
90
DésavantagesDésavantagesIl est plus difficile de maintenir l’illusion de
travailler sur une seule machine lorsqu’on peut se connecter sur n’importe quel ordinateur possédant son propre nom.
Difficulté de balancer le travail entre les ordinateurs
Difficile d’obtenir une bonne performance losrqu’il y a plusieurs processus en concurrence pour l’utilisation des processeurs◦ Ex. La mémoire cache sert les processeurs et
non pas les processus.
91
Quel est le meilleur Quel est le meilleur modèle?modèle?L’utilisation d’un système d’exploitation
unique et complet facilitant le déboguage (e.g. Linux) plaide en faveur des multi-orninateurs symétriques
Les performances d’un processeurs dépendent beaucoup de l’efficacité de sa mémoire cache.◦ Cette situation est favorisé lorsqu’il n’y a qu’un seul
processus par processeur◦ Cela plaide en faveur des multi-ordinateur
asymétrique
92
Cluster maisonCluster maisonOrdinateurs regroupésDédié à l’exécution de
programmes parallèlesSans clavier ni écranSystèmes d’exploitation
identiquesImages disque logiques
identiques
93
Réseau de station de Réseau de station de travailtravailOrdinateur dispersésLa priorité est donné à l’usagé
qui utilise le clavierLes tâches parallèles sont
exécutées en arrière planDifférents systèmes d’exploitation
Différentes images disque
94
5. Taxonomie de Flynn5. Taxonomie de FlynnFlux d’instructionsFlux de donnéesSimple vs. multipleQuatre combinaisons
◦SISD◦SIMD◦MISD◦MIMD
95
SISDSISDSingle Instruction, Single DataSystème monoprocesseurNote: On ne compte pas les co-
processeurs◦Calcul en points flottant◦Carte graphique◦I/O
Exemple: PC
96
SIMDSIMDSingle Instruction, Multiple Data
Ex. Réseaux de processeurs(e.g., Connection Machine, nCube, iPSC, etc.)
97
MISDMISDMultiple
Instruction,Single Data
Architecture pipeline
Grilles systoliques
Ordinateur tolérant aux fautes Controleur de vol de la
navette spatiale 98
MIMDMIMDMultiple Instruction, Multiple Data
◦Multiprocesseurs
◦Multi-ordinateurs
99
100
Recommended