lisation Paralléééélisation thodologie de Parall MMMMééééthodologie de lisation lisation Parall Parall thodologie de thodologie de quentiels Algorithmes Sééééquentiels dddd’’’’Algorithmes S quentiels quentiels Algorithmes S Algorithmes S

Plan du cours Plan du cours Plan du cours Plan du cours

lisation paralléééélisation 1. Principe de parall 1. Principe de lisation lisation parall parall 1. Principe de 1. Principe de 2. Graphe de tâches 2. Graphe de tâches 2. Graphe de tâches 2. Graphe de tâches 3. Ordonnancement de tâches 3. Ordonnancement de tâches 3. Ordonnancement de tâches 3. Ordonnancement de tâches parallèèèèlesleslesles algorithmes parall Complexitéééé des des des des algorithmes 4. 4. 4. 4. Complexit parall parall algorithmes algorithmes Complexit Complexit raux sultats ggggéééénnnnééééraux 5. 5. 5. 5. RRRRéééésultats rauxraux sultats sultats

lisation paralléééélisation 1. Principe de parall 1. Principe de lisation lisation parall parall 1. Principe de 1. Principe de

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

(cid:1)

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.

le graphe de précédence qui permet de définir

Elaborer 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.

Remarque

(cid:1)

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).

2. Graphe de tâches 2. Graphe de tâches 2. Graphe de tâches 2. Graphe de tâches

2.1. Notion de tâche

(cid:1)

tâche est une unité de

Une indivisible caractérisée uniquement par son comportement extérieur: entrées, sorties, instructions et temps d’exécution.

traitement

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 leur exécution est séquentielle) soit précédence (dans ce cas indépendantes et leur exécution peut être effectuée en //.

2.2. Notion de granularité

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

Exemple: Produit matriciel C=A*B

(cid:1)

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

(cid:1)

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

(cid:1)

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

(cid:1)

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.

2.3. Système de tâches

Définitions

(cid:1)

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.

indépendantes

dépendantes

(cid:1)

Les tâches Ti et Tk sont consécutives s’il n’existe aucune autre tâche Tj / Ti<<Tj<<Tk ou Tk<<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.

2.4. Graphe de précédence

Définition

(cid:1)

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.

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<<T3 T1<<T4 T1<<T5 T1<<T6 T1<<T7 T1<<T8 T2<<T3 T2<<T4 T2<<T5 T2<<T6 T2<<T7 T2<<T8 T3<<T7 T3<<T8 T4<<T6 T4<<T7 T4<<T8 T5<<T7 T6<<T8

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

T1<<T3 T1<<T4 T1<<T5

T2<<T3 T2<<T4 T2<<T5

T3<<T7 T3<<T8

T4<<T6 T4<<T7

T5<<T7

T6<<T8

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

T1 T2

T3 T4 T5

T6 T7

3. Ordonnancement de tâches 3. Ordonnancement de tâches 3. Ordonnancement de tâches 3. Ordonnancement de tâches

3.1. Le problème

(cid:1)

Dans un contexte tâches (sous- programmes, processus, fils d’exécution, …) revient à affecter à chaque tâche :

informatique, ordonnancer des

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.

3.2. Modèle de référence

(cid:1)

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

(cid:1)

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

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

T1 T2

Processeurs

T3 T4 T5

P3 T5 T7

T6 T7

P2 T2 T4 T6

Temps libre

(temps d’inactivité)

P1 T1 T3 T8

Temps

Makespan (Cmax)

Graphe de tâches Diagramme de Gantt associé

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

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

des algorithmes parallèèèèlesleslesles 4. Complexitéééé des algorithmes parall 4. Complexit des algorithmes parall des algorithmes parall 4. Complexit 4. Complexit

(cid:1)

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.

influençant

la performance peuvent être mesurés

Les critères quantitativement comme suit: Temps d’exécution. • Nombre de processeurs. • Le coût de l’algorithme ( = temps d’exécution * nombre de • processeurs) .

(cid:1)

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 (cid:1)

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

(cid:1)

//, En algorithmique supplémentaire du Pb.

le nombre p de procs est un paramètre

Définitions fondamentales

(cid:1)

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 topt) sur un nombre infini de procs.

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

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).

(cid:1)

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).

raux sultats géééénnnnééééraux 5. R5. R5. R5. Réééésultats g raux raux sultats g sultats g

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

(cid:1)

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.

(cid:1)

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

D(G)={N1,…,NH(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.

(cid:1) On

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

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.

(cid: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}

(cid:1)

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}

Autres décompositions possibles :

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

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

(cid:1)

On appellera largeur d’une décomposition D(G) le maximum des cardinaux des niveaux :

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

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

décompositions de G :

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

5.2. Tâches UET

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

Détermination de topt et de popt

Théorème

(1) Avec un nombre illimité de procs, le temps topt 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 popt permettant de réaliser un algo s’exécutant en temps topt est égal à la largeur L(G) du graphe des tâches.

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 topt = 4.

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

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

sa largeur = 3

P3 T5 T7

P2 T2 T4 T6

T5 T7

P2 T2 T4 T6

P1 T1 T3 T8

Autres décompositions :

largeur = 2

P2 T2 T4 T6 T8 P2 T2 T5 T6 T8

P1 T1 T3 T5 T7 P1 T1 T4 T3 T7

D’où, popt = 2

Nombre fixé de processeurs

(cid:1)

Problème difficile (voir plus loin) !

Algorithmes parallèles : principes et schémas de tâches

Algorithmes parallèles : principes et schémas de tâches