384
7 Optimierung
Die Optimierung des Wiederverwendungsfaktors war das Thema umfassender
Arbeiten. Die ursprünglichen Ansätze konzentrierten sich dabei auf die durch Kachelung erzielbaren Leistungsverbesserungen. Für Matrixmultiplikation wurde eine
Leistungsverbesserung um einen Faktor von 3 bis 4,3 von Lam [321] berichtet.
Weitere Verbesserungen ergeben sich bei größerem Abstand zwischen Prozessorund Speichergeschwindigkeiten. Kachelung kann zudem eingesetzt werden, um den
Energieverbrauch von Speichersystemen zu senken [103].
7.1.3 Aufteilen von Schleifen
Im Folgenden betrachten wir die Schleifenaufteilung (engl. loop splitting) als eine
weitere Optimierung, die vor dem Compilieren eines Programms angewendet werden
kann. Diese Optimierung könnte möglicherweise auch Bestandteil eines Compilers
sein.
Viele Bildverarbeitungsalgorithmen verwenden Filter. Diese Filterung besteht
vielfach aus der Betrachtung von Informationen über ein bestimmtes Pixel und einige von dessen Nachparpixeln. Die zugehörigen Berechnungen sind normalerweise
recht regulär. Wenn das zu betrachtende Pixel sich aber nahe des Randes eines
Bildes befindet, existieren nicht alle benötigten Nachbarpixel und die Berechnungen müssen entsprechend angepasst werden. In einer einfachen Beschreibung des
Filteralgorithmus können diese Modifikationen zur Folge haben, dass Tests in der
innersten Schleife des Algorithmus durchgeführt werden müssen. Eine effizientere
Version des Algorithmus kann erzeugt werden, indem die Schleifen so aufgespalten werden, dass ein Schleifenkörper die regulären Fälle behandelt und ein zweiter
Schleifenkörper für die Ausnahmen zuständig ist. Abb. 7.4 ist eine graphische Darstellung dieser Transformation.
Viele if-Anweialle Pixel
prüfung, fast
Keine ÜberRandüberprüfung
weisungen zur
wenige Pixel
überprüfung,
Rand+
Abb. 7.4 Aufteilung des Bildverarbeitungsbeispiels in reguläre und spezielle Fälle
Die manuelle Aufteilung von Schleifen ist sehr kompliziert und fehleranfällig.
Falk et al. haben einen Algorithmus veröffentlicht [159], um diesen Vorgang auch für
größere Dimensionen zu automatisieren. Er basiert auf einer ausführlichen Analyse
von Zugriffen auf Arrayelementen innerhalb von Schleifen. Optimierte Lösungen
werden mit einer Polyederanalyse-Bibliothek [586] und genetischen Algorithmen
[341] erzeugt.
7 Optimierung
Die Optimierung des Wiederverwendungsfaktors war das Thema umfassender
Arbeiten. Die ursprünglichen Ansätze konzentrierten sich dabei auf die durch Kachelung erzielbaren Leistungsverbesserungen. Für Matrixmultiplikation wurde eine
Leistungsverbesserung um einen Faktor von 3 bis 4,3 von Lam [321] berichtet.
Weitere Verbesserungen ergeben sich bei größerem Abstand zwischen Prozessorund Speichergeschwindigkeiten. Kachelung kann zudem eingesetzt werden, um den
Energieverbrauch von Speichersystemen zu senken [103].
7.1.3 Aufteilen von Schleifen
Im Folgenden betrachten wir die Schleifenaufteilung (engl. loop splitting) als eine
weitere Optimierung, die vor dem Compilieren eines Programms angewendet werden
kann. Diese Optimierung könnte möglicherweise auch Bestandteil eines Compilers
sein.
Viele Bildverarbeitungsalgorithmen verwenden Filter. Diese Filterung besteht
vielfach aus der Betrachtung von Informationen über ein bestimmtes Pixel und einige von dessen Nachparpixeln. Die zugehörigen Berechnungen sind normalerweise
recht regulär. Wenn das zu betrachtende Pixel sich aber nahe des Randes eines
Bildes befindet, existieren nicht alle benötigten Nachbarpixel und die Berechnungen müssen entsprechend angepasst werden. In einer einfachen Beschreibung des
Filteralgorithmus können diese Modifikationen zur Folge haben, dass Tests in der
innersten Schleife des Algorithmus durchgeführt werden müssen. Eine effizientere
Version des Algorithmus kann erzeugt werden, indem die Schleifen so aufgespalten werden, dass ein Schleifenkörper die regulären Fälle behandelt und ein zweiter
Schleifenkörper für die Ausnahmen zuständig ist. Abb. 7.4 ist eine graphische Darstellung dieser Transformation.
Viele if-Anweialle Pixel
prüfung, fast
Keine ÜberRandüberprüfung
weisungen zur
wenige Pixel
überprüfung,
Rand+
Abb. 7.4 Aufteilung des Bildverarbeitungsbeispiels in reguläre und spezielle Fälle
Die manuelle Aufteilung von Schleifen ist sehr kompliziert und fehleranfällig.
Falk et al. haben einen Algorithmus veröffentlicht [159], um diesen Vorgang auch für
größere Dimensionen zu automatisieren. Er basiert auf einer ausführlichen Analyse
von Zugriffen auf Arrayelementen innerhalb von Schleifen. Optimierte Lösungen
werden mit einer Polyederanalyse-Bibliothek [586] und genetischen Algorithmen
[341] erzeugt.