Computer Architecture
Dynamic Scheduling
Dynamic Scheduling-Instruction Level parallelism
• Rearrange execution order of instructions to reduce stalls while
maintaining data flow
Advantages:
• Compiler doesn’t need to have knowledge of micro architecture
• Handles cases where dependencies are unknown at compile time
Disadvantages:
Substantial increase in hardware complexity
Complicates exceptions
How dynamic scheduling works?
Limitations of simple pipelining:
• In order instruction issue and execution.
• Instructions are issued(giving the operands of the instructions to the
functional unit) in program order.
• If an instruction is stalled in the pipeline, no later instruction can
proceed.
If instruction j depends on a long-running instruction I, currently in
execution in the pipeline, then all instructions after j must be stalled
until I is finished and j can execute.
How dynamic scheduling works?
Separate the issue process into two parts:
• Checking for any structural hazards.
• Waiting for the absence of a data hazards.
Use in-order instruction issue but we want an instruction to begin
execution as soon as its data operands are available.
out-of –order execution -> out-of-order completion.
Ooo execution introduces the possibilities of WAR and WAW hazards.
How dynamic scheduling works?
• DIV F1, F2, F3
• ADD F4, F1, F5
• SUB F6, F7, F8
• MUL F9, F10, F4
[Link] and WAW hazards remove: by register renaming
[Link] of imprecise exception:
The pipeline may have already completed instruction that are later in
program order than the instruction causing the exception.
The pipeline may have not yet completed some instructions that are
earlier in program order than instruction causing the exception.
How dynamic scheduling works?
• To allow out-of-order execution, split the ID stage into two:
• Issues: decode the instructions, and check for structural hazards.
• Read operands: wait until no data hazards, then read operands.
• In a dynamically scheduled pipeline, all instructions pass through the
issue stage in order (in-order issue); however, they cab be stalled or
bypassed each other in the second stage (read operands) and thus
enter execution out of order.
Done by – score boarding technique
Approach used: Tomasulo’s algorithms
Register Renaming
Register renaming is done by reservation stations (RS) (set of buffer
with operational unit)
Each RS contains:
• The instruction (operation to be done)
• Buffered operand values (when available)
• Reservation station number of instruction providing the operand
values
RS fetches and buffered an operand as soon as it becomes available (no
necessarily involving register file)
The pending instruction designate the RS that will provide input.
The result values broadcast on the common data bus (CDB)
Dynamic Scheduling- Tomasulo
Dynamic Scheduling- Tomasulo
Issues:
• Get next instruction from FIFO queue.
• If RS available, issue the instruction to the RS with operand values if
available.
• If operand values are not available, stall the instruction
Dynamic Scheduling- Tomasulo
• Execute:
• When operand becomes available, store it in any reservation stations
waiting for it
• When all operands are ready, execute the instructions
• Loads and store uses buffers
• No instruction will initiate execution until all branches that precede it
in program order have completed
Dynamic Scheduling- Tomasulo
• Write result:
• Write results into CDB (there by it reaches the reservation station,
store buffer and register file) with name of execution until that
generated the result.
• Stores must wait until address and value are recieved
Tomasulo’s Algorithm
• Load and store buffers contain data and address.
• They also act like RS