5.2 Performanzbewertung
271
{c}
{e}
{a}
{d}
{}
{}
{a,c} {d}
{d}
{c,f}
{}
{a}
Durchschnitt+maximales Alter
Abb. 5.9 Must-Analyse für LRU-Caches bei rekonvergenten Pfaden
nach der Rekonvergenz ist. Offensichtlich können wir nach der Rekonvergenz im
Cache mit Sicherheit nur solche Speicherobjekte finden, die sich in der Schnittmenge
der beiden ursprünglichen Cacheinhalte befanden. Als Alter müssen wir im Sinne
der worst case-Analyse das maximale Alter annehmen. Abb. 5.9 zeigt das Ergebnis.
Offensichtlich muss die Analyse für jeden Platz (jede Spalte) im Cache mit Mengen
möglicher Einträge arbeiten.
Betrachten wir nun die may-Analyse für rekonvergente Programmpfade. Abb.
5.10 zeigt wiederum die Situation. Im resultierenden Cache können nunmehr offen{c}
{e}
{a}
{d}
{}
{a,c}
{d}
{a}
{}
{c,f}
{d}
{e,f}
Vereinigung+minimales Alter
Abb. 5.10 May-Analyse für LRU-Caches bei rekonvergenten Pfaden
sichtlich Speicherobjekte vorhanden sein, die vor der Rekonvergenz in einem der
beiden Programmpfade vorhanden waren. Also müssen wir die Vereinigung der
Speicherobjekte betrachten. Im bestmöglichen Fall müssen wir von dem jüngsten
Alter der Speicherobjekte ausgehen. Abb. 5.10 zeigt das Ergebnis.
Zu den statischen Analysen zählen auch Fließbandanalysen. Eine Fließbandanalyse muss sichere Schranken für die Anzahl an Zyklen berechnen, die für die
Ausführung des Maschinencodes, der sich im Fließband des Prozessors befindet,
benötigt wird. Details der Fließbandanalyse werden von Hahn et al. [197] sowie S.
Thesing [534] beschrieben. Das Endergebnis statischer Analysen enthält Schranken
für die Ausführungszeiten für jeden Basisblock eines Programms. Die Ergebnisse
werden in einer PER-Datei abgelegt, wie in Abb. 5.5 zu sehen.
Die folgende Phase von aiT verwendet diese Schranken, um größtmögliche Ausführungszeiten für das gesamte Programm zu ermitteln. Dieser Schritt basiert auf
einem Modell der Ganzzahligen Linearen Programmierung (engl. integer linear
programming (ILP), siehe Anhang A). Dementsprechend enthält das Modell der
Ausführungszeiten zwei Typen von Information:
271
{c}
{e}
{a}
{d}
{}
{}
{a,c} {d}
{d}
{c,f}
{}
{a}
Durchschnitt+maximales Alter
Abb. 5.9 Must-Analyse für LRU-Caches bei rekonvergenten Pfaden
nach der Rekonvergenz ist. Offensichtlich können wir nach der Rekonvergenz im
Cache mit Sicherheit nur solche Speicherobjekte finden, die sich in der Schnittmenge
der beiden ursprünglichen Cacheinhalte befanden. Als Alter müssen wir im Sinne
der worst case-Analyse das maximale Alter annehmen. Abb. 5.9 zeigt das Ergebnis.
Offensichtlich muss die Analyse für jeden Platz (jede Spalte) im Cache mit Mengen
möglicher Einträge arbeiten.
Betrachten wir nun die may-Analyse für rekonvergente Programmpfade. Abb.
5.10 zeigt wiederum die Situation. Im resultierenden Cache können nunmehr offen{c}
{e}
{a}
{d}
{}
{a,c}
{d}
{a}
{}
{c,f}
{d}
{e,f}
Vereinigung+minimales Alter
Abb. 5.10 May-Analyse für LRU-Caches bei rekonvergenten Pfaden
sichtlich Speicherobjekte vorhanden sein, die vor der Rekonvergenz in einem der
beiden Programmpfade vorhanden waren. Also müssen wir die Vereinigung der
Speicherobjekte betrachten. Im bestmöglichen Fall müssen wir von dem jüngsten
Alter der Speicherobjekte ausgehen. Abb. 5.10 zeigt das Ergebnis.
Zu den statischen Analysen zählen auch Fließbandanalysen. Eine Fließbandanalyse muss sichere Schranken für die Anzahl an Zyklen berechnen, die für die
Ausführung des Maschinencodes, der sich im Fließband des Prozessors befindet,
benötigt wird. Details der Fließbandanalyse werden von Hahn et al. [197] sowie S.
Thesing [534] beschrieben. Das Endergebnis statischer Analysen enthält Schranken
für die Ausführungszeiten für jeden Basisblock eines Programms. Die Ergebnisse
werden in einer PER-Datei abgelegt, wie in Abb. 5.5 zu sehen.
Die folgende Phase von aiT verwendet diese Schranken, um größtmögliche Ausführungszeiten für das gesamte Programm zu ermitteln. Dieser Schritt basiert auf
einem Modell der Ganzzahligen Linearen Programmierung (engl. integer linear
programming (ILP), siehe Anhang A). Dementsprechend enthält das Modell der
Ausführungszeiten zwei Typen von Information: