Abwickeln der Schleife - Loop unrolling

Nicht zu verwechseln mit dem Abwickeln des Stapels .

Das Abrollen von Schleifen , auch als Abwickeln von Schleifen bezeichnet , ist eine Schleifentransformationstechnik , die versucht, die Ausführungsgeschwindigkeit eines Programms auf Kosten seiner Binärgröße zu optimieren . Dies ist ein Ansatz, der als Raum-Zeit-Kompromiss bezeichnet wird . Die Transformation kann manuell vom Programmierer oder von einem optimierenden Compiler durchgeführt werden . Auf modernen Prozessoren ist das Abrollen von Schleifen häufig kontraproduktiv, da die erhöhte Codegröße zu mehr Cache-Fehlern führen kann. vgl. Duffs Gerät .

Das Ziel des Abwickelns einer Schleife besteht darin, die Geschwindigkeit eines Programms zu erhöhen, indem Anweisungen, die die Schleife steuern, wie Zeigerarithmetik und "Ende der Schleife" -Tests bei jeder Iteration reduziert oder entfernt werden . Reduzierung der Zweigstrafen; sowie das Ausblenden von Latenzen, einschließlich der Verzögerung beim Lesen von Daten aus dem Speicher. Um diesen Rechenaufwand zu vermeiden , können Schleifen als wiederholte Folge ähnlicher unabhängiger Anweisungen neu geschrieben werden.

Das Abrollen von Schleifen ist auch Teil bestimmter formaler Verifikationstechniken , insbesondere der eingeschränkten Modellprüfung .

Vorteile

Der Overhead in "engen" Schleifen besteht häufig aus Anweisungen zum Inkrementieren eines Zeigers oder Index zum nächsten Element in einem Array ( Zeigerarithmetik ) sowie aus Tests zum Ende der Schleife. Wenn ein optimierender Compiler oder Assembler in der Lage ist, Offsets für jede einzeln referenzierte Array-Variable vorab zu berechnen , können diese direkt in die Maschinencode- Anweisungen integriert werden, sodass zur Laufzeit keine zusätzlichen arithmetischen Operationen erforderlich sind.

  • Signifikante Gewinne können erzielt werden, wenn die Reduzierung der ausgeführten Anweisungen eine Leistungsminderung kompensiert, die durch eine Vergrößerung des Programms verursacht wird.
  • Die Verzweigungsstrafe wird minimiert.
  • Wenn die Anweisungen in der Schleife unabhängig voneinander sind (dh wenn Anweisungen, die früher in der Schleife auftreten, keine Auswirkungen auf die darauf folgenden Anweisungen haben), können die Anweisungen möglicherweise parallel ausgeführt werden .
  • Kann dynamisch implementiert werden, wenn die Anzahl der Array-Elemente zur Kompilierungszeit unbekannt ist (wie bei Duffs Gerät ).

Beim Optimieren von Compilern wird das Abrollen manchmal automatisch oder auf Anfrage durchgeführt.

Nachteile

  • Erhöhte Programmcodegröße, was insbesondere für eingebettete Anwendungen unerwünscht sein kann. Kann auch zu einer Zunahme von Befehls-Cache-Fehlern führen, was die Leistung beeinträchtigen kann.
  • Wenn der Code nicht transparent von einem optimierenden Compiler ausgeführt wird, ist er möglicherweise weniger lesbar .
  • Wenn der Code im Hauptteil der Schleife Funktionsaufrufe enthält, ist es möglicherweise nicht möglich, das Abrollen mit dem Inlining zu kombinieren , da die Zunahme der Codegröße möglicherweise übermäßig ist. Somit kann es einen Kompromiss zwischen den beiden Optimierungen geben.
  • Möglicherweise erhöhte Registernutzung in einer einzelnen Iteration zum Speichern temporärer Variablen, was die Leistung verringern kann, obwohl vieles von möglichen Optimierungen abhängt.
  • Abgesehen von sehr kleinem und einfachem Code sind nicht gerollte Schleifen, die Zweige enthalten, noch langsamer als Rekursionen.

Abwickeln der statischen / manuellen Schleife

Beim manuellen (oder statischen) Abrollen der Schleife analysiert der Programmierer die Schleife und interpretiert die Iterationen in eine Folge von Anweisungen, wodurch der Schleifenaufwand verringert wird. Dies steht im Gegensatz zum dynamischen Abrollen, das vom Compiler durchgeführt wird.

Einfaches manuelles Beispiel in C.

Eine Prozedur in einem Computerprogramm besteht darin, 100 Elemente aus einer Sammlung zu löschen. Dies geschieht normalerweise über eine for -schleife, die die Funktion delete (item_number) aufruft . Wenn dieser Teil des Programms optimiert werden soll und der Overhead der Schleife im Vergleich zu denen für die Funktion delete (x) erhebliche Ressourcen erfordert , kann das Abwickeln verwendet werden, um ihn zu beschleunigen.

Normale Schleife Nach dem Abrollen der Schleife 
 int x;
 for (x = 0; x < 100; x++)
 {
     delete(x);
 }

 int x; 
 for (x = 0; x < 100; x += 5 )
 {
     delete(x);
     delete(x + 1);
     delete(x + 2);
     delete(x + 3);
     delete(x + 4);
 }

Infolge dieser Änderung muss das neue Programm nur 20 statt 100 Iterationen durchführen. Danach müssen nur noch 20% der Sprünge und bedingten Verzweigungen ausgeführt werden, was über viele Iterationen hinweg eine potenziell signifikante Abnahme der Verwaltungsaufwand für die Schleife. Um den optimalen Nutzen zu erzielen, sollten im nicht gerollten Code keine Variablen angegeben werden, die eine Zeigerarithmetik erfordern . Dies erfordert normalerweise eine Adressierung " Basis plus Versatz" anstelle einer indizierten Referenzierung.

Andererseits erweitert dieses manuelle Abrollen der Schleife die Quellcode-Größe von 3 Zeilen auf 7, die erstellt, überprüft und debuggt werden müssen, und der Compiler muss möglicherweise mehr Register zuweisen, um Variablen in der erweiterten Schleifeniteration zu speichern. Darüber hinaus müssen die Regelungsvariablen und die Anzahl der Operationen innerhalb der nicht gerollten Schleifenstruktur sorgfältig ausgewählt werden, damit das Ergebnis tatsächlich das gleiche wie im ursprünglichen Code ist (vorausgesetzt, dies ist eine spätere Optimierung des bereits funktionierenden Codes). Betrachten Sie beispielsweise die Auswirkungen, wenn die Anzahl der Iterationen nicht durch 5 teilbar war. Die erforderlichen manuellen Änderungen werden auch etwas komplizierter, wenn die Testbedingungen Variablen sind. Siehe auch Duffs Gerät .

Frühe Komplexität

Im einfachen Fall ist die Schleifensteuerung lediglich ein Verwaltungsaufwand, der die produktiven Anweisungen anordnet. Die Schleife selbst trägt nichts zu den gewünschten Ergebnissen bei, sondern erspart dem Programmierer lediglich die Mühe, den Code hundertmal zu replizieren, was von einem Vorprozessor, der die Replikationen generiert, oder einem Texteditor hätte durchgeführt werden können. In ähnlicher Weise if -Aussagen und andere Strömungssteueranweisungen könnten durch Code - Replikation ersetzt werden, außer dass Code aufblasen das Ergebnis sein kann. Computerprogramme verfolgen die Kombinationen leicht, aber Programmierer finden diese Wiederholung langweilig und machen Fehler. Erwägen:

Normale Schleife Nach dem Abrollen der Schleife 
for i := 1:8 do
    if i mod 2 = 0 then do_even_stuff(i) 
                   else do_odd_stuff(i);
    next i;

do_odd_stuff(1); do_even_stuff(2);
do_odd_stuff(3); do_even_stuff(4);
do_odd_stuff(5); do_even_stuff(6);
do_odd_stuff(7); do_even_stuff(8);

Aber der durchgeführte Code muss natürlich nicht der Aufruf einer Prozedur sein, und dieses nächste Beispiel bezieht die Indexvariable in die Berechnung ein:

Normale Schleife Nach dem Abrollen der Schleife 
x(1) := 1;
For i := 2:9 do
    x(i) := x(i - 1) * i;
    print i, x(i);
    next i;

