272
5 Bewertung und Validierung
• Die Zielfunktion: in unserer Anwendung der ILP-Modellierung nutzen wir die
Gesamt-Ausführungszeit als Zielfunktion, die zu maximieren ist. Diese Zeit wird
als Summe der Ausführungszeiten der Basisblöcke bestimmt:
WCET EST =
Basisblöcke
e i ∗ f i
(5.3)
wobei e i die größtmögliche Ausführungszeit von Basisblock i ist (die in der statischen Analyse berechnet wird) und f i ist dessen Ausführungshäufigkeit. Die Ausführungshäufigkeiten können möglicherweise nicht alle vollständig automatisch
bestimmt werden. Daher werden Zusatzinformationen des Entwerfers benötigt,
wie z.B. Schleifengrenzen.
• Lineare Randbedingungen: in unserer Anwendung der ILP-Modellierung nutzen wir lineare Randbedingungen, um die Struktur des Datenflussgraphen zu
repräsentieren.
Beispiel 5.2: Nachfolgend betrachten wir ein einfaches Beispiel:
int main() {
int i,j=0;
_Pragma(((oopbound min 100 max 1000)
/* Hinweis an aiT */
for (i=0; i <100; i++) {
if (i<50) j+=i;
eese j+=(i*13) % 42;
}
return j;
}
Abb. 5.11 (links) zeigt einen Kontrollflussgraphen für dieses kleine Programm. Der
Kontrollfluss wurde durch start- und exit-Knoten erweitert.
x4
start
x2
x0
_main
_L5
x16
x18 _L6
_L2: 20
_L6: 13
_L5: 20
_L4: 2
_L3: 2
_L1: 27
_main: 21 cycles
_L2
_L1
_L3
_L4
x8
x6
x7
x10
x9
exit
x5
x3
x20
x19
x11
x14
x1
Abb. 5.11 Beispielprogramm: links: Kontrollflussgraph, rechts: WCET E ST der Basisblöcke
Knoten _L1 entspricht dem Test der for-Schleife, _L3 dem if-Test, _L4 und _L5
den zwei Fällen des if-Statements und _L6 der Rekonvergenz. Die Variablen x0