Quel temps d’exécution pour mon programme - univ-ubs.frlabsticc.univ-ubs.fr/archi2019/cours-christine.pdfpour mon programme dans le pire des cas ? Ecole ARCHI —Lorient —2019

Queltempsd’exécutionpourmonprogrammedanslepiredescas?

EcoleARCHI— Lorient— 2019 ChristineRochange

Unsystèmesoumisàdescontraintestemporelles▪︎ parexemple,surletempsquisépareunévénementdelaréponsedusystème

▪︎ lavaliditédusystèmereposeautantsurlerespectdescontraintesdetemps(deadlines)quesurlacorrectiondurésultatdescalculs

Temps-réel≠rapide▪︎ cequiimporte,c’estd’êtrecapabled’estimer(borner)letempsderéponse

Systèmetemps-réel

2

Exemple:contrôled’unairbag

3

acquisition commandecalcul

capteurs actionneurs

PapaBench (inspiréduprojetPaparazzidel’ENAC)

Autreexemple:contrôled’undrone

4

PapaBench (inspiréduprojetPaparazzidel’ENAC)

5

modemanuelseulement

modeautomatiqueseulement

danslesdeuxmodes

1

2

dépendancededonnées

dépendancedecontrôle

Tx

Tx

Tx

Autreexemple:contrôled’undrone

Autresexemples

6

Ordonnancementtemps-réel

7

Modèledetâche▪︎ périodique,sporadique,apériodique

tempsjobi

reli(releasetime)

reli+1

Ci (tempsd’exécution)

Ri (tempsderéponse)

Di (deadline)

Pi (période)

jobi+1

Objectif▪︎ allouerdesressourcespartagéesauxtâchesdesortequ’ellespuissenttoutesrespecterleurséchéances

Approches▪︎ hors-ligneouen-ligne▪︎ prioritésfixesoudynamiques

□ RateMonotonic,DeadlineMonotonic,Earliest DeadlineFirst▪︎ préemptifoupas▪︎ suruneplateformemulticoeurs,globaloupartitionné

Ordonnancementtemps-réel

8

Chetto etal.Ordonnancementtemps-réel,ISTEWiley,2014

Exemple:EDF(Earliest DeadlineFirst)nonpréemptif

Testd’ordonnançabilité

9

Ci Pi=Di

t1 2 5

t2 2 10

t3 3 20

!𝐶#𝑃#≤ 1

'

#()

avec 1 < 𝑖 ≤ 𝑛 et 𝑃) < 𝐿 ≤ 𝑃#𝐶# +!𝐿 − 1𝑃0

×𝐶0

#2)

0()

≤ 𝐿

Dequoidépendletempsd’exécutiond’unetâche?§ desdonnéesenentrée

§ del’étatinitialduprocesseur

§ desinterférencesavecd’autrestâches

index = 0;while (data_in[index] != 0){

/* processing */} combien

d’itérations ?

if (temperature > T_MAX){/* error processing */

}else{

/* normal processing */}

quelle branche ?

