Ordonnancement de tâches dans un milieu hétérogène

Dr. Yosr SLAMA

2020-2021

Introduction

 Contexte : L'ordonnancement de tâches indépendantes

en milieu hétérogène (OTIMHTR) est applicable pour un ordonnancement par niveau sans chevauchement dans le cas d'un graphe de tâches.

 Hypothèses : on dispose d’un ensemble de n tâches

indépendantes tj de coûts respectifs cj (j=1..n) à ordonnancer sur p processeurs de vitesses respectives v1, v2, … vp

 Objectif : Equilibrage de charge ➔ Minimiser le

makespan

2

Métriques

 La charge pondérée d’un processeur Pi (notée CHPi) est

définie par la somme des coûts des tâches allouées à Pi divisée par sa vitesse vi

CHPi= Somme cj (cj : coût des tâches tj affectées à i) / vi

 Lorsque toutes les tâches seront allouées aux processeurs,

le makespan M(p) sera alors le maximum des charges pondérées des différents processeurs

M(p)= max(CHPi) (i=1..p)

3

Principes

On présente différentes méthodes d’ordonnancement basées principalement sur les deux principes suivants :

 Principe 1 : On affecte la tâche courante au processeur

dont la charge pondérée (CHP) est la plus faible.

Remarque : Si deux processeurs ont la même CHP, on choisira le plus rapide

 Principe 2 : On affecte la tâche courante au processeur

qui la terminera le plus vite (on comparera les CHP des processeurs si on leur affecte la tâche courante)

4

Algorithmes :

On présente 3 algorithmes itératifs (1 étape = allocation d’une tâche sur un processeur qu’on choisira):

 LS ‘List Scheduling’ (tâches prises dans l'ordre 1...n),

 SPT ‘Shortest Precessing Time’ (tâches triées par coût croissant)

 LPT ‘Longest Precessing Time’ (tâches triées par coût décroissant)

 Chacun de ces 3 algorithmes a une version1 et une version 2 selon le principe appliqué.

 On aura donc 6 versions d’algorithmes :

LS-1 SPT-1 LPT-1

LS-2 SPT-2 LPT-2

5

LS-1, SPT-1 et LPT-1

 n=8 de coûts 4, 6, 3,10, 7, 3, 8, 3. p=2 v1=1 et v2 =1/2

6

 LS-1 4, 6, 3,10, 7, 3, 8, 3

M(2)=32

 SPT-1 3, 3, 3, 4, 6, 7, 8, 10

M(2)=38

 Pour placer la tâche de coût 4,

on a le même CHP=6 donc on choisit

le processeur le plus rapide : P1

 LPT-1 10, 8, 7, 6, 4, 3, 3, 3

M(2)=30

LPT-1 est le meilleur

P1	4	3	10	3	8
CHP1	4	7	17	20	28
P2	6	7	3
CHP2	12	26	32

P1	3	3	4	7	8
CHP1	3	6	10	17	25
P2	3	6	10
CHP2	6	18	38

P1	10	7	4	3	3	3
CHP1	10	17	21	24	27	30
P2	8	6
CHP2	16	28

Heuristique d’amélioration

7

 Il existe une heuristique d’amélioration basée sur le transfert d’une tâche d’un processeur à un autre.

 Exemple pour SPT-1

On peut transférer la tâche

de coût 3 de P2 vers P1

 M(2) qui était égal à 38

devient : M’(2)=38-6=32

P1	3	3	4	7	8
CHP1	3	6	10	17	25
P2	3	6	10
CHP2	6	18	38

P1	3	3	4	7	8	3
CHP1	3	6	10	17	25	28
P2	X	6	10
CHP2	X	12	32

 On calcule d=max CHP- min CHP (ici 38-25 =13) et on choisit une tâche ti à transférer du processeur le plus chargé au processeur le moins chargé permettant de minimiser d

LS-2, SPT-2 et LPT-2

 n=8 de coûts 4, 6, 3,10, 7, 3, 8, 3. p=2 v1=1 et v2 =1/2

8

 LS-2 4, 6, 3,10, 7, 3, 8, 3

M(2)=31

LS-2 Meilleur que LS-1

 SPT-2 3, 3, 3, 4, 6, 7, 8, 10

M(2)=34

SPT-2 Meilleur que SPT-1

 LPT-2 10, 8, 7, 6, 4, 3, 3, 3

M(2)=30

LPT-2 aussi performant que LPT-1

(meilleur équilibrage de charge)

P1	3	3	4	6	8	10
CHP1	3	6	10	16	24	34
P2	3	7
CHP2	6	20

P1	4	6	10	3	8
CHP1	4	10	20	23	31
P2	3	7	3
CHP2	6	20	26

P1	10	7	6	3	3
CHP1	10	17	23	26	29
P2	8	4	3
CHP2	16	24	30

Comparaison

 LS-2 Meilleur que LS-1

 SPT-2 Meilleur que SPT-1

 Même makespan pour LPT-2 et LPT-1 mais LPT-2 offre un meilleur

équilibrage de charge

Donc le principe 2 est plus pertinent que le principe 1 pour le cas des ordonnancements hétérogènes

car il permet quand il faut d’éliminer le processeur le plus faible ou les processeurs les plus faibles au début ou au milieu de l’ordonnancement

Exemple : p=2 P1 v1=1 et P2 v2=1/5 ; n=2 c1=10 c2=5

 Si on affecte la tâche c1 à P1 et c2 à P2,

M(2)=max(CHP1,CHP2)=max(c1/v1,c2/v2)=max(10,25)=25

 Si on affecte les 2 tâches à P1, M(1)=CHP2=(c1+c2)/v1=15

 M(2)>M(1) donc ici le processeur P2 sera éliminé des le début car son

utilisation ralentit l’exécution

9

Généralisation

 Cas p=2 : 2 processeur P1 et P2 tels que v1>v2 et de n tâches de coûts

c1,… cn

 Si on affecte la tâche tq de coût cq=min(ci) à P2 et le reste des tâches à

P1, M(2)= max ((somme (ci)-cq)/v1, cq/v2)

 Si on affecte toutes les tâche à P1 : M(1)= somme (ci)/v1

 Si M(2)>M(1) alors P2 sera éliminé dès le début

 Cas p=3 : 3 proceurs v1>v2>=v3 et n tâches coûts triés c1>=c2…>=cn

 Si on affecte la tâche de coût cn à P3 et de coût c(n-1) à P2 et le reste des

tâches à P1, M(3)= max ((somme (ci)-cn-c(n-1))/v1, c(n-1)/v2,cn/v3)