Question

In this exercise, we examine how data dependences affect execution in the basic 5-stage pipeline described in section 4.5. Problems in this exercise refer to the following sequence of instructions:

or r1,r2,r3

or r2,r1,r4

or r1,r1,r2

Also, assume the following cycle times for each of the options related to forwarding:

Without Forwarding	With Full Forwarding	With ALU-ALU Forwarding Only
250ps	300ps	290ps

4.9.1 Indicate dependences and their type.

4.9.2 Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them.

4.9.3 Assume there is full forwarding. Indicate hazards and addNOPinstructions to eliminate them.

4.9.4 What is the total execution time of this instruction sequence

without forwarding and with full forwarding? What is the speedup achieved by adding full forwarding to a pipeline that had no forwarding?

4.9.5 Addnopinstructions to this code to eliminate hazards if there is ALU-ALU forwarding only (no forwarding from the MEM to the EX stage).

4.9.6 What is the total execution time of this instruction sequence with only ALU-ALU forwarding? What is the speedup over a no-forwarding pipeline?

Short answer

4.9.1 For the given sequence of instruction, dependences, and their types are as follows:

Instructions	Dependence
I1: or r1, r2, r3	RAW on r1
I2: or r2, r1, r4	RAW on r2
I3: or r1, r2, r2	WAR on r2
	WAR on r1
	WAW on r1

4.9.2 In a no forwarding pipeline processor, the dependency with nop instructions is as follows:

Instructions	Description
I1:or r1, r2, r3	Delay I2 to avoid a RAW hazard
nop
nop
I2:or r2, r1, r4	Delay I3 to avoid a RAW hazard
nop
nop
I3: or r1, r2, r2

4.9.3 With the full forwarding pipeline processor, the dependency with nop instructions is as follows:

Instructions	Dependence
I1: or r1, r2, r3
I2: or r2, r1, r4	No RAW on r1(forwarded)
I3: or r1, r2, r2	No RAW on R2(forwarded)

4.9.4 The total execution time :

Without forwarding=1980ps

With forwarding =1680ps

Speedup due to forwarding=1.18

4.9.5

Instruction	Description
I1: or r1, r2, r3
I2: or r2, r1, r4	ALU-ALU
I3: or r1, r2, r2	ALU-ALU

4.9.6 The total execution time:

Without forwarding=1980ps

With ALU-ALU forwarding=1470ps

Speed up with ALU-ALU=1.35

Step-by-step solution

Determine the Data dependency.

The dependence occurs when the data needed by the instructions are produced by the other instruction. Based on the read and write operations the chances of overlapping will cause hazards. There are three types of hazards structural, data and control hazards. The hazard and dependency occurs randomly concerning each other.

Determine the dependency type.

4.9.Given a sequence of instructions:

I1: or r1, r2, r3

I2: or r2, r1, r4

I3: or r1, r2, r2

The instruction I1 produces Read After Write dependency on register r1 from I1 to I2 and I3. Instructions I2 and I3 read the value of r1. The instruction I2 produces Read After Write dependency on r2 from I2 to I3. Because I3 performs read on r2 after the I2. Write After Read will be created on r2 from I1 to I2. Because I1 and I2 write on the same location r2. Write After Read will be created on r1 from I1 to I3. Because I1 and I3 write on the same location r1.Write After Write will occur on r1 from I1 to I3 because I3 rewrites r1 after I1.

For the given sequence of instruction, dependences, and their types are as follows:

Instructions	Dependence
I1: or r1, r2, r3	RAW on r1
I2: or r2, r1, r4	RAW on r2
I3: or r1, r2, r2	WAR on r2
	WAR on r1
	WAW on r1

Determine the dependency with nop.

4.9.2

WAR and WAW do not cause hazards in a basic five-stage pipeline. The nop instructions will eliminate the hazards In a no forwarding pipeline processor, the dependency with nop instructions is as follows:

Instructions	Description
I1:or r1, r2, r3	Delay I2 to avoid RAW hazard
nop
nop
I2:or r2, r1, r4	Delay I3 to avoid RAW hazard
nop
nop
I3: or r1, r2, r2

Determine the dependency with nop.

4.9.3

An ALU instruction with full forwarding can forward the value to the EX stage of the next instruction without any hazard. The load will not be forwarded to the EX stage of the next instruction.

With the full forwarding pipeline processor, the dependency with nop instructions is as follows:

Instructions	Dependence
I1: or r1, r2, r3
I2: or r2, r1, r4	No RAW on r1(forwarded)
I3: or r1, r2, r2	No RAW on R2(forwarded)

Determine the total execution time.

4.9.4 The total execution will be calculated by the number of cycles and the clock cycle time. Let us consider the clock cycle time to be 180ps. The sequence of instruction takes 7 cycles for execution.

The total execution time without forwarding will be calculated as follows:

$$\begin{gathered} (7+4)\times 180ps=11\times 180 \\ =1980ps \end{gathered}$$

The Total execution time with forwarding is calculated as follows:

$7\times 240=1680ps$

The speed-up due to forwarding will be 1.18 as per the total execution time.

Determine nop for ALU-ALU forwarding.

4.9.5 The ALU instruction will be forwarded to the next instruction with ALU-ALU only forwarding.

Instruction	Description
I1: or r1, r2, r3
I2: or r2, r1, r4	ALU-ALU forwarding of r1 from I1
I3: or r1, r2, r2	ALU-ALU forwarding of r2 from I2

Determine the total execution time for ALU-ALU.

4.9.6 The total execution will be calculated by the number of cycles and the clock cycle time. Let us consider the clock cycle time to be 180ps. The sequence of instruction takes 7 cycles for execution.

The total execution time without forwarding will be calculated as follows:

$$\begin{gathered} (7+4)\times 180ps=11\times 180 \\ =1980ps \end{gathered}$$

The Total execution time with ALU-ALU forwarding is calculated as follows:

$7\times 120=1470ps$

The speed-up due to forwarding will be 1.35 as per the total execution time.