di  -  giovedì 10 novembre 2011

Per trent’anni, prima che il raggiungimento del power wall terminasse la “corsa ai GHz” e iniziasse la “corsa ai core”, il modo più semplice e gettonato per aumentare le prestazioni dei processori è stato l’aumento della frequenza operativa, raggiungibile tramite pipeline più profonde e processi produttivi più raffinati.

Aumentare il numero di stadi di pipeline ha un doppio impatto sul front-end del processore (fetch e branch prediction):

  • da un lato, avere più stadi aumenta la branch misprediction, riducendo le prestazioni; questo rende necessario l’adozione di strategie di predizione più sofisticate per aumentare la precisione delle predizioni
  • dall’altro, il tempo di accesso alla cache (almeno di primo livello) e il tempo necessario per generare le predizioni deve diminuire, che significa che le dimensioni delle cache e dei predittori deve diminuire; questo causa un aumento dei cache miss e un peggioramento dell’accuratezza delle predizioni

In questo settimo (e ultimo!) articolo sulla branch prediction vedremo un paio di tecniche per risolvere questi problemi.

Line & way predictor

Che cosa significa predire il bersaglio di salto? Significa forse predire l’indirizzo che viene generato dall’istruzione di salto? Credo che tutti noi risponderemmo “ovviamente sì, che altro?! Se il salto va all’indirizzo 0x12345678, il predittore deve generare il valore 0x12345678″.

Questo sicuramente funzionerebbe… ma potrebbe non essere la cosa migliore da fare. Innanzitutto, quell’indirizzo è in genere un indirizzo virtuale, che deve essere tradotto per ottenere l’indirizzo fisico con cui la cache è indicizzata; il processo per accedere alla cache sarebbe quindi:

  • il predittore genera l’indirizzo virtuale
  • si esegue la traduzione nell’indirizzo fisico, accedendo alla TLB
  • si usa questo indirizzo per accedere alla cache

Ecco che per accedere alla cache istruzioni dobbiamo accedere prima ad un’altra cache! e il numero di cicli necessari ad prelevare la prossima istruzione cresce a dismisura, rendendo il front-end della pipeline molto inefficiente e abbattendo le prestazioni del processore.

Non solo, ma a pensarci bene quello che ci interessa è predire un’istruzione solo se questa si trova nel primo livello di cache. Se anche riuscissimo a  predire con successo un’istruzione solo per scoprire che questa si trova in una pagina che al momento è in RAM e dobbiamo aspettare centinaia di cicli di clock per potervi accedere, la predizione è completamente inutile e potevamo semplicemente eseguire il salto e risparmiare l’energia spesa per fare la predizione.

Queste due considerazioni ci suggeriscono che non è particolarmente importante predire l’indirizzo assoluto della prossima istruzione, bensì qual è la sua posizione nella cache L1. Quello che possiamo fare è quindi una cosa del genere:

dove ogni cache line ha, oltre ai dati, una tag e un puntatore alla prossima cache line, sempre all’interno della cache L1. In questo modo ad ogni accesso possiamo prelevare contemporaneamente i dati e la posizione della prossima linea di cache. A lato possiamo comunque avere un predittore più sofisticato (e lento) che predice anche lui il bersaglio del prossimo salto e controlla (ad esempio al ciclo successivo) che la linea predetta dalla cache stessa fosse quella giusta, controllando la tag.

In questo modo abbiamo costruito un sistema con multipli livelli di controllo e correzione:

  1. ogni cache line genera immediatamente una predizione alla prossima cache line
  2. un predittore più preciso e lento genera una predizione più accurata e controlla la predizione della cache
  3. l’esecuzione dell’istruzione di salto (che deve sempre e comunque essere portata a termine) funziona da “ultima linea di difesa”, controllando che tutti i meccanismi precedenti abbiano funzionato e assicurando la correttezza nell’esecuzione del programma

Nell’esempio mostrato la cache è direct-mapped, ma è possibile applicare lo stesso principio anche ad una cache set-associativa, cioè con più vie (ways). Queste cache hanno un miss-rate minore ma un tempo di accesso maggiore: invece di accedere ad una singola linea bisogna accedere a più linee e poi capire qual è quella giusta. Usando lo stesso meccanismo possiamo predire non solo la linea ma anche la via della prossima cache line; se la via è predetta correttamente possiamo accedere ad una cache set-associativa con la stessa latenza di una cache direct-mapped, altrimenti dovremo inserire una bolla nella pipeline e fare un altro accesso.

Override predictor

Come spiegato prima, esiste un compromesso tra la velocità a cui possiamo generare una predizione e la sua accuratezza: più il predittore è complesso più è preciso ma più cicli di clock servono per generare la predizione. Un predittore di tipo override combina due diversi predittori: uno lento ma preciso e uno veloce ma meno preciso. Il predittore veloce è in grado di generare una predizione in un ciclo di clock in modo da ridurre al minimo la latenza del front-end, mentre il predittore lento serve a validare le predizioni di quello veloce:

