5.2 Performanzbewertung
273
bis x20 bezeichnen die Ausführungshäufigkeiten der Blöcke und die Anzahl der
Übergänge zwischen den Blöcken. Beispielsweise haben wir x6 Übergänge von
Block main zum Block _L1 und führen den Zielblock x7-mal aus. Wir nehmen an,
dass die Analyse der WCET für die Basisblöcke zu der Liste auf der rechten Seite
von Abb. 5.11 geführt hat. Dies führt zu dem nachfolgenden Auszug aus der Liste
der ILP-Randbedingungen.
01: 21 x2 + 27 x7 + 2 x11 + 2 x14 + 20 x16 + 13 x18 + 20 x19;/*Zieefunktion*/
02: x7 - x8 - x6 = 0;
/* Randbedingung für FFuss nach _L1 */
03: x7 - x9 - x10 = 0;
/* Randbedingung für FFuss von _L1 */
04: x7 - 101 x9 >= 0; /* Randbedingung für untere Schheifengrenze von _L1 */
05: x7 - 101 x9 <= 0; /* Randbedingung für obere Schheifengrenze von _L1 */
06: x0 - x4 = 0;
/* CFG Start-Randbedingung */
07: x2 - x4 = 0;
/* Randbedingung für FFuss nach _main */
08: x2 - x6 = 0;
/* Randbedingung für FFuss von _main */
09: ...
Zeile 01 enthält die Zielfunktion. Alle anderen Zeilen enthalten Randbedingungen, welche die Struktur des Graphen modellieren. Beispielsweise sind die Randbedingungen für den Knoten _L1 in den Zeilen 02 und 03 angegeben. Die Häufigkeit
des Verzweigens in diesen Knoten (x6+x8) ist gleich der Anzahl der Ausführungen
(x7). Die Häufigkeit des Verlassens dieses Knotens (x9+x10) ist ebenfalls gleich der
Anzahl der Ausführungen (x7). Die Zeilen 04 und 05 korrespondieren zu den Schleifeniterationen. Die Anzahl der Iterationen wurde dem Pragma im Code entnommen.
Zeile 06 sagt aus, dass die Anzahl der Ausführungen des start-Knotens gleich der
Anzahl der Verzweigungen in den Code ist. Die übrigen Zeilen beschreiben die
Struktur in ähnlicher Weise.
∇
Das so definierte ILP-Problem kann mit einem Standard-ILP-Solver, der die Zielfunktion maximiert, gelöst werden. Das so berechnete Maximum ist eine sichere
obere Schranke für die gesamte Ausführungszeit.
Diese Technik der Modellierung von Ausführungszeiten heißt Implicit Path Enumeration Technique (IPET) [344]. Sie vermeidet eine vollständige Aufzählung aller
möglichen Ausführungspfade. Eine solche Aufzählung würde zu i.d.R. zu sehr vielen
Pfaden führen.
In aiT ist auch eine Visualisierung der Ergebnisse in Form annotierter Kontrollflussgraphen verfügbar. Der Entwickler kann diese Graphen analysieren, um das zu
entwerfende System zu optimieren. aiT besitzt eine Reihe von Einschränkungen, die
sich aus dem beschriebenen Vorgehen erklären lassen: so werden keine Verdrängungen durch andere Prozesse, keine Hardware-Unterbrechungen, keine Ein/Ausgaben,
keine direkten Speichertransfers (DMA) und keine Interferenzen durch andere Hardwarekomponenten betrachtet.
Für die WCET-Analyse von Mehrkern-Systemen existieren nur wenige Ansätze [265, 266, 287]. Mit neuen probabilistischen Methoden [2] sollen existierende
Ansätze ergänzt werden. Sie basieren meist auf der Extremwerttheorie [196].
273
bis x20 bezeichnen die Ausführungshäufigkeiten der Blöcke und die Anzahl der
Übergänge zwischen den Blöcken. Beispielsweise haben wir x6 Übergänge von
Block main zum Block _L1 und führen den Zielblock x7-mal aus. Wir nehmen an,
dass die Analyse der WCET für die Basisblöcke zu der Liste auf der rechten Seite
von Abb. 5.11 geführt hat. Dies führt zu dem nachfolgenden Auszug aus der Liste
der ILP-Randbedingungen.
01: 21 x2 + 27 x7 + 2 x11 + 2 x14 + 20 x16 + 13 x18 + 20 x19;/*Zieefunktion*/
02: x7 - x8 - x6 = 0;
/* Randbedingung für FFuss nach _L1 */
03: x7 - x9 - x10 = 0;
/* Randbedingung für FFuss von _L1 */
04: x7 - 101 x9 >= 0; /* Randbedingung für untere Schheifengrenze von _L1 */
05: x7 - 101 x9 <= 0; /* Randbedingung für obere Schheifengrenze von _L1 */
06: x0 - x4 = 0;
/* CFG Start-Randbedingung */
07: x2 - x4 = 0;
/* Randbedingung für FFuss nach _main */
08: x2 - x6 = 0;
/* Randbedingung für FFuss von _main */
09: ...
Zeile 01 enthält die Zielfunktion. Alle anderen Zeilen enthalten Randbedingungen, welche die Struktur des Graphen modellieren. Beispielsweise sind die Randbedingungen für den Knoten _L1 in den Zeilen 02 und 03 angegeben. Die Häufigkeit
des Verzweigens in diesen Knoten (x6+x8) ist gleich der Anzahl der Ausführungen
(x7). Die Häufigkeit des Verlassens dieses Knotens (x9+x10) ist ebenfalls gleich der
Anzahl der Ausführungen (x7). Die Zeilen 04 und 05 korrespondieren zu den Schleifeniterationen. Die Anzahl der Iterationen wurde dem Pragma im Code entnommen.
Zeile 06 sagt aus, dass die Anzahl der Ausführungen des start-Knotens gleich der
Anzahl der Verzweigungen in den Code ist. Die übrigen Zeilen beschreiben die
Struktur in ähnlicher Weise.
∇
Das so definierte ILP-Problem kann mit einem Standard-ILP-Solver, der die Zielfunktion maximiert, gelöst werden. Das so berechnete Maximum ist eine sichere
obere Schranke für die gesamte Ausführungszeit.
Diese Technik der Modellierung von Ausführungszeiten heißt Implicit Path Enumeration Technique (IPET) [344]. Sie vermeidet eine vollständige Aufzählung aller
möglichen Ausführungspfade. Eine solche Aufzählung würde zu i.d.R. zu sehr vielen
Pfaden führen.
In aiT ist auch eine Visualisierung der Ergebnisse in Form annotierter Kontrollflussgraphen verfügbar. Der Entwickler kann diese Graphen analysieren, um das zu
entwerfende System zu optimieren. aiT besitzt eine Reihe von Einschränkungen, die
sich aus dem beschriebenen Vorgehen erklären lassen: so werden keine Verdrängungen durch andere Prozesse, keine Hardware-Unterbrechungen, keine Ein/Ausgaben,
keine direkten Speichertransfers (DMA) und keine Interferenzen durch andere Hardwarekomponenten betrachtet.
Für die WCET-Analyse von Mehrkern-Systemen existieren nur wenige Ansätze [265, 266, 287]. Mit neuen probabilistischen Methoden [2] sollen existierende
Ansätze ergänzt werden. Sie basieren meist auf der Extremwerttheorie [196].