Transcript
¨ 1 Uberblick
Gliederung
Echtzeitsysteme Exkurs: WCET-Analyse
1
¨ Uberblick
2
Problemstellung
3
Pfadanalyse Problemstellung Timing Schema Implicit Path Enumeration Technique ¨ Ubersicht
4
Hardware-Analyse Cache-Analyse
5
Messbasierte WCET-Analyse
6
Zusammenfassung
Lehrstuhl Informatik 4
24. Januar 2013
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
c fs (Lehrstuhl Informatik 4)
1 / 38
¨ 1 Uberblick
IX WCET
Fragestellungen
WS 2012/13
2 / 38
WS 2012/13
4 / 38
2 Problemstellung
Gliederung
Alle sprechen von der WCET – aber wo kommt sie eigentlich her? Wie geht man mit der Abh¨angigkeit von Eingabedaten um? Welche Rolle spielt der Prozessor beim Thema WCET?
Pfadanalyse ; bestimmt den l¨angsten Pfad durch ein Programm
1
¨ Uberblick
2
Problemstellung
3
Pfadanalyse Problemstellung Timing Schema Implicit Path Enumeration Technique ¨ Ubersicht
4
Hardware-Analyse Cache-Analyse
5
Messbasierte WCET-Analyse
6
Zusammenfassung
Timing Schema
; orientiert sich an der Programmstruktur
Implicit Path Enumeration Technique (IPET) ; Abbildung auf ein Flussproblem
Hardware-Analyse ; bestimme Dauer des l¨angsten Pfads
Prozessoren werden hinsichtlich Geschwindigkeit optimiert . . . Caches, Pipelines, Out-of-Order-Execution, Sprungvorhersage, . . .
. . . nicht hinsichtlich Vorhersagbarkeit
Warum bestimmen wir die WCET nicht einfach durch Messung? c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
Echtzeitsysteme
WS 2012/13
3 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
IX WCET
2 Problemstellung
IX WCET
2 Problemstellung
Auf der Suche nach dem e
Warum ist es so schwierig, e zu bestimmen?
Die maximale Ausf¨ uhrungszeit ist eine unabk¨ ommliche Information f¨ ur die Ablaufplanung
Anders: Wovon h¨ angt die maximale Ausf¨ uhrungszeit eigentlich ab?
Statische Ablaufplanung ordnet Jobs Zeitintervallen zu ; diese Zeitintervalle m¨ ussen ausreichend groß sein Planbarkeitsanalyse basiert auf Absch¨atzungen . . . der maximalen CPU-Auslastung:
k=1
binp ek + ≤1 min(Dk , pk ) min(Di , pi )
for ( i = size - 1; i > 0; --i ) { for ( j = 0; j < i ; ++ j ) { if ( a [ j ] > a [ j +1]) { swap (& a [ j ] ,& a [ j +1]); } } }
; i = 1, 2, . . . , n
return ;
Pipeline ; Wie ist der Zustand der Pipeline an einer Instruktion? Cache ; Liegt die Instruktion/das Datum im schnellen Cache? Out-of-Order-Execution, Branch-Prediction, Hyper-Threading, . . .
die ohne die maximale Ausf¨ uhrungszeit e nicht auskommen selbst die Blockadezeit b np ist eine maximale Ausf¨ uhrungszeit ; n¨ amlich die des l¨ angsten kritischen Abschnitts Echtzeitsysteme
IX WCET
sowohl die Gr¨oße als auch der Inhalt des Felds kann zur Laufzeit variieren
Die Maschinenprogrammebene liefert Dauer der Elementaroperationen: wie lange dauert ein ADD, ein LOAD, . . . ist prozessorabh¨angig und f¨ ur moderne Prozessoren sehr schwierig
i−1 X t e k ; 0 < t ≤ pi pk k=1
c fs (Lehrstuhl Informatik 4)
Anzahl der Vertauschungen (swap) h¨angt vom Inhalt des Feldes ab ; exakte Vorhersage ist kaum m¨oglich
}
der maximalen Antwortzeit: ωi (t) = ei + binp +
Anzahl der Schleifendurchl¨aufe h¨angt von der Gr¨oße des Feldes a[] ab
void bubbleSort ( int a [] , int size ) { int i , j ;
mindestens so groß, wie die maximale Ausf¨ uhrungszeit e des Jobs
n X
Programmiersprachenebene:
Beispiel: Bubblesort
WS 2012/13
c fs (Lehrstuhl Informatik 4)
5 / 38
2 Problemstellung
IX WCET
Aufgabenstellung
Echtzeitsysteme
WS 2012/13
6 / 38
WS 2012/13
8 / 38
3 Pfadanalyse
Gliederung
Die maximale Ausf¨ uhrungszeit nach oben absch¨ atzen BCET
WCET
1
2
3
4
beobachtete Verteilung
5
6
¨ Uberblick
2
Problemstellung
3
Pfadanalyse Problemstellung Timing Schema Implicit Path Enumeration Technique ¨ Ubersicht
4
Hardware-Analyse Cache-Analyse
5
Messbasierte WCET-Analyse
6
Zusammenfassung
Ausführungszeit
Bereits f¨ ur relativ einfache Programme ergibt sich eine Bandbreite m¨ oglicher Programmlaufzeiten, besondere Bedeutung haben bestm¨ogliche Ausf¨ uhrungszeiten (engl. best case execution time) 1
1
tatsächlich mögliche Verteilung
Häufigkeit
gesch¨atzt,
2
tats¨achlich und
3
beobachtet
und maximale Ausf¨ uhrungszeiten (engl. worst case execution time) 4
+
beobachtet,
5
tats¨achlich und
6
gesch¨atzt
Ziel ist eine sichere Absch¨atzung der WCET und den Abstand zur tats¨achlichen WCET klein zu halten
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
7 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
IX WCET
3 Pfadanalyse
3.1 Problemstellung
IX WCET
Ableitung des maximalen Pfads anhand der Programmstruktur
betrachte Aufrufe: bubbleSort(a,s)
void bubbleSort ( int a [] , int size ) { int i , j ; for ( i = size - 1; i > 0; --i ) { for ( j = 0; j < i ; ++ j ) { if ( a [ j ] > a [ j +1]) { swap (& a [ j ] ,& a [ j +1]); } } }
Anzahl von Durchl¨aufen, Vergleichen und Vertauschungen (engl. Swap)
Sequenzen ; Hintereinanderausf¨ uhrung
a = {1, 2}, s = 2
S1;
Summation der WCETs: eseq = eS1 + eS2
S1 (); S2 ();
S2;
; D = 1, V = 1, S = 0;
a = {1, 3, 2}, s = 3 ; D = 3, V = 3, S = 1;
Verzweigung ; bedingte Ausf¨ uhrung
; D = 3, V = 3, S = 3;
if ( P1 ()) S1 (); else S2 ();
a = {3, 2, 1}, s = 3
return ; }
3.2 Timing Schema
Abstrakter Syntaxbaum ; Timing Schema
Den l¨angsten Weg durch ein Programm finden Beispiel: Bubblesort
3 Pfadanalyse
ist f¨ ur den allgemeinen Fall nicht berechenbar ; Halteproblem
Absch¨atzung der Gesamtausf¨ uhrungszeit: econd = eP1 + max (eS1 , eS2 )
P1; f t S1; S2;
Wieviele Schleifendurchl¨aufe werden ben¨ otigt?
; in Echtzeitsystemen ist dieses Problem aber h¨aufig l¨osbar
Schleifen ; wiederholte Ausf¨ uhrung
kanonische Schleifenkonstrukte: for(int i = 0;i < X;++I) X ist oft eine Konstante oder zumindest beschr¨ ankt ggf. muss die obere Schranke manuell annotiert werden
while ( P1 ()) S1 ();
P1; t S1; f
Schleifendurchl¨aufe ber¨ ucksichtigen: eloop = eP1 + n (eP1 + eS1 )
die maximale, nicht die exakte Pfadl¨ange ist von Belang c fs (Lehrstuhl Informatik 4)
IX WCET
Echtzeitsysteme
3 Pfadanalyse
WS 2012/13
9 / 38
3.2 Timing Schema
IX WCET
Beispiel: Bubblesort void bubbleSort ( int a [] , int size ) { int i , j ; for(i = size - 1; i > 0; --i) { for (j = 0; j < i; ++j) { if(a[j] > a[j+1]) { swap(&a[j],&a[j+1]); } } } return ; }
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
3 Pfadanalyse
WS 2012/13
10 / 38
3.2 Timing Schema
Timing Schema: Vor- und Nachteile Schleife L1 : P1 = i > 0
Traversierung des abstrakten Syntaxbaums bottom-up
Rumpf: L2 ; --i; Durchl¨aufe: size - 1 ; eL1 = eP1 +(size −1)(eP1 +eL2 +e−−i )
d. h. an den Bl¨attern beginnend, bis man zur Wurzel gelangt
maximale Ausf¨ uhrungszeit wird nach festen Regeln akkumuliert f¨ ur Sequenzen, Verzweigungen und Schleifen
Schleife L2 : P2 = j < i
Rumpf: C1 ; ++j; Durchl¨aufe: size - 1 ; eL2 = eP2 +(size −1)(eP2 +eC1 +e++j )
Vorteile + einfaches Verfahren mit geringem Berechnungsaufwand + skaliert gut mit der Programmgr¨oße
Verzweigung C1 : P3 = a[j] > a[j + 1] Nachteile - generische Flussinformation kann kaum ber¨ ucksichtigt werden
S1 = swap(&a[j],&a[j + 1]) ; e C1 = e P3 + e S 1
Funktionsaufruf S1 = swap(&a[j],&a[j + 1])
z. B. sich ausschließende Zweige aufeinanderfolgender Verzweigungen
analog zum hier vorgestellten Verfahren
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
- schwierige Integration mit einer separaten Hardware-Analyse WS 2012/13
11 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
12 / 38
IX WCET
3 Pfadanalyse
3.3 IPET
IX WCET
3 Pfadanalyse
3.3 IPET
Den l¨angsten Weg durch ein Programm finden
Wie berechnet man den l¨angsten Pfad?
Die m¨ oglichen Wege lassen sich durch Kontrollflussgraphen beschreiben
. . . und bestimmt so auch gleicht die maximale Ausf¨ uhrungszeit
L¨osungsansatz: Fasse die Bestimmung der WCET als Flussproblem auf [2]
Ein Kontrollflussgraphen (engl. control flow graph) ist ein gerichteter Graph und setzt sich aus Grundbl¨ ocken (engl. basic blocks) zusammen Grundbl¨ocke sind sequentielle Code-Schnipsel“ ”
die Maximierung des Flusses in einem gerichteten Graphen ist ein gut untersuchtes Problem aus dem Bereich der Graphentheorie
hier wird gearbeitet ; Grundbl¨ocke verbrauchen Rechenzeit
Kanten im Kontrollflussgraphen ; Spr¨ unge zwischen Grundbl¨ocken i = size - 1; void bubbleSort ( int a [] , int size ) { int i , j ;
i > 0 t
f
for(i = size - 1; i > 0; --i) { for (j = 0; j < i; ++j) { if(a[j] > a[j+1]) { swap(&a[j],&a[j+1]); } } }
return;
1
bestimme einen Zeitanalysegraph aus dem Kontrollflussgraphen
2
formuliere das lineare Optimierungsproblem bestimme die Flussrestriktionen des Zeitanalysegraphen
f --i
return;
3
t a[j] < a[j + 1] t f swap(&a[j],&a[j + 1]);
}
++j
IX WCET
Vorgehen: Transformiere den Kontrollflussgraphen in ein ganzzahliges, lineares Optimierungsproblem (ILP) und l¨ose es
j = 0; j <= i
c fs (Lehrstuhl Informatik 4)
mithilfe ganzzahliger linearer Programmierung (engl. integer linear programming) l¨asst sich dieses Problem zudem effektiv l¨osen
4 1
Echtzeitsysteme
3 Pfadanalyse
dies sind die Nebenbedingungen im Optimierungsproblem
WS 2012/13
13 / 38
3.3 IPET
l¨ose des Optimierungsproblem (z.B. mit lpsolve1 ) http://lpsolve.sourceforge.net/
c fs (Lehrstuhl Informatik 4)
IX WCET
Der Zeitanalysegraph (engl. timing analysis graph)
Knoten, aus denen/in die nur Kanten entspringen/m¨ unden
jede Kante ist Bestandteile eines Pfads P von der Senke zur Kante jeder Kante wird ihre WCET ei zugeordnet Grundbl¨ocke des Kontrollflussgraphen werden auf Kanten abgebildet f¨ ur Verzweigungen ben¨ otigt man Dummy-Kanten di
1 2
1:e1 2:e2
1 2
P
2:e2
3:e3 4:e4
Echtzeitsysteme
+ L¨ osung: fasse die Bestimmung der WCET als Flussproblem auf ; der maximale Fluss durch das durch den T-Graphen gegebene Netzwerk f¨ uhrt zur gesuchten WCET
3:e3 2:e2 3 d1 4
; Flussprobleme sind mathematisch gut untersucht und lassen sich durch lineare Ganzzahlprogrammierung l¨osen
4:e4 WS 2012/13
Ei ∈P
; das ist algorithmisch nicht handhabbar
1:e1
1 2
3 4
c fs (Lehrstuhl Informatik 4)
d1
3.3 IPET
+ Problem: erfordert die explizite Aufz¨ahlung aller Pfade
Schleife 1:e1 d2
14 / 38
Mit der Anzahl fi der Ausf¨ uhrungen einer Kante Ei bestimmt man die WCET e durch Summation der Ausf¨ uhrungszeiten des l¨angsten Pfades: X e = max fi e i
solche ein Pfad P entspricht einer m¨oglichen Abarbeitung
Verzweigung
3 Pfadanalyse
WS 2012/13
Bestimmung der WCET
Ein Zeitanalysegraph (oder kurz T-Graph) ist ein gerichteter Graph mit einer Menge von Knoten V = {Vi } und Kanten E = {Ei }. mit genau einer Quelle und einer Senke
Sequenz
Echtzeitsysteme
15 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
16 / 38
IX WCET
3 Pfadanalyse
3.3 IPET
IX WCET
Zirkulationen
3 Pfadanalyse
3.3 IPET
Beispiel: Bubblesort
Eine Abbildung f : E 7→ R heißt Zirkulation, falls sie den Fluss erh¨alt
1:e1
jeder Kante wird die Zahl der Ausf¨ uhrungen fi als Fluss zugeordnet Flusserhaltung: jeder Knoten wird gleich oft betreten und verlassen
i = size - 1; 1:e1
f
erfordert die Einf¨ uhrung einer R¨ uckkehrkante Ee mit fe = 1
9:e9 return;
d8
8:e8 --i
f
8:e8
4:e4 d
j <= i 4:e4 t
Beschr¨ankung der maximalen Anzahl von Schleifendurchl¨aufen
d1 3:e3
j = 0; 3:e3
Flussrestriktionen schließen Zirkulationen ung¨ ultiger Abarbeitungen aus Formulierung als Nebenbedingungen des Optimierungsproblems
2:e2 d7
i > 0 2:e2 t
6
d2
a[j] < a[j + 1] 5:e5 t f swap(&a[j],&a[j + 1]); 6:e6
9:e9 d5
5:e5 d4 d3
2:e2 4:e4 d1
7:e7 ++j
f1 = f2 + f4 wird durch die Zirkulation garantiert g¨ ultige Zirkulation: {E1 , E4 , d2 , E5 , Ee } ∪ {E3 , d1 }
1:e1
3:e3
d2 d3 5:e5 c fs (Lehrstuhl Informatik 4)
IX WCET
; aber keine g¨ ultige Abarbeitung
Flussrestriktionen, die sich aus Schleifen ergeben:
Flussrestriktion f3 ≤ 5f2 l¨ost dieses Problem wird E2 nicht abgearbeitet, so gilt f3 ≤ 5 · 0 = 0 hier: Beschr¨ankung auf 5 Schleifendurchl¨aufe ; Nebenbedingung des Optimierungsproblems Echtzeitsysteme
WS 2012/13
3 Pfadanalyse
17 / 38
3.3 IPET
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
3 Pfadanalyse
WS 2012/13
18 / 38
3.3 IPET
zun¨achst wird aus dem Kontrollflussgraph ein T-Graph erzeugt dieser wird in ganzzahliges lineares Optimierungsproblem u uhrt ¨berf¨
Ei ∈E
Vorteile + M¨oglichkeit komplexer Flussrestriktionen
Nebenbedingungen garantieren tats¨achlich m¨ ogliche Ausf¨ uhrungen Flusserhaltung f¨ ur jeden Knoten des T-Graphen X X fj = fk
¨ z. B. sich ausschließende Aste aufeinanderfolgender Verzweigungen
+ Nebenbedingungen f¨ ur das ILP sind leicht aufzustellen
Ek− =Vi
+ viele Werkzeuge zur L¨osung von ILPs verf¨ ugbar Nachteile
Flussrestriktionen f¨ ur alle Schleifen des T-Graphen, z.B.
- das L¨osen eines ILP ist im Allgemeinen NP-hart - auch Flussrestriktionen sind kein Allheilmittel
f2 ≤ (size − 1)f1
Beschreibung der Ausf¨ uhrungsreihenfolge ist problematisch
R¨ uckkehrkante kann nur einmal durchlaufen werden: fEe = 1 Echtzeitsysteme
bedingte Vertauschung: fd3 + f6 = f7
betrachte m¨ogliche Abarbeitungen des Kontrollflussgraphen dabei werden alle Pfade implizit in Betracht gezogen
; der Vektor (f1 , . . . , fe ) maximiert die Ausf¨ uhrungszeit
c fs (Lehrstuhl Informatik 4)
Flussrestriktionen, die sich aus Verzweigungen ergeben:
Vor- und Nachteile
Zielfunktion: Maximierung des gewichteten Flusses X WCETe = max fi e i
Ej+ =Vi
¨außere Schleife“: f2 ≤ (size − 1)f1 ” innerer Schleife“: f4 ≤ (size − 1)f3 ”
IX WCET
Ganzzahliges Lineares Optimierungsproblem
(f1 ,...,fe )
6:e6 7:e7
WS 2012/13
19 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
20 / 38
IX WCET
¨ 3.4 Ubersicht
3 Pfadanalyse
IX WCET
Werkzeugkette f¨ur die WCET-Analyse [3]
Gliederung
Extraktion von Flussrestriktionen
Quelltext
1
¨ Uberblick
2
Problemstellung
3
Pfadanalyse Problemstellung Timing Schema Implicit Path Enumeration Technique ¨ Ubersicht
4
Hardware-Analyse Cache-Analyse
5
Messbasierte WCET-Analyse
6
Zusammenfassung
Transformation von Flussrestriktionen
¨ Ubersetzer
4 Hardware-Analyse
Berechnung der Ausf¨ uhrungsszenarien Harware-Analyse
Bin¨ arcode
WCET
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
IX WCET
WS 2012/13
21 / 38
4 Hardware-Analyse
c fs (Lehrstuhl Informatik 4)
IX WCET
Wie lange dauern die sequentiellen Code-Schnipsel“ ”
Echtzeitsysteme
WS 2012/13
22 / 38
4 Hardware-Analyse
Hardware-Analyse
Die WCETs ei der einzelnen Grundbl¨ ocke ist Eingabe f¨ ur die Flussanalyse
Hardware-Analyse teilt sich in verschiedene Phasen Grundproblem: Ausf¨ uhrungszyklen von Instruktionen z¨ahlen _getop : link moveml movel movel
a6 ,#0 #0 x3020 , sp@ a6@ (8) , a2 a6@ (12) , d3
; ; ; ;
16 32 16 16
Zyklen Zyklen Zyklen Zyklen
Aufteilung ist nicht dogmenhaft festgeschrieben
Ergebnis: e getopt = 80 Zyklen Annahmen: obere Schranke f¨ ur jede Instruktion die obere Schranke der Sequenz bestimmt man durch Summation
Quelle: Peter Puschner [2]
WS 2012/13
Cache- und Pfad-Analyse sowie WCET-Berechnung
Separate Pfad- und Cache-Analyse 1 Cache-Analyse
pessimistisch f¨ ur moderne Prozessoren Pipeline, Cache, Branch Prediction, Prefetching, . . . haben großen Anteil an der verf¨ ugbaren Rechenleistung heutiger Prozessoren blanke Summation einzelner WCETs ignoriert diese Maßnahmen Echtzeitsysteme
Wie lange dauert die Ausf¨ uhrung der Instruktionssequenz? 2
Cache-Analyse wird direkt in das Optimierungsproblem integriert
Problem: Vorgehen ist ¨außerst pessimistisch und zum Teil falsch falsch f¨ ur Prozessoren mit Laufzeitanomalien WCET der Sequenz > Summe der WCETs aller Instruktionen
c fs (Lehrstuhl Informatik 4)
Integration von Pfad- und Cache-Analyse 1 Pipeline-Analyse
23 / 38
kategorisiert Speicherzugriffe mit Hilfe einer Datenflussanalyse 2
Pipeline-Analyse Ergebnisse der Cache-Analyse werden direkt ber¨ ucksichtigt
3
Pfad-Analyse und WCET-Berechnung
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
24 / 38
IX WCET
4 Hardware-Analyse
4.1 Cache-Analyse
IX WCET
Cache-Analyse [4, Kapitel 22]
engl. (pseudo) least recently used, (Pseudo-)LRU engl. (pseudo) first in first out, (Pseudo-)FIFO Echtzeitsysteme
IX WCET
4.1 Cache-Analyse
Ergebnisse der Cache-Analyse
Cache: ein kleiner, schneller Zwischenspeicher, Zugriffszeiten auf Daten/Instruktionen variieren je nach Zustand des Caches enorm: Treffer (engl. hit), Daten/Instruktion sind im Cache ; eh Fehlschlag (engl. miss), Daten/Instruktion sind nicht im Cache ; em Hits sind schneller als Misses: em eh (> 100 Taktzyklen m¨oglich) Folgende Eigenschaften von Caches haben Einfluss auf seine Analyse Typ Cache f¨ ur Instruktionen Cache f¨ ur Daten kombinierter Cache f¨ ur Instruktionen und Daten Auslegung direkt abgebildet (engl. direct mapped) vollassoziativ (engl. fully associative) satz- oder mengenassoziativ (engl. set associative) Seitenersetzungsstrategie
c fs (Lehrstuhl Informatik 4)
4 Hardware-Analyse
4 Hardware-Analyse
Hilfreich ist, zu wissen, ob z.B. eine Instruktion im Cache ist, oder nicht: must, die Instruktion ist garantiert im Cache ; man kann immer die schnellere Ausf¨ uhrungszeit eh annehmen wird f¨ ur die Vorhersage von Treffern verwendet may, die Instruktion ist vielleicht im Cache ; ist dies nicht der Fall, muss man die Ausf¨ uhrungszeit em annehmen wird f¨ ur die Vorhersage von Fehlschl¨agen verwendet persistent, die Instruktion verbleibt im Cache ; erster Zugriff ist ein Fehlschlag, alle weiteren sind Treffer ; erster Zugriff: em , weitere Zugriffe: eh
ist besonders f¨ ur Schleifen interessant, die den Cache f¨ ullen“ ”
WS 2012/13
25 / 38
4.1 Cache-Analyse
c fs (Lehrstuhl Informatik 4)
IX WCET
Beispiel: LRU-Cache, 4-fach assoziativ
Echtzeitsysteme
4 Hardware-Analyse
WS 2012/13
26 / 38
4.1 Cache-Analyse
Beispiel: LRU-Cache, Zugriff auf eine Speicherstelle
LRU = least recently used“ – Das ¨ alteste Element fliegt raus! ”
Ann¨aherung des Cache-Verhaltens durch must- und may-Approximation: Aktualisierung von Inhalt und Verwaltungsinformation
Caches werden h¨aufig in S¨atze (engl. cache set) unterteilt ein n-fach assoziativer Cache besitzt pro Satz n Cache-Bl¨ocke ; Aufnahme von n konkurrierende Speicherstellen pro Satz m¨oglich Inhalt und Verwaltungsinformation (bei LRU das Alter des Blocks) werden sowohl bei Treffern als auch bei Fehlschl¨agen aktualisiert konkrete Semantik des Cache
Cache Miss
{S}
mustApproximation
S S Z Y X
Alter
Z Y S T
S Z Y T
Alter
must-Analyse und may-Analyse approximieren diese konkrete Semantik: must Obergrenze des Alters ; Unterapproximation des Inhalts Obergrenze ≤ Assoziativit¨at ; garantiert im Cache ¨ may Untergrenze des Alters ; Uberapproximation des Inhalts Untergrenze > Assoziativit¨at ; garantiert nicht im Cache c fs (Lehrstuhl Informatik 4)
Definitive Cache Hit
{Z }
Cache Hit
S Z Y X T
Potential Cache Miss
Echtzeitsysteme
WS 2012/13
27 / 38
{X }
{Z }
{X }
{S}
{}
{X }
{}
{X }
{S, T }
{}
{S, T }
{T }
{}
{S, T }
{}
{}
Definitive Cache Miss
Potential Cache Hit
{Z }
{S}
mayApproximation
c fs (Lehrstuhl Informatik 4)
{X }
{Z }
{X }
{S}
{}
{X }
{}
{X }
{S, T }
{}
{S, T }
{}
{Y }
{S, T }
{Y }
{Y , T }
Echtzeitsysteme
WS 2012/13
28 / 38
IX WCET
4 Hardware-Analyse
4.1 Cache-Analyse
IX WCET
Wie funktioniert nun die Cache-Analyse?
4 Hardware-Analyse
4.1 Cache-Analyse
Verschmelzungsoperatoren f¨ur must- und may-Analyse
Die Analyse ist eine Datenflussanalysen [1, Kapitel 8] may-Analyse
must-Analyse 1
sammle Information in den Grundbl¨ocken Speicherzugriffe (s. Folie IX/28) ¨ man bestimmt die Ubertragungsfunktion (engl. transfer function) des Grundblocks
Entry 3 1 2
2 2 1
2
die Information wird u ¨ber ausgehende Kanten weiterverteilt ¨ Eingabe f¨ ur die Ubertragungsfunktion der folgenden Grundbl¨ ocke
1
3
{A} {} {C , F } {D}
3 1
+ Verschmelzungsoperatoren f¨ ur must- und may-Analyse c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
IX WCET
WS 2012/13
4 Hardware-Analyse
29 / 38
4.1 Cache-Analyse
Schnittmenge + max. Alter“ ”
Vereinigungsmenge + min. Alter“ ”
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
4 Hardware-Analyse
WS 2012/13
30 / 38
4.1 Cache-Analyse
Praxisrelevante Cache-Implementierungen Cache-Analyse mithilfe einer Datenflussanalyse funktioniert f¨ ur mengenassoziative Caches mit LRU sehr gut
Entry [{} , {} , {} , {}]
A
t
{A, C } {E } {F } {D}
IX WCET
Beispiel: must-Analyse f¨ur LRU
{C } {E } {A} {D}
{} {} {A, C } {D}
fließt der Kontrollfluss wieder zusammen, wird auch die Information verschmolzen ; Verschmelzungsoperatoren
Exit
t
{A} {} {C , F } {D}
{C } {E } {A} {D}
[{D} , {} , {A} , {}] t [{} , {} , {} , {}] = [{} , {} , {} , {}]
Zugriffe auf unterschiedliche Cache-Zeilen beeinflussen sich nicht TriCore: 2-fach assoziativer LRU-Cache Zur Leistungssteigerung kommen auch andere Strategien zum Einsatz:
[{A} , {} , {} , {}]
B
C
D
[{A} , {} , {} , {}]
im Durchschnitt ¨ahnliche Leistung wie LRU, weniger vorhersagbar Psuedo-LRU
[{B} , {A} , {} , {}] t [{C } , {A} , {} , {}] = [{} , {A} , {} , {}]
Cache-Zeilen werden als Bl¨atter eines Baums verwaltet must-Analyse eingeschr¨ankt brauchbar, may-Analyse unbrauchbar z. B. PowerPC 750/755
Pseudo-Round-Robin
Exit [{D} , {} , {A} , {}]
4-fach mengenassoziativer Cache mit einem 2-bit Ersetzungsz¨ahler Z¨ ahler deutet auf zu ersetzende Cache-Zeile, Erh¨ ohung bei Fehlschlag
+ Hier ist leider keine Vorhersage von Treffern m¨oglich /
; Tip: ein einfaches, virtuelles Ausrollen der Schleife hilft weiter! c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
must-Analyse kaum, may-Analyse u ¨berhaupt nicht brauchbar z. B. Motorola Coldfire 5307 31 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
32 / 38
IX WCET
5 Messbasierte WCET-Analyse
IX WCET
Gliederung
Messbasierte WCET-Analyse [3]
1
¨ Uberblick
2
Problemstellung
3
Pfadanalyse Problemstellung Timing Schema Implicit Path Enumeration Technique ¨ Ubersicht
Idee: der Prozessor selbst ist das pr¨aziseste Hardware-Modell ; F¨ uhre das Programm aus und beobachte die Ausf¨ uhrungszeit!
Hardware-Analyse Cache-Analyse
5
Messbasierte WCET-Analyse
6
Zusammenfassung
IX WCET
Probleme messbasierter Ans¨atze - in der Praxis ist es unm¨oglich alle relevanten Pfade zu betrachten - gew¨ahlte Testdaten f¨ uhren nicht unbedingt zum l¨angsten Pfad - seltene Ausf¨ uhrungsszenarien werden nicht abgedeckt - abschnittsweise WCET-Messung 6; globalen WCET
4
c fs (Lehrstuhl Informatik 4)
- schwierig/unm¨oglich den Startzustand des Prozessors zu identifizieren/erzwingen, der zur WCET f¨ uhrt + messbasierte Ans¨atze untersch¨atzen die WCET meistens + systematischere, messbasierte Analysetechniken sind vonn¨oten Echtzeitsysteme
WS 2012/13
Messbasierte WCET-Analyse [3]
c fs (Lehrstuhl Informatik 4)
33 / 38
5 Messbasierte WCET-Analyse
IX WCET
z. B. Echtzeitsystem mit weichen Zeitschranken (engl. soft real-time systems)
¨ Uberblick
2
Problemstellung
3
Pfadanalyse Problemstellung Timing Schema Implicit Path Enumeration Technique ¨ Ubersicht
4
Hardware-Analyse Cache-Analyse
5
Messbasierte WCET-Analyse
6
Zusammenfassung
h¨aufig ist kein geeignetes statisches Analysewerkzeug verf¨ ugbar
geringer Aufwand f¨ ur Annotationen verschafft leicht Orientierung u ¨ber die tats¨achliche Laufzeit
sinnvolle Erg¨anzung zur statischen WCET-Analyse Validierung statisch bestimmter Werte Ausgangspunkt f¨ ur die Verbesserung der statischen Analyse
+ Allerdings sollte man nicht einfach draus los messen“ ” ; z. B. immer Pfade vermessen (d. h. Ablauf und Zeit) Echtzeitsysteme
WS 2012/13
34 / 38
WS 2012/13
36 / 38
6 Zusammenfassung
1
lassen sich leicht an neue Hardwareplattformen anpassen
; auf einen definierten Startzustand achten
Echtzeitsysteme
Gliederung
(Forts.)
Andererseits besteht Bedarf f¨ ur messbasierte Methoden g¨angige Praxis in der Industrie nicht alle Echtzeitsysteme ben¨ otigen eine sichere WCET
c fs (Lehrstuhl Informatik 4)
5 Messbasierte WCET-Analyse
WS 2012/13
35 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
IX WCET
6 Zusammenfassung
IX WCET
Res¨umee
7 Bibliographie
Literaturverzeichnis
Problemdefinition identifiziert zwei Teilprobleme Flussanalyse finde die l¨angsten Pfade durch ein Programm Hardwareanalyse bestimmt die WCET einzelner Grundbl¨ocke
[1] Muchnick, S. S.: Advanced compiler design and implementation. San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 1997. – ISBN 1–55860–320–4
Pfadanalyse ; findet auf Programmiersprachenebene statt Timing Schema verwendet den abstrakten Syntaxbaum IPET basiert auf dem Kontrollflussgraphen
[2] Puschner, P. : Zeitanalyse von Echtzeitprogrammen. Treitlstr. 1-3/182-1, 1040 Vienna, Austria, Technische Universit¨ at Wien, Institut f¨ ur Technische Informatik, Diss., 1993
Erzeugung eines T-Graphen, Ableitung eines Flussproblems ; ganzzahliges lineares Optimierungsproblem
[3] Puschner, P. ; Huber, B. : Zeitanalyse von sicherheitskritischen Echtzeitsystemen. http://ti.tuwien.ac.at/rts/teaching/courses/wcet, 2012. – Lecture Notes
Werkzeugkette f¨ ur die statische WCET-Analyse
Hardware-Analyse ; Eingaben f¨ ur die WCET-Berechnung Hauptaufgaben: Cache- und Pipeline-Analyse Beispiel: Datenflussanalyse f¨ ur 4-fach assoziativen LRU-Cache
[4] Wilhelm, R. : Embedded Systems. http: //react.cs.uni-sb.de/teaching/embedded-systems-10-11/lecture-notes.html, 2010. – Lecture Notes
must-Approximation und may-Approximation
messbasierte WCET-Analyse ; ein kleiner Fingerzeig! c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
37 / 38
c fs (Lehrstuhl Informatik 4)
Echtzeitsysteme
WS 2012/13
38 / 38