Al primo ciclo, il predittore veloce (a sinistra) fa una predizione iniziale che viene usata per accedere alla cache; nello stesso tempo il predittore lento comincia a generare la sua predizione, che sarà disponibile solo 2 cicli più tardi. Entrambi hanno un throughput di una predizione per ciclo di clock: quello veloce perchè un ciclo è tutto quello che gli serve per generare le sue predizioni, quello lento perchè è pipelinizzato.

Al terzo ciclo il predittore lento ha generato il suo valore e si procede a confrontarlo con quello del predittore veloce: se sono in accordo, la predizione veloce ha avuto successo e si è riusciti a procedere alla massima velocità; altrimenti le istruzioni fetchate vengono cancellate (cioè si inseriscono bolle nella pipeline) e si riprende a fare il fetch dall’istruzione predetta dal predittore lento:

Ci sono quattro possibili combinazioni:

  1. i due predittori hanno predetto correttamente: nessuna bolla viene iniettata nella pipeline e il processore procede alla massima velocità
  2. il predittore veloce ha sbagliato ma quello lento ha predetto correttamente: alcune bolle vengono iniettate nella pipeline (override), pari alla differenza di stadi tra i due predittori (2 nell’esempio) ma è comunque un prezzo piccolo da pagare rispetto ad un intero flush della pipeline
  3. entrambi i predittori hanno sbagliato: il risultato è un pipeline flush, che è lo stesso prezzo da pagare per la misprediction di qualsiasi altro schema di predizione
  4. il predittore veloce ha predetto correttamente ma quello lento ha sbagliato: in questo caso la misprediction penalty è peggiore, perchè è somma del secondo e terzo caso (override + flush); questo però molto più raro del secondo caso e quindi il risultato netto è un aumento di prestazioni

Conclusioni

Con questo articolo ci siamo finalmente liberati di fetch e branch prediction; ora che siamo riusciti a prelevare le istruzioni dalla cache possiamo mandarle al decoder, che vedremo nel prossimo articolo.

