Assignment6:Pipelining Solution

Description

1. ​Consider the execution of the following sequence of three instructions on the 5-stage MIPS pipeline.

add	8	9	10
lw	10 400(8)
sub	9	10	8

1. List all dependences and their types

2. Show all forwarding links between each instruction pair assuming full forwarding

Assume three cases separately – (i) no forwarding (ii) ALU-ALU forwarding only and

1. 1. 61. full forwarding. Also assume that the pipeline clock cycle times are 250,

270 and 280 picosecs. for the three cases respectively. Answer the following questions for each of the three cases.

1. 3. Draw a multicycle pipeline diagram showing clearly the stage each instruction is in during each cycle

1. 3. What is the total execution time?

1. 3. What is the average utilization of the pipeline?

1. 3. Can the instructions be re-ordered to decrease the total execution time? If so, how?

2. The goal of this problem is to compare the performance (accuracy) of different predictors for the snippet below.

• join

bnez t0 chalo

In each part below assume that the branch predictor is initially in the “Strong NOT Taken”state.

1. The number of mispredictions with a (0, 2) branch predictor is ______ out of 100 and is asymptotically _______ .

2. The number of mispredictions with a (0, 3) branch predictor is ______ out of 100 and is asymptotically _______ .

3. The minimum number of mispredictions with a (0, k) branch predictor is

______ , is asymptotically _______ and occurs for k = ______ .

4. The number of mispredictions with a (2, 2) correlating branch predictor is

______ out of 100 and is asymptotically _______ . (An (m, k) correlating branch predictor keeps track of the outcomes of the most recent branches – both local and global.

5. As the number of iterations, n , tends to infinity, the minimum number of mispredictions with an (m, k) correlating branch predictor is achieved for m = ______ and k = _____ . For this predictor, the number of mispredictions is

______ out of 100 and is asymptotically _______ .