The following question may not be related to the content of math stack exchange, however; I fiercely believe that math is the mother of all sciences and not philosophy like many people claim, so I think that people from math stack exchange can help me solve this problem because of their open mindedness, kindness and knowledge.
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. Your job is to determine the original sequence of the following five instructions in program order.
ADD R3, R10, R3
MUL R1, R1, R10
MUL R11, R7, R9
ADD R1, R2, R3
ADD R5, R1, R11
ADD R7, R2, R6
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 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 a value is captured (at a reservation station) or written back (to a register) in this machine, the old tag that was previously at that location is not cleared; only the valid bit is set.
● When an instruction in a reservation station finishes executing, the reservation station is cleared.
● Both the adder and multiplier are fully pipelined. Add instructions take 4 cycles. Multiply instructions take 6 cycles.
● When an instruction completes execution, it broadcasts its result, and dependent instructions can begin execution in the next cycle if they have all operands available.
● When multiple instructions are ready to execute at a functional unit, the oldest ready instruction is chosen.
Initially, the machine is empty. Six instructions then are fetched, decoded, and dispatched into reservation stations, before any instruction executes. Then, one instruction completes execution. Here is the state of the machine at this point, after the single instruction completes:
I have been working on this problem for 6 hours, but I still can't understand clearly tomasulo's algorithm.
For the first question, I guess somehow I have to find out what the right order is. For the first instruction, it looks like I have to backtrack along the way, but I still don't see how to tackle it.