Exercice 1 :

Soit le programme suivant comportant 8 tâches supposées toutes de même coût :

𝑇1 : 𝑢= 𝑏× 𝑐 𝑇2 : 𝑣= 𝑎+ 𝑐 𝑇3 : 𝑤= 𝑢+ 𝑣 𝑇4 : 𝑥= 𝑢× 𝑣 𝑇5 : 𝑦= 2𝑢+ 5𝑣 𝑇6 : 𝑧= 𝑥+ 𝑢 𝑇7 : 𝑡= 𝑦+ 𝑣 𝑇8 : 𝑟= (𝑣+ 𝑤) × 𝑧

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 s’il y en a) décomposition(s) optimale(s) et déterminer Popt. 4. Etudier le cas où les communications ne sont pas negligeables.

Exercice 2 :

Soit à calculer l’expression arithmétique suivante :

𝐸= (𝑎+ 2) ∗(𝑏+ 𝑐) −(𝑑−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 l’expression E . 2. Calculer l’accélération, l’efficacité pour chaque proposition.

Faculté des Sciences de Tunis Département des Sciences de l’Informatique

Exercice 3 :

Soit le programme P suivant comportant 7 tâches 𝑇1, 𝑇2, … 𝑇7 où chaque opération arithmétique coûte une unité de temps.

𝑇1 : 𝑢= 𝑏∗𝑐+ 2 𝑇2 : 𝑣= 𝑎+ 𝑐 𝑇3 : 𝑤= 𝑑∗𝑒∗4 𝑇4 : 𝑥= 𝑏+ 𝑒 𝑇5 : 𝑦= 𝑥 [3] + 𝑢 𝑇6 : 𝑧= 𝑣+ 𝑤 𝑇7 : 𝑡= 𝑦+ 𝑧

1. Calculer le temps de l’exécution séquentielle de P. Dessiner le digramme de Gantt de

l’exé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 qu’on 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 d’exécution parallèle, le nombre de

processeurs utilisés ainsi que l’accélération et ‘efficacité. c. Peut-on proposer un autre ordonnancement des tâches en minimisant le nombre de

processeurs. 4. Supposons qu’on dispose de deux processeurs, proposer un ordonnancement (placement)

minimisant le temps d’exécution parallèle.

Exercice 4 :

On désire calculer l’expression associative suivante :

𝐸𝑥𝑝 : = (𝑎−𝑐) × (𝑏× 𝑑) −(𝑒/𝑓) −(𝑔× (ℎ+ 𝑖))

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 𝐸𝑥𝑝. 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

Faculté des Sciences de Tunis Département des Sciences de l’Informatique

processeurs égal à Popt, que l’on déterminera en justifiant. Calculer l’accélération et l’efficacité. 4. Reprendre la question 2 en prenant en compte les communications en supposant que la

transmission d’un réel d’un 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 d’images P prend en entrée une image Im et lui applique les étapes Ei (i=0..8) suivantes :

E0 : Découper l’image 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 I m12 ;
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 l’exé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 T opt que peut avoir une exécution parallèle de P. Justifier. 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 l’accélération Sp et l’efficacité 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 l’accélération Sp et l’efficacité Ep. 8. Déterminer Popt en justifiant votre réponse. 9. Supposons qu’on ne possède que de 2 processeurs. Proposer une exécution parallèle de P qui

minimise le temps d’exécution T2 à déterminer. Calculer l’accélération et l’efficacité.

Faculté des Sciences de Tunis Département des Sciences de l’Informatique

10. On suppose uniquement pour cette question que l’opération de filtrage peut être décomposée.

En effet, appliquer un filtre à une image revient à l’appliquer indépendamment à chaque pixel de l’image. (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 ?

TD Ordonnancement des t ches

TD Ordonnancement des t ches

Exercice 1 :

Exercice 2 :

Exercice 3 :