Srotolamento del loop

Da Wikipedia, l'enciclopedia libera.

Lo srotolamento del loop è 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. Questa tecnica come tutte quelle che elaborano i loop puntano a ridurre le istruzioni non indispensabili durante l'esecuzione del loop in modo da rendere il programma più veloce. Questa tecnica raggruppa istruzioni eseguite in più loop in un singolo loop in modo da ridurre i salti da effettuare durante l'esecuzione del loop.

Questa tecnica ha lo svantaggio di incrementare l'uso dei registri del microprocessore e incrementa la dimensione del codice.

Questa tecnica può essere utilizzata anche per rendere i programmi più facilmente parallelizzabili.

Primo esempio[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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 dispari(i) else pari(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 pericolare 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Un particolare algoritmo di srotolamento è stato proposto da Tom Duff nel 1983[1]. 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 [2] 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[modifica | modifica wikitesto]

  1. ^ (EN) Duff's device
  2. ^ in realtà l'algoritmo originale prevedeva di non incrementare il puntatore to, in quanto era utilizzato per copiare dati in un registro di I/O