In _______, the bodies of the two loops are merged together to form a single…
2016
In _______, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other.
- A.
Loop unrolling
- B.
Strength reduction
- C.
Loop concatenation
- D.
Loop jamming
Attempted by 149 students.
Show answer & explanation
Correct answer: D
Answer: Loop jamming
Explanation: Loop jamming, also known as loop fusion, merges the bodies of two separate loops into a single loop when the loops do not have dependencies on each other. This transformation combines iterations so the combined loop performs the work of both original loops.
When it is allowed: The two loops must iterate over the same bounds (or compatible bounds) and there must be no loop-carried dependencies or cross-references between the loop bodies that would change program semantics.
Benefits: Improved cache locality, reduced loop overhead, and sometimes better opportunities for further optimization (e.g., vectorization).
Caution: Do not apply loop jamming if the order of updates between the two loops matters or if merging would introduce dependencies that change results.
Example before merging: for i in 1..N: A[i] = f(i) for i in 1..N: B[i] = g(i)
Example after loop jamming (merged): for i in 1..N: A[i] = f(i); B[i] = g(i)
Why other choices are incorrect: Loop unrolling replicates the body of a single loop to reduce control overhead; strength reduction replaces expensive operations with cheaper ones; loop concatenation usually means placing loops sequentially and is not the standard term for merging bodies.