TD Ordonnancement des t ches

Exercice 1 - Graphes et ordonnancement de tâches élémentaires

Question 1 - Graphes de dépendance et de précédence

Identifions d'abord les 8 tâches et leurs opérandes. Chaque tâche a un coût unitaire (1 u.t.).

• T1 : u = b × c
• T2 : v = a + c
• T3 : w = u + v (dépend de T1, T2)
• T4 : x = u × v (dépend de T1, T2)
• T5 : y = 2u + 5v (dépend de T1, T2)
• T6 : z = x + u (dépend de T4, T1)
• T7 : t = y + v (dépend de T5, T2)
• T8 : r = (v + w) × z (dépend de T2, T3, T6)

Graphe de dépendance (toutes les dépendances) : Les arcs relient chaque tâche à celles qui utilisent son résultat.

• De T1 vers : T3, T4, T5, T6
• De T2 vers : T3, T4, T5, T7, T8
• De T3 vers : T8
• De T4 vers : T6
• De T5 vers : T7
• De T6 vers : T8

Graphe de précédence (sans dépendances transitives) : On élimine les arcs redondants créés par la transitivité :

• L'arc (T1, T6) est supprimé car le chemin T1 → T4 → T6 existe.
• L'arc (T2, T7) est supprimé car le chemin T2 → T5 → T7 existe.
• L'arc (T2, T8) est supprimé car le chemin T2 → T3 → T8 existe.

Les arcs finaux du graphe de précédence sont : (T1, T3), (T1, T4), (T1, T5), (T2, T3), (T2, T4), (T2, T5), (T4, T6), (T5, T7), (T3, T8), (T6, T8).

Calcul du temps d'exécution optimal Topt : Topt correspond à la longueur du chemin critique dans le graphe de précédence. Les chemins possibles depuis les sommets initiaux jusqu'aux terminaux sont :

• T1 → T4 → T6 → T8 (longueur 4)
• T2 → T4 → T6 → T8 (longueur 4)
• T1 → T5 → T7 (longueur 3)
• T2 → T5 → T7 (longueur 3)
• T1 → T3 → T8 (longueur 3)
• T2 → T3 → T8 (longueur 3)

Le chemin le plus long comporte 4 tâches. Donc, Topt = 4 unités de temps.

Question 2 - Décompositions au plus tôt et au plus tard

Décomposition au plus tôt (ASAP) : Chaque tâche est lancée dès que ses prédécesseurs ont terminé.

• t = 0 à 1 : T1, T2
• t = 1 à 2 : T3, T4, T5
• t = 2 à 3 : T6 (attend T4), T7 (attend T5)
• t = 3 à 4 : T8 (attend T3 et T6)

Diagramme de Gantt (au plus tôt) :

Temps	0 - 1	1 - 2	2 - 3	3 - 4
P1	T1	T3	T6	T8
P2	T2	T4	T7
P3		T5

Décomposition au plus tard (ALAP) : En partant de Topt = 4, on recule pour lancer chaque tâche le plus tard possible sans retarder le temps global.

• t = 3 à 4 : T8, T7
• t = 2 à 3 : T6 (doit précéder T8), T3 (doit précéder T8), T5 (doit précéder T7)
• t = 1 à 2 : T4 (doit précéder T6)
• t = 0 à 1 : T1, T2 (doivent précéder T4, T3, T5)

Diagramme de Gantt (au plus tard) :

Temps	0 - 1	1 - 2	2 - 3	3 - 4
P1	T1	T4	T6	T8
P2	T2		T3	T7
P3			T5

Question 3 - Décomposition optimale et Popt

Le travail total (W) est de 8 tâches. Le temps optimal (Topt) est de 4. Le nombre minimal de processeurs théorique est P ≥ W / Topt = 8 / 4 = 2. Vérifions si on peut placer les tâches sur 2 processeurs (Popt = 2) en respectant les dépendances :

• t = 0 à 1 : T1, T2
• t = 1 à 2 : T4, T5
• t = 2 à 3 : T6, T3 (T3 peut attendre ici car T8 n'a lieu qu'à t=3)
• t = 3 à 4 : T8, T7

Cette planification est valide car toutes les dépendances sont respectées. Donc, Popt = 2 processeurs.

Question 4 - Prise en compte des communications

Si les communications ne sont plus négligeables, l'envoi du résultat d'une tâche d'un processeur à un autre consomme du temps supplémentaire. Pour minimiser ces pénalités, il devient nécessaire de regrouper (clusteriser) les tâches ayant de fortes dépendances sur un même processeur. Cela oblige souvent à exécuter des tâches séquentiellement même si elles pourraient être parallèles en théorie, ce qui entraîne une augmentation de Topt et une diminution de l'efficacité de la parallélisation.

Exercice 2 - Parallélisation d'une expression arithmétique

Question 1 - Précédences et exécutions parallèles

L'expression est : E = (a + 2) × (b + c) - (d - 1). Coût = 1 par opération. Décomposons en opérations élémentaires :

• O1 : a + 2
• O2 : b + c
• O3 : d - 1
• O4 : O1 × O2 (dépend de O1 et O2)
• O5 : O4 - O3 (dépend de O4 et O3)

Proposition 1 (avec 3 processeurs - parallélisme maximal) :

Temps	1	2	3
P1	O1	O4	O5
P2	O2
P3	O3

Proposition 2 (avec 2 processeurs - optimisation des ressources) :

Temps	1	2	3
P1	O1	O4	O5
P2	O2	O3

Question 2 - Accélération et efficacité

Le temps séquentiel (T1) est de 5 unités (5 opérations).

Pour la proposition 1 (P = 3) :

• Temps parallèle (Tp) = 3
• Accélération (S) = T1 / Tp = 5 / 3 ≈ 1.67
• Efficacité (E) = S / P = (5 / 3) / 3 = 5 / 9 ≈ 0.55

Pour la proposition 2 (P = 2) :

• Temps parallèle (Tp) = 3
• Accélération (S) = T1 / Tp = 5 / 3 ≈ 1.67
• Efficacité (E) = S / P = (5 / 3) / 2 = 5 / 6 ≈ 0.83

Exercice 3 - Ordonnancement du programme P

Question 1 - Exécution séquentielle

Déterminons le coût unitaire de chaque tâche (chaque opération = 1 u.t.) :

• T1 : b × c + 2 (2 opérations) → Coût = 2
• T2 : a + c (1 opération) → Coût = 1
• T3 : d × e × 4 (2 opérations) → Coût = 2
• T4 : b + e (1 opération) → Coût = 1
• T5 : y = x³ + u. Note : En supposant que "x3" désigne x au cube (x³), l'élévation à la puissance et l'addition font 2 opérations. (S'il s'agit de x × 3, le coût reste de 2). → Coût = 2
• T6 : v + w (1 opération) → Coût = 1
• T7 : y + z (1 opération) → Coût = 1

Le temps séquentiel est la somme des coûts : T1 = 2 + 1 + 2 + 1 + 2 + 1 + 1 = 10 unités de temps.

Diagramme de Gantt séquentiel :

Temps	0-2	2-3	3-5	5-6	6-8	8-9	9-10
P1	T1	T2	T3	T4	T5	T6	T7

Question 2 - Graphe de précédence et chemin critique

Dépendances : T5 dépend de T4 et T1. T6 dépend de T2 et T3. T7 dépend de T5 et T6.

Les chemins possibles aboutissant à T7 :

• T1 → T5 → T7 (coûts : 2 + 2 + 1 = 5)
• T4 → T5 → T7 (coûts : 1 + 2 + 1 = 4)
• T2 → T6 → T7 (coûts : 1 + 1 + 1 = 3)
• T3 → T6 → T7 (coûts : 2 + 1 + 1 = 4)

Le chemin critique est le chemin le plus long : T1 → T5 → T7. Les tâches critiques sont T1, T5 et T7.

Question 3 - Parallélisme sans contrainte de communication

a. Degré maximal de parallélisme (dmax) : Le nombre maximal de tâches indépendantes pouvant s'exécuter simultanément est de 4 (T1, T2, T3, T4 peuvent toutes démarrer à t=0). Donc, dmax = 4.

b. Gantt, Tp, processeurs, accélération et efficacité : Avec un lancement au plus tôt (ASAP) :

