[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

5.4 Schleifen-Transformation

Die Rechenzeit von Programmen in der Numerischen Datenverarbeitung ist hauptsächlich auf Schleifen zurückzuführen. Ein Lösungsansatz, der hier diskutiert werden soll, ist, Modifikationen im Bereich der Schleifen durchzuführen und an die Gegebenheiten (Rechnerstruktur, Art der internen Rechnungsdurchführung) anzupassen. Diese Veränderungen nennt man Schleifen-Transformationen.

5.4.1 Aufrollen von Schleifen

Unter Schleifen-Aufrollen versteht man eine Schleifentransformation, bei der wiederholte Teil mehrmals dupliziert wird und so die Schleife weniger Rechenschritte benötigt, weil die Prüfung der Schleifenbedingung beispielsweise statt bei jedem Durchgang nur jedes n-te mal vor sich geht.

Beispiel (SAXPY-Operation)
DO i = 1, n
  y(i) = y(i) + a*x(i)
END DO
Soll diese Schleife aufgerollt werden, ist es üblich, im folgenden Fall vom dreifachen aufrollen gesprochen.
Nrest = MOD(n,4)	Vorschleife, für die ersten 4 Elemente
DO i = 1, nrest
  y(i) = y(i) + a*x(i)
END DO
n1 = nrest + 1

DO i = n1, n, 4	3-fach aufgerollte Schleife, Aufrolltiefe 4
  y(i  ) = y(i  ) + a*x(i  )
  y(i+1) = y(i+1) + a*x(i+1)
  y(i+2) = y(i+2) + a*x(i+2)
  y(i+3) = y(i+3) + a*x(i+3)
END DO
Dieses Aufrollen hat mehrere Vorteile. Einerseits werden weniger Schleifendurchgänge benötigt und was sich vor allem bei einem großen n bemerkbar macht dadurch weniger Abbruchbedingungen zu prüfen sind. Viel wichtiger hingegen ist die Möglichkeit, stärker zu parallelisieren. Der Compiler kann bei der aufgerollten Schleife die einzelnen Schritte gleichzeitig berechnen lassen, da er erkennt, daß zwischen den Berechnungen keine Abhängigkeiten bestehen. Bei m-fach aufgerollten Schleifen kann es im Idealfall zu einer Erhöhung des Grades der Software-Parallelität um den Faktor m + 1 kommen, wenn es für den Compiler ersichtlich ist, daß m + 1 aufeinanderfolgende Operationen gleichzeitig ausgeführt werden können.

Gleitpunktleistung
Gleitpunktleistung
m-faches Schleifen-Aufrollen

Obige Grafik zeigt die Leistungssteigerung bei der Durchführung der SACPY-Operation mit m-fachen Aufrollen auf einem PC. Der Geschwindigkeitsgewinn resultiert vor allem daher, daß Daten, die für mehrere parallelisierte Operationen benötigt werden, im schnellen Cache oder gar im Register gehalten werden und nicht jedesmal aus dem langsamen" Hauptspeicher geholt werden. Ob und wie das Aufrollen von Schleifen eine Effizienzsteigerung mit sich bringt, hängt von mehreren Faktoren ab: Beispiel (Inneres Produkt)
summe = 0.
DO i = 1, n
  summe = summe + x(i)*y(i)
END DO
1-fach aufgerollt erhält man aufgrund der Abhängigkeit von summe keine Effizienzsteigerung (keine Parallelisierung möglich):
summe = 0.
DO i = 1, n, 2
  summe = summe + x(i  )*y(i  )
  summe = summe + x(i+1)*y(i+1)
END DO
Assoziative Transformation ist eine Möglichkeit, trotzdem zu parallelisieren. Aufrollen von Schleifen hat meist ein unübersichtlicheres, größeres Programm zur Folge. Oft gibt es auch schon fertige, rechnerspezifische, hochoptimierte Unterprogrammbibliotheken.
5.4.2 Aufrollen äußerer Schleifen Bei verschachtelten Schleifen kann man beliebige Schleifen aufrollen, mit den Vor- und Nachteilen wie man sie schon von den einfachen Schleifen her kennt. Nicht vom äußeren Schleifenindex abhängige Variablen im Schleifenrumpf wäre eine Motivation, eine äußere Schleife aufzurollen.

Beispiel (Aufrollen äußerer Schleifen)
DO j = 1, n
  DO i = 1, n
    a(i,j) = d*b(i,j) + c(i)
  END DO
END DO
c(i) hängt nicht vom äußeren Schleifenindex j ab:
DO j = 1, n, 2
  DO i = 1, n
    a(i,j  ) = d*b(i,j  ) + c(i)
    a(i,j+1) = d*b(i,j+1) + c(i)
  END DO
END DO

Gleitpunktleistung
Gleitpunktleistung
Auf einer HP-Workstation erhält man bei n = 90 eine Leistungssteigerung um 26%.

Eine Erhöhung der Referenzlokalität durch das Aufrollen äußerer Schleifen kann insbesonders dann oft erreicht werden, wenn sich der aufgerollte Algorithmus als Blockalgorithmus im Sinne der numerischen Linearen Algebra auffassen läßt.

5.4.3 Schleifenverschmelzung

Unter Verschmelzung von Schleifen (loop fusion) versteht man die Vereinigung von mehreren Schleifenrümpfen zu einem einzigen. Die Datentransfers vom und zum langsamen Hauptspeicher können veringert werden.

Beispiel (Schleifenverschmelzung)
DO i = 1, n
  x = x*a(i) + b(i)
END DO
DO j = 1, n
  y = y*a(j) + c(j)
END DO
Die zwei Schleifen werden zu einer Schleife zusammengefaßt,
DO i = 1, n
  x = x*a(i) + b(i)
  y = y*a(i) + c(i)
END DO
was den Vorteil hat, daß a(i) nur einmal anstatt zweimal aus dem Hauptspeicher geholt werden muß.

Cache leer Daten und Code im Cache
zwei getrennte Schleifen 5.6 Mflop/s (11.2%) 15.4 Mflop/s (30.8%)
Schleifenverschmelzung 6.8 Mflop/s (13.6%) 30.2 Mflop/s (60.4%)
Die Leistungsdaten auf einer HP-Workstation für n = 3000

Durch Schleifenverschmelzung kann sich auch eine Verschlechterung ergeben, wenn in den zusammengeschmolzenen Schleifen auf gänzlich verschiedene Felder zugegriffen wird.

5.4.4 Eliminieren von Verzweigungen in Schleifen

Verzweigungen sind zeitraubende Aktionen, die einer Parallelisierung entgegenwirken. Sie zu vermeiden kann sich auf die Effizienz wesentlich auswirken. Von schleifen-invarianten Verzweigungen spricht man dann, wenn das Ergebnis von der Schleifeniteration unabhänig ist. In diesem Fall kann man die Bedingung aus der Schleife herausziehen.

Beispiel (Schleifen-invariante Verzweigung)
DO i = 1, n
  IF (indikator > 0) THEN
    y(i) = y(i) + a*x(i) 
  ELSE
    y(i) = y(i) - a*x(i)
  END IF
END DO
Zieht man nun die Auswertung des logischen Ausdrucks indikator > 0 vor die DO-Schleife, erspart man sich n - 1 Abfragen.
IF (indikator > 0) THEN
  DO i = 1, n
    y(i) = y(i) + a*x(i) 
  END DO  
ELSE
  DO i = 1, n
    y(i) = y(i) - a*x(i)
  END DO
END IF
Cache leer Daten und Code im Cache
IF in der Schleife 7.2 Mflop/s (14.4%) 15.0 Mflop/s (30.0%)
IF außerhalb der Schleife 9.8 Mflop/s (19.6%) 34.8 Mflop/s (69.6%)
Die Leistungsdaten auf einer HP-Workstation für n = 3000

Von index-abhängigen Verzweigungen spricht man dann, wenn das Ergebnis der IF-Bedingung nur von Schleifenindex abhängt.

Beispiel (Index-abhängige Verzweigung)
DO i = 1, n
  IF (MOD(i,2) == 0) THEN
    y(i) = y(i) + a*x(i) 
  ELSE
    y(i) = y(i) - a*x(i)
  END IF
END DO
Der IF-Zweig wird nur bei geradem i durchlaufen, ansonsten der ELSE-Zweig. Das kann man auch besser formulieren.
DO i = 2, n, 2
  y(i) = y(i) + a*x(i) 
END DO
DO i = 1, n, 2
  y(i) = y(i) - a*x(i) 
END DO
Cache leer Daten und Code im Cache
IF in der Schleife 3.2 Mflop/s (6.4%) 5.9 Mflop/s(11.8%)
kein IF (zwei Schleifen) 4.9 Mflop/s (9.8%) 17.2 Mflop/s (34.4%)
Die Leistungsdaten auf einer HP-Workstation für n = 3000

Schließlich gibt es noch die schleifen-abhängigen Verzweigungen. Das Ergebnis dieser IF-Bedingungen ist von der jeweiligen Schleifeniteration abhängigen Daten abhängig. Im allgemeinen ist es nicht möglich, die Verzweigung aus der Schleife herauszuziehen.

Beispiel (Schleifen-abhängige Verzweigung)
DO i = 1, n
  IF (x(i) < 0) THEN
    y(i) = y(i) + a*x(i) 
  ELSE
    y(i) = y(i) - a*x(i)
  END IF
END DO
Statt der der umständlichen Realisierung der SAXPY-Operation (vom Vektor x sollen die Absolutbeträge genommen werden) könnte man eine äquivalente, effizientere Lösung realisieren:
DO i = 1, n
  y(i) = y(i) + a*ABS(x(i)) 
END DO
Cache leer Daten und Code im Cache
IF in der Schleife 3.2 Mflop/s (6.2%) 5.2 Mflop/s (10.4%)
kein IF 4.7 Mflop/s (9.4%) 15.1 Mflop/s (30.2%)
Die Leistungsdaten auf einer HP-Workstation für n = 3000

5.4.5 Assoziative Transformation

Unter assoziativen Transformationen versteht man Programmmodifikationen, die auf dem Assiotiativgesetz

(x ° y) ° z = x ° (y ° z)
beruhen. In der Mathematik gilt dieses Gesetz bekanntermaßen beispielsweise für die Addition und Multiplikation reeller Zahlen, nicht so im Computer. Durch die beschränkte Darstellungsmöglichkeit von Zahlen im Computer kommt es zu Rundungsfehlern. Daher führen Compiler in der Regel nur wirklich äquivalente Operationen durch; sonstige Transformationen müssen vom Programmierer in Anbetracht der Rundungsfehlereinflüsse getätigt werden. Assoziative Transformationen werden in erster Linie bei sogenannten Reduktionsoperationen angewendet. Von einer Reduktion spricht man im Zusammenhang mit Feldoperationen, wenn die Dimension der Resultatsfelder kleiner ist als die Dimension der Operandenfelder. Dabei werden oft Operandenfelder zunächst komponentenweise miteinander verknüpft und die Ergebnisfelder durch fortgesetzte Anwendung einer assoziativen Operation in ein Feld niedrigerer Dimension oder einen Skalar (ein Feld der Dimension 0) übergeführt. Durch geeignetet Klammerung der assoziativen Operationen kann man in diesem Fall die Anzahl der parallel ausführbaren Operationen erhöhen.

Beispiel (Inneres Produkt)
s = 0.
DO i = 1, n
  s = s + x(i)*y(i)
END DO
Dieses einfache Beispiel einer Reduktionsoperation ist das Skalarprodukt. Die Multiplikation mit anschließender Addition kann man aber auch zusammenfassen, gerades n vorausgesetzt.
x1y1 + x2y2 + ... + xnyn = (x1y1 + x3y3 + ... + x n-1y n-1) + (x2y2 + x4y4 + ... + xnyn)
Mit dieser Umformung ist es möglich, das Programm zu transformieren und dadurch effizienter zu machen:
s1 = 0.
S2 = 0.
DO i = 1, n, 2
  s1 = s1 + x(i  )*y(i  )
  s2 = s2 + x(i+1)*y(i+1) 
END DO
s = s1 + s2
Die Teilsummen s1 und s2 sind voneinander unabhängig, fördern also Parallelität.

Gleitpunktleistung
Gleitpunktleistung
Die Leistungsdaten auf einer HP-Workstation für n = 3000

Dem Programmierer obliegt die Entscheidung über die Optimierung von solcherlei Problemen unter Anbetracht der geänderten Rundungsfehlereinflüssen.

5.4.6 Schleifen-Vertauschung

Wenn Schleifen wiederum Schleifen enthalten - sogenannte Schleifenschachtelungen -, gibt es die Möglichkeit, die Verschachtelungsreihenfolge zu permutieren. Das hat zwei Zielsetzungen: Einerseits kann man durch geeignete Wahl der innersten Schleife eine Möglichkeit des Aufrollens schaffen und andererseits soll die Referenzlokalität der Speicherzugriffe durch eine kleine Schrittweite beim Zugriff auf die Elemente garantiert werden. Im Falle einer Matrix könnte man die transponierte Matrix bilden, und so eine effizientere Möglichkeit der Berechnung bekommen.

Beispiel (Schleifen-Vertauschung)
REAL, DIMENSION (idim, jdim, kdim) : feld
...
DO i = 1, idim
  DO j = 1, jdim
    DO k = 1, kdim
      feld(i,j,k) = a*feld(i,j,k) + b
    END DO
  END DO
END DO
Schleifenanordnung ijk ikj jik jki kij kji
Gleitpunktleistung [Mflop/s] 12.3 25.7 12.3 12.6 29.1 25.4
Die Leistungsdaten auf einer DEC-Workstation für idim=2, jdim=30, und kdim=800

In diesem Fall würde man natürlich die kji-Variante wählen, sie hat jedoch den Mangel, daß die innerste Schleife nur zwei mal aufgerufen wird. Es empfiehlt sich hier, die Schleife aufzurollen.

Markus Rossler


[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]