Nei precedenti due articoli (qui e qui) ho brevemente descritto alcuni schemi di branch prediction, illustrando i punti di forza di ognuno. Alcuni sono facili da costruire e moderatamente efficienti, altri funzionano bene per salti con forte correlazione con la loro storia locale, altri ancora funzionano perfettamente ma solo per alcuni tipi di salti particolari (ad esempio i loop), eccetera.
Visto che ogni programma ha un mix di diversi tipi di salti e diversi programmi hanno un diverso mix, quale di quei predittori scegliere? La soluzione più semplice è quella di scegliere il predittore che fa meglio in media, per un qualche definizione della media: ad esempio, in fase di progettazione, si possono ottenere delle stime dando in pasto dei micro-benchmark al simulatore della CPU (come M5). Benchè la soluzione sia ragionevole vorremmo fare di meglio: vorremmo poter avere a disposizione diversi predittori e usare per ogni salto quello che ne predice meglio il comportamento. Per fare questo dobbiamo usare un predittore ibrido: ci serve cioè un sistema per combinare insieme diversi predittori “base” e generare politiche di aggiornamento sia per i predittori “base” che per il meccanismo di selezione del predittore. Questi sistemi sono ampiamente usati in processori reali.
Tournament predictor
Questo predittore fu proposto dal McFarling (lo stesso del predittore gshare) nel ’93, ed è il primo e il più semplice schema di predittore ibrido. Il predittore consiste di due predittori P0 e P1 (che possono essere un qualsiasi predittore visto nelle puntate precedenti) e un meta-predittore M. Il meta-predittore è una tabella di contatori a 2 bit che funziona come un normale predittore di Smith e dice quale dei predittori, P0 o P1, va usato per generare la predizione di salto; il bit più significativo viene usato per pilotare il mux di selezione:
Quando il salto viene eseguito e la sua direzione è nota, essa viene usata per aggiornare tutte le strutture (P0, P1 e M). I predittori P0 e P1 vengono aggiornati secondo le loro regole. M invece, che è un contatore a saturazione, viene incrementato quando P1 ha predetto correttamente e P0 no, e decrementato nel caso opposto. Se entrambi i predittori hanno predetto correttamente o hanno sbagliato M non cambia, perchè non c’è informazione sufficiente per dire quale dei due si comporta meglio per quel particolare salto.
Una cosa interessante da notare è che P0 e P1 possono essere predittori di qualsiasi tipo, anche un altro predittore ibrido! Ciò significa che è possibile innestare ricorsivamente un predittore tournament dentro un altro, per creare un albero di predittori.
Un predittore di questo tipo è stato usato nell’Alpha 21264 per sfruttare sia la storia locale che quella globale dei salti.
Classificazione dei salti
Questo algoritmo di meta-predizione è di tipo statico, cioè richiede una fase di analisi del codice tramite un profiler. Il programma viene eseguito e il profiler calcola, per ogni salto, quante volte esso viene preso e quante no. I salti vengono quindi divisi in 3 categorie: quelli fortemente non presi (es. < 5%), quelli fortemente presi (es. > 95%) e gli altri. I salti fortemente polarizzati vengono quindi predetti in modo statico (servono ovviamente dei bit nelle istruzioni di salto per codificare questo suggerimento, detto branch hint, e renderlo noto al predittore in fase di esecuzione) mentre gli altri vengono predetti con un normale predittore dinamico, ad esempio un Tournament:
Il vantaggio di questo schema è che i salti fortemente polarizzati, essendo predetti staticamente, non occupano spazio nel predittore dinamico: questo porta ad avere meno aliasing e aumenta le prestazioni del predittore; questo principio è lo stesso del predittore branch filtering. Come tutti i predittori che usano branch hint lo svantaggio è che il “suggerimento” non è disponibile fino a che la decodifica dell’istruzione non è stata completata, il che è un problema perchè il predittore deve generare una nuova predizione ad ogni ciclo di clock per il ciclo successivo, prima che la decodifica sia completata (il problema può essere mitigato tramite pre-decodifica paziale delle istruzioni in cache).
Predittore multi-ibrido
Mentre il predittore tournament è in grado di scegliere tra due diversi predittori di base (a meno di non costruire un albero ricorsivo di predittori) il predittore multi-ibrido può scegliere dinamicamente tra un numero arbitrario di predittori (Evers 1996):
L’indice del salto è usato per accedere ad una tabella di contatori a 2 bit che contiene un contatore per ogni predittore. Il predittore il cui contatore vale 3 (il massimo) viene selezionato per generare la predizione di salto; in caso due o più contatori valgano 3, un priority encoder viene usato per decidere quale scegliere. Tutti i contatori sono inizializzati a 3 e le regole di aggiornamento dei contatori della tabella sono congegnate in modo tale che almeno un contatore abbia sempre il valore massimo, semplificando il problema della selezione.
Lo schema venne proposto per risolvere un problema che si ha nei context switch. Quando si cambia processo, i predittori devono ripartire da zero ed essere riaddestrati da capo; predittori più complessi (e più precisi) richiedono sempre un periodo di addestramento superiore, per cui nelle fasi iniziali dell’addestramento un contatore più semplice può fornire predizioni migliori. Un predittore multi-ibrido può avere un mix di predittori semplici (che generano predizioni abbastanza precise nelle prime fasi dopo il context switch) e complessi (che generano predizioni molto precise una volta che hanno raccolto abbastanza informazioni sui pattern dei salti).
Questo algoritmo è quindi diverso da tutti gli altri visti finora perchè cerca non solo di associare predittori diversi a salti diversi, ma anche predittori diversi allo stesso salto, evolvendo da uno all’altro man mano che maggiori informazioni sul salto diventano disponibili.
Fusione delle predizioni
I predittori ibridi visti finora usano un meccanismo di selezione per scegliere un predittore tra N. Così facendo, però, essi scartano l’eventuale informazione utile contenuta negli altri predittori.
Questa classe di predittori cerca di fondere insieme le predizioni di tutti di N predittori individuali nella speranza di estrarre maggiore informazione sui salti. Uno di questi schemi è chiamato fusion table:
Le predizioni degli N predittori vengono concatenate all’indirizzo del salto e alla storia globale del salto; questo indice viene usato per accedere ad una normale tabella di contatori a saturazione a 2 bit.
Questo predittore è molto flessibile e può essere molto efficace perchè riesce a catturare salti con comportamenti molto diversi. Come sempre, la dimensione dell’indice deve essere tenuta sotto controllo: indici troppo lunghi risultano in tabelle molto grandi e quindi lente, con effetti deleteri sul funzionamento del circuito nel suo complesso.
il predittore multi-ibrido suona come una cosa malefica :-D
continuo a seguire con estremo interesse i tuoi articoli!
Che bello un nuovo articolo! :D
Questi dispositivi sono magnifici: sarà anche perché il branch prediction è stato uno degli argomenti che mi risultavano più oscuri, e scoprendoli così semplici (anche come li spieghi tu), è tutta un’altra cosa! :D
beh sono semplici a parole, poi costruirli con i constraint temporali corretti sarà un’opera assurda… Tutta quella logica ha delle latenze e più si fa complessa più aumenta la profondità (come numero di porte logiche da attraversare), e di conseguenza aumentano i tempi di propagazione che sforano facilmente il singolo ciclo di clock… bella impresa :-)
Infatti ricordo nei precedenti articoli che Pleg parlava proprio di questo aspetto, che ovviamente in questi predittori ibridi è peggiorato, a causa della presenza del metapredittore (che richiederà il suo tempo per essere elaborato oltre quello dei predittori di cui fa uso).
Veramente interessante, altro bell’articolo, continua così!
Grazie a tutti.
In effetti, coem sempre, il diavolo sta nei dettagli :) ad esempio, finora ho lasciato intendere che predizione e fetch avvengono in un solo ciclo di clock, ma per processori moderni (con pipeline lunghe) non e’ cosi’. Sia la cache istruzioni che il predittore possono prendere piu’ cicli di clock e quindi occupare multipli stadi di pipeline… e potrebbero prendere un numero di stadi diverso :) mettere insieme le due cose crea interazioni interessanti.
Ho ancora uno o due articoli da scrivere sulla branch prediction prima di passare oltre agli stadi successivi, dovrei riuscire a cacciare dentro da qualche parte qualcosina su cosa succede quando vai di super-pipelining.
:-O
sento un tremito nella forza…
Non temere, giovane Skywalker :D
@Antonio:
Io infatti parlavo solo della semplicità del principio di funzionamento; puoi immaginare, prima di leggere questi articoli pensavo che la branch prediction fosse una scatola magica, scoprire questi algoritmi che sono al contempo così ingegnosi e semplici è molto interessante!
@Pleg:
E’ anche interessante notare come per aumentare la velocità si aggiunge altra roba, la quale viene aggiunta altra roba per renderla più veloce… sembra quasi un controsenso! ;)
Visto che continui a dire che e’ “semplice” :) te ne butto li’ un’altra: in un processore superscalare macini piu’ istruzioni per ciclo di clock, quindi fai anche il fetch di piu’ istruzioni (“fetch group”). Quindi, in un singolo fetch group potresti avere piu’ branch: il predittore deve generare una predizione per tutti i branch e capire qual e’ il prossimo fetch group da prelevare dalla i-cache e qual e’ l’istruzione a cui saltare all’interno del gruppo (sempre che tu non voglia prevedere non l’indirizzo del salto, ma direttamente la linea e il set in cache in cui si trova il prossimo fetch group…)
Per il resto, beh si’ e’ sempre cosi’! Per questo la complessita’ dei chip (e l’area, e il consumo) cresce sempre piu’ che linearmente con le prestazioni: spremere quell’ultima goccia di prestazioni costa molto. Da cui e’ intuitivo capire perche’ nell’ultima decade si e’ passati dai core singoli ai multicore: tanti core piu’ piccoli sono piu’ facili (ed efficienti, e consumano meno) di un singolo core grosso (con questo non intendo dire che che un Sandy Bridge abbia un core semplice: ma 4 core superscalari a 4 vie e’ fattibile, un singolo core superscalare out-of-order a 16 vie no, oltre al fatto che sarebbe enorme ed inefficiente).
Purtroppo non tutti i problemi sono “parallelizzabili”, altrimenti il multicore sarebbe stato il classico “uovo di Colombo” per risolvere i problemi prestazionali.
Lo sviluppo di (singoli) core molto veloci continuerà sempre, e ci sarà ancora spazio per la ricerca (anche se parecchio è stato fatto negli ultimi vent’anni, specialmente per i CISC).
@Pleg:
Ok, ho capito cosa vuoi farmi capire! :)
Però il mio “semplice” è come dire che capire il funzionamento di un motore a scoppio è semplice; dopo quando vuoi costruirne uno ad alte prestazioni diventa complesso, ovvio! ;)
@Z80Fan: se vuoi ci sono anche i bellissimi post di Simone Serra sui motori a scoppio… :D
parafrasando… “è facile fare i filtri passa basso, con i condensatori degli altri” ^^,
@ Cesare
Senza dubbio, i core grossi e complessi non andranno mai via, sono necessari per far girare tutta la roba non parallelizzabile.
Facevo solo notare a Z80Fan che e’ proprio come dice, la complessita’ cresce piu’ che linearmente ed e’ proprio per questo che assistiamo, in questi anni, all’ingresso dei computer paralleli/multicore/eterogenei nel mercato consumer: proprio perche’, a causa di quella non-linearita’, scendere lungo la curva della complessita’ riduce i consumi (e la complessita’ di progettazione) piu’ velocemente di quanto fai calare le prestazioni.
(naturalmente, c’e’ chi come ARM sta _salendo_ la curva della complessita’, perche’ si trovava troppo in basso e, come si diceva, di core grossi e potenti ne hanno bisogno tutti; e’ come sempre un problema di bilanciamento).
@Antonio:
Infatti il paragone non era a caso. :)