 [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. Lowercase variables
are local to the processes that use them; all other variables are shared.
 (5 points) What implications exist between processes P1 and P2
concerning the values of a and b at the end of
the processes?
 (5 points) Draw the ShashaSnir graph for the two processes.
 (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.
 (5 points) What might cause those edges to be not respected?
 [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 taskrecycling 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);


fork5ways
/    \
/    \
x=    if (p) x=
    
    
 barrier  < each thread executes b.reached(); b.waitUntilReached();
    
    
 =x =x =x 
    
\    /
\    /
join5ways
 [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.
 [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.
 [5 points] Based on your treatment of barrier, describe how no
access anomaly for x is caught after the barrier.
 [40 points] Dependence analysis
for i=1 to 30
for j=1 to 50
A(i+1,j2) = B(i,j)
C(i,j) = A(i+j, j)
end
end
 [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.
 [5 points] What does the GCD test say about independence of the references?
Show your work!
 [5 points] What inequalities do the loop bounds for i and j
impose on x1, y1, x2, y2?
 [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.
 [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!
 [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?
 [25 points] Consider the flow graph shown below:
 [2 points] Depthfirst number the vertices of the
flow graph.
 [3 points] Based on your depthfirst numbering, what is
the reverse topological order for the graph?
 [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 
 [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
pathprofiling path index.
 [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  