Homework 13

Details

For each problem make sure you clearly and neatly show all of your work! Each part/problem is worth 5 points unless otherwise stated.

Do not worry about potential problems that jump instructions might cause. If you are not sure why this matters, you probably do not need to worry about it. Also, for each problem show your calculations and not just the final answer!

1. (6) Recall that our machine language uses 3 cycles (F, D, E). If a program written in our machine language consists of 15 instructions,
   1. How many steps are required to execute the program if it is executed normally?
   2. How many steps are required if pipelining is used?
   3. How much faster is pipelining than normal execution for this program? (Give your answer in the form "x times faster", where x is a number. Hint: You need to divide one number by another number to get the answer.)
2. (6) If a program written in our machine language consists of 100 instructions,
   1. How many steps are required to execute the program if it is executed normally?
   2. How many steps are required if pipelining is used?
   3. How much faster is pipelining than normal execution for this program?
3. (8) Generalize the previous results: If a program written in our machine language consists of n instructions,
   1. Give a formula (in terms of n) for the number of steps required to execute the program normally.
   2. Give a formula (in terms of n) for the number of steps required if pipelining is used.
   3. Give a formula (in terms of n) for how much faster pipelining is than normal execution.
   4. We define speedup to be the theoretical upper limit on how much faster pipelining is than normal execution. Give a formula (in terms of n) for the speedup in this case. (Hint: What happens when n is really really large?)
4. (12) Let's generalize one more time: Assume a machine has a machine cycle with 7 steps (IT, IF, ID, EX, MT, MM, WB) instead of 3 and that the steps can be overlapped in much the same way as we discussed with our machine (that is, we can start a new instruction at each step of the machine cycle). Then assume we have a program with n instructions.
   1. Draw a picture of what the execution of 3 instructions looks like with normal execution.
   2. Draw a picture of what the execution of 3 instructions looks like with pipelining.
   3. Give a formula (in terms of n) for the number of steps required to execute the program normally.
   4. Give a formula (in terms of n) for the number of steps required if pipelining is used.
   5. Give a formula (in terms of n) for how much faster pipelining is than normal execution.
   6. Give a formula (in terms of n) for the speedup in this case.
5. (2 bonus) It turns out that for various reasons, including the presence of jump instructions, one rarely attains the theoretical speedups you calculated in the previous questions. Why do jump instructions slow things down? (Hint: Think about what happens when a jump instruction occurs that is different when you are pipelining versus not pipelining.)