Srotolamento del loop

Lo srotolamento del loop (loop unrolling) è una tecnica di ottimizzazione utilizzata dai compilatori e dai microprocessori per migliorare l'esecuzione dei programmi.

Questa tecnica fa parte delle tecniche di trasformazione dei loop e punta a velocizzare il programma riducendo le istruzioni che gestiscono il flusso del loop intervenendo sull'algebra dei puntatori e sui controlli di fine loop. Inoltre, raggruppa istruzioni eseguite in loop diversi in un singolo ciclo in modo tale da ridurre i salti nel codice effettuati durante l'esecuzione. Questa tecnica può essere utilizzata anche per rendere i programmi più facilmente parallelizzabili.

Uno degli svantaggi principali del loop unrolling è il maggior uso dei registri del microprocessore ed un codice compilato più grande in termini di dimensioni.

Primo esempio

Supponendo di avere un programma che deve cancellare 100 elementi dalla memoria. Questo può essere realizzato con un semplice loop come quello indicato in questo frammento di codice:

for (int x = 0; x < 100; x++)
{
    delete(x);
}

Ogni cancellazione richiede l'esecuzione di un salto e l'incremento dell'indice, utilizzando lo srotolamento del loop si possono ridurre in modo significativo i salti e le somme non indispensabili ottenendo un codice di questo tipo:

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

Nel nuovo codice in ogni loop vengono eseguite cinque cancellazioni e quindi serviranno solo 20 esecuzioni del loop per completare il programma e non 100 come inizialmente. Quindi il nuovo codice ha eliminato 80 salti e 80 incrementi dell'indice i. Supponendo di poter eseguire tutte le operazioni in un ciclo di clock il ciclo iniziale richiede 300 cicli di clock (1 salto, 1 cancellazione e 1 incremento eseguiti 100 volte) mentre quello ottimizzato richiede solo 140 cicli di clock (1 salto, 5 cancellazioni e un incremento per 20 cicli).

Lo svantaggio dello srotolamento è che il nuovo codice richiede l'utilizzo di molti registri e il codice invece di occupare 3 righe ne occupa 7, inoltre nel caso di loop più articolati la gestione del codice interno diventa complesso.

Secondo esempio

Nel primo caso il loop eseguiva del codice non condizionato quindi renderlo parallelo era semplice. Spesso i loop devono eseguire del codice condizionato e spesso in questi casi l'esecuzione dello srotolamento del codice può migliorare le prestazioni. In alcuni casi lo srotolamento del codice può essere totale al fine di eliminare totalmente il loop, per esempio si veda il seguente codice:

for i:=1:8 do
 if i mod 2 = 0 then pari(i) else dispari(i);
next i;

Questo codice esegue la funzione dispari() se il numero è dispari e la funzione pari() se il numero è pari(). Il ciclo viene eseguito otto volte e all'interno del ciclo si ha un if che alternativamente esegue pari e dispari, questa particolare configurazione di if metterebbe in crisi le unità di predizione dei salti dato che queste unità prevedono il comportamento dei salti basandosi sui comportamenti passati ma in questo ciclo ogni volta l'if esegue un'operazione diversa. Lo srotolamento del loop porterebbe a eseguire il seguente codice:

dispari(1); pari(2);
dispari(3); pari(4);
dispari(5); pari(6);
dispari(7); pari(8);

Questo codice elimina totalmente il ciclo e i salti rendendo l'esecuzione del codice lineare e quindi semplice da eseguire per un microprocessore (ovviamente non è necessario che le istruzioni siano invocazioni di una procedura). La tecnica si può applicare anche a casi più complessi, ad esempio questo codice:

x(1) = 1;
For i:=2:9 do 
 x(i):=x(i - 1)*i;
 stampa i,x(i);
Next i;

dopo lo srotolamento del codice diventa

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

Questo codice risulta essere come sempre più lungo di quello originale e utilizza più registri di quello di partenza, sebbene molti processori siano dotati di unità di rinominazione dei registri e quindi possano ridurre l'incidenza dei registri occupati dall'algoritmo.

Utilizzi

La tecnica di srotolamento dei registri può essere utilizzata a livello hardware o software. A livello hardware viene svolto a livello del processore, ma avendo il processore un tempo molto limitato per eseguire le ottimizzazioni del codice (tipicamente nanosecondi) questo può svolgere solo le ottimizzazioni più semplici. A livello software invece il compilatore ha potenzialmente tutto il tempo necessario per eseguire le ottimizzazioni e quindi può eseguire anche le ottimizzazioni più complesse. Il compilatore può cercare di eseguire delle ottimizzazioni che coinvolgano anche più loop cercando di raccogliere istruzioni di diversi loop in un singolo loop al fine di ridurre i salti da eseguire.

Lo strumento di Duff

Un particolare algoritmo di srotolamento è stato proposto da Tom Duff nel 1983. La porzione di codice

 do {
   *to++ = *from++;
 } while (--count > 0) 

presentava il problema del numero di srotolamenti da scegliere, dato che il contatore non era noto al compilatore a priori.

Ottimizzando queste istruzioni Duff si rese conto che era possibile interlacciare un loop srotolato ad una istruzione di scelta ovviando al problema del loop incompleto, ovvero delle singole istruzioni da eseguire inizialmente quando il contatore non è divisibile per il numero di istruzioni srotolate.

   int n = (count + 7) / 8;
   switch (count % 8) {
   case 0: do { *to++ = *from++;
   case 7:      *to++ = *from++;
   case 6:      *to++ = *from++;
   case 5:      *to++ = *from++;
   case 4:      *to++ = *from++;
   case 3:      *to++ = *from++;
   case 2:      *to++ = *from++;
   case 1:      *to++ = *from++;
              } while (--n > 0);
   }

Come si vede, l'istruzione switch serve a decidere il punto di entrata nel loop srotolato quando le istruzioni totali non sono divisibili per le istruzioni srotolate.

Note

Annotazioni

Fonti