1
PARADIGME DU PARALLÉLISME
ALGORITHMIQUE
Principe Parallélisme des
2
algorithmes
Déterminer les sous-traitements indépendants
dans l’objectif de les traiter sur des unités
d’exécution
Proposer un nouveau ordre d’exécution tout en
gardant le même comportement
Problème :
Comment déterminer un ordre d’exécution ?
Comment modifier un ordre d’exécution ?
Comment évaluer le parallélisme au niveau
algorithmique ?
Démarche du parallélisme des
3
algorithmes
Transformer l’algorithme sous la forme d’un modèle
Graphes, matrices
Fouiller le modèle pour dégager les traitements
indépendants
instructions, tâches, itérations, …)
Proposer un ordonnancement
Modifier le modèle (l’algorithme) pour augmenter le
niveau du parallélisme
Appliquer les techniques de parallélisme (déroulage des
boucles, pipeline logiciel, …)
Parallélisme des algorithmes
4
Représentation de l’algorithme
en graphe
Différents types de graphes,
permettant de représenter :
Les instructions
Les boucles (1 ou plusieurs)
Les dépendances des données
entre les instructions (dans la
même itération, dans la même
boucle, à travers les boucles)
Les itérations des boucles
Algorithme des applications
5
Reconstruction Supervision Pilotage Supervision
Jeux vidéo Simulation
4D médicale automatique industrielle
météorologique
Pour i de … à … faire
…
Pour i de … à … faire
Inst-1
Inst-2
…
Inst-n
Fin pour
…
Fin pour
Augmentation du temps d’itération
Temps d’exécution important
Augmentation du nombre des
!!
boucles
Modèle de parallélisme
6
Parallélisme algorithmique
Parallélisme
des itérations
des itérations &
des instructions
* 20 des instructions
* 10 Déroulage
* 10 de degré 2
Inst-1
Inst-2
Inst-1
Contraintes de dépendances de données ??
Optimisation au niveau
8
algorithmique
Parallélisme Itération Instruction
Sans dépendances de
Déroulage de boucles Retiming
données
Avec dépendances de Loop Stripping Retiming
données Loop Tiling multidimensionnel
Appliquer le parallélisme au niveau des itérations ET au
niveau des instructions
Syntaxe :
9
ForAll k=0 to 1 do
For i =1 to 10 do Déroulage For i =0+k*5 to (k+1)*5 do
… d’ordre 2 …
… …
EndFor EndFor
EndForAll
Technique de « Split & merge »
10
Déroulage de boucles : principe
11
Dupliquer une boucle n fois à exécuter en parallèle
Exemple : boucle avec nombre d’itération = 20
* 20
* 10
Déroulage de degré 2
* 10
*7
*7 Déroulage de degré 3
*6
*5
*5 Déroulage de degré 4
*5
*5
Minimisation du nombre des cycles
Augmentation du nombre des UC
Déroulage de boucles : Optimisation
12
Choix du déroulage : basé sur les nouvelles valeurs
du temps et du nombre des UC
Cas d’applications complexes à plusieurs boucles :
Déterminer tous les déroulages possibles
Tester toutes les combinaisons
Enorme temps d’exploration architecturale
Exploration partielle de l’espace de solution
Heuristique d‘optimisation
Déroulage de boucles:
13
Caractéristiques
* 20
L = 180
* 10 Déroulage de L = 90
Temps1
* 10 degré 2 d’exécution
*7
*7 Déroulage de L = 60
*6
degré 3
1
*5 2
L = 45
*5 Déroulage de 3
*5 degré 4 4
NB CPU
*5 5
6
7
1 8
2
3
4
Plus le degré de factorisation est petit,
5
6
plus le gain est important
7
8
9
Exemple :
14
25 25
50 50 50 10
*2 *5 *5
*10 * 10 * 10
*2
*5 *5
*2
*2
*2
T= 100 T= 60 T= 50
1 UC 5 UC 2 UC
Parallélisme par traitement
15
complémentaire
Traitement parallèle : duplications des
données dépendantes
S: tableau [1 ..10]
Convergence des données dépendantes
Somme des S[]
Graphe Flot de Données
16
Multidimensionnel (GFDM)
GFDM
Algorithme
Pour k de 0 à m faire (0, 0)
(1, -1)
Pour j de 0 à n faire
D(k , j) = B(k-1 , j+1) × C(k-1,j-1) (0, 0) (1, 1)
A(k , j) = D(k , j) × 5
B(k , j) = A(k , j) + 1
(0, 0)
C(k , j) = A(k , j) + 2
Fin pour
Fin pour
e: uv , d(e) = ( x , y )
Espace d’itération & graphe de
17
dépendances des données
Graphe de Espace d’itérations
dépendances
Loop striping : principe (1/2)
18
Algorithme GFDM Espace d’itération
Loop striping : principe (2/2)
19
Principe : exécuter des itérations en parallèle
Objectif : aucune dépendances de données
entre les itérations exécuter ensemble
Loop striping : démarche
20
Déterminer deux paramètres :
f : le nombre des itérations collectées dans le
même groupe
g : le sens de collection des itérations
Déterminer g :
Déterminer un vecteur b tel que b.d(e) > 0 pour
tout d(e) ≠ (0, …, 0)
g est un vecteur orthogonal à b
Exemple :
21
Déterminer b (x,y) tel que :
(1,0) * (x,y) > 0
(0,1) * (x,y) > 0
(-1,1) * (x,y) > 0
y > x > 0 b =(1,2) g = (-2, 1)
Loop striping : génération de
22
l’algorithme
Les instructions des itérations collectées sont regroupées
dans la boucle interne pour les exécuter en parallèle.
Un ensemble d’itérations sont exécutés en amont de la
boucle interne, intitulées prologue.
Simultanément, d’autres itérations sont à exécuter en aval,
intitulées épilogue.
Épilogue
prologue
exemple : transformation de
23
l’algorithme