396
7 Optimierung
Dann ist das Ziel die Maximierung des Gewinns
G = g
i
n f i · x f i +
i
nv i · xv i
(7.3)
unter Berücksichtigung der Größenbeschränkung
i
s f i · x f i +
i
sv i · xv i ≤ S
(7.4)
Dieses Problem ist ein Rucksack-Problem (engl. knapsack problem). StandardKnapsack-Algorithmen können verwendet werden, um die dem SPM zuzuordnenden
Objekte auszuwählen. Die Gleichungen (7.3) und (7.4) haben aber auch die Form
eines Ganzzahligen Linearen Programmierungsproblems (ILP) (siehe Anhang A),
damit können ILP-Solver verwendet werden. Die entsprechende Optimierung kann
vor dem üblichen Übersetzungsvorgang durchgeführt werden (siehe Abb. 7.12).
to-sourceTransformation
Speicherhierarchiebeschreibung
(z.B. SPM-Größe)
Transformation
code
Quellcode
Maschinen(z.B. gcc)
Compiler
Die Optimierung betrifft Adressen von Funktionen und globalen Variablen. Üblicherweise ermöglichen Compiler es, diese Adressen manuell im Quellcode festzulegen. Daher sind keine Änderungen am Compiler selbst notwendig. Der Vorteil
solch einer Source-to-source-Transformation ist, dass sie mit Compilern für viele
verschiedene Zielprozessoren verwendet werden kann. Damit ist es nicht notwendig,
eine große Anzahl zielspezifischer Compiler abzuändern.
Dieses Modell lässt sich in verschiedene Richtungen erweitern:
• Zuordnung von Basisblöcken: Der gerade beschriebene Ansatz erlaubt es nur,
ganze Funktionen oder Variablen im SPM zu allozieren. Folglich kann ein großer
Teil des SPM ungenutzt bleiben, wenn Funktionen und Variablen groß sind. Daher versuchen wir, die Granularität der Objekte, die im SPM alloziert werden
können, zu reduzieren. Die naheliegende Wahl fällt dabei auf Basisblöcke als
Speicherobjekte. Zudem betrachten wir auch Mengen benachbarter Basisblöcke,
wobei „benachbart” definiert ist als zusammenhängende Teilgraphen im Kontrollflussgraphen. Wir nennen Blöcke, die aus zusammenhängenden Teilgraphen
entstehen, auch Multibasisblöcke [509]. Abb. 7.13 zeigt drei Multibasisblöcke
M12, M23 und M123 für die Basisblöcke BB1, BB2 und BB3.
Das ILP-Modell kann entsprechend erweitert werden. Seien:
7 Optimierung
Dann ist das Ziel die Maximierung des Gewinns
G = g
i
n f i · x f i +
i
nv i · xv i
(7.3)
unter Berücksichtigung der Größenbeschränkung
i
s f i · x f i +
i
sv i · xv i ≤ S
(7.4)
Dieses Problem ist ein Rucksack-Problem (engl. knapsack problem). StandardKnapsack-Algorithmen können verwendet werden, um die dem SPM zuzuordnenden
Objekte auszuwählen. Die Gleichungen (7.3) und (7.4) haben aber auch die Form
eines Ganzzahligen Linearen Programmierungsproblems (ILP) (siehe Anhang A),
damit können ILP-Solver verwendet werden. Die entsprechende Optimierung kann
vor dem üblichen Übersetzungsvorgang durchgeführt werden (siehe Abb. 7.12).
to-sourceTransformation
Speicherhierarchiebeschreibung
(z.B. SPM-Größe)
Transformation
code
Quellcode
Maschinen(z.B. gcc)
Compiler
Die Optimierung betrifft Adressen von Funktionen und globalen Variablen. Üblicherweise ermöglichen Compiler es, diese Adressen manuell im Quellcode festzulegen. Daher sind keine Änderungen am Compiler selbst notwendig. Der Vorteil
solch einer Source-to-source-Transformation ist, dass sie mit Compilern für viele
verschiedene Zielprozessoren verwendet werden kann. Damit ist es nicht notwendig,
eine große Anzahl zielspezifischer Compiler abzuändern.
Dieses Modell lässt sich in verschiedene Richtungen erweitern:
• Zuordnung von Basisblöcken: Der gerade beschriebene Ansatz erlaubt es nur,
ganze Funktionen oder Variablen im SPM zu allozieren. Folglich kann ein großer
Teil des SPM ungenutzt bleiben, wenn Funktionen und Variablen groß sind. Daher versuchen wir, die Granularität der Objekte, die im SPM alloziert werden
können, zu reduzieren. Die naheliegende Wahl fällt dabei auf Basisblöcke als
Speicherobjekte. Zudem betrachten wir auch Mengen benachbarter Basisblöcke,
wobei „benachbart” definiert ist als zusammenhängende Teilgraphen im Kontrollflussgraphen. Wir nennen Blöcke, die aus zusammenhängenden Teilgraphen
entstehen, auch Multibasisblöcke [509]. Abb. 7.13 zeigt drei Multibasisblöcke
M12, M23 und M123 für die Basisblöcke BB1, BB2 und BB3.
Das ILP-Modell kann entsprechend erweitert werden. Seien: