Méthodologie de parallélisation
Méthodologie de parallélisation
Computer Science (Task Scheduling and Parallel Computing) · notes
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
Cette conférence traite de la méthodologie de parallélisation dans le cadre de l'informatique parallèle. Elle s'inscrit dans un cours sur l'optimisation et l'exécution efficace des programmes en environnement multiprocesseur. Le contenu aborde la notion de système de tâches, la représentation par graphes de précédence, ainsi que l'ordonnancement optimal des tâches sur plusieurs processeurs.
La parallélisation d’un programme repose sur sa décomposition en tâches. Cette segmentation n’est pas unique et dépend de la granularité choisie, c’est-à-dire de la taille des tâches à paralléliser. Par exemple, dans un calcul matriciel où l’on effectue pour i et j de 1 à n l’opération :
pour i=1 à n faire
pour j=1 à n faire
Y(i) = Y(i) + A(i,j) * X(j)
fin pour j
fin pour i
On peut définir une tâche comme l’opération élémentaire Y(i) = Y(i) + A(i,j) * X(j), correspondant à la boucle interne, ou regrouper plusieurs opérations pour obtenir une granularité plus grosse. Une granularité fine correspond à une tâche élémentaire, ce qui conduit à 2n² tâches. Plus la granularité est fine, plus le parallélisme potentiel est élevé.
Une tâche est une unité indivisible caractérisée par :
La tâche est donc représentée par le quadruplet (Ei, Si, Fi, Θi).
Quelques remarques importantes :
Un système de tâches S = (T1, ..., Tn, <<) est un ensemble de tâches muni d’une relation d’ordre partiel <<. Cette relation signifie que Ti << Tj (avec i ≠ j) indique que l’exécution de la tâche Tj ne peut commencer que si Ti a terminé.
La relation d’indépendance entre deux tâches Ti et Tj est définie par la relation de Bernstein :
Si ∩ Sj = Si ∩ Ej = Ei ∩ Sj = ∅
Cette condition est nécessaire mais non suffisante pour que les deux tâches puissent s’exécuter en parallèle.
Quelques propriétés de la relation << :
Le graphe de tâches (GT) est un graphe orienté acyclique représentant les relations << entre les tâches. Chaque nœud correspond à une tâche, et un arc orienté Ti → Tj existe si Ti << Tj.
Pour obtenir le graphe de précédence (GP), on élimine les arcs transitifs du GT. Par exemple, si Ti << Tj et Tj << Tk, alors l’arc direct Ti << Tk est transitif et doit être supprimé dans le GP.
On distingue également le graphe de fermeture transitive (GFT), qui complète le graphe avec tous les arcs transitifs.
La connaissance du GFT rend la relation de Bernstein nécessaire et suffisante pour déterminer si deux tâches peuvent s’exécuter en parallèle.
Le graphe de précédence S = (T1, ..., Tn, <<) peut être représenté par une matrice d’adjacence A d’ordre n, où :
aij = 1 si Ti << Tj, sinon 0
Cette matrice est creuse et, après un tri topologique des nœuds (numérotation des tâches telle que si Ti << Tj alors i < j), elle est triangulaire supérieure.
Si la matrice A comporte des 1 sur la diagonale, cela indique que le programme est séquentiel.
Les dépendances entre tâches sont cruciales pour l’ordonnancement et la communication entre processeurs. On distingue :
Seule la dépendance de flux (RAW) engendre des coûts de communication entre tâches.
L’ordonnancement consiste à affecter à chaque tâche Ti un temps de début d’exécution tdb(Ti) et un processeur Proc(Ti). On note :
L’ordonnancement ORD est défini par :
ORD = {Ti (tdb(Ti), Proc(Ti))}
avec les contraintes :
tdb(Ti) + Θi ≤ tdb(Tj) ou tdb(Tj) + Θj ≤ tdb(Ti)
La durée totale d’exécution Tp (makespan) est :
Tp = max_i [tdb(Ti) + Θi]
L’objectif est de minimiser Tp pour obtenir un ordonnancement optimal Topt.
Le temps optimal Topt correspond à la longueur du chemin critique dans le graphe de précédence GP :
Topt = max_i [tdb(Ti) + Θi]
Pour chaque tâche Ti, on définit :
Dans le cas sans dépendance (<< vide), les temps au plus tôt sont nuls, et les temps au plus tard sont égaux à la durée des tâches. Plusieurs ordonnancements sont possibles avec le même coût Topt.
Dans le cas général avec dépendances, on calcule Topt et les temps teti et teTi pour chaque tâche afin de définir un ordonnancement optimal.
L’algorithme de balayage par prédécesseur permet de calculer les temps au plus tôt :
tet = 0, Topt = 0
pour k = 2 à n faire
pour i = 1 à k-1 faire
si a_ik = 1 alors
tet_k = max(tet_k, tet_i + Θ_i)
fin pour i
Topt = max(Topt, tet_k + Θ_k)
fin pour k
Les tâches sans prédécesseurs commencent à 0.
Le calcul des temps au plus tard se fait en partant de Topt :
te_T = Topt pour toutes les tâches
pour k = n à 1 faire
pour i = k+1 à n faire
si a_ik = 1 alors
te_Tk = min(te_Tk, te_Ti)
fin pour i
te_Tk = te_Tk - Θ_k
fin pour k
Les tâches pour lesquelles teti = teTi sont dites critiques. Elles forment le chemin critique, qui détermine la durée minimale d’exécution Topt.
Le graphe de précédence est décomposé en niveaux Nk, où chaque niveau regroupe des tâches pouvant potentiellement s’exécuter en parallèle :
On définit deux décompositions :
La largeur du graphe est définie comme :
Le nombre optimal de processeurs Popt satisfait :
n / h(G) ≤ Popt ≤ min(Lt, LT)
où n est le nombre total de tâches et h(G) la hauteur du graphe.
Dans l’exemple étudié, on obtient :
max(Lt, LT) ≤ Pmax ≤ max L(D(G))Un ordonnancement au plus tôt, au plus tard et optimal est présenté sur un système à trois processeurs. Bien que la durée Topt soit atteinte, le nombre de processeurs utilisé n’est pas optimal.