Facult des Sciences de Tunis
D partement des Sciences de lInformatique
TD Ordonnancement des t ches
Y.SLAMA
Exercice 1 :
Soit le programme suivant comportant 8 t ches suppos es toutes de m me co t :
5G1 : 5b = 5O 5P
5G2 : 5c = 5N + 5P
5G3 : 5d = 5b + 5c
5G4 : 5e = 5b 5c
5G5 : 5f = 25b + 55c
5G6 : 5g = 5e + 5b
5G7 : 5a = 5f + 5c
5G8 : 5_ = (5c + 5d) 5g
1. Construire le graphe de d pendance (toutes les d pendances) puis le graphe de pr c dence (sans
d pendances transitives). Calculer le temps d x cution optimal Topt.
2. D terminer la d composition au plus t t et au plus tard des t ches. Donner le diagramme de
Gantt pour chacune des d compositions.
3. Proposer une (ou plus sil y en a) d composition(s) optimale(s) et d terminer Popt.
4. Etudier le cas o les communications ne sont pas negligeables.
Publicité
Exercice 2 :
Soit calculer lexpression arithm tique suivante :
58 = (5N + 2) (5O + 5P) (5Q 1)
On supposera que toute op ration arithm tique co te 1 unit de temps.
1. Etudier les pr c dences entre les op rations et proposer diff rentes ex cutions parall les pour
calculer lexpression E.
2. Calculer lacc l ration, lefficacit pour chaque proposition.
Facult des Sciences de Tunis
D partement des Sciences de lInformatique
Exercice 3 :
Soit le programme P suivant comportant 7 t ches 5G1, 5G2, & 5G7 o chaque op ration arithm tique
co te une unit de temps.
5G1 : 5b = 5O 5P + 2
5G2 : 5c = 5N + 5P
5G3 : 5d = 5Q 5R 4
5G4 : 5e = 5O + 5R
5G5 : 5f = 5e3 + 5b
5G6 : 5g = 5c + 5d
5G7 : 5a = 5f + 5g
1. Calculer le temps de lex cution s quentielle de P. Dessiner le digramme de Gantt de
Publicité
lex cution s quentielle du programme.
2. Construire le graphe de pr c dence des t ches pour le programme P. D terminer le chemin
critique et par cons quent les t ches critiques.
3. En n gligeant les communications et supposons quon poss de suffisamment de processeurs,
a. D terminer le degr maximal de parall lisme dmax.
b. Dessiner le diagramme de Gantt et d terminer le temps dex cution parall le, le nombre de
processeurs utilis s ainsi que lacc l ration et efficacit .
c. Peut-on proposer un autre ordonnancement des t ches en minimisant le nombre de
processeurs.
4. Supposons quon dispose de deux processeurs, proposer un ordonnancement (placement)
minimisant le temps dex cution parall le.
Exercice 4 :
On d sire calculer lexpression associative suivante :
585e5] : = (5N 5P) (5O 5Q) (5R/5S) (5T ( + 5V))
On supposera que toutes les variables sont de type r el et que toute op ration arithm tique co te 1
unit de temps.
1. Calculer le temps T1 du calcul s quentiel de 585e5].
2. Calculer Tmin : le temps parall le minimal. Justifier.
3. On supposant que les co ts de communication sont n gligeables, proposer une ex cution
parall le (ordonnancement/placement) du calcul de Exp, de dur e Tmin utilisant un nombre de
Publicité
Facult des Sciences de Tunis
D partement des Sciences de lInformatique
processeurs gal Popt, que lon d terminera en justifiant. Calculer lacc l ration et
lefficacit .
4. Reprendre la question 2 en prenant en compte les communications en supposant que la
transmission dun r el dun processeur co te toujours 0.25 unit de temps, que les liens sont
full duplex et en linkbound et que la communication bloque uniquement le r cepteur.
Exercice 5 :
Un programme de traitement dimages P prend en entr e une image Im et lui applique les tapes
Ei (i=0..8) suivantes :
- E0 : D couper limage Im en 4 images Im1, Im2, Im3 et Im4 ;
- E1, E2, E3 et E4 : Appliquer des filtres Im1, Im2, Im3 et Im4 respectivement ;
- E5 : Fusionner Im1 et Im2 filtr es pour obtenir Im12 ;
- E6 : Fusionner Im3 et Im4 filtr es pour obtenir Im34 ;
- E7 : Appliquer un filtre Im12 ;
- E8 : Fusionner Im12 filtr e et Im34 pour obtenir une image Im-finale.
On supposera que le d coupage co te 2 unit s de temps (u.t), toute op ration de filtrage co te
1 u.t et toute op ration de fusion co te 3 u.t.
Pour simplifier le probl me, on supposera que toutes les images utilis es sont de m me taille
gale N pixels (= N octets).
1. Calculer le temps T1 de lex cution s quentielle de P.
2. Repr senter les pr c dences entre les tapes de P (on repr sentera un graphe de pr c dence).
Partie A : On supposera ici que les co ts de communication sont n gligeables.
On supposera que chaque tape est une t che ind composable.
5. D terminer le temps minimal Topt que peut avoir une ex cution parall le de P. Justifier.
Publicité
6. Proposer une ex cution parall le de P bas e sur un ordonnancement au plus t t. Donner le
nombre de processeurs utilis s. Calculer le temps parall le Tp ainsi que lacc l ration Sp et
lefficacit Ep.
7. Proposer une ex cution parall le de P bas e sur un ordonnancement au plus tard. Calculer le
temps parall le Tp ainsi que lacc l ration Sp et lefficacit Ep.
8. D terminer Popt en justifiant votre r ponse.
9. Supposons quon ne poss de que de 2 processeurs. Proposer une ex cution parall le de P qui
minimise le temps dex cution T2 d terminer. Calculer lacc l ration et lefficacit .
Facult des Sciences de Tunis
D partement des Sciences de lInformatique
10. On suppose uniquement pour cette question que lop ration de filtrage peut tre d compos e.
En effet, appliquer un filtre une image revient lappliquer ind pendamment chaque pixel
de limage.
(a) Comment pourrait-on am liorer la parall lisation de P (utiliser une description textuelle, un
sch me ou un bout de code ?
(b) Sp cifier la (les) source(s) de parall lisme utilis e pour la parall lisation propos e ?
(c) Quel est le nombre de processeurs n cessaires ?