Here is an unusual loop First list the dependencies and then

Here is an unusual loop. First, list the dependencies and then re-write the loop so that it is parallel. for i = 1; i

Solution

Dependencies in the loop are
=> dependence from S1 to S2 on b which will be Anti dependence.
=> dependence from S1 to S2 on a which will be True dependence.
=> dependence from S1 to S3 on a which will be True dependence.
=> dependence from S3 to S1 on a which will be loop carried output dependence.
=> dependence from S3 to S2 on a which will be loop carried true dependence.
=> dependence from S3 to S3 on a which will be loop carried true dependence.

To make it parallel, loop carried dependencies need to be broken. This can be done by deleting S3 from the loop as there is not much signicicance of S3 in the loop. Only the last iteration is useful (for S3) as all values of a[i+1] are modified on the next iteration by a[i]. Hence the modified for loop will be S1 and S2, removing S3 and adding a new statement S4 after the loop is finished

for (i=1; i<100; i++)
{
a[i]=b[i]+c[i] ; /*S1*/
b[i]=a[i]+d[i] ; /*S2 */
}
a[100]=a[99]+e[99] ; /*S4*/