Performance des algorithmes à véracité garantie pour l'ordonnancement de tâches individualistes

F. Pascual - Laboratoire d’Informatique de GrenobleEn collaboration avec : G. Christodoulou, L. Gourvès, E. Koutsoupias E. Angel, E. Bampis, A. Tchetgnia

2SOGEA - 16/02/2007

Ordonnancement P||Cmax

m machines identiques n tâches toute tâche i a - une longueur li

- un numéro d’identification

Objectif : minimiser le makespan (la plus grande date de fin)

M2 M2

M1 M1

3SOGEA - 16/02/2007

Algorithmes d’approximation

SPT (Shortest Processing Time first)

2-1/m approché LPT (Largest Processing Time first)

4/3-1/(3m) approché Schéma d’approximation

4SOGEA - 16/02/2007

Ordonnancement de tâches individualistes

Chaque tâche i est contrôlée par un agent qui seul connaît li (tâche ≡ agent)

Les tâches communiquent leur longueur à un protocole qui doit les ordonnancer de sorte à minimiser le makespan

5SOGEA - 16/02/2007

Stratégies des agents

L’algorithme d’ordonnancement est connu. Le but de chaque tâche est de minimiser

sa date de fin d’exécution. Chaque tâche i déclare une valeur bi

représentant sa longueur. Hyp : bi ≥ li (exécution incomplète si bi<li)

li

bi

6SOGEA - 16/02/2007

Un exemple Le protocole utilise l’algorithme LPT 3 tâches de longueurs {2,1,1}, 2 machines

La tâche rouge a intérêt à mentir sur sa longueur afin de minimiser sa date de fin d’exécution.

7SOGEA - 16/02/2007

Algorithmes à véracité garantie

Algorithme à véracité garantie : algorithme avec lequel les tâches ne peuvent pas diminuer leur date de fin en mentant sur leur longueur.

8SOGEA - 16/02/2007

Retour sur l’exemple

Le protocole utilise l’algorithme SPT

C’est un algorithme déterministe, à véracité garantie et 2-1/m approché. [Christodoulou et al. ICALP’04]

9SOGEA - 16/02/2007

Objectif

Borner la performance d’un protocole (algorithme) à véracité garantie

Pas de paiements

10SOGEA - 16/02/2007

Autres travaux en ordonnancement

Algorithmes à véracité garantie : économie Paiement des agents Ordonnancement :

Les agents sont les tâches : veulent minimiser la charge de leurs machines [Auletta et al, SPAA’04]

Les agents sont les machinesMécanisme de coordination [Christodoulou et al,

ICALP’04]

11SOGEA - 16/02/2007

Objectif

Borner la performance d’un protocole (algorithme) à véracité garantie dans divers contextesDéterministe ou randomiséModèle d’exécution fort ou souple

12SOGEA - 16/02/2007

Modèles d’exécution Modèle fort

Une tâche i ayant déclaré bi obtiendra son résultat li unités de temps après le début de son exécution.

Modèle souple Une tâche i ayant déclaré bi obtiendra son

résultat bi unités de temps après le début de son exécution.

li = 2

bi = 3

13SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2-1/m *

Souple

* [Christodoulou, Nanavati, Koutsoupias, ICALP 2004]

14SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort ? 2-1/m *

Souple

* [Christodoulou, Nanavati, Koutsoupias, ICALP 2004]

15SOGEA - 16/02/2007

Modèle fort, algorithme déterministe, borne inférieure (1/2)

m machines m(m-1)+1 tâches de longueur 1

Au moins une tâche t se termine à la date m.

Hyp : Algorithme déterministe et de rapport d’approximation < 2-1/m .

1M1

M2

M3

1 1

1 1

1 1

16SOGEA - 16/02/2007

Modèle fort, algorithme déterministe, borne inférieure (2/2) la tâche t déclare 1 : 1 1 1

1 1

1 1

3

11 1

1 1 1

fin(t) ≥ 3

début(t) < 2, fin(t) < 3OPT = 3

