Présentation de thèse - Fadi KACEM

Preview:

Citation preview

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Algorithmes exacts et approchés pour desproblèmes d’ordonnancement et de placement

Travaux de thèse de Fadi Kacem

Directeur de thèse : Evripidis BampisCo-encadrant : Eric Angel

27 Juin 2012

Laboratoire IBISC, Université d’Evry Val d’Essonne

1/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Organisation générale

Problèmes de minimisation d’énergie.

Problèmes d’optimisation classiques :

. Ordonnancement avec des temps de communnication.

. Placement de données dans un réseau pair à pair.

2/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Organisation générale

Problèmes de minimisation d’énergie.

Problèmes d’optimisation classiques :

. Ordonnancement avec des temps de communnication.

. Placement de données dans un réseau pair à pair.

2/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Organisation générale

Problèmes de minimisation d’énergie.

Problèmes d’optimisation classiques :

. Ordonnancement avec des temps de communnication.

. Placement de données dans un réseau pair à pair.

3/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

4/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

5/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Contexte et motivationsL’enjeu énergétique

1.3% de l’énergie mondiale est consommée par les centres dedonnées [J.G. Koomey’2011].

Critique du point de vue environnemental (émission de carbone, dechaleur, etc.), mais aussi économique (coût de l’énergie, coût derefroidissement, etc.).

Approches Logicielles de conservation de l’énergie :

. Ordonnancement et Allocation de Ressources

6/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Contexte et motivationsL’enjeu énergétique

1.3% de l’énergie mondiale est consommée par les centres dedonnées [J.G. Koomey’2011].

Critique du point de vue environnemental (émission de carbone, dechaleur, etc.), mais aussi économique (coût de l’énergie, coût derefroidissement, etc.).

Approches Logicielles de conservation de l’énergie :

. Ordonnancement et Allocation de Ressources

6/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Contexte et motivationsL’enjeu énergétique

1.3% de l’énergie mondiale est consommée par les centres dedonnées [J.G. Koomey’2011].

Critique du point de vue environnemental (émission de carbone, dechaleur, etc.), mais aussi économique (coût de l’énergie, coût derefroidissement, etc.).

Approches Logicielles de conservation de l’énergie :

. Ordonnancement et Allocation de Ressources

6/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Contexte et motivationsL’enjeu énergétique

1.3% de l’énergie mondiale est consommée par les centres dedonnées [J.G. Koomey’2011].

Critique du point de vue environnemental (émission de carbone, dechaleur, etc.), mais aussi économique (coût de l’énergie, coût derefroidissement, etc.).

Approches Logicielles de conservation de l’énergie :

. Ordonnancement et Allocation de Ressources

6/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

7/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Présentation des modèles.

1 Modèle de gestion des états de veille (Power DownManagement).

2 Modèle d’adaptation des vitesses (Speed Scaling).

3 Modèle mixte : Adaptation des vitesses avec états de veille.

4 Modèle des vitesses discrètes.

8/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Présentation des modèles.

1 Modèle de gestion des états de veille (Power DownManagement).

2 Modèle d’adaptation des vitesses (Speed Scaling).

3 Modèle mixte : Adaptation des vitesses avec états de veille.

4 Modèle des vitesses discrètes.

9/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle de gestion des états de veille.Power Down Management

Le système peut, à tout moment, mettre le processeur dansun état de veille ( mode Off ) où la consommation d’énergieest basse voire nulle. Dans cet état, aucun travail ne peut êtreeffectué.

OnouOff ?

OnouOff ?

OnouOff ?

OnouOff ?

10/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle de gestion des états de veille.Power Down Management

Une quantité fixe d’énergie est requise pour revenir à un étatactif et reprendre l’exécution.

OffOn On On

11/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Présentation des modèles.

1 Modèle de gestion des états de veille (Power DownManagement).

2 Modèle d’adaptation des vitesses (Speed Scaling).

3 Modèle mixte : Adaptation des vitesses avec états de veille.

4 Modèle des vitesses discrètes.

12/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling [Yao et al.’ 1995]

Chaque processeur peut tourner à des vitesses différentes.

Si un processeur tourne à une vitesse v pendant t unités detemps alors :

. il effectue un travail w = v .t

. il consomme une énergie E = P(v).tP(v) : puissance de consommation d’énergie (P(v) = vα, α > 1).

Donc moins la vitesse est grande, moins d’énergie estconsommée par le processeur mais moins la qualité de servicesera préservée.

13/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling [Yao et al.’ 1995]

Chaque processeur peut tourner à des vitesses différentes.

Si un processeur tourne à une vitesse v pendant t unités detemps alors :

. il effectue un travail w = v .t

. il consomme une énergie E = P(v).tP(v) : puissance de consommation d’énergie (P(v) = vα, α > 1).

Donc moins la vitesse est grande, moins d’énergie estconsommée par le processeur mais moins la qualité de servicesera préservée.

13/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling [Yao et al.’ 1995]

Chaque processeur peut tourner à des vitesses différentes.

Si un processeur tourne à une vitesse v pendant t unités detemps alors :

. il effectue un travail w = v .t

. il consomme une énergie E = P(v).tP(v) : puissance de consommation d’énergie (P(v) = vα, α > 1).

