Predizione delle diramazioni
Da Wikipedia, l'enciclopedia libera.
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 il passeggero consulta la cartina, imbocca una strada basandosi sull'intuito. Se indovina, evita di fermarsi al bivio e perdere tempo; se non indovina, non deve tornare al bivio come il povero turista, 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 viene 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.
Indice |
[modifica] Predizione elementare
I primi esemplari di SPARC e MIPS (due delle prime architetture RISC commerciali) facevano una specie di predizione, molto elementare: non consideravano mai il salto accettato, e decodificavano l'istruzione seguente. L'operazione di salto veniva effettutata solo dopo che la condizione veniva 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 viene definito branch delay slot.
[modifica] 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 sono elementi per usare altre tecniche come la predizione dinamica e il processore deve andare "alla cieca".
[modifica] 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 qui 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, vengono scartate rispettivamente 0,5, 1,5 e 3,5 istruzioni decodificate. Lo stesso discorso vale per le istruzioni successive all'istruzione di salto, che devono essere 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.
[modifica] Predizione bimodale
Questa tecnica sfrutta una tabella di contatori a due bit, e indicizzati con i bit meno significativi dell'indirizzo dell'istruzione cui si riferiscono (a differenza della cache per le istruzioni, questa tabella non ha tag e 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 questi quattro stati:
- Strongly not taken, "non accettato molto spesso";
- Weakly not taken, "non accettato poco spesso";
- Weakly taken, "accettato poco spesso";
- Strongly taken, "accettato molto spesso".
Ogni volta che una condizione è valutata, il contatore relativo viene aggiornato secondo il risultato, e la volta successiva viene preso come riferimento per la previsione. Un pregio di questo sistema è che i cicli vengono sempre accettati, e viene fallita 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.
[modifica] Predizione locale
La predizione bimodale fallisce all'uscita di ogni ciclo: per cicli che si ripetono con andamento sempre simile a sé 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, in quanto ogni contatore traccia il comportamento di una singola condizione.
[modifica] 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 tiene 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 non è migliore della predizione locale in nessun caso.
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 e viene 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 in quanto richiedono in controllo di una sola tabella per ogni previsione.
