1 - IDL

Report
Ordonnancement temps réel
orienté consommation
Jean-Philippe Diguet
LAB-STICC
CNRS / UBS / UBO / Telecom Bretagne
En avec collaboration de Cécile Belleudy Univ. Nice
ETR, Brest, Sep. 2011
Plan
1.
2.
Introduction
DVFS
2.1 Monoprocesseur
2.2 Multiprocesseur
3.
DPM
3.1 Généralités (Mémoires, I/O, processeurs)
3.2 Contexte non temps réel
3.3 Contexte temps réel
4.
Conclusion
2
1-Problématique
• Consommation des systèmes embarqués, plusieurs aspects …
 Batterie : Durée de vie et Volume
 Production: Electronique ambiante (Maison, Voiture, Capteurs, IT ..): GW !
Consommation équipement portables ITRS’08
Densité énergétique (EpoSS 2009)
3
1-Problématique
 Production Energie : produits de masse
• 5.109 abonnements mobile atteint en 2010 selon l’ITU
• Somavat et al. [21]: ICT: 6% de la consommation totale
d’électricité mais part plus importante dans pays à forte
croissance (Inde, Chine, Brésil …)
 Fiabilité :
• Dégradation durée de vie: exponentielle avec
Température
• Dilatation non homogène
4
1-Problématique
• Modèles de consommation
 P = Pstatique + Pdynamique
 Pdynamique ♯ C1.Vdd2.F
; Pstatique ♯ Vdd . Ileak
 Ileak♯ (W/L).exp(-Vth/T)
 Changement de Vdd
Pstatique : Gain en V1/V2 ;
Estatique : (V1/V2) / (f1/f2) (?)
Pdynamique : Gain en (V1/V2)2 . (f1/f2)
Edynamique : Gain (V1/V2)2
 Adaptation Vth : VTCMOS: Vth variable via adaptive body bias VBS
•
Ex. Processor Crusoe 70nm
- Vdd=1V, Vbs = 0V => E =93.5μJ
- Vdd=0.85, Vbs = 0V => E = 73.8μJ,
- Vdd=1V, Vbs =-0.66V => E =50.6μJ
5
1-Problématique
• Optimisation à plusieurs niveaux ?
 Du niveau Système : OS
 Application: localité des données (réduction des accès off-chip)
 Architecture : parallélisme, pipeline, mémoire (multi-bancs, hiérarchie)
 Logique : clock gating, multi-VDD, multi-Vth
 Technologique : VTCMOS, dimensions W/L adaptées
- Ordonnancement + Temps Réel
- Contrôle (HAL) de l’activité de ressources avec modes faible consommation
6
1-Problématique
ETi
• OS + Temps Réel :
 DFVS:
 a = F’/F
• Respect di
• Réduction pics puissance
• Complexité
• E2=E(F2,Vdd2) +EDVFS
• DVFS 1>2 => E2 < E(F1,Vdd1)
a=1
F = Fmax
WCETi
di
aopt
Fopt
a
F’
 DPM
• Processeurs: couple VDD/F (ex.)
• Mémoire (MRAM : états Active, Standby, Napping, PowerDown, DeepPowerDown,
compromis Tsleep / Psleep)
• Périphériques (ex. radio)
• E2 = E(T2) + EDPM + Elp < E1(T1)
P
ETi
Xscale PXA 270
di
Mem. Rambus
E(T2)
t
7
2.1-DVFS: Monoprocesseur
• Redistribution Intra-Tâche, Sudha et al. [11]
 Décomposer le programme temp-réel en CFG (Control Flow Graph)
 Nœud : basic block (Texec), arc orienté (Probabilité)
 Approche simplifiée par Chemins Fréquents (Hot Paths)
 Choix des couples V/F pour chaque Bi selon parcours Breath First Search:
• Tpc(Bi): Chemin le plus long possible à partir de Bi
• Hpc(Bi): Chemin commun à la moitié des Hots Paths
• F(Bi) = L(Hpc(Bi)) / t_restant – (L(tpc(Bi))-L(Hpc(Bi)))
p1
p2

p3
Sont donc privilégiés les gains associés aux Bi fréquents et communs aux Hot Paths
8
 Sous-optimal lors de passage sur Bi rares.
2.1-DVFS: Monoprocesseur
• Redistribution Intra-Tâche [11]
 Exemple:
• P1, P2, P3: {35%, 30%, 30%}. 10 couples V/F possibles [0.1, 0.2, … ,1]
• Tpc(B1) = {B1,B6,B8}, Hpc(B1)={B1, B3, B8}
• F(B1) = 130 / 200 - (140 - 130) = 0.68 => 0.7
 Généralisable aux graphes plus complexes via des heuristiques (choix) des
combinaisons (graphes série, parallèle, boucles)
 Difficultés:
• Instrumentalisation du code : points de mesure des (WCET restants)
• Choix des granularités (Bi ou Boucle ou CDFG…)
• Overhead du calcul en ligne éventuel
9
2.1-DVFS: Monoprocesseur
• Redistribution Inter-Tâches, DRA-AGR, Aydin et al. [1]
 Hypothèse: Modèle F-V continues, Ti indépendantes, Périodiques, Pi = Di
Modèle quadratique : Pclk ; D = 1/Fmax = k.Vdd/ (Vdd-Vt)2
 3 phases (aussi 3 familles classiques de techniques DVFS):
1)
2)
3)
Calcul hors ligne de la vitesse relative optimale (ie. facteur a) S* (WCET)
Réduction de la vitesse en ligne / Workload réelle
Adaptation spéculative (prédiction / cas moyen)
1- Utot = Σi WCET(i)/ Pi ≤ 1. S* = max{Smin, Utot} en considérant un algorithme
d’ordonnancement temps réel permettant une utilisation de 100% (ex. EDF)
S =1
C=WCET P=D
S =S*
C*
D
10
2.1-DVFS: Monoprocesseur
2- Dynamic Reclaiming Algorithm (DRA) [1]
 En pratique le WCET est rarement atteint: U< 1 => utiliser cette marge pour réduire S
 Ordonnancement EDF* (EDF + priorité par date d’arrivée pour les tâches de même deadline)
 Remij(t) : temps exécution restant à t en conditions 1) (EDF,WCET, S*)
 wxS(t) : temps d’exécution pire cas restant à t avec vitesse S et ordonnancement courant
 Création de
aqueue <=> Liste Tâches prêtes avec S=S* et ordo. EDF* : { rij(t), dij(t), Remij(t) }
mise à jour à chaque événement => calcul du gain (earliness) / ordo statique :
Speed: S*, Utot=1
T1
T12
T11
C1=4
D1=10
T2
Earliness Tâche x :
T13
ex= Si | di*≤dx* rem (t) – w
i
x
Sx(t)
Algorithme: à chaque événement :
- wxSx = wxSx – Δt (temps activation Tx)
- réévaluation de la vitesse S <= S’ telle Tx soit
ralentie de Y slots de temps supplémentaires:
S’ = S . wxSx / (wxSx + Y)
C2=4 D2=10
T3
Y≤
ex
C3=6 D3=30
11
2.1-DVFS: Monoprocesseur
•
One-Task Extension technique [14]: applicable à toute technique d’ordo.

Applicable lorsqu’une seule tâche présente dans la liste des tâches prêtes et
WCET < date arrivée d’une prochaine tâche (NTA).

Principe: Z = NTA – t – ωxSx(t) => Sx’ = Sx . wxSx / (wxSx + Z)
T1: C1=100,P1=200
T1: C1=100,P1=200
T2 : C2=300,P2=600
T2 : C2=300,P2=600
0
100
200 300
400
500 600
0
100
200 300
400
500 600
12
2.1-DVFS: Monoprocesseur
3- Aggressive Speed Reduction [1]
 Principe: réduire S non plus par rapport au pire cas mais d’un WCET moyen ET garantir le
temps réel par (re)augmentation de la vitesse pour les tâches suivantes si le pire cas est
finalement obtenu.
Conclusion
 Théoriquement correct mais suppose des tâches périodiques, un couple F-Vdd continue
(irréaliste mais adaptable) et ignore la consommation statique : non recours au DPM
13
2.1-DVFS: Monoprocesseur
•
Redistribution Inter-Tâches, Feedback EDF, Dudani al. [6]
Scaling factor : α = Si / Smax = Fi / Fmax
 Principe: EDF + DVFS pour la tâche courante Tk individuellement exploitant le gain de
