di  -  giovedì 6 ottobre 2011

Negli scorsi articoli abbiamo visto alcune tecniche utilizzate dai processori moderni per predire la direzione dei salti.  Siamo partiti con le tecniche più vecchie e semplici e poi abbiamo visto predittori più sofisticati e predittori ibridi, che possono combinare predittori diversi per ottenere risultati ancora migliori.

Predire la direzione dei salti è però solo uno dei problemi che è necessario risolvere: bisogna anche predire il bersaglio dei salti presi e bisogna costruire tutti questi meccanismi in modo da interagire in modo efficiente con la cache e in modo da fornire più istruzioni per ogni ciclo di clock (dato che stiamo sempre parlando di processori superscalari).

Ci sono due casi in cui è necessario predire il bersaglio di salto: per i salti condizionali predetti presi e per i salti non condizionati. Può a prima vista sembrare strano che si debba “predire” qualcosa di un salto non condizionato (dato che è sempre preso), ma bisogna ricordare che la predizione avviene i testa alla pipeline, nello stadio di fetch, quando l’istruzione non è ancora stata nemmeno decodificata!

Branch Target Buffer

Per predire il bersaglio del salto si usa in genere una struttura simile ad una cache (chiamata Branch Target Buffer o Branch Target Address Cache) in cui viene salvato l’ultimo bersaglio visto per quel salto. Durante la predizione di salto, parallelamente alla generazione della predizione preso/non preso, si accede alla BTB usando il Program Counter corrente; la BTB ha in genere delle tag (parziali) per distinguere i diversi PC e può essere set-associativa.

Se il predittore di direzione predice non preso il bersaglio è semplicemente la prossima istruzione (per una macchina RISC sarà l’indirizzo corrente più la dimensione dell’istruzione, 4 byte nell’esempio in figura); altrimenti, se il salto è predetto preso e c’è cache hit nella BTB, allora il valore restituito dalla BTB viene usato come prossimo Program Counter.

Se invece il salto è predetto preso ma non c’è hit nella BTB, ci sono un paio di approcci possibili:

  • il processore stalla fino a che il bersaglio non è noto: questo può prendere pochi cicli nel caso il bersaglio di salto sia relativo al PC (è necessario attendere il fetch e il decode dell’istruzione e quindi aggiungere il valore al PC) o più a lungo se il bersaglio va calcolato a partire da valori nei registri (in questo caso è necessario attendere il risultato dall’unità di esecuzione dei branch)
  • scartare la predizione e continuare a fare fetch dalla prossima istruzione, come se il salto fosse non preso

La prima soluzione è più conservativa e risparmia energia, in quanto non si esegue nulla fino a che il bersaglio non è noto (a quel punto non si tratta più di una speculazione, il risultato è al 100% corretto perchè il salto è stato effettivamente eseguito). La seconda soluzione è più aggressiva e può dare prestazioni lievemente migliori, nel caso il predittore si fosse sbagliato e il salto fosse effettivamente non preso (aiuta anche nel caso di phantom branch, come vedremo in seguito); costa però più energia, perchè se il predittore aveva indovinato (e cioè il salto era preso) il processore ha eseguito istruzioni che devono essere cancellate (sprecando così energia).

Inoltre, ci sono diverse strategie riguardo quale informazione mantenere nella BTB. Un approccio semplice potrebbe essere quello di registrare nella BTB tutti i bersagli di tutti i salti incontrati. Un approccio migliore può essere quello di registrare solo i salti presi, dato che se un salto è non preso il bersaglio è facile da calcolare (è la prossima istruzione); questo risparmia spazio nella BTB e diminuisce la probabilità di interferenza tra salti, migliorando le prestazioni; per contro, prima di registrare un bersaglio nella BTB è in questo caso necessario attendere che il salto sia stato risolto completamente (in bersaglio e in direzione) per decidere se l’informazione va registrata o meno.

Un altro fattore molto importante di cui tenere conto è che in un processore moderno, che opera ad alta frequenza, la cache istruzioni non riesce a rispondere in un singolo ciclo di clock: anch’essa è pipelinizzata e ha un throughput di una cache line per ciclo di clock, ma la latenza è maggiore di un ciclo. Questo può creare uno strano effetto per cui il predittore predice un salto… che non esiste! Per esempio, supponiamo che la cache abbia un tempo di risposta di due cicli di clock:

Al ciclo n il PC corrente viene fornito al predittore, che predice un salto preso; contemporaneamente comincia l’accesso alla cache istruzioni. Alla fine del ciclo n la BTB ha fornito il bersaglio per il salto evidenziato; questo valore viene caricato nel PC ed è il valore che verrà usato al ciclo n+1 per caricare la prossima istruzione. Ma al ciclo n+1 la cache non ha ancora risposto! E’ solo al ciclo successivo che la cache fornisce l’istruzione puntata dal PC al ciclo n: il salto è stato eseguito in modo speculativo prima ancora che ne venisse completato il fetch!

