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

• entweder durch eine äquivalente Schleife ersetzt, die mehrere Kopien des Schleifenrumpfes enthält und dafür eine geringere Anzahl an Durchläufen hat,
• oder komplett aufgelöst, indem der Schleifenrumpf so oft aneinandergereiht wird, wie die ursprüngliche Anzahl Durchläufe war.

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

• die Anzahl der Schleifendurchläufe bei der Übersetzung noch nicht bekannt ist (siehe hierzu auch Duff’s Device),
• der Schleifenrumpf zu lang oder die Anzahl der Iterationen zu hoch ist, d. h. der erzeugte Maschinencode zu groß würde.

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

• Weniger auszuführende Befehle: Durch den Wegfall oder das seltenere Ausführen der Kontrollanweisungen sinkt die Ausführungszeit.
• Verbesserte Registerzuteilung: Der Schleifenzähler muss seltener oder gar nicht mehr in ein Register geladen werden. Dadurch stehen mehr Register für andere Berechnungen zur Verfügung.
• Latenzverdeckung (englisch „Latency hiding“): Tritt eine Verzögerung durch Zugriff auf einen langsameren Speicher auf, kann der nächste (entrollte) Durchlauf begonnen oder sogar parallel abgearbeitet werden (Pipelining).
• Entfernen von gemeinsam verwendetem Code (englisch „common subexpression elimination“): Mehrfache Berechnungen des gleichen Wertes können entfernt werden.
• Vektorisierung: Die Anweisungen können vektorisiert werden, d. h. mehrere Berechnungen können innerhalb eines Befehls zusammengefasst werden (z. B. von SSE).
• optimierter Speicherzugriff: Speicherzugriffe können so umgeordnet werden, dass sie das Prefetching des Prozessors oder Write-Through des Caches besser berücksichtigen.

Nachteile

• Manuelles Entrollen verschlechtert meist die Lesbarkeit des Quelltextes.
• Die Größe des Programms wächst, da die Anzahl der Instruktionen steigt. Es muss berücksichtigt werden, dass die Wahrscheinlichkeit steigt, dass Programmteile aus dem Befehlscache verdrängt werden und das langsame Nachladen den Geschwindigkeitsvorteil kompensiert.
• Evtl. können nicht mehr alle von der Schleife benötigten Variablen in Registern gespeichert werden, insbesondere bei registerarmen Architekturen wie z. B. x86. Dann muss auf den Hauptspeicher (oder den Prozessorcache) ausgewichen werden, der meist langsamer ist.

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,

• je komplexer die Schleife ist (komplexe Berechnungen, viele Daten, innere Schleifen, abhängige Anzahl an Durchläufen),
• wenn bedingte Anweisungen ausgeführt werden (Kontrollflussabhängigkeiten) oder
• wenn (teilweise) rekursive Berechnungen durchgeführt werden (Datenflussabhängigkeiten).

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 (i² + j²) sowohl vom äußeren als auch vom inneren Schleifenindex abhängt. Von Hand lässt sich diese Schleife problemlos entrollen.

Siehe auch

• Duff’s Device

Weblinks

• Intel 64 and IA-32 Architectures Software Developer Manuals, Intel 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes:1, 2A, 2B, 2C, 3A, 3B, and 3C (PDF; 15,4 MB)
• AMD Developer Central: Developer Guides & Manuals, Software Optimization Guide for AMD Family 15h Processors (PDF; 2,0 MB)
• Kapitel 7, S. 8–10. (PDF; 2,2 MB), Michael Abrashs Graphics Programming Black Book mit einem Loop unrolling Beispiel in x86 Assembler (englisch)
• Optimizing subroutines in assembly language (PDF; 1,4 MB) Agner Fogs Optimierungshandbuch u. a. mit der Loop unrolling-Technik (englisch, 2012)