Parallélisation d’un Algorithme CNFT
Olivier Gilloire, Issa Kebe (2A)
Stéphane Vialle, Hervé Frezza-Buet
Février-Juin 2002
SIDP-SIDSupélec
La CNFT: définition succincte
• Algorithme qui permet de déterminer le meilleur neurone dans l’algorithme de Kohonen (phase de compétition)…
• Algorithme de calcul numérique intensif en virgule flottante, régulier.
• Exemple : extraction de contours démo
La CNFT: objectifs du projet
1. Concevoir une algorithmique parallèle et séquentielle optimisée pour la CNFT
2. Développement parallèle optimisé en environnement de bas niveau (C, MPI, Pthreads)
3. Développement parallèle en environnement de haut niveau (bibliothèque ParCeL-6/NRV)
4. Expérimentation sur Cluster de PC multiprocesseurs :
Séq +Parallèle ShM +Blocage en cache +Parallèle Cluster
L’algorithme CNFT
Version séquentielle de référence
L’algorithme CNFT
• Données de type double (utilisation du FPU)
• Balayage d’une image d’entrée de taille m x m• Influence du voisinage dans un rayon n avec un
poids précalculé « chapeau mexicain »
• Environ M.N calculs, M=m² et N=n²
• Démonstration
L’algorithme CNFT• Erreur = |Sortie(influence ) - Sortie(influence n)|• Taux d’erreurs en fonction du rayon d’influence :
minimal à partir de 35 : nmin = 35
Taux d'erreur
0%10%20%30%40%50%
0 10 20 30 40Taille de masque
Tau
x d'
erre
ur Taux d'erreur
L’algorithme CNFT
• Performances (image 300x300, voisinage 50, 10 itérations)– Algorithme « naïf » : 2m27s– Avec optimisations sérielles : 44s
+70,1%(Loop Unrolling, etc…)
L’algorithme CNFT• Performances en séquentiel, en fonction de la
taille du fichier d’entrée… cache resonance!
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
0 200 400 600 800 1000 1200 1400
Taille du fichier d'entrée (Ko)
Vit
esse
(p
ts/s
)
256Ko 1024Ko
Athlon 1GHz, L2=256Ko, L1=64Ko
L’algorithme CNFT• Performances en fonction de la taille du voisinage
pris en compte… cache resonance!
0
100
200
300
400
500
10 100 1000 10000Occupation RAM (Ko)
Vit
esse
(M
flop
s)
P-III Xeon 700MHzL2=1Mo, L1=16Ko
L’algorithme CNFT
• Performances indépendantes de la taille du fichier
• Performances dépendantes de la taille du voisinage (vs. taille cache).
• Bilan de l’algorithme séquentiel :– Optimisation de l’utilisation des caches– Parallélisation : décomposition en domaines
CNFT Parallèle
Version Parallèle SPMD
CNFT Parallèle Multiprocesseur
• PC à mémoire partagée - Pthreads• Découpage de l’image en tranches
horizontales• SPMD-Barrière de synchronisation
• Pas de problèmes de False Sharing (perte du cache)
• Pas d’exclusions mutuelles nécessaires
• Démonstration du balayage
P0
P1
P2P3
CNFT Parallèle Multiprocesseur• Performances en fonction de la taille de voisinage, sur QuadX1:
PC 4-Xeon 700MHz, L2=1Mo, L1=16Ko, RAM=1Go
0
200
400
600
800
1 000
1 200
1 400
1 600
10 100 1 000 10 000
Occupation RAM (Ko)
Vit
esse
(M
flo
ps)
X1-1proc
X1-2proc
X1-4proc
CNFT Parallèle Multiprocesseur• Accélération réelle sur QuadX1 • MAIS Fonction de la taille de voisinage
0,0
0,5
1,0
1,5
2,0
2,5
3,0
3,5
4,0
10 100 1 000 10 000Occupation RAM (Ko)
Sp
eed
Up
(vs
. Séq
. Op
tim
isé)
SU-2 processeurs SU-4 processeurs 1 P-III Xeon
CNFT Parallèle Multiprocesseur
• Performances (image 300x300, voisinage 50, 10 itérations)– Parallèle sur 4 processeurs avec optimisations
sérielles :
12,7s +91,2%(+71% par rapport au séquentiel optimisé)
CNFT Parallèle Multiprocesseur
• Bilan parallélisation en mémoire partagée :– Gain de performances x4 dans le cache
– Les performances s’écroulent en dehors du cache :• En Mflops : normal
• En Speed up : anormal (S < 1,2 pour 4 processeurs)
• Phénomène classique sur PC multiprocesseur.
• Nécessité de blocage des données à la taille du cache
CNFT Parallèle Bloquée
Nouvelle optimisation sérielle :blocage des données en cache
CNFT Parallèle Bloquée
• Dans chaque thread : – Limite du calcul à un sous-ensemble du
voisinage– Nécessité de plusieurs passes (sommes
partielles)
• Démonstration
CNFT Parallèle Bloquée• Performances sur QuadX1, 4 PIII-Xeon
utilisés (700 MHz, L2=1Mo, L1=16Ko)• Chute réduite/annulée hors du cache
0
500
1 000
1 500
2 000
10 100 1 000 10 000Occupation mémoire (Ko)
Vit
esse
(M
flop
s)
sans blocageblocage 100Koblocage 10Ko
CNFT Parallèle Bloquée
• Bilan du blocage– Ce type de problèmes se prête bien au blocage– Blocage efficace mais imparfait, impossible de
contrôler précisément le niveau de performances– Performances aussi grandes sur des processeurs
simples (Athlon, Pentium…) que sur des Pentium III Xeon (2Mo cache, quadri-processeurs…)
L’algorithme CNFT
Version Cluster MPI
CNFT Parallèle Cluster
• Même distribution de données qu’en parallèle local
• Conservation du multithread sur nœud multiprocesseur
• Utilisation de MPI : envoi de messages
• Utilisation d’un maître pour la gestion des données (le numéro 0).
!
"# $
Ethernet 100Mbits
CNFT Parallèle Cluster• Évaluation des pertes dues à MPI
Pertes indépendantes de la taille de l’image
0
200400
600
8001 000
1 200
1 4001 600
1 800
100 1 000Taille de fichier (Ko)
Vit
esse
(Mfl
ops)
QuadX2 : 4 threads-4 procs
QuadX1+QuadX2 : 4 threads - 8 procs
Comparaison de deux configurations à 4 threads :
CNFT Parallèle Cluster• Performances en fonction de la taille de voisinage
(Volume de communications constant)
0
500
1 000
1 500
2 000
2 500
3 000
3 500
10 100 1 000 10 000Occupation mémoire(Ko)
Vit
esse
(Mfl
ops)
4 threads-4 procs sur QuadX28 threads-8 procs sur QuadX1+X2
Comparaison de deux configurations à 4 et 8 threads :
CNFT Parallèle Cluster• Accélération en fonction de la taille du
voisinage : globalement bénéfique
0
1
2
3
4
5
6
7
8
10 100 1 000 10 000Occupation mémoire (Ko)
Sp
eed
Up
vs.
Séq
Op
tim
1 X
eon
SU 2x4 proc - 2x4 threads
SU 1x4 proc - 1x4 threads
2 machines
1 machine
CNFT Parallèle Cluster
• Inefficace pour des voisinages trop petits.
• Mais dans un cas réel (n 35 50Ko), gain de performances notable.
• Supérieur au multiprocesseur en terme de €/Mflops dans la zone de rendement optimal (données 100Ko).
CNFT Cluster• Test sur un cluster plus étendu :
6 machines/14 processeurs : 6,2 Gflops en pointe.
502
1 928
3 650
6 124
0
1 000
2 000
3 000
4 000
5 000
6 000
7 000
Vit
esse (
Mfl
op
s)
P-III Xeon700MHz (1 cpu)
Quadri P-IIIXeon (4 cpu)
2 Quadri P-IIIXeon (8 cpu)
Cluster ERSIDP(14 cpu)
Calcul CNFT1152x1152, 2 cycles de calcul
x3,83
x7,26
x12,2
Courbe de performances sur Cluster• Speed up en fonction du nombre de
processeurs : proche de l’optimumCNFT - SpeedUp 400x400, 2 cycles de calcul Rayon de
voisinage: 32
02468
10121416
0 5 10 15Nombre de processeurs
Spe
ed u
p
SU 400x400 n=32
SU 1152x1152, n=128
SU idéal S(P)=P
Référence séquentielle : programme optimisé sur unP-III Xeon 700MHz, 1Mo de cache
Conclusion
• L’élément d’importance majeure dans ces algorithmes est le cache.
• Nécessité de « cache-driven parallelization ».
• Bon résultat général sur un calcul flottant intensif :
• Version séquentielle naïve : 120Mflops puis : 502
1 928
3 650
6 124
0
1 000
2 000
3 000
4 000
5 000
6 000
7 000V
ites
se (
Mfl
op
s)
P-III Xeon700MHz (1 cpu)
Quadri P-IIIXeon (4 cpu)
2 Quadri P-IIIXeon (8 cpu)
Cluster ERSIDP(14 cpu)
Calcul CNFT1152x1152, 2 cycles de calcul
x3,83
x7,26
x12,2
Parallélisation d’un Algorithme CNFT
Questions ?