Branch Prediction Theory

Question 1

What is branch prediction?

Answer 1

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

Question 2

What are the two branch prediction techniques?

Answer 2

The static branch prediction and the dynamic branch prediction

Question 3

What is the static branch prediction?

Answer 3

The action taken or untaken for a branch prediction is fixed at comp time for each branch during the entire execution

Question 4

What is dynamic branch prediction?

Answer 4

The actions taken or untaken for a branch prediction can change at run time during the program execution

Question 5

What are the static branch prediction techniques?

Answer 5

Branch always not taken (predicted – not – taken)

Branch always taken (predicted – taken)

Backward taken forward not taken

Profile – driven prediction

Delayed branch

Question 6

Define the static branch prediction technique, branch always not taken

Answer 6

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.

Question 7

To what case the branch always not taken technique is most suitable to?

Answer 7

Suitable for if – then – else conditional statements

Question 8

When do we know that we predicted the branch wrongly and what are the consequences?

Answer 8

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.

Question 9

Define the branch always taken technique, to what condition is most suitable for, and the main challenge of it

Answer 9

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.

Question 10

How do we deal with the challenge of the branch always taken technique

Answer 10

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

Question 11

Define the backward taken forward not taken technique for static branch prediction

Answer 11

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)

Question 12

Define the profile – driven prediction technique

Answer 12

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

Question 13

Define the delay branch technique

Answer 13

It is a shadowing technique. The compiler statically schedules an independent instruction in the branch delay the slot

Question 14

What are the four ways to schedule an instruction in the branch delays lot?

Answer 14

From before, from after, from target, from fall through

Question 15

Define the delayed branch technique, using a from before approach

Answer 15

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.

Question 16

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

Answer 16

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.

Question 17

Describe the delayed branch technique, using a from fall – through approach

Answer 17

The branch delay slot is scheduled with one instruction from the fall - through path (branch not taken)

Question 18

How are the four dynamic branch prediction techniques interconnected?

Answer 18

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).

Question 19

Describe the 1-bit branch history table

Answer 19

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.

Question 20

Describe the 1-bit branch history table mechanism

Answer 20

If the prediction turns out to be wrong, the prediction bit is inverted and stored back

Question 21

Describe the 2-bit branch history table

Answer 21

It is a 2-bit branch history table used to encode four stages in order to change the prediction after two miss predictions

Question 22

Describe the 2-bit branch history table mechanism

Answer 22

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.

Question 23

Describe the correlating branch predictor

Answer 23

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

Question 24

Define the two – level adaptive branch predictor

Answer 24

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

Question 25

What is the difference between a GA predictor and a GShare predictor

Answer 25

In the GA predictor the indexation of the PHT he done exclusively by the BHR, while for the GShare predictor we aim to correlate the branch instruction address with the Global history by XORing the low – order 4-bit off the branch address with the BHR to index the PHT

Question 26

Define the branch target buffer

Answer 26

Branch target buffer or branch target predictor is a cashe storing the predicted target address for taken – branch instructions

Question 27

Describe the branch target buffer mechanism

Answer 27

The BTB is accessed in the IF stage by using the address of the fetched branch instruction to index the cache, then tags are used for the associative look up