Question

Computer organization

6) Given the MIPS five stage pipeline and the following instruction sets: [30 pts, 10 pts each] instruction set #1 1w $1, 40 ($6) add $2, $3, $1 add $1, $6, $4 and $1, $1, $4 sw $2, 20 ($4) instruction set #2 add $1, $5, $3 sw$1, 0 ($2) lw $1, 4 ($2) add $5, $5, $1 sw$1, 8 ($2) a) If there is no forwarding or hazard detection, write the instructions (same order) and insert nop's to force the appropriate number of stalls which would be required

Answer 1

There are 5 stages in pipeline which are :- 1. instruction fetch(IF), 2. instruction decode(ID), 3. execute (EX) ,4. Memory operation (MEM) and 5. write back (WB).

Now data hazard occur between two consecutive instruction whenever they accessing over common register or data and one of the instruction is performing Write operation over the common data. Hence if there is data dependency between instructions say I1 and I2, then I2 after passing through first stage of pipeline, it has to wait for 3 clock cycle for I1 to complete.

Hence we will insert 3 nops between two consecutive instruction, whenever there is data dependency between them.

In instruction set #1

There is Read After Write dependency between I1 and I2 because I1 is writing some value into $1 which is being Read by I2. Hence 3 nops will be inserted between them.

Then there is Write After Read dependency between I2 and I3 because I2 is performing Read over register $1 into which I3 is performing Write.

Then there is Write After Write dependency between I3 and I3 because of register $1.

There is no data dependency between I4 and I5.

Hence the instructions with nop will be

lw $1, 40($6)

nop

nop

nop

add $2, $3, $1

nop

nop

nop

add $1, $6, $4

nop

nop

nop

and $1, $1, $4

sw $2, 20($4)

In Instruction set #2

There is Read After Write dependency between I1 and I2 due to register $1.

There is no data dependency between I2 and I3 because both are performing Read operation over $1 and $2.

There is Read After Write dependency between I3 and I4 due to $1

There is no data dependency between I4 and I5 because both are performing Read over $1.

Hence the instructions with nop will be

add $1, $5, $3

nop

nop

nop

sw $1, 0($2)

nop

nop

nop

lw $1, 4($2)

nop

nop

nop

add $5, $5, $1

sw $1, 8($2)

Please comment for any clarification.