Questo significa che, quando il predittore si sbaglia, esso potrebbe fornire il risultato di salto per un salto che non c’è:

Solo al ciclo n+2 la cache restituisce il gruppo di fetch e si scopre che non c’è alcun salto. L’azione errata del predittore va cancellata: nella pipeline viene inserita una bolla e il PC viene ricaricato al valore corretto, perdendo così un ciclo di clock. Questo salto predetto ma inesistente è chiamato phantom branch.

Se il gruppo di fetch non ha salti, il prossimo Program Counter è il blocco di istruzioni successivo, che è equivalente ad una predizione di salto non preso. Se, come spiegato sopra, nella BTB vengono caricati solo i bersagli dei salti presi, ci sarà sempre un BTB miss quando un gruppo di fetch non contiene salti, mitigando il problema dei phantom branch.

Un’ultima cosa da notare è che gli indirizzi sono “larghi” (32 e ora anche 64 bit): questo occupa un sacco di spazio nelle tag della BTB. Per ridurre questo problema si può usare una tag parziale, cioè solo una parte dell’indirizzo di salto viene registrato nella tag. Questo riduce la dimensione della BTB, rendendola più veloce, ma crea la possibilità di avere aliasing (come visto qui). L’aliasing non inficia il corretto funzionamento del processore, rende solo meno preciso il predittore. Un effetto collaterale è il ritorno dei phantom branch: un gruppo di fetch senza branch potrebbe comunque avere uno hit nella BTB perchè, a causa della tag parziale, il PC corrente mappa sulla tag errata.  Tuttavia, se il tasso di falsi hit è basso questo non è un grosso problema.

Return Address Stack

Uno dei casi più comuni di salto è la chiamata a funzione: salto nella funzione e salto (ritorno) dalla funzione. Il bersaglio di salto nella funzione è facile da predire perchè è sempre lo stesso; il ritorno dalla funzione è più difficile perchè la stessa funzione può essere chiamata da molti punti del programma (ad esempio, ogni volta che chiamiamo “printf” saltiamo nello stesso punto, ma quando usciamo da “printf” possiamo tornare ad un’infinità di punti diversi, tutti i punti in cui abbiamo chiamato “printf”).

Un modo efficace di risolvere questo problema e fornire una predizione accurata ad un salto che può cambiare bersaglio ad ogni esecuzione è il Return Address Stack: uno stack di indirizzi di ritorno delle subroutine. Ogni volta che si esegue il salto ad una subroutine l’indirizzo di ritorno viene messo su questo stack; ogni volta che si incontra un ritorno da funzione si esegue il pop da questo stack, ottenendo quindi il bersaglio esatto. L’uso di uno stack invece che un singolo registro permette di gestire chiamate di funzioni annidate.

Il RAS è quindi un predittore particolare che predice solamente i ritorni da funzione; esso integra la BTB e gli altri meccanismi di predizione, ma è necessario avere della circuiteria in grado di determinare esattamente quando accettare il valore fornito dal RAS e quando scartarlo. Inolre, dato che il RAS ha una capacità limitata alla dimensione massima dello stack (ad esempio 16 nel Pentium-4), è possibile che esso fallisca quando il numero di funzioni annidate è superiore alla dimensione dello stack; in questo caso si avranno predizioni errate, con conseguente scadimento delle prestazioni.

Conclusioni

In questo articolo abbiamo visto come predire il bersaglio di salto, che è la vera quantità che ci interessa calcolare per far proseguire il programma senza stalli.

Restano da vedere ancora un paio di cose: come eseguire predizioni a “larga banda” (cioè ottenere più istruzioni per ciclo di clock, necessarie ad alimentare pipeline superscalari) e ad “alta frequenza” (cioè ottenere una predizione ad ogni ciclo di clock anche quando cache e predittori occupano più stadi di pipeline).

10 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
    Z80Fan
     scrive: 

    Che bello, un nuovo articolo di Pleg! :D

    Ho un piccolo dubbio, sul RAS: se non ho capito male, è uno stack interno al processore che memorizza solo gli indirizzi di ritorno. Ovviamente, l’indirizzo di ritorno deve essere salvato nello stack “normale” per rimanere coerente con le specifiche dell’architettura.

    Ora, come si comporta il processore se la funzione modifica manualmente il suo indirizzo di ritorno? Posso pensare a una funzione del kernel che costruisce nello stack un frame su misura, ed eseguendo un “return” ritorna in un’altra zona di memoria.
    Come fa il processore a essere sicuro che il contenuto del RAS è corretto? Esegue cmq le istruzioni in modo speculativo finchè l’indirizzo “giusto” diventa disponibile ai circuiti di controllo, e in tal caso si svuota la pipeline e si ricaricano le istruzioni dal punto giusto?

  • # 2
    Sasha
     scrive: 

    Mi sei mancato pleg! Ottimo articolo come sempre, ma d’altra parte, il tuo nome, come quello di tutti gli altri che scrivono qui sopra, è una garanzia!
    Ora non resta che una riapparizione del buon yossarian, e non potrò chiedere altro!!!

  • # 3
    Pleg (Autore del post)
     scrive: 

    Grazie :)

    Z80Fan, onestamente non sapevo che ci fossero funzioni che modificano il proprio indirizzo di ritorno! Ma questo non e’ un problema: il RAS, come tutto il motore di branch prediction, esegue in modo speculativo. Quindi quando l’istruzione di ritorno viene effettivamente eseguita e il salto validato, scopri se hai azzeccato o se devi flushare e ripetere. E’ semplicemente un pezzo in piu’ che si occupa di predire quei salti di ritorno il cui comportamento sarebbe molto difficile da catturare con la normale BTB.

  • # 4
    Cla
     scrive: 

    Come sempre, complimenti! :)

  • # 5
    Cesare Di Mauro
     scrive: 

    Con la diffusione della programmazione a oggetti e, in particolare, dei metodi virtuali, i salti non condizionati “calcolati” sono estremamente diffusi e, immagino, non facilmente “digeribili” dalle unità di branch prediction.

    Per caso esiste qualche statistica o, meglio, studio su come si comportano le unità BP moderne con questa tipologia di codice?

  • # 6
    Pleg (Autore del post)
     scrive: 

    Bella domanda :)
    Conosco il problema ma non conosco la soluzione. Da quel che so, la predizione e’ piuttosto scadente e il problema e’ ancora argomento di ricerca accademica. Se googoli “branch prediction virtual method” trovi un po’ di paper recenti sull’argomento; non so dirti niente di piu’ perche’ nno li ho letti nemmeno io :) e non mi e’ mai capitato di leggerli o affrontare il problema.
    Alla fine tutta la predizione dei salti si basa sullo sfruttamento delle regolarita': se le chiamate ai metodi virtuali hanno una qualche regolarita’ allora qualcosa forse si puo’ fare (ma bisogna spendere silicio, e quindi il problema e’ quanto silicio si puo’/vuole spendere per risolvere il problema e quanto vantaggio da’ in termini di prestazioni e di energia).
    Se ad esempio fossimo in un loop che esegue molte volte e la stessa istruzione chiama sempre lo stesso metodo virtuale, allora questa predizione e’ “standard” e ricade nei casi gia’ trattai dai BP correnti. Se no, nun zo :)

  • # 7
    Cesare Di Mauro
     scrive: 

    Purtroppo il caso a cui pensavo era ovviamente quello peggiore, e non un loop che chiama i metodi degli stessi oggetti. :P

    Per dirla tutta, avevo in mente una foresta di oggetti con VMT diverse (caso non certo raro di questi tempi, con tanto codice OOP in giro), ma siccome alla perversione non c’è limite, pensavo a qualcosa di simile alla (o alle O:-) dispatch table di una virtual machine (o emulatore) che esegue il codice degli opcode.

    A naso direi che c’è un flush della pipeline per ogni tipo di questa chiamata. Purtroppo l’indirizzo della destinazione è noto soltanto giusto qualche ciclo (magari proprio quello precedente) prima della chiamata vera e propria.

    In ogni caso grazie dei suggerimenti. Tempo permettendo, vedrò di cercare qualcosa.

  • # 8
    Z80Fan
     scrive: 

    @Pleg:

    Bene, proprio come pensavo! :)

    Riguardo le funzioni che modificano l’indirizzo di ritorno: nell’x86, per fare un task switch e entrare in user-mode, bisogna (oltre a settare tutte le tabelle necessarie) creare un frame apposito nello stack, e eseguire un return.
    Poi ovviamente ci sono i malware che usano i buffer overflow per reindirizzare l’esecuzione in un punto diverso.
    Per questo avevo quel dubbio.

  • # 9
    Pleg (Autore del post)
     scrive: 

    @ Cesare
    Si’ immaginavo non intendessi quello :)
    Nel caso che dici dell’emulatore, se davvero l’indirizzo viene calcolato appena prima del branch allora non c’e’ proprio niente da fare, il predittore sbagliera’ ogni volta e dovrai inserire bolle in pipeline.

    @ Z80Fan
    Buono a sapersi, non si finisce mai d’imparare :)

  • # 10
    banryu
     scrive: 

    @Pleg:
    Negli scorsi articoli abbiamo visto alcune tecniche utilizzate dai processori moderni per predire la direzione dei salti. Siamo partiti con le tecniche più e poi abbiamo visto predittori e , che possono combinare predittori diversi per ottenere risultati ancora migliori.

    I link inseriti nell’articolo non linkano a nulla (errore 404)

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.