Wie funktioniert aiT?

Die WCET-Berechnung erfolgt in mehreren Schritten:

1. Rekonstruktion des Kontrollflusses aus den ausführbaren Binärdateien des zu analysierenden Systems
2. Value-Analyse: Bestimmung von Schleifengrenzen und Berechnung von Adreßbereichen für Instruktionen, die auf den Speicher zugreifen
3. Cache-Analyse: Klassifizierung der Speicherzugriffe als Cache-Treffer oder Cache-Verfehlen
4. Pipeline-Analyse: Vorausberechnung des Verhaltens der Prozessor-Pipeline
5. Pfadanalyse: Bestimmung des Worst-Case-Ausführungspfades

Bei modernen Mikroprozessoren sind viele dieser Teilaufga­ben sehr komplex.

Die Anordnung der einzelnen Schritte ist in dem etwas ver­einfachten Bild rechts zu sehen. Die Ergebnisse der Value-Analyse werden von der Cache-Analyse gebraucht, um das Verhalten des (Daten-)Cache vorherzusagen. Die Ergebnisse der Cache-Analyse werden wiederum an die Pipeline-Analyse weitergereicht, um Pipeline-Staus aufgrund von Cache-Verfehlen vorherzusagen. Die kombinierten Ergebnisse der Cache- und der Pipeline-Analyse werden benutzt, um die Aus­führungs­zeit der einzelnen Programm­pfade zu berechnen.

Die Unterteilung der WCET-Bestimmung in einzelne Schritte hat den Vorteil, daß in jedem Schritt eigene, speziell für die­sen Schritt optimierte Analyse­methoden zum Einsatz kom­men können. Die Value-, Cache- und Pipeline-Analyse basie­ren auf der sogenannten abstrakten Interpretation. Die Pfad­analyse erfolgt durch ganzzahlige lineare Optimierung (ILP).

Rekonstruktion des Kontrollflusses aus Binärdateien

Der Ausgangspunkt der WCET-Analyse ist ein von einem Compiler erzeugtes ausführ­bares Bi­närprogramm sowie optional durch den Systementwickler gemachte Zusatzangaben, z. B. zur An­zahl der möglichen Schleifendurchläufe, Obergrenzen für Rekursionen, udgl.

Im ersten Schritt liest aiT das zu analysierende Programm und rekonstruiert daraus den Kon­trollfluß. Dies erfordert einige Kenntnisse über die zugrundeliegende Hardware – z. B., welche Instruktionen Verzweigungen oder Aufrufe darstellen. Der rekonstruierte Kontrollfluß wird mit eini­gen Zusatzinformationen versehen, die von den nachfolgenden Analysen gebraucht werden. An­schließend wird der Kontrollfluß in das Zwischenformat CRL (Control Flow Representation Language) übersetzt, das speziell entwickelt wurde, um Analysen und Optimierungen auf der Ausführungsebene zu vereinfachen. Der annotierte Kontrollflußgraph im CRL-Format dient als Eingabe für die darauffolgenden Analysen.

Value-Analyse

Die Value-Analyse bestimmt die Wertebereiche von Registerwerten und Speicherzellen. Dies ermöglicht die Bestimmung von Schleifen­grenzen und die Auflösung von indirekten Speicher­zugriffen. Mit dem optionalen ValueAnalyzer-Zusatz­modul können Sie diese Ergebnisse interaktiv erkunden – alle Register- und Speicherzellen­inhalte, für jede Instruktion, in jedem Ausführungs­kontext.

Cache-Analyse

In diesem Teilschritt wird für jeden Speicherzugriff in jedem möglichen Ausführungs­szenario überprüft, ob die be­nötigten Daten im Cache vorhanden sind. Dabei werden alle Speicher­zugriffe in die folgenden Kategorien unterteilt:

Für bestimmte Prozessoren berechnet aiT darüberhinaus Unterbrechungskosten durch Cache-Effekte. Dies ge­schieht mittels der sogenan­nten UCB-Analyse.

Pipeline-Analyse

In diesem Teilschritt wird das Verhalten der Mikroprozes­sor-Pipeline formal model­liert, um die Ausführungs­zeit von einzel­nen Instruktionen und von Fluß­sequenzen (Basis­blöcken) zu bestimmen. Dabei wird stets der aktu­elle Pipeline-Zustand be­rücksichtigt, insbesondere die Ressourcen­belegung, der aktu­elle Inhalt der Prefetch-Queue, die Grup­pierung der Instruk­ti­onen und die Klassifi­zierung der Speicher­zugriffe als Cache-Hits oder -Misses. Das Ergebnis der Analyse ist die Ausfüh­rungszeit einer jeden Instruktion in jedem einzelnen Ausführungs­kontext.

Pfad-Analyse

Basierend auf den Ergebnissen der Mikroarchitektur-Analysen liefert die Pfad-Analyse eine sichere Vorher­sage der WCET. Dazu wird der Kontroll­fluß des Programms mithilfe der ganz­zahligen linearen Optimierung modelliert. Für jede Basisblock­kante wird die Anzahl ihrer Durch­läufe berechnet.

Spezialbehandlung für Schleifen und rekursive Prozeduren

Schleifen und rekursive Prozeduren sind vom besonderen Interesse, da sie für den größten Teil der Aus­führung­szeit verantwortlich sind. Sie erfordern eine Spezial­behandlung – andernfalls leidet die Genauigkeit der Cache- und Pipe­line-Analyse-Ergebnisse ganz erheblich.

In der Regel werden beim ersten Durchlauf einer Schleife die benötigten Daten erst in den Cache geladen, während alle nach­folgenden Durchläufe die meisten dieser Daten bereits im Cache vor­finden. Somit unter­scheidet sich der Cache-Kontext des ersten Schleifen­durchlaufs in aller Regel ganz erheblich von dem Kontext aller anderen Durchläufe.

Naive Analyse-Methoden ignorieren diese Tatsache und fassen einfach den abstrakten Cache-Zustand vor dem Ein­tritt in die Schleife mit dem abstrakten Zustand nach deren Verlassen zusammen. Wichtige Informationen über das eigentliche Verhalten des Systems in der Schleife gehen dabei verloren.

aiT hingegen implementiert die sogenannte „VIVU“-Methode (virtual inlining, virtual unrolling) zum virtuellen Abrollen der Schleifen. Damit können Speicherzugriffe in den unterschiedlichen Aus­führungs­kontexten der ein­zelnen Schlei­fen­durch­läufe analysiert werden.