Implement Loop Unrolling and Measure the Speedup

Topic Overview

Trade Code Size for Latency Hiding

Loop unrolling duplicates the body to cut branch instructions per iteration and expose instruction-level parallelism. Compilers unroll at -O3; manual #pragma unroll or partial unrolling helps when the compiler is conservative about trip counts.

Manual Unroll Example

Process four elements per iteration with a cleanup loop for remainder.

cCopy
Loading…

• Unrolling too far blows icache and register pressure
• Pair with SIMD for 4x or 8x logical unroll
• -funroll-loops lets GCC decide automatically
• Measure on target CPU; unroll depth is not portable

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement manual loop unrolling on a reduction loop and compare against compiler-unrolled assembly. This exercise requires reporting when unrolling helped and when it regressed.

Your Task

Unrolling a sum loop saves loop overhead, but on its own it does not make a reduction faster. Every add still waits for the previous one, because they all feed one accumulator. The real speed-up comes from splitting the sum across several independent accumulators, so adds overlap in the pipeline. Implement the unrolled sums for real (check that the result is unchanged), then use a simple cost model to see whether each version is limited by latency (the dependency chain) or by throughput (instructions per cycle).

Input

cCopy
Loading…

The default array is array 1000 1.

Rules

• Sum. The main loop handles K elements per iteration while at least K remain, and element j of an iteration goes to accumulator j mod ACC. The remainder loop adds leftover elements to accumulator 0. The accumulators are then added together. Compare the result with a plain sum.
• Instructions: main_iters * (2K + 3) + remainder * 5 + (ACC - 1). Each element costs a load and an add, and each loop iteration costs 3 overhead instructions. Code size: 2K + 3, plus 5 if K > 1 (the remainder loop), plus ACC - 1.
• Cycles = max(chain, ceil(instructions / W)), where chain = (the largest number of adds on any one accumulator + ACC - 1) * L. The bound is latency if chain >= the throughput term, else throughput.
• The speed-up is baseline cycles (K = 1, ACC = 1, current settings) / cycles, rounded half up to 2 decimals.
• Errors: array: 1..100000 elements, latency: must be >= 1, issue: must be >= 1, and unroll K ACC: need 1 <= accumulators <= factor <= 64.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Actually run the unrolled loops with real accumulators. The cost model must describe code you executed.
2. Use integer arithmetic throughout, so every number is exact.

Hidden tests cover a length that is not a multiple of K (remainder iterations), a latency of 1 (throughput-bound from the start), a narrow issue width, more accumulators than needed, a 1-element array, another seed, and invalid settings.