Using Tomasulo’s algorithm, for each instruction in the following sequence determine when (in which cycle, counting from the start) it issues, begins execution, and writes its result to the CDB. Assume that the result of an instruction can be written in the cycle after it finishes its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that. The execution time of all instructions is two cycles, except for multiplication (which takes 4 cycles) and division (which takes 8 cycles). The processor has one multiply/divide unit and one add/subtract unit. The multiply/divide unit has two reservation stations and the add/subtract unit has four reservation stations. None of the execution units is pipelined – each can only be executing one instruction at a time. If a conflict for the use of an execution unit occurs when selecting which instruction should start to execute, the older instruction (the one that appears earlier in program order) has priority. If a conflict for use of the CBD occurs, the result of the add/subtract unit has priority over the result of the multiply/divide unit. Assume that at start all instructions are already in the instruction queue, but none has yet been issued to any reservation stations. The processor can issue only one instruction per cycle, and there is only one CDB for writing results.
In this problem, we consider the same processor described above but add an 8-entry reorder buffer (ROB). Assume that no more than one instruction can be committed in each cycle. Also assume that an instruction that writes its result in cycle X can only commit in cycle X+1 or later, that reservation stations are freed as soon as possible in a processor with an ROB, and that a resource freed in cycle Y can be reused in cycle Y+1.
For each instruction in the following sequence, determine when it issues, executes, writes result, and commits:
I1-I4 issue, execute, and write results exactly as we did in Problem 2. However, now we can free a RS as soon as the instruction starts executing and reuse it in the cycle after that. As a result, a MUL/DIV RS is freed by I1 in cycle 2 and I5 can issue in cycle 5, and I6 and I7 can issue in cycles 6 and 7, respectively. These instructions then execute and write results in the same cycles they did in Problem 2. In cycle 8 we can issue I8, because by that time we again have a free MUL/DIV RS (I2 freed its unit in cycle 6). Commit proceeds according to its simple rules – an instruction can commit after it has written its result and after the previous instruction has committed. Therefore, we commit I1 in cycle 6 (after writing its result in cycle 5), I2 in cycle 14 (write its result in 13), I3 in 15 (after I2 is committed), I4 in 16 (after I3 is committed), I5 in 22 (write result in 21), etc. In cycles 9 we can issue I9, because we have a free ADD/SUB RS (only I6 and I8 are using ADD/SUB RS entries in cycle 9) and a free ROB entry (instructions I2-I8 are using 7 of the eight ROB entries). In cycle 10, when we attempt to issue I10, there is a free RS but all eight ROB entries are in use. We get a free ROB entry only after I2 commits in cycle 14, so I10 can issue in cycle 15. Because I10 does not depend on any of the previous instructions, it can execute in cycle 16 (the ADD/SUB unit is free then, because I6 has just finished execution) and write its result in cycle 17.