5. Out-of-Order Execution - Reverse Engineering (II) A five instruction sequence executes according to Tomasulo's algorithm. Each instruction is of the form ADD DR.SR1,SR2 or MUL DR.SR1, SR2. ADDs are pipelined and take 9 cycles (F-D-E1-E2-E3-E4-E5-E6-WB). MULs are also pipelined and take 11 cycles (two extra execute stages). An instruction must wait until a result is in a register before it sources it (reads it as a source operand). For instance, if instruction 2 has a read-after-write dependence on instruction 1, instruction 2 can start executing in the next cycle after instruction 1 writes back (shown below). instruction 1 |FD|E1|E2|E3|..... | WB | instruction 2 |F|D |- |- ..... |- |E1| The machine can fetch one instruction per cycle, and can decode one instruction per cycle. The register file before and after the sequence are shown below. Valid Tag Value Tag 1 1 1 1 RO RI R2 R3 R4 R5 R6 R7 DI Valid 1 1 1 1 1 RO RI R2 R3 R4 R5 R6 R7 5 6 7 8 9 10 11 Value 310 5 410 31 8 9 10 21 1 1 1 1 17 1 1 1 (a) Complete the five instruction sequence in program order in the space below. Note that we have helped you by giving you the opcode and two source operand addresses for the fourth instruction. (The program sequence is unique.) Give instructions in the following format: "opcode destination sourcel, source2." (50 points) = MUL R6 R6 (b) In each cycle, a single instruction is fetched and a single instruction is decoded. Assume the reservation stations are all initially empty. Put each instruction into the next available reservation station. For example, the first ADD goes into "a". The first MUL goes into "x". Instructions remain in the reservation stations until they are completed. Show the state of the reservation stations at the end of cycle 8. (50 points) Note: to make it easier for the grader, when allocating source registers to reservation stations, please always have the higher numbered register be assigned to source2. b N X (c) Show the state of the Register Alias Table (Valid, Tag, Value) at the end of cycle 8. (50 points) Valid Tag Value RO RI R2 R3 R4 R5 R6 R7 5. Out-of-Order Execution - Reverse Engineering (II) A five instruction sequence executes according to Tomasulo's algorithm. Each instruction is of the form ADD DR.SR1,SR2 or MUL DR.SR1, SR2. ADDs are pipelined and take 9 cycles (F-D-E1-E2-E3-E4-E5-E6-WB). MULs are also pipelined and take 11 cycles (two extra execute stages). An instruction must wait until a result is in a register before it sources it (reads it as a source operand). For instance, if instruction 2 has a read-after-write dependence on instruction 1, instruction 2 can start executing in the next cycle after instruction 1 writes back (shown below). instruction 1 |FD|E1|E2|E3|..... | WB | instruction 2 |F|D |- |- ..... |- |E1| The machine can fetch one instruction per cycle, and can decode one instruction per cycle. The register file before and after the sequence are shown below. Valid Tag Value Tag 1 1 1 1 RO RI R2 R3 R4 R5 R6 R7 DI Valid 1 1 1 1 1 RO RI R2 R3 R4 R5 R6 R7 5 6 7 8 9 10 11 Value 310 5 410 31 8 9 10 21 1 1 1 1 17 1 1 1 (a) Complete the five instruction sequence in program order in the space below. Note that we have helped you by giving you the opcode and two source operand addresses for the fourth instruction. (The program sequence is unique.) Give instructions in the following format: "opcode destination sourcel, source2." (50 points) = MUL R6 R6 (b) In each cycle, a single instruction is fetched and a single instruction is decoded. Assume the reservation stations are all initially empty. Put each instruction into the next available reservation station. For example, the first ADD goes into "a". The first MUL goes into "x". Instructions remain in the reservation stations until they are completed. Show the state of the reservation stations at the end of cycle 8. (50 points) Note: to make it easier for the grader, when allocating source registers to reservation stations, please always have the higher numbered register be assigned to source2. b N X (c) Show the state of the Register Alias Table (Valid, Tag, Value) at the end of cycle 8. (50 points) Valid Tag Value RO RI R2 R3 R4 R5 R6 R7