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 ri,r2,r3 or r2,r1, r4 or ri, ri, 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 a. Indicate dependences and their type. b. Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them. c. Assume there is full forwarding. Indicate hazards and add NOP instructions to eliminate them. d. 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? e. Add nop instructions to this code to eliminate hazards if there is ALU-ALU forwarding only (no forwarding from the MEM to the EX stage). f. What is the total execution time of this instruction sequence with only ALU-ALU forwarding? What is the speedup over a no-forwarding pipeline?

Answer 1

This exercise discusses data dependences and their effects on execution in a basic 5-stage pipeline. It covers identifing dependences, hazards, adding NOP instructions, and calculating execution times and speedup.

Step-by-step explanation:

a. Dependences and their types:

The dependences and their types in the given instruction sequence are as follows:

• Dependency between the first instruction 'or ri,r2,r3' and the third instruction 'or r2, r1, r4' is a Read-After-Write (RAW) dependence.
• Dependency between the second instruction 'or r2, r1, r4' and the fourth instruction 'or ri, ri, r2' is a Write-After-Write (WAW) dependence.
• Dependency between the third instruction 'or r2, r1, r4' and the fourth instruction 'or ri, ri, r2' is a Read-After-Write (RAW) dependence.

b. Hazards and adding nop instructions:

If there is no forwarding in the pipelined processor, the hazards that occur are:

• A RAW hazard between the first and third instructions.
• A WAW hazard between the second and fourth instructions.
• A RAW hazard between the third and fourth instructions.
• To eliminate these hazards, we need to add nop (no-operation) instructions to stall the pipeline for one cycle. The corrected code is as follows:

or ri,r2,r3
nop
or r2,r1,r4
or r2,r1,r4
or ri,ri,r2

c. Hazards and adding NOP instructions with full forwarding:

If there is full forwarding, the hazards that occur are:

• No hazards occur with full forwarding.

d. Total execution time and speedup:

The total execution time of the instruction sequence without forwarding is 1250ps (5 cycles x 250ps). The total execution time of the instruction sequence with full forwarding is 1450ps (5 cycles x 290ps), resulting in a speedup of 200ps (250ps - 290ps).

e. Adding NOP instructions for ALU-ALU forwarding:

If there is only ALU-ALU forwarding (no forwarding from the MEM to the EX stage), the hazards that occur are:

• A RAW hazard between the first and third instructions.
• A RAW hazard between the third and fourth instructions.
• To eliminate these hazards, we need to add nop (no-operation) instructions to stall the pipeline for one cycle. The corrected code is as follows:

or ri,r2,r3
nop
or r2,r1,r4
or r2,r1,r4
or r2,r1,r4

f. Total execution time and speedup with ALU-ALU forwarding:

The total execution time of the instruction sequence with only ALU-ALU forwarding is 1450ps (5 cycles x 290ps), resulting in a speedup of 140ps (290ps - 300ps).