Question

This exercise is intended to help you understand the relationship between forwarding, hazard detection, and ISA design. Problems in this exercise refer to the following sequence of instructions, and assume that it is executed on a 5-stage pipelined datapath:

add r5,r2,r1

lw r3,4(r5)

lw r2,0(r2)

or r3,r5,r3

sw r3,0(r5)

4.13.1 [5] If there is no forwarding or hazard detection, insert nops to ensure correct execution.

4.13.2 [10] Repeat 4.13.1 but now use nops only when a hazard cannot be avoided by changing or rearranging these instructions. You can assume register R7 can be used to hold temporary values in your modified code.

4.13.3 [10] If the processor has forwarding, but we forgot to implement the hazard detection unit, what happens when this code executes? 4.13.4 [20] If there is forwarding, for the first five cycles during the execution of this code, specify which signals are asserted in each cycle by hazard detection and forwarding units in Figure 4.60.

4.13.5 [10] If there is no forwarding, what new inputs and output signals do we need for the hazard detection unit in Figure 4.60? Using this instruction sequence as an example, explain why each signal is needed. 4.13.6 [20] For the new hazard detection unit from 4.13.5, specify which output signals it asserts in each of the first five cycles during the execution of this code.

Short answer

4.13.1

The required sequence of the instructions:

add r5, r2, r1

nop

nop

ld r3, 4(r5)

ld r2, 0(x2)

nop

or r3, r5, r3

nop

nop

sd r3, 0(r5)

4.13.2

In the sequence of instructions, “nop” was used only when the necessary purpose. So, this can’t possible to change or rearrange these instructions.

4.13.3

For the given condition, the code will be executed without any obstacles.

4.13.4

Which signals are asserted in every cycle is specified by the hazard detection and the units of forwarding in the mentioned figure:

instruction	Cycles
add	IF	ID	EX	ME	WB
ld		IF	ID	EX	ME	WB
ld			IF	ID	EX	ME	WB
or				IF	ID	EX	ME	WB
sd					IF	ID	EX	ME	WB

4.13.5

Further, no signal is needed.

4.13.6

After assertion of each output signal is specified in every cycle:

instruction	Cycles									Values
add	IF	ID	EX	ME	WB					PCWrite -1
ld		IF	ID	EX	ME	WB				PCWrite-1
ld			IF	ID	EX	ME	WB			PCWrite-1
or				IF	ID	EX	ME	WB		PCWrite-0
sd					IF	ID	EX	ME	WB	PCWrite-0

Step-by-step solution

Define the concept.

4.13.1

If neither forwarding nor hazard detection exists.

The instruction “nops” is inserted two times after the instruction “add”.

The instruction “nops” is inserted one time after the instruction “ld r2, 0(x2)”.

The instruction “nops” is inserted two times after the instruction “or r3, r5, r3”.

4.13.2

add r5, r2, r1

nop

nop

ld r3, 4(r5)

ld r2, 0(x2)

nop

or r3, r5, r3

nop

nop

sd r3, 0(r5)

In the sequence of instructions,

The instruction “nops” is inserted two times after the instruction “add”.

The instruction “nops” is inserted one time after the instruction “ld r2, 0(x2)”.

The instruction “nops” is inserted two times after the instruction “or r3, r5, r3”.

Therefore, “nop” was used only when the necessary purpose. So, this can’t possible to change or rearrange these instructions.

4.13.3

Hazard detection is only needed for inserting the stall when any load that uses the result of the load is followed by the instruction.

Hence, that does not occur for this purpose.

Hence, no obstacle will be created for this.

4.13.4

For the instruction “add” ,

In the first cycle “IF”.

In the second cycle “ID”.

In the third cycle “EX”.

In the fourth cycle “ME”.

In the fifth cycle “WB”.

For the instruction “ld” ,

In the second cycle “IF”.

In the third cycle “ID”.

In the fourth cycle “EX”.

In the fifth cycle “ME”.

In the sixth cycle “WB”.

For the instruction “ld” ,

In the third cycle “IF”.

In the fourth cycle “ID”.

In the fifth cycle “EX”.

In the sixth cycle “ME”.

In the seventh cycle “WB”.

For the instruction “or” ,

In the fourth cycle “IF”.

In the fifth cycle “ID”.

In the sixth cycle “EX”.

In the seventh cycle “ME”.

In the eigth cycle “WB”.

For the instruction “sd” ,

In the fifth cycle “IF”.

In the sixth cycle “ID”.

In the seventh cycle “EX”.

In the eigth cycle “ME”.

In the ninth cycle “WB”.

4.13.5

The instruction which is in the stages of "ID" requires to stall if it relys on the produced value by the "EX" stage instruction or the "MEM" stage instruction . Hence, it is needed for checking the destination register of these two specified instructions.

For the "EX" stage instruction, it is needed for checking the “Rd” for instruction of type "R" and “RD” for loading.

For the "MEM" stage instruction, already the destination register has been selected. Hence, it is needed for checking the number of the “register”.

The further inputs to the unit of the "hazard detection” are register "Rd" from the pipeline register of the "ID/EX" and the output register number from the pipeline register of the "EX/MEM".

The field of "Rt" from the register of "ID/EX" already is the hazard detection input unit in the mentioned figure.

4.13.6

The PCWrite will contain 1 for the first instruction.

The PCWrite will contain 1 for the second instruction.

The PCWrite will contain 1 for the third instruction.

The PCWrite will contain 0 for the fourth instruction.

The PCWrite will contain 0 for the fifth instruction.

Determine the calculation.

4.13.1

Here, neither forwarding nor hazard detection exists.

After inserting the instruction “nops” by ensuring the correct execution.

The required sequence of the instructions:

add r5, r2, r1

nop

nop

ld r3, 4(r5)

ld r2, 0(x2)

nop

or r3, r5, r3

nop

nop

sd r3, 0(r5)

4.13.2

add r5, r2, r1

nop

nop

ld r3, 4(r5)

ld r2, 0(x2)

nop

or r3, r5, r3

nop

nop

sd r3, 0(r5)

In this sequence of the instructions, “nop” was used only when the necessary purpose. So, this can’t possible to change or rearrange these instructions.

4.13.3

For the given condition, the code will be executed without any obstacles.

Hazard detection is only needed for inserting the stall when any load that uses the result of the load is followed by the instruction.

Hence, that does not occur for this purpose.

4.13.4

Here, no forwarding exists in the first five cycles.

Which signals are asserted in every cycle is specified by the hazard detection and the units of forwarding in the mentioned figure:

instruction	Cycles
add	IF	ID	EX	ME	WB
ld		IF	ID	EX	ME	WB
ld			IF	ID	EX	ME	WB
or				IF	ID	EX	ME	WB
sd					IF	ID	EX	ME	WB

Details of the forwarding:

ForwardA	ForwardB	Explanation
X	X	There are no instructions for the “EX” stage.
X	X	There are no instructions for the “EX” stage.
0	0	There are no forwarding values that are taken from the registers.
2	0	The base register is taken from the result of previous instruction
0	0	base register taken from registers
0	1	rs1 = x15 taken from register rs2 = x13 taken from result of 1st ld – two instructions ago
0	0	base register is taken from the register file

4.13.5

The required sequence of the instructions:

add r5, r2, r1

nop

nop

ld r3, 4(r5)

ld r2, 0(x2)

nop

or r3, r5, r3

nop

nop

sd r3, 0(r5)

Further, no signal is needed.

4.13.6

After assertion of each output signal is specified in every cycle:

instruction	Cycles									Values
add	IF	ID	EX	ME	WB					PCWrite -1
ld		IF	ID	EX	ME	WB				PCWrite-1
ld			IF	ID	EX	ME	WB			PCWrite-1
or				IF	ID	EX	ME	WB		PCWrite-0
sd					IF	ID	EX	ME	WB	PCWrite-0