Konsepter:Branch Prediction
Fra CodeWiki
Branch Prediction omhandler en problemstilling rundt Pipelining. For at Pipelining skal fungere optimalt er det nødvendig å holde alle stadiene fulle. Men det oppstår et problem hvis den kommer over en instruksjon som endrer den sekvensielle flyten av kontroll i programmet. If-setninger, loop-setninger og procedure-setninger forårsaker problemer med pipeliningen. Branch Prediction fører til svært økt ytelse da den viser seg å være veldig effektiv. Man sier gjerne at Branch Prediction klarer å oppnå en 96-98% forutsigbarhetsrate. Se for deg følgende kode:
if (x > 0) { a=0; b=1; c=2; } d=3;
Da får vi følgende instruksjonstabell basert på Pipelining konseptet:
| Cycle | Fetch | Decode | Execute | Save |
|---|---|---|---|---|
| 1 | if (x>0) | |||
| 2 | a=0 | if(x>0) | ||
| 3 | b=1 | a=0 | if (x>0) | |
| 4 | c=2 | b=1 | a=0 | if (x>0) |
| 5 | c=2 | b=1 | a=0 | |
| 6 | c=2 | b=1 | ||
| 7 | c=2 |
Hvis x er større enn 0, så vil instruksjonene i pipeliningen være korrekte siden kroppen av if-setningen vil bli utført. Problemet oppstår hvis x er mindre eller lik 0.
| Cycle | Fetch | Decode | Execute | Save |
|---|---|---|---|---|
| 1 | if (x>0) | |||
| 2 | a=0 | if(x>0) | ||
| 3 | b=1 | a=0 | if (x>0) | |
| 4 | d=3 | squash b=1 | squash a=0 | if (x>0) |
| 5 | d=3 | squash b=1 | squash a=0 | |
| 6 | d=3 | squash b=1 | ||
| 7 | d=2 |
I dette tilfellet burde den neste instruksjonen i pipelinen være d=3, og instruksjonene som omhnalder a, b og c burde ikke være der. Her ville det være nødvendig å avbryte effekten disse instruksjonene hadde på prosessoren og fjerne disse fra pipelinen. Dette er kjent som å squashe instruksjonen. Hvis vi anntar at dette kan gjøres så vil d=3-instruksjonen bli hentet på starten av cycle 4 når resultatet av x>0 blir kjent. I dette tilfellet er pipelinen mindre effektiv, siden enkelte av stadiene ikke blir brukt til å utføre gyldige instruksjoner. Det vil faktisk ta 7 cycles for å fullføre disse to instruksjonene.
Hvis det hadde vært mulig å forutsi hva resultatene skulle bli, ville det vært mulig å holde pipelinen full. Hvis vi viste på forhånd at x>0 blir false så kunne datamaskinen laste inn instruksjonen d=3 istedet for instruksjonen a=0. Dette er ideen bak Branch Prediction.
| Cycle | Fetch | Decode | Execute | Save |
|---|---|---|---|---|
| 1 | if (x>0) | |||
| 2 | d=0 | if(x>0) | ||
| 3 | d=3 | if (x>0) | ||
| 4 | d=3 | if (x>0) | ||
| 5 | d=3 |
Her bruker vi bare 5 cycles på å å utføre de to instruksjonene. Branch Prediction gjetter altså hvilken vei en gren vil gå. Hvis den gjetter riktig så vil pipelinen forbli full. Hvis den tar feil må det squashes litt og pipelinen vil bli mindre effektiv.
