4
$\begingroup$

I am reading two books, Computer organization and design by David A Patterson, and Digital Design and Computer Architecture by Harris and Harris. These books claim that a 1 bit branch predictor mispredicts on the first and last iterations of every loop.
I don't understand why it mispredicts on the first iteration. I think that the first prediction result depends on the history of the CPU, so we don't know whether the predictor would predict correctly or not.
My question is whether I have to assume that the initial state of the 1 bit predictor is for the branch to be taken.

$\endgroup$
6
$\begingroup$

I believe the assumption is that the loop has been encountered previously (i.e., assuming a long-running program with the loop encountered multiple times and assuming no aliasing in the branch predictor), so the first iteration has the predictor set based on the last iteration of the previous encounter (i.e., not-taken) and, of course, the last iteration has the predictor set based on the previous iteration (i.e., taken). This results in two mispredictions.

In general, a one-bit branch predictor will have two mispredictions per instance of unusual branch direction; first for the unusual instance and second for the instance immediately after that unusual instance. By providing some form of hysteresis (as with a 2-bit predictor) or resistance to change (e.g., by randomly dropping misprediction information, possibly with probabilities determined by static branch prediction--so far as I know, a technique that is only theoretical), such unusual branch behavior is less likely to cause mispredictions for the usual behavior of a branch.

$\endgroup$
  • $\begingroup$ This answer is correct. The observation about 2 mispredicts on inner loops was first made by James E Smith in 1981 in a paper where he proposed 2-bit predictors and gave a number of motivating examples to explain why $N$ 2-bit predictors are so much more effective than $2N$ 1-bit predictors in practice. $\endgroup$ – Wandering Logic May 22 '13 at 12:22
  • $\begingroup$ Note that POWER and PowerPC have special instructions for loops where the loop control is performed inside the branching unit, and is not "predicted" at all. You set up a counter, and the branch unit "knows" whether the branch at the end of the loop will be executed or not. $\endgroup$ – gnasher729 May 23 '17 at 5:15
  • $\begingroup$ @gnasher729 In theory such special handling of counted loops could eliminate branch prediction for such, but even the PowerPC 750 had a single cycle delay in determining the branch (not a problem for loop because the branch target instruction cache supported zero cycle taken branches). Itanium has a similar mechanism (along with support for early availability of indirect target addresses, similar to PPC's count and link registers). Predecode could allow early detection of a loop branch but the count needs to be set early enough to handle pipeline latency (or use prediction initially). $\endgroup$ – Paul A. Clayton May 23 '17 at 13:44
0
$\begingroup$

Hennessy and Patterson clearify this a little bit in an example in "Computer Architecture: A Quantitative Approach (3rd edition)". On page 197, they give an example on 1-bit branch predictors. Consider the following pseudo code:

for (int i = 0; i < 9; ++i) {
    do_sth();
}

after_loop();

This pseudo code results in 3 branches: the if statement in the beginning, a branch to form the loop and a branch to exit the loop. The following sequence of operations would be possible:

do_sth(); // will be mispredict
do_sth(); // will not be mispredicted
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
after_loop(); // will be mispredicted

The question is: why will the first do_sth_else() be executed after a mispredict?

Hennessy and Patterson define a branch-prediction buffer as (emphasize mine)

[...] a small memory indexed by the lower portion of the address of the branch instruction. The memory contains a bit that says wether the branch was recently taken or not.

If the lower part of the branch's address was not encountered before, it will be mispredicted. The address of the branch for the first execution of do_sth_else() was not encountered before (otherwise, the loop must have been executed before, which is not the case), hence it will be mispredicted.

I believe you are right that this omits the branch history of the CPU. But as the lower portion of the branch address is used, I believe it is very likely that a misprediction will happen. So my answer to your question is: No, you don't have to assume that the state is taken, but it is very likely. You could flush a lot of NOP operations to generate situations where this is not the case.

$\endgroup$
  • $\begingroup$ The only way I see for NOP to influence a branch predictor is using them to ensure that two branches are hashed to the same cache entry. $\endgroup$ – AProgrammer May 22 '13 at 12:07
  • $\begingroup$ I am completely confused by this answer. 1) do_sth_else? 2) The branches that control the statements are mispredicted, not the statements themselves. 3) As @PaulAClayton pointed out: the assumption H&P are making is that this is the second time this inner loop has been encountered. 4) "not been encountered before" makes a 1 bit predictor 50% likely to mispredict, in H&P's situation they are explaining why the mispredict probability is 100%. This whole discussion in H&P is to motivate one of the major reasons architects have moved to 2-bit predictors. $\endgroup$ – Wandering Logic May 22 '13 at 12:17
  • $\begingroup$ @AProgrammer Yes, that's what i meant. @wandering-logic: You are right, my example is confusing. I tried to use do_sth_else() as a short term for one iteration. You are also right that H&P assume that the loop has been encountered before. $\endgroup$ – evnu May 22 '13 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.