Embed Size (px)
Citation preview
Analyse et mesure de performancesdu calcul distribué
Mohsine Eleuldj
Département Génie Informatique, EMI
CruCID Workshop, EMI, Rabat, 5 au 7 juillet 1999
2
Motivation
• Types d’applications :– Ensemble immense de données : prévision météorologique, sismique,
intelligence artificielle (traitement de l’image, reconnaissance de forme,…) recherche médicale (réaction chimique), recherche militaire (simulation des armes), recherche spatiale…
– Temps réel : réservation des billets d’avion, pilotage automatique d’un avion, gestion d’une centrale nucléaire,…
• Solution : traitement parallèle, concurrent, simultané, pipeline, réparti, distribué,…
3
Plan• Introduction
• Calcul distribué
• Mesures de performance
• Analyse des algorithmes
• Equilibre des charges
• Granularité
• Extensibilité
• Ordonnancement
• Sources d ’interblocage
• Conclusion
4
Niveaux de traitement parallèle
• Niveaux– Travail ou programme (Job) : multitraitement
– Tâche ou procédure : décomposition du programme
– inter-instruction : analyse de la dépendance des données, vectorisation
– Intra-instruction : type de contrôle (micro-progammation ou câblage)
• Evolution : le matériel remplace le logiciel– Coût du matériel diminue et logiciel augmente
– Augmentation de la vitesse (application temps réel)
– Tolérance aux pannes
5
Mécanismes de Traitement parallèle dans un monoprocesseur
• Multiplicité des unités fonctionnelles : additionneur, mutilpieur, virgule flottante…
• Parallélisme et pipeline dans l’UCT (processeur)• Chevauchement des opérations de l’UCT et des E/S : DMA,
cannaux d’E/S, E/S programmées• Système de mémoire hiérarchique : mémoire virtuelle• Equilibrage des tâches bornées par le calcul et celles bornées par
les E/S• Multiprogrammation (chevauchement entre le CPU et les E/S)
et le temps partagé (efficace en interactif et application tempsréel)
6
Classification architecturale
Basée sur la multiplicité du flot d’instructions et le flot de données (Flynn 1966) :
• SISD : Single Instruction Single Data stream (ordinateur conventionnel)
• SIMD : Single Instruction Mulitple Data stream (Cray 1:ordinateur vectoriel)
• MISD : Multiple Instruction Single Data stream
• MIMD : Multiple Instruction Multiple Data stream (Cray 2, MPP)
Basée sur l’utilisation de la mémoire• Système à mémoire partagée (Cray 1)
• Système à mémoire distribuée (Cray 2)
7
Calcul distribué - Plate forme
Réseau de communication
Cray J916(6 processeurs)
Réseau local 1 Réseau local 2
P
P : est un poste de travail (PC, Station de travail, SIMD, MPP,...)sous un système d ’exploitation (Unix, Windows, SunOS,…)
P P P P P P P
8
Calcul distribué - Principe
• Décomposition du problème en plusieurs processus
• Répartition des processus sur les différents processeurs (selon le modèle maître/esclave, arborescent,...)
• Possibilité d’échange de messages au cours du traitement
• Combinaison des résultats des processus afin de résoudre le problème de départ
9
Calcul distribué - Objectifs
?⇒⇒⇒⇒ amélioration de la performance
Programme séquentiel+
fonctions MPI
programme parallèle
Performance P = 1/t où t est le temps d ’exécution
Objectifs : amélioration de la performance
10
Calcul distribué - Eléments de performance
• Taille de l’exemplaire
• Algorithme (itératif, diviser-pour-régner,…)
• Equilibre des charges, Granularité, Extensibilité, Ordonnancement
• Paradigmes de parallélisation (maître/esclave, arborescent, …)
• Bibliothèques (MPI, PVM,…)
• Langage (Fortran, C, …), Compilateur (vectorisation, …)
• Système d ’exploitation (Linux, Windows NT, Windows 95/98,…)
• Protocole de communication (Ethernet, TCP/IP, ATM…)
• Architecture (mémoire partagée, distribuée)
• Processeurs (nombre, fréquence, …), Mémoire (temps d ’accès)
11
Mesures de performance - Accélération
• Accélération (Speed up)
A = T(1,n)/T(m,n)
où T(1,n) et T(m,n) sont les temps d ’exécution du programme avec 1 et m processeurs respectivement sur un exemplaire de taille n
• Efficacité E = A/m
• En général 1 ≤ A ≤ m et E ≤ 1
si A > m alors sur-accélération
12
Accélération - Exemple
… … …… … …… … …… … …… … …… … …… … …… … …… … …
Supposons que T(1,n) = cn2 où n : ordre de la matrice et c : constanteEn négligeant les temps de communication
T(9,n) = T(1,n/3) = cn2/9A = T(1,n)/T(9,n) = 9 et E = A/9 = 1
… … …… … …… … …… … …… … …… … …… … …… … …… … …
n
n
13
Mesures de performance - Parallélisme
Degré de parallélismeD(t) = nombre de processeurs utilisés pendant l’instant t
avec m processeurs (D(t) ≤ m)
∫−=
2
112)(
1 t
tdttD
ttD
Degré moyen de parallélisme
où t1 et t2 les temps de début et fin de l ’exécution
∑=−
=2
112)(
1 t
tt
tDtt
DD(t) est discrète ⇒
14
Degré de parallélisme - Exemple
8 9 10 11 127654
1
2
3
4
5
6
7
8
9
10
temps
processeurs
Degré de parallélisme
Exemple : D = (1 + 4 + 8 + 6 + 5 + 3 + 4 + 1) / 8 = 4
15
Analyse des algorithmes
Notion d ’ordreO(f(n)) = {t:N > R*/ (∃c ∈ R+)(n0 ∈ N)( ∀n> n0 ) [t(n) < cf(n)]}t(n) est de l’ordre de f(n)
Soit t(n) le temps d ’exécution d ’un algorithme sur un exemplaire de taille nt(n) ∈O(log n) ⇒ algorithme est logarithmique t(n) ∈O(n) ⇒ linéairet(n) ∈O(n2) ⇒ quadratiquet(n) ∈O(p(n)), où p polynôme ⇒ polynomialt(n) ∈O(f(n)), où f exponentielle⇒ exponentiel
Classes des problèmes : P, NP, NP-complet
16
Analyse des algorithmes - Exemple
⇒ t(n) ∈O(n2)
Calcul des sommes partielles Si (1≤ i ≤ n)
∑=
=i
j
i jS1
ncnbnnnabiabantn
i
n
i
i
j
*2/)1()()()(11 1∑∑ ∑
== =
≤++=+=+=
pour i=1 à n faireS(i) � 0pour j=1 à i faire
S(i) � S(i) + j
Soient a et b les temps de la mise à zéro et de l’addition
17
Equilibre des charges - Exemple
Calcul des sommes partielles Si (1≤ i ≤ 256) sur 8 processeurs
Supposons que le temps de communication est négligeable devant le calculT(8) = Max(t(p1),t(p2),…,t(p8))
∑=
=i
j
i jS1
pour i=1 à 256 faireS(i) � 0pour j=1 à i faire
S(i) � S(i) + j
18
Equilibre des charges - Affectation 1
128 150 192 224 2569664321
p1 p2 p3 p4 p5 p6 p7 p8
p1 exécute les itérations i=1 à 32p2 i=33 à 64…pk i=(32k - 31) à 32k…p8 i=225 à 256
19
Equilibre des charges - Affectation 1
N(k) : nombre d’additions effectuées par le processeur k
N(k) = 16 x (64k – 31)
Par pour k=1 à 8 fairepour i=(32k - 31) à 32k faire
S(i) � 0pour j=1 à i faire
S(i) � S(i) + j
20
Equilibre des charges - Affectation 1
0
1000
2000
3000
4000
5000
6000
7000
8000
p1 p2 p3 p4 p5 p6 p7 p8
Affectation 1
Temps(Affectation 1) = t(p8)
21
Equilibre des charges - Affectation 2
128 144 160 176 192 208 224 2402561129680644832161
p1 p2 p3 p4 p5 p6 p7 p8 p8 p7 p6 p5 p4 p3 p2 p1
p1 exécute les itérations i=1 à 16 et i=241 à 256p2 i=17 à 32 et i=225 à 240…pk i=(16k-15) à 16k et i=(257 - 16k) à (272 - 16k)…p8 i=113 à 128 et i=129 à 144
22
Equilibre des charges - Affectation 2
N(k) = 8 x (32k – 15) + 8 x (529 – 32k) = 8 x 514 = 4112
Par pour k=1 à 8 fairepour i=(16k - 15) à 16k et i=(257 - 16k) à (272 - 16k) faire
S(i) � 0pour j=1 à i faire
S(i) � S(i) + j
23
Equilibre des charges - Affectations
0
1000
2000
3000
4000
5000
6000
7000
8000
p1 p2 p3 p4 p5 p6 p7 p8
Affectation 1Affectation 2
Temps(Affectation 2) = t(p1) =t(p2) = ... = t(p8)
24
Equilibre de charges - Parallélisme
t4 t5 t6 t7 t8t3t2t1t0
1
2
3
4
5
6
7
8
9
10
temps
processeursAffectation 1
Affectation 2
D(Affectation 1) = 4 et D(Affectation 2) = 8
25
Granularité
Exemple : Produit matriciel C = AB où A et B deux matrices d’ordre n.
Granularité = taille de la tâche allouée à un processeur (ou processus)
temps d ’exécution = temps de calcul + temps de communicationtemps de communiquer un message de taille n est a + bn
Version 1: pour i=1 à n faireC(i,j) � 0pour j=1 à n faire
C(i,j) � 0 pour k=1 à n faireC(i,j) � C(i,j) + A(i,k) * B(k,j)
26
Granularité - Exemplesversion 2 : granularité grosse Par pour i=1 à n faireprocessus : vecteur x matrice pour j=1 à n faire
C(i,j) � 0 pour k=1 à n faire
C(i,j) � C(i,j) + A(i,k) * B(k,j)
version 3 : granularité moyenne pour i=1 à n faireprocessus : vecteur x vecteur Par pour j=1 à n faire
C(i,j) � 0pour k=1 à n faire
C(i,j) � C(i,j) + A(i,k) * B(k,j)
version 4 : granularité fine pour i=1 à n faireprocessus : scalaire x scalaire pour j=1 à n faire
C(i,j) � 0Par pour k=1 à n faire
C(i,j) � C(i,j) + A(i,k) * B(k,j)
27
Granularité - Exemples
0
5
10
15
20
25
30
Version 1 Version 2 Version 3 Version 4
ItérationsCommunication
Temps de calcul et de communication pour n=3
28
Ordonnancement
• Les processeurs alternent entre les phases de calcul et de communication
• congestion du réseau de communication réduit le débit
• ordonnancement des processus de telle sorte que lorsque certains calculent les autres communiquent
Calcul
Communication
CalculCommunication
Calcul
Calcul
p1p2
p3
p4
29
Extensibilité (scalability)
0
20
40
60
80
100
1 2 3 4 5 6 7 8
Détermination du nombre optimal de processeurs
processeurs
temps
30
Sources d ’interblocage
• Envoi d ’un grand message du processus 0 au processus 1
• communication bloquante « unsafe » (avec accusé de réception)
p0 p1
Envoyer (1) Envoyer (0)
Recevoir(1) Recevoir(0)
• Solution
p0 p1
Envoyer (1) Recevoir(0)
Recevoir(1) Envoyer (0)
31
Conclusion
• Contenu de l’exposé
– Introduction au traitement parallèle
– Mesures de performances du calcul distribué
– Techniques générales de performance
• Objectifs
– Importance de la performance
– Prévoir la performance
– Améliorer la performance
32
Références
• Ivan Lavallée, « Algorithmique parallèle et distribuée » Traité des nouvelles technologies, Hermes, 1990.
• Kai Hwang, « Advanced computer architecture: Parallelism, Sqcalability, Programmability », McGraw Hill Series in Computer Science, 1993.
• http://www.unix.mcs.anl.gov/mpi/tutorial/perf/index.html
• http://www.unix.mcs.anl.gov/mpi « MPI : A message Passing Interface Standard », Message Passing Interface Forum, 1995
