【正文】 1 Y e s M U L T D M (A 2) R(F 4)M ul t 2 Y e s D IV D M (A 1) M ul t 1R e gis te r r e s ult s tat us :C loc k F0 F2 F4 F6 F8 F 10 F 12 ... F 309 FU M ul t 1 M (A 2) A dd2 (M M ) M ul t 22022/8/17 26 Tomasulo Example Cycle 10 I ns tr uc ti on s tat us : E xec W r i t eIns t ruc t i on j k Is s u e Co m p R es u l t Bu s y A d d res sLD F6 34+ R2 1 3 4 L oa d1 NoLD F2 45+ R3 2 4 5 L oa d2 NoM U L T D F0 F2 F4 3 L oa d3 NoS U BD F8 F6 F2 4 7 8D IV D F 10 F0 F6 5ADDD F6 F8 F2 6 10R e s e r v ati on Stat ions : S1 S2 RS RST i m e Nam e Busy Op Vj Vk Qj QkA dd1 No0 A dd2 Y e s ADDD (M M ) M (A 2)A dd3 No5 M ul t 1 Y e s M U L T D M (A 2) R(F 4)M ul t 2 Y e s D IV D M (A 1) M ul t 1R e gis te r r e s ult s tat us :C loc k F0 F2 F4 F6 F8 F 10 F 12 ... F 3010 FU M ul t 1 M (A 2) A dd2 (M M ) M ul t 2? Add2 (ADDD) pleting。 each instruction has other operand, then instructions can be released simultaneously by broadcast on CDB – If a centralized register file were used, the units would have to read their results from the registers when register buses are available 2. Elimination of stalls for WAW and WAR hazards HardwareBased Speculation ? Problem – A wide issue processor may need to execute a branch every clock cycle to maintain maximum performance. ? just predicting branches accurately may not be sufficient to generate the desired amount of ILP ? Solution – speculating on the oute of branches and executing the program as if our guesses were correct ? fetch, issue, and execute instructions, as if branch predictions were always correct – Provide mechanisms to handle the situation where the speculation is incorrect. HardwareBased Speculation ? 3 key ideas – dynamic branch prediction ? to choose which instructions to execute – speculation ? to allow the execution of instructions before the control dependences are resolved ? with the ability to undo the effects of an incorrectly speculated sequence – dynamic scheduling ? to deal with the scheduling of different binations of basic blocks. HardwareBased Speculation ? Tomasulo’s algorithm can be extended to support speculation – separate the bypassing of results among instructions from the actual pletion of an instruction – allow an instruction to execute and to bypass its results to other instructions ? without allowing the instruction to perform any updates that cannot be undone ? Instructions using speculated results bee speculative – When an instruction is no longer speculative, we allow it to update the register file or memory ? instruction mit HardwareBased Speculation ? The key idea – allow instructions to execute out of order but to force them to mit in order – prevent any irrevocable action until an instruction mits 阻止任何不可更改的活動直到指令提交 ? such as updating state or taking an exception – separate the process of pleting execution from instruction mit 把完成執(zhí)行與指令提交分開 ? an additional set of hardware buffers that hold the results of instructions before being mitted ? reorder buffer (ROB) – a source of operands for instructions – supplies operands in the interval between pletion of instruction execution and instruction mit. HardwareBased Speculation ? ROB – A circular buffer ? Entries allocated and deallocated by two revolving pointers – Entries allocated to each instruction ? Strictly in program order ? Keeps track of the execution status of the instruction HardwareBased Speculation ? ROB fields – instruction type ? opcode – branch (has no destination result) – store (has a memory address destination) – register operation (has register destinations). – destination ? the register number or the memory address – value ? Instruction result – Ready ? The value is ready – Address ? For load/store operation ? ROB replaces the store buffer ROB[ ].Instruction ROB[ ].Dest ROB[ ].Value ROB[ ].Ready type dest value ready ROB[ ].A HardwareBased Speculation ? Register fields – Busy ? RegisterState[ ].Busy – Reorder ? RegisterState[ ].Reorder ? Instruction sequence number – Qi ? RegisterState[ ].Qi – Value ? RegisterState[ ].Value Busy reorder Qi Value HardwareBased Speculation ? 4 steps – Issue – Execute – Write result – Commit HardwareBased Speculation ? 4 steps – Issue ? If there is an empty station and empty slot in the ROB – Mark the reservation station and ROB as busy ? Send the operands to the reservation station if they are available in the register or ROB – Execute – Write result ? Write result on the CDB and from CDB into the ROB ? Mark the reservation station as empty – Commit ? When an instruction reaches the head of the ROB ? Mark the ROB as empty ? When the instruction is a branch with incorrect prediction, indicate the speculation was wrong – The ROB is flu