Méthodologie de Parallélisation d’Algorithmes Séquentiels

Plan du cours

1. Principe de parallélisation

2. Graphe de tâches 3. Ordonnancement de tâches 4. Complexité des algorithmes parallèles 5. Résultats généraux

1. Principe de parallélisation

Pour paralléliser un algo sur une machine // donnée, on procède comme suit :

• Partitionner l’algo en tâches (instructions ou groupes d’instructions) : ce partitionnement peut être fait automatiquement par programme ou bien au cas par cas.

• Elaborer le graphe de précédence qui permet de définir les contraintes temporelles pour l’exécution des tâches et de rechercher les tâches indépendantes, susceptibles d’être exécutées en parallèle.

• Ordonnancer ensuite les tâches sur les procs, en respectant les contraintes de dépendances, ainsi que les contraintes matérielles liées à l’architecture de la machine.

2

Remarque

• Un même algo peut conduire à plusieurs versions parallèles différentes suivant :

  - l’accès aux données,
  
  - le découpage en tâches,
  
  - l’affectation des tâches aux procs,
  
  - etc.
  

• Certaines versions seront mieux adaptées à une structure d’ordinateurs.

• Plusieurs facteurs peuvent influencer le choix de la meilleure (au sens performances) version parmi toutes les versions parallèles obtenues pour la machine utilisée (voir plus tard).

3

2. Graphe de tâches

2.1. Notion de tâche

• Une tâche est une unité de traitement indivisible caractérisée uniquement par son comportement extérieur: entrées, sorties, instructions et temps d’exécution.

• Le temps d’exécution (ou durée) d’une tâche est en général la somme de 2 termes: le temps de calcul et le temps de communications .

• L’étude des dépendances entre les tâches permet de construire un système de précédence qui traduit le parallélisme interne à l’algo.

• Dans un tel système, 2 tâches sont soit liées par une relation de précédence (dans ce cas leur exécution est séquentielle) soit indépendantes et leur exécution peut être effectuée en //.

4

2.2. Notion de granularité

Plusieurs décompositions différentes sont possibles pour un même algo.

Exemple: Produit matriciel C=A*B

• Si nous prenons comme tâches les opérations élémentaires:

C(i,j) = C(i,j) + A(i,k) * B(k,j)

la granularité de la décomposition est fine.

A B C

5

• Si chaque tâche est le calcul d’un élément de C:

Pour k=1 à n faire C(i,j) = C(i,j) + A(i,k) * B(k,j)

la granularité de la décomposition est moyenne.

A B C

6

• Si chaque tâche correspond au calcul d’une ligne ou d’une colonne du produit:

Pour j = 1 à n faire Pour k = 1 à n faire C(i,j) = C(i,j) + A(i,k) * B(k,j)

la granularité est grosse.

A B C

7

• Le choix de la meilleure décomposition est un problème difficile lié aux temps d’exécution des tâches et à l’architecture de la machine. Les principaux facteurs de choix sont :

  • Le nombre de processeurs.

  • Le rapport entre unité de temps de communication et unité de temps de calcul.

  • Les accès mémoire.

  • Etc.

8

2.3. Système de tâches

Définitions

• Un système de tâches S=(T1,…,Tn,<<) est un ensemble de tâches muni d’une relation d’ordre partiel notée <<.

≠ Ti << Tk (i k) signifie que l’exécution de la tâche Ti doit être terminée avant que l’exécution de Tk ne commence.

• 2 tâches Ti et Tk sont indépendantes si elles ne modifient aucune variable commune, sinon elles sont dépendantes .

dépendantes indépendantes

9

• Les tâches Ti et Tk sont consécutives s’il n’existe aucune autre tâche

Tj / Ti<

• Un système de tâches S=(T1,…,Tn,<<) est un système de précédence

si, pour tout couple de tâches consécutives (Ti,Tk), une et une seule des

3 conditions suivantes est vérifiée :

 - Ti<<Tk.

 - Tk<<Ti.

 - Ti et Tk sont indépendantes.

10

2.4. Graphe de précédence

Définition

• Le graphe de précédence G associé à un système de précédence S=(T1,…,Tn,<<) est défini de la manière suivante :

  • L’ensemble des sommets de G est l’ensemble des tâches de S.

  • Ti et Tk sont reliées par un arc ssi Ti et Tk sont consécutives et ordonnées par la relation <<.

• Les contraintes de précédence qui lient les tâches ont un graphe de connexion sans circuit ( DAG : Directed Acyclic Graph ).

