Four Bits Of History

A two-level adaptive predictor keeps an nn-bit branch history register and one 2-bit saturating counter per history pattern, so there are 2n2^n counters. Take n=4n = 4: 16 counters, indexed by the last four outcomes.

A branch inside a loop produces one of the repeating sequences below forever (0 = not taken, 1 = taken).

More than one of these is predicted essentially perfectly after warm-up. Which are?

A

000011 000011 ... (period 6)

B

A uniformly random taken/not-taken sequence

C

0101 0101 ... (period 2)

D

0011 0011 ... (period 4)

E

000001 000001 ... (period 6)