Objectifs
• Savoir répondre aux questions suivantes:
– Quel gain potentiel à paralléliser une application ?
– Quel est le coût d’une communication réseau ?
– Comment découper une application pour la rendre
parallèle ?
– Comment répartir le travail de manière équitable ?
Architectures parallèles
• Au sein d’un processeur:
– Cœurs de calcul,
–hyper-threading,
–superscalaire,
–vectorisation
Architectures parallèles
• Au sein d’un processeur(suite):
• Cœurs de calcul, hyper-threading,
superscalaire, vectorisation
Architectures parallèles
• Au sein d’une machine:
• SMP (Symmetric Multi Processor), NUMA
(Non-Uniform Memory Architecture)
Architectures parallèles
• Entre machines:
• Grappes de calcul
Modèles à mémoire partagée
• Chaque tâche a accès à toutes les
données
Répartition des traitements
Limiter les synchronisations entre
tâches
--→ OpenMP, Pthread, Intel TBB
Modèles à mémoire distribuée
• Chaque tâche a accès à ses propres
données
• Répartition des données et communications
entre processeurs
• Une tâche effectue le traitement lié aux
donnée locales
• Règle « owner computes »
• Limiter les communications entre tâches
---→MPI
Modèles de programmation
hybrides
• Modèle distribué pour répartir sur plusieurs
nœuds
• Modèle à mémoire partagée au sein d’un
nœud
• Permet de tirer partie de la topologie de la
grappe
• Un processus MPI par nœud NUMA + threads
OpenMP
• Un processus MPI par machine + CUDA
Taxonomie de Flynn
• Classification des architectures
Théorie du parallélisme
•Parallélisation
–Utiliser plusieurs processeurs
pour traiter un problème plus
rapidement
–Généralement, seule une partie
du problème peut se paralléliser
Loi d’Amdahl
• Loi d’Amdahl
• Accélération maximale théoriquement
atteignable
• s = fraction du programme parallélisée
• 1 -s = fraction du programme séquentielle
• r = 1 / (1 -s) + (s/p)
r = 1 / (1 -s) + (s/p)
Mesures de performances
• Métriques de performance parallèle
– Evolution du temps d’exécution en fonction du
nombre de processeurs p
– Accélération (en anglais, speedup):
– Sp = Ts/Tp
• Ts: temps d’exécution du meilleur algorithme
séquentiel
• Tp: temps d’exécution de l’algorithme parallèle sur p
processeurs
Courbes de speedup
Courbes de speedup
• Plusieurs classes de speedup
• • Idéal : Tp = Ts/p
• • Linéaire: Sp= α.Si (α<1) (alpha)
• Asymptotique: Sp < β
• Superlinéaire: Sp > Si
• Dû à l’architecture (effets de cache)
• Dû à l’algorithme (algo de recherche)
Efficacité
• Efficacité: E= S/p
• Mesure le taux d’occupation
« utile » des processeurs
Quel est le coût d’une
communication réseau ?
Topologies réseau
• Comment connecter N machines à l’aide de
switch 4-ports ?
• Arbre de switches
Topologies réseau
• Comment connecter N machines à l’aide
de switch 4-ports ?
• Arbre de switches
•
Fat Tree
• Comment connecter N machines à l’aide
de switch 4-ports ?
• Fat Tree
Autres topologies
Beaucoup d’autres topologies.
Buts:
–Minimiser le nombre de sauts
(~latence)
–Maximiser la bande passante
Modèle de communication
• Propriétés
– Coût de communication (quasiment)
identique entre une paire quelconque de
nœuds
– Modèle de communication 1 –port
– Liens de communication bidirectionnels
(full-duplex)
• Coût d’échange d’un mot (word) de taille
m: ts + m Tw
• ts: temps de démarrage (startup)
• tw: temps de transfert par mot
Communications point à point
• Communications bloquantes
• Le thread émetteur se bloque jusqu’à ce
que le buffer soit utilisable:
– Après recopie dans un buffer,
– Ou après la fin de l’envoi
Communications bloquantes
• Communications non bloquantes
• Le thread émetteur ne se bloque pas
lors de l’envoi
• Réutilisation du buffer après vérification
de la terminaison
Communications non bloquantes
Communications collective
• Ensemble d’opérations de communication
impliquant un groupe de nœuds
• Exemple: diffusion 1-to-n (Broadcast)
• Un processus diffuse un message de taille
m à tous les autres
• Algorithme naïf:
– Le processus émetteur envoie à chacun des
autres processus
– n-1 étapes
Communications collective
• Ensemble d’opérations de communication
impliquant un groupe de nœuds
Exemple: diffusion 1-to-n (Broadcast)
• Un processus diffuse un message de taille
m à tous les autres
• Autre algorithme :
– log n étapes
– Algo optimal dépend de la topologie
– Temps d’exécution: log n . (ts + tw.m)
All-to-all: exercice
• Diffusion all-to-all
–Tous les processus envoient un
message de taille m à tous les autres
• Exercice:
–Écrire l’algorithme
–Calculer le temps d’exécution
All-to-all: solution
• void all_to_all( int my_rank, message m, int m_size) {
for(int i=0; i<log(n); i++) {
int offset = 1<<i;
int direction = my_rank & offset;
int dest;
if(direction == 0) {
dest = my_rank + offset;
} else {
dest = my_rank - offset;
}
send(m, m_size, dest);
recv(&m[ m_size], m_size, dest);
m_size *=2;
}
}
Communications collective
• Diffusion (Broadcast)
• Distribution (Scatter)
• Collecte (Gather)
• Reduction (Reduce)
Communications collective
•
Communications collective:
diffusion all-to-all
Communications collective collecte all-to-all
• Collecte n to 1 (Gather)
• Collecte n to n (AllGather)
Communications collective: Réduction all-to-all
• Reduction n to 1 (Reduce)
•
•Comment découper une
application pour la rendre
parallèle ?
Parallélisme de données
• Parallélisation basée sur la distribution des
données
• Distribution des données
• Owner computes
• Pour un même tableau, plusieurs
distributions possible
• Maximiser le rapport entre travail local et
communication
Distribution de tableaux denses
• Distribution d’un tableau 1D
• Par bloc, cyclique (élément par élément), bloc-
cyclique
Distribution de tableaux denses:
Distribution d’un tableau 2D
Exercice
• Multiplication de matrices NxN
• Comment distribuer les matrices sur 4 processus ?
• Écrire le code exécuté par les processus
• Calculer l’occupation mémoire pour chaque processus
Exercice
• Multiplication de matrices NxN
• Comment distribuer les matrices sur 4
processus ?
• Écrire le code exécuté par les processus
• void matmul(float**A, float**B, float**C, int n)
{
int i, j, k;
for(i=0; i<n/2; i++) {
for(j=0; j<n/2; j++) {
C[i][j] = 0;
for(k=0; k<n; k++) {
C[i][j] += A[i][k] * B[k][j];
} }}}
Multiplication de matrice compléxité
• Multiplication de matrices NxN
• Occupation mémoire pour chaque processus:
Problème de scalabilité en mémoire
• Communications: 0
Multiplication de matrice
algorithmes alternatifs
• Pas de duplication des données
• Occupation mémoire pour chaque processus:
• phases de communication
• Algorithmes de Cannon, Fox, Snyder
Multiplication de matrice
algorithmes alternatifs
• phases de communication
• Algorithmes de Cannon, Fox, Snyder
Parallélisme de tâches
• Parallélisation basée sur la décomposition
du calcul
• Décomposition en tâche
• Ordonnancement des tâches de calcul
Exemple: Choleski factorization
Data parallelism vs task parallelism
• Choleski parallélisé avec un #pragma omp
parallel for
Choleski parallélisé avec des tâches
• Comment répartir le travail
de manière équitable ?
Équilibrage de charge
• But de la parallélisation:
Réduire le temps d’exécution
~ équilibrer le temps d’exécution
entre threads
• Load balancing
Load balancing
Équilibrage de charge
• 3 niveaux de difficulté:
Facile: cas régulier – n jobs de même coût
• Difficile: cas irrégulier – n jobs de coût différent,
mais connu
Équilibrage de charge
• Difficile: cas irrégulier – n jobs de coût différent,
mais connu
• Très difficile: le coût des jobs est inconnu à
l’avance
Répartition statique
• Répartition statique du travail entre les
threads
• Répartir les données de manière équitable
• Pas de communication pendant l’exécution
• En OpenMP: schedule(static)
Répartition statique(suie..)
• Efficace pour les cas homogènes
Difficile dans certains cas
• Ressources de calcul hétérogènes
• Travail irrégulier
Répartition dynamique
• exemple:
• recherche dans un arbre
• Recherche d’une valeur
• dans un arbre/graphe
exemple: recherche dans un
arbre
• Répartition statique
• Créer une tâche et l’affecter à un CPU inutilisé
•
exemple: recherche dans un
arbre
1 task queue
maître esclave
• Une liste de tâches à exécuter
• Gérée par un thread manager (maître-esclave)
• Ou une structure de donnée protégée par un
lock
– ex: schedule(dynamic) d’OpenMP
1 task queue
maître esclave
• Problèmes
• Granularité des tâches
– Ne pas créer de tâches trop petites
• Pas de localité
• Contention sur le manager/lock
1 task queue
maître esclave
Task queue multiples
vol de tâches
• Une liste de tâches par thread
• Conserve la localité des données
• Pas de contention
Task queue multiples
vol de tâches
• Une liste de tâches par thread
• Conserve la localité des données
• Pas de contention
• Quand liste locale vide: vol de tâche
– Qui voler ?
– Voler une « grosse » tâche
• Deque (Double-ended queue)
Task queue multiples
vol de tâches
7 dwarves of HPC
• A dwarf is an algorithmic method that
captures a pattern of computation and
communication.
•
7 dwarves of HPC:
Complete list: [Link]
• Dense Linear Algebra
• Sparse Linear Algebra
• Spectral Methods
• N-Body Methods
• Structured Grids
• Unstructured Grids
• MapReduce
Exercice: Mandelbrot
• L’application mandelbrot_seq.c
calcule les éléments de l’ensemble de Mandelbrot
• Pour chaque “pixel”, un calcul est effectué
• La quantité de calcul nécessaire à chaque pixel
donne une couleur
– Blanc beaucoup de calcul
– Noir très peu de calcul
Exercice: Mandelbrot(suite..)
• Modifiez l’application pour assurer
l’équilibrage de charge
• De manière dynamique
• De manière statique