x(1) := 1;
x(2) := x(1) * 2; print 2, x(2);
x(3) := x(2) * 3; print 3, x(3);
x(4) := x(3) * 4; print 4, x(4);
... etc.

Wenn diese kompiliert werden, wird möglicherweise viel Code erzeugt ( Druckanweisungen sind berüchtigt), aber eine weitere Optimierung ist möglich. In diesem Beispiel wird nur auf x (i) und x (i - 1) in der Schleife Bezug genommen (letzteres nur, um den neuen Wert x (i) zu entwickeln ), da es keinen späteren Verweis auf das hier entwickelte Array x gibt. seine Verwendung könnte durch eine einfache Variable ersetzt werden. Eine solche Änderung würde jedoch eine einfache Variable bedeuten, deren Wert geändert wird, während die Compiler-Analyse bei einem Verbleib im Array möglicherweise feststellt, dass die Werte des Arrays konstant sind, jeweils von einer vorherigen Konstante abgeleitet, und daher die konstanten Werte so weiterführt, dass der Code wird 

print 2, 2;
print 3, 6;
print 4, 24;
...etc.

Im Allgemeinen kann der Inhalt einer Schleife groß sein und eine komplizierte Array-Indizierung beinhalten. Diese Fälle lassen sich wahrscheinlich am besten der Optimierung der Compiler zum Abrollen überlassen. Das Replizieren der innersten Schleifen kann viele mögliche Optimierungen ermöglichen, führt jedoch nur zu einer geringen Verstärkung, es sei denn, n ist groß.

WHILE-Schleifen abrollen

Stellen Sie sich eine Pseudocode-WHILE-Schleife vor, die der folgenden ähnelt:

Normale Schleife Nach dem Abrollen der Schleife Abgerollte & "optimierte" Schleife 
WHILE (condition) DO
    action
ENDWHILE
.
.
.
.
.
.

WHILE (condition) DO
    action
    IF NOT(condition) THEN GOTO break
    action
    IF NOT(condition) THEN GOTO break
    action
ENDWHILE
LABEL break:
.

IF (condition) THEN
    REPEAT
        action
        IF NOT(condition) THEN GOTO break
        action
        IF NOT(condition) THEN GOTO break
        action
    WHILE (condition)
LABEL break:

In diesem Fall ist das Abrollen schneller, da ENDWHILE (ein Sprung zum Anfang der Schleife) 66% seltener ausgeführt wird.

Noch besser ist das "optimierte" Pseudocode-Beispiel, das von einigen optimierenden Compilern automatisch ausgeführt werden kann, wodurch bedingungslose Sprünge insgesamt vermieden werden.

Dynamisches Abrollen

Da die Vorteile des Abrollens von Schleifen häufig von der Größe eines Arrays abhängen - was häufig erst zur Laufzeit bekannt ist - können JIT- Compiler (zum Beispiel) bestimmen, ob eine "Standard" -Schleifensequenz aufgerufen oder stattdessen eine (relativ kurze) generiert werden soll ) Reihenfolge der einzelnen Anweisungen für jedes Element. Diese Flexibilität ist einer der Vorteile von Just-in-Time-Techniken gegenüber statischer oder manueller Optimierung im Zusammenhang mit dem Abrollen von Schleifen. In dieser Situation sind die Einsparungen häufig bei relativ kleinen Werten von n noch nützlich - was eine recht geringe (wenn überhaupt) Erhöhung der Programmgröße insgesamt erfordert (die möglicherweise nur einmal als Teil einer Standardbibliothek enthalten ist).

Assembler- Programmierer (einschließlich der Optimierung von Compiler-Writern) können ebenfalls von der Technik des dynamischen Abrollens von Schleifen profitieren, indem sie eine Methode verwenden, die der für effiziente Verzweigungstabellen verwendeten ähnelt . Hier ist der Vorteil am größten, wenn der maximale Versatz eines referenzierten Feldes in einem bestimmten Array kleiner ist als der maximale Versatz, der in einer Maschinenanweisung angegeben werden kann (die vom Assembler markiert wird, wenn sie überschritten wird).

