Introduction aux architectures et
programmes parallèles
Daniel Etiemble
de@lri fr
de@[Link]
Accélération
• Accélération (p processeurs) = Performance (p processeurs)
Performance (1 processeur)
• Pour un problème de taille fixe (entrées fixées),
performance = 1/temps
• Accélération à problème fixé
– (p processeurs) = Temps (1 processeur)
Temps (p processeurs)
IFIPS-2
D. Etiemble 2
Calcul parallèle
1
Amdahl et Gustafson
S: Temps séquentiel
P: Temps parallélisable
Application fixe Application extensible
Amdahl Gustafson
SP
Acc(n) P = a*n
SP S a.P
n Acc(n)
SP
Ts = S+P = fs + (1
(1-fs)
fs)
Ts = S+P = fs + n (1-fs)
Tp = S+P/n = fs +(1-fs)/n
Tp = S+P/n = fs +(1-fs)
Acc(n) n 1/ f s fs
E ( n) 1 fs
n
IFIPS-2
D. Etiemble 3
Calcul parallèle
Classification de Flynn
• Flot d’instructions x Flot de données
– Single Instruction Single Data (SISD)
– Single Instruction Multiple Data (SIMD)
– Multiple Instruction Single Data
– Multiple Instruction Multiple Data (MIMD)
• “Tout est MIMD” !
IFIPS-2
D. Etiemble 4
Calcul parallèle
2
SIMD
• Modèle d’exécution Contrôleur
– CM2 Lancement instructions
– Maspar
ML PE ML PE ML PE
Réseau d’interconnexion
• Modèle obsolète pour machines parallèles
– Processeurs spécifiques différents des CPU standards
– Lancement des instructions incompatible avec les fréquences
d’horloge des microprocesseurs modernes
– Synchronisation
S h i ti après è chaque
h instruction
i t ti : lesl instructions
i t ti
conditionnelles sont synchronisées
• SPMD
• Extensions SIMD dans les microprocesseurs
IFIPS-2
D. Etiemble 5
Calcul parallèle
Version SPMD du SIMD
• Modèle d’exécution
ML CPU ML CPU ML CPU
Réseau d’interconnexion
– Chaque CPU exécute le même code.
– Les CPU sont synchronisés par des barrières avant les transferts
de données.
• Clusters de PCs
– PC
– Ethernet
IFIPS-2
D. Etiemble 6
Calcul parallèle
3
Organisation mémoire du MIMD
+
Mémoire centralisée Espace d’adressage unique Accès mémoire uniforme
Mémoire @Max
Mémoire Mémoire
12
Réseau 9 3
@0
6 12
9 3
PE PE PE
Complexité
PE PE PE PE PE
Opposé
Mémoire distribuée Plusieurs espaces d’adressage Accès mémoire non uniforme
Mémoire Mémoire Mémoire
Réseau @Max @Max @Max
Mé i
Mémoire
PE PE PE 12
@0 @0 @0 9 3
6 12
Mémoire
Mémoire
Mémoire
9 3
PE PE
PE PE PE 6
-
IFIPS-2
D. Etiemble 7
Calcul parallèle
Classification mémoire (MIMD)
Mémoire
Mé i partagée
Mémoire é Mé i distribuée
Mémoire di ib é
SMP ccNUMA MMP Hybrid Clusters
P1 Pn
Réseau
Cache C h
Cache PE PE PE
Bus
Mémoire
Mémoire
Mémoire
Mémoire Composants d’E/S
Modèle mémoire SMP
IFIPS-2
D. Etiemble 8
Calcul parallèle
4
Multi-thread et multiprocesseurs
Processeur Processeur Processeur
Processeur
logique 1 logique 2 physique 2
physique 1
Etat archit. Etat archit. Etat archit. Etat archit.
(registres) (registres) (registres) (registres)
Unités fonctionnelles Unités Unités
fonctionnelles fonctionnelles
Caches Caches Caches
Mémoire principale Mémoire principale
IFIPS-2
D. Etiemble 9
Calcul parallèle
Multiprocesseurs et multi-cœurs
CPU State CPU State
Execution Execution
unit Cache Cache
unit
Multiprocesseur
CPU State CPU State
Execution Execution
unit Cache unit Cache
Multi-cœurs
CPU State CPU State
Execution Execution
unit unit
IFIPS-2 Cache
D. Etiemble 10
Calcul parallèle
5
Le problème de cohérence des caches
P1 P2 P3
u=? u=? u=7
Cache 4 C h
Cache 5 Cache 3
u:5 u:5
1 Composants d’E/S
u:5 2
Mémoire
1 P1 lit u Résultat
é l des d lectures
l 4 et 5
2 P3 lit u avec écriture simultanée ?
3 P3 écrit dans u avec la réécriture ?
4 P1 lit u
5 P2 lit u
IFIPS-2
D. Etiemble 11
Calcul parallèle
Cohérence des caches avec un bus
• Construite au dessus de deux
fondements des systèmes
monoprocesseurs
– Les transactions de bus
– Le diagramme de transitions d’états
des caches
• La transaction de bus
monoprocesseur P1 Pn
– Trois phases : arbitrage,
commande/adresse, transfert de
données Cache Cache
– Tous les composants observent les
adresses ; un seul maître du bus Bus
• Les états du cache
monoprocesseur Mémoire Composants d’E/S
– Ecriture simultanée sans allocation
d’écriture
• Deux états : valide et invalide Modèle mémoire SMP
– Réécriture
• Trois états : valide, invalide, modifié
• Extension aux multiprocesseurs
pour implémenter la cohérence
IFIPS-2
D. Etiemble 12
Calcul parallèle
6
La cohérence par espionnage de bus
• Idée de base
– Les transactions bus sont visibles par tous les processeurs.
– Les processeurs peuvent observer le bus et effectuer les actions nécessaires sur
les évènements importants (changer l’état)
• Implémenter un protocole
– Le contrôleur de cache reçoit des entrées de deux côtés :
• Requêtes venant du processeur, requêtes/réponses bus depuis l’espion
– Dans chaque cas, effectue les actions nécessaires
• Mise à jour des états, fourniture des données, génération de nouvelles transactions bus
– Le protocole est un algorithme distribué : machines d’états coopérantes.
• Ensemble d’états, diagramme de transitions, actions
– La granularité de la cohérence est typiquement le bloc de cache
P1 Pn
Cache Cache
Bus
Mémoire Composants d’E/S
Modèle mémoire SMP
IFIPS-2
D. Etiemble 13
Calcul parallèle
Cohérence avec cache à écriture simultanée
P1 Pn
Espionnage de bus
Cache Cache
Transaction
Composants E/S Cache-mémoire
Mémoire
– Propagation des écritures
• la mémoire est à jour (écriture simultanée)
– Bande passante élevée nécessaire
IFIPS-2
D. Etiemble 14
Calcul parallèle
7
Cohérence avec cache à écriture différée
P1 Pn
Ecriture
Espionnage de bus
Invalidation
Cache
Cache
Transaction
Composants E/S Cache-mémoire
Mémoire
• Ligne dans un seul cache
– Ecriture dans la ligne et recopie mémoire lors d’un remplacement
• Ligne dans plusieurs caches
– Ecriture dans la ligne et invalidation des lignes correspondantes dans les
autres caches
IFIPS-2
D. Etiemble 15
Calcul parallèle
Le protocole MESI
PrRd
• 4 états PrWr/—
– Exclusif
M
• Seule copie du bloc
• Non modifié (= Mémoire) BusRdX/Flush
BusRd/Flush
– Modifié
• Modifié (!= Mémoire) PrWr/—
– Partagé PrWr/BusRdX
• Copie dans plusieurs blocs E
• Identique en mémoire BusRd/
– Invalide Flush
BusRdX/Flush
PrRd/—
• Actions PrWr/BusRdX
– Processeurs
S
– Bus
BusRdX/Flush’
PrRd/
BusRd (S )
PrRd/—
BusRd/Flush’
PrRd/
BusRd(S)
IFIPS-2
D. Etiemble 16
Calcul parallèle
8
Le problème du faux partage
• Un processeur écrit dans une
partie d’une ligne de cache.
• Un autre processeur écrit dans
une autre p
partie d’une ligne
g de
cache
• Même si chaque processeur ne
modifie que sa « partie » de la
ligne de cache, toute écriture
dans un cache provoque une
invalidation de « toute » la
ligne de cache dans les autres
caches.
IFIPS-2
D. Etiemble 17
Calcul parallèle
Modèles de programmation
PARALLÉLISME DE DONNÉES TÂCHES CONCURRENTES
p
Opérations successives sur des Le pprogramme
g est décomposé
p en
PRINCIPLE données multidimensionnelles tâches concurrentes indépendantes
Données distribuées dans les Données dans une mémoire
mémoires locales (distribution, logiquement partagée
DONNEES alignement, partage)
Plusieurs espaces d’adressage Espace d’adressage unique
Un seul programme de type
séquentiel
é i l Distribué (tâches concurrentes)
- Accès aux variables partagées
CONTRÔLE Contrôle centralisé ou
- coopération entre processus
distribué
- instructions (SIMD)
- code (SPMD)
IFIPS-2
D. Etiemble 18
Calcul parallèle
9
Modèles de programmation (2) + -
Parallélisme SPSA :
Coomplexité pour le prograammeur
AUTOMATIQUE
Coomplexité pour le compiilateur
de données Un seul programme Ordonnancement du calcul
Un seul espace d’adressage Accès lointain
(HPF) Synchronisation
Mémoire
MISA :
partagée Plusieurs flots d’instructions
MANUEL
Ordonnancement du calcul
(OpenMP,P Un seul espace d’adressage Synchronisation
threads)
Passage de MIMA : MANUEL
Plusieurs flots d’instructions Ordonnancement du calcul
messages Plusieurs espaces d’adressage Accès lointain
(MPI) Synchronisation
- +
IFIPS-2
D. Etiemble 19
Calcul parallèle
Un exemple: le calcul de
1 1
0 1 x 2 dx arctan(1) arctan(0)
4
Calcul de PI/4
1,2
0,8
1/(1+x*x)
0,6
0,4
0,2
0
4
0
1
05
1
15
2
25
3
35
4
45
5
55
6
65
7
75
8
85
9
95
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
IFIPS-2
D. Etiemble 20
Calcul parallèle
10
Programme PI : version séquentielle
static long etapes = 100000;
double pas;
void main ()
{ int i; double x, pi, sum = 0.0;
pas = 1.0/(double) etapes;
for (i=1;i<= etapes; i++){
x = ((double)i
((double)i-0.5)*pas;
0 5)*pas;
sum = sum + 4.0/(1.0+x*x);
}
pi = pas * sum;
}
IFIPS-2
D. Etiemble 21
Calcul parallèle
Primitives de base en « mémoire partagée »
• Création et destruction de
threads
– CREATE (p, proc, arg) : création
de p threads qui commence à
e éc ter la procédure
exécuter procéd re proc avec
a ec
les arguments arg
– WAIT_for_end (p) : fin
d’exécution de p processus
• Variables privées et partagées
• Accès exclusif à des variables
partagées
for (i=1;i<= etapes; i++){
– LOCK(var) et UNLOCK(var) : x = ((double)i
((double)i-0.5)*pas;
0.5) pas;
accès exclusif à une région sum = sum + 4.0/(1.0+x*x)
critique de code
• Barrières -Répartir les itérations sur différents
– Barrière (nom, p) : threads
synchronisation de p threads -Réduction des sommes partielles dans
une variable globale
IFIPS-2
D. Etiemble 22
Calcul parallèle
11
PI open MP : approche SPMD
#include <omp.h> Programmes
static long etapes = 100000; double pas; SPMD :
#define NB_THREADS 2
void main () Chaque
q thread
{ int i; double x, pi, sum[NB_THREADS]; exécute le même
pas = 1.0/(double) etapes;
omp_set_num_threads(NB_THREADS)
code avec
#pragma omp parallel l’identificateur de
{ double x; int id; thread spécifiant le
id = omp_get_thread_num(); travail spécifique
for (i=id, sum[id]=0.0;i< etapes; i=i+NB_THREADS){
x = ((double)i+0.5)*pas;
du thread.
sum[id] += 4.0/(1.0+x*x);
}
}
for(i=0, pi=0.0;i<NB_THREADS;i++)
pi += sum[i] * pas;
}
IFIPS-2
D. Etiemble 23
Calcul parallèle
Programme PI OpenMP: clause privée et section critique
#include <omp.h>
static long etapes = 100000; double pas;
#define NB_THREADS 2
void main ()
{ int i; double x, sum, pi=0.0;
pas = 1.0/(double) etapes;
omp_set_num_threads(NB_THREADS)
#pragma omp parallel private (x, sum)
{ id = omp_get_thread_num();
for (i=id,sum=0.0;i< etapes;i=i+NB_THREADS){
x = ((double)i+0.5)*pas;
sum +=
+ 4.0/(1.0+x*x);}
4 0/(1 0+ * ) }
#pragma omp critical
pi += sum*pas;
}
}
IFIPS-2
D. Etiemble 24
Calcul parallèle
12
SECTIONS CRITIQUES
#pragma omp parallel private (x, sum)
{
id = omp_get_thread_num();
for (i=id,sum=0.0;i< etapes;i=i+NB_THREADS){
x = ((double)i+0.5)*pas;
sum += 4.0/(1.0+x*x);
}
#pragma omp critical
pi += sum
pii estt partagé
t é ett sum (chaque
( h processeur)) estt privé.
i é
Chaque itération pi+=sum (chaque processeur) doit être atomique.
IFIPS-2
D. Etiemble 25
Calcul parallèle
Programme PI OpenMP : For parallèle + réduction
#include <omp.h>
static long etapes = 100000; double pas;
#define NB_THREADS 2
void main ()
{ int i; double x, pi, sum = 0.0;
pas = 1.0/(double) etapes;
omp_set_num_threads(NB_THREADS)
#pragma omp parallel for reduction(+:sum) private(x)
for (i=1;i<= etapes; i++){
x = ((double)i-0.5)*pas;
sum = sum + 4.0/(1.0+x*x);
}
pi = pas * sum;
}
OpenMP ajoute 2 à 4
lignes de code
IFIPS-2
D. Etiemble 26
Calcul parallèle
13
Approche MPI
for (i=1;i<= etapes; i++){
x = ((double)i-0.5)*pas;
sum = sum + 4.0/(1.0+x*x)
ML CPU ML CPU ML CPU
-Répartir
p les itérations sur différents
ordinateurs
Réseau d’interconnexion
-Réduction des sommes partielles dans
une variable globale
• Initialiser l’environnement
• Identifier le nombre d’ordinateurs
et les identifier
• Calcul dans chaque ordinateur,
avec (ou
( sans)) communication
i ti ded
données intermédiaires
• Opération globale pour obtenir le
résultat
IFIPS-2
D. Etiemble 27
Calcul parallèle
Programme PI : version MPI
#include <mpi.h>
#include <math.h> if (myid==0)
int main(argc, argv) printf();
int argc; char *argv[]; }
{ i done=0,
int d 0 n=100000,
100000 myid,
id numprocs, ii; MPI Finalize();
MPI_Finalize();
double mypi, pi, h, sum, x; Return 0;
MPI_Init (&argc, &argv) }
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
MPI_Comm_rank(MPI_COMM_WORLD, &myid);
MPI_Bcast(&n, 1,MPI_INT, 0, MPI_COMM_WORLD);
h=1.0/(double) n; sum=0.0;
for (i=myid+1;i<= n; i+=numprocs)
{
x = ((double)i-0.5)*h;
sum+ = 4.0/(1.0+x*x);
}
mypi = pas * sum;
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE,
MPI_SUM, 0, MPI_COMM_WORLD);
IFIPS-2
D. Etiemble 28
Calcul parallèle
14
Primitives MPI utilisée dans PI
• MPI_Init (&argc, &argv)
– Initialise l’environnement MPI
• MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
– Fournit le nombre de processeurs
• MPI_Comm_rank(MPI_COMM_WORLD, &myid);
– Chaque processus reçoit son rang dans le groupe associé avec un
communicateur. Chaque processus reçoit une valeur myid différente
• MPI_Finalize
– Clôt l’environnement MPI
IFIPS-2
D. Etiemble 29
Calcul parallèle
Primitive MPI globale dans le programme PI
• MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
– La valeur de n est diffusée à chaque processus. Communication collective.
• MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,
MPI_COMM_WORLD); );
Diffusion Réduction
(Broadcast) (Reduce)
Pi= Mypi(0)+ Mypi(1)+ Mypi(2)+ Mypi(2)
IFIPS-2
D. Etiemble 30
Calcul parallèle
15
