Solutions of Sample Test #2

Problem 3:

(a)

     1. True dependence from S1 to S2 on a. (RAW)
     2. Loop-carried true dependence from S4 to S1 on b. (RAW)
     3. Loop-carried true dependence from S4 to S3 on b. (RAW)
     4. Loop-carried true dependence from S4 to S4 on b. (RAW)
     5. Loop-carried output dependence from S1 to S3 on a. (WAW)
     6. Loop-carried antidependence from S1 to S3 on a. (WAR)
     7. Loop-carried antidependence from S2 to S3 on a. (WAR)

(b)

   True dependencies 2, 3, and 4 are loop-carried.

(c)

Because dependencies 1, 2, 3, and 4 are true dependencies, they can not be 
removed through renaming.  In addition, as dependencies 2, 3, and 4 are 
loop-carried, they imply that iterations of the loop are not independent. 
These factors together imply the loop can not be made parallel as the
loop is written.  However, by ``rewriting'' the loop it may be possible to 
find a loop that is functionally equivalent to the original loop that can be 
made parallel.