• En cas de dépendance, il faut respecter l’ordre séquentiel des tâches.

11

Construction du graphe de tâches

Exemple

Considérons un algo composé de 8 tâches T1,…,T8 dont le système de

précédence associé est le suivant :

T1<

T2<

T3<

T4<

T5<

T6<

12

En éliminant les contraintes redondantes, on obtient l’ensemble de relations

suivantes:

T1<

T2<

T3<

T4<

T5<

T6<

13

Le graphe de précédence associé est le suivant :

14

3. Ordonnancement de tâches

3.1. Le problème

• Dans un contexte informatique, ordonnancer des tâches (sousprogrammes, processus, fils d’exécution, …) revient à affecter à chaque tâche :

  • Une date d’exécution

Un processeur

(Sous contraintes de ressources ou non)

• Le problème de l’allocation des tâches d’un prog // à un ensemble de procs est très difficile.

• On suppose ici qu’on connaisse les tâches (en particulier leur temps d’exécution ou une estimation de coût) et les relations de précédence qui les lient entre elles.

15

3.2. Modèle de référence

• Les tâches Tj (j=1..n) sont caractérisées par une durée d’exécution, et éventuellement par une date au plutôt ou une date au plus tard.

• On s’interdit la préemption: possibilité d’interrompre l’exécution d’une tâche commencée.

3.3. Objectif

• Le plus courant objectif à réaliser est de minimiser la fonction qui représente le temps d’exécution total (le makespan ).

16

Exemple précédent avec p=3 et tâches identiques un 1 ordonnancement peut être représenté par le diagramme de Gantt suivant :

Processeurs

Temps libre

(temps d’inactivité)

Temps

Col1	T5	T7	Col4
* T2*	* T4*	* T6*
* T1*	* T3*		* T8*

Makespan (Cmax)

Graphe de tâches Diagramme de Gantt associé

17

Exercice

Soit le code suivant :

For i=1,n

Tâche Ti : X(i) = B(i)/A(i,i)

For j=i+1,n

Tâche Ti,j : B(j) = B(j) – A(j,i) * X(i)

Fin

Fin

1. Que fait-il un tel programme?

2. Déterminer l’ordre séquentiel des tâches

3. Représenter le graphe des tâches

18

4. Complexité des algorithmes parallèles

• La complexité a été connue à être la plus importante mesure de

performances d’un algorithme.

• L’analyse de la complexité // permet de mesurer l’efficacité des algos //s

et de les comparer.

• Les critères influençant la performance peuvent être mesurés

quantitativement comme suit:

• Temps d’exécution.

• Nombre de processeurs.

• Le coût de l’algorithme ( = temps d’exécution * nombre de

processeurs) .

19

• Le type d’architecture // qu’on a supposé (MIMD à mémoire partagée) est idéalisé au sens où pour évaluer la vitesse d’un algo //, on néglige les temps de transfert des données.

On dit, sous ces hypothèses, qu’un algo est optimal si son temps d’exécution est minimal parmi toutes les versions possibles.

Remarques

• Il peut exister plusieurs algos nécessitant des nombres différents de procs qui s’exécutent en temps optimal.

• En algorithmique //, le nombre p de procs est un paramètre supplémentaire du Pb.

20

Définitions fondamentales

• Le problème fondamental de la parallélisation d’une méthode de calcul est de trouver un ordonnancement optimal pour affecter les tâches aux procs en respectant le graphe de précédence, de telle façon que l’algo // s’exécute en temps minimal (que l’on note t ) sur un nombre infini de opt procs.

• Dans une phase ultérieure, déterminer le nombre minimum de procs (p ) nécessaires pour effectuer l’algo en t . opt opt

• Enfin, étant donné un nombre p fixé de procs, on doit être en mesure de trouver un algo optimal.

• ∞ Les résultats asymptotiques sont obtenus quand n -> (n étant la taille du problème).

21

• ∞ ∞ On dit qu’un algo est asymptotiquement optimal quand E est max (E étant l’efficacité asymptotique).

• Pour concevoir des algorithmes parallèles éfficaces, on doit considérer les règles générales suivantes:

  • Le nombre de processeurs doit être borné par la taille du problème.

  • Le temps d’exécution parallèle doit être considérablement inférieur au temps d’exécution du meilleur algo séquentiel.

  • Le coût de l’algorithme est optimal. (attention: utiliser plus de processeurs peut augmenter le coût de l’algo).

22

5. Résultats généraux

5.1. Décompositions du graphe de précédence

