Aller au contenu

TD Ordonnancement des t ches

Ordonnancement des tâches L'ordonnancement des tâches est un domaine clé en informatique qui traite de la planification et de l'exécution efficace des tâches dans un programme. Cet article présente des exercices pratiques sur l'ordonnancement des tâches, y compris la construction de graphes de dépendance, l'analyse des temps d'exécution, et les méthodes de parallélisation.

D'après le document TD Ordonnancement des t ches

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

TD Ordonnancement des t ches

Computer Science (Task Scheduling and Parallel Computing) · PDF · 4 pages

Afficher l'aperçu du document

Consulter le document original →

Ordonnancement des tâches

L'ordonnancement des tâches est un domaine clé en informatique qui traite de la planification et de l'exécution efficace des tâches dans un programme. Cet article présente des exercices pratiques sur l'ordonnancement des tâches, y compris la construction de graphes de dépendance, l'analyse des temps d'exécution, et les méthodes de parallélisation. Les étudiants apprendront à calculer le temps d'exécution optimal, à utiliser des diagrammes de Gantt, et à évaluer l'accélération et l'efficacité des différentes stratégies d'ordonnancement.

Exercice 1 : Graphes de dépendance et temps d'exécution

Dans cet exercice, nous avons un programme avec 8 tâches, toutes supposées de même coût. Les tâches sont définies comme suit :

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

Les étapes à suivre sont :

  1. Construire le graphe de dépendance, puis le graphe de précédence sans dépendances transitives.
  2. Calculer le temps d'exécution optimal Topt.
  3. Déterminer la décomposition au plus tôt et au plus tard des tâches, et donner le diagramme de Gantt pour chacune.
  4. Proposer une ou plusieurs décompositions optimales et déterminer Popt.
  5. Étudier le cas où les communications ne sont pas négligeables.

Exercice 2 : Exécution parallèle d'une expression arithmétique

Nous allons calculer l'expression arithmétique suivante :

E = (a + 2) * (b + c) - (d - 1)

Les étapes à suivre sont :

  1. Étudier 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 et l'efficacité pour chaque proposition.

Exercice 3 : Analyse d'un programme avec 7 tâches

Considérons un programme P avec 7 tâches, où chaque opération arithmétique coûte une unité de temps :

T1 : u = b * c + 2
T2 : v = a + c
T3 : w = d * e * 4
T4 : x = b + e
T5 : y = x^3 + u
T6 : z = v + w
T7 : t = y + z

Les étapes à suivre sont :

  1. Calculer le temps de l'exécution séquentielle de P et dessiner le diagramme de Gantt de l'exécution séquentielle.
  2. Construire le graphe de précédence des tâches pour le programme P et déterminer le chemin critique.
  3. En négligeant les communications, déterminer le degré maximal de parallélisme dmax.
  4. Proposer un ordonnancement minimisant le nombre de processeurs.

Exercice 4 : Calcul d'une expression associative

Nous allons calculer l'expression associative suivante :

Exp := (a - c) × (b × d) - (e/f) - (g × (h + i))

Les étapes à suivre sont :

  1. Calculer le temps T1 du calcul séquentiel de Exp.
  2. Calculer Tmin, le temps parallèle minimal, et justifier.
  3. Proposer une exécution parallèle du calcul de Exp, et déterminer Popt.
  4. Prendre en compte les communications et justifier les calculs.

Exercice 5 : Traitement d'images

Un programme de traitement d'images P prend en entrée une image Im et applique les étapes 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 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.

Les étapes à suivre sont :

  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.
  3. Déterminer le temps minimal Topt pour une exécution parallèle de P.
  4. Proposer une exécution parallèle de P basée sur un ordonnancement au plus tôt.
  5. Proposer une exécution parallèle de P basée sur un ordonnancement au plus tard.
  6. Déterminer Popt en justifiant votre réponse.
  7. Proposer une exécution parallèle de P qui minimise le temps d'exécution avec 2 processeurs.
  8. Améliorer la parallélisation de P en spécifiant les sources de parallélisme utilisées.

Points clés à retenir

  • Comprendre les graphes de dépendance et de précédence est essentiel pour l'ordonnancement.
  • Le diagramme de Gantt est un outil utile pour visualiser l'exécution des tâches.
  • Le calcul de l'accélération et de l'efficacité permet d'évaluer les performances des différentes stratégies d'ordonnancement.
  • La parallélisation peut considérablement réduire le temps d'exécution des programmes.

Questions fréquentes

Qu'est-ce que l'ordonnancement des tâches ?

L'ordonnancement des tâches est le processus de planification et d'exécution des tâches dans un programme pour optimiser l'utilisation des ressources et réduire le temps d'exécution.

Comment construire un diagramme de Gantt ?

Un diagramme de Gantt est construit en représentant les tâches sur un axe horizontal et le temps sur un axe vertical, en indiquant les périodes d'exécution de chaque tâche.

Qu'est-ce que l'accélération et l'efficacité ?

L'accélération mesure le gain de performance d'une exécution parallèle par rapport à une exécution séquentielle, tandis que l'efficacité évalue l'utilisation des ressources par rapport au nombre de processeurs utilisés.

Comment déterminer le degré maximal de parallélisme ?

Le degré maximal de parallélisme est déterminé en analysant les dépendances entre les tâches et en identifiant combien de tâches peuvent être exécutées simultanément sans conflit.

Quels sont les coûts de communication dans l'ordonnancement ?

Les coûts de communication se réfèrent au temps nécessaire pour transférer des données entre les processeurs, ce qui peut affecter l'efficacité de l'ordonnancement parallèle.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions