Instruction Scheduling
1. What and Why
Instruction scheduling reorders IR/machine ops to keep functional units busy and hide latencies, without changing semantics. Needed because CPUs execute in parallel / out-of-order, but stalls occur on data hazards.
2. Hazards (must respect)
| Hazard | Example | Fix |
|---|---|---|
| RAW (true) | r1=a+b; r2=r1*2 — second needs first |
keep order / forward |
| WAR (anti) | r1=a; a=r1+1 with reuse |
rename |
| WAW (output) | two writes same reg | rename |
| Structural | two ops need same unit | spread apart |
Only independent ops may swap (dependence DAG check).
3. List Scheduling (basic-block method)
1. build dependence DAG with latencies (e.g. load=2, mul=3, add=1)
2. priority = longest path to exit (critical path first)
3. cycle by cycle: issue ready op with highest priority whose units free
Example: a=load x; b=load y; c=a+b; d=c*2 — issue both loads together, then add, then mul (hides load latency).
4. Scope
Local (one block) vs global (trace/superblock across branches, speculative). Compilers favour local + loop software pipelining.
5. Exam Points
- Define scheduling + hazards — 5 marks, very frequent.
- List-schedule given DAG — 5-7 marks, frequent.
- Dependence vs independence check — 3 marks, frequent.