MÉTHODOLOGIE DE PARALLÉLISATION
1/107
100%
Rendu du PDF...
MÉTHODOLOGIE DE PARALLÉLISATION
Programming, Math · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
La méthodologie de parallélisation est essentielle pour optimiser l'exécution des programmes en segmentant les tâches. Cet article couvre les notions de système de tâches, les graphes de précédence, l'ordonnancement des tâches, ainsi que les types de dépendance. Des exemples pratiques et des méthodes de détermination de Popt seront également présentés pour aider à la compréhension de ces concepts.
La décomposition d'un programme en tâches n'est pas unique et dépend de la granularité demandée, c'est-à-dire la taille des tâches à paralléliser. Par exemple, pour un programme donné, on peut avoir :
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
Dans cet exemple, la granularité peut être fine, moyenne ou grande. Une granularité fine correspond à une seule opération élémentaire, ce qui peut entraîner jusqu'à 2n² tâches. Plus la granularité est fine, plus le parallélisme peut être exploité.
Une tâche est une unité indivisible définie par les propriétés suivantes :
La tâche est représentée par (Ei, Si, Fi, Θi). Il est important de noter que la tâche ne peut s'exécuter que sur un seul processeur et que son exécution est non préemptive.
Un système de tâches S = (T1,…,Tn, <<) est un ensemble de tâches muni d'une relation d'ordre partiel notée <<. Cela signifie que l'exécution de la tâche Tj ne peut commencer que si Ti a terminé son exécution.
Deux tâches Ti et Tj sont indépendantes si :
Si ∩ Sj = Si ∩ Ej = Ei ∩ Sj = Ø, c'est la condition de Bernstein. Cette relation d'ordre est transitive mais non symétrique.
Le graphe de précédence (GP) est un outil graphique qui représente les relations d'ordre entre les tâches. Pour construire le GP, il faut éliminer les redondances du graphe de tâches (GT).
Un exemple de graphe de tâches est :
T1 << T4 T2 << T4, T2 << T5, T2 << T6 T3 << T5, T3 << T6 T5 << T6
Pour chaque programme, on associe un graphe de tâches. Il est important de noter que le GP doit supprimer les arcs transitifs pour obtenir une représentation claire des dépendances.
La matrice d'adjacence d'ordre n est définie par :
aij = 1 ssi Ti << Tj
Cette matrice est souvent creuse et peut être utilisée pour appliquer un algorithme de tri topologique, qui permet de numéroter les nœuds d'un graphe de manière à respecter les relations d'ordre.
L'ordonnancement est défini comme suit :
ORD : (tdb(Ti), Proc(Ti))
où tdb(Ti) est le temps de début d'exécution de Ti, et Proc(Ti) est le processeur qui va exécuter Ti.
Pour minimiser le temps d'exécution total Tp, on doit respecter les contraintes suivantes :
Le temps d'exécution total est donné par :
Tp = maxi[tdb(Ti) + θi]
Il est crucial de minimiser Tp pour obtenir un ordonnancement optimal.
Pour chaque tâche, on détermine le temps au plus tôt (teti) et le temps au plus tard (teTi). Dans le cas où il n'y a pas de dépendance, les temps peuvent être calculés directement. Cependant, dans le cas général, il faut tenir compte des dépendances pour déterminer Topt.
Il existe plusieurs types de dépendance entre les tâches :
Dans la pratique, la dépendance de flux est souvent la plus préoccupante, car elle engendre des coûts de communication.
Pour déterminer Popt, on utilise les relations d'ordre et les temps calculés pour chaque tâche. On doit également prendre en compte le type de dépendance pour optimiser l'ordonnancement.
Un système de tâches est un ensemble de tâches avec une relation d'ordre partiel, indiquant que certaines tâches doivent être terminées avant que d'autres puissent commencer.
Pour construire un graphe de précédence, il faut d'abord établir un graphe de tâches, puis éliminer les redondances et les arcs transitifs pour obtenir une représentation claire des dépendances.
Les types de dépendance incluent la dépendance de flux (RAW), l'anti-dépendance (WAR) et la dépendance de sortie (WAW), chacun ayant des implications différentes sur l'ordonnancement des tâches.
Le temps d'exécution optimal est déterminé en calculant les temps au plus tôt et au plus tard pour chaque tâche, tout en respectant les dépendances entre elles.
Minimiser le temps d'exécution total permet d'optimiser l'utilisation des ressources et d'améliorer l'efficacité globale du système de traitement.