branch prediction

I don't understand on how the following question works... can someone please clarify what the branch predictor is?
branch.JPG
kuntilanakAsked:
Who is Participating?
 
CallandorConnect With a Mentor Commented:
I think the two-level branch predictor will only cause the predictor state to flip if it missed on the last two guesses, instead of just the last one in the first example.  The BHR always contains the previous outcome, so the table looks like:

N N T *
N T T *
T T T
T T N *
T N T

Since the outcome contains a lot of T's, a good predictor would also contain a lot of T's, and it is true in this case.
0
 
CallandorCommented:
Branch prediction is used in pipeline processors to queue up instructions so that the cpu is utilized most efficiently, executing instructions instead of waiting for results.  The branch predictor tries to guess which branch will be taken.
0
 
kuntilanakAuthor Commented:
I don't understand the concepts of a two level branch predictor explained here:

http://en.wikipedia.org/wiki/Branch_predictor

I mean how will the branch history index to the pattern history table?  what's in the branch history register?
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
CallandorCommented:
If you look at the example given for n=2 and a conditional jump every third time, a pattern of 001001001... occurs.  If 00 is seen in the pattern history table, 1 is expected next, so this will result in a "strongly taken" path.  11 never occurs, and any other combination is considered "strongly not taken".  Essentially, the branch history is used to created the combinations in the branch history table.

The branch history register contains the binary values of the last branches selected, so if it has 00, it would predict that the next branch would be 1.
0
 
kuntilanakAuthor Commented:
so the branch history register is just an index to the pattern history table? so how does this then gives the prediction that we want?

If the question now changes to:

Now, assume a two-level branch predictor that uses one bit of branch history—i.e., a one-bit BHR. Since there is only one branch in the program, it does not matter how the BHR is concatenated with the branch PC to index the BHT. Assume that the BHT uses one-bit counters and that, again, all entries are initialized to N. Which of the branches in this sequence would be mis-predicted? Use the table below.

So if we have a two-level branch that uses one bit of branch history then there will be only two entries in the pattern history table and it only records the history of the last branch? I am kind of confused on how to complete the following table
branch.JPG
0
 
CallandorCommented:
No, the branch history register holds the most recent pattern and it is trying to guess what comes next.  The pattern history table holds all the combinations we know about.  By matching the pattern in the branch history register to the pattern in the pattern history table, we see what is most likely to happen next.

Did you see in the example you originally posted how the predictor state was filled in?  The branch outcome column is given.  The predictor state flips if there is a misprediction.
0
 
kuntilanakAuthor Commented:
I have understand the example that I originally posted and now I want to expand that idea using this two-level branch predictor... I am confused with that though
0
 
kuntilanakAuthor Commented:
so after re-reading the article in wikipedia over and over again, here's my understanding of it:

the branch history register will be matched against the pattern history table to get the prediction we want? question is say it matches with a particular counter...how does it know what is the prediction to make?
0
 
CallandorCommented:
It knows because in the case of 001001001..., everytime a 00 occurs, a 1 follows.  I think the table includes what to expect after a match.  You can generalize this with a statistical probability model to make guesses.
0
 
kuntilanakAuthor Commented:
well in my case.... in the table above... could you give me an example of what should I fill in in the line below after the predictor state before prediction and the BHR as it's confusing. I think it will make more sense once I get an example... and then I can proceed forward.

if I were only using 1 bit for the BHR then I would only have two counter right and I would only be saving the history of the last one not the last two
0
 
kuntilanakAuthor Commented:
so how did you actually get the BHR value in the table?
0
 
CallandorCommented:
BHR always contains the branch history, so it has the outcome from the previous decision for a 1-bit register, outcomes from the last two decisions for a 2-bit register, etc.  Just take the branch outcome column and shift it down one row and you get the values.  I am not sure of the reason why there is a column for it, if my reasoning is correct and the predictor state is determined by the last two mis-predictions.
0
 
kuntilanakAuthor Commented:
and why do you think that the predictor is determined by the last two mis predictions?
0
 
CallandorCommented:
A single-level branch predictor uses just the last mis-prediction.  The wikipedia article talks about a two-level predictor using a two-bit register to match the historical pattern from the last two branches, so I combined the two concepts for a two-level predictor with a single-bit register.
0
All Courses

From novice to tech pro — start learning today.