Loop unrolling

Loop unrolling (manchmal auch Loop unwinding), das „Strecken zyklischer Rechenpläne“ oder „Strecken einer Schleife“, ist eine Optimierungsmethode, die die Laufzeit eines Computerprogramms auf Kosten der Größe seiner Programmdatei beschleunigen kann. Dabei wird eine Schleife

Dadurch wird die Schleifenbedingung seltener oder gar nicht mehr überprüft. Es wird ferner oft ermöglicht, anschließend weitere Optimierungen des (entrollten) Schleifenrumpfes durchzuführen. Die Anzahl der Kopien des ursprünglichen Schleifenrumpfes wird Abrollfaktor (englisch unroll factor) genannt.

Moderne Compiler versuchen Schleifen automatisch zu entrollen, falls auf Geschwindigkeit optimiert werden soll. Ist bekannt, auf welcher Architektur genau ein Programm später ausgeführt wird, kann eine manuelle Optimierung jedoch überlegen sein.

Kommen die Wiederholungen durch Selbst-Aufrufe (Rekursionen) zustande, lassen sich durch Vervielfältigung des Prozedurrumpfes Prozeduraufrufe und -rücksprünge einsparen. In solchen Fällen spricht man von Recursion unrolling.

Idee

Die ursprüngliche Idee des Loop unrolling war es, das Verhältnis von Schleifenrumpf zu Schleifenkontrollanweisungen zu optimieren. Da heutige Prozessoren komplexe Mechanismen zur Optimierung des Programmflusses besitzen (z. B. Sprungvorhersage und Pipelining), kann der entrollte Schleifenrumpf noch weiter optimiert werden.

Ansatz

Bei einer Schleife muss bei jedem Durchlauf die sog. Schleifenbedingung geprüft werden, ob ein weiterer Durchlauf stattfinden soll. Gerade bei Schleifen mit sehr kleinem Rumpf kann diese Prüfung einen großen Anteil der Laufzeit ausmachen.

for( i=0 ; i<8 ; i=i+1 )
    dest[i] = src[i];

Eine solche Schleife besteht nur aus wenigen Anweisungen: Kopieren, Erhöhen des Zählers, Prüfen der Bedingung und ggf. ein Sprung. Somit verbringt der Prozessor etwa die Hälfte der Zeit nur mit Kontrollanweisungen.

Eine naheliegende Optimierung ist es, die Schleife durch n Kopien ihres Schleifenkörpers zu ersetzen (vollständiges Entrollen). Schleifenkontrollanweisungen und -zähler entfallen dann ganz:

dest[0] = src[0];
dest[1] = src[1];
dest[2] = src[2];
dest[3] = src[3];
dest[4] = src[4];
dest[5] = src[5];
dest[6] = src[6];
dest[7] = src[7];

Teilweises Entrollen

Wenn ein vollständiges Entrollen nicht möglich oder nicht sinnvoll ist, kann alternativ auch der ursprüngliche Schleifenrumpf mehrmals innerhalb einer Iteration ausgeführt werden (teilweises Entrollen). Dadurch sinkt die Anzahl der auszuführenden Kontrollanweisungen.

Dabei wird der ursprüngliche Schleifenrumpf durch eine weitere Schleife ersetzt, deren Durchläufe dem Abrollfaktor entsprechen (hier: 2):

for( i=0 ; i<8 ; i=i+2 ) {
    for( j=0; j<2; j=j+1 )
      dest[i+j] = src[i+j];
}

Anschließend wird die innere Schleife komplett entrollt:

for( i=0 ; i<8 ; i=i+2) {
    dest[i]   = src[i];
    dest[i+1] = src[i+1];
}

Ein teilweises Entrollen kann verwendet werden, wenn

Verschnitt

Dabei besteht immer die Möglichkeit, dass die Anzahl der ursprünglichen Iterationen kein ganzzahliges Vielfaches der Durchläufe der entrollten Schleife ist. Es verbleibt dann ein Rest bzw. ein partieller Durchlauf der entrollten Schleife, der gesondert behandelt werden muss.