• Supposons pour simplifier que toutes les tâches ont le même temps d’exécution (on le prend égal à 1). On parle alors de tâches UET (Unit Execution Time).

• Le temps d’un chemin du graphe de précédence est la somme des temps d’exécution des tâches qui le composent.

• Le plus long chemin du graphe de précédence est celui dont le temps d’exécution est le plus grand.

• La hauteur H(G) du graphe des tâches est le nombre de tâches du plus long chemin.

23

• On appellera décomposition en niveaux du graphe des tâches, l’ensemble :

D(G)={N,…,N } 1 H(G)

qui constitue une partition en H(G) sous-ensembles (niveaux) des sommets de ce graphe vérifiant les conditions suivantes:

• Le niveau 1 est constitué de tâches n’ayant aucun prédécesseur.

• Le niveau k est constitué de tâches dont tous les prédécesseurs sont dans des niveaux inférieurs et dont tous les successeurs sont dans des niveaux supérieurs.

• Le niveau H(G) est constitué de tâches n’ayant aucun successeur.

Remarque

Un même graphe peut admettre plusieurs décompositions en niveaux.

24

On appellera décomposition par prédécesseur Dp(G) la

décomposition en niveaux suivante:

• Le niveau 1 est constitué de toutes les tâches n’ayant aucun prédécesseur.

• Pour k=2 à H(G), le niveau k est constitué des tâches dont tous les prédécesseurs sont dans des niveaux inférieurs et ayant au moins un prédécesseur dans le niveau k-1.

  • Cette décomposition est aussi appelée décomposition au plus tôt.

Exemple Niveau(1) = {T1,T2} Niveau(2) = {T3,T4,T5} Niveau(3) = {T6,T7} Niveau(4) = {T8}

25

De même, on appellera décomposition par successeur Ds(G) la

décomposition en niveaux suivante:

• Le niveau H(G) est constitué des tâches n’ayant aucun successeur.

Pour k=H(G)-1 à 1, le niveau k est constitué des tâches dont tous les successeurs sont dans des niveaux supérieurs et ayant au moins un successeur dans le niveau k+1.

Cette décomposition est aussi appelée décomposition au plus tard.

Exemple

Niveau(1) = {T1,T2} Niveau(2) = {T4} Niveau(3) = {T3,T5,T6} Niveau(4) = {T7,T8}

26

Autres décompositions possibles :

Niveau(1) = {T1,T2} Niveau(1) = {T1,T2}

Niveau(2) = {T3,T4} Niveau(2) = {T4,T5}

Niveau(3) = {T5,T6} Niveau(3) = {T3,T6}

Niveau(4) = {T7,T8} Niveau(4) = {T7,T8}

27

• On appellera largeur d’une décomposition D(G) le maximum des

cardinaux des niveaux :

L(D) = max(|N |), pour k = 1..H(G) k

On appellera en fin largeur L(G) du graphe le min des largeurs des

décompositions de G :

L(G) = min(L(D))

28

5.2. Tâches UET

On étudie dans ce paragraphe le temps de calcul et le nombre de processeurs optimaux (t ) pour exécuter un algo //. opt et popt

Détermination de t opt et de popt

Théorème

(1) Avec un nombre illimité de procs, le temps t opt d’un algo // optimal est égal au temps d’exécution du plus long chemin du graphe des tâches, c-à-d H(G) (sans communications).

(2) Le nombre minimal de procs p permettant de réaliser un algo opt s’exécutant en temps t est égal à la largeur L(G) du graphe des opt tâches.

29

Exemple

Considérons le graphe de tâches à 8 tâches et supposons que toutes

les tâches sont UET .

Le plus long chemin (T1-T4-T6-T8 ou T2-T4-T6-T8) a un temps

d’exécution = 4 et par conséquent t opt = 4.

A chacune des 4 décompositions en niveaux correspond un algo //.

30

Décomposition par prédécesseur Décomposition par successeur

sa largeur = 3 sa largeur = 3

Col1	T5	T7	Col4
* T2*	* T4*	* T6*
* T1*	* T3*		* T8*

Col1	Col2	T5	T7
* T2*	* T4*	* T6*
* T1*		* T3*	* T8*

31

Autres décompositions :

largeur = 2 largeur = 2

T2	T4	T6	T8
* T1*	* T3*	* T5*	* T7*

D’où, p

opt = 2

T2	T5	T6	T8
* T1*	* T4*	* T3*	* T7*

32

Nombre fixé de processeurs

• Problème difficile (voir plus loin) !

33