Donc moins la vitesse est grande, moins d’énergie estconsommée par le processeur mais moins la qualité de servicesera préservée.

13/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling [Yao et al.’ 1995]

Chaque processeur peut tourner à des vitesses différentes.

Si un processeur tourne à une vitesse v pendant t unités detemps alors :

. il effectue un travail w = v .t

. il consomme une énergie E = P(v).tP(v) : puissance de consommation d’énergie (P(v) = vα, α > 1).

Donc moins la vitesse est grande, moins d’énergie estconsommée par le processeur mais moins la qualité de servicesera préservée.

13/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling [Yao et al.’ 1995]

Chaque processeur peut tourner à des vitesses différentes.

Si un processeur tourne à une vitesse v pendant t unités detemps alors :

. il effectue un travail w = v .t

. il consomme une énergie E = P(v).tP(v) : puissance de consommation d’énergie (P(v) = vα, α > 1).

Donc moins la vitesse est grande, moins d’énergie estconsommée par le processeur mais moins la qualité de servicesera préservée.

13/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling

0 temps3 4 5 6 7 8 10

w1 = 12

w2 = 8 w3 = 2

v1 = 3

v2 = 8

v3 = 1

Énergie =

P (v) = v3

w1v1

33.4 + 83.1 13.2+

= 622

14/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling

0 temps3 4 5 6 7 8 10

w1 = 12

w2 = 8 w3 = 2

v1 = 3

v2 = 8

v3 = 1Énergie = 622

P (v) = v3

15/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle d’adaptation des vitesses.Speed Scaling

v1 = 2

v2 = 4

v3 = 1Énergie = 178

0 temps3 4 5 6 7 8 10

w1 = 12

w2 = 8 w3 = 2

v1 = 3

v2 = 8

v3 = 1Énergie = 622

P (v) = v3

16/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Présentation des modèles.

1 Modèle de gestion des états de veille (Power DownManagement).

2 Modèle d’adaptation des vitesses (Speed Scaling).

3 Modèle mixte : Adaptation des vitesses avec états de veille.

4 Modèle des vitesses discrètes.

17/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixteAdaptation des vitesse avec états de veille [Irani et Pruhs’2005]

Modèle d’Adapatation des Vitesses (Speed Scaling) :consommation nulle en l’absence de tâches à exécuter.

Dans un modèle plus réaliste, il existe toujours une dissipationd’énergie même si la machine est inactive.

18/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixteAdaptation des vitesse avec états de veille [Irani et Pruhs’2005]

Modèle d’Adapatation des Vitesses (Speed Scaling) :consommation nulle en l’absence de tâches à exécuter.

Dans un modèle plus réaliste, il existe toujours une dissipationd’énergie même si la machine est inactive.

18/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixteAdaptation des vitesse avec états de veille

Dans un modèle plus réaliste, il existe toujours une dissipationd’énergie même si la machine est inactive.

Etats de la machine

On (v ≥ 0) Off (machine en veille, v = 0)

P (v) = vα + g P (v) = 0.

Coût du passage de Off à On: L > 0.énergie d’exécution énergie basique

19/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixteAdaptation des vitesse avec états de veille

4/31

5/3

Ordonnancement optimal sous le modèle d’adaptation des vitesses

temps0 3 4 7 12

w3 = 6

w4 = 4 w5 = 5

(P (v) = v3)

20/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixteAdaptation des vitesse avec états de veille

4/31

5/3

Off Off

Énergie =

exécution= ( 43)3.3 + ( 5

3)3.3 + 13.6 = 27

basique= 16× 12 = 192

+

P (v) = v3 + 16

L = 40

temps0 3 4 7 12

w3 = 6

w4 = 4 w5 = 5

1 8.5

21/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixteAdaptation des vitesse avec états de veille

4/31

5/3

Off Off

Énergie =

exécution= ( 43)3.3 + ( 5

3)3.3 + 13.6 = 27

basique= 16× 12 = 192

+

P (v) = v3 + 16

L = 40

v = 2

Off

Énergie =

Off

exécution= 23 × 7.5 = 60

basique= 16 × 7.5 = 120

+

temps0 3 4 7 12

w3 = 6

w4 = 4 w5 = 5

1 8.5

22/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Présentation des modèles.

1 Modèle de gestion des états de veille (Power DownManagement).

2 Modèle d’adaptation des vitesses (Speed Scaling).

3 Modèle mixte : Adaptation des vitesses avec états de veille.

4 Modèle des vitesses discrètes.

23/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle des vitesses discrètesUn modèle discret

Un ensemble discret et fini de vitesses possibles pour chaqueprocesseur.

La fonction de puissance de consommation d’énergie ne suitpas une loi particulière.

Des processeurs hétérogènes :

. Pour chaque tâche, la durée d’exécution ainsi que lacontribution à la consommation totale d’énergie dépendent dela machine d’affectation et de la vitesse sélectionnée.

24/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle des vitesses discrètesUn modèle discret

Un ensemble discret et fini de vitesses possibles pour chaqueprocesseur.

La fonction de puissance de consommation d’énergie ne suitpas une loi particulière.

Des processeurs hétérogènes :

