Compilers
Why is the loop above hard to vectorize with SIMD instructions?
for (i = 1; i < n; i++)
a[i] = a[i - 1] + b[i];- AEach a[i] needs a[i-1] from the previous iteration
- BThe array elements are integers, which SIMD instructions cannot process
- CVectorization is impossible whenever the trip count n is unknown at compile time
Show answer and explanation
Answer: A. Each a[i] needs a[i-1] from the previous iteration
Vectorization computes, say, four elements at once with one SIMD instruction. Here a[i] needs the result a[i-1] from the previous iteration, so a[1] through a[4] cannot be computed simultaneously. A dependence that crosses iterations (a loop-carried dependence) prevents straightforward vectorization. SIMD handles integers, and loops whose trip count is known only at run time can still be vectorized by handling the remainder separately.
- A. Correct. Each result depends on the previous one, so they cannot be computed together.
- B. SIMD instructions can process integers.
- C. Unknown trip counts can be handled by processing the remainder separately.