a. Identify the data dependences (which variable? true/flow, anti or output?)

b. Describe in words one or more correct parallelizations of the code -- only one is needed, but more versions will test your knowledge.

Example 1: Matrix-vector multiply

for (i=0; i

for (j=0; j

a[i] = a[i] + c[i][j] * b[j];

}

}

Example 2: 1D Jacobi stencil

for (t=0; t

for (i=1; i

B[i] = 0.33 * (A[i-1] + A[i] + A[i+1]);

}

for (i=1; i

A[i] = B[i];

}

}

Example 3: Floyd Warshall

for (k=0; k

for (i=0; i

for (j=0; j

path_old = path[i][j];

path_new = path[i][k] + path[k][j];

if (path_old > path_new) {

path[i][j] = path_new;

}

}

}

}

Example 4: bicg

for (i=0; i

q[i] = 0;

for (j=0; j

s[j] = s[j] + r[i] * A[i][j];

q[i] = q[i] + A[i][j] * p[j];

}

}