Buclă zero-overhead - Zero-overhead looping

Buclarea zero-overhead este o caracteristică a unor seturi de instrucțiuni ale procesorului al căror hardware poate repeta automat corpul unei bucle , mai degrabă decât necesită instrucțiuni software care necesită cicluri (și deci timp) pentru a face acest lucru. Buclele zero-overhead sunt frecvente în procesoarele digitale de semnal și în unele seturi de instrucțiuni CISC .

fundal

În multe seturi de instrucțiuni, o buclă trebuie să fie implementată folosind instrucțiuni pentru a crește sau decrementa un contor, verificați dacă a fost atins sfârșitul buclei și, dacă nu, săriți la începutul buclei, astfel încât să poată fi repetată. Deși acest lucru reprezintă de obicei în jur de 3-16 octeți de spațiu pentru fiecare buclă, chiar și acea cantitate mică ar putea fi semnificativă în funcție de dimensiunea cache-urilor procesorului . Mai semnificativ este că acele instrucțiuni necesită fiecare timp pentru a fi executate, timp care nu este cheltuit făcând o muncă utilă.

Cheltuielile generale ale unei astfel de bucle sunt evidente în comparație cu o buclă complet derulată , în care corpul buclei este duplicat exact de câte ori se va executa. În acest caz, nu se pierde spațiu sau timp de execuție la instrucțiuni pentru a repeta corpul buclei. Cu toate acestea, duplicarea cauzată de derularea buclei poate crește în mod semnificativ dimensiunea codului, iar dimensiunea mai mare poate afecta chiar timpul de execuție din cauza ratărilor cache . (Din acest motiv, este obișnuit să derulați doar parțial buclele, cum ar fi transformarea acestuia într-o buclă care efectuează lucrarea a patru iterații într-un singur pas înainte de a repeta. Aceasta echilibrează avantajele derulării cu cheltuielile generale de repetare a buclei.) Mai mult, derularea completă a unei bucle este posibilă numai pentru un număr limitat de bucle: cele al căror număr de iterații este cunoscut în momentul compilării .

De exemplu, următorul cod C ar putea fi compilat și optimizat în următorul cod de asamblare x86:

unsigned int array[100];
unsigned int i;

for (i = 0; i < 100; i++) {
    array[i] = i;
}

; Set up number of loop iterations.
; Note that the compiler has reversed the loop
; so that it counts backwards from 99 to 0,
; rather than up from 0 to 99.
mov eax, 99

.LABEL:
; array[i] = i
mov DWORD PTR array[0+eax*4], eax

; Decrement i
sub eax, 1

; Check i >= 0. If true, repeat the loop.
jnb .LABEL

Implementare

Procesoarele cu looping zero-overhead au instrucțiuni și registre ale mașinii pentru a repeta automat una sau mai multe instrucțiuni. În funcție de instrucțiunile disponibile, acestea pot fi potrivite numai pentru buclele controlate cu număr („pentru bucle”) în care numărul de iterații poate fi calculat în avans sau numai pentru buclele controlate de condiții („în timp ce buclele”), cum ar fi operațiile pe șiruri terminate cu nul .

Exemple

PIC

În setul de instrucțiuni PIC , REPEAT și DO instrucțiunile implementează bucle zero-overhead. REPEAT repetă doar o singură instrucțiune, în timp ce DO repetă un număr specificat de instrucțiuni următoare.

Negru

Blackfin oferă două bucle zero-overhead. Buclele pot fi cuibărite; dacă ambele bucle hardware sunt configurate cu aceeași adresă "buclă de capăt", bucla 1 se va comporta ca bucla interioară și se va repeta, iar bucla 0 se va comporta ca bucla exterioară și se va repeta numai dacă bucla 1 nu ar repeta.

Buclele sunt controlate folosind LTx și LBx registrele ( x fie 0 până la 1) pentru a seta partea de sus și de jos a buclei - adică prima și ultima instrucțiuni care trebuie executate, care pot fi aceleași pentru o buclă cu o singură instrucțiune - și LCx pentru numărul de bucle. Bucla se repetă dacă LCx este diferită de zero la sfârșitul buclei, caz în care LCx este decrementată.

Registrele buclei pot fi setate manual, dar acest lucru ar consuma de obicei 6 octeți pentru a încărca registrele și 8-16 octeți pentru a configura valorile care trebuie încărcate. Mai frecvent este să folosiți instrucțiunea de configurare a buclei (reprezentată în asamblare fie LOOP cu pseudo-instrucțiuni LOOP_BEGIN și LOOP_END , fie într-o singură linie ca LSETUP ), care inițializează LCx și setează opțional LTx și LBx la valorile dorite. Acest lucru necesită doar 4-6 octeți, dar poate fi setat LTx și LBx într-un interval limitat în raport cu locul în care se află instrucțiunea de configurare a buclei.

P0 = array + 396;
R0 = 100;
LC0 = R0;
LOOP my_loop LC0;   // sets LT0 and LB0

LOOP_BEGIN my_loop;   // pseudo-instruction; generates a label used to compute LT0
// LC0 cannot be written directly to memory,
// so we must use a temporary register.
R0 += -1;   // equally fast and small would be R0 = LC0
[P0--] = R0;
LOOP_END my_loop;   // pseudo-instruction; generates a label used to compute LB0

x86

În limbaj de asamblare x86 REP prefixele pune în aplicare bucle aeriene zero pentru câteva instrucțiuni ( și anume MOVS/STOS/CMPS/LODS/SCAS ). În funcție de prefix și instrucțiune, instrucțiunea va fi repetată de mai multe ori cu (E)CX menținerea numărului de repetări sau până când se găsește o potrivire (sau non-potrivire) cu AL/AX/EAX sau cu DS:[(E)SI] . Aceasta poate fi utilizată pentru a implementa unele tipuri de căutări și operații pe șiruri terminate cu nul .

Referințe