Branch Prediction Theory Flashcards
What is branch prediction?
It is a method for solving a branch hazard that assumes a given outcome for the branch and proceeds speculatively from that assumption rather than waiting to certify the actual branch outcome
What are the two branch prediction techniques?
The static branch prediction and the dynamic branch prediction
What is the static branch prediction?
The action taken or untaken for a branch prediction is fixed at comp time for each branch during the entire execution
What is dynamic branch prediction?
The actions taken or untaken for a branch prediction can change at run time during the program execution
What are the static branch prediction techniques?
Branch always not taken (predicted – not – taken)
Branch always taken (predicted – taken)
Backward taken forward not taken
Profile – driven prediction
Delayed branch
Define the static branch prediction technique, branch always not taken
We assume the branche as not taken, thus the sequential instruction flow that we have fetched can continue as if the branch condition was not satisfied.
To what case the branch always not taken technique is most suitable to?
Suitable for if – then – else conditional statements
When do we know that we predicted the branch wrongly and what are the consequences?
If the branch outcome at the end of the ID stage will be taken/untaken the prediction might be incorrect (misprediction). In that case we flush the instruction already fetched (it is turned into a NOP) in order to fetch the instruction at the branch target address.
Define the branch always taken technique, to what condition is most suitable for, and the main challenge of it
In the branch always taken technique we assume every branch as taken. it is most suitable for backward branches (such as do – while loop branches) that are most likely taken. The main challenge of it is that we need to know the branch target address (BTA) to start fetching and executing instructions at the target.
How do we deal with the challenge of the branch always taken technique
We need to add in the iF stage a branch target buffer, cache where to store the predicted target address based on the previous branch behavior
Define the backward taken forward not taken technique for static branch prediction
The prediction is based on the branch direction. Backward – going branches are predicted as taken (such as do – while loops) .While forward – going branches are predicted as not taken (such as IF – then – else conditional statements)
Define the profile – driven prediction technique
In this case, we assume to have a profile of the behavior of the target application application program by several early runs by using different data set. The branch prediction is based the profiled information. The profile – driven prediction method requires compiler hint bits included in the branch instruction format
Define the delay branch technique
It is a shadowing technique. The compiler statically schedules an independent instruction in the branch delay the slot
What are the four ways to schedule an instruction in the branch delays lot?
From before, from after, from target, from fall through
Define the delayed branch technique, using a from before approach
The branch Village lot is scheduled with an independent instruction from before the branch. The instruction in the branch delays lot is always executed, whether the branch will be taken or not taken.
Define the delayed branch technique, using a from target approach, describe also what happens in case of a miss prediction and when this technique is preferred
The branch delays lot is scheduled with one instruction from the target of the branch (branch taken). This technique is preferred when the branch is taken with high probability. If the branch is untaken (misprediction) the instruction in the delays slot needs to be flushed, or it must be OK to execute when the branch goes in the unexpected direction.
Describe the delayed branch technique, using a from fall – through approach
The branch delay slot is scheduled with one instruction from the fall - through path (branch not taken)
How are the four dynamic branch prediction techniques interconnected?
We need to have a mechanism to decide whether to take or not the branch (branch outcome predictor), which corresponds to BHD, CBP, and two level adaptive branch predictors, we also need a buffer to store the branch target address (branch target predictor), which corresponds to the branch target buffer (BTB).
Describe the 1-bit branch history table
It is a table containing one bit for each entry that says whether the branch was recently taken or not taken. This table is indexed by the lower portion K – bit off the address of the branch instruction.
Describe the 1-bit branch history table mechanism
If the prediction turns out to be wrong, the prediction bit is inverted and stored back
Describe the 2-bit branch history table
It is a 2-bit branch history table used to encode four stages in order to change the prediction after two miss predictions
Describe the 2-bit branch history table mechanism
Supposing that a branch history table is in the strongly taken prediction stage, once a branch output is miss predicted, The stage is changed to weekly taken. Another miss prediction leads to a strongly not taken prediction, while a correct prediction changes the state back to strongly taken. Finally, when in strongly not taken stage, a miss predict lead to a weekly not taken stage, while a correct prediction maintains the mechanism in its current strongly not taken stage.
Describe the correlating branch predictor
In the branch history table method we used only the recent behavior of a single branched to predict the future behavior of that branch. In these method, otherwise, we use the recent behavior of other branches to predict the current branch behavior.
The rational is that we try to exploit the correlation existing amount different branches
Define the two – level adaptive branch predictor
There is a two level history, a Global (branch history, register, BHR), and a local (pattern history table, BHT).the first one is used to index the first one.
The branch history register is a k-bit shift register, which records the outcomes of the k most recent branches