3

Makespan < (2-1/m) OPT = 5

Ordonnancement optimal Ordonnancement (2-1/m-ε)-approché

La tâche t a intérêt à déclarer m plutôt que 1 :

17SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m)

Souple

18SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m) ?

Souple

19SOGEA - 16/02/2007

Modèle fort, algorithme randomisé

Idée : combiner : - un algorithme avec véracité garantie- un algorithme pas à véracité garantie mais avec un meilleur

rapport d’approximation.

Exemple : algorithme SPT-LPT- avec une probabilité p : retourner un ordonnancement SPT- avec une probabilité (1-p) : retourner un ordonnancement

. LPT

20SOGEA - 16/02/2007

SPT-LPT n’est pas à véracité garantie.

On a trois tâches : , ,

- La tâche 1 déclare sa vraie longueur : 1

- La tâche 1 déclare une fausse valeur : 2.5

123

12

3 32 1SPT : LPT :

E[C1] = p + 3(1-p) = 3 - 2p

2.52 3SPT :

LPT : 32.5 2

E[C1] = 1

Modèle fort, algorithme randomisé

J’ai intérêt à déclarer 2.5 plutôt que 1

21SOGEA - 16/02/2007

Algorithme DSPT

Ordonnancer les tâches t.q. b1 < b2 < … < bn.

La tâche i+1 commence quand 1/m de la tâche i a été exécuté.

Exemple : (m=3)

0 1 2 3 4 5 6 7 8 9 10 11 12

1

2

3

5

6

7

8

9

4

22SOGEA - 16/02/2007

Algorithme DSPT

Propriété : DSPT est (2-1/m)-approché Idée de la preuve :

0 1 2 3 4 5 6 7 8 9 10 11 12

1

2

3

5

6

7

8

9

4

Temps d’inactivité :inactivite_avant(i) = ∑ (1/3 lj)inactivite_milieu(i) = 1/3 ( li-3 + li-2 + li-1 ) – li-3inactivite_fin(i) = li+1 – 2/3 li + inactivite_fin(i+1)

23SOGEA - 16/02/2007

Algorithme DSPT

Propriété : DSPT est (2-1/m)-approché Idée de la preuve :

0 1 2 3 4 5 6 7 8 9 10 11 12

1

2

3

5

6

7

8

9

4

Cmax

Cmax = (∑(idle times) + ∑(li)) / m ∑(idle times) ≤ (m-1) ln and ln ≤ OPT Cmax ≤ ( 2 – 1/m ) OPT

24SOGEA - 16/02/2007

Un algorithme à véracité garantie

Algorithme DSPT-LPT :- Avec une probabilité m/(m+1), retourner DSPT- Avec une probabilité 1/(m+1), retourner LPT.

Le rapport d’approximation de DSPT-LPT est inférieur à celui de SPT. si m=2, rapport(SPT-LPT) < 1.39, rapport(SPT)=1.5

Propriété : DSPT-LPT is à véracité garantie.

25SOGEA - 16/02/2007

DSPT-LPT est à véracité garantie.

On a trois tâches : , ,

- La tâche 1 déclare sa vraie longueur : 1

- La tâche 1 déclare une fausse valeur : 2.5

123

12

3 32 1DSPT : LPT :

E[C1] = 5/3

3DSPT :

LPT : 32.5 2

E[C1] = 5/3

Un algorithme à véracité garantie

Je n’ai pas intérêt à mentir.

22.5

26SOGEA - 16/02/2007

Un algorithme à véracité garantie

Propriété : DSPT-LPT est à véracité garantie.

Idée de la preuve : Supposons que i déclare b>li. Elle est maintenant plus grande

que les tâches 1,…, x, plus petite que la tâche x+1.

l1 < … < li < li+1 < … < lx < b < lx+1 < … < ln

LPT : diminution de Ci(lpt) ≤ (li+1 + … + lx) DSPT : augmentation de Ci(dspt) = 1/m (li+1 + … + lx) DSPT-LPT:

