400
7 Optimierung
Beispiel 7.9:
Speichern(A);
Laden(A)
Laden(T3);
Definiere A
Modifiziere A
Benutze A
Benutze A
Benutze T3
Benutze T3
SPM-Größe=|A|=|T3|
T3
B10
B9
B6
B5
B8
B7
B4
B3
B2
B1
Abb. 7.15 Potentielles Freiräumen des Speichers
In Abb. 7.15 betrachten wir Basisblöcke B1 bis B10 und eine Verzweigung
des Kontrollflusses bei B2. Wir nehmen an, dass das Feld A im linken Pfad
definiert, modifiziert und benutzt wird.
T3 wird nur im rechten Pfad benutzt.
Wir betrachten das potentielle Freiräumen des SPMs, sodass T3 lokal dem
SPM zugewiesen werden kann. Dies
erfordert Operationen zum Freiräumen
und zum Laden in potentiell einzufügenden Blöcken B9 und B10 (rote gepunktete Linien: potentielle Einfügungen). Kosten und Nutzen dieser Operationen werden anschließend in ein globales ILP-Modell übernommen. Eine
Lösung dieses Modells stellt eine optimale Menge von Kopieroperationen dar. ∇
Verglichen mit dem nicht-überlagernden Fall wurde für eine Menge an Benchmarks
eine durchschnittliche Reduktion des Energieverbrauchs um 34% und der Ausführungszeit von 18% beobachtet.
Der Algorithmus von Udayakumararan ist ähnlich, aber er bewertet Speicherobjekte anhand des Quotienten aus der Anzahl der Speicherzugriffe und der Größe der
Objekte.
Schwierigkeiten ergeben sich bei der Zuordnung großer Felder zu SPMs. Tatsächlich kann schon ein einzelnes Feld zu groß sein, um einem SPM zugeordnet
zu werden. Eine einzelne Aufspaltung eines größeren Feldes kann mit der Strategie von Verma et al. [160] vorgenommen werden. Loop tiling ist eine allgemeinere
Technik, die entweder manuell oder automatisch eingesetzt werden kann [343]. Außerdem können Werte von Feldindices im Detail analysiert werden, um so häufig
verwendete Elemente von Feldern im SPM zu halten [358].
Unsere Erklärungen betrafen bislang v.a. Code und globale Daten. Der Stack
und der Heap benötigen besondere Aufmerksamkeit. In beiden Fällen können sehr
einfache Lösungen möglich sein: In manchen Fällen wird man es vielleicht vorziehen,
Stack oder Heap-Elemente nicht dem SPM zuzuordnen. In anderen Fällen können
wir eine Analyse der Größe des Stacks [5] oder des Heaps ausführen [220], um zu
prüfen, ob diese vollständig in den SPM passen und, falls dies der Fall ist, dem SPM
zuweisen.
Für den Heap haben Dominguez et al. [134] vorgeschlagen, die Lebendigkeit von
Heap-Objekten zu überprüfen und so nicht benötigte Objekte von der Speicherverwaltung auszuschließen. Wann auch immer ein Objekt potentiell benötigt wird, wird
Code erzeugt, der sicherstellt, dass sich dieses Objekt im SPM befindet. Die Objekte
befinden sich immer an derselben Adresse im SPM, sodass das Problem der potentiell
ungültigen Speicheradressen vermieden wird. McIllroy et al. [385] schlagen eine dy-
7 Optimierung
Beispiel 7.9:
Speichern(A);
Laden(A)
Laden(T3);
Definiere A
Modifiziere A
Benutze A
Benutze A
Benutze T3
Benutze T3
SPM-Größe=|A|=|T3|
T3
B10
B9
B6
B5
B8
B7
B4
B3
B2
B1
Abb. 7.15 Potentielles Freiräumen des Speichers
In Abb. 7.15 betrachten wir Basisblöcke B1 bis B10 und eine Verzweigung
des Kontrollflusses bei B2. Wir nehmen an, dass das Feld A im linken Pfad
definiert, modifiziert und benutzt wird.
T3 wird nur im rechten Pfad benutzt.
Wir betrachten das potentielle Freiräumen des SPMs, sodass T3 lokal dem
SPM zugewiesen werden kann. Dies
erfordert Operationen zum Freiräumen
und zum Laden in potentiell einzufügenden Blöcken B9 und B10 (rote gepunktete Linien: potentielle Einfügungen). Kosten und Nutzen dieser Operationen werden anschließend in ein globales ILP-Modell übernommen. Eine
Lösung dieses Modells stellt eine optimale Menge von Kopieroperationen dar. ∇
Verglichen mit dem nicht-überlagernden Fall wurde für eine Menge an Benchmarks
eine durchschnittliche Reduktion des Energieverbrauchs um 34% und der Ausführungszeit von 18% beobachtet.
Der Algorithmus von Udayakumararan ist ähnlich, aber er bewertet Speicherobjekte anhand des Quotienten aus der Anzahl der Speicherzugriffe und der Größe der
Objekte.
Schwierigkeiten ergeben sich bei der Zuordnung großer Felder zu SPMs. Tatsächlich kann schon ein einzelnes Feld zu groß sein, um einem SPM zugeordnet
zu werden. Eine einzelne Aufspaltung eines größeren Feldes kann mit der Strategie von Verma et al. [160] vorgenommen werden. Loop tiling ist eine allgemeinere
Technik, die entweder manuell oder automatisch eingesetzt werden kann [343]. Außerdem können Werte von Feldindices im Detail analysiert werden, um so häufig
verwendete Elemente von Feldern im SPM zu halten [358].
Unsere Erklärungen betrafen bislang v.a. Code und globale Daten. Der Stack
und der Heap benötigen besondere Aufmerksamkeit. In beiden Fällen können sehr
einfache Lösungen möglich sein: In manchen Fällen wird man es vielleicht vorziehen,
Stack oder Heap-Elemente nicht dem SPM zuzuordnen. In anderen Fällen können
wir eine Analyse der Größe des Stacks [5] oder des Heaps ausführen [220], um zu
prüfen, ob diese vollständig in den SPM passen und, falls dies der Fall ist, dem SPM
zuweisen.
Für den Heap haben Dominguez et al. [134] vorgeschlagen, die Lebendigkeit von
Heap-Objekten zu überprüfen und so nicht benötigte Objekte von der Speicherverwaltung auszuschließen. Wann auch immer ein Objekt potentiell benötigt wird, wird
Code erzeugt, der sicherstellt, dass sich dieses Objekt im SPM befindet. Die Objekte
befinden sich immer an derselben Adresse im SPM, sodass das Problem der potentiell
ungültigen Speicheradressen vermieden wird. McIllroy et al. [385] schlagen eine dy-