⭐ Trace Scheduling

1. Definition

Trace scheduling is a compiler optimization technique used to increase instruction-level parallelism (ILP) across basic blocks by reordering instructions along likely execution paths (traces).

It is mainly used in VLIW (Very Long Instruction Word) and superscalar architectures to produce statically scheduled code that exploits parallelism beyond a single basic block.

2. Key Concepts

1. Trace

   • A trace is a sequence of basic blocks that is likely to execute consecutively during program execution.
   • Usually determined using profiling (branch probabilities).

2. Goal

   • Schedule instructions along the entire trace to maximize parallel execution and keep functional units busy.
   • Reduces pipeline stalls and idle cycles.

3. Difference from Local Scheduling

   Feature	Local Scheduling	Trace Scheduling
   Scope	Single basic block	Across multiple blocks (trace)
   Parallelism	Limited (intra-block)	Higher (inter-block)
   Complexity	Low	High
   Hardware Support	Not needed	Still static, VLIW-friendly

3. Steps in Trace Scheduling

1. Trace Selection

   • Identify the most likely path of execution using branch probabilities.
   • Example: if if branch taken 90% of the time, include it in trace.

2. Instruction Scheduling Along the Trace

   • Reorder instructions from multiple basic blocks in the trace to exploit parallelism.
   • Use pipeline hazards analysis to prevent RAW/WAR/WAW conflicts.

3. Compensating Code

   • Instructions moved outside their original blocks may need extra code in other paths to maintain program correctness.
   • Example: If an instruction is scheduled before a branch, add fix-up code in the path not taken.

4. Register Allocation and Finalization

   • After scheduling, assign registers carefully to avoid conflicts caused by moving instructions across blocks.

4. Example

Original code:

if (x > 0) {
    A = B + C;
} else {
    D = E + F;
}
G = H + I;

Likely trace: if (x > 0) path

• Trace includes: {A = B + C} → {G = H + I}

Trace scheduling:

• Instructions from the else-block {D = E + F} may be moved or compensated in the unlikely path.
• Instructions are reordered to maximize parallel execution along the likely trace.

Result:

• More instructions executed per cycle on a VLIW or superscalar pipeline.
• Less pipeline idle time.

5. Advantages

1. Exploits ILP across basic blocks → higher performance than local scheduling.
2. Improves VLIW pipeline utilization.
3. Static scheduling → simpler hardware (no dynamic scheduling needed).

6. Limitations

1. Complex compiler algorithm – selecting traces and inserting compensating code is tricky.
2. Code size increase – compensating code may duplicate instructions in unlikely paths.
3. Accuracy depends on profiling – mispredicted traces can reduce performance.
4. Best suited for frequently executed paths.

7. Comparison: Local Scheduling vs Trace Scheduling vs Software Pipelining

8. Exam Summary

• Trace Scheduling: A compiler technique to maximize ILP across basic blocks by scheduling instructions along likely execution paths (traces).
• Key idea: Move instructions across blocks, use compensating code for correctness.
• Used in: VLIW and statically scheduled superscalar architectures.
• Advantages: High ILP, better pipeline utilization.
• Limitations: Compiler complexity, code size increase, dependent on profiling accuracy.