Introduc)on
au
parallélisme


Introduc on
au
parallélisme 

Cécile
Germain‐Renaud

cecile.germain@lri.fr

Organisa on 

•  12
séances
cours
et
TD,
4h
chacune

•  3
séances
par
Joël
Falcou

•  Les
slides
ne
suffisent
vraiment
pas

– Aide
mémoire
+
illustra ons

– Le
cours
oral
est
supposé
connu
pour
l’examen

•  Calendrier
et
toutes
informa ons
sur
le
site
du
cours

–
vous
devez
le
consulter.

www.lri.fr/~cecile/ENSEIGNEMENT/IPAR

Introduction au parallélisme 2
Contrôle
des
connaissances

•  Contrôle
con nu

– Deux
devoirs
‐
largement
commencés
en
TD.
A
rendre
à
la

date
prévue.
1
jour
de
retard
=
‐1
point.
Devoirs

individuels.


– Un
exposé.
Choix
dans
6
semaines,
exposés
+
fiche
résumé

à
la
dernière
séance.
Travail
en
binôme,
l’un
est
noté
sur
la

fiche
de
lecture,
l’autre
sur
l’exposé.

•  Examen

– Tous
documents
autorisés.
Vous
devez
amener
les

documents,
énoncés,…
u lisés
en
cours/TD.

www.lri.fr/~cecile/ENSEIGNEMENT/IPAR

Introduction au parallélisme 3
1 Plan

1.  Mo va on
et
concepts

2.  Algorithmique
parallèle

3.  Programma on 
parallèle

–  Passage
de
messages

–  OpenMP

4.  Modèles
formels

–  Parallélisa on 
automa que


–  Modèles
avancés

Introduction au parallélisme 4
1.
Mo va on
et
concepts

Introduction au parallélisme 5
Plan

•  Mo va on

•  Architectures
parallèles

–  Les
infrastructures
parallèles
en
2009

–  Typologie

–  Exemples

•  Performance

–  Accéléra on

–  Autres
indicateurs

Introduction au parallélisme 6
2 Mo va on
I
:
Les
applica ons

•  Simula on
numérique
:
expériences
in
 silico

‐
Troisième

composante
de
la
science

–  Trop
grandes
:
météorologie,
matériaux,…

–  Trop
dangereuses
:
maintenance
nucléaire

–  Trop
coûteuses
:
crash‐tests,
concep on
aéronau que

–  Impossibles
:
climat,
astrophysique


•  Informa on
 deluge

–  Puces
à
ADN

–  Traitement
personnalisé

•  Réalité
virtuelle
ou
augmentée
:
médias,
médical

Besoin
en
puissance
de
calcul
(compu ng )
virtuellement
illimités

Introduction au parallélisme 7
Mo va on
II
:
Les
ordinateurs

Toutes
les
infrastructures
de
calcul
sont
parallèles


Introduction au parallélisme 8
Mo va on
III
:
Les
sources
du
parallélisme

•  Parallélisme
de
données

– Dès
qu’on
a
des
tableaux
(à
préciser)

•  Parallélisme
de
contrôle

– High
Throughput
applica ons

– Procédures
récursives

– RPC


– …

Les
applica ons
peuvent
exploiter
les
infrastructures
parallèles


Introduction au parallélisme 9
3 Un
environnement
logiciel
stabilisé
mais
non

unifié

Résolution système linéaire Application
Spécification
Relaxation, méthode directe Algorithme
Programmation
OpenMP, HPF, pC++… LHN Compilateurs
parallèles
Environnement MPI, PVM, threads
Compilateurs d’exécution //
+ exécutifs
Programmes séquentiels
Introduction au parallélisme 10
Un
environnement
logiciel
stabilisé
mais
non

unifié

Résolution système linéaire Application
Spécification
Relaxation Algorithme
Programmation
Environnement MPI, PVM, threads Compilateurs
d’exécution //
+ exécutifs
Programmes séquentiels
Introduction au parallélisme 11
Un
environnement
logiciel
stabilisé
mais
non

unifié

Résolution système linéaire Application
Spécification
Relaxation Algorithme Programmation
OpenMP, HPF, pC++… LHN Compilateurs
parallèles
Environnement MPI, PVM, threads
d’exécution //
+ exécutifs
Programmes séquentiels
Introduction au parallélisme 12
4 Le
Top
500

•  Les
500
ordinateurs
les
plus

puissants

–  Volontariat

–  2
fois
par
an
depuis
1993.

•  Evalué
sur
Linpack,
un

benchmark
facile
et
non

trivial

•  Performance
R 
mesurée
Max
en
FLOPS

•  A
comparer
avec
R ,
la
Peak www.top500.org
puissance
indépassable.

La
barrière
du
PetaFlops
a
été
franchie
en
2008


Introduction au parallélisme 13
TOP
500
:
Nombre
de
processeurs
/
système

Novembre

2009

Introduction au parallélisme 14
Le
Top
500
en
Novembre
2009


RMax
(GFlops)

1E+07

1E+06
 PetaFlops

1E+05

1E+04

1
 10
 100
 1000
Rang
Introduction au parallélisme 15
5 Evolu on

