Loop Perforation
Loop perforation discards some loop iterations and scales the result to compensate. It applies the “skip work” idea to sequential programs [HMS+09], a form of approximate computing. Covered in ECE459 L14.
Why does scaling work?
Only when inputs are appropriately distributed. Summing uniformly random values at stride 2 and doubling the result is unbiased in expectation; summing a sorted list that way is not.
// Original
for i in 0 .. n { sum += numbers.get(i).unwrap(); }
// Perforated: every 2nd element, multiply by 2
for i in (0 .. n).step_by(2) { sum += numbers.get(i).unwrap(); }
sum *= 2;Example domains [RHMS10]
- evaluating forces on water molecules (summing numbers)
- Monte-Carlo swaption pricing
- video encoding: changing loop increment from 4 to 8 gave 1.67x speedup, 0.87% SNR decrease, 18.47% bitrate increase. Results were visually indistinguishable