. Pour chaque tâche, la durée d’exécution ainsi que lacontribution à la consommation totale d’énergie dépendent dela machine d’affectation et de la vitesse sélectionnée.

24/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle des vitesses discrètesUn modèle discret

Un ensemble discret et fini de vitesses possibles pour chaqueprocesseur.

La fonction de puissance de consommation d’énergie ne suitpas une loi particulière.

Des processeurs hétérogènes :

. Pour chaque tâche, la durée d’exécution ainsi que lacontribution à la consommation totale d’énergie dépendent dela machine d’affectation et de la vitesse sélectionnée.

24/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle d’adaptation des vitesses

Un algorithme optimal pour le problème S1|ri , di , pmtn|E , [Yao etal.’1995].

Le problème S|ri , di , pmtn, no-mig |E est NP-difficile [Albers et al.’2007].Les auteurs ont proposé un algorithme αα24α-approché.

⇒ Nous nous basons sur la programmation convexe et des techniques de calculde flots pour résoudre le problème S|ri , di , pmtn,mig |E .

25/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle d’adaptation des vitesses

Un algorithme optimal pour le problème S1|ri , di , pmtn|E , [Yao etal.’1995].

Le problème S|ri , di , pmtn, no-mig |E est NP-difficile [Albers et al.’2007].Les auteurs ont proposé un algorithme αα24α-approché.

⇒ Nous nous basons sur la programmation convexe et des techniques de calculde flots pour résoudre le problème S|ri , di , pmtn,mig |E .

25/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle d’adaptation des vitesses

Un algorithme optimal pour le problème S1|ri , di , pmtn|E , [Yao etal.’1995].

Le problème S|ri , di , pmtn, no-mig |E est NP-difficile [Albers et al.’2007].Les auteurs ont proposé un algorithme αα24α-approché.

⇒ Nous nous basons sur la programmation convexe et des techniques de calculde flots pour résoudre le problème S|ri , di , pmtn,mig |E .

25/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle mixte : adaptation des vitesse + état de veille

Le problème S1|ri , di , pmtn,mixte|E a été posé par Irani et Pruhs en2005.

Un algorithme 2-approché [Irani et al.’2007].

Albers et al. ont récemment prouvé que le problème est NP-complet(SODA’2012) (même dans le cas de structure d’arbres).

⇒ Nous proposons un algorithme polynomial basé sur la programmationdynamique pour résoudre le problème dans le cas d’instances agréables : ∀paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj .

26/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle mixte : adaptation des vitesse + état de veille

Le problème S1|ri , di , pmtn,mixte|E a été posé par Irani et Pruhs en2005.

Un algorithme 2-approché [Irani et al.’2007].

Albers et al. ont récemment prouvé que le problème est NP-complet(SODA’2012) (même dans le cas de structure d’arbres).

⇒ Nous proposons un algorithme polynomial basé sur la programmationdynamique pour résoudre le problème dans le cas d’instances agréables : ∀paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj .

26/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle mixte : adaptation des vitesse + état de veille

Le problème S1|ri , di , pmtn,mixte|E a été posé par Irani et Pruhs en2005.

Un algorithme 2-approché [Irani et al.’2007].

Albers et al. ont récemment prouvé que le problème est NP-complet(SODA’2012) (même dans le cas de structure d’arbres).

⇒ Nous proposons un algorithme polynomial basé sur la programmationdynamique pour résoudre le problème dans le cas d’instances agréables : ∀paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj .

26/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle mixte : adaptation des vitesse + état de veille

Le problème S1|ri , di , pmtn,mixte|E a été posé par Irani et Pruhs en2005.

Un algorithme 2-approché [Irani et al.’2007].

Albers et al. ont récemment prouvé que le problème est NP-complet(SODA’2012) (même dans le cas de structure d’arbres).

⇒ Nous proposons un algorithme polynomial basé sur la programmationdynamique pour résoudre le problème dans le cas d’instances agréables : ∀paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj .

26/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle discret

[Carrasco et al.’2011] : des algorithmes O(1)-approchés pour lesproblèmes :

. S1|ri , prec, discret|E +∑

wjCj ,

. S1|ri , prec, discret|E +∑

wjTj .

⇒ Nous proposons un algorithme approché basé sur la programmation linéaireet la technique de l’arrondi aléatoire pour résoudre les problèmes :

.RS|ri , discret,E |∑

wjCj ,

.RS|ri , discret|E +∑

wjCj .

27/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

État de l’art.Modèle discret

[Carrasco et al.’2011] : des algorithmes O(1)-approchés pour lesproblèmes :

. S1|ri , prec, discret|E +∑

wjCj ,

. S1|ri , prec, discret|E +∑

wjTj .

⇒ Nous proposons un algorithme approché basé sur la programmation linéaireet la technique de l’arrondi aléatoire pour résoudre les problèmes :

.RS|ri , discret,E |∑

wjCj ,

.RS|ri , discret|E +∑

wjCj .

27/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

28/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationPrésentation du problème

Données du problème :

Un ensemble J = {J1, . . . , Jn} de n tâches.

Chaque tâche Ji est caractérisée par une quantité de travailwi , une date d’arrivée ri et une date d’échéance di .

m machines identiques et un spectre continu et infini devitesses possibles pour chaque machine.

Objectif : résoudre le problème S|ri , di , pmtn|E avec migration etpréemption sous le modèle d’adaptation des vitesses.

29/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationPrésentation du problème

Données du problème :

Un ensemble J = {J1, . . . , Jn} de n tâches.

Chaque tâche Ji est caractérisée par une quantité de travailwi , une date d’arrivée ri et une date d’échéance di .

m machines identiques et un spectre continu et infini devitesses possibles pour chaque machine.

Objectif : résoudre le problème S|ri , di , pmtn|E avec migration etpréemption sous le modèle d’adaptation des vitesses.

29/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationPrésentation du problème

Données du problème :

Un ensemble J = {J1, . . . , Jn} de n tâches.

Chaque tâche Ji est caractérisée par une quantité de travailwi , une date d’arrivée ri et une date d’échéance di .

m machines identiques et un spectre continu et infini devitesses possibles pour chaque machine.

Objectif : résoudre le problème S|ri , di , pmtn|E avec migration etpréemption sous le modèle d’adaptation des vitesses.

29/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationPrésentation du problème

Données du problème :

Un ensemble J = {J1, . . . , Jn} de n tâches.

Chaque tâche Ji est caractérisée par une quantité de travailwi , une date d’arrivée ri et une date d’échéance di .

m machines identiques et un spectre continu et infini devitesses possibles pour chaque machine.

Objectif : résoudre le problème S|ri , di , pmtn|E avec migration etpréemption sous le modèle d’adaptation des vitesses.

29/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationPrésentation du problème

Données du problème :

Un ensemble J = {J1, . . . , Jn} de n tâches.

Chaque tâche Ji est caractérisée par une quantité de travailwi , une date d’arrivée ri et une date d’échéance di .

m machines identiques et un spectre continu et infini devitesses possibles pour chaque machine.

Objectif : résoudre le problème S|ri , di , pmtn|E avec migration etpréemption sous le modèle d’adaptation des vitesses.

29/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Vitesse ConstanteDans un ordonnancement optimal, chaque tâche Ji est exécutée àune vitesse constante vi .

La difficulté consiste donc à déterminer la vitesse d’exécutionattribuée à chaque tâche.

Une fois toutes les vitesses calculées, nous obtenons uneinstance du problème de faisabilité P|ri , di , pmtn|−.

30/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Vitesse ConstanteDans un ordonnancement optimal, chaque tâche Ji est exécutée àune vitesse constante vi .

La difficulté consiste donc à déterminer la vitesse d’exécutionattribuée à chaque tâche.

Une fois toutes les vitesses calculées, nous obtenons uneinstance du problème de faisabilité P|ri , di , pmtn|−.

30/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Vitesse ConstanteDans un ordonnancement optimal, chaque tâche Ji est exécutée àune vitesse constante vi .

La difficulté consiste donc à déterminer la vitesse d’exécutionattribuée à chaque tâche.

Une fois toutes les vitesses calculées, nous obtenons uneinstance du problème de faisabilité P|ri , di , pmtn|−.

30/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationUn algorithme optimal

Quelques idées directrices :

les tâches sont exécutées à des vitesses aussi faibles quepossible.

utiliser des vitesses aussi proches que possible (convexité de lafonction de puissance) :

. idéalement, toutes les tâches sont exécutées avec lamême vitesse.

31/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationUn algorithme optimal

Quelques idées directrices :

les tâches sont exécutées à des vitesses aussi faibles quepossible.

utiliser des vitesses aussi proches que possible (convexité de lafonction de puissance) :

. idéalement, toutes les tâches sont exécutées avec lamême vitesse.

31/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationUn algorithme optimal

Quelques idées directrices :

les tâches sont exécutées à des vitesses aussi faibles quepossible.

utiliser des vitesses aussi proches que possible (convexité de lafonction de puissance) :

. idéalement, toutes les tâches sont exécutées avec lamême vitesse.

31/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationAlgorithme SSM : exemple

0 2 3 6I1 I2 I3

J2 (w2 = 3)

J3 (w3 = 6) J6 (w6 = 4)

J5 (w5 = 4)

J1 (w1 = 8) J4 (w4 = 6)

32/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationAlgorithme SSM : exemple

0 2 3 6I1 I2 I3

J2 (w2 = 3)

J3 (w3 = 6) J6 (w6 = 4)

J5 (w5 = 4)

J1 (w1 = 8) J4 (w4 = 6)

v = 8

33/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationAlgorithme SSM : exemple

0 2 3 6I1 I2 I3

J2 (w2 = 3)

J3 (w3 = 6) J6 (w6 = 4)

J5 (w5 = 4)

J1 (w1 = 8) J4 (w4 = 6)

v = 4

34/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationAlgorithme SSM : exemple

0 2 3 6I1 I2 I3

J2 (w2 = 3)

J3 (w3 = 6) J6 (w6 = 4)

J5 (w5 = 4)

J1 (w1 = 8) J4 (w4 = 6)

v = 3

v = 4

v = 3

35/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationAlgorithme SSM : exemple

0 2 3 6I1 I2 I3

J2 (w2 = 3)