changement = - m/(m+1) Ci(lpt) + 1/(m+1) Ci(dspt) ≥ 0

b <

27SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m) 2-(5/3+1/(3m))/(m+1)

Souple ?

28SOGEA - 16/02/2007

Un algorithme déterministe pour le modèle souple Idée : bénéficier de l’avantage de LPT

(son rapport d’approx) mais pas de son inconvénient (les tâches mentent pour être exécutées en premier)

Construire un ordonnancement LPT puis l’exécuter en sens opposé, i.e. du makespan (Cmax) à la date 0

29SOGEA - 16/02/2007

LPT mirror

Toute tâche t se commençant en d(t) dans LPT se termine à la date Cmax - d(t) dans LPT mirror.

Si t déclare une valeur plus grande que sa longueur réelle alors Cmax ne peut qu’augmenter tandis que d(t) ne peut que diminuer.

LPT mirror est à véracité garantie et 4/3 – 1/(3m) approché.

30SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m) 2-(5/3+1/(3m))/(m+1)

Souplem=2: ρ≥1.1

m≥3: 7/64/3-1/(3m)

31SOGEA - 16/02/2007

Block : un algorithme randomisé pour le modèle souple

Ordonnancer les tâches de façon optimale. Makespan = OPT; Sommes des longueurs sur Mi = Li.

Ajouter une tâche fictive de longueur OPT-Li sur Mi.

Sur chaque machine, ordonnancer les tâches dans un ordre aléatoire.

9 9

10

9

3 5

2 4 3

M1

M2

M3

32SOGEA - 16/02/2007

Block : un algorithme randomisé pour le modèle souple

Lemme : Soit un ensemble de tâches à ordonnancer selon un ordre aléatoire. E[ fin de i ] = li + ½ ( lj)= ½ (( lj) + li)

Block est à véracité garantie.

- i déclare li : Makespan= OPTli.

E[ fin de i ] = ½ (OPTli + li)

- i déclare bi>li : Makespan= OPTbi ≥ OPTli.

E[ fin de i ] = ½ (OPTbi + bi)

i j

33SOGEA - 16/02/2007

Bornes pour un système centralisé

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m) 2-(5/3+1/(3m))/(m+1)

Souplem=2: ρ≥1.1

m≥3: 7/64/3-1/(3m) 1 1

34SOGEA - 16/02/2007

Système distribué

Les tâches décident sur quelle machine elles vont être exécutées.

La stratégie de la tâche i est (bi,mi) Chaque machine j a un algorithme local

d’ordonnancement. Cet algorithme ne dépend que des tâches ayant choisi j : mécanisme de coordination [Christodoulou et al. ICALP’04]

35SOGEA - 16/02/2007

Prix de l’anarchie Équilibre de Nash : Situation dans laquelle

aucune tâche ne peut se terminer plus tôt en changeant unilatéralement de stratégie.

Prix de l’Anarchie = max {MakÉq. Nash / MakOPT}

Objectif : borner le prix de l’anarchie pour les mécanismes de coordination à véracité garantie.

36SOGEA - 16/02/2007

Bornes pour un système distribué

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m) 2-1/m

Souple?

2-1/m 2-1/m

37SOGEA - 16/02/2007

Modèle souple, mécanisme de coordination déterministe, borne inf

ρ < (2+ε)/2 et ρ ≥ 2/(1+ε)

→ ρ ≥(1+√17)/4 > 1.28

M1

M1 M1

M1

M2 M2

M2 M2

38SOGEA - 16/02/2007

Bornes pour un système distribué

Déterministe Randomisé

inf. sup. inf. sup.

Fort 2–1/m 2-1/m 3/2-1/(2m) 2-1/m

Souple (1+√17)/4 > 1.28 2-1/m 1+(√13-3)/4>1.15 2-1/m

39SOGEA - 16/02/2007

Perspectives

Réduire les écarts entre bornes sup et inf Mécanismes de coordination avec véracité

garantie Agents contrôlant plusieurs tâches Machines avec vitesses