Rozwijanie pętli - Loop unrolling

Nie należy mylić z rozwijaniem stosu .

Odwijanie pętli , znane również jako rozwijanie pętli , jest techniką transformacji pętli , która próbuje zoptymalizować szybkość wykonywania programu kosztem jego binarnego rozmiaru, co jest podejściem znanym jako kompromis czasoprzestrzenny . Transformacja może być wykonana ręcznie przez programistę lub przez optymalizujący kompilator . Na nowoczesnych procesorach rozwijanie pętli często przynosi efekty odwrotne do zamierzonych, ponieważ zwiększony rozmiar kodu może spowodować więcej błędów pamięci podręcznej; por. Urządzenie Duffa .

Celem rozwijania pętli jest zwiększenie szybkości programu poprzez zmniejszenie lub wyeliminowanie instrukcji sterujących pętlą, takich jak arytmetyka wskaźnika i testy „końca pętli” w każdej iteracji; zmniejszenie kar dla oddziałów; a także ukrywanie opóźnień, w tym opóźnienie odczytu danych z pamięci. Aby wyeliminować ten narzut obliczeniowy , pętle można ponownie zapisać jako powtarzającą się sekwencję podobnych niezależnych instrukcji.

Odwijanie pętli jest również częścią niektórych formalnych technik weryfikacji , w szczególności ograniczonego sprawdzania modelu .

Zalety

Narzut w „ciasnych” pętlach często składa się z instrukcji zwiększania wskaźnika lub indeksu do następnego elementu w tablicy ( arytmetyka wskaźników ), a także z testów „końca pętli”. Jeśli optymalizujący kompilator lub asembler jest w stanie wstępnie obliczyć przesunięcia dla każdej zmiennej tablicowej, do której się odwołujemy , można je bezpośrednio wbudować w instrukcje kodu maszynowego , nie wymagając w ten sposób żadnych dodatkowych operacji arytmetycznych w czasie wykonywania.

  • Znaczące korzyści można osiągnąć, jeśli redukcja wykonywanych instrukcji kompensuje jakiekolwiek zmniejszenie wydajności spowodowane jakimkolwiek wzrostem rozmiaru programu.
  • Kara gałęzi jest zminimalizowana.
  • Jeśli instrukcje w pętli są od siebie niezależne (tj. Gdy instrukcje występujące wcześniej w pętli nie wpływają na instrukcje, które następują po nich), instrukcje mogą być potencjalnie wykonywane równolegle .
  • Może być implementowany dynamicznie, jeśli liczba elementów tablicy jest nieznana w czasie kompilacji (jak w urządzeniu Duffa ).

Optymalizujące kompilatory czasami wykonują rozwijanie automatycznie lub na żądanie.

Niedogodności

  • Zwiększony rozmiar kodu programu, co może być niepożądane, szczególnie w przypadku aplikacji wbudowanych. Może również powodować wzrost chybień w pamięci podręcznej instrukcji, co może niekorzystnie wpływać na wydajność.
  • Jeśli nie zostanie wykonany w sposób przejrzysty przez optymalizujący kompilator, kod może stać się mniej czytelny .
  • Jeśli kod w ciele pętli wymaga wywołania funkcji, może nie być możliwe łączenie jej rozwinięcie z inline , ponieważ zwiększenie rozmiaru kodu może być nadmierne. Dlatego może wystąpić kompromis między dwiema optymalizacjami.
  • Możliwe zwiększone użycie rejestru w pojedynczej iteracji do przechowywania zmiennych tymczasowych, co może zmniejszyć wydajność, chociaż wiele będzie zależało od możliwych optymalizacji.
  • Oprócz bardzo małego i prostego kodu, rozwinięte pętle, które zawierają gałęzie, są nawet wolniejsze niż rekursje.

Statyczne / ręczne rozwijanie pętli

Ręczne (lub statyczne) rozwijanie pętli wymaga przez programistę analizy pętli i interpretacji jej iteracji w sekwencję instrukcji, co zmniejszy narzut pętli. Jest to przeciwieństwo dynamicznego rozwijania, które jest wykonywane przez kompilator.

Prosty przykład ręczny w C

Procedura w programie komputerowym polega na usunięciu ze zbioru 100 pozycji. Zwykle jest to realizowane za pomocą for -loop, która wywołuje funkcję delete (numer_pozycji) . Jeśli ta część programu ma być zoptymalizowana, a obciążenie pętli wymaga znacznych zasobów w porównaniu z zasobami przeznaczonymi na funkcję delete (x) , można skorzystać z rozwijania, aby ją przyspieszyć.

Normalna pętla Po rozwinięciu pętli 
 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);
 }

W wyniku tej modyfikacji nowy program musi wykonać tylko 20 iteracji zamiast 100. Następnie wystarczy wykonać tylko 20% skoków i gałęzi warunkowych i reprezentuje, w wielu iteracjach, potencjalnie znaczący spadek obciążenie administracyjne pętli. Aby uzyskać optymalną korzyść, w rozwiniętym kodzie nie należy określać żadnych zmiennych, które wymagają arytmetyki wskaźnika . Zwykle wymaga to adresowania „ podstawa plus przesunięcie”, a nie odwołań indeksowanych.

Z drugiej strony, to ręczne rozwijanie pętli rozszerza rozmiar kodu źródłowego z 3 do 7 linii, które trzeba wygenerować, sprawdzić i zdebugować, a kompilator może być zmuszony do przydzielenia większej liczby rejestrów do przechowywania zmiennych w iteracji rozszerzonej pętli. Ponadto zmienne sterujące pętlą i liczba operacji wewnątrz struktury pętli rozwiniętej muszą być starannie dobrane, aby wynik był rzeczywiście taki sam jak w oryginalnym kodzie (zakładając, że jest to późniejsza optymalizacja już działającego kodu). Na przykład rozważ konsekwencje, gdyby liczba iteracji nie była podzielna przez 5. Wymagane ręczne poprawki również stają się nieco bardziej skomplikowane, jeśli warunki testu są zmiennymi. Zobacz także urządzenie Duffa .

Wczesna złożoność

W prostym przypadku sterowanie w pętli jest jedynie narzutem administracyjnym, który organizuje produktywne instrukcje. Sama pętla nie przyczynia się w żaden sposób do pożądanych wyników, oszczędzając jedynie programiście nudy stukrotnego replikowania kodu, co mogłoby być zrobione przez preprocesor generujący replikacje lub edytor tekstu. Podobnie if -statements i inne instrukcje kontroli przepływu można zastąpić replikacją kodu, z tą różnicą, że wynikiem może być rozdęcie kodu . Programy komputerowe łatwo śledzą kombinacje, ale programiści uważają to powtórzenie za nudne i popełniają błędy. Rozważać:

Normalna pętla Po rozwinięciu pętli 
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);

Ale oczywiście wykonywany kod nie musi być wywołaniem procedury, a ten następny przykład obejmuje obliczenie zmiennej indeksu:

Normalna pętla Po rozwinięciu pętli 
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.

który, jeśli zostanie skompilowany, może wygenerować dużo kodu ( notoryczne są instrukcje drukowania ), ale możliwa jest dalsza optymalizacja. Ten przykład odnosi się tylko do x (i) i x (i - 1) w pętli (ta ostatnia tylko w celu opracowania nowej wartości x (i) ), biorąc pod uwagę, że nie ma później odniesienia do tablicy x opracowanej tutaj, jego zastosowania można by zastąpić prostą zmienną. Taka zmiana oznaczałaby jednak prostą zmienną, której wartość jest zmieniana, podczas gdy pozostając przy tablicy, analiza kompilatora może zauważyć, że wartości tablicy są stałe, każda pochodzi z poprzedniej stałej, a zatem przenosi wartości stałe, tak że kod staje się 

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

Ogólnie zawartość pętli może być duża i obejmować skomplikowane indeksowanie tablic. Te przypadki prawdopodobnie najlepiej pozostawić do optymalizacji kompilatorów do rozwinięcia. Replikowanie najbardziej wewnętrznych pętli może pozwolić na wiele możliwych optymalizacji, ale daje tylko niewielki zysk, chyba że n jest duże.

Rozwijanie pętli WHILE

Rozważ pseudokodową pętlę WHILE podobną do poniższej:

Normalna pętla Po rozwinięciu pętli Rozwinięta i „ulepszona” pętla 
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:

W tym przypadku rozwijanie jest szybsze, ponieważ ENDWHILE (skok na początek pętli) będzie wykonywany 66% rzadziej.

Jeszcze lepiej, przykład „ulepszonego” pseudokodu, który może być wykonywany automatycznie przez niektóre optymalizujące kompilatory, całkowicie eliminując bezwarunkowe skoki.

Dynamiczne rozwijanie

Ponieważ korzyści płynące z rozwijania pętli są często zależne od rozmiaru tablicy - która często może nie być znana do czasu wykonania - kompilatory JIT (na przykład) mogą określić, czy wywołać „standardową” sekwencję pętli, czy zamiast tego wygenerować (stosunkowo krótką ) sekwencja indywidualnych instrukcji dla każdego elementu. Ta elastyczność jest jedną z zalet technik just in time w porównaniu z optymalizacją statyczną lub ręczną w kontekście rozwijania pętli. W tej sytuacji często przy stosunkowo małych wartościach n oszczędności są nadal użyteczne - wymagając dość niewielkiego (jeśli w ogóle) ogólnego zwiększenia rozmiaru programu (który może zostać uwzględniony tylko raz, jako część biblioteki standardowej).

