7.1 High-Level-Optimierungen
381
Für ein derartiges Layout ist es üblicherweise vorteilhaft, Schleifen so zu organisieren, dass der letzte Index der innersten Schleife entspricht. So werden die
Zugriffe auf den Speicher möglichst lokal gehalten. Dagegen ist die Anordnung
von Feldern in FORTRAN unterschiedlich: hier werden benachbarte Werte des
ersten Indexes in einen zusammenhängenden Speicherblock abgebildet (im Englischen column-major order genannt). Veröffentlichungen, die Optimierungen
für FORTRAN beschreiben, können daher leicht verwirren.
Beispiel 7.1: Entsprechend dem jeweiligen Speicherlayout ist die nachfolgende
Schleifenpermutation geeignet, die Lokalität der Zugriffe auf den Speicher zu
erhöhen:
for (k=0; k
for (k=0; k
p[j][k]= ...
Diese Art von Permutationen kann eine positive Auswirkung auf die Wiederverwendung von im Cache befindlichen Feldelementen haben, da die folgende
Schleifeniteration auf eine benachbarte Speicherstelle zugreifen wird.
∇
Caches sind üblicherweise so organisiert, dass auf benachbarte Speicherstellen
wesentlich schneller zugegriffen werden kann als auf weiter von der vorherigen
Stelle entfernte Stellen. Auf diese Weise nutzen Caches eine räumliche Lokalität
der Speicherzugriffe.
Definition 7.1: Wir betrachten Speicherzugriffe auf Adressen a und b. Angenommen, es liegt ein Zugriff auf a vor. Räumliche Lokalität besteht, wenn
unter dieser Voraussetzung die Wahrscheinlichkeit eines Zugriffs auf b mit einem
kleinen Abstand der Adressen a und b wächst.
• Schleifen abrollen: Das Abrollen von Schleifen ist eine Standardtransformation,
die mehrere Instanzen des Schleifenkörpers erzeugt.
Beispiel 7.2: Dieses Beispiel zeigt eine einmal abgerollte Schleife:
for (j=0; j
p[j]= ... ;
⇔
{p[j]= ... ;
p[j+1]= ...}
∇
Die Anzahl der Kopien der Schleife wird Abrollfaktor genannt. Dabei sind Abrollfaktoren größer als zwei möglich. Das Abrollen verringert die Kosten der
Schleife (es sind weniger Sprünge pro Ausführung des ursprünglichen Schleifenkörpers erforderlich) und verbessert dadurch normalerweise die Performanz. Im
Extremfall können Schleifen vollständig abgerollt werden, was den Kontrollaufwand und Sprünge vollständig beseitigt. Abrollen ermöglicht üblicherweise eine
Reihe von Folgetransformationen und kann daher auch in den Fällen vorteilhaft
381
Für ein derartiges Layout ist es üblicherweise vorteilhaft, Schleifen so zu organisieren, dass der letzte Index der innersten Schleife entspricht. So werden die
Zugriffe auf den Speicher möglichst lokal gehalten. Dagegen ist die Anordnung
von Feldern in FORTRAN unterschiedlich: hier werden benachbarte Werte des
ersten Indexes in einen zusammenhängenden Speicherblock abgebildet (im Englischen column-major order genannt). Veröffentlichungen, die Optimierungen
für FORTRAN beschreiben, können daher leicht verwirren.
Beispiel 7.1: Entsprechend dem jeweiligen Speicherlayout ist die nachfolgende
Schleifenpermutation geeignet, die Lokalität der Zugriffe auf den Speicher zu
erhöhen:
for (k=0; k
for (k=0; k
p[j][k]= ...
Diese Art von Permutationen kann eine positive Auswirkung auf die Wiederverwendung von im Cache befindlichen Feldelementen haben, da die folgende
Schleifeniteration auf eine benachbarte Speicherstelle zugreifen wird.
∇
Caches sind üblicherweise so organisiert, dass auf benachbarte Speicherstellen
wesentlich schneller zugegriffen werden kann als auf weiter von der vorherigen
Stelle entfernte Stellen. Auf diese Weise nutzen Caches eine räumliche Lokalität
der Speicherzugriffe.
Definition 7.1: Wir betrachten Speicherzugriffe auf Adressen a und b. Angenommen, es liegt ein Zugriff auf a vor. Räumliche Lokalität besteht, wenn
unter dieser Voraussetzung die Wahrscheinlichkeit eines Zugriffs auf b mit einem
kleinen Abstand der Adressen a und b wächst.
• Schleifen abrollen: Das Abrollen von Schleifen ist eine Standardtransformation,
die mehrere Instanzen des Schleifenkörpers erzeugt.
Beispiel 7.2: Dieses Beispiel zeigt eine einmal abgerollte Schleife:
for (j=0; j
⇔
{p[j]= ... ;
p[j+1]= ...}
∇
Die Anzahl der Kopien der Schleife wird Abrollfaktor genannt. Dabei sind Abrollfaktoren größer als zwei möglich. Das Abrollen verringert die Kosten der
Schleife (es sind weniger Sprünge pro Ausführung des ursprünglichen Schleifenkörpers erforderlich) und verbessert dadurch normalerweise die Performanz. Im
Extremfall können Schleifen vollständig abgerollt werden, was den Kontrollaufwand und Sprünge vollständig beseitigt. Abrollen ermöglicht üblicherweise eine
Reihe von Folgetransformationen und kann daher auch in den Fällen vorteilhaft