temps gagné (Slack time) sur les exécutions de tâches précédentes :


α-1.Ck/Pk + Σi\k Ci / Pi < 1

Slack Passing (sk):
Ci (WCET EDF schedule)
Ti

Task splitting: Tk = TA + TB
Tâche ralentie (a)



t2
t3
t4
t5
t6
t7
Slack hérité par Ti
t8
t9
t10
t11
Slack Produite par Ti
Objectif: Tk=TA => feedback CA = Cavg (observations exécutions précédentes)
Ck=CA+ CB ; CA/a + CB = Ck+sk => a = Cavg / (Cavg+ Sk) (+ condition deadline à vérifier)
Si Ck > Cavg => CB ≠ 0 : overhead à prendre en compte pour activation Fmax mais
Fréquence Discrètes => aréel ≥ a
14
2.1-DVFS: Monoprocesseur
•
Redistribution Inter-Tâches, Feedback EDF, Dudani al. [6]
Résultats simulation:
- 4 couples F-Vdd
- 3 tâches
- Taux utilisation 80%
- Look-ahead EDF : ralentissement
identique pour toutes les tâches.
Conclusion
 Approche simple et pragmatique
 Questions: choix de Cavg ? Overhead en cas d’accélération (CB) ?
15
2.2-DVFS: Multiprocesseurs
•
Approche encore peu utilisée en pratique
1) Approche Partitioning puis uniprocesseur DVFS
2) Global Scheduling + DVFS
 Complexité NP difficile pour DVFS + Partitioning  MCKP
•
Architecture homogène et hétérogènes
16
2.2-DVFS: Multiprocesseurs
•
Partitionning + DVFS / Architectures Homogènes Aydin et al. [2]

Principe:
Ti
1
Task ordering
(Ui décroissant)
Reservation
Heuristique
2
Tâches périodiques
{Ti,Ri,Di,Pi}

Partitionnement: 1) si taches connues
2) si arrivées de tâches aléatoires
Reservation = heuristique entre Best-Fit
(Faisabilité) et Worst Fit (Energie)
E(Mi) = Σj g(S) . P/Pj . Ci/S
-
P hyperpériode : PPCM{ Pi}
g(S): puissance=a.V3+bV2+c

Avec DVFS : E(Mi) = P.g(Ui)

Objectif : Min

Pb: solution V-F continues
-
Worst Fit
partitioning
EDF+DVFS
P1
EDF+DVFS
P2
EDF+DVFS
P3
EDF+DVFS
P4
Ordonnancement EDF
+ DVFS: S* = max{Smin, Ui}
(cf DVFS monoproc)
Nb de solutions faisables/ Energie
16 processeurs, taux utilisation par tâche max = 50%
Modèle puissance: g(S) = x2
{ Σj P.g(Ui) }
17
2.2-DVFS: Multiprocesseurs
•
EDF global + DVFS / Architectures Homogènes Bhatti [3]


3 phases
1) EDF et Dynamic Slack Reservation (DSR)
Ti
EDF
Tâches périodiques
{Ti,Ri,Di,Pi}
Ordo Canonique Sscan
Priorité EDF, M plus élevés
assignées aux M processeurs
DSR (S1)
P1
DSR (S2)
P2
DSR (S3)
P3
DSR (S4)
P4
MaJ Slack: e= Ci-1,j – AETi-1,j (actual exec time)
Tdispo = Cij + e
Scaling factor: a =
Tdispo / Ci,j
Adaptation S*= F(a)
Exécution Cij
✪ Exige un Ordonnancement canonique préalable (Cij)
Contrairement au cas 1 proc, impossible de suivre un Ordo. précalculé (migration tâche globale + taille mémoire)
Online Sscan : Répéter pour les M prochaines tâches sous l’hypothèse de WCET:
a) Calcul priorité des tâches prêtes ou en attente (sélection Ti)
b) Calcul de la plus proche date de fin d’exécution de les M processeurs (sélection Mj)
c) Calcul de Cij pour Ti sur Mj sous hypothèse WCET
2.2-DVFS: Multiprocesseurs
•
EDF global + DVFS / Architectures Homogènes Bhatti [3]

2) Online Speculation Algorithm
• Cas particulier des préemptions (tâche de plus haute priorité passe de bloquée à
active sur Pk). DSR impose Smax car Ci-1,j inconnu (Ti-1 interrompue)
• Calcul d’un Cij avg uniquement pour les Tâches Soft real-time.
 3) m-Task Extension
• Extension de la technique One-task
• Si Nb tâches prêtes ≤ M : Texec peut être étendu jusqu’à t= minTâches en attente{Ri}
Simulations pour
exemple H264
3.1-DPM: Généralités
•
•
•
•
•
•
DVFS ne prend pas en compte la consommation statique => DPM
But: Modes très faible consommation pour éléments non utilisés
Contraintes: Passage via des états Idle avant et après le mode Sleep
Condition: Eon>off+Eoff>on< Esleep soit Tsleep > (Pon>off.Ton>off+Toff>on.Poff>on)/Psleep
Hétérogénéités des composants: I/O, Mémoires, Périphériques, Processeurs
Nombreux travaux mais peu en contexte temps réel.


Si Didle j> Dminj alors Pj passe en mode faible consommation, Dminj est l’enjeu des
méthodes existantes:
Trop faible: pas de gain (Tidle < Tsleep)
Trop élevé:
opportunités manquées.
Statique, Adaptatives (plusieurs timeout testés et évalués), stochastiques (Chaînes de
Markov => probabilités de succès)
3.2-DPM: temps réel
•
Approche orientée I/O, MDO, Vishnu et al. [17]
EDS: méthode exacte  Branch Bound qui maximise SDi pour pour chaque I/O k
•
I/O Device k
Ti
Ti+1
Ti+2
•
•
Di
Di+1
Tâches non préemptibles, Complexité => Hors ligne, Borne inférieure
MDO : EDF puis heuristique (algo. glouton): maximiser Sdi où di =1 si Di>Tsleep ; 0 sinon
• Tâches préemptibles, Texec MDO < 1s,
• Emdo-EEDS / EEDS < 3%.
• Difficilement applicable en ligne.
3.2-DPM: adaptatif temps réel
Approche conjointe I/O + processeurs, Sys-EDF, Cheng et al. [5]
• Monoprocesseur : DVFS (Dual Speed Dynamic Reclaiming, Zhang [21])
• I/O: DPM (CEA-EDF)
• Prise en compte d’I/O non préemptibles
• Efficacité Energétique hors ligne => vitesse optimale Sopt
• Modèle Energie (composant λk)
-9
Eλk =
PakTak+PikTik+EaikNaik
+
EiakNiak
3
x 10
Mobile RAM
Mobile RAM+SimpleTech flash
Mobile RAM+MaxStream wireless module
2.5
Energy efficiency scale
•
Efficacité énergétique (MIPS/W) en
fonction de:
- Composants actifs
- Vitesse Processeur
(offline)
2
1.5
1
0.5
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Normalized processor speed
0.8
0.9
1
3.2-DPM: adaptatif temps réel
•
Approche conjointe I/O + processeurs, Sys-EDF, Cheng et al. [5]
• CEA-EDF :
λk off si t-Min(Ri(λk)) > Tsleep(λk)
•
-
DSDR :
Calcul hors ligne des vitesses min/max (H, L)
k
n
Ci Bk
Ci
k,1  k  n,Hk   
L


Pk
i1 Pi
P
i1 i
Mean energy saving under different system utilizations
H  max(Hk ) Bk  max(BlocageTk )
0.8
CEA-EDF
SYS-EDF
DS+CEA-EDF
DS
0.7