J3 (w3 = 6) J6 (w6 = 4)

J5 (w5 = 4)

J1 (w1 = 8) J4 (w4 = 6)

v = 2

v = 4

v = 3

36/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationAlgorithme SSM

Tâche Critique en terme de Flot

s p

x1

x2

xn

y1

y2

y3

y

y

L-1

L

w1

v

w2

v

wn

v

|I1|

|I1|

|I2|

|I2|

|I3|

|IL−1|

|IL|

m1|I1|

m2|I2|

m3|I3|

mL−1|IL−1|

mL|IL|

Une (s, p)-coupe Minimale

37/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Propriété de la Charge Maximale

J1 J3J5

J4J2

tempst0 t1 t2 t3 t4 t5 t6 t7 t8

I1 I2 I3 I4 I5 I6 I7 I8

t9

I9

J6

J7

machine 1

machine 2

38/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Propriété de la Charge Maximale

J1 J3J5

J4J2

tempst0 t1 t2 t3 t4 t5 t6 t7 t8

I1 I2 I3 I4 I5 I6 I7 I8

t9

I9

J6

J7

machine 1

machine 2

39/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Propriété de la Charge Maximale

J1 J3J5

J4J2

tempst0 t1 t2 t3 t4 t5 t6 t7 t8

I1 I2 I3 I4 I5 I6 I7 I8

t9

I9

J6

J7

machine 1

machine 2

40/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Profil des Vitesses

Ji

tempsI

Jj

Jk

⇒ vi = vj = vk

41/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Profil des Vitesses

Ji

tempsI

Jj

Jk

⇒ vi = vj ≤ vk

42/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationStructure de la solution optimale

Profil des Vitesses

Ji

tempsI

Jj

Jk

⇒ vi = vj ≥ vk

Preuve : application des conditions KKT à une formulation convexe du problème.43/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationOptimalité de l’algorithme SSM

ThéorèmeToute solution vérifiant les propriétés de la vitesse constante, de lacharge maximale et du profil des vitesses est optimale.

L’algorithme SSM est optimal : toute solution retournéevérifie les conditions d’optimalité (vitesse constante, chargemaximale, profil des vitesses).

Complexité : O(nC(n, n2)log(P)).

Indépendemment, Albers et al. ont aussi utilisé la techniquedes flots pour résoudre le problème.

44/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationOptimalité de l’algorithme SSM

ThéorèmeToute solution vérifiant les propriétés de la vitesse constante, de lacharge maximale et du profil des vitesses est optimale.

L’algorithme SSM est optimal : toute solution retournéevérifie les conditions d’optimalité (vitesse constante, chargemaximale, profil des vitesses).

Complexité : O(nC(n, n2)log(P)).

Indépendemment, Albers et al. ont aussi utilisé la techniquedes flots pour résoudre le problème.

44/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationOptimalité de l’algorithme SSM

ThéorèmeToute solution vérifiant les propriétés de la vitesse constante, de lacharge maximale et du profil des vitesses est optimale.

L’algorithme SSM est optimal : toute solution retournéevérifie les conditions d’optimalité (vitesse constante, chargemaximale, profil des vitesses).

Complexité : O(nC(n, n2)log(P)).

Indépendemment, Albers et al. ont aussi utilisé la techniquedes flots pour résoudre le problème.

44/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationOptimalité de l’algorithme SSM

ThéorèmeToute solution vérifiant les propriétés de la vitesse constante, de lacharge maximale et du profil des vitesses est optimale.

L’algorithme SSM est optimal : toute solution retournéevérifie les conditions d’optimalité (vitesse constante, chargemaximale, profil des vitesses).

Complexité : O(nC(n, n2)log(P)).

Indépendemment, Albers et al. ont aussi utilisé la techniquedes flots pour résoudre le problème.

44/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

45/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Extension du modèle : les machines peuvent passer dans unétat de veille (consommation nulle).

Nous supposons que les dates d’arrivée et d’échéance sontagréables : ∀ paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj

Objectif : Construire sur une machine un ordonnancementréalisable qui minimise l’énergie consommée tout en autorisant lapréemption des tâches.

46/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Extension du modèle : les machines peuvent passer dans unétat de veille (consommation nulle).

Nous supposons que les dates d’arrivée et d’échéance sontagréables : ∀ paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj

Objectif : Construire sur une machine un ordonnancementréalisable qui minimise l’énergie consommée tout en autorisant lapréemption des tâches.

46/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Extension du modèle : les machines peuvent passer dans unétat de veille (consommation nulle).

Nous supposons que les dates d’arrivée et d’échéance sontagréables : ∀ paire de tâches (Ji , Jj), ri ≤ rj ⇔ di ≤ dj

Objectif : Construire sur une machine un ordonnancementréalisable qui minimise l’énergie consommée tout en autorisant lapréemption des tâches.

46/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

La difficulté consiste donc à ordonnancer les travaux soumis àla machine de façon à :

. minimiser la fréquence des transitions entre les états defonctionnement ( On ) et les états de veille ( Off ).

. maximiser les durées des périodes de veille.

Rappel : un algorithme optimal dans le modèle d’Adaptationdes Vitesses [Yao et al’1995], (YDS).

