Instruction Scheduling for Pipeline
1. Pipeline Problem
A pipelined CPU overlaps fetch/decode/execute stages. Without scheduling, data + control hazards cause bubbles (NOPs). Compiler orders code to fill all stages.
2. Classic 5-Stage Hazards
IF → ID → EX → MEM → WB
load-use: LW r1,0(r2) | ADD r3,r1,r4 → 1 bubble unless independent op inserted
branch: fetched next may be wrong → delay slot filled with useful op or NOP
Techniques: forwarding (HW) + scheduling (SW): hoist independent op between producer and consumer.
3. Delay-Slot Example (MIPS-style)
before: LW r1,0(r2) | NOP | ADD r3,r1,r4 (bubble wasted)
after: LW r1,0(r2) | ADD r5,r6,r7 (independent) | ADD r3,r1,r4 (slot filled, no stall)
branch: BEQ ... | (delay slot: useful op from before branch) | target...
Software pipelining overlaps loop iterations: iter i+1 load while iter i computes.
4. Compiler Role vs Hardware
In-order pipelines rely on compiler scheduling; out-of-order HW reschedules at run time but compiler still helps (less logic, better I-cache).
5. Exam Points
- Explain pipeline bubbles + delay slots — 5-7 marks, very frequent.
- Fill load-delay / branch-delay example — 5 marks, frequent.
- Software pipelining idea for loops — 3-5 marks, frequent.