⭐ Dynamic Pipelines: Dynamic Scheduling

1. Definition

Dynamic scheduling is a hardware technique used in pipelined processors to reorder instructions at runtime to maximize instruction-level parallelism (ILP) while avoiding hazards.

Unlike static scheduling (done by the compiler), dynamic scheduling is performed by the hardware at execution time, allowing instructions to execute out of program order as long as data dependencies are respected.

Dynamic pipelines rely on hardware mechanisms to track hazards and ensure precise exceptions.

2. Purpose of Dynamic Scheduling

1. Minimize pipeline stalls caused by:

   • Data hazards (RAW, WAR, WAW)
   • Control hazards (branches)

2. Exploit instruction-level parallelism (ILP) beyond what static scheduling can achieve.

3. Support out-of-order execution while maintaining program correctness.

3. Key Concepts

a) Instruction Window / Reservation Stations

• Hardware buffer where instructions wait until operands are ready.
• Enables out-of-order execution when instructions are not dependent.

b) Register Renaming

• Prevents name dependencies (WAR and WAW hazards) by assigning physical registers instead of program registers.

c) Reorder Buffer (ROB)

• Ensures precise exceptions: instructions can execute out-of-order, but results are committed in program order.

d) Scoreboarding

• Hardware technique to track resource usage and data dependencies to decide when an instruction can execute.
• Used in some dynamic scheduling designs (e.g., early CDC and IBM machines).

e) Tomasulo’s Algorithm

• Famous dynamic scheduling algorithm that uses:

  • Reservation stations for instruction buffering
  • Common data bus (CDB) for result forwarding
  • Register renaming to avoid false dependencies

4. Example

Consider the following instructions:

I1: R1 = R2 + R3
I2: R4 = R1 + R5
I3: R6 = R7 + R8

• Static scheduling: I2 must wait for I1 to complete → pipeline stalls.
• Dynamic scheduling: I3 can execute before I2, since it does not depend on I1 → pipeline stays busy.

Pipeline Execution Order (dynamic):

Cycle 1: I1 fetch
Cycle 2: I1 execute, I3 fetch
Cycle 3: I3 execute, I2 waits (R1 not ready)
Cycle 4: I2 execute (after R1 ready)

Dynamic scheduling reduces idle cycles by reordering instructions on the fly.

5. Advantages

1. Reduces pipeline stalls → higher throughput.
2. Supports out-of-order execution safely.
3. Automatically adapts to runtime conditions (cache misses, branch outcomes, etc.).
4. Maximizes instruction-level parallelism (ILP) without relying solely on compiler optimizations.

6. Limitations

1. Hardware complexity:

   • Needs reservation stations, reorder buffer, register renaming, forwarding paths.

2. Power and area overhead in CPU design.

3. Precise exception handling is more complex.

7. Dynamic vs. Static Scheduling

8. Exam Summary

• Dynamic Scheduling: Hardware reorders instructions at runtime to exploit ILP while avoiding hazards.

• Mechanisms include:

  1. Reservation stations (instruction buffering)
  2. Register renaming (avoid false dependencies)
  3. Reorder buffer (precise exceptions)
  4. Forwarding and scoreboarding

• Goal: Keep pipelines busy, reduce stalls, support out-of-order execution.