Assembler-Beispiel (IBM / 360 oder Z / Architecture)

Ein x86-Beispiel finden Sie im Abschnitt Externe Links .

Dieses Beispiel gilt für IBM / 360- oder Z / Architecture- Assembler und setzt voraus, dass ein Feld von 100 Byte (bei Offset Null) von Array FROM zu Array TO kopiert werden soll - beide mit 50 Einträgen mit Elementlängen von jeweils 256 Byte. 

* The return address is in R14.
* Initialize registers R15, R0, R1, and R2 from data defined at the end of 
* the program starting with label INIT/MAXM1.
         LM    R15,R2,INIT                  Set R15 = maximum number of MVC
*                                           instructions (MAXM1 = 16), 
*                                           R0 = number of entries of array,
*                                           R1 = address of 'FROM' array, and
*                                           R2 = address of 'TO' array.
*
* The loop starts here.
LOOP     EQU   *                            Define LOOP label.
* At this point, R15 will always contain the number 16 (MAXM1).
         SR    R15,R0                       Subtract the remaining number of 
*                                           entries in the array (R0) from R15.
         BNP   ALL                          If R15 is not positive, meaning we
*                                           have more than 16 remaining entries
*                                           in the array, jump to do the entire
*                                           MVC sequence and then repeat.
*
* Calculate an offset (from start of MVC sequence) for unconditional branch to 
* the 'unwound' MVC loop below.
* If the number of remaining entries in the arrays is zero, R15 will be 16, so 
* all the MVC instructions will be bypassed.
         MH    R15,=AL2(ILEN)               Multiply R15 by the length of one
*                                           MVC instruction.
         B     ALL(R15)                     Jump to ALL+R15, the address of the
*                                           calculated specific MVC instruction 
*                                           with drop through to the rest of them.
*
* MVC instruction 'table'. 
* First entry has maximum allowable offset with single register = hexadecimal F00
* (15*256) in this example.
* All 16 of the following MVC ('move character') instructions use base-plus-offset 
* addressing and each to/from offset decreases by the length of one array element
* (256). This avoids pointer arithmetic being required for each element up to a 
* maximum permissible offset within the instruction of hexadecimal FFF 
* (15*256+255). The instructions are in order of decreasing offset, so the last 
* element in the set is moved first.
ALL      MVC   15*256(100,R2),15*256(R1)    Move 100 bytes of 16th entry from 
*                                           array 1 to array 2 (with 
*                                           drop-through).
ILEN     EQU   *-ALL                        Set ILEN to the length of the previous
*                                           MVC instruction.
         MVC   14*256(100,R2),14*256(R1)    Move 100 bytes of 15th entry.
         MVC   13*256(100,R2),13*256(R1)    Move 100 bytes of 14th entry.
         MVC   12*256(100,R2),12*256(R1)    Move 100 bytes of 13th entry.
         MVC   11*256(100,R2),11*256(R1)    Move 100 bytes of 12th entry.
         MVC   10*256(100,R2),10*256(R1)    Move 100 bytes of 11th entry.
         MVC   09*256(100,R2),09*256(R1)    Move 100 bytes of 10th entry.
         MVC   08*256(100,R2),08*256(R1)    Move 100 bytes of 9th entry.
         MVC   07*256(100,R2),07*256(R1)    Move 100 bytes of 8th entry.
         MVC   06*256(100,R2),06*256(R1)    Move 100 bytes of 7th entry.
         MVC   05*256(100,R2),05*256(R1)    Move 100 bytes of 6th entry.
         MVC   04*256(100,R2),04*256(R1)    Move 100 bytes of 5th entry.
         MVC   03*256(100,R2),03*256(R1)    Move 100 bytes of 4th entry.
         MVC   02*256(100,R2),02*256(R1)    Move 100 bytes of 3rd entry.
         MVC   01*256(100,R2),01*256(R1)    Move 100 bytes of 2nd entry.
         MVC   00*256(100,R2),00*256(R1)    Move 100 bytes of 1st entry.
*
         S     R0,MAXM1                     Reduce the number of remaining entries
*                                           to process.
         BNPR  R14                          If no more entries to process, return
*                                           to address in R14.
         AH    R1,=AL2(16*256)              Increment 'FROM' array pointer beyond
*                                           first set.
         AH    R2,=AL2(16*256)              Increment 'TO' array pointer beyond
*                                           first set.
         L     R15,MAXM1                    Reload the maximum number of MVC 
*                                           instructions per batch into R15
*                                           (destroyed by the calculation in the 
*                                           first instruction of the loop).
         B     LOOP                         Execute loop again.
*
* Static constants and variables (these could be passed as parameters, except 
* MAXM1).
INIT     DS    0A                           4 addresses (pointers) to be 
*                                           pre-loaded with the 'LM' instruction
*                                           in the beginning of the program.
MAXM1    DC    A(16)                        Maximum number of MVC instructions
*                                           executed per batch.
N        DC    A(50)                        Number of actual entries in array (a 
*                                           variable, set elsewhere).
         DC    A(FROM)                      Address of start of array 1 
*                                           ("pointer").
         DC    A(TO)                        Address of start of array 2 
*                                           ("pointer").
*
* Static arrays (these could be dynamically acquired).
FROM     DS    50CL256                      Array of 50 entries of 256 bytes each.
TO       DS    50CL256                      Array of 50 entries of 256 bytes each.

In diesem Beispiel wären ungefähr 202 Befehle mit einer "herkömmlichen" Schleife (50 Iterationen) erforderlich, während der obige dynamische Code nur ungefähr 89 Befehle erfordern würde (oder eine Einsparung von ungefähr 56%). Wenn das Array nur aus zwei Einträgen bestanden hätte, würde es immer noch ungefähr zur gleichen Zeit wie die ursprüngliche abgewickelte Schleife ausgeführt. Die Zunahme der Codegröße beträgt nur etwa 108 Bytes - selbst wenn das Array Tausende von Einträgen enthält.

Ähnliche Techniken können natürlich verwendet werden, wenn mehrere Befehle beteiligt sind, solange die kombinierte Befehlslänge entsprechend angepasst wird. Wenn in demselben Beispiel beispielsweise der Rest jedes Array-Eintrags unmittelbar nach dem Kopieren des 100-Byte-Felds auf Null gesetzt werden muss XC xx*256+100(156,R1),xx*256+100(R2) , kann unmittelbar nach jeder MVC in der Sequenz (wobei die xx Übereinstimmung mit der übereinstimmt) eine zusätzliche Löschanweisung hinzugefügt werden Wert in der MVC darüber).

Es ist natürlich durchaus möglich, den obigen Code "inline" mit einer einzelnen Assembler- Makroanweisung zu generieren , wobei nur vier oder fünf Operanden angegeben werden (oder es alternativ zu einer Bibliotheksunterroutine zu machen, auf die durch einen einfachen Aufruf zugegriffen wird und eine Liste von übergeben wird Parameter), wodurch die Optimierung leicht zugänglich wird.

C Beispiel

Das folgende Beispiel zeigt das Abrollen der dynamischen Schleife für ein einfaches Programm, das in C geschrieben wurde . Im Gegensatz zum obigen Assembler-Beispiel wird die Zeiger- / Indexarithmetik in diesem Beispiel weiterhin vom Compiler generiert, da weiterhin eine Variable (i) zum Adressieren des Array-Elements verwendet wird. Eine vollständige Optimierung ist nur möglich, wenn in den Ersetzungsanweisungen absolute Indizes verwendet werden. 

#include <stdio.h>

/* The number of entries processed per loop iteration.                        */
/* Note that this number is a 'constant constant' reflecting the code below.  */
#define BUNCHSIZE (8)

int main(void)
{ 
  int i = 0;                                    /* counter */
  int entries = 50;                             /* total number to process    */
  int repeat;                                   /* number of while repetitions*/
  int left = 0;                                 /* remainder (process later)  */ 
 
  /* If the number of elements is not be divisible by BUNCHSIZE,              */ 
  /* get repeat times required to do most processing in the while loop        */

  repeat = (entries / BUNCHSIZE);                /* number of times to repeat */
  left   = (entries % BUNCHSIZE);                /* calculate remainder       */

  /* Unroll the loop in 'bunches' of 8                                        */ 
  while (repeat--) 
  { 
    printf("process(%d)\n", i    );
    printf("process(%d)\n", i + 1); 
    printf("process(%d)\n", i + 2); 
    printf("process(%d)\n", i + 3); 
    printf("process(%d)\n", i + 4); 
    printf("process(%d)\n", i + 5); 
    printf("process(%d)\n", i + 6); 
    printf("process(%d)\n", i + 7);

    /* update the index by amount processed in one go                         */ 
    i += BUNCHSIZE;
  }

  /* Use a switch statement to process remaining by jumping to the case label */ 
  /* at the label that will then drop through to complete the set             */ 
  switch (left) 
  {
     case 7 : printf("process(%d)\n", i + 6);   /* process and rely on drop 
                                                   through                    */
     case 6 : printf("process(%d)\n", i + 5); 
     case 5 : printf("process(%d)\n", i + 4);  
     case 4 : printf("process(%d)\n", i + 3);  
     case 3 : printf("process(%d)\n", i + 2); 
     case 2 : printf("process(%d)\n", i + 1);   /* two left                   */
     case 1 : printf("process(%d)\n", i);       /* just one left to process   */ 
     case 0 : ;                                 /* none left                  */
  } 
}

Eine Codeduplizierung könnte vermieden werden, indem die beiden Teile wie bei Duffs Gerät zusammengeschrieben werden .

Beispiel für das Abrollen der C-zu-MIPS-Assembler-Schleife

Das folgende Beispiel berechnet ein Punktprodukt aus zwei Vektoren A und B mit 100 Einträgen vom Typ double . Hier ist der Code in C: 

double dotProduct = 0;
for (int i = 0; i < 100; i++) {
  dotProduct += A[i]*B[i];
}

Konvertieren in die MIPS-Assemblersprache

Das Folgende ist der MIPS-Assemblycode, der das Punktprodukt von zwei Vektoren mit 100 Einträgen, A und B, berechnet, bevor das Abrollen der Schleife implementiert wird. Der folgende Code lässt die Schleifeninitialisierungen aus:

  • Initialisieren Sie die Anzahl der Schleifen ($ 7) auf 100.
  • Initialisieren Sie das Punktprodukt ($ f10) auf 0.
  • Initialisieren Sie den A[i] Zeiger ($ 5) auf die Basisadresse von A .
  • Initialisieren Sie den B[i] Zeiger ($ 6) auf die Basisadresse von B .

Beachten Sie, dass die Größe eines Elements der Arrays (a double ) 8 Byte beträgt. 

    loop3:
            l.d     $f10, 0($5)       ; $f10 ← A[i]
            l.d     $f12, 0($6)       ; $f12 ← B[i]
            mul.d   $f10, $f10, $f12  ; $f10 ← A[i]*B[i]
            add.d   $f8, $f8, $f10    ; $f8 ← $f8 + A[i]*B[i]
            addi    $5, $5, 8         ; increment pointer for A[i] by the size
                                      ; of a double.
            addi    $6, $6, 8         ; increment pointer for B[i] by the size
                                      ; of a double.
            addi    $7, $7, -1        ; decrement loop count
    test:
            bgtz    $7, loop3         ; Continue if loop count > 0

Abwickeln der Schleife in MIPS

Das Folgende ist das gleiche wie oben, jedoch mit implementiertem Schleifenrollen bei einem Faktor von 4. Beachten Sie erneut, dass die Größe eines Elements der Arrays (a double ) 8 Bytes beträgt; somit die 0, 8, 16, 24 Verschiebungen und die 32 Verschiebungen auf jeder Schleife. 

    loop3:
            l.d     $f10, 0($5)         ; iteration with displacement 0
            l.d     $f12, 0($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 8($5)         ; iteration with displacement 8
            l.d     $f12, 8($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 16($5)        ; iteration with displacement 16
            l.d     $f12, 16($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 24($5)        ; iteration with displacement 24
            l.d     $f12, 24($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            addi    $5, $5, 32
            addi    $6, $6, 32
            addi    $7, $7, -4
    test:
            bgtz    $7, loop3           ; Continue loop if $7 > 0

Siehe auch

Verweise

Weiterführende Literatur

Externe Links