hpca/SampleMidterms/Midterm2/problem3

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)

A) [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)?

B) [5 points] For a two-bit saturating counter predictor, what is the misprediction

rate on this branch in the second occurrence of this pattern?

C) [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.