Dynamic Scheduling

•         Dynamic scheduling - hardware rearranges the instruction execution to reduce stalls while maintaining data flow and exception behavior •         It handles cases when dependences unknown at compile time •         it allows the processor to tolerate unpredictable delays such as cache misses, by executing other code while waiting for the miss to resolve •         It allows code that compiled for one pipeline to run efficiently on a different pipeline •         It simplifies the compiler •         Key idea: Allow instructions behind stall to proceed             DIVD  F0,F2,F4             ADDD            F10,F0,FF12,F8,F14 •         Enables out-of-order execution and allows out-of-order completion (e.g., SUBD) –        In a dynamically scheduled pipeline, all instructions still pass through issue stage in order (in-order issue) •         Will distinguish when an instruction begins execution and when it completes execution; between 2 times, the instruction is in execution •         Note: Dynamic execution creates WAR and WAW hazards and makes exceptions harder Tomasulo Algorithm •         Control & buffers distributed with Function Units (FU) –        FU buffers called “reservation stations”; have pending operands •         Registers in instructions replaced by values or pointers to reservation stations(RS); called  register renaming ; –        Renaming avoids WAR, WAW hazards –        More reservation stations than registers, so can do optimizations compilers can’t •         Results to FU from RS, not through registers, over Common Data Bus that broadcasts results to all FUs –        Avoids RAW hazards by executing an instruction only when its operands are available •         Load and Stores treated as FUs with RSs as well •         Integer instructions can go past branches (predict taken), allowing FP ops beyond basic block in FP queue 1.         Issue—get instruction from FP Op Queue             If reservation station free (no structural hazard), control issues instr & sends operands (renames registers). 2.         Execute—operate on operands (EX)             When both operands ready then execute;  if not ready, watch Common Data Bus for result 3.         Write result—finish execution (WB)             Write on Common Data Bus to all awaiting units; mark reservation station available •         Normal data bus: data + destination (“go to” bus) •         Common data bus: data + source  (“come from” bus) –        64 bits of data + 4 bits of Functional Unit  source address –        Write if matches expected Functional Unit (produces result) –        Does the broadcast