Homework 9

General Comments

• Problem from the book are taken from the Chapter Review Problems sections.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).

Details

Do the following exercises from pages 112-113 of your textbook (106-107 in full book) and the ones listed below.

Problem	Points	Comments
43	4
48	3
50	3	In other words, give an algorithm/procedure that accomplishes what is asked.
#1 below	6
#2 below	6
#3 below	4
#4 below	2
#5 below	4

Note: For problems 1-4, do not worry about potential problems that jump instructions might cause.

1. 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. 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. Generalize the previous results: If a program written in our machine language consists of n instructions,
   1. Give a formula for the number of steps required to execute the program normally.
   2. Give a formula for the number of steps required if pipelining is used.
   3. Give a formula 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. What is the speedup in this case? (Hint: What happens when n is really large?)
4. Let's generalize one more time: Assume a machine has a machine cycle with 7 steps 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). What would the speedup be? Make sure to justify your answer.
5. 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? It might help to run through one of the examples in the book that has jumps using pipelining to see what the problem is.