Calcul vitesse optimale / ressources actives:
S = Sopt (λk) 
DS:
S=H si λk bloqué, sinon L
DR:
Exploitation en ligne des marges (WCET, Blocage)
Si = CiH/L / ( CiH/L + RiF) ou RiF=temps gagné accumulé
0.6
-
Normilized Energy Saving
0.5
0.4
0.3
0.2
0.1
0
0-0.1
0.1-0.2
0.2-0.3
0.3-0.4
0.4-0.5
0.5-0.6
System utilization
0.6-0.7
0.7-0.8
0.8-0.9
0.9-1
3.2-DPM: adaptatif temps réel
•
Cible: multiprocesseurs homogènes, AsDPM, Batthi [3]
• Principe : Contrôler la liste des tâches prêtes de manière à collecter et migrer le
« idle time » de k processeurs actifs vers M-k processeurs inactifs pour optimiser les
opportunités de DPM. Allouer le minimum de Proc. nécessaire.
•
Technique : Defered Task Queue (DeTQ) permet d’étendre virtuellement le moment
où la tâche Ti est prête. Possible sans compromettre le respect des contraintes TR si
Laxity Bottom Test ≥ 0 pour au moins un processeur j. Sinon, allouer un autre Proc.
Ti
Re
TQ
TQ
Laxity
Bottom test
De
TQ
[Pi]
EDF
P1
Ru
TQ
EDF
P2
Ru
TQ
EDF
P3
Ru
TQ
EDF
P4
Mode faible consommation
Tâches périodiques
{Ti,Ri,Di,Pi}
Pour tout événement (terminé, prêt, préemption) et proc. j,
calculer Laxité anticipée li et test LBT: li≥0
li = di –( t + max(Cjrem,Toff>on) + Cirem + SDETQ(j) Ckrem )
Ordonnancement EDF
+ décision On/Off
WCET restant pour Tâches de plus haute
priorité virtuellement affectées à P k
WCET restant pour Tâche i
Temps Retour Actif
WCET restant pour Tâche Courante sur Pj
Ru
TQ
3.2-DPM: adaptatif temps réel
•
Cible: multiprocesseurs homogènes, AsDPM, Batthi [3]
Ex. Allongement Tidle de Proc. 2
•
H264 simulations sur STORM [3]
Conclusion : Approche complète, mais complexité du Global EDF si Nb processeurs
important, question de l’équilibre thermique.
Conclusion
• Des solutions existent pour associer Temps Réel et Optimisation
de la consommation
• Les gains en DVFS se réduisent avec la technologie (Vth, Vdd )
• Evolution nécessaire vers les processeurs hétérogènes
(complexité accrue) et éventuellement adaptatifs.
• Incertitude grandissante sur Texec: un sérieux handicap
• Travaux en cours : température (distribution), problème
WCET/Cache (politiques de cache adaptatives, …)
26
Biblio
[1] H. Aydin, R. Melhem, D. Mosse, and P. Mejia-Alvarez. Power- aware scheduling for periodic real-time tasks. Computers,
IEEE Transactions on, 53(5) :584 – 600, may 2004.
[2] H. Aydin and Qi Yang. Energy-aware partitioning for multiprocessor real-time systems.Int. Parallel and Distributed
Processing Symposium, 2003.
[3] M. Khurram Bhatti. Energy-aware Scheduling for Multiprocessor Real-time Systems. PhD thesis, University of Nice,
Sophia-Antipolis, France, march 2011
[5] H. Cheng and S. Goddard. Sys-EDF: a system-wide energy-efficient scheduling algorithm for hard real-time systems.
IJES, 4(2) :141–151, 2009.
[6] A. Dudani, F.Mueller, and Y.Zhu. Energy-conserving feedback edf scheduling for embedded systems with real-time
constraints. SIGPLAN Not., 37 :213–222, June 2002.
[11] G. Sudha Anil Kumar and G. Manimaran. An intra-task dvs algorithm exploiting program path locality for real-time
embedded systems. In High Performance Computing (HIPC), Lectures Notes in Computer Science, Volume 3769/2005
, pp 225–234, 2005.
[14] Y. Shin and K. Choi. Power conscious fixed priority scheduling for hard real-time systems. In Design Automation
Conference, 1999. Proceedings. 36th, pages 134 – 139, 1999.
[17] V. Swaminathan and K. Chakrabarty. Pruning- based, energy-optimal, deterministic i/o device scheduling for hard realtime systems. ACM Trans. Embed. Comput. Syst., 4 :141–167, Feb. 2005
[21] F. Zhang, S. Chanson, Processor Voltage Scheduling for Real-Time Tasks with Non-Preemptible Sections, IEEE RealTime Systems Symp., 2002.
[22] P. Somavat, S. Jadhav and V. Namboodiri, Accounting for the energy consumption of personal computing including
portable devices, 1st Int. Conf. on Energy-Efficient Computing and Networking (e-Energy), NY, USA, 2010
27

similar documents