Beispiel: Die Anzahl der Durchläufe ergebe sich erst zur Laufzeit, die ursprüngliche Schleife sei 10-fach entrollt worden (d. h. der ursprüngliche Schleifenkörper steht 10-mal im neuen Schleifenkörper). Zur Laufzeit ergibt sich, dass 1005 Iterationen berechnet werden sollen, also 100 Durchläufe, die 10-fach rechnen – bleibt (in diesem Programmlauf) ein Rest von 5 Iterationen.

Es können nun folgende Maßnahmen ergriffen werden:

  • Den Rest vollständig entrollen, sofern schon zum Übersetzungszeitpunkt die Anzahl der Schleifendurchläufe bekannt ist,
  • den Rest in einer eigenen Schleife einzeln verarbeiten (wie in der ursprünglichen Schleife),
  • den entrollten Schleifenrumpf nur teilweise ausführen (siehe Duff’s Device) oder
  • die zu verarbeitenden Daten auf ein ganzzahliges Vielfaches der inneren Schleife auffüllen.

Vorteile

Nachteile

Manuelles Abrollen

Wann genau ein manuelles Abrollen besser als die automatische Compiler-Optimierung ist, kann auf Grund der fortschreitenden Entwicklung nicht allgemein beschrieben werden. Im Zweifelsfall müssen Laufzeitmessungen vorgenommen werden.

Allgemein gilt, dass die automatische Optimierung erschwert wird,

Beispiel

Ein einfaches Beispiel, bei dem es heutigen Compilern (Stand: 2001) nicht gelingt, die Schleife automatisch zu entrollen, ist:

double sum = 0.0;

for (int i=0; i<n; ++i)
    for (int j=0; j<n; ++j)
        sum += x[i][j] * (i*i + j*j);

Der Grund ist, dass der Faktor (i2 + j2) sowohl vom äußeren als auch vom inneren Schleifenindex abhängt. Von Hand lässt sich diese Schleife problemlos entrollen.

Siehe auch

Einzelnachweise

  1. ↑ Rutishauser, Heinz: Automatische Rechenplanfertigung bei programmgesteuerten Rechenmaschinen. In: Mitteilungen aus dem Institut für angewandte Mathematik an der ETH Zürich. Birkhäuser, 1961, abgerufen am 6. Januar 2019.
  2. ↑ Bauer, F.L.; Wössner, H.: Algorithmische Sprache und Programmentwicklung. 2. Auflage. Springer, Berlin/Heidelberg/New York 1984, ISBN 3-540-12962-6, S. 287.
  3. ↑ Jeffrey D. Ullman, Alfred V. Aho: Principles of compiler design. Addison-Wesley, 1977, ISBN 0-201-10073-8.
  4. ↑ Steven S. Muchnick: Advanced Compiler Design & Implementation. Morgan Kaufmann Publishers, 1997, ISBN 1-55860-320-4.
  5. ↑ Intel 64 and IA-32 Architectures Optimization Reference Manual
  6. ↑ Intel C++ Compiler XE 13.0 User and Reference Guides: O
  7. ↑ GCC 4.7.2 Manual: Optimization Options
  8. 1 2 Mike Wall: Using Block Prefetch for Optimized Memory Performance. (PDF; 136 kB) mit.edu, 19. März 2002, archiviert vom Original (nicht mehr online verfügbar) am 30. August 2017; abgerufen am 22. September 2012 (englisch).  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  9. 1 2 Tom Duff on Duff’s Device auf www.lysator.liu.se (englisch)
  10. ↑ Agner Fog: Optimizing subroutines in assembly language. (PDF; 873 kB) Copenhagen University College of Engineering, 29. Februar 2012, S. 100, abgerufen am 22. September 2012 (englisch): „12.11 Loop unrolling“
  11. ↑ Stefan Goedecker, Adolfy Hoisie: Performance Optimization of Numerically Intensive Codes. SIAM, 2001, ISBN 978-0-89871-484-5, S. 59.