Introduction au parallélisme 16
Linpack
est‐il
un
benchmark
per nent
?


(…)
the
LINPACK
Benchmark
is
to
solve
a
dense
system
of

linear
equa ons 
(…)



In
an
a empt 
to
obtain
uniformity
across
all
computers
in

performance
repor ng ,
the
algorithm
used
in
solving
the

system
of
equa ons 
in
the
benchmark
procedure
must

conform
to
LU
factoriza on 
with
par al
 pivo ng .
In

par cular ,
the
opera on 
count
for
the
algorithm
must
be

2/3
n^3
+
O(n^2)
double
precision
floa ng 
point
opera ons .

This
excludes
the
use
of
a
fast
matrix
mul ply 
algorithm

like
"Strassen's
Method"
or
algorithms
which
compute
a

solu on
in
a
 precision
lower
than
full
precision
(64
bit

floa ng 
point
arithme c )
and
refine
the
solu on
 using
an

itera ve 
approach.

Introduction au parallélisme 17
Gordon
Bell
Prize:
“peak
performance”

Année 
Performance

 Performance
(Gflops)

1E+07
1987 
 
450
Mflops 


1E+06
1988 
 
1
Gflops 


1990 
 
14
Gflops

 1E+05

1996 
 
111
Gflops 


1E+04

1999 
 
1.2
Tflops 


1E+03

2001 
 
11.4
Tflops 


1E+02
2005 
 
107
Tflops 


2006 
 
207
Tflops 

 1E+01

2008 
 
1.35
Pflops

1E+00

1987
 1992
 1997
 2002
 2007

2009 
 
1.84
Pflops

1E‐01

18
6 Processeur
séquen el 

•  Par e
opéra ve

Processeur •  Par e
contrôle

Automates
•  Hiérarchie
mémoire

CP
•  Bus
(au
pluriel)
 RI
Bus
Mémoire Centrale
Caches
Mémoire Principale
Introduction au parallélisme 19
La
classifica on
de
Flynn 


Degré
de
réplica on
de

Processeur la
par e
opéra ve
et

Automates de
la
par e
contrôle

CP
RI
Bus Instructions
Mémoire Centrale
SISD
 MISD

Caches
Mémoire Principale
SIMD
 MIMD

Introduction au parallélisme 20
MIMD
non
vectoriel


Exploite
les
acquis
des
architectures
de

microprocesseurs:
Hiérarchie
mémoire,
OS

Microprocesseur
 Microprocesseur
 Microprocesseur

standard
 standard
 standard

Réseau
hautes
performances

Introduction au parallélisme 21
7
Données Modèles
de
programma on
:
Djikstra/Flynn 

Parallélisme
de
contrôle
 Parallélisme
de
données



Composi on
parallèle
de
 
Composi on
séquen elle

processus
séquen els

 de
processus
parallèles



PAR(SEQ)
–
MIMD
 SEQ(PAR)
‐
SIMD

parfor
i
=
1,
n
 
forall
i
=
1,
n




 
a(i)
=
b(i)
+c(i)
 


 
a(i)
=
b(i)
+c(i)




 
x(i)
=
y(i)
+
z(i)
 
forall
i
=
1,
n




 


end
do
 


 
x(i)
=
y(i)
+
z(i)

Et
beaucoup
d’autres
modèles

Introduction au parallélisme 22
Organisa on
et
accès
mémoire 

•  Situa on
de
la
m émoire/
des
caches
par
rapport

aux
processeurs
:
 Processeur
Centralisée
ou
Distribuée

STORE LOAD •  Organisa on
de
l’e space

d’adressage:
Unique
ou
 Bus
Plusieurs

Mémoire Centrale
•  Hiérarchie
des
temps

Caches d’accès
mémoire:

Uniforme
ou
non
 Mémoire Principale
unif

Introduction au parallélisme 23
Organisa on
mémoire

+
Mémoire centralisée Espace dʼadressage unique Accès mémoire uniforme
Mémoire @Max
La partie de Mémoire MémoireLa partie de
12
Réseau 9 3
@0
6 12
9 3 PE PE PE PE PE PE PE PE
6
Plusieurs espaces dʼadressage Accès mémoire non uniforme Mémoire distribuée
Mémoire Mémoire Mémoire
Réseau @Max @Max @Max
La partie de Mémoire
PE PE PE
12
@0 @0 @0 9 3
6 12
9 3
PE PE
6 PE PE PE
-
Introduction au parallélisme 24
8
Opposé
Mémoire
Mémoire
Mémoire
Complexité Modèles
de
programma on/exécu on 

•  Espaces
d’adressage
mul ples

–  p processus

– Communiquent
par
messagerie

– Le
programmeur
ou
le
compilateur
ou
l’exécu f
doit
définir

le
placement
des
données
et
l’ordonnancement
des
calculs

– Le
placement
des
données
peut
définir
celui
des
calculs
:

ex.
OCR

•  Espace
d’adressage
unique

–  p
threads

– Communiquent
à
travers
des
variables
partagées

– Le
programmeur
ou
le
compilateur
ou
l’exécu f
doit
définir

le
placement
et
l’ordonnancement