SampleMidterm/Problem03

Problem 3. [15 points] Branch Prediction

A processor is executing a program in which the most frequently occurring branch is having the following repeating sequence of outcomes: N, T, N, T, T, N, T, T, then repeat.
(not-taken, taken, not-taken, taken, taken, not taken, taken, taken, then repeat)

  1. [5 points] For a one-bit predictor, how many mispredictions occur on this branch in the second occurrence of this pattern (i.e. the eight branches that occur after the first eight have been processed already)?

  2. [5 points] For a two-bit predictor, what is the misprediction rate on this branch in the second occurrence of this pattern? (Assume that we are using the using the 0  1  2  3 counter from the lectures, not the 023/320 one from the textbook).

  3. [5 points] For a local history predictor with a 1-bit history (and 2 two-bit counters), what is the misprediction rate on this branch in the second occurrence of this pattern? The history and counters are all 0 before the first occurrence.