47/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

La difficulté consiste donc à ordonnancer les travaux soumis àla machine de façon à :

. minimiser la fréquence des transitions entre les états defonctionnement ( On ) et les états de veille ( Off ).

. maximiser les durées des périodes de veille.

Rappel : un algorithme optimal dans le modèle d’Adaptationdes Vitesses [Yao et al’1995], (YDS).

47/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

La difficulté consiste donc à ordonnancer les travaux soumis àla machine de façon à :

. minimiser la fréquence des transitions entre les états defonctionnement ( On ) et les états de veille ( Off ).

. maximiser les durées des périodes de veille.

Rappel : un algorithme optimal dans le modèle d’Adaptationdes Vitesses [Yao et al’1995], (YDS).

47/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

La difficulté consiste donc à ordonnancer les travaux soumis àla machine de façon à :

. minimiser la fréquence des transitions entre les états defonctionnement ( On ) et les états de veille ( Off ).

. maximiser les durées des périodes de veille.

Rappel : un algorithme optimal dans le modèle d’Adaptationdes Vitesses [Yao et al’1995], (YDS).

47/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

48/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

Énergie = L

49/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

Énergie = L +∫ t2

t1(vitesse(t)α + g)dt

50/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

Énergie = L +∫ t2

t1(vitesse(t)α + g)dt +

∫ t3t2

g .dt

51/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

Énergie = L +∫ t2

t1(vitesse(t)α + g)dt +

∫ t3t2

g .dt +∫ t4

t3(vitesse(t)α + g)dt

52/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

Énergie = L +∫ t2

t1(vitesse(t)α + g)dt +

∫ t3t2

g .dt +∫ t4

t3(vitesse(t)α + g)dt + L

53/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machinePrésentation du problème

Coût d’un ordonnancement :

Off

On

t1 t2 t3 t4 t5 t6 temps

OffOff

On

Énergie = L +∫ t2

t1(vitesse(t)α + g)dt +

∫ t3t2

g .dt +∫ t4

t3(vitesse(t)α + g)dt +

L +∫ t6

t5(vitesse(t)α + g)dt

54/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineVitesse parfaite

Si une tâche Ji avec une quantité de travail wi est exécutée à unevitesse constante v : Énergie = wi

v P(v).P(v)

v : énergie nécessaire à l’exécution d’une unité de travail.P (v)v

= vα+gv

v

b

v? = ( gα−1

)1/α

55/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineDécomposition en sous instances

Les intervalles denses calculés par YDS décomposent en dessous instances (i , j) telles que la vitesse ne dépasse pas v?

dans une solution optimale.

vitesse ≤ v?sous instance (i, j)

Intervalle dense

di−1 rj+1

L’indépendance des sous instances est une conséquence desdates d’échéance agréables.

56/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineSuffixes et Préfixes

Intervalle dense

suffixe

OffJa Jb Jb+1 Jc

ra dc

préfixe

Intervalle dense

57/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

On caclule l’ordonnancement optimal sans état de veille(YDS) et on considère les sous instances (i , j) non denses.

58/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

Cas basique. Sous Instance (i , j) vide (i = j + 1)

Ji−1 Ji

di−1 ri

59/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

Première alternative. Sous Instance (i , j) sans période deVeille (Off)

Ji−1 Jj+1

di−1 rj+1

60/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

Deuxième alternative. Sous Instance (i , j) avec période deVeille : machine en veille au début de l’ordonnancement

Ji−1 Jj+1

di−1 rj+1

Ji Jc

préfixe

Off

dc

Sous Instance (c+ 1, j)

61/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

Troisième alternative. Sous Instance (i , j) avec une seulepériode de Veille : machine en veille à la fin del’ordonnancement

Ji−1 Jj+1

di−1 rj+1

Ja Jj

suffixe

ra

Sous Instance (i, a− 1)

Off

sans période de veille

62/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

Quatrième alternative. Sous Instance (i , j) avec une premièrepériode de Veille au milieu de l’ordonnancement

Ji−1 Jj+1

di−1 rj+1

Ja Jb

suffixe

ra

Sous Instance (i, a− 1)

Off

sans période de veille

Jb+1 Jc

préfixe

dc

Sous Instance (c+ 1, j)

63/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle mixte : cas d’une seule machineProgramme dynamique

ThéorèmeLe programme dynamique calcule une solution optimale pour touteinstance du problème en O(n3).

64/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

65/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

m machines hétérogènes et un ensemble fini V de vitesses.

Chaque tâche Jj est caractérisée par :. un poids wj et une date d’arrivée rij dépendante de la machine id’affectation,

. un temps d’exécution pijv et une quantité d’énergie Eijv qui dépendentde la machine d’affectation i et de la vitesse d’exécution v ∈ V.

. un budget d’énergie B > 0.

66/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

m machines hétérogènes et un ensemble fini V de vitesses.

Chaque tâche Jj est caractérisée par :. un poids wj et une date d’arrivée rij dépendante de la machine id’affectation,

. un temps d’exécution pijv et une quantité d’énergie Eijv qui dépendentde la machine d’affectation i et de la vitesse d’exécution v ∈ V.

. un budget d’énergie B > 0.

66/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

