Homework 8

22C:122, Fall 1999

Due Monday Nov 1, 1999, in class

1. Background: Consider the problem of building a pipelined CPU with the canonical 5-stage pipe:

                          ______       _____
   Instruction Fetch     |______|-----|     |
                          |____|   _  |     |
   Address Computation   |______|-| | |     |
                          |____|  | | |     |
   Operand Fetch         |______|=| |-|  M  |
                          |____|  |R| |     |
   Operate               |______| | | |     |
                          |____|  | | |     |
   Operand Store         |______|=|_|-|_____|
   

   Note that the fetch stages only read from registers or memory, while the final operand store stage is the only one that writes to memory.

   Part A: Which of the pipeline stages do no useful work for each of the following classes instructions:

   1. jump to an absolute address
   2. indexed jump
   3. PC relative jump
   4. load register immediate
   5. load register from memory
   6. store register to memory
   7. add immediate
   8. add register to memory
   9. add memory to register

   Part B: Consider a pure load-store architecture, that is, an architecture where all arithmetic operations are done register-to-register, and where the only memory reference instructions are load and store, moving values from register to memory and visa versa. Would there be a performance penalty for collapsing the pipeline down to fewer stages? If collapsing the pipe is feasible, how many stages are in the result, and what would each pipeline stage do?

   Hint: You might consider looking at what use each instruction makes of each pipeline stage in the canonical 5-stage pipe, notice what pipeline stages do work that is similar to other stages, and notice which stages are unused. Working from this foundation, see if you can move functions around until some stage is never needed.

   Part C: Considering only the instructions listed in part A, for each of the 4 interstage registers, what information must be included in that register?

2. Background: Assume you have an Ultimate RISC with a 3-stage pipeline, where stage 1 fetches the source operand address, stage 2 fetches the source operand and, in parallel, fetches the destination address, and stage 3 stores the operand in the destination.

   NOTE: This is not the pipeline scheme used in any lecture for this or any previous offering of this course!

   Part A: How many delay slots must be filled between an operand store and: The next load from that memory location, the entry to a new block of code if the destination was the PC, the execution of a modified instruction where the destination is the source address field of the instruction, and the execution of a modified instruction where the destination address is the destination field of the modified of the instruction?

   Part B: What information must be included in each interstage register of this machine!