2. (20 pts) Consider a system employing Tomasulo's dynamic scheduling. Issue: issue only if RS is available; get an instruction from the instruction stack as well as read available operands. At an issue stage, if not all operands are available, stall and wait for operands on CDB. When operands are broadcast on CDB, grab them. When a reservation station obtains its last operand value, it can begin execution on the next cycle. Execute: If all operands are read, begin execution at the next cycle. Reservation stations are deallocated during the result writing cycle and can be reassigned on the following cycle. The floating point functional units are pipelined and can begin a new instruction every clock cycle. The Integer (load/store), FPAdd and FPMult units each have two reservation stations while FPDiv has only one reservation station. The functional unit latencies are FPAdd = 8, FPMult = 5, FPDiv = 10 execution cycles. (These latencies do not include writing the results to reservation stations and/or registers.) Reservation stations are deallocated during the result writing cycle and can be reassigned on the following cycle. Deallocated but not reassigned reservation stations should be indicated with null (empty) fields, denoted by "-". Initial Register File status FO F1 F2 F3 F4F5F6F7F8 Register Producer Value 10 15 20 25 30 35 40 8 0 Current Instruction status Results Written? I1: 12: 13: 14: Instruction DIVF F1,F2.FO MULTF F3,F4,F3 ADDF F1,F3.F1 SUBF F7.F6,F7 Issued? Exec. Complete? TN Y Y Y N Y N Reservation Station status FU# Busy? OperValue 1 Value 2 Producer 1 Producer 2 Add1 Add2 Mult1 Mult2 Div1 (a) [11 pts) Assume that instructions 1-4 have issued and instruction 2 has completed execution and has broadcast its results. No other instruction has completed execution. Fill in the register file status and reservation station status that would be consistent with this state. Current Register File status FO F1 F2 F3 F4F5 F6 F7F8 Register Producer Value Current Reservation Station status Busy? Oper Value 1 Value 2 Producer 1 Producer 2 Addi Add2 Mult 1 Mult2 Divl (b) Fill in the table below with the following information: (6-1) [3 pts) Suppose that instruction 1 issued in cycle 1. In which order does each of the remaining instructions issue? For any instructions whose issue is stalled, briefly explain why they are stalled below the table. (b-2) [3 pts] What is the order in which the instructions complete execution? (6-3) [3 pts] Which instructions will write their results to the register file throughout all the executions? Instruction Order in which instructions are Order of execution completion (e.g., 1, 2nd, 3rd) Are instruction's results written to the register file? issued? Il: DIVF F1,F2,FO 12: MULTF F3.F4,F3 13: 14: ADDF F1,F3,F5 SUBF F7,F6,F7 Cycles Inst 1 2 (1) IRE 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (3) Explanation of any instruction issue stalls: 2. (20 pts) Consider a system employing Tomasulo's dynamic scheduling. Issue: issue only if RS is available; get an instruction from the instruction stack as well as read available operands. At an issue stage, if not all operands are available, stall and wait for operands on CDB. When operands are broadcast on CDB, grab them. When a reservation station obtains its last operand value, it can begin execution on the next cycle. Execute: If all operands are read, begin execution at the next cycle. Reservation stations are deallocated during the result writing cycle and can be reassigned on the following cycle. The floating point functional units are pipelined and can begin a new instruction every clock cycle. The Integer (load/store), FPAdd and FPMult units each have two reservation stations while FPDiv has only one reservation station. The functional unit latencies are FPAdd = 8, FPMult = 5, FPDiv = 10 execution cycles. (These latencies do not include writing the results to reservation stations and/or registers.) Reservation stations are deallocated during the result writing cycle and can be reassigned on the following cycle. Deallocated but not reassigned reservation stations should be indicated with null (empty) fields, denoted by "-". Initial Register File status FO F1 F2 F3 F4F5F6F7F8 Register Producer Value 10 15 20 25 30 35 40 8 0 Current Instruction status Results Written? I1: 12: 13: 14: Instruction DIVF F1,F2.FO MULTF F3,F4,F3 ADDF F1,F3.F1 SUBF F7.F6,F7 Issued? Exec. Complete? TN Y Y Y N Y N Reservation Station status FU# Busy? OperValue 1 Value 2 Producer 1 Producer 2 Add1 Add2 Mult1 Mult2 Div1 (a) [11 pts) Assume that instructions 1-4 have issued and instruction 2 has completed execution and has broadcast its results. No other instruction has completed execution. Fill in the register file status and reservation station status that would be consistent with this state. Current Register File status FO F1 F2 F3 F4F5 F6 F7F8 Register Producer Value Current Reservation Station status Busy? Oper Value 1 Value 2 Producer 1 Producer 2 Addi Add2 Mult 1 Mult2 Divl (b) Fill in the table below with the following information: (6-1) [3 pts) Suppose that instruction 1 issued in cycle 1. In which order does each of the remaining instructions issue? For any instructions whose issue is stalled, briefly explain why they are stalled below the table. (b-2) [3 pts] What is the order in which the instructions complete execution? (6-3) [3 pts] Which instructions will write their results to the register file throughout all the executions? Instruction Order in which instructions are Order of execution completion (e.g., 1, 2nd, 3rd) Are instruction's results written to the register file? issued? Il: DIVF F1,F2,FO 12: MULTF F3.F4,F3 13: 14: ADDF F1,F3,F5 SUBF F7,F6,F7 Cycles Inst 1 2 (1) IRE 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (3) Explanation of any instruction issue stalls
