Suppose that a machine with a 5-stage pipeline uses branch prediction (i.e., no branch delay slots). 15% of the instructions for a given test program are branches, of which 80% are correctly predicted. The other 20% of the branches suffer a 4-cycle mis-prediction penalty.
(In other words, when the branch predictor predicts incorrectly, there are four 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.
Now suppose you are given the option of replacing this processor's branch prediction scheme with a 1-cycle branch delay system (i.e., there is one branch delay slot after every branch). What percentage of the branch delay slots must be ?lled in order for the CPU with the
branch-delay system to have better performance than the CPU described in question 4?