3. Tomasulo's Algorithm (Reverse Engineering) In this problem, we will give you the state of the Register Alias Table (RAT) and Reservation Stations (RS) for an out-of-order execution engine that employs Tomasulo's algorithm, as we discussed in lectures. Your job is to determine the original sequence of four instructions in program order. The out-of-order machine in this problem behaves as follows: The frontend of the machine has a one-cycle fetch stage and a one-cycle decode stage. The machine can fetch one instruction per cycle, and can decode one instruction per cycle. The machine executes only register-type instructions, e.g., OP Rdest - Rre, Rr42. The machine dispatches one instruction per cycle into the reservation stations, in program order. Dispatch occurs during the decode stage. . An instruction always allocates the first reservation station that is available in top-to-bottom order) at the required functional unit. When an instruction in a reservation station finishes executing, the reservation station is cleared. The adder and multiplier are not pipelined. An add operation takes 2 cycles. A multiply operation takes 3 cycles. The result of an addition and multiplication is broadcast to the reservation station entries and the RAT in the writeback stage. A dependent instruction can begin execution in the next cycle after the writeback if it has all of its operands available in the reservation station entry. When multiple instructions are ready to execute at a functional unit at the same cycle, the oldest ready instruction is chosen to be executed first. Initially, the machine is empty. Four instructions then are fetched, decoded, and dispatched into reser- vation stations. Pictured below is the state of the machine when the final instruction has been dispatched into a reservation station: RAT Reg Tag Value RO R1 0 A R2 1 R30 E R4 0 B R5 1001 II - ID V Tag Value | V| Tag Value A OD 1 8 BO A 0 A c ID V Tag Value D1 - 5 EO A F - Tag Value 1 5 0 B - ' + (a) Give the four instructions that have been dispatched into the machine, in program order. The source registers for the first instruction can be specified in either order. Give instructions in the following format: "opcode destination = sourcel, source:2." (40 points) 11 1t 1 1 (b) Now assume that the machine flushes all instructions out of the pipeline and restarts fetch from the first instruction in the sequence above. Show the full pipeline timing diagram below for the sequence of four instructions that you determined above, from the fetch of the first instruction to the writeback of the last instruction. Assume that the machine stops fetching instructions after the fourth instruction. As we saw in lectures, use "F* for fetch, "D" for decode, En" to signify the nth cycle of execution for an instruction, and "W" to signify writeback. You may or may not need all columns shown. (40 points) Cycle: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 15 16 17 18 Inst.: Inst.: Inst.: Inst.: Inst. (c) Finally, show the state of the RAT and reservation stations at the end of the 12th cycle of execution in the figure below. Complete all blank parts. (40 points) RAT Reg v Tag Value RO R1 R2 R3 R4 R5 IDV Tag Value | V| Tag Value D IDV Tag Value | V| Tag Value A B E F + 3. Tomasulo's Algorithm (Reverse Engineering) In this problem, we will give you the state of the Register Alias Table (RAT) and Reservation Stations (RS) for an out-of-order execution engine that employs Tomasulo's algorithm, as we discussed in lectures. Your job is to determine the original sequence of four instructions in program order. The out-of-order machine in this problem behaves as follows: The frontend of the machine has a one-cycle fetch stage and a one-cycle decode stage. The machine can fetch one instruction per cycle, and can decode one instruction per cycle. The machine executes only register-type instructions, e.g., OP Rdest - Rre, Rr42. The machine dispatches one instruction per cycle into the reservation stations, in program order. Dispatch occurs during the decode stage. . An instruction always allocates the first reservation station that is available in top-to-bottom order) at the required functional unit. When an instruction in a reservation station finishes executing, the reservation station is cleared. The adder and multiplier are not pipelined. An add operation takes 2 cycles. A multiply operation takes 3 cycles. The result of an addition and multiplication is broadcast to the reservation station entries and the RAT in the writeback stage. A dependent instruction can begin execution in the next cycle after the writeback if it has all of its operands available in the reservation station entry. When multiple instructions are ready to execute at a functional unit at the same cycle, the oldest ready instruction is chosen to be executed first. Initially, the machine is empty. Four instructions then are fetched, decoded, and dispatched into reser- vation stations. Pictured below is the state of the machine when the final instruction has been dispatched into a reservation station: RAT Reg Tag Value RO R1 0 A R2 1 R30 E R4 0 B R5 1001 II - ID V Tag Value | V| Tag Value A OD 1 8 BO A 0 A c ID V Tag Value D1 - 5 EO A F - Tag Value 1 5 0 B - ' + (a) Give the four instructions that have been dispatched into the machine, in program order. The source registers for the first instruction can be specified in either order. Give instructions in the following format: "opcode destination = sourcel, source:2." (40 points) 11 1t 1 1 (b) Now assume that the machine flushes all instructions out of the pipeline and restarts fetch from the first instruction in the sequence above. Show the full pipeline timing diagram below for the sequence of four instructions that you determined above, from the fetch of the first instruction to the writeback of the last instruction. Assume that the machine stops fetching instructions after the fourth instruction. As we saw in lectures, use "F* for fetch, "D" for decode, En" to signify the nth cycle of execution for an instruction, and "W" to signify writeback. You may or may not need all columns shown. (40 points) Cycle: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 15 16 17 18 Inst.: Inst.: Inst.: Inst.: Inst. (c) Finally, show the state of the RAT and reservation stations at the end of the 12th cycle of execution in the figure below. Complete all blank parts. (40 points) RAT Reg v Tag Value RO R1 R2 R3 R4 R5 IDV Tag Value | V| Tag Value D IDV Tag Value | V| Tag Value A B E F +