CS61c Lab 11 -- Basic Pipelining
Spring 2005


In this lab you will be asked questions about the basic 5-stage MIPS pipeline and generation of a "pipeline timing" diagram.


At some point during lab please ask your lab TA to grade your Homework 6 submission. You will be asked to walk through a series of tests of your circuit. If you can not get your submission graded during lab you will need to contact your TA to setup another time for your demo.


Given the following MIPS code:

1) addi $t0 $t1 100
2) lw   $t2 4($t0)
3) add  $t3 $t1 $t2
4) sw   $t3 8($t0)
5) lw   $t5 0($t6)
6) or   $t5 $t0 $t3


Given the perfectly pipelined representation below
(I = "Instruction Fetch", D="Decode", E="Execute", M="Memory Access", W="Write Back")

1) addi $t0 $t1 100   I D E M W
2) lw   $t2 4($t0)      I D E M W
3) add  $t3 $t1 $t2       I D E M W
4) sw   $t3 8($t0)          I D E M W
5) lw   $t5 0($t6)            I D E M W
6) or   $t5 $t0 $t3             I D E M W

Draw directed arrows to indicate data dependencies between stages. The arrow should start at the stage where the data is available and end at the stage where the data is needed. (You can either print this page out and edit our ASCII picture above or draw your own with more room.


Based on your table above, you might notice that some arrows are "forward" arrows, indicating the values are needed *after* they are available, which is what is intended. Some arrows are not -- use these arrows to fill in the table below:

For each instruction, list the instructions which are read-after-write dependant (which cause stalls) on that instruction.

________ is dependant on instruction 1
________ is dependant on instruction 2
________ is dependant on instruction 3
________ is dependant on instruction 4
________ is dependant on instruction 5


Rewrite the table from exercise 1 to include stalls.
"Stalls" means that noop instructions will be inserted between relevant instructions, and no gap between the stages will be introduced.


How many clock cycles does it take to finish executing all six instructions?