Question

1. Assume we have 8 registers, R0~R7, and we have a pipeline of 6 stages:

Instruction Fetch (IF), Instruction Issue (II), Operands Fetch (OF), Execution (EX), Write Back (WB), and Commitment (CO). Each stage needs exactly 1 cycle to finish its work.

Also assume that the pipeline supports forwarding, which means the result of WB can be forwarded to OF.

Given the following piece of instructions:

R1 = R0 + R2

R3 = R4 + R5

R6 = R1 + R3

R0 = R2 + R7

1. Identify all the data dependencies and their types.

2. Assume we run the instructions in the 6 stage pipeline that supports forwarding, register renaming, and out-of-order execution. Show which of the registers should be renamed, and show the new order of the instructions.

3. How many cycles do we need if we run the instructions in the 6 stage pipeline that supports forwarding, register renaming, and out-of-order execution?
   
   
   2. C Programming Language was developed in 1970’s, but why the classic 1980’s arcade game “Donkey Kong” was still written in an assembly language?

Answer 1

Multiple questions asked in a single post, Solution for the first problem is provided below, please comment if any doubts:

1.

i)

• The data decencies are a result of mixed use registers in a sequence of instruction such that their appearances in various instruction make it dependable on another instruction.
• The dependencies in the given instruction sequence are:
  1. There is a dependency between first and third instruction
     • Here R1 resister is used in both the instructions.
     • It is of type Read-after-Write
  2. There is a dependency between second and third instruction
     • Here R3 resister is used in both the instructions.
     • It is of type Read-after-Write
  3. There is a dependency between first and fourth instruction
     • Here R0 resister is used in both the instructions.
     • It is of type Write-after-read

ii)

• The register renaming and out-of-order execution can be used to reduce the dependency in nearer instruction so as to increase the efficiency in pipelined execution.
• The given instruction set is:
  • R1 = R0 + R2
  • R3 = R4 + R5
  • R6 = R1 + R3
  • R0 = R2 + R7
• The resister R0 in the first instruction can be renamed as R1 since there is a write after read dependency between first and fourth instruction then reordering of third and fourth instruction can be done, the modified instruction set is shown below:
  • R1 = R1 + R2
  • R3 = R4 + R5
  • R0 = R2 + R7
  • R6 = R1 + R3
• The pipeline can be depicted as given below:

Instruction	1	2	3	4	5	6	7	8	9
R1 = R1 + R2	IF	II	OF	EX	WB	CO
R3 = R4 + R5		IF	II	OF	EX	WB	CO
R0 = R2 + R7			IF	II	OF	EX	WB	CO
R6 = R1 + R3				IF	II	OF	EX	WB	CO

Number of cycles required in the pipelined execution is 9.