Méthodologie de parallélisation

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.

Notion de système de tâches

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 :

• Ei : les entrées de la tâche Ti
• Si : les sorties de la tâche Ti
• Fi : l’opérateur appliqué sur Ti
• Θi : le coût de Ti, exprimé en nombre d’opérations élémentaires

La tâche est donc représentée par le quadruplet (Ei, Si, Fi, Θi).

Quelques remarques importantes :

• Une tâche s’exécute sur un seul processeur, de manière non préemptive.
• Le modèle est dit statique si les propriétés (Ei, Si, Fi, Θi) sont connues à l’avance.
• Dans un programme séquentiel segmenté, on obtient un ensemble de tâches PS = (T1, ..., Tn, →) où → est une relation d’ordre total.

Système de tâches et relation d’ordre partiel

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 << :

• Ti est prédécesseur immédiat de Tj s’il n’existe aucune tâche Tk telle que Ti << Tk << Tj.
• La relation << est transitive mais non symétrique.
• Ti << Tj implique que Ti précède Tj dans l’ordre d’exécution.

Graphe de précédence

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.

Matrice d’adjacence

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.

Types de dépendance entre tâches

Les dépendances entre tâches sont cruciales pour l’ordonnancement et la communication entre processeurs. On distingue :

• Dépendance de flux (RAW - Read After Write) : Ti produit une sortie Si utilisée comme entrée Ej de Tj.
• Anti-dépendance (WAR - Write After Read) : Ti lit une donnée Ei que Tj écrira plus tard dans Sj.
• Dépendance de sortie (WAW - Write After Write) : Ti et Tj écrivent sur la même donnée.

Seule la dépendance de flux (RAW) engendre des coûts de communication entre tâches.

Ordonnancement des 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 :

• PS = (T1, ..., Tn, →) le programme séquentiel segmenté
• S = (T1, ..., Tn, <<) le système de tâches avec relation d’ordre partiel
• Pr = (P1, ..., Pp) l’ensemble des processeurs disponibles

L’ordonnancement ORD est défini par :

ORD = {Ti (tdb(Ti), Proc(Ti))}

avec les contraintes :

• Si Ti << Tj alors tdb(Ti) < tdb(Tj)
• Si tdb(Ti) = tdb(Tj) alors Proc(Ti) ≠ Proc(Tj)
• Si Proc(Ti) = Proc(Tj) alors les intervalles d’exécution ne se chevauchent pas :

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]

Détermination des temps au plus tôt et au plus tard

Pour chaque tâche Ti, on définit :

• teti : temps au plus tôt de début d’exécution
• teTi : temps au plus tard de début d’exécution

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

Chemin critique et tâches critiques

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.

Décomposition du graphe en niveaux

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 :

• h(G) = hauteur du graphe = longueur du chemin critique
• N1 = nœuds sans prédécesseurs
• Nh(G) = nœuds sans successeurs

On définit deux décompositions :

• Dtot(G) : chaque tâche Ti est associée à un niveau Ntôt(i) = (teti / Θ) + 1
• Dtard(G) : chaque tâche Ti est associée à un niveau Ntard(i) = (teTi / Θ) + 1

La largeur du graphe est définie comme :

• Lt = max nombre de nœuds dans un niveau pour Dtot(G)
• LT = max nombre de nœuds dans un niveau pour Dtard(G)

Détermination du nombre optimal de processeurs Popt

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 :

• Popt = 2
• Nombre maximal de processeurs Pmax = 4 avec max(Lt, LT) ≤ Pmax ≤ max L(D(G))

Exemple d’ordonnancement

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.

Points clés

• La décomposition d’un programme en tâches dépend de la granularité choisie, influençant le parallélisme exploitable.
• Une tâche est définie par ses entrées, sorties, opérateur et coût en opérations élémentaires.
• La relation d’ordre partiel << entre tâches impose des contraintes d’exécution séquentielle partielle.
• Le graphe de précédence est un graphe orienté acyclique sans arcs transitifs, représentant les dépendances entre tâches.
• La relation de Bernstein permet de déterminer l’indépendance des tâches et leur exécution parallèle possible.
• La matrice d’adjacence du graphe de précédence est triangulaire supérieure après tri topologique.
• Les dépendances entre tâches sont classées en dépendance de flux (RAW), anti-dépendance (WAR) et dépendance de sortie (WAW), avec des implications sur la communication.
• L’ordonnancement associe à chaque tâche un temps de début et un processeur, respectant les contraintes d’ordre et d’exclusion.
• Le temps optimal d’exécution Topt correspond à la longueur du chemin critique dans le graphe de précédence.
• Les temps au plus tôt et au plus tard permettent d’identifier les tâches critiques et de construire un ordonnancement optimal.
• La décomposition en niveaux du graphe et la largeur des niveaux déterminent les bornes sur le nombre optimal de processeurs.