⭐ Static Scheduling

Definition

Static scheduling is a technique where the compiler, not the hardware, determines the order in which instructions are executed to avoid pipeline hazards and improve performance.

In static scheduling, decisions about instruction reordering, pipeline hazard handling, and parallelism are made before runtime, during compile time.

The compiler schedules instructions so the pipeline can execute efficiently without needing complex hardware.

Static scheduling is used extensively in RISC architectures (such as MIPS, ARM, and RISC-V).

---

⭐ Why Static Scheduling Is Used

• To reduce pipeline stalls
• To improve instruction-level parallelism (ILP)
• To simplify hardware (no need for expensive out-of-order logic)
• To achieve near one-instruction-per-cycle performance
• To handle RAW hazards using compiler reordering instead of hardware stalling

Hardware becomes simpler, and the compiler takes over hazard avoidance.

---

⭐ How Static Scheduling Works

The compiler analyzes the program and identifies:

• Data dependencies
• Control dependencies
• Resource conflicts
• Instruction latencies (e.g., load delays, FP operations)

Then the compiler reorders instructions so that long-latency operations (like loads) have enough time to complete before their results are needed.

General approach:

1. Detect pipeline hazards
2. Reorder independent instructions
3. Insert NOPs (only if reordering is not possible)
4. Generate scheduled instruction sequence

---

⭐ Static Scheduling Example (Load Delay Slot)

Suppose we have:

I1: LW R1, 0(R2)
I2: ADD R3, R1, R4   ; depends on R1

Without scheduling, ADD will stall waiting for the load result.

With Static Scheduling (Compiler reorders):

I1: LW R1, 0(R2)
I3: SUB R5, R6, R7   ; independent instruction placed here
I2: ADD R3, R1, R4

This eliminates the stall by inserting useful work.

---

⭐ When No Independent Instruction Is Available

The compiler may insert a NOP (No Operation):

LW R1, 0(R2)
NOP
ADD R3, R1, R4

This avoids hazard but wastes a cycle. Still, the decision is made statically, at compile time.

---

⭐ Types of Hazards Managed by Static Scheduling

✔ RAW hazards (True dependencies)

Compiler reorders or inserts NOPs.

✔ Control hazards

Using delay slots (e.g., branch delay slots in MIPS):

BEQ R1, R2, Target
Instruction in delay slot (executed regardless)

✔ Load-use hazards

As shown earlier.

✘ WAR and WAW hazards

These depend on out-of-order execution and are handled by dynamic scheduling, not static. Static pipelines do not allow out-of-order execution.

---

⭐ Static vs Dynamic Scheduling

Feature	Static Scheduling	Dynamic Scheduling
Who handles hazards?	Compiler	Hardware
Reordering	Before execution (compile-time)	During execution (runtime)
Hardware complexity	Low	High (requires Tomasulo, ROB)
Flexibility	Low	High
Used in	RISC	CISC, advanced CPUs
Handles WAW/WAR	No	Yes
Handles latency variations	Poor	Excellent

---

⭐ Advantages of Static Scheduling

✔ Simpler CPU hardware ✔ Lower power consumption ✔ Predictable performance ✔ Less pipeline complexity ✔ Compiler can optimize aggressively

---

⭐ Disadvantages of Static Scheduling

✘ Compiler cannot predict runtime events (cache misses, branch behavior, etc.) ✘ Cannot handle dynamic latency variations ✘ Rarely ideal scheduling for all execution conditions ✘ May require extra NOPs if no independent instructions exist

---

⭐ Static Scheduling in Modern Architectures

• Classical RISC CPUs (MIPS, SPARC) use static scheduling heavily.
• Branch delay slots and load delay slots are typical examples.
• Some embedded CPUs still rely on static scheduling for power efficiency.
• Modern superscalar CPUs rely more on dynamic scheduling, but compilers still do static optimizations first.

---

⭐ Exam-Friendly Summary

• Static scheduling is compiler-based instruction reordering to avoid pipeline hazards.
• Used mainly in RISC architectures.
• Handles RAW and control hazards by reordering or inserting NOPs.
• Simplifies hardware but reduces flexibility.
• Contrast: Dynamic scheduling is hardware-based (Tomasulo, ROB) and handles hazards at runtime.