Translate

Friday, January 4, 2013

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


No comments:

Post a Comment