Predizione delle diramazioni

In informatica, la predizione delle diramazioni (branch prediction) è il compito della BPU (Branch Prediction Unit), una componente della CPU che cerca di prevedere l'esito di un'operazione su cui si basa l'accettazione di una istruzione di salto condizionato, evitando rallentamenti che possono essere molto evidenti in una architettura con pipeline.

Per fare un esempio molto pratico, la CPU si comporta come un turista che non sa quale strada prendere ad un bivio; mentre consulta la cartina, imbocca una strada sperando nell'intuito. Se indovina, evita di fermarsi al bivio e perdere tempo; se non indovina, non deve tornare al bivio, ma è come se ripartisse istantaneamente dal bivio. L'importanza di questa operazione è evidente soprattutto per i microprocessori moderni, superscalari e con lunghe pipeline, che per ogni errore di previsione devono sprecare molti cicli di clock di lavoro prezioso.

La predizione delle diramazioni non va confusa con la predizione dell'indirizzo di arrivo della diramazione. Questa predizione è svolta dall'unità branch target predictor che, data la predizione dell'unità di predizione delle diramazioni, cerca di predire l'indirizzo di arrivo del salto e di caricare le istruzioni corrispondenti prima che il salto sia svolto, in modo da evitare rallentamenti dovuti al caricamento delle istruzioni dopo il salto.

Predizione elementare

I primi esemplari di SPARC e MIPS (due delle prime architetture RISC commerciali) eseguivano una specie di predizione, molto elementare: non consideravano mai il salto accettato, e decodificavano l'istruzione seguente. L'operazione di salto era effettuata solo dopo che la condizione era stata valutata.

Entrambe le CPU effettuavano questa predizione in fase di decodifica, e dedicavano al fetch delle istruzioni un solo ciclo di clock. In questo modo per effettuare un salto servivano due cicli di clock, ma dopo il primo la CPU aveva già effettuato il fetch dell'istruzione subito successiva al salto, l'esecuzione di questa istruzione non necessaria è definito branch delay slot.

Predizione statica

I processori che impiegano questa tecnica considerano sempre i salti verso la parte precedente del codice come "accettati" (ipotizzando che siano le istruzioni riguardanti un ciclo) e i salti in avanti sempre come "non accettati" (ipotizzando che siano uscite precoci dal ciclo o altre funzioni di programmazione particolari). Per cicli che si ripetono molte volte, questa tecnica fallisce solo alla fine del ciclo.

La predizione statica è usata come paracadute quando non ci siano elementi per usare altre tecniche come la predizione dinamica e il processore deve andare alla cieca.

Predizione della linea successiva

Alcuni processori superscalari (es.: MIPS R8000 e DEC Alpha EV6/EV8) eseguivano col fetch di una linea di istruzioni, quello di un puntatore alla successiva. Questo metodo è piuttosto diverso dagli altri trattati perché esegue la previsione sia della scelta della diramazione che dell'obiettivo del salto.

Quando un puntatore indica un gruppo di 2, 4 o 8 istruzioni, solitamente l'istruzione ricercata non è la prima (per un fatto statistico), così la scansione delle prime istruzioni è tempo perso. Generalizzando, sono scartate rispettivamente 0,5, 1,5 e 3,5 istruzioni decodificate. Lo stesso discorso vale per le istruzioni successive all'istruzione di salto, scartate con identica distribuzione media.

Le istruzioni scartate dall'unità di predizione fanno guadagnare quasi un completo ciclo di fetch, anche con predizioni eseguite solo sulla linea successiva e in un solo ciclo di clock.

Predizione bimodale

Questa tecnica sfrutta una tabella di contatori a due bit, indicizzata con i bit meno significativi dell'indirizzo dell'istruzione cui si riferiscono (a differenza della cache per le istruzioni. Questa tabella non ha tag, quindi uno stesso contatore può essere riferito a più istruzioni: ciò è definito interferenza o aliasing e porta a una perdita di precisione nella previsione). Ogni contatore può trovarsi in uno di quattro stati:

Strongly not taken, fortemente non scelto;
Weakly not taken, debolmente non scelto;
Weakly taken, debolmente scelto;
Strongly taken, fortemente scelto.

Ogni volta che una condizione è valutata, il contatore relativo è aggiornato secondo il risultato, e la volta successiva è preso come riferimento per la previsione. Un pregio di questo sistema è che i cicli sono sempre accettati, e fallisce solo la previsione relativa all'uscita del ciclo, mentre un sistema con contatori a bit singolo fallisce sia la prima che l'ultima istruzione.

Esempi di unità di predizione molto grandi basate su questo sistema hanno ottenuto una percentuale di successo pari al 93,5% su benchmark SPEC.

Predizione locale

La predizione bimodale fallisce all'uscita di ogni ciclo: per cicli che si ripetono con andamento sempre simile a se stesso si può fare molto meglio.

Con questo metodo ci si avvale di due tabelle. Una è indicizzata con i bit meno significativi dell'istruzione relativa, e tiene traccia della condizione nelle ultime n esecuzioni. L'altra è una tabella molto simile a quella usata nella predizione bimodale, ma indicizzata sulla base della prima. Per effettuare una predizione, l'unità cerca, grazie alla prima tabella, la parte della seconda che tiene traccia del comportamento della condizione non in media, ma a quel punto del ciclo.

Sui benchmark SPEC, sono stati ottenuti risultati intorno al 97,1%.

Questa tecnica è più lenta perché richiede il controllo di due tabelle per effettuare ogni previsione. Una versione più veloce organizza un insieme separato di contatori bimodali per ogni istruzione cui si accede, così il secondo accesso all'insieme può procedere in parallelo con l'accesso all'istruzione. Questi insiemi non sono ridondanti, poiché ogni contatore traccia il comportamento di una singola condizione.

Predizione globale

Nella predizione globale si fa affidamento sul fatto che il comportamento di molte condizioni si basa su quello di condizioni vicine e valutate da poco. Si può così tenere un unico registro che tenga conto del comportamento di ogni condizione valutata da poco, e usarne i valori per indicizzare una tabella di contatori bimodali. Questo sistema è di per sé migliore della predizione bimodale solo per grandi tabelle, e in nessun caso è migliore della predizione locale.

Se invece si indicizzano i contatori bimodali con la storia recente delle condizioni, concatenata ad alcuni bit dell'indirizzo delle istruzioni, si ottiene un previsore gselect, che supera la previsione locale in tabelle piccole ed è staccato di poco in tabelle maggiori di un KB.

Si ottiene un metodo ancora migliore per le tabelle più grandi di 256 B, detto gshare, sostituendo nel gselect la concatenazione con l'operazione logica XOR.

Quest'ultimo metodo ottiene nei benchmark un'efficienza del 96,6%, di poco inferiore alla predizione locale.

Le predizioni globali sono più facili da rendere più veloci della predizione locale poiché richiedono il controllo di una sola tabella per ogni previsione.

Altri progetti

Wikimedia Commons contiene immagini o altri file sulla predizione delle diramazioni

Collegamenti esterni

(EN) Denis Howe, branch prediction, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica