[Solved]: Why do most books say that a 1 bit branch predictor mispredicts on the first loop iteration?

Problem Detail: 

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.

Asked By : inherithandle

Answered By : Paul A. Clayton

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12213