m machines hétérogènes et un ensemble fini V de vitesses.

Chaque tâche Jj est caractérisée par :. un poids wj et une date d’arrivée rij dépendante de la machine id’affectation,

. un temps d’exécution pijv et une quantité d’énergie Eijv qui dépendentde la machine d’affectation i et de la vitesse d’exécution v ∈ V.

. un budget d’énergie B > 0.

66/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

m machines hétérogènes et un ensemble fini V de vitesses.

Chaque tâche Jj est caractérisée par :. un poids wj et une date d’arrivée rij dépendante de la machine id’affectation,

. un temps d’exécution pijv et une quantité d’énergie Eijv qui dépendentde la machine d’affectation i et de la vitesse d’exécution v ∈ V.

. un budget d’énergie B > 0.

66/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

m machines hétérogènes et un ensemble fini V de vitesses.

Chaque tâche Jj est caractérisée par :. un poids wj et une date d’arrivée rij dépendante de la machine id’affectation,

. un temps d’exécution pijv et une quantité d’énergie Eijv qui dépendentde la machine d’affectation i et de la vitesse d’exécution v ∈ V.

. un budget d’énergie B > 0.

66/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

Objectif : un algorithme approché pour le problèmeRS|ri , discret,E |

∑wjCj , sans préemption ni migration.

. Il s’agit d’objectifs orthogonaux :

énergie basse → petites vitesses → temps de complétudesimportants.

67/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesPrésentation du problème

Objectif : un algorithme approché pour le problèmeRS|ri , discret,E |

∑wjCj , sans préemption ni migration.

. Il s’agit d’objectifs orthogonaux :

énergie basse → petites vitesses → temps de complétudesimportants.

67/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesNotre approche

Le problème est NP-difficile. En effet, le problème sans lacontrainte sur l’énergie est NP-difficile :

. 1|rj |∑

Cj ; P2|rij |∑

wjCj ; P|rij |∑

wjCj sont NP-difficiles.

Shulz et al. ont proposé un algorithme approché basé sur latechnique de l’arrondi aléatoire pour le problème R|rij |

∑wjCj .

. On se propose donc d’étendre cette approche pour résoudre leproblème avec énergie.

68/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesNotre approche

Le problème est NP-difficile. En effet, le problème sans lacontrainte sur l’énergie est NP-difficile :

. 1|rj |∑

Cj ; P2|rij |∑

wjCj ; P|rij |∑

wjCj sont NP-difficiles.

Shulz et al. ont proposé un algorithme approché basé sur latechnique de l’arrondi aléatoire pour le problème R|rij |

∑wjCj .

. On se propose donc d’étendre cette approche pour résoudre leproblème avec énergie.

68/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

On utilise des intervalles de tailles géométriques pour discrétiser letemps.

temps0 1 1 + ε (1 + ε)2 (1 + ε)3 (1 + ε)L

I0 I1 I2 I3 IL

. ε > 0 : un réel fixé.

. T =∑

Jjmaxi pij : horizon du temps.

. L ≥ 0 : plus petit entier tel que (1+ ε)L ≥ T .

69/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

Relaxation Linéaire : → on autorise la préemption.→ on autorise l’exécution parallèle.

Variables du Programme Linéaire :. yij`v : proportion de l’intervalle I` occupée par la tâche Jj sur lamachine i lorsqu’elle tourne à la vitesse v .

. CLPj : date de complétude de la tâche Jj dans la relaxation.

70/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

Relaxation Linéaire : → on autorise la préemption.→ on autorise l’exécution parallèle.

Variables du Programme Linéaire :. yij`v : proportion de l’intervalle I` occupée par la tâche Jj sur lamachine i lorsqu’elle tourne à la vitesse v .

. CLPj : date de complétude de la tâche Jj dans la relaxation.

70/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

Relaxation Linéaire : → on autorise la préemption.→ on autorise l’exécution parallèle.

Variables du Programme Linéaire :. yij`v : proportion de l’intervalle I` occupée par la tâche Jj sur lamachine i lorsqu’elle tourne à la vitesse v .

. CLPj : date de complétude de la tâche Jj dans la relaxation.

70/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

Relaxation Linéaire : → on autorise la préemption.→ on autorise l’exécution parallèle.

Variables du Programme Linéaire :. yij`v : proportion de l’intervalle I` occupée par la tâche Jj sur lamachine i lorsqu’elle tourne à la vitesse v .

. CLPj : date de complétude de la tâche Jj dans la relaxation.

70/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

min∑Jj∈J

wj CLPj

m∑i=1

L∑`=0

∑v∈V

yij`v |I`|

pijv= 1, pour tout j, (1)

∑Jj∈J

∑v∈V

yij`v ≤ 1, pour tout i et `, (2)

CLPj ≥

m∑i=1

∑v∈V

12

yij0v |I0|(

1 +1

pijv

)+

m∑i=1

L∑`=1

∑v∈V

