Desfășurarea buclei

Deconectarea buclelor este o tehnică de optimizare utilizată de compilatoare și microprocesoare pentru a îmbunătăți execuția programului.

Această tehnică face parte din tehnicile de transformare a buclei. Această tehnică, la fel ca toate cele care procesează bucle, își propune să reducă instrucțiunile inutile în timpul executării buclei pentru a face programul mai rapid. Această tehnică grupează instrucțiunile executate în mai multe bucle într-o singură buclă, astfel încât să reducă numărul de salturi care trebuie făcute la executarea buclei.

Această tehnică are dezavantajul de a crește utilizarea registrelor microprocesorului și de a crește dimensiunea codului.

Această tehnică poate fi utilizată și pentru a face programele mai ușor de paralelizat .

Primul exemplu

Presupunând că aveți un program care trebuie să șteargă 100 de elemente din memorie. Acest lucru poate fi realizat cu o buclă simplă precum cea indicată în acest fragment de cod:

 pentru (int x = 0; x <100; x ++)
{
    șterge (x);
}

Fiecare anulare necesită executarea unui salt și creșterea indexului, folosind derularea buclei este posibilă reducerea semnificativă a salturilor și sumelor inutile obținând un cod de acest tip:

 pentru (int x = 0; x <100; x + = 5)
{
    șterge (x);
    șterge (x + 1);
    șterge (x + 2);
    șterge (x + 3);
    șterge (x + 4);
}
   

În noul cod, cinci ștergeri sunt efectuate în fiecare buclă și, prin urmare, va dura doar 20 de execuții ale buclei pentru a finaliza programul și nu 100 ca inițial. Deci, noul cod a eliminat 80 de salturi și 80 de pași de index i. Presupunând că puteți efectua toate operațiile într-un singur ciclu de ceas, ciclul inițial necesită 300 de cicluri de ceas (1 hop, 1 ștergere și 1 increment efectuat de 100 de ori) în timp ce cel optimizat necesită doar 140 de cicluri de ceas (1 hop, 5 ștergeri și un increment pentru 20 de cicluri).

Dezavantajul derulării este că noul cod necesită utilizarea multor registre și codul în loc de a ocupa 3 linii ocupă 7, în plus, în cazul buclelor mai complexe, gestionarea codului intern devine complexă.

Al doilea exemplu

În primul caz, bucla a rulat cod necondiționat, astfel încât să fie paralel a fost simplu. Buclele trebuie adesea să execute cod condițional și, adesea, în aceste cazuri, derularea codului poate îmbunătăți performanța. În unele cazuri derularea codului poate fi totală pentru a elimina complet bucla, de exemplu, a se vedea următorul cod:

 pentru i: = 1: 8 faceți
 dacă i mod 2 = 0 atunci pare (i) altceva impar (i);
apoi eu;

Acest cod execută funcția impar () dacă numărul este impar și funcția pare () dacă numărul este par (). Bucla este executată de opt ori și în cadrul buclei există un dacă, alternativ, execută impar și par, acest lucru în special dacă configurația ar submina unitățile de predicție a saltului, deoarece aceste unități prezic comportamentul salturilor pe baza comportamentelor anterioare, dar în această buclă de fiecare dată dacă efectuează o operație diferită. Desfacerea buclei ar duce la rularea următorului cod:

 impar (1); chiar (2);
impar (3); chiar (4);
impar (5); chiar (6);
impar (7); chiar (8);

Acest cod elimină în totalitate bucla și salturile, făcând executarea codului liniară și, prin urmare, simplu de executat pentru un microprocesor (evident, nu este necesar ca instrucțiunile să fie invocații unei proceduri). Tehnica poate fi aplicată și în cazuri mai complexe, de exemplu acest cod:

 x (1) = 1;
Pentru i: = 2: 9 faceți 
 x (i): = x (i - 1) * i;
 print i, x (i);
Apoi eu;

după derularea codului devine

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

Acest cod este întotdeauna mai lung decât cel original și folosește mai multe registre decât cel original, deși multe procesoare sunt echipate cu unități de redenumire a registrelor și, prin urmare, pot reduce incidența registrelor ocupate de algoritm.

Utilizări

Tehnica de derulare a jurnalului poate fi utilizată la nivel de hardware sau software. La nivel hardware se face la nivel de procesor, dar având procesorul un timp foarte limitat pentru a efectua optimizări de cod (de obicei nanosecunde) acest lucru poate efectua doar cele mai simple optimizări. Pe de altă parte, la nivel de software, compilatorul are potențial tot timpul necesar pentru a efectua optimizări și, prin urmare, poate efectua chiar și cele mai complexe optimizări. Compilatorul poate încerca să realizeze optimizări care implică și mai multe bucle încercând să colecteze instrucțiuni de la diferite bucle într-o singură buclă pentru a reduce salturile care trebuie efectuate.

Instrumentul lui Duff

Un anumit algoritm de derulare a fost propus de Tom Duff în 1983 ^[1] . Porțiunea de cod

 face {
   * la ++ = * de la ++;
 } while (--count> 0) 

a prezentat problema numărului de deconectări de a alege, deoarece contorul nu a fost cunoscut a priori de către compilator.

Prin optimizarea acestor instrucțiuni ^[2] Duff a realizat că era posibil să se întrepătrundă o buclă derulată cu o instrucțiune la alegere, evitând problema buclei incomplete, sau mai degrabă a instrucțiunilor unice care trebuie executate inițial atunci când contorul nu este divizibil cu numărul de instrucțiuni derulate.

 int n = (număr + 7) / 8;
   comutați (numărați% 8) {
   cazul 0: faceți {* până la ++ = * din ++;
   cazul 7: * la ++ = * de la ++;
   cazul 6: * la ++ = * de la ++;
   cazul 5: * la ++ = * de la ++;
   cazul 4: * la ++ = * de la ++;
   cazul 3: * la ++ = * de la ++;
   cazul 2: * la ++ = * de la ++;
   cazul 1: * la ++ = * de la ++;
              } while (--n> 0);
   }

După cum puteți vedea, instrucțiunea switch este utilizată pentru a decide punctul de intrare în bucla derulată atunci când instrucțiunile totale nu sunt divizibile cu instrucțiunile derulate.

Notă