Using Tomasulo\'s algorithm, fill in the table below to show the clock cycle on

Question

Using Tomasulo's algorithm, fill in the table below to show the clock cycle on which each instruction progresses through the corresponding functional unit. Start at clock cycle 0. For each of the instructions, write the RS identifier that the instruction issues to, write the sources (e.g., R2 if read from the register file, MDF1 if waiting on MDF1 's result), and the cycle in which the instruction issues, executes, writes-back its result, and commits. Instructions are in {dest, src, src} format except for branches and stores which are {src, src}; consider MUL.D, DIV.D, SUB.D, ADD.D as FP instructions. One instruction can issue (allocate) per cycle Reservation stations: Load/store unit (3), FP ADD(2), FP MD(2); call these ADF1-ADF2, MDF1-MDF2 There is one FP adder, one FP multiplier Functional units are not pipelined Latencies: FP ADD(3), FP MULF (5), FP DIV (10) Write Result and Exec occur in separate cycles (i.e., an instruction writes to the CDB in cycle n, and its dependent instruction starts execution in cycle n+1) There is a single CDB Loads and stores take 2 cycle in total An instruction stalls at issue if an appropriate reservation station (RS) is not available. It may issue in the cycle after the previous instruction writesback (i.e., if ADD.D X is stalled because all add RS's are occupied, and then one of the ADD.D's writes back on cycle n, then the ADD.D X can issue on cycle n+1) If more than one reservation station is available (e.g., ADF1 and ADF2), issue the instruction to the RS with the lower number (e.g., ADF1) If one instruction stalls at issue, the succeeding instructions also stall.

Explanation / Answer

Tamasulo's algorithm

Tomasulo's algorithm is another method of implementing dynamic scheduling. This scheme was invented by Robert Tomasulo, and was first used in the IBM 360/91. Tomasulo's algorithm differs from scoreboarding in that it uses register renaming to eliminate output and anti-dependences, i.e. WAW and WAR hazards. Output and anti-dependences are just name dependences, there is no actual data dependence

Instruction         Issue        Execute    writeback

L.D F6,44(R1)      0              1-2              3

MUL.D F4,F6,F2     1             4-8               9

DIV.D   F8,F4,F9        2             10-53          54

ADD.D F10,F8,F14 3 55-57 58

ADD.D F8,F22,F24 59 60-62 63

SUB.D F4,F20,F26 64    65-67    68

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.