sum = 0;for (i=0 ; i

Worst-CaseExecution Time(WCET)▪︎ valeurmaximalequepeutprendreletempsd’exécution

□ quellesquesoientlesdonnéesenentrée□ quelquesoitl’étatinitialdumatériel□ quellesquesoientlesinterférencesavecd’autrestâches

Tempsd’exécutionpirecas

11

Tempsd’exécutionpirecas

12

nombred’exécutions

tempsd’exécution

WCETréel

WCETestimé

surapproximation

BCET

touslesscénariospossibles

CommentdéterminerleWCET?

13

Mesures

14

#exécutions

tempsd’exécution

WCETréelWCETobservé

Idéedebase▪︎ calculerlaprobabilitéd’unedéfaillancetemporelle(leWCETdépasseunecertainevaleur)

Techniques▪︎ matériel« randomisé »▪︎ analysesstatistiques,théoriedes valeursextrêmes

▪︎ statiqueoudynamique

Analyseprobabiliste

15

tempsd’exécution

prob

abilité

10-610-9

WCET(10-6) WCET(10-9)

F.Cazorlaetal.,Probabilistic Worst-CaseTimingAnalysis:Taxonomy andComprehensive Survey,ACMCSUR52(1),2019

Principegénéral▪︎ graphedeflotdecontrôle(CFG)▪︎ « décoré »paruneséried’analyses▪︎ calculdesWCETs desblocsdebase▪︎ combinaisondecesWCETs pourdéterminerleWCETglobalduprogramme

Analysestatique

16

B

C D

E

A

F

G

H

I

Implicit PathEnumeration Technique(IPET)

17

even = 0;odd = 0;for (i=0 ; i


18

max T=xA.tA + xB.tB+ xC.tC + xD.tD + xE.tE

xA = 1 xA = xABxB = xAB + xEBxB = xBC + xBDxC = xBC xC = xCExD = xBD xD = xDExE = xCE + xDExE = 1 + xEB

xEB ≤ 255; xBC ≤ 0.5 xB;

tA = …; tB = …; tC = …; tD = …; tE = …;

solveurILPmaxT = …xA = 1 xAB = …xB = … xBC = … xBD = …xC = … xCE = …xD = … xDE = …xE = … xEB = …

LiandMalik, PerformanceAnalysis ofEmbeddedSoftwareusing Implicit PathEnumeration,1995

Outilsacadémiques:▪︎ Chronos(Singapour)▪︎ Heptane(Rennes)▪︎ OTAWA(Toulouse)▪︎ SWEET(Mälardalen)

Outilspourl’analysedeWCET

19

Outilscommercialisés:▪︎ aiT

▪︎

20 www.otawa.fr

21 Ballabriga etal.OTAWA:AnOpenToolbox forAdaptiveWCETAnalysis,SEUS2010

Analysetemporelled’unetâcheenisolation

22


23

even = 0;odd = 0;for (i=0 ; i

Exemple

24

int product = 1;int init_val;for (int i=1; i

Exemple

25

uneinstructionlue/décodéeàchaquecycle

lecturedecodage

mul retrait

tampon d’instructions

add/mov/cmp/bxx

ldr/str

1 cycle

5 cycles

5 cycles

lesbranchementssontpréditsnonpris

uneinstructionlancéeàchaquecycle

uneinstructionretiréeàchaquecycle

(dansl’ordreduprogramme)

Commentcalculerletempsd’exécutiond’unblocdebase?

26

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

b1 aprèsb0

b1 aprèsb2

t0-1 =3cycles

t2-1 =4cycles

b0

b1

b2b3

maxT =x0.t0+x1.t1 +x2.t2 +x3.t3

maxT =x0.t0+x0-1.t0-1 +x2-1.t2-1 +x1-2.t1-2 +x1-3.t2-3

F

A

Mu

Me

C

F 0a 0b 0c 0d 0eA 0a 0b 0c 0dMu

Me 0e 0e 0e 0e 0eC 0a 0b 0c 0d 0e

F 0a 0b 0c 0d 0e 1a 1b 1cA 0a 0b 0c 0d 1b 1cMu 1a 1a 1a 1a 1aMe 0e 0e 0e 0e 0eC 0a 0b 0c 0d 0e 1a 1b 1c

F 2a 2b 2cA 2b 2cMu

Me 2a 2a 2a 2a 2aC 2a 2b 2c

F 2a 2b 2c x 1a 1b 1cA 2b 2c 1b 1cMu 1a 1a 1a 1a 1aMe 2a 2a 2a 2a 2aC 2a 2b 2c 1a 1b 1c

t0 =11cycles

▪︎ pipelinescomplexes:superscalaires,ooo,unitésfonctionnellesmultiples,etc.

▪︎ étatinitial/historique:effetslongs

Limites

27

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

b0

b1

b2b3

b1 aprèsb0

F 1a 1b 1c 2a 2b 2cA 1b 1c 2b 2cMu 1a 1a 1a 1a 1aMe 2a 2a 2a 2a 2aC 1a 1b 1c 2a 2b 2c

F 0a 0b 0c 0d 0e 1a 1b 1cA 0a 0b 0c 0d 1b 1cMu 1a 1a 1a 1a 1aMe 0e 0e 0e 0e 0eC 0a 0b 0c 0d 0e 1a 1b 1c

t0-1 =3cyclest0 =11cycles

b2 aprèsb1 t1-2 =3cycles

maxT =x0.t0 +x0-1.t0-1 +x2-1.t2-1 +x1-2.t1-2 +x1-3.t2-3

Effetstemporelslongs

28

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

b0

b1

b2b3

b2 aprèsb1 aprèsb0F 0a 0b 0c 0d 0e 1a 1b 1c 2a 2b 2cA 0a 0b 0c 0d 1b 1c 2b 2cMu 1a 1a 1a 1a 1aMe 0e 0e 0e 0e 0e 2a 2a 2a 2a 2aC 0a 0b 0c 0d 0e 1a 1b 1c 2a 2b 2c

t0-1 =3cyclest0 =11cycles t1-2 =3cycles

t0-1-2 =18cycles

t0-1-2 =t0 +t0-1 +t1-2 =17cycles

😧

calculdel’étatdesortie

calculdel’étatdesortieetdutempsd’exécution

Unethéoried’approximationdelasémantiquedeprogrammes

▪︎ exécutionpartielled’unprogrammepourobtenirdesinformationsquipeuventêtreutiliséespourrépondreàunequestiondonnée

Interprétationabstraite

29

P.Cousot,R.Cousot,Abstractinterpretation:aunified lattice modelforstatic analysisofprogramsbyconstructionorapproximationoffixpoints,POPL,1977

max

tempsd’exécutionpirecas

interprétatio

nab

straite

étatpossible

étatpossible

étatpossible

b0

b1

b2b3

étatabstrait

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

Commentpourrait-onanalyserl’effetdupipelineparinterprétationabstraite?

30

b0

b1

b2

b3

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

F

A

Mu

Me

C

après b0

31

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


32

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


33

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


34

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

F

A

Mu

Me

C

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


35

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2F

A

Mu

Me

C

F

A

Mu

Me

C

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


36

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


37

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


38

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

on a atteintun point fixe !

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


39

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

t1-2 = max(4,4,3) = 4

t0-1-2 = 11 + 3 + 4 = 18

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


40

b0

b1

b2

b3

F

A

Mu

Me

C

F

A

Mu

Me

C

après b0

après b1

F

A

Mu

Me

C

après b2

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

F

A

Mu

Me

C

t2-1 = max(4,4,4) = 4

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]


Uneautreapproche(locale)pourl’analysedepipeline

41

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

F(1a)

F(1b)

F(1c)

F(2a)

F(2b)

F(2c)

Mu(1a)

A(1b)

A(1c)

Me(2a)

A(2a)

A(2c)

C(1a)

C(1b)

C(1c)

C(2a)

C(2b)

C(2c)

0

1

2

3

4

5

1

2

3

4

5

6

6

7

8

9

10

11

t1-2 =3cycles

😕

Etatinitial« paramétré »


42

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

F A MuMe C r0 r1 r2 r3datededémarraged’unnoeud

ei =dépenddelaressource?

chaqueressourceaunedatededisponibilité

di =délaiaprèsquelaressourcesoitdevenuedisponible

Rochange,Sainrat,AContext-Parameterized ModelforStatic Analysis ofExecutionTimes,TransactionsonHiPEAC,Springer,2009

0a

0b

0c

0d

0e

1a

1b

1c

2a

2b

2c

3a

3b

__start: mov r0,#1

mov r1,#0

adr r2,a

adr r3,init_val

ldr r3,[r3]

while: mul r0,r1,r0

cmp r1,#N

bhs end

str r3,[r2],#4

add r1,r1,#1

b while

end: adr r2,product

str r0,[r2]

F A Mu Me C

F(1a) Mu(1a) C(1a)

F(1b) A(1b) C(1b)

F(1c) A(1c) C(1c)

F(2a) Me(2a) C(2a)

F(2b) A(2b) C(2b)

F(2c) A(2c) C(2c)

1 0

00

00

00

00

11

00

00

00

00

16

00

15

00

10

11

00

10

00

00

12

00

00

00

00

13

00

00

00

00

14

00

00

00

00

15

00

00

00

00

11

10

00

00

00

17

11

16

00

11

13

11

00

00

00

15

12

00

00

00

16

13

00

00

00

14

00

00

10

00

18

12

17

00

12

19

13

18

15

13

110

14

19

16

14

111

15

110

17

15

t1-2 =?


44

C(1c)

C(2c)

18

12

17

00

12

111

15

110

17

15

tC(1c) =max(tF+8,tA+2,tMu+7,,tC+2)

F A Mu Me C

tC(2c) =max(tF+11,tA+5,tMu+10,tMe+7,tC+5)

t1-2 ≤4cycles

≤tC +6

tMe ≤tC - 1

tC(2c) - tC(1c) =max(11-8,5-2,10-7,6-2,5-2)

Latencevariable?▪︎ quidépenddelavaleurdesopérandes(ex:multiplication)▪︎ quidépenddel’étatdecertainscomposants

□ exemple:cached’instructionsoudedonnées

Peut-onconsidérerlepirecas?▪︎ lavaleurmaximaledelalatence

Instructionàlatencevariable

45

Risqued’anomalietemporelle…Non!

Lundqvist,Stenström,Timinganomaliesindynamically scheduled microprocessors.RTSS,1999

Reineke etal.,Adefinition andclassificationoftiminganomalies.WorkshoponWCETanalysis,2006

Anomaliestemporelles

46

decodecycle

1

2

3

4

5

ldr r4,[r3]

add r5,r4,r4

add r11,r10,r10

mul r11,r8,r11

mul r19,r1,r2

memory

add

mul

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

memory

add

mul

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

cachehit

cachemiss

Lepirecaslocaln’estpasforcémentlepirecasglobal…

Objectif:classifierlesaccèsaucache▪︎ AlwaysHit,Always Miss▪︎ FirstMiss▪︎ ?(NotClassified)

Analyseducomportementducache

47

lalatenceestconnue

lalatencen’estpasconnue B

C D

E

A

F

G

H

I

Altetal.,Cachebehaviour prediction byabstractinterpretation,SAS1996

Li,Malik,Wolfe,Cachemodeling forreal-timesoftware:beyond direct-mappedinstructioncaches,RTSS1996

Lv etal.,ASurvey onStatic CacheAnalysis forReal-TimeSystems,LITES3(1),2016

Hypothèses(pourlaprésentation)▪︎ cached’instructionsassociatifparensembles▪︎ avecunepolitiquederemplacementLRU

48

MEMOIRE

CACHE

nensembles


Etat(concret)d’unensembleducache

Analyseparinterprétationabstraite▪︎ calculelesétatspossiblesdechaqueensembleenchaquepointduprogramme

▪︎ deuxanalyses:□ MAY:quelsblocsmémoirepeuvent êtredanslecache?□ MUST:… doivent ….?

▪︎ pourchaqueanalyse,ondoitdéfinir:□ cequ’estl’étatabstraitd’unensemble(ACS)□ desfonctionsdemiseàjour(update())etdejonction(join())

49

a c d b

contenudel’ensemble3 1 0 2

âge(LRU) dcba

séquence d’accès : a-b-c-d0123

b0

b1

b2b3


AnalyseMUST▪︎ étatabstraitd’unensemble=bornessupérieuresurlesâgesdesblocsmémoire

50

{ }

{a, b}

{ }

{c}

âge

0

1

2

3

a

b

c

d

b

a

c

d

b

a

e

c

…

abstrait concret

Contenu d’un ensemble


AnalyseMUST▪︎ fonctionupdate()

51

{ }

{a, b}

{}

{c}

âge

0

1

2

3

{e}

{ }

{a, b}

{}

read(e)

{ }

{a, b}

{c}

{d}

âge

0

1

2

3

{c}

{ }

{a, b}

{d}

read(c)

hit

miss?


AnalyseMUST▪︎ fonctionjoin()

52

{ }

{a, b}

{c }

{d}

âge0

1

2

3

{a}

{ }

{c}

{b}

{}

{a}

{c}

{b}

intersection&

âge maximum


AnalyseMAY▪︎ étatabstraitd’unensemble=bornesinférieuressurlesâgesdesblocsmémoire

53

{a,b}

{c,d}

{ }

{e}

âge

0

1

2

3

a

c

b

e

a

b

c

d

b

c

d

a

…

abstrait concret

Contenu d’un ensemble


AnalyseMAY▪︎ fonctionupdate()

54

{a,b }

{c,d}

{ }

{e}

âge

0

1

2

3

{f}

{a,b}

{c,d}

{}

read(f)

{a,b}

{c,d}

{ }

{e}

âge

0

1

2

3

{c}

{a,b }

{d}

{e}

read(c)

hit?

miss


AnalyseMAY▪︎ fonctionjoin()

55

{a,b}

{c,d}

{ }

{e}

âge0

1

2

3

{c}

{f}

{a, b}

{}

{a,b,c}

{d,f}

{}

{e}

union&

âge minimum


AnalyseMAY

56

a

c

{ }{ }

entrée sortieâge 0

âge 1

b

join = union & âge minimum


AnalyseMAY

57

a

c

{ }{ }


âge 1

b

{a}{ }



AnalyseMAY

58

a

c

{ }{ }


âge 1

b

{a}{ }

{a}{ }

{b}{a}



AnalyseMAY

59

a

c

{ }{ }


âge 1

b

{a}{ }

{b}{a}

{c}{b}



{a}{ }

{b}{a}

AnalyseMAY

60

a

c


âge 1

b{a,c}{b}

{b}{a,c}



{ }{ }

{a}{ }

{b}{a}

{c}{b}

AnalyseMAY

61

a

c


âge 1

b

{b}{a,c}



{a,c}{b}

{b}{a,c}

{ }{ }

{a}{ }

{c}{b}

AnalyseMAY

62

a

c


âge 1

b

alwaysmiss



{b}{a,c}

{a,c}{b}

{b}{a,c}

{ }{ }

{a}{ }

{c}{b}

AnalyseMUST

63

a

c

{ }{ }


âge 1

b

join = intersection & âge maximum


AnalyseMUST

64

a

c

{ }{ }


âge 1

b

{a}{ }



AnalyseMUST

65

a

c

{ }{ }


âge 1

b

{a}{ }

{a}{ }

{b}{a}



AnalyseMUST

66

a

c

{ }{ }


âge 1

b

{a}{ }

{a}{ }

{b}{a}

{b}{a}

{c}{b}



AnalyseMUST

67

a

c

{ }{ }


âge 1

b

{a}{ }

{ }{ }

{b}{ }

{b}{a}

{c}{b}



AnalyseMUST

68

a

c

{ }{ }


âge 1

b

{a}{ }

{ }{ }

{b}{ }

{b}{ }

{c}{b}



AnalyseMUST

69

a

c

{ }{ }


âge 1

b

{a}{ }

{ }{ }

{b}{ }

{b}{ }

{c}{b}

???

???


AnalysedePERSISTENCE▪︎ étatabstraitd’unensemble=âgesmaximum+âgespécifiquepourlesblocsremplacés

70

{ }

{a, b}

{ }

{c}

âge

0

1

2

3

{e,f}remplacé


AnalysedePERSISTENCE▪︎ update()

□ commepourl’analyseMUST▪︎ join()

□ union&âgemaximum

▪︎ déterminelesblocsquinepeuventpasêtreéjectés(remplacés)unefoisqu’ilsontétéchargésdanslecache

71


PERSISTENCE

72

a

c

{ }{ }


âge 1

b

{ } remplacé

join = union & âge maximum


PERSISTENCE

73

a

c

{ }{ }


âge 1

b

{ } remplacé

{a}{ }{ }



PERSISTENCE

74

a

c

{ }{ }


âge 1

b

{ } remplacé

{a}{ }{ }

{a}{ }{ } { }

{a}{b}



PERSISTENCE

75

a

c

{ }{ }


âge 1

b

{ } remplacé

{a}{ }{ }

{a}{ }{ } { }

{a}{b}

{ }{a}{b}

{a}{b}{c}



PERSISTENCE

76

a

c

{ }{ }


âge 1

b

{ } remplacé

{a}{ }{ }

{c}{b}{a} {a}

{c}{b}

{ }{a}{b}

{a}{b}{c}



PERSISTENCE

77

a

c

{ }{ }


âge 1

b

{ } remplacé

{a}{ }{ }

{c}{b}{a} {a}

{c}{b}

{a}{c}{b}

{a}{b}{c}



PERSISTENCE

78

a

c

{ }{ }


âge 1

b

{ } remplacé

{a}{ }{ }

{c}{b}{a} {a}

{c}{b}

{a}{c}{b}

{a}{b}{c}

persistent

persistent



Principaldéfi:▪︎ adressesciblesinconnueset/oumultiples

Analyseducachededonnées

80

char a[MAX];

void isort() {int i,p,j,x;

for (i=1 ; i=p ; j--)

a[j+1] = a[j]; a[p] = x;

} }

isort: stmfd sp!,{r0-6}mov r0,#1adr r10,a

for1: cmp r0,#MAXbcs endmov r1,#0

while: ldrb r2,[r10,r1]ldrb r3,[r10,r0]cmp r2,r3bcs next1add r1,r1,#1b while

next1: sub r4,r0,#1for2: cmp r4,r1

blt next2ldrb r5,[r10,r4]add r6,r4,#1strb r5,[r10,r6]sub r4,r4,#1b for2

next2: strb r3,[r10,r1]add r0,r0,#1b for1

end: ldmfd sp!,{r0-6}mov pc,lr

Analysedesadresses

Impactdesécritures

Analyseducachededonnées

81

Ramaprasad,Mueller,Bounding Worst-CaseDataCacheBehaviour byAnalytically Deriving CacheReferencePatterns,RTAS2005

Huynh,Ju,Roychoudhury,Scope-aware DataCacheAnalysis forWCETEstimation,RTAS2011

Hahn,Grund,Relational CacheAnalysis forStatic TimingAnalysis,ECRTS2012

Blaß,Hahn,Reineke,Write-BackCachesinWCETAnalysis,ECRTS2017

Analysed’unehiérarchiedecaches

82

analyseduniveauL

analyseduniveauL+1

référencesmémoire

classificationdesaccèsauniveauL

classificationdesaccèsauniveauL+1

classificationhit/missauniveauL

classificationhit/missauniveauL+1

classificationdesaccèsauniveauL+2

⊕

⊕

NeverAlwaysUncertain

Hardy,Puaut,WCETAnalysis ofMulti-Level Non-InclusiveSet-AssociativeInstructionCaches,RTSS2008

Objectif:▪︎ rendrelalatencedesaccèsmémoireplusprévisible

Défis:▪︎ miseenoeuvre

□ sélectionnerlecontenuàverrouiller□ insérerdesinstructionsdechargementetdeverrouillage

▪︎ surcoûttemporel□ routinesdeverrouillage,défautsadditionnels

Verrouillagedecache

83

Mittal,ASurveyofTechniquesforCacheLocking,ACMTrans.onDesignAutomationofElectronic Systems 21(3),2016

Différentesapproches▪︎ verrouillagestatiqueoudynamique▪︎ completoupartiel▪︎ verrouillagedeligneoudevoie

▪︎ stratégiespoursélectionnerlecontenu:□ algorithmesgénétiques□ programmationlinéaire□ algorithmesgloutons

Verrouillagedecache

84

Exemple

□ Pointsderechargement:entréesdefonctionsetdeboucles

▪︎ Algorithmeglouton□ sélectionducontenufondésurlafréquencedesinstructionssurlecheminlepluslong(WCEP)

□ algorithmeitératifquimetàjourrégulièrementleWCEPetsélectionnelesblocsquitirentleplusbénéficeduverrouillagedeleursinstructions

▪︎ Algorithmegénétique□ chromosome=paire(pointdechargement,contenuàcharger)□ fonctionfitness=WCET□ crossover =échangerunchromosomealéatoireentrelesparents□ mutations=suppressionouajoutd’unpointdechargement,modificationducontenuducache(aléatoirement,unnombrefixedeblocsmémoire)

□ populationinitiale=nombrefixedepointsdechargementchoisisaléatoiremet etcontenudecachealéatoire

Verrouillagedecache

85

Puaut,WCET-centric Software-controlled InstructionCachesforHardReal-TimeSystems,ECRTS,2006

Références

Verrouillagedecache

86

Campoy etal.,CacheContentsSelection forStatically-locked InstructionCaches:anAlgorithm Comparison,ECRTS2005

Ding,Liang,Mitra,WCET-centric PartialInstructionCacheLocking,DAC2012

Ding,Liang,Mitra,WCET-centric Dynamic InstructionCacheLocking,DAC2014

Zheng,Wu,WCET-aware Dynamic D-cacheLocking foraSingleTask,LCTES2015

Interférencesavecd’autrestâches

87

Calculducoûtdelapréemptionvis-à-visducache▪︎ CRPD:Cache-Related Preemption Delays▪︎ quelssontlesblocsquivont(peut-être)êtreéjectésparlatâchepréemptrice etdevrontêtrerechargésdanslecache?

Impactdelapréemption

88

t0 t1

preemption (P)

t0’

t0’ t0’’’

WCET0inisolation

t0’’ t0’’’WCET0

with interferences

t0

t0’’t0’

Leeetal.Analysis ofCache-Related Preemption Delays inFixed-priority PreemptiveScheduling,IEEETrans.onComputers47(6)),1998

Analysedesblocsutiles(Useful CacheBlocks)▪︎ susceptiblesd’êtredanslecacheaupointP▪︎ peuventêtreréutilisésaupointQ,quipeutêtreatteintdepuis P,sansêtreremplacéssurcechemin(hormisparpréemption)

Analysedesblocsutiles

89

L0

L1

exit

L2

L6

• L0estdanslecacheetseraréutilisé

• L1n’estpasdanslecache• L2estdanslecachemaisne

serapasréutilisé

UCBs ={L0}

L0L9L2L3

contenu du cache (à correspondance directe) avant le

point de préemption

UCBs ?

Useful CacheBlocks(UCBs)▪︎ leurnombreestunebornesupérieuredunombrededéfautsdecachesupplémentairesdusàlapréemption

▪︎ pourunepréemptionaupointP:

▪︎ pourunepréemptionenn’importequelpoint:

Evicting CacheBlocks(ECBs)▪︎ seulslesblocsréférencésparunetâchepréemptrice peuventdéteriorer lecontenuducache…

CalculdesCRPDs

90

𝐶𝑅𝑃𝐷567 𝑃 = ! min 𝑈𝐶𝐵 𝑃 , 𝑎 ×𝑡�

CDCEFGFHG

𝐶𝑅𝑃𝐷567 = maxK 𝐶𝑅𝑃𝐷567(𝑃)

Interférencesdansunearchitecturemulti-cœurs

91

memory

$

Cτ

$ $

$

C

$

C

$

C

interconnect

Analyseintégrée▪︎ considèrel’entrelacementprécisdesaccèsàlaressourcepartagée

▪︎ très(trop)complexe

Analyseconservatrice▪︎ pessimiste

Analyseducoûtdesinterférences▪︎ supposelacompositionnalité

□ WCET=WCETisolation +coût_interférences▪︎ viseàconsidérerlenombre« réel »d’interférencespourlimiterlepessimisme

Estimationdesinterférences

92

C C

M

C Cτ

request by τ

L L L L

worst-caselatency

roundrobin

Approchesfaisantl’hypothèsedecompositionnalité

93

Altmeyer etal.,AGeneric andCompositional FrameworkforMulticore ResponseTimeAnalysis,RTNS2015

Pellizzoni etal.,Worst-caseDelayAnalysis forMemoryInterference inMulticoreSystems,DATE2010

Schliecker,Negrean,Ernst,Bounding theShared ResourceLoad forthePerformanceAnalysis ofMultiprocessor Systems,DAC2010

Dasari,Nelis,Akesson,AFrameworkforMemoryContentioninMulti-corePlatforms,JournalofReal-TimeSystems 52(3),2016

Kimetal.,Bounding MemoryInterference DelayinCOTS-based MulticoreSystems,RTAS2014

Analysecompositionnelle

94

Hahn,Jacobs,ReinekeEnabling Compositionality forMulticore TimingAnalysis,RTNS2016

WCET

I=quantitéd’interférences

Ci =WCETenisolation

réel

sous-estimé

surestimé

blocked =0time=2

blocked =1time=8

max!𝑡𝑖𝑚𝑒F. 𝑥F

�

F

!𝑏𝑙𝑜𝑐𝑘𝑒𝑑. 𝑥F ≤ 𝐼�

F

Idée:calculerunWCETdebase« compositionnel »

95

WCET

I=quantitéd’interférences

C’i =WCETenisolation

+effetsindirectsdesinterférences

réel!𝑏𝑙𝑜𝑐𝑘𝑒𝑑. 𝑥F ≤ 𝑖�

F

max !𝑡𝑖𝑚𝑒F. 𝑥F

�

F

− 𝑝. 𝑖

Analysecompositionnelle

Modèledecalculprévisible

96

Durrieu etal.,Predictable FlightManagementSystemImplementation onaMulticore Processor,ERTS2014

A=Acquisition/E=Exécution/R=Restitution

Objectif▪︎ minimiserletempsderéponseglobalencontrôlantlesinterférencesvialemapping etl’ordonnancementdestâchessurlescœurs

Deuxapproches▪︎ formulationILP▪︎ heuristiquedetype« ordonnancementparliste »

Modèledecalculprévisible

Rouxel,Derrien,Puaut,Tightening contentiondelays while scheduling parallelapplicationsonmulti-core architectures,EMSOFT2017

graphedetâchesdépendantes

read execute write

Perspectives

98

Documents

Quel temps d’exécution pour mon programme - univ-ubs.frlabsticc.univ-ubs.fr/archi2019/cours-christine.pdfpour mon programme dans le pire des cas ? Ecole ARCHI —Lorient —2019