Esecuzione fuori ordine

Schema concettuale dell'esecuzione fuori ordine. Il programma viene caricato come istruzioni seriali, le istruzioni vengono analizzate, riordinate tenendo conto delle dipendenze, eseguite in parallelo, ed riordinate prima di provvedere al salvataggio dei dati in memoria.

In informatica l'esecuzione fuori ordine indica la capacità di molti processori di eseguire le singole istruzioni senza rispettare necessariamente l'ordine imposto dal programmatore. Il processore in sostanza analizza il codice che dovrà eseguire, individua le istruzioni che non sono vincolate da altre istruzioni e le esegue in parallelo con il codice principale. Questa strategia permette di migliorare le prestazioni dei moderni microprocessori dato che l'esecuzione fuori ordine permette di riempire unità funzionali del processore che altrimenti rimarrebbero inutilizzate.

Storia

L'esecuzione fuori ordine è diventata nota in ambito industriale verso la fine degli anni 70 e l'inizio degli anni 80, periodo dove si concentrano la maggior parte delle ricerche sull'argomento. La prima ricerca di un certo peso sull'argomento è quella svolta da Yale Patt sul simulatore HPSim. Un documento di James E. Smith e A.R. Pleszkun pubblicato nel 1985 include un'accurata analisi di come poter gestire efficacemente le eccezioni durante l'esecuzione fuori ordine delle istruzioni.

La prima macchina ad eseguire l'esecuzione fuori ordine e probabilmente il CDC 6600 (1964) che utilizzava lo scoreboarding per risolvere i conflitti. Meno di tre anni dopo con l'IBM 360/91 (1966) venne presentato l'Algoritmo di Tomasulo. IBM ha anche realizzato il primo processore con esecuzione fuori ordine, il POWER 1 (1990) per le macchine RS/6000. Con la presentazione da parte di Intel del Pentium Pro (1995) si ha la diffusione dell'esecuzione fuori ordine anche nel mercato degli IBM compatibili. In molti altri produttori adottarono questa tecnologia per i loro processori come IBM/Motorola per il PowerPC 601 (1992/1993), Fujitsu/Hal per lo Sparc64 (1995), HP per il PA-8000 (1996) la MIPS Technologies per il MIPS R-10000 (1996), AMD per l'K5 (1996) e la Digital Equipment Corporation con il DEC Alpha 21264 (1998). Eccezioni notevoli sono la Sun Microsystems con i processori UltraSparc l'alleanza HP/Intel con i processori Itanium e la Transmeta con il Crusoe.

Implementazione

La rilevazione delle dipendenza tra le varie istruzioni è un compito complesso dato che le istruzioni possono essere vincolate in vari modi. Per esempio se si ha un'istruzione che esegue una somma tra due registri e poi il risultato della somma viene utilizzato come operando per una divisione va da se che la divisione e la somma non possono essere eseguite in parallelo senza generare conflitti. Il problema può essere risolto replicando delle unità funzionali oppure eseguendo in parallelo all'istruzione di somma un'istruzione che non ha dipendenze e rimandando la divisione. In generale queste unità funzionali decodificano le istruzioni e pongono le istruzioni che non hanno vincoli (o che hanno vincoli che sono stati risolti) entro buffer (reservation station) che alimenta le pipeline. Dopo le pipeline vi è un'unita che utilizzando delle etichette collegate alle istruzioni ricostruisce l'ordine cronologico delle istruzioni facendo uscire dal processore i risultati delle istruzioni con l'ordine cronologico impostato dal programma. Questa unità inoltre provvede ad eliminare le eventuali operazioni eseguite erroneamente dal processore. La presenza di unità di predizione dei salti implica che il processore spesso esegua delle istruzioni presupponendo che il processore esegua ( o non esegua) un certo salto. Ma, se la previsione fornita dall'unità di predizione dei salti si dovesse dimostrare non corretta le istruzioni eseguite erroneamente vanno eliminate per preservare il corretto funzionamento del programma.

Svantaggi

L'esecuzione di istruzioni fuori ordine implica la realizzazioni di alcune unità aggiuntive all'interno del microprocessore che ne innalzano i costi di sviluppo e di realizzazione. La complessità di queste unità aggiuntive dipende molto dal set di istruzioni da analizzare. Alcuni set di istruzioni segnalano esplicitamente al processore quali istruzioni possono essere eseguite fuori ordine e quindi l'implementazione dell'esecuzione fuori ordine è un'operazione banale mentre altri set di istruzioni (architettura x86 per esempio) non prevedevano minimamente questa possibilità e quindi la realizzazione di queste unità richiede molti transistor e complica di molto l'architettura del processore. Comunque visto il basso costo dei singoli transistor e vista la richiesta di prestazioni sempre più elevate quasi tutti i processori attuali implementano l'esecuzione fuori ordine.