Lab13 : Basic Pipelining

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 3 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?