Temps	0 - 1	1 - 2	2 - 3	3 - 4	4 - 5
P1	T1 (partie 1)	T1 (partie 2)	T5 (partie 1)	T5 (partie 2)	T7
P2	T3 (partie 1)	T3 (partie 2)	T6
P3	T2
P4	T4

• Temps parallèle Tp = 5 unités.
• Processeurs utilisés = 4.
• Accélération (Sp) = 10 / 5 = 2.
• Efficacité (Ep) = 2 / 4 = 0.5.

c. Minimisation du nombre de processeurs : On peut regrouper les tâches sur 3 processeurs sans dégrader le temps (T=5) :

Temps	0 - 1	1 - 2	2 - 3	3 - 4	4 - 5
P1	T1 (1)	T1 (2)	T5 (1)	T5 (2)	T7
P2	T3 (1)	T3 (2)	T6
P3	T2	T4
Oui, un ordonnancement optimal à 3 processeurs est possible.

Question 4 - Ordonnancement avec deux processeurs

Avec P=2, il est impossible d'atteindre Tp=5 car le travail total est 10 et les contraintes de précédence forcent des temps morts si on serre trop l'emploi du temps. Le mieux que l'on puisse faire est Tp=6.

Ordonnancement proposé minimisant le temps :

Temps	0 - 1	1 - 2	2 - 3	3 - 4	4 - 5	5 - 6
P1	T1 (1)	T1 (2)	T5 (1)	T5 (2)	(inactif)	T7
P2	T4	T2	T3 (1)	T3 (2)	T6

Exercice 4 - Expression associative

Question 1 - Temps séquentiel

Expression : Exp = (a - c) × (b × d) - (e / f) - (g × (h + i)) Décomposition : O1 = a - c O2 = b × d O3 = O1 × O2 O4 = e / f O5 = h + i O6 = g × O5 O7 = O3 - O4 O8 = O7 - O6 Il y a 8 opérations au total. T1 = 8.

Question 2 - Temps parallèle minimal (Tmin)

Tmin correspond à la hauteur de l'arbre d'évaluation le plus contraint. Les feuilles O1, O2, O4, O5 s'évaluent en 1 u.t. Le niveau suivant O3 (à partir de O1, O2) et O6 (à partir de O5) termine à t=2. Les soustractions pour fusionner les trois termes (O3, O4, O6) nécessitent 2 étapes (on ne peut fusionner que 2 opérandes par unité de temps). Donc, les étapes de soustraction prendront 2 u.t. supplémentaires. Tmin = 2 (calcul des termes) + 2 (soustractions) = 4.

Question 3 - Exécution parallèle, Popt, accélération et efficacité

Pour obtenir T = 4, P=2 est insuffisant (travail W=8, mais avec les précédences, P=2 repousse la fin à 5). Il faut Popt = 3. Ordonnancement proposé :

Temps	1	2	3	4
P1	O1	O3	O7	O8
P2	O2	O4
P3	O5	O6

• Accélération = 8 / 4 = 2.
• Efficacité = 2 / 3 ≈ 0.67.

Question 4 - Intégration des temps de communication

Une communication prend 0.25 u.t. et bloque le récepteur. Reprenons le placement (P1 fait O1, O3, O7, O8 ; P2 fait O2, O4 ; P3 fait O5, O6).

• t = 0 à 1 : P1 effectue O1. P2 effectue O2. P3 effectue O5.
• t = 1 à 1.25 : P1 reçoit O2 depuis P2 (P1 est bloqué). Pendant ce temps, P2 démarre O4, P3 démarre O6.
• t = 1.25 à 2.25 : P1 effectue O3.
• t = 2.25 à 2.50 : P1 reçoit O4 (prêt depuis t=2) de P2.
• t = 2.50 à 3.50 : P1 effectue O7.
• t = 3.50 à 3.75 : P1 reçoit O6 (prêt depuis t=2) de P3.
• t = 3.75 à 4.75 : P1 effectue O8.

En tenant compte des pénalités, le nouveau temps parallèle minimal est de 4.75 u.t.

Exercice 5 - Traitement d'images

Question 1 - Temps séquentiel

T1 est la somme des coûts : T1 = 2 (E0) + 4×1 (E1 à E4) + 3 (E5) + 3 (E6) + 1 (E7) + 3 (E8) = 16 unités de temps.

Question 2 - Graphe de précédence

• E0 précède E1, E2, E3, E4.
• E1 et E2 précèdent E5.
• E3 et E4 précèdent E6.
• E5 précède E7.
• E7 et E6 précèdent E8.

Partie A - Questions 5 à 10

Question 5 - Temps minimal Topt : Le chemin critique correspond au temps maximum depuis l'entrée vers la sortie. Chemin 1 : E0 → E1 → E5 → E7 → E8 = 2 + 1 + 3 + 1 + 3 = 10. Chemin 2 : E0 → E3 → E6 → E8 = 2 + 1 + 3 + 3 = 9. Topt = 10.

Question 6 - Ordonnancement au plus tôt :

Temps	0-2	2-3	3-6	6-7	7-10
P1	E0	E1	E5	E7	E8
P2		E2	E6
P3		E3
P4		E4

• Nombre de processeurs utilisés = 4.
• Tp = 10.
• Sp = 16 / 10 = 1.6.
• Ep = 1.6 / 4 = 0.4.

Question 7 - Ordonnancement au plus tard : On recule à partir de T=10 :

• E8 : 7-10.

• E7 : 6-7.

• E6 : 4-7.

• E5 : 3-6.

• E3, E4 : 3-4.

• E1, E2 : 2-3.

• E0 : 0-2.

• Tp = 10.

• Sp = 1.6.

• L'utilisation maximale simultanée est entre t=3 et t=4 (E5, E3, E4 en même temps), soit 3 processeurs. Ep = 1.6 / 3 ≈ 0.53.

Question 8 - Popt : Nous avons vu que la décomposition au plus tard permet de réaliser le travail en 10 u.t. avec 3 processeurs. Peut-on le faire avec 2 ? Entre t=2 et t=7, il faut réaliser E1, E2, E3, E4, E5, E6, E7, soit 11 u.t. de charge. Avec 2 processeurs, 5 unités de temps calendaires ne fournissent que 10 u.t. de puissance de calcul. C'est mathématiquement insuffisant pour terminer à temps et lancer E8 à t=7. Donc, Popt = 3.

Question 9 - Exécution avec 2 processeurs : Puisque le temps optimal de 10 est impossible, le minimum absolu suivant avec 2 processeurs est 11, en reportant E8 d'une unité de temps.

Temps	0-2	2-3	3-4	4-7	7-8	8-11
P1	E0	E1	E2	E5	E7	E8
P2		E3	E4	E6

• Tp (ou T2) = 11.
• Accélération = 16 / 11 ≈ 1.45.
• Efficacité = 1.45 / 2 ≈ 0.72.

Question 10 - Parallélisation au niveau pixel : (a) Pour améliorer la parallélisation, on peut distribuer l'image pixel par pixel (ou bloc par bloc) sur plusieurs processeurs, évitant ainsi le coût de découpage explicite et exécutant la même instruction de filtrage simultanément sur un large ensemble de données. (b) La source de parallélisme utilisée est le parallélisme de données (contrairement au parallélisme de tâches vu précédemment). (c) Si l'image comporte N pixels, on peut en théorie utiliser N processeurs (un par pixel) pour maximiser ce type de parallélisme.

Méthode

Face à ce type d'épreuve d'ordonnancement, la démarche la plus fiable consiste toujours à extraire l'ensemble des tâches pour tracer au brouillon un graphe orienté. C'est ce graphe qui pilote tout le reste.

1. La longueur du chemin le plus long vous donnera la limite infranchissable du temps parallèle optimal (Topt).
2. Pour élaborer des diagrammes de Gantt viables, surveillez en permanence les temps de libération de chaque opérande.
3. Ne cherchez pas à deviner le nombre de processeurs idéaux (Popt) au hasard. Calculez d'abord le travail total W, puis divisez-le par Topt. Cette borne inférieure vous indique par où commencer. Si des contraintes de précédence créent des inactifs incontournables (bulles d'air dans le diagramme), vous devrez systématiquement ajouter des processeurs ou accepter de repousser le délai global.