⭐ 1. Loop Unrolling

Definition

Loop unrolling is a compiler optimization technique where the body of a loop is replicated multiple times to reduce the overhead of branch instructions and increase instruction-level parallelism (ILP).

Essentially, the compiler transforms a loop to do multiple iterations in a single loop pass.

---

Purpose of Loop Unrolling

1. Reduce loop control overhead – fewer branch instructions and loop counter updates.
2. Increase ILP – more instructions in a single sequence can be scheduled in pipelines.
3. Enable better register allocation – more independent operations can run in parallel.

---

Example of Loop Unrolling

Original Loop:

for (i = 0; i < 8; i++) {
    A[i] = B[i] + C[i];
}

2x Unrolled Loop:

for (i = 0; i < 8; i += 2) {
    A[i] = B[i] + C[i];
    A[i+1] = B[i+1] + C[i+1];
}

4x Unrolled Loop:

for (i = 0; i < 8; i += 4) {
    A[i] = B[i] + C[i];
    A[i+1] = B[i+1] + C[i+1];
    A[i+2] = B[i+2] + C[i+2];
    A[i+3] = B[i+3] + C[i+3];
}

Benefits:

• Fewer loop branches (one for 8 iterations vs. one for each iteration).
• More instructions available for pipeline scheduling or VLIW slot filling.

Trade-offs:

• Increased code size (can be a problem for instruction cache).
• Need careful handling if loop count isn’t divisible by unroll factor.

---

⭐ 2. Software Pipelining

Definition

Software pipelining is a compiler technique that reorders instructions from different iterations of a loop to maximize parallelism and pipeline utilization.

Think of it as overlapping successive loop iterations, similar to how hardware pipelines overlap stages of instructions.

---

Key Idea

Instead of executing one iteration at a time:

1. Split loop body into pipeline stages.
2. Reorder instructions from multiple iterations so that all pipeline stages remain busy.

Goal: Achieve steady-state execution, where each clock cycle executes some part of an iteration without stalls.

---

Example

Original Loop (single iteration):

for (i = 0; i < N; i++) {
    load R1, A[i]
    add  R2, R1, #1
    store B[i], R2
}

Software-Pipelined Version (overlapping 3 iterations):

Cycle	Instruction
1	load A[0]
2	add R2, R1, #1 (i=0), load A[1]
3	store B[0], R2; add R2, R1, #1 (i=1); load A[2]
4	store B[1], R2; add R2, R1, #1 (i=2); load A[3]
…	…

Explanation:

• Each cycle executes parts of different iterations.
• Pipeline remains full; no stalls due to data dependencies.

---

Difference Between Loop Unrolling and Software Pipelining

Feature	Loop Unrolling	Software Pipelining
Purpose	Reduce branch overhead, increase ILP	Overlap iterations to improve pipeline utilization
How it works	Duplicate loop body multiple times	Reorder instructions from different iterations
Effect on pipeline	More instructions per iteration	Keeps pipeline stages busy continuously
Code size	Increases significantly	Slightly increases, often less than unrolling
Dependency handling	Within iteration only	Across iterations

---

Advantages of Software Pipelining

1. Maximizes pipeline throughput.
2. Reduces idle cycles caused by hazards.
3. Improves ILP without massively increasing code size.
4. Works well for loops with fixed iteration counts.

---

Limitations

1. Compiler complexity – requires detailed dependency analysis.
2. Harder for loops with conditional branches inside.
3. Less effective for loops with very short bodies.

---

⭐ Exam-Friendly Summary

• Loop Unrolling: Replicate loop body to reduce branch overhead and increase ILP within iteration.
• Software Pipelining: Reorder instructions from different iterations to keep the pipeline busy.
• Key Difference: Unrolling is within iteration, pipelining is across iterations.
• Both are compiler optimizations for high-performance pipelines (RISC or VLIW).