Consider the loop a[0] = 0

a0-0-for-i-1-i-n-i-a

#1

Consider the loop
a[0] = 0;
for (i = 1; i < n; i++)
a[i] = a[i-1] + i;
There’s clearly a loop-carried dependence, as the value of a[i] can’t be computed without the value of a[i-1]. Can you see a way to eliminate this dependence and parallelize the loop?

Answer:

image
image