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, e 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. 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.

Architettura

L'esecuzione fuori ordine è una forma limitata di architettura dataflow. In un'architettura dataflow l'esecuzione del programma non è guidata dal flusso del programma, ma dalla disponibilità degli operandi da processare. In un'architettura dataflow appena tutti gli operandi di un'istruzione sono disponibili l'istruzione è marcata come eseguibile e appena un'unità di calcolo risulta disponibile l'istruzione viene eseguita. In un'architettura fuori ordine si segue lo stesso principio solo che non è l'intero programma a essere analizzato alla ricerca di operazioni pronte per essere eseguite ma solo una finestra di esecuzione. In questa finestra vengono analizzate le disponibilità degli operandi e le istruzioni con tutti gli operandi disponibili vengono marcate come eseguibili. Questo permette di estrarre dal codice buona parte dell'instruction level parallelism mantenendo l'architettura relativamente semplice. Una architettura dataflow in teoria riuscirebbe a estrarre un livello maggiore di instruction level parallelism e quindi otterrebbe prestazioni migliori, ma le complicazioni a livello architetturali sono talmente elevate da rendere non conveniente l'approccio per un sistema generico.

Storia

L'esecuzione fuori ordine divenne nota in ambito industriale verso la fine degli anni 70 e l'inizio degli anni 80, periodo in cui si concentrarono la maggior parte delle ricerche sull'argomento. La prima ricerca di un certo peso sull'argomento fu svolta da Yale Patt sul simulatore HPSim. Un documento di James E. Smith e A.R. Pleszkun pubblicato nel 1985 analizzò come gestire in modo efficiente un'eccezione durante un'esecuzione fuori ordine e permise di gettare i presupporti teorici per la realizzazione di una macchina che implementasse questa modalità di esecuzione.

La prima macchina ad eseguire l'esecuzione fuori ordine fu probabilmente il CDC 6600 (1964) che utilizzava lo scoreboarding per risolvere i conflitti. Secondo la terminologia moderna lo scorebording non è propriamente una tecnica che permette l'esecuzione fuori ordine dato che le istruzioni vengono bloccate al primo conflitto RAW (Read After Write). Lo scoreboarding avvia l'esecuzione delle istruzioni in ordine ma può terminare l'esecuzione delle stesse fuori ordine. Meno di tre anni dopo con l'IBM 360/91 (1966) venne presentato l'Algoritmo di Tomasulo, questo algoritmo permetteva una piena esecuzione fuori ordine dato che le istruzioni potevano essere completate e avviate non in ordine. 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 ebbe la diffusione dell'esecuzione fuori ordine anche nel mercato degli IBM compatibili. In seguito 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 il 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 dipendenze 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 sé 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 (ROB) 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.

Nel gennaio 2018 è stata pubblicata una vulnerabilità nell'implementazione dell'esecuzione fuori ordine da parte dei processori Intel e ARM, chiamata Meltdown.

Svantaggi

L'esecuzione di istruzioni fuori ordine implica la realizzazione 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.

Collegamenti esterni

• (EN) "Implementation of precise interrupts in pipelined processors", a paper by Smith and Pleszkun (1985).