Formation IUP3 - Test du 14/11/97

On considère le texte de programme séquentiel suivant :

1: x:= 1
2: y:= log(x)
3: z:= x+1
4: t:= x+x*x
5: t:= t*t+1
6: z:= z+t
7: x:= y*z

Graphe de dépendance des instructions

On suppose que chaque instruction est modélisée par une tâche, tracer le graphe de précédence associé à ce programme séquentiel.

T// est la longueur d'un chemin critique du graphe, ici le chemin 1 - 4 - 5 - 6 - 7 et un chemin critique de durée 5. C'est d'ailleurs le seul chemin critique.

Diagramme de Gantt de l'ordonnancement au plus tôt

Diagramme de Gantt de l'ordonnancement au plus tard

On utilise un algorithme de liste pour ordonnancer les tâches. C'est à dire que dès qu'une tâche est prête on l'affecte au premier processeur disponible. Dans le cas où plusieurs tâches sont prêtes on affecte les tâche par valeur minimale d'indice de tâche. Par exemple si les tâches 4, 8 et 10 sont prêtes on exécutera en priorité la tâche 4.

Calculer l'ordonnancement du programme sur 2 processeurs (donner le diagramme de Gantt).

Cet ordonnancement est-il optimal ? Non car celui-ci est meilleur.

Cet ordonnancement est optimal car sa durée est égale à la longueur du chemin critique.

Ceci pour l'ordonnancement de liste avec priorité.

Pour les 2 exemples ci-dessus, les bornes de Graham sont-elles vérifiées ?

Il faut vérifier que Tp<(2-1/p)Tp*, ici p=2.

Dans le premier cas, Tp = 6, or Tp* est toujours supérieur à T//, qui ici est égal à 5. Comme 2-1/p=1.5, on a bien 6 <= 1.5*5 <=1.5*Tp*.

Dans le deuxieme cas, Tp = 7 et T// est égal à 7 (le vérifier ). L'ordonnancement est donc optimal sur 2 processeurs, il vérifie donc forcemment la borne de Graham.