Méthodologie de Parallélisation

Chapitre 4 2 Plan 1. Notion de système de tâches 2. Graphe de précédence 3. Ordonnancement de tâches 3 Notion de système de tâches 1. Notion de tâche La décomposition (segmentation) d’un programme en tâches n’est pas unique. Elle dépend de la granularité demandée (taille de tâche). 4 Notion de système de tâches 1. Notion de tâche La décomposition (segmentation) d’un programme en tâches n’est pas unique. Elle dépend de la granularité demandée (taille des tâches à paralléliser). pour i=1 à n faire pour j=1 à n faire Y(i)= Y(i)+ A(i,j)* X(j) fin pour j fin pour i 5 Notion de système de tâches 1. Notion de tâche La décomposition (segmentation) d’un programme en tâches n’est pas unique. Elle dépend de la granularité demandée (taille de tâche). pour i=1 à n faire pour j=1 à n faire Y(i)= Y(i)+ A(i,j)* X(j) fin pour j fin pour i Tâche Granularité Y(i)= Y(i)+ A(i,j)* X(j) Moyenne (=2) Boucle interne Grande (=2n) 6 Notion de système de tâches 1. Notion de tâche La décomposition (segmentation) d’un programme en tâches n’est pas unique. Elle dépend de la granularité demandée (taille de tâche). pour i=1 à n faire pour j=1 à n faire Y(i)= Y(i)+ A(i,j)* X(j) fin pour j fin pour i Une granularité fine correspond à une seule opération élémentaire  2n [2] tâches 7 Notion de système de tâches 1. Notion de tâche La décomposition (segmentation) d’un programme en tâches n’est pas unique. Elle dépend de la granularité demandée (taille de tâche). pour i=1 à n faire pour j=1 à n faire Y(i)= Y(i)+ A(i,j)* X(j) fin pour j fin pour i Plus la granularité est fine, plus nous pouvons apparaitre le parallélisme 8 Notion de système de tâches 1. Notion de tâche Tâche c’est une unité indivisible définie par les propriétés suivantes E : les entrées de la tâche T i i Si : les sorties de la Fi tâches Ti F : opérateur sur T E  S i i i i  :coût de T (nombre d’opérations élémentaires) i i Ainsi la tâche est représentée par (E , S , F ,  i i i i [)] 9 Notion de système de tâches 1. Notion de tâche Remarques  La tâche ne peut s’exécuter que sur un seul processeur  L’exécution d’une tâche est non préemptive  Le modèle est dit statique si on connait à l’avance de (E ,  ) i, Si, Fi i  PS le programme séquentiel, une fois segmenté PS=(T ,…,T ,  ) 1 n «  » relation d’ordre total puisque le programme est séquentiel 10 Notion de système de tâches 2. Système de tâches Un système de tâches S =(T ,…,T ,<<) est un ensemble de tâches muni 1 n d’une relation d’ordre partiel notée <<. T i << Tj (i≠j) signifie que l’exécution de la tâche Tj ne peut commencer que si T i a terminé son exécution 11 Notion de système de tâches 2. Système de tâches Un système de tâches S =(T ,…,T ,<<) est un ensemble de tâches muni 1 n d’une relation d’ordre partiel notée <<. T i << Tj (i≠j) signifie que l’exécution de la tâche Tj ne peut commencer que si T i a terminé son exécution Comparaison de deux tâches : Deux tâches T i et Tj sont indépendantes (non interférentes) si 12 Notion de système de tâches 2. Système de tâches Un système de tâches S =(T ,…,T ,<<) est un ensemble de tâches muni 1 n d’une relation d’ordre partiel notée <<. T i << Tj (i≠j) signifie que l’exécution de la tâche Tj ne peut commencer que si T i a terminé son exécution Comparaison de deux tâches : Deux tâches T i et Tj sont indépendantes (non interférentes) si S  S = S  E = E  S = Ø : c’est une condition nécessaire i j i j i j mais non suffisante pour que les deux tâches puissent s’exécuter en //. 13 Notion de système de tâches 2. Système de tâches S=(T,…,T,<<) : 1 n T << T i j T << T j i T et T indépendantes i j Remarques  T T T T ) i est prédécesseur immédiat de j (ou j est successeur immédiat de i s’il n’existe aucune autre tâche T T <<T <<T . k telle que i k j  Cette relation d’ordre partiel << est transitive mais non symétrique. 14 Notion de système de tâches 2. Système de tâches S=(T,…,T,<<) : 1 n T << T i j T << T j i T et T indépendantes i j Remarques  Cette relation d’ordre partiel <<, est transitive mais non symétrique.  T <<T  ( T  T & S  S = S  E = E  S ≠ Ø ) i j i j i j i j i j 15 Graphe de précédence 1. Graphe de tâches (GT) Remarques  GT (graphe de tâches) est un graphe orienté mais non cyclique (puisque la relation est non symétrique)  On associe pour chaque programme un graphe de tâches 16 Graphe de précédence 1. Graphe de tâches (GT) T6 T3  Exp  T 1 <  T < , T < 2 4 2 5, T2 <  T << T , T << T 3 5 3 6  T < 5 6 T1 T2 T4 17 Graphe de précédence 2. Graphe de précédence (GP)  Pour construire le GP il faut éliminer les redondances du GT. T6 T3  Exp  T 1 <  T < , T < 2 4 2 5, T2 <  T << T , T << T 3 5 3 6  T < 5 6 T1 T2 T4 18 Graphe de précédence 2. Graphe de précédence  Pour construire le GP il faut éliminer les redondances du GT.  Exp  T 1 <  T < , T < T 2 4 2 5, 2 <  T << T , T << T 3 5 3 6  T < 5 6 T4 19 Graphe de précédence 2. Graphe de précédence  Pour construire le GP il faut éliminer les redondances du GT.  Exp  T 1 <  T < , T < T 2 4 2 5, 2 <  T << T , T << T 3 5 3 6  T < 5 6 T4 transitif 20 Graphe de précédence 2. Graphe de précédence  Pour construire le GP il faut éliminer les redondances du GT. T3  Exp  T 1 <  T < , T < T 2 4 2 5, 2 <  T << T , T << T 3 5 3 6  T < 5 6 T1 T2 T4 21 Graphe de précédence 2. Graphe de précédence  Pour construire le GP il faut éliminer les redondances du GT.  Exp  T 1 <  T < , T < T 2 4 2 5, 2 <  T << T , T << T 3 5 3 6  T < 5 6 T4 22 Graphe de précédence 2. Graphe de précédence  Pour construire le GP il faut éliminer les redondances du GT. T5 T6 T3  Exp  T 1 <  T < , T < T 2 4 2 5, 2 <  T << T , T << T 3 5 3 6  T < 5 6 T1 T2 T4 23 Graphe de précédence 2. Graphe de précédence  Remarques GT : graphe de tâches GP : graphe de précédence GFT : graphe de fermeture transitive 24 Graphe de précédence 2. Graphe de précédence  Remarques GT : graphe de tâches GP : graphe de précédence : on supprime tous les arcs transitifs GFT : graphe de fermeture transitive : on complète tous les arcs transitifs 25 Graphe de précédence 2. Graphe de précédence  Remarques GT : graphe de tâches GP : graphe de précédence GFT : graphe de fermeture transitive la relation de Bernstein : S  S = S  E = E  S = Ø i j i j i j p our savoir si deux tâches peuvent s’exécuter en //. 26 Graphe de précédence 2. Graphe de précédence  Remarques GT : graphe de tâches GP : graphe de précédence GFT : graphe de fermeture transitive La connaissance de GFT rends nécessaire et suffisante la relation de Bernstein : S  S = S  E = E  S = Ø i j i j i j p our savoir si deux tâches peuvent s’exécuter en //. 27 Graphe de précédence 3. Matrice d’adjacence S=(T ,…,T ,<<)  GP 1 n  A matrice d’adjacence d’ordre n  a =1 ssi T <<T ij i j T1 T2 T4 T5 T6 T3 28 Graphe de précédence 3. Matrice d’adjacence S=(T ,…,T ,<<)  GP 1 n  A matrice d’adjacence d’ordre n  a =1 ssi T <<T ij i j T1 T2 T4 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 T3 T5 T6 29 Graphe de précédence 3. Matrice d’adjacence S=(T ,…,T ,<<)  GP 1 n  A matrice d’adjacence d’ordre n  C’est une matrice creuse T1 T2 T4 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 T3 T5 T6 30 Graphe de précédence 3. Matrice d’adjacence Il existe un algorithme dit tri topologique qui permet de numéroter les nœuds d’un graphe pour avoir : si T <<T  i<j i j 31 Graphe de précédence 3. Matrice d’adjacence Il existe un algorithme dit tri topologique qui permet de numéroter les nœuds d’un graphe pour avoir : si T <<T  i<j i j La matrice A sera une matrice triangulaire supérieure 32 Graphe de précédence 3. Matrice d’adjacence Il existe un algorithme dit tri topologique qui permet de numéroter les nœuds d’un graphe pour avoir : si T <<T  i<j i j La matrice A sera une matrice triangulaire supérieure Si la matrice A a des 1 sur la diagonale alors le programme est séquentiel 33 Graphe de précédence 3. Matrice d’adjacence Il existe un algorithme dit tri topologique qui permet de numéroter les nœuds d’un graphe pour avoir : si T <<T  i<j i j La matrice A sera une matrice triangulaire supérieure Si la matrice A a des 1 sur la diagonale alors le programme est séquentiel Ainsi, nous devons comparer i avec i+1, .., n pour avoir une information sur l’ordre et l’indépendance des tâches. 34 Graphe de précédence 3. Matrice d’adjacence Il existe un algorithme dit tri topologique qui permet de numéroter les nœuds d’un graphe pour avoir : si T <<T  i<j i j La matrice A sera une matrice triangulaire supérieure Si la matrice A a des 1 sur la diagonale alors le programme est séquentiel Ainsi, nous devons comparer i avec i+1, .., n pour avoir une information sur l’ordre et l’indépendance des tâches. Il est important aussi de préciser le type de dépendance sur le GP 35 Graphe de précédence 4. Types de dépendance T : S = F (E ) i i i i T : S = F (E ) j j i j 36 Graphe de précédence 4. Types de dépendance T : S = E i i i T : S = E j j j 37 Graphe de précédence 4. Types de dépendance T : S = E i i i T : S = E j j j  : Dépendance de flux RAW (Read And Write) 38 Graphe de précédence 4. Types de dépendance T : S = E i i i T : S = E j j j  : Anti-Dépendance WAR (Write And Read) 39 Graphe de précédence 4. Types de dépendance T : S = E i i i T : S = E j j j  [°] : Dépendance de sortie WAW (Write And Write) 40 Graphe de précédence 4. Types de dépendance  : communication  : pas de communication  [°] : pas de communication Dans la pratique nous nous intéressons plus à la dépendance  qui engendre des coûts de communication. 41 Graphe de précédence 4. Types de dépendance Sur le GP T1 T2  T3  [°] T4 T5 T6 42 Graphe de précédence 4. Types de dépendance Sur le GP T1 T2  T3  [°] T4 T5 T6 43 Ordonnancement des tâches 1. Généralités PS=(T ,…,T ,  ) 1 n S =(T,…,T,<<) 1 n Pr = (P ,…,P ) 1 p L’ ordonnancement est défini comme suit ORD : tdb(T : temps de début d’exécution de T i ) i Proc(T ) : processeur qui va exécuter T i i  : durée de la tâche T i i 44 Ordonnancement des tâches 1. Généralités PS=(T ,…,T ,  ) 1 n S =(T,…,T,<<) 1 n Pr = (P ,…,P ) 1 p L’ ordonnancement est défini comme suit ORD : Si T <<T alors tdb(T ) < tdb(T ) i j i j Si tdb(T )=tdb(T ) alors Proc (T ) ≠Proc(T ) i j i j 45 Ordonnancement des tâches 1. Généralités PS=(T ,…,T ,  ) 1 n S =(T,…,T,<<) 1 n Pr = (P ,…,P ) 1 p L’ ordonnancement est défini comme suit ORD : Si Proc (T ) = Proc(T ) alors tdb(T )+  ≤tdb(T ) i j i i j ou tdb(T )+  ≤tdb(T ) j j i 46 Ordonnancement des tâches 1. Généralités PS=(T ,…,T ,  ) 1 n S =(T,…,T,<<) 1 n Pr = (P ,…,P ) 1 p L’ ordonnancement est défini comme suit ORD : T = durée de l’exécution des n tâches (makespan) p = maxi 47 Ordonnancement des tâches 1. Généralités PS=(T ,…,T ,  ) 1 n S =(T,…,T,<<) 1 n Pr = (P ,…,P ) 1 p L’ ordonnancement est défini comme suit ORD : T il faut le minimiser pour obtenir l’ORD optimal T p opt = maxi 48 Ordonnancement des tâches 1. Généralités PS=(T ,…,T ,  ) 1 n S =(T,…,T,<<) 1 n Pr = (P ,…,P ) 1 p L’ ordonnancement est défini comme suit ORD : T longueur du chemin critique dans GP opt = maxi 49 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard  tet = temps au plus tôt de la tâche i i  teT = temps au plus tard de la tâche i i 50 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard  tet = temps au plus tôt de la tâche i i  teT = temps au plus tard de la tâche i i a) Cas de << vide  T1 :  1= 3, tet1= 0, teT1= 3  T2 :  2= 4, tet2= 0, teT2= 2  T3 :  3= 6, tet3= 0, teT3= 0 51 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard  tet = temps au plus tôt de la tâche i i  teT = temps au plus tard de la tâche i i a) Cas de << vide  T1 :  1= 3, tet1= 0, teT1= 3  T2 :  2= 4, tet2= 0, teT2= 2  T3 :  3= 6, tet3= 0, teT3= 0 Au plus tôt Col1 T1 Col3 Col4 Col5 Col6 Col7 T2 T2 T2 T2 T3 T3 T3 T3 T3 T3 0 1 2 3 4 5 6 52 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard  tet = temps au plus tôt de la tâche i i  teT = temps au plus tard de la tâche i i a) Cas de << vide  T1 :  1= 3, tet1= 0, teT1= 3  T2 :  2= 4, tet2= 0, teT2= 2  T3 :  3= 6, tet3= 0, teT3= 0 Au plus tard Col1 Col2 Col3 Col4 T1 Col6 Col7 T2 T2 T2 T2 T3 T3 T3 T3 T3 T3 0 1 2 3 4 5 6 53 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard  tet = temps au plus tôt de la tâche i i  teT = temps au plus tard de la tâche i i a) Cas de << vide  T1 :  1= 3, tet1= 0, teT1= 3  T2 :  2= 4, tet2= 0, teT2= 2  T3 :  3= 6, tet3= 0, teT3= 0 Il existe 12 possibilités d’exécuter ces tâches avec un même coût T 6. opt = 54 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard b) Cas général  lorsqu’il ya dépendance entre les tâches, il faut déterminer T opt et déterminer pour chaque tâche tet et puis teT pour pouvoir définir l’ORD optimal. 55 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard b) Cas général T 2 56 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard b) Cas général Matrice d’adjacence T 2 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 57 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 58 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k C’est l’algorithme de balayage par prédécesseur 59 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k Les tâches qui n’ont pas de prédécesseurs commencent à 0 60 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 61 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 62 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 63 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 64 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 65 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 66 Ordonnancement des tâches b) Cas général Détermination de T opt tet=0 T =0 opt pour k=2 à n faire pour i=1 à k-1 faire si a =1 ik T 2 k k i i fin pour i T =max (T , tet +  ) opt opt k k fin pour k 67 Ordonnancement des tâches 2. Détermination de temps au plus tôt et au plus tard b) Cas général Donc T = 9 opt T 2 68 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 69 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 70 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 71 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 72 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 73 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 74 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 75 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 76 Ordonnancement des tâches b) Cas général teT=T pour toutes les tâches opt T 2 pour k=n à 1 faire pour i=k+1 à n faire si a =1 ik alors teT =min(teT, teT ) k k i fin pour i teT = teT -  k k k fin pour k 77 Ordonnancement des tâches b) Cas général (recap) T 2 T 2 78 Ordonnancement des tâches b) Cas général (recap) T 2 T 2 79 Ordonnancement des tâches b) Cas général (recap) T 2 T 2 Ordonnancement des tâches 80 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i Déterminer tet et teT T T 1 2 T 3 T 5 T 7 9 Ordonnancement des tâches 81 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i T T 1 2 T T 5 T 7 2, 4 9 4, 4 Ordonnancement des tâches 82 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i T T 1 2 T T 5 T 7 2, 4 Ordonnancement des tâches 83 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i T T 1 2 T T 5 T 7 2, 4 Ordonnancement des tâches 84 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i T T 1 2 T T 5 T 7 2, 4 Ordonnancement des tâches 85 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i T T 1 2 T T 5 T 7 2, 4 Ordonnancement des tâches 86 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i T 5 T 7 2, 4 Ordonnancement des tâches 87 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i Décomposer le graphe en des niveaux N k = niveau k T T 1 2 T T 5 T 7 2, 4 9 4, 4 Ordonnancement des tâches 88 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i Décomposer le graphe en des niveaux N k = niveau k T T 1 2 T N 1 = nœuds sans prédécesseurs N h(g) = nœuds sans successeurs T 5 T 7 2, 4 9 4, 4 Ordonnancement des tâches 89 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i Décomposer le graphe en des niveaux Deux décompositions : D tot (G) : chaque Ti se trouve Ntôt (i) D (G) : chaque T tard i se trouve Ntard (i) T T 1 2 T T 5 T 7 2, 4 9 4, 4 Ordonnancement des tâches 90 3. Détermination de P opt Pour toutes les tâches on suppose que  =1 i Décomposer le graphe en des niveaux Ntôt (i) = (teti/  )+1 Ntard (i) = (teTi/  )+1 T T 1 2 T T 5 T 7 2, 4 9 4, 4 Ordonnancement des tâches 91 3. Détermination de P opt Ntôt (i) = (teti /  ) +1 T T 1 2 T T 5 T 7 2, 4 9 4, 4 Ordonnancement des tâches 92 N N N N N 3. Détermination de P opt Ntôt (i) = (teti /  ) +1 5 T 5 Ordonnancement des tâches 93 N N N N N 3. Détermination de P opt Ntard (i) = (teTi/  )+1 94 Ordonnancement des tâches 3. Détermination de P opt N N N N N Ntard (i) = (teTi/  )+1 Ntôt (i) = (teti /  ) +1 N 5 N N N N Ordonnancement des tâches 95 3. Détermination de P opt Les tâches critiques sont toujours dans le même niveau N N N N N N 5 N N N N Ordonnancement des tâches 96 3. Détermination de P opt L : largeur du graphe = max du nombre de nœud dans un niveau N N N N N N 5 N N N N Ordonnancement des tâches 97 3. Détermination de P opt P ≤ min( Lt, LT) opt N N N N N Ntard (i) = (teTi/  )+1 Ntôt (i) = (teti /  ) +1 N 5 N N N N Ordonnancement des tâches 98 3. Détermination de P opt Topt =  *h(G) Tseq =  *n  S = n/h(G) N N N N N Ntard (i) = (teTi/  )+1 Ntôt (i) = (teti /  ) +1 N 5 N N N N Ordonnancement des tâches 99 3. Détermination de P opt n/h(G) ≤ Popt ≤ min( Lt, LT) N N N N N Ntard (i) = (teTi/  )+1 Ntôt (i) = (teti /  ) +1 N 5 N N N N Ordonnancement des tâches 100 3. Détermination de P opt n/h(G) ≤ Popt ≤ min( Lt, LT) Dans notre cas 2 ≤ Popt ≤ 3 N N N N N Ntard (i) = (teTi/  )+1 Ntôt (i) = (teti /  ) +1 N 5 N N N N Ordonnancement des tâches 101 P = 2 opt N N N N N 3. Détermination de P opt Ordonnancement des tâches 102 3. Détermination de P opt max( Lt, LT) ≤ P ≤ max L(D(G)) max N N N N N Ntard (i) = (teTi/  )+1 Ntôt (i) = (teti /  ) +1 N 5 N N N N Ordonnancement des tâches 103 max( Lt, LT) ≤ P ≤ max L(D(G)) max Dans notre cas P max = 4 N N N N N 3. Détermination de P opt 104 N N N N N Ordonnancement des tâches 3. Détermination de P opt ORD au plus tôt Proc1 T2 T4 T6 T8 T10 Proc2 T1 T5 T7 T9 Proc3 T3 0 1 2 3 4 5 5 105 N N N N N Ordonnancement des tâches 3. Détermination de P opt ORD au plus tard Proc1 T2 T4 T6 T8 T10 Proc2 T3 T5 T1 T9 Proc3 T7 0 1 2 3 4 5 106 N N N N N Ordonnancement des tâches 3. Détermination de P opt ORD optimal Proc1 T2 T4 T6 T8 T10 Proc2 T3 T5 T7 T1 T9 0 1 2 3 4 5 107 N N N N N Ordonnancement des tâches 3. Détermination de P opt ORD optimal Proc1 T2 T4 T6 T8 T10 Proc2 T3 T5 T7 T1 T9 0 1 2 3 4 5 Avec trois processeurs on a T opt mais le coût n’est pas optimal en nombre de processeur