5.2 Performanzbewertung
269
zu Problemen der Analysierbarkeit von Hochsprachen-Code folgend, führt aiT die
Analyse auf einer ausführbaren Binärdatei des zu analysierenden Codes durch. Aus
diesem Code wird ein Kontrollflussgraph (engl. Control Flow Graph (CFG)) erzeugt.
Daraufhin werden Schleifentransformationen angewandt. Diese umfassen Transformationen zwischen Scheifen und rekursiven Funktionsaufrufen sowie das virtuelle
„Abrollen” von Schleifen (engl. loop unrolling). Dieses Abrollen ist „virtuell”, da
es nur intern stattfindet, ohne tatsächlich den ausführbaren Code zu verändern. Die
Ergebnisse werden im CRL-Format (engl. Control flow Representation Language)
dargestellt. Die nächste Phase setzt nun statische Analysen ein. Statische Analysen
lesen eine AIP-Datei mit Annotationen (Anmerkungen) des Entwicklers ein. Diese
Annotationen beschreiben schwer oder unmöglich automatisch aus der Programmstruktur zu ersehende Information (z.B. Schranken für komplexe Schleifen). Die
statischen Analysen bestehen aus Werte-, Cache- und Fließbandanalysen.
Eine Werteanalyse berechnet maximale Intervalle für Werte in Registern und
lokalen Variablen. Diese Angaben können für die Kontrollflussanalyse und die Datencacheanalyse verwendet werden. Häufig sind Werte wie Adressen genau bekannt
(besonders für „sauberen” Code). Dies erleichtert die Vorhersage von Speicherzugriffen sehr.
Die nächsten Schritte sind die Cache- und die Fließbandanalyse. Nachfolgend
beschreiben wir einige Details der Cacheanalyse. Wir gehen von einem n-fach mengenassoziativen Cache aus (siehe Abb. 5.6)1. Betrachten wir nun einen Teil (eine
Tag
Offset
Index
Adresse
Cache
mengenassoziativer
4-fach
=
=
=
=
innerhalb des Teilcaches
LRU-basierter Austausch
Abb. 5.6 n-fach mengenassoziativer Cache mit n=4
Zeile) des Caches mit einem bestimmten Index (in Abb. 5.6 fett und blau dargestellt).
Wir nehmen an, dass die Verdrängung aus dem Cache mittels der Least Recently
Used (LRU)-Strategie erfolgt. Damit werden für alle Zugriffe auf einen bestimmten Index die n Speicherblöcke, auf die zuletzt zugegriffen wurde, in diesem Teil
des Caches gespeichert. Dabei soll die erforderliche LRU-Verwaltungshardware für
1 Wir setzen voraus, dass der Leser mit dem Konzept von Caches vertraut ist.
269
zu Problemen der Analysierbarkeit von Hochsprachen-Code folgend, führt aiT die
Analyse auf einer ausführbaren Binärdatei des zu analysierenden Codes durch. Aus
diesem Code wird ein Kontrollflussgraph (engl. Control Flow Graph (CFG)) erzeugt.
Daraufhin werden Schleifentransformationen angewandt. Diese umfassen Transformationen zwischen Scheifen und rekursiven Funktionsaufrufen sowie das virtuelle
„Abrollen” von Schleifen (engl. loop unrolling). Dieses Abrollen ist „virtuell”, da
es nur intern stattfindet, ohne tatsächlich den ausführbaren Code zu verändern. Die
Ergebnisse werden im CRL-Format (engl. Control flow Representation Language)
dargestellt. Die nächste Phase setzt nun statische Analysen ein. Statische Analysen
lesen eine AIP-Datei mit Annotationen (Anmerkungen) des Entwicklers ein. Diese
Annotationen beschreiben schwer oder unmöglich automatisch aus der Programmstruktur zu ersehende Information (z.B. Schranken für komplexe Schleifen). Die
statischen Analysen bestehen aus Werte-, Cache- und Fließbandanalysen.
Eine Werteanalyse berechnet maximale Intervalle für Werte in Registern und
lokalen Variablen. Diese Angaben können für die Kontrollflussanalyse und die Datencacheanalyse verwendet werden. Häufig sind Werte wie Adressen genau bekannt
(besonders für „sauberen” Code). Dies erleichtert die Vorhersage von Speicherzugriffen sehr.
Die nächsten Schritte sind die Cache- und die Fließbandanalyse. Nachfolgend
beschreiben wir einige Details der Cacheanalyse. Wir gehen von einem n-fach mengenassoziativen Cache aus (siehe Abb. 5.6)1. Betrachten wir nun einen Teil (eine
Tag
Offset
Index
Adresse
Cache
mengenassoziativer
4-fach
=
=
=
=
innerhalb des Teilcaches
LRU-basierter Austausch
Abb. 5.6 n-fach mengenassoziativer Cache mit n=4
Zeile) des Caches mit einem bestimmten Index (in Abb. 5.6 fett und blau dargestellt).
Wir nehmen an, dass die Verdrängung aus dem Cache mittels der Least Recently
Used (LRU)-Strategie erfolgt. Damit werden für alle Zugriffe auf einen bestimmten Index die n Speicherblöcke, auf die zuletzt zugegriffen wurde, in diesem Teil
des Caches gespeichert. Dabei soll die erforderliche LRU-Verwaltungshardware für
1 Wir setzen voraus, dass der Leser mit dem Konzept von Caches vertraut ist.