Problem 1: Tomasulo's algorithm (38 points)

This exercise examines Tomasulos algorithm on a simple loop operation. Consider the following code fragment:

LOOP: L.D F2, 0(R1)

L.D F4, 8(R1)

DIV.D F6, F2, F4

MUL.D F8, F6, F6

ADD.D F6, F2, F4

MUL.D F10, F6, F6

S.D F8, 0(R1)

S.D F10, 8(R1)

DADDI R1, R1, 16

BNEZ R1, LOOP

1. The pipeline functional units are described by the following table: FU type Cycles in EX #of FUs # of Reservation Stations Integer 1 1 5 FP add/subtract 4 1 4 FP multiply/divide 15 2 4

2. Functional units are NOT pipelined (i.e., if one instruction is using the functional unit, another instruction cannot enter it).

3. All stages except EX take one cycle to complete.

4. There is no forwarding between functional units. Both integer and floating point results are communicated through the CDB.

5. Memory accesses use the integer functional unit to perform effective address calculation..

6. There is an infinite instruction queue. Loads and stores use integer reservation stations.

7. Loads and stores take one cycle to execute. Loads and stores share a memory access unit.

8. If an instruction finishes execution in cycle x, then another instruction that is waiting on the same functional unit (due to a structural hazard) can begin execution in cycle x+1.

9. There is only 1 CDB. So, only one instruction can write to the CDB in a clock cycle.

10. Branches and stores do not need the CDB since they dont have WR stage.

11. Whenever there is a conflict for a functional unit or the CDB, assume program order.

12. When an instruction is done executing in its functional unit and is waiting for the CDB, it is still occupying its reservation station. (meaning no other instruction may use the same reservation station). If the instruction broadcasts in CDB in cycle x, then its reservation station will be available in cycle x+1. For a store, its reservation station will be available in cycle x+1 if the store writes to memory in cycle x.

13. Treat the BNEZ instruction as an Integer instruction. Assume L.D instruction after the BNEZ can be issued the cycle after BNEZ instruction is issued due to branch prediction.

14. Initially, R1

The reservation station used by each instruction. This should include both the functional unit type and the number of the reservation station. If multiple reservation stations of a particular type are available, associate early program order with lower cardinality.

EXE Reservation Station ISSUE Instruction Begin-End L.D F2,0(RI) Integer l L.D F4, 8(RI) DIV.D F6, F2,F4 MUL. D F8,F6, F6 ADD. D F6,F2,F4 MUL.D F10, F6,F6 S.D F10, S.D 8(R) DADDI R1 R1.16 BNEZ RI LOOP D F2.0 (RI) I D F4, 80 RI) DIV.D F6, F2,F4 MUL. D F8,F6,F6 ADD D F6,F2,F4 MUL.D F100 F6,F6 S.D S.D F 10 8(R) DADDI RI,R1,16 BNEZ RI, LOOP Table 1. Execution profile using Tomasulo's algorithm Mem Access CDB Write EXE Reservation Station ISSUE Instruction Begin-End L.D F2,0(RI) Integer l L.D F4, 8(RI) DIV.D F6, F2,F4 MUL. D F8,F6, F6 ADD. D F6,F2,F4 MUL.D F10, F6,F6 S.D F10, S.D 8(R) DADDI R1 R1.16 BNEZ RI LOOP D F2.0 (RI) I D F4, 80 RI) DIV.D F6, F2,F4 MUL. D F8,F6,F6 ADD D F6,F2,F4 MUL.D F100 F6,F6 S.D S.D F 10 8(R) DADDI RI,R1,16 BNEZ RI, LOOP Table 1. Execution profile using Tomasulo's algorithm Mem Access CDB Write