Exam II (Extended HW Set) Due by 18th December 2007 5 PM

1. [20 points] (Given 15 Nov 2007) Suppose that initially, X=Y=0, and the two processes below then execute concurrently:

       P1               |          P2
                        |
      t = Y + 1         |         t = X + 4
      X = t             |         Y = t
      t = X + 2         |         t = Y + 8
      Y = t             |         X = t
      a = Y             |         b = X
                        |
   
   

   There is no synchronization between the two processes, so statements can interleave in any manner possible, as long as program order appears to be followed within each process. Lower-case variables are local to the processes that use them; all other variables are shared.

   1. (5 points) What implications exist between processes P1 and P2 concerning the values of a and b at the end of the processes?
   2. (5 points) Draw the Shasha-Snir graph for the two processes.
   3. (5 points) Give an example whereby some edges of your graph would not be respected and that would cause an implication from part (1) to fail to hold.
   4. (5 points) What might cause those edges to be not respected?
2. [15 points] (Given 19 November 2007) Access anomaly detection A barrier synchronization is a mechanism by which no thread from a given set of threads can proceed past the barrier until all threads in that set have reached the barrier. An implementation in Java for a barrier is given here.

   Recall the task-recycling approach to access anomaly detection:

   • Each task is assigned a sync vector
   • There is an entry in the sync vector for each concurrently running task in the system.
   • The entry is a version number -- an integer -- such that the task assigned the version number is synchronized with every version at or less than the entry listed in the sync vector.
   As before, concurrency is generated and recovered using forks and joins. However, in this problem, you consider what happens when all threads execute a barrier, such that none can proceed until all have hit the barrier.

   Consider the concurrent taks graph shown below:

          Barrier b = new Barrier(5);
                      |
                      |
                 fork-5-ways
                /  |  |  |  \
               /   |  |  |   \
              x=   |  |  | if (p) x=
              |    |  |  |   |
              |    |  |  |   |
              ---  barrier --- <--- each thread executes b.reached(); b.waitUntilReached();
              |    |  |  |   |
              |    |  |  |   |
              |   =x =x =x   |
              |    |  |  |   |
              \    |  |  |   /
               \   |  |  |  /
                 join-5-ways
   

   1. [5 points]
      • Explain exactly what happens in terms of tasks' sync vectors at a barrier instruction. Be general! Do not base this part of your answer only on the example above. Do assume that all tasks participate in the barrier.
      • Starting at the top of the program above, show the tasks' sync vectors everywhere they are affected, including what happens by way of your treatment of barrier.
   2. [5 points] Describe under what conditions an access anomaly for x would be caught before the barrier executes. Show the task vectors and how the anomaly can be found.
   3. [5 points] Based on your treatment of barrier, describe how no access anomaly for x is caught after the barrier.
3. [40 points] Dependence analysis

      for i=1 to 30
        for j=1 to 50
           A(i+1,j-2) = B(i,j)
           C(i,j)     = A(i+j, j)
         end
      end
   

   1. [6 points] Let x1 and x2 represent i and j, respectively, at the def of A; let y1 and y2 represent i and j, respectively, at the use of A. Write the system of dependence equations for the def and use of A.
   2. [5 points] What does the GCD test say about independence of the references? Show your work!
   3. [5 points] What inequalities do the loop bounds for i and j impose on x1, y1, x2, y2?
   4. [8 points] What does the Banerjee Wolfe test say about the independence of the references? Take into account the loop bounds but not any direction vector.
   5. [8 points] Suppose we want to interchange the two loops.
      • Under what direction vector should your dependence equations be tested to see if the loops can be interchanged?
      • What is the result of your testing (do the references allow or disallow loop interchange)? Show your work!
   6. [8 points] Now consider the direction vector (=,=).
      • Are the references dependent or independent, based on the dependence tests taught in class? Show your work!
      • Based on your analysis, can the order of the two assignment statements be switched?
4. [25 points] Consider the flow graph shown below:

   

   1. [2 points] Depth-first number the vertices of the flow graph.
   2. [3 points] Based on your depth-first numbering, what is the reverse topological order for the graph?
   3. [5 points] Using the Ball and Larus approach from their Path Profiling paper, fill in the table below:

      Node x	NumPaths(x)
      Entry
      A
      B
      C
      D
      E
      F
      G
      H
      J
      K
      Exit	1

   4. [10 points] Using the Ball and Larus approach, and assuming that the F→B edge is very heavily weighted, label the edges by the bump required to compute a path-profiling path index.
   5. [5 points] Based on your edge labels, fill in the following table:

      Path p	Path index for p
      Entry A C F H Exit
      Entry A C F B E J K Exit