Predizione dei salti: contatori a due bit, predittori correlati e bersagli

In un programma tipico un’istruzione su cinque o sei è un salto. In un processore con una pipeline profonda e un’ampia finestra fuori ordine, ogni salto di cui non si conosce la direzione bloccherebbe il flusso per decine di cicli. La soluzione è indovinare, e farlo molto bene: i predittori moderni sbagliano meno di un salto su cento. In questa lezione vediamo il costo di un errore, i contatori a due bit con la dimostrazione del loro vantaggio sui cicli, i predittori correlati, la previsione degli indirizzi e come si scrive codice che i predittori amano.

Il costo di un errore

Quando il processore scopre di aver previsto male, scarta tutte le istruzioni speculative e riparte dall’indirizzo giusto (lezione sull’esecuzione fuori ordine). I cicli persi, la penalità, sono circa quanti ne servono dal prelievo dell’istruzione alla risoluzione del salto: 15-20 nei processori moderni. Con l’equazione delle prestazioni con gli stalli:

con la frazione di istruzioni che sono salti, la frazione prevista male e la penalità. Con il 20 % di salti, il 5 % di errori e 15 cicli di penalità si aggiungono 0,15 cicli per istruzione: su un processore che potrebbe completarne 4 per ciclo (CPI ideale 0,25), il tempo di esecuzione cresce del 60 %. Ogni punto percentuale di precisione conta.

Previsione statica e contatori a un bit

La previsione statica decide senza guardare la storia: per esempio “i salti all’indietro sono presi” (sono quasi sempre la chiusura di un ciclo) e “quelli in avanti non lo sono”. Funziona per circa il 70 % dei salti.

La previsione dinamica più semplice ricorda, per ogni salto, che cosa ha fatto l’ultima volta: un bit, in una tabella indicizzata con alcuni bit dell’indirizzo del salto. Ha un difetto evidente sui cicli.

Il contatore a due bit

Il contatore saturante a due bit conta da 0 a 3: aumenta quando il salto è preso, diminuisce quando non lo è, senza superare gli estremi. Si prevede “preso” negli stati 2 e 3, “non preso” negli stati 0 e 1.

Teorema. Un ciclo interno con iterazioni, eseguito ripetutamente, ha un salto di chiusura preso volte e non preso all’ultima. Il predittore a un bit sbaglia due volte per ogni esecuzione del ciclo, quello a due bit una sola.

Dimostrazione. *Un bit.* All’ultima iterazione il bit dice “preso” (l’ultima volta lo era) e il salto non lo è: primo errore, e il bit diventa “non preso”. Alla prima iterazione dell’esecuzione successiva il bit dice “non preso” ma il salto è preso: secondo errore. Le altre iterazioni sono previste bene. *Due bit.* Dopo le iterazioni prese il contatore è a 3. All’ultima iterazione prevede “preso” e sbaglia, ma scende solo a 2, che prevede ancora “preso”. Alla prima iterazione successiva la previsione è giusta e il contatore torna a 3. Un solo errore per esecuzione. ∎

Con , la precisione passa dall’80 al 90 %. L’isteresi del contatore impedisce che un’eccezione isolata cambi la previsione.

I predittori correlati

Molti salti dipendono da quello che hanno fatto i salti precedenti: se un if (x > 0) è stato preso, un successivo if (x < 0) non lo sarà. Un predittore correlato tiene un registro della storia globale, gli esiti degli ultimi salti eseguiti (1 se preso, 0 se no), e la usa insieme all’indirizzo del salto per scegliere il contatore. Nel predittore gshare l’indice della tabella è lo XOR tra i bit dell’indirizzo e quelli della storia: lo stesso salto usa contatori diversi in contesti diversi.

I predittori odierni, come la famiglia TAGE, combinano tabelle con storie di lunghezza diversa, da pochi salti a centinaia, e scelgono la previsione della tabella con la storia più lunga che ha un’informazione affidabile. Raggiungono precisioni del 97-99 % sui programmi tipici. Alcuni usano anche piccoli percettroni, una forma elementare di rete neurale.

Prevedere anche dove si salta

Sapere che un salto è preso non basta: bisogna sapere dove va, prima ancora di aver decodificato l’istruzione. Il buffer dei bersagli (BTB) è una cache indicizzata con l’indirizzo dell’istruzione che restituisce l’indirizzo di destinazione dell’ultima volta. I ritorni da funzione hanno un predittore apposito, la pila degli indirizzi di ritorno, che imita lo stack delle chiamate: a ogni chiamata si spinge l’indirizzo di ritorno, a ogni ritorno lo si estrae. I salti indiretti (le chiamate a funzioni virtuali, i switch compilati con tabelle) hanno predittori che usano anche la storia.

Scrivere codice prevedibile

Il predittore non fa miracoli con i salti che dipendono da dati casuali. L’esempio classico: un ciclo che somma solo gli elementi di un vettore maggiori di una soglia gira molto più veloce se il vettore è ordinato, perché il salto diventa una lunga sequenza di “non preso” seguita da una lunga sequenza di “preso”. Su dati casuali il predittore sbaglia la metà delle volte. Le contromisure:

• trasformare il salto in un’operazione senza salti, con le mosse condizionate (cmov su x86, la selezione in RISC-V con estensioni) o con aritmetica: somma += (x > soglia) * x. I compilatori lo fanno da soli quando i due rami sono brevi;
• riordinare i dati o i controlli, mettendo prima i casi più frequenti;
• con i profili d’esecuzione, lasciare che il compilatore disponga il codice in modo che il percorso comune non salti.