Test sulla Branch Prediction Unit
Branch Prediction Unit - cos'è?
La Branch Prediction Unit è quella sezione, fondamentale per un processore basato su pipeline, che si occupa di "prevedere" la prossima istruzione da eseguire in presenza di salti condizionati. Un processore provvisto di pipeline ottiene un’accelerazione considerevole. Lo svantaggio di questa soluzione risiede proprio nella gestione dei salti condizionati. Tale svantaggio ha un impatto tanto maggiore quanto più la pipeline è lunga, poiché una scelta sbagliata della prossima istruzione da compiere comporta un cosiddetto "restart della pipeline", con conseguente perdita di cicli di clock. Nell’Intel® Pentium IV, dotato di una pipeline di ben 20 stadi, la branch prediction è basata su un algoritmo misto, cioè sia statico sia dinamico:
- Dinamico. Si basa sulla storia delle predizioni precedenti, comportandosi come già fatto in precedenza per quella stessa istruzione. Qualora l’istruzione non sia già stata eseguita, si basa sull’algoritmo statico.
- Statico. Si basa su delle politiche prefissate. Ad esempio
- Salto all’indietro. Viene sempre effettuato, probabilmente proviene da un ciclo di codice ad alto livello.
- Salto in avanti. Viene sempre ignorato, probabilmente viene effettuato se si verificano particolari condizioni di errore.
Parametri del test
Avendo a disposizione un Intel® Pentium IV ho voluto provare a verificare l’effettiva utilità di tale dispositivo tramite il confronto di tre diversi piccoli programmi java, da me realizzati. Ognuno di questi programmi entra in un ciclo di circa 2 miliardi di passi (2G).
- Nel primo programma, ogni passo non è altro che un "if" che non è mai verificato;
- Nel secondo programma, ogni passo è un "if" che, stavolta, è sempre verificato;
- Nel terzo programma, ogni passo è un "if" che è verificato una volta su due.
Risultati attesi
Il risultato atteso è un tempo impiegato a completare il terzo ciclo che sia maggiore dei tempi impiegati per completare i primi due cicli, dal momento che la Branch Prediction Unit non sarà mai in grado di prevedere qual è l’istruzione corretta da eseguire.
Realizzazione dei test
In basso abbiamo il codice dei tre programmi che saranno eseguiti.
Nella prima classe abbiamo un ciclo che fa eseguire un "if" che, però, non sarà mai verificato.
Nella seconda classe abbiamo un ciclo che fa eseguire un "if" che, invece, sarà sempre verificato.
Nella terza classe, infine, abbiamo un ciclo che fa eseguire un "if" che sarà verificato una volta su due.
Risultati dei test
I risultati ottenuti ricalcano quelli attesi.
L’esecuzione dei primi due cicli dura circa 7.2 secondi.
Mentre il terzo ciclo richiede circa 9.3 secondi.
L’esecuzione di questo ciclo richiede il 30% di tempo in più rispetto ai primi due.
Questa differenza è dovuta al continuo svuotamento della pipeline occorso in questo caso, dal momento che la BPU non è capace di prevedere la prossima istruzione da eseguire.