382
7 Optimierung
sein, in denen das Abrollen an sich keine direkten Vorteile bietet. Allerdings
erhöht sich die Codegröße durch das Abrollen. Abrollen ist normalerweise auf
Schleifen mit einer festen Anzahl an Iterationen beschränkt.
• Schleifenfusion, Schleifenaufspaltung: Es kann Fälle geben, in denen zwei
getrennte Schleifen zusammengeführt werden können sowie Fälle, in denen eine
einzelne Schleife in zwei separate aufgeteilt wird.
Beispiel 7.3: Dieses Beispiel zeigt zwei Versionen eines Softwarecodes:
for (j=0; j
{p[j]= ... ;
for (j=0; j
p[j]=p[j]+ ...}
p[j]=p[j]+ ...
Die links dargestellte Version kann Vorteile bringen, wenn der Zielprozessor
einen Schleifenbefehl zur Realisierung von Schleifen ohne Overhead (engl. zerooverhead loop instruction) besitzt, der aber nur für kleine Schleifen genutzt werden kann. Die rechte Version kann zu einem verbesserten Cacheverhalten führen
(durch die verbesserte Lokalität der Referenzen auf das Array p) und vergrößert
zudem das Potential für parallele Berechnungen innerhalb des Schleifenkörpers.
Wie bei vielen anderen Transformationen auch, ist es schwierig zu erkennen,
welche der Transformationen den besten Code ergibt.
∇
7.1.2 Kachel-/Blockweise Verarbeitung von Schleifen
Da kleine Speicher schneller als große Speicher sind (siehe Seite 186), kann die
Verwendung von Speicherhierarchien vorteilhaft sein. Mögliche „kleine” Speicher
sind Caches und Scratchpad-Speicher (SPMs). Informationen in diesen Speichern
sollten einen hohen Wiederverwendungsgrad aufweisen, da die Speicherhierarchie
sonst nicht effizient ausgenutzt werden kann.
Beispiel 7.4: Wiederverwendungseffekte lassen sich an einer Analyse des folgenden
Beispiels zeigen. Wir betrachten eine Matrixmultiplikation für Felder der Größe N
× N [321]:
for (i=0; i
r=0;
for (k=0; j
Z[i][j]=r;
}
Wir betrachten die Zugriffsmuster für diesen Code. Die skalare Variable r repräsentiert Z[i,j] in allen Iterationen der innersten Schleife. Wir nehmen an, dass die
7 Optimierung
sein, in denen das Abrollen an sich keine direkten Vorteile bietet. Allerdings
erhöht sich die Codegröße durch das Abrollen. Abrollen ist normalerweise auf
Schleifen mit einer festen Anzahl an Iterationen beschränkt.
• Schleifenfusion, Schleifenaufspaltung: Es kann Fälle geben, in denen zwei
getrennte Schleifen zusammengeführt werden können sowie Fälle, in denen eine
einzelne Schleife in zwei separate aufgeteilt wird.
Beispiel 7.3: Dieses Beispiel zeigt zwei Versionen eines Softwarecodes:
for (j=0; j
{p[j]= ... ;
for (j=0; j
p[j]=p[j]+ ...}
p[j]=p[j]+ ...
Die links dargestellte Version kann Vorteile bringen, wenn der Zielprozessor
einen Schleifenbefehl zur Realisierung von Schleifen ohne Overhead (engl. zerooverhead loop instruction) besitzt, der aber nur für kleine Schleifen genutzt werden kann. Die rechte Version kann zu einem verbesserten Cacheverhalten führen
(durch die verbesserte Lokalität der Referenzen auf das Array p) und vergrößert
zudem das Potential für parallele Berechnungen innerhalb des Schleifenkörpers.
Wie bei vielen anderen Transformationen auch, ist es schwierig zu erkennen,
welche der Transformationen den besten Code ergibt.
∇
7.1.2 Kachel-/Blockweise Verarbeitung von Schleifen
Da kleine Speicher schneller als große Speicher sind (siehe Seite 186), kann die
Verwendung von Speicherhierarchien vorteilhaft sein. Mögliche „kleine” Speicher
sind Caches und Scratchpad-Speicher (SPMs). Informationen in diesen Speichern
sollten einen hohen Wiederverwendungsgrad aufweisen, da die Speicherhierarchie
sonst nicht effizient ausgenutzt werden kann.
Beispiel 7.4: Wiederverwendungseffekte lassen sich an einer Analyse des folgenden
Beispiels zeigen. Wir betrachten eine Matrixmultiplikation für Felder der Größe N
× N [321]:
for (i=0; i
r=0;
for (k=0; j
Z[i][j]=r;
}
Wir betrachten die Zugriffsmuster für diesen Code. Die skalare Variable r repräsentiert Z[i,j] in allen Iterationen der innersten Schleife. Wir nehmen an, dass die