Tomasulo algorithm exercises with answer
Answers
Answered by
0
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.
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.
Similar questions