Branch prediction

I salti costano cicli perché destinazione e condizione si conoscono tardi nella PipelineIdea della catena di montaggio; pipeline a 5 stadi IF, ID, EX, MEM, WB; tempo di ciclo, tempo per n istruzioni in una pipeline a k stadi e speedup con esempi svolti; registri di pipeline; scrittura e lettura dei registri nello stesso ciclo; limiti (stadi sbilanciati, hazard).Pipeline → (vedi Hazard nella pipelineHazard strutturali, sui dati e sul controllo; dipendenze RAW, WAR e WAW; stalli e bolle con diagrammi; data forwarding (bypass) e caso load-use; riordino delle istruzioni da parte del compilatore e dell'hardware; costo dei salti.Hazard nella pipeline →). I salti condizionati sono circa il 15–20% delle istruzioni: senza contromisure le prestazioni crollano.

Tecniche senza predizione

• Stallo: appena in ID si riconosce un salto, si ferma il prelievo finché non si sa dove andare. Semplice ma sempre costoso.
• Flussi multipli: si prelevano entrambe le strade e si scarta quella sbagliata. Richiede risorse doppie e non regge salti a breve distanza l'uno dall'altro.
• Prelievo anticipato del bersaglio: si preleva anche l'istruzione di destinazione e la si tiene pronta.
• Anticipare la decisione: calcolare condizione e indirizzo già in ID (un sommatore e un comparatore in più): il costo scende a 1 ciclo.
• Loop buffer (o buffer circolare): una piccola memoria velocissima (es. 256 byte) con le ultime istruzioni prelevate, indirizzata dai bit bassi dell'indirizzo (8 bit per 256 byte) e con i bit alti come etichetta, come una cache. Un ciclo breve che salta all'indietro trova le istruzioni già nel buffer.
• Salto ritardato (delayed branch, MIPS): l'istruzione subito dopo il salto (delay slot) viene sempre eseguita. Il compilatore ci mette un'istruzione utile che va eseguita comunque (presa da prima del salto), oppure una nop.

Predizione statica

Decisa senza guardare la storia dell'esecuzione:

• sempre non preso: si continua a prelevare in sequenza; se il salto è preso si buttano le istruzioni prelevate;
• sempre preso;
• in base al codice operativo o alla direzione: i salti all'indietro (chiusura dei cicli) presi, quelli in avanti non presi. Il compilatore può anche indicare la previsione con un bit nell'istruzione.

Predizione dinamica

Si usa la storia dello stesso salto, memorizzata in una tabella indicizzata dai bit bassi dell'indirizzo del salto.

1 bit: si prevede ciò che il salto ha fatto l'ultima volta. In un ciclo che si ripete sbaglia due volte per ogni esecuzione completa del ciclo: all'uscita (previsto preso, invece non preso) e al primo giro successivo (previsto non preso, invece preso).

2 bit: quattro stati, due "prevedi preso" e due "prevedi non preso"; per cambiare previsione servono due errori consecutivi.

(Esistono varianti con transizioni leggermente diverse tra gli stati deboli; l'idea è la stessa.)

Esempio: un ciclo interno di 10 iterazioni eseguito più volte, il salto di chiusura è preso 9 volte e non preso 1.

• 1 bit: 2 errori ogni 10 → 80% di previsioni corrette.
• 2 bit: all'uscita lo stato passa da 11 a 10 (1 errore); al giro successivo prevede ancora "preso" ed è giusto → 1 errore ogni 10, 90%.

Branch Target Buffer (BTB): una cache che, dato l'indirizzo dell'istruzione in IF, dà subito l'indirizzo di destinazione previsto e la previsione. Così il prelievo dalla destinazione inizia senza nemmeno decodificare il salto.

I processori attuali usano predittori più elaborati (che combinano la storia del singolo salto con quella degli ultimi salti eseguiti) e superano il 95% di previsioni corrette.

Costo di una predizione errata

Le istruzioni prelevate sulla strada sbagliata vanno annullate (non devono aver scritto registri o memoria). Il costo è pari al numero di stadi tra IF e lo stadio in cui il salto si risolve: 1–2 cicli in una pipeline a 5 stadi, 15–20 cicli nelle pipeline profonde. Per questo la qualità del predittore conta tanto più quanto più la pipeline è lunga.

In ARM a 32 bit l'esecuzione condizionata (vedi Strutture di controllo in assembly ARMSalti B e condizionati, codici di condizione con e senza segno; traduzione di if, if-else, while, for e do-while da C ad ARM; esecuzione condizionata per eliminare salti brevi; switch con tabella di salto.Strutture di controllo in assembly ARM →) evita del tutto i salti brevi.

Errori tipici

• Dire che con il predittore a 2 bit si cambia previsione dopo un errore: ne servono due consecutivi.
• Dimenticare che l'istruzione nel delay slot viene eseguita anche se il salto è preso.