Question

Suppose that a machine with a 14-stage pipeline uses branch prediction. 13% of the instructions for a given test program are branches, of which 88% are correctly predicted. Branch instructions the are predicted correctly have a 1 cycle branch delay. The other 12% of the branches suffer a 7-cycle mis-prediction penalty. (In other words, when the branch predictor predicts incorrectly, there are 7 instructions in the pipeline that must be discarded.) Assuming there are no other stalls, develop a formula for the number of cycles it will take to complete n lines of this program.

Answer 1

Answer:

The formula is: 1.2236n + 13

Explanation:

Given data:

14-stage pipeline

13% of the instructions for a given test program

88% are correctly predicted

1 cycle branch delay

12% of the branches suffer a 7-cycle mis-prediction penalty

Question: Develop a formula for the number of cycles it will take to complete n lines of the program

Here

$\frac{13n}{100}$ are branching instructions, but, 88% are correctly predicted, therefore:

$(\frac{13n}{100} )*(\frac{88}{100} )=0.1144n$

According the question, 12% of the branches suffer a 7-cycle mis-prediction penalty, the delay due this mis-prediction:

$(\frac{13n}{100} )*(\frac{12}{100} )*7=0.1092n$

The total delay:

0.1144n + 0.1092n = 0.2236n

The number of cycles it will take to complete n lines of the program:

n + 0.2236n + 14 - 1 = 1.2236n + 13