List all the dependencies output anti and true in the follow

List all the dependencies (output, anti, and true) in the following code fragment Indicate whether the true dependences are loop-carried or not. Show why the loop is not parallel. for (i = 2; i

Solution

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

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

True dependencies cannot be removed and since there are loop-carried dependencies as well, thus the loop is not independent. Hence the loop cannot be made parallel because of the sturcture of the for loop. Recreating the loop might be helpful in finding equivalent loop to the original one which can further be made parallel