This question is taken from Modern Processor Design by Shen and Lipasti.
Consider the following code segment within a loop body for problems 5:
if (x is even) then (branch b1) increment a (b1 taken) if (x is a multiple of 10) then (branch b2) increment b (b2 taken)
Assume that the following list of 9 values of x is to be processed by 9 iterations of this loop. 8, 9, 10, 11, 12, 20, 29, 30, 31. Note: assume that predictor entries are updated by each dynamic branch before the next dynamic branch accesses the predictor (i.e., there is no update delay).
Assume a two-level branch prediction scheme is used. In addition to the one-bit predictor, a one bit global register (g) is used. Register g stores the direction of the last branch executed (which may not be the same branch as the branch currently being predicted) and is used to index into two separate one-bit branch history tables (BHTs) as shown below.
Depending on the value of g, one of the two BHTs is selected and used to do the normal one-bit prediction. Again, fill in the predicted and actual branch directions of b1 and b2 for nine iterations of the loop. Assume the initial value of g = 0, i.e., NT. For each prediction, depending on the current value of g, only one of the two BHTs is accessed and updated. Hence, some of the entries below should be empty.
Note: assume that predictor entries are updated by each dynamic branch before the next dynamic branch accesses the predictor (i.e. there is no update delay).
8 9 10 11 12 20 29 30 31
For g=0
b1 predicted : __ N____ T____N___ _ __ T____ T_ __ __ T ______
b1 actual :__ T____ N____T____ N____ T____ T____ N____ T____ N__
b2 predicted: ____ __ N______ __ N____ __ _ _ __ N____ __ __ N
b2 actual :__ N____ N____T____ N____ N____ T____ N____ T____ N__
For g=1
b1 predicted: ____ ____ ____ __ N______ _ _ __ N_ _ __ N
b1 actual :__ T____N____ T____ N____ T____ T____ N____ T____ N__
b2 predicted: __ N______ __ N______ __ T____ N____ __ __ T____ __
b2 actual :__ N____N____ T____ N____N____ T____ N____ T____ N__
What is the logic behind these table values for both g=0 and g=1?