Srotolamento del loop: differenze tra le versioni

Versione delle 02:50, 26 apr 2009

Versione attuale delle 16:22, 5 ago 2025

(26 versioni intermedie di 15 utenti non mostrate)

Riga 1:

{{F|linguaggi di programmazione|giugno 2023}}

Lo '''srotolamento del loop''' ({{Inglese|loop unrolling}}) è una tecnica di [[Ottimizzazione (informatica)|ottimizzazione]] utilizzata dai [[compilatore|compilatori]] e dai [[microprocessore|microprocessori]] per migliorare l'esecuzione dei programmi.

Questa tecnica fa parte delle tecniche di trasformazione dei loop. Questae tecnicapunta comea tuttevelocizzare quelleil cheprogramma elaborano i loop puntano a ridurreriducendo le istruzioni nonche indispensabiligestiscono duranteil l'esecuzioneflusso del loop inintervenendo modosull'algebra dadei renderepuntatori ile programmasui piùcontrolli di velocefine loop. Questa tecnicaInoltre, raggruppa istruzioni eseguite in più loop diversi in un singolo loopciclo in modo tale da ridurre i salti danel codice effettuareeffettuati durante l'esecuzione. delQuesta tecnica può essere looputilizzata anche per rendere i programmi più facilmente [[calcolo parallelo|parallelizzabili]].

QuestaUno tecnicadegli hasvantaggi loprincipali svantaggiodel di incrementare''loop lunrolling'' è il maggior uso dei [[registro (informatica)|registri]] del microprocessore eed incrementaun lacodice dimensionecompilato delpiù codicegrande in termini di dimensioni.

Questa tecnica può essere utilizzata anche per rendere i programmi più facilmente [[calcolo parallelo|parallelizzabili]].

== 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:

<code>

for (int x = 0; x < 100; x++)

Riga 16 ⟶ 14:

}

Ogni cancellazione richiede l'esecuzione di un [[Salto (informatica)|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:

</code>

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:

<code>

for (int x = 0; x < 100; x += 5)

Riga 29 ⟶ 25:

}

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

</code>

Nel nuovo codice 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:

<code>

for i:=1:8 do

if i mod 2 = 0 then disparipari(i) else paridispari(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 pericolareparticolare configurazione di if metterebbe in crisi le [[Predizione delle diramazioni|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:

</code>

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 [[Predizione delle diramazioni|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:

<code>

dispari(1); pari(2);

Riga 51 ⟶ 43:

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:

</code>

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:

<code>

x(1) = 1;

Riga 61 ⟶ 51:

Next i;

dopo lo srotolamento del codice diventa

</code>

dopo lo srotolamento del codice diventa

<code>

x(1):=1;

Riga 70 ⟶ 58:

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

</code>

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<ref>{{en}}[http://www.lysator.liu.se/c/duffs-device.html Duff's device]</ref>. La porzione di codice

<syntaxhighlight lang="c">

<code>

do {

*to++ = *from++;

} while (--count > 0);

</syntaxhighlight>

</code>

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

Ottimizzando queste istruzioni <ref group="N">in realtà l'algoritmo originale prevedeva di non incrementare il puntatore <ttkbd>to</ttkbd>, in quanto era utilizzato per copiare dati in un registro di I/O</ref> 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.

<syntaxhighlight lang="c">

<code>

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);

}

}

</syntaxhighlight>

</code>

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

== Note ==

;Annotazioni

<references group="N"/>

;Fonti

<references/>

{{Portale|informatica}}

[[Categoria:Compilatori]]

[[Categoria:Compilatori]]

[[en:Loop unwinding]]

[[ja:ループ展開]]

[[pl:Odwijanie pętli]]

[[ru:Размотка цикла]]