Zgromadzenie język programistów (w tym optymalizacji pisarzy kompilatora) są też w stanie skorzystać z tej techniki dynamicznego odwijanie pętli, stosując metodę podobną do tej stosowanej dla wydajnych tabelach branży . Tutaj korzyść jest największa, gdy maksymalne przesunięcie dowolnego pola, do którego się odwołujemy w określonej tablicy, jest mniejsze niż maksymalne przesunięcie, które można określić w instrukcji maszynowej (które zostanie oflagowane przez asembler, jeśli zostanie przekroczone).

Przykład asemblera (IBM / 360 lub Z / Architecture)

Aby zapoznać się z przykładem x86, zobacz sekcję Linki zewnętrzne .

Ten przykład dotyczy asemblerów IBM / 360 lub Z / Architecture i zakłada, że ​​pole 100 bajtów (z przesunięciem zerowym) ma zostać skopiowane z tablicy FROM do tablicy TO - oba mają 50 wpisów o długości elementów po 256 bajtów każdy. 

* 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.

W tym przykładzie potrzebnych byłoby około 202 instrukcji z „konwencjonalną” pętlą (50 iteracji), podczas gdy powyższy kod dynamiczny wymagałby tylko około 89 instrukcji (lub oszczędność około 56%). Gdyby tablica składała się tylko z dwóch wpisów, nadal wykonywałaby się mniej więcej w tym samym czasie, co pierwotna rozwinięta pętla. Wzrost rozmiaru kodu wynosi tylko około 108 bajtów - nawet jeśli w tablicy są tysiące wpisów.

Podobne techniki można oczywiście zastosować w przypadku wielu instrukcji, o ile łączna długość instrukcji jest odpowiednio dostosowana. Na przykład, w tym samym przykładzie, jeśli wymagane jest wyczyszczenie reszty każdego wpisu tablicy do wartości null bezpośrednio po skopiowaniu pola 100-bajtowego, dodatkową instrukcję XC xx*256+100(156,R1),xx*256+100(R2) można dodać bezpośrednio po każdym MVC w sekwencji (gdzie xx pasuje do wartość w MVC powyżej).

Jest oczywiście całkowicie możliwe wygenerowanie powyższego kodu „inline” przy użyciu pojedynczej instrukcji makro asemblera , określającej tylko cztery lub pięć operandów (lub alternatywnie, przekształcenie go w procedurę biblioteczną, do której można uzyskać dostęp za pomocą prostego wywołania, przekazując listę parametry), dzięki czemu optymalizacja jest łatwo dostępna.

Przykład C.

Poniższy przykład demonstruje dynamiczny jej rozwinięcie pętli dla prostego programu napisanego w C . W przeciwieństwie do powyższego przykładu asemblera, arytmetyka wskaźnika / indeksu jest nadal generowana przez kompilator w tym przykładzie, ponieważ zmienna (i) jest nadal używana do adresowania elementu tablicy. Pełna optymalizacja jest możliwa tylko wtedy, gdy w instrukcjach zamiany używane są indeksy bezwzględne. 

#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                  */
  } 
}

Powielania kodu można było uniknąć, zapisując obie części razem, tak jak w urządzeniu Duffa .

Przykład rozwijania pętli języka asemblera C do MIPS

Poniższy przykład obliczyć iloczyn skalarny dwóch wektorów 100 wejścia A i B jest typu double . Oto kod w C: 

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

Konwersja do języka asemblera MIPS

Poniżej znajduje się kod asemblera MIPS, który obliczy iloczyn skalarny dwóch 100-wejściowych wektorów, A i B, przed wdrożeniem rozwijania pętli. Poniższy kod pomija inicjalizacje pętli:

  • Zainicjuj liczbę pętli (7 USD) do 100.
  • Zainicjuj iloczyn skalarny ($ f10) na 0.
  • Zainicjuj A[i] wskaźnik ($ 5) do adresu podstawowego A .
  • Zainicjuj B[i] wskaźnik ($ 6) do adresu podstawowego B .

Zauważ, że rozmiar jednego elementu tablic (a double ) wynosi 8 bajtów. 

    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

Rozwijanie pętli w MIPS

Następujące jest to samo, co powyżej, ale z rozwijaniem pętli zaimplementowanym przy współczynniku 4. Zauważ ponownie, że rozmiar jednego elementu tablic (a double ) wynosi 8 bajtów; a zatem przemieszczenia 0, 8, 16, 24 i przemieszczenia 32 w każdej pętli. 

    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

Zobacz też

Bibliografia

Dalsza lektura

Linki zewnętrzne