(yij`v |I`|

pijv(1 + ε)`−1 +

12

yij`v |I`|), pour tout j, (3)

71/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesProgrammation linéaire

CLPj ≥

m∑i=1

L∑`=0

∑v∈V

yij`v |I`|, pour tout j, (4)

m∑i=1

∑Jj∈J

L∑`=0

∑v∈V

Eijvyij`v |I`|

pijv≤ B, (5)

yij`v = 0, pour tout i, j , (1 + ε)` ≤ rij , et v, (6)yij`v ≥ 0, pour tout i, j , `, et v, (7)

CLPj ≥ 0, pour tout j. (8)

72/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesUn algorithme probabiliste : LP Rounding

Résoudre le PL et retourner une solution optimale Y ,

Jj

Jj

(1 + ε)`−2 (1 + ε)`−1 (1 + ε)` (1 + ε)`+1

I`−1 I` I`+1

Jj

73/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesUn algorithme probabiliste : LP Rounding

Affecter chaque tâche Jj à un triplet (i , I`, v) en utilisant lesprobabilités yij`v |I`|

pijv. Poser tj = max{rij , (1+ ε)`−1},

Jj

Jj

(1 + ε)`−2 (1 + ε)`−1 (1 + ε)` (1 + ε)`+1

I`−1 I` I`+1

Jj

74/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesUn algorithme probabiliste : LP Rounding

Ordonnancer les tâches, attribuées à chaque machine, le plustôt possible sans préemption en suivant l’ordre croissant des tj .

Jj

Jj

(1 + ε)`−2 (1 + ε)`−1 (1 + ε)` (1 + ε)`+1

I`−1 I` I`+1

Jj

{Jk; tk ≤ tj} {Jk′ ; tk′ ≥ tj}

75/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesUn algorithme probabiliste : analyse en moyenne

ThéorèmePour tout ε > 0 , l’algorithme LP Rounding construit une solutionréalisable telle que E

[∑wjCj

]≤ 2(1+ ε)OPT (B) et E

[Energie

]≤ B.

. Ces bornes ne sont pas garanties simultanément pour touteinstance du problème.

76/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesUn algorithme probabiliste : analyse en moyenne

ThéorèmePour tout ε > 0 , l’algorithme LP Rounding construit une solutionréalisable telle que E

[∑wjCj

]≤ 2(1+ ε)OPT (B) et E

[Energie

]≤ B.

. Ces bornes ne sont pas garanties simultanément pour touteinstance du problème.

76/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Modèle discret : cas de plusieurs machines hétérogènesUn algorithme probabiliste : analyse probabiliste

ThéorèmeSoit deux réels u,w > 0 tels que 1

u + 1w ≤ 1 et soit un réel ε > 0.

L’algorithme LP Rounding construit un ordonnancement réalisablequi vérifie :

Prob[∑

wjCj < 2u(1+ ε)OPT (B) et Energie < wB]≤ 1− 1

u −1w

. Preuve : Combiner les bornes de l’analyse en moyenne avecl’inégalité de Markov : Prob[X ≥ x ] ≤ E[X ]

x .

77/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Plan

1 Contexte et Motivations

2 Présentation des modèles

3 Ordonnancement sur des machines parallèles avec migration

4 Ordonnancement sur une seule machine

5 Ordonnancement sur des machines hétérogènes

6 Conclusion

78/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Conclusion

Des problèmes de minimisation d’énergie :

Des algorithmes optimaux pour les problèmesS|ri , di , pmtn,mig |E et S1|agreable, pmtn,mixte|E .

Un algorithme approché pour les problèmesRS|ri , discret,E |

∑wjCj et RS|ri , discret|E +

∑wjCj .

79/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

ConclusionPerspectives :

Résoudre les problèmes S|ri , di , pmtn, no-mig ,mixte|E etS|ri , di , pmtn,mig ,mixte|E .

Problèmes dans le modèle mixte avec plusieurs états de veille.

Dérandomisation de l’algorithme probabiliste pour le problèmeRS|ri , discret,E |

∑wjCj .

Dans le modèle discret, utiliser l’approche de l’arrondialéatoire pour des problèmes de minimisation de l’énergie etdes temps de réponse.

80/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Conclusion

Des problèmes classiques :

Algorithme de liste pour le problème d’ordonnancement surdes machines typées avec des temps de communication.

Algorithme de liste basé sur la programmation dynamiquepour le placement de données dans des réseaux pair à pair.

81/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Merci pour votre attention !

82/83 Fadi Kacem IBISC, UEVE

Contexte et MotivationsPrésentation des modèles

Ordonnancement sur des machines parallèles avec migrationOrdonnancement sur une seule machine

Ordonnancement sur des machines hétérogènesConclusion

Adaptation des vitesses : machines parallèles avec migrationOptimalité de l’algorithme SSM : une formulation convexe

min∑Ji∈J

wi vα−1i

wi

vi−∑

Ij : Ji∈Dj

ti,j 6 0 Ji ∈ J (9)

∑Ji∈Dj

ti,j −m · |Ij | 6 0 1 6 j 6 L (10)

∑Ji∈Dj

ti,j − |Dj | · |Ij | 6 0 1 6 j 6 L (11)

ti,j − |Ij | 6 0 1 6 j 6 L, Ji ∈ Dj (12)−ti,j 6 0 1 6 j 6 L, Ji ∈ Dj (13)−vi 6 0 Ji ∈ J (14)

83/83 Fadi Kacem IBISC, UEVE

Recommended