Question

Consider the MIPS five-stage pipeline processor with branch prediction. For a particular beq instruction, the branch outcomes are repeatedly (and for a very long time) as follows:

NT, T, NT, NT, T, NT

where NT = "not taken" and T = "taken". In other words, the conditional-branch outcomes are NT, T, NT, NT, T, NT, NT, T, NT, NT, T, NT.....

(a) Suppose the branch prediction is the static "always-taken". What is the percentage of outcomes that the predictor was correct.

Answer 1

The static 'always-taken' branch predictor would be correct 20% of the time for the given pattern of branch outcomes (NT, T, NT, NT, T, NT...), as it accurately predicts the 'taken' outcome once in every five outcomes.

Step-by-step explanation:

The student is asking about the accuracy of a static branch predictor in a MIPS five-stage pipeline processor, where the branch outcomes follow a specific pattern (NT, T, NT, NT, T, NT...). Assuming an always-taken branch prediction, we need to calculate the percentage of times the predictor is correct given the pattern of branch outcomes.

Looking at the pattern (NT, T, NT, NT, T, NT...), we see that there is 1 'T' for every 4 outcomes. Since the predictor always predicts 'taken,' it would only be correct for the 'T' outcomes and incorrect for every 'NT' outcome.

Therefore, the percentage of correct predictions is:

• Total outcomes = 5
• Correct predictions ('T') = 1
• Percentage of correct predictions = (Number of correct predictions / Total outcomes) * 100%
• Percentage of correct predictions = (1 / 5) * 100% = 20%

Thus, the static "always-taken" branch predictor is correct 20% of the time for the given pattern of branch behavior.