CS61c Lab 11 -- Basic Pipelining
Fall 2004

TAKE HOME LAB!

Due to the Veterans Day holiday this Thursday we will not be holding lab for 61c this week. Please complete the lab at your leisure and be prepared to show your results to your TA in lab next week.

Once again, there will be no labs held this week!

GOALS

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

GIVEN

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

EXERCISE 1

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.

EXERCISE 2

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

EXERCISE 3

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.

EXERCISE 4

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