Architetture dei processori/Unità predizione salti

Pentium IV, processore utilizzante la predizione della linea successiva

Esistono molte tecniche per implementare la predizione dei salti. Tecniche più complesse portano ad ottenere percentuali di previsione migliori ma comportano anche costi maggiori per via del maggior numero di transistor impiegati e quindi spesso non vengono utilizzate le migliori strategie di previsione ma strategie più semplici e quindi più economiche da implementare.

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 effettuata solo dopo che la condizione veniva valutata.

Entrambe le CPU effettuavano questa "predizione" in fase di decodifica e dedicavano al fetch delle istruzioni (il caricamento della istruzione dalla cache) 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; piuttosto che sprecare questo lavoro, entrambi i microprocessori eseguivano anche queste istruzioni, avvantaggiandosi magari per fasi successive del lavoro. Ovviamente i compilatori (o i programmatori assembler) devono essere ben consci di questa caratteristica pena bug molto difficili da scovare.

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

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.

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:

1. Strongly not taken, "non accettato molto spesso";
2. Weakly not taken, "non accettato poco spesso";
3. Weakly taken, "accettato poco spesso";
4. 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.

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.

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.

Esistono altre tipologie di predizioni ma sono tecniche che richiedono un dispendio di transistor eccessivo per le prestazioni che effettivamente offrono. Data l'importanza delle predizione dei salti comunque tutti i processori moderni implementano unità di predizione dei salti molto avanzate. Per esempio il POWER 5 prodotto da IBM implementa tre unità di predizione dei salti. Due unità cercano di predire i salti utilizzando strategie diverse e la terza unità tiene traccia delle percentuali di successo delle due unità e a seconda dell'istruzione sceglie l'unità che ha avuto la percentuale di successo maggiore.