8 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    Cla
     scrive: 

    Notevole! Interessanti le considerazioni sulla cache, e che solo alcune predizioni possono essere effettivamente utili. Come sempre un gran articolo, chiaro e approfondito. Saluto con già un po’ di nostalgia l’argomento, in attesa del prossimo capitolo!

  • # 2
    Cesare Di Mauro
     scrive: 

    E’ da un po’ che ci rifletto, e m’è venuto un dubbio. In un’architettura superscalare in linea teorica si potrebbero eseguire n istruzioni di salto, una per ogni pipeline del processore.

    In questi casi dovremmo avere n predittori, che però devono necessariamente essere “correlati” / dipendenti (specialmente su architetture con opcode a lunghezza variabile).

    Immagino che realizzare un “mega-predittore” del genere sarebbe troppo complicato e costoso. In questi casi si opta per supportare una sola istruzione di salto alla volta?

  • # 3
    Pleg (Autore del post)
     scrive: 

    Un processore superscalare moderno ha tranquillamente 20-30 stadi e una “larghezza” di 3 o 4 istruzioni, quindi ci possono essere anche un centinaio di istruzioni in-flight nel processore in ogni ciclo di clock: e’ quindi assolutamente necessario poter avere piu’ branch in esecuzione nello stesso momento, cioe’ speculare attraverso piu’ salti. Per tenere traccia di tutto e risolvere le speculazioni annidate man mano che si procede, puoi usare un meccanismo come quello descritto in

    http://www.appuntidigitali.it/14033/processori-superscalari-out-of-order-branch-prediction-parte-prima/

    figure 8 e 9.

    Tieni presente che le “pipeline parallele” sono solo nel core di esecuzione out-of-order, vedi

    http://www.appuntidigitali.it/11713/processori-superscalari-out-of-order-una-vista-dinsieme/

    figura 2.
    Predizioni, fetch e decode sono eseguite da degli engine unici (e larghi, capaci cioe’ di predire/decodificare/ecc. un intero bundle di istruzioni alla volta), non distribuiti tra le pipe.

  • # 4
    Cesare Di Mauro
     scrive: 

    OK, grazie. In particolare avevo dimenticato quella parte del primo articolo.

    Riguardo al secondo, mi sembra che generalmente nei processori moderni il fetch & decode preveda una sola istruzione di salto decodificata per “bundle”. Con ciò mi riferisco al fatto che, pur potendo decodificare un certo numero di istruzioni di qualunque natura per ciclo di clock, in genere esistono dei limiti per quanto riguarda l’invio di queste istruzioni decodificate nelle rispettive code o unità. Ad esempio: 1 solo branch, 2 istruzioni intere, 2 floating point.

    Comunque ciò che importava nel discorso di cui sopra era la possibilità di eseguire predizioni multiple allo stesso momento, e il primo articolo ha dissipato i dubbi. Grazie ancora. :)

  • # 5
    Pleg (Autore del post)
     scrive: 

    Onestamente non so come funzioni la branch prediction quando hai piu’ branch all’interno dello stesso gruppo di fetch. E’ un caso di cui bisogna tenere conto, visto che non e’ cosi’ raro, ma non so come.

    L’esecuzione di istruzioni invece e’ una cosa diversa: tu ti stai riferendo al fatto che la macchina ha un tot fisso di pipeline diverse (ad esempio, come dici, una dedicata al branch, 2 interi, 2 float, eccetera). E’ possibile (anzi, desiderabile) fetchare e decodificare piu’ istruzioni rispetto al numero di pipeline che hai, per creare una “scorta per i periodi di magra” :) Supponiamo che in un gruppo di fetch di 4 istruzioni ci siano 2 branch; l’unita’ di branch prediction potrebbe riuscire a risolverli entrambi e speculare sia quali istruzioni di questo gruppo vanno effettivamente eseguite che quale sara’ il prossimo gruppo di fetch (cioe’ il prossimo Program Counter a cui accedere). Dopodiche’ entrambi i branch verranno decodificati e andranno nella coda della pipeline che esegue i branch (quella coda si chiama “Reservation Station”, come accennato qui: http://www.appuntidigitali.it/11713/processori-superscalari-out-of-order-una-vista-dinsieme/ ). Da quella coda andranno in esecuzione uno dopo l’altro (verranno quindi si’ serializzati, ma solo a questo stadio) e verranno poi ritirati in-order, e infine aggiorneranno il predittore e valideranno l’esecuzione speculativa.

    COme vedi, il front-end e il core di esecuzione sono disaccoppiati: il front-end deve fornire il massimo numero di istruzioni possibile, indipendentemente dalla larghezza del core out-of-order di esecuzione. Se riesce a decodificare piu’ istruzioni di quelle che il core riesce ad eseguire, tanto meglio: verranno accumulate nelle Reservation Station e creeranno una “scorta”. In questo modo, se per esempio il fetch stallasse per qualche ciclo di clock (ad esempio per un accesso in L2) gli stadi a valle potrebbero continuare a funzionare ancora per un po’, svuotando gradualmente le Reservation Station. In questo modo e’ spesso possibile “mascherare” un buco di pochi cicli di clock nel front-end.

  • # 6
    j
     scrive: 

    Onestamente non so come funzioni la branch prediction quando hai piu’ branch all’interno dello stesso gruppo di fetch. E’ un caso di cui bisogna tenere conto, visto che non e’ cosi’ raro, ma non so come.

    apparentemente supponendo che un’ istruzione di salto possa trovarsi ovunque a intervalli di 2 byte, ve ne possano essere fino a 4 per fetch group (cache line), prevedendo un campo nel branch selector per ogni gruppo di 16 bit del fetch group e gestendo ogni possibile caso – almeno su architettura amd stando a http://chip-architect.com/news/2003_09_21_Detailed_Architecture_of_AMDs_64bit_Core.html (apparentemente l’ ultimo articolo di hans de vries, non recente ma sempre utile e illuminante essendo riferito a un’ architettura comunque moderna)

    Da quella coda andranno in esecuzione uno dopo l’altro (verranno quindi si’ serializzati, ma solo a questo stadio) e verranno poi ritirati in-order, e infine aggiorneranno il predittore e valideranno l’esecuzione speculativa.

    anche perchè in effetti a pensarci bene la JEU (o branch unit che dir si voglia) in pratica “esegue il salto” nel senso di:
    controllare (cosa che non si può fare negli stadi a monte, che per cercare di alimentare a ritmo sostenuto quelli successivi hanno dovuto speculare l’ esito del salto prima ancora di decodificare l’ istruzione stessa di salto) se la condizione da cui dipendeva sia effettivamente verificata
    e nel caso non lo sia, invalidare nel ROB tutte le istruzioni successive al salto (compresi altri branch eseguiti speculativamente e in attesa di retirement, quindi sostanzialmente dipendenti dal primo anche se sottoposti a una diversa condizione) e aggiornare il program counter
    cosa questa che dubito sia opportuno fare concorrentemente (se non su thread separati) ma è ciò che rischierebbe di avvenire con branch unit parallele…

  • # 7
    snow4life
     scrive: 

    Ciao Pleg, ho letto tutti gli articoli sulla branch prediction, l’esecuzione out-of-order, ecc, e volevo chiederti se potevi consigliarmi un libro su cui approfondire questi argomenti?
    Ho già letto Computer Architecture: A Quantitative Approach ma “non mi basta”, e dato che vorrei intraprendere una carriera in questo campo vorrei passare ad una lettura più avanzata (che sia magari più organica e didattica di qualche paper preso qui e li che il nostro prof. ci propone).

  • # 8
    Pleg (Autore del post)
     scrive: 

    Il testo che uso come riferimento (l’unico che conosco che tratti processori superscalari) e’ lo Shen, Lipasti, “Modern Processor Design: Fundamentals of Superscalar Processors”.

    E’ un pochino vecchio, ma non conosco niente di piu’ recente (non credo ci sia), quindi per roba piu’ avanzata e moderna l’unica e’ proprio leggere i paper pubblicati.

    Buona fortuna per la carriera!

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.