ROB/Problem 3 & 4

A processor with dynamic scheduling and issue bound operand fetch (operands are fetched during instruction issue) has 3 execution units { one LOAD/STORE unit, one ADD/SUB unit and one MUL/DIV unit. } It has a reservation station with 1 slot per execution unit and a single register file.

Starting with the following instruction sequence in the instruction fetch buffer and empty reservation stations, Determine for each instruction the cycle in which it will be issued and the cycle in which it will write result.

Screen Shot 2014-04-16 at 4.16.14 PM.png

Assumptions: out of order issue, out of order execution, 4 stage pipeline (instruction fetch, decode and issue, execute, and write back), no data forwarding, and succinct instruction window size. Execute cycles taken by different instructions are:

LOAD/STORE: 2
ADD/SUB: 1
MUL: 2
DIV: 4

This problem was adapted from: "Exercises for Computer Architecture", Anders Ardo, Lund University

Solution

The following chart shows the execution of the given instruction sequence cycle by cycle.

The stages of instruction execution:

F Instruction fetch

D Decode and issue

E1 Execute in LOAD/STORE unit

E2 Execute in ADD/SUB unit

E3 Execute in MUL/DIV unit

W Write back into register file and reservation stations

Instruction 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   LOAD R6, 34(R12) F D E1 E1 W
    LOAD R2, 45(R13) F r r r D E1 E1 W
    MUL R0, R2, R4 F D s s s s s s E3 E3 W
    SUB R8, R2, R6 F D s s s s s s E2 W
    DIV R10, R0, R6 F r r r r r r r r r D E3 E3 E3 E3 W
    ADD R6, R8, R2 F r r r r r r r r D E2 W

Cycles in which an instruction is waiting for a reservation station are marked as 'r' and the cycles in which an instruction is waiting for one or more operands are marked as 's'.

As seen in the time chart, the issue and write back cycles for various instructions are:

Screen Shot 2014-04-16 at 4.21.52 PM.png