Due: Friday, November 17, 2017, 9:00 am (start of the class)

## Pipelining and Branch Prediction

Given the following parameters, answer the following questions.

• Each stage of combinational circuitry takes 2ns
• The latch delay time is 1ns
• The single stage CPU has 10 layers of circuitry and 1 layer of latches
• A multi-stage pipeline has to execute the same 10 layers of circuitry and will have a latch for each stage.
1. What is the time required to execute one instruction on the single stage CPU?
2. What is the time required to execute one stage on a 10-stage CPU?
3. What is the time required to execute one instruction on a 10-stage CPU?
4. What is the time required to execute one instruction on a 5-stage CPU?
5. What is the speedup for 1000 instructions using a 5-stage CPU?
6. What is the speedup for 1000 instructions using a 10-stage CPU?

Assume that the CPU uses branch prediction to estimate which instruction to fetch next in the case of a conditional branch. When answering the following problems, assume that 20% of the instructions are conditional branches.

1. What is the probability there are no conditional branches currently being executed in a 5-stage pipeline?
2. What is the probability there are no conditional branches currently being executed in a 10-stage pipeline?

Assume that it is known whether branch prediction failed during the last stage of the pipeline. Further assume that there is zero time cost to fetching the right instruction and start it executing.

1. What is the time delay between the discovery of the failed branch and the proper next instruction completing execution for a 5-stage pipeline?
2. What is the time delay between the discovery of the failed branch and the proper next instruction completing execution for a 10-stage pipeline?