================================================================ COMS 4130, Fall 2012 Columbia University Homework #5/6 Concurrent Programming ================================================================ PROBLEM 1: Graph Algorithms We desire to define graph algorithms using the techniques of structural operational semantics. Consider a configuration containing a multi-set of atoms, each of the form n(X), e(X,Y) or n(X,Y) where X and Y are non-negative integers. We say that a configuration A represents a (directed) graph if for every atom e(X,Y) in A it is the case that n(X) in A and n(Y) in A, and each atom in A has multiplicity 1 (no duplicates). In such a case, each n(X) in A represents a node in the graph labeled with the id X, and each e(X,Y) in A represents an edge from X to Y. Further, by design, no two nodes in the graph can be labeled with the same id. In a directed graph we say that two nodes are connected if there is an edge between them (in either direction), or, recursively, there is a third node to which both are (separately) connected. We define the transition relation as follows. Below, {a_0, a_1, a_{k-1} | S} represents a multi-set which contains exactly each a_i (i < k) and each element in the multi-set S. The transition relation is defined by: (I) {n(X) | S} --> {n(X,X) | S} n(X,C) in S e(X,Y) in S C < D (II) ------------------------------------- { n(Y,D) | S} --> {n(Y,C) | S} n(X,C) in S e(Y,X) in S C < D (III) ------------------------------------- { n(Y,D) | S} --> {n(Y,C) | S} Q1 Suppose a configuration A represents a finite directed graph. Can there be an infinite execution sequences starting from A. Why or why not? Q2 Is this transition system determinate? Why or why not? Q3 Let A be a configuration representing a graph and containing only n(X) and e(X,Y) atoms. Let Z be a terminal configuration such that A -->* Z. For each of the following assertions, specify which are true or false. Justify. A. For every node n(X) in A, Z contains an atom n(X,C) for some C. B. If n(X,C) in Z then n(C) in A and n(X) in A, and X and C are connected in A. C. For any node X in A, let C be the node in A connected to X s.t. no node connected to X in A has lower id. Then n(X,C) in Z. Q4 Provide the tightest upper bound you can for the run-time of the algorithm, in terms of number of transitions, assuming the initial graph has N nodes and E edges. (Do not go overboard, O(N^2) is acceptable compared to O(N^1.73565), and O(log(N)) is acceptable compared to O(log(log(N))).) Q5 Implement the following method in X10 to compute the connected components of a graph -- feel free to use whatever ideas you may have gleaned from the questions above. Your code need run in only one place, but should take advantage of multiple workers in the place. The runtime will be tested for 1, 2, 4 and 8 workers on inputs with O(10^5) vertices and O(10^9) edges. Each vertex in the graph is identified by a non-negative id, ranging from 0 through N-1. The rails D and A are of size N. On entry into the procedure, D(i)=i, for all i. A specifies the adjacency matrix for the graph -- for each i, A(i) is the rail of vertices connected to i. The graph is undirected, so if j is in (the rail) A(i) then it is the case that i will be in A(j). class CC { static def cc(D:Rail[Int], A:Rail[Rail[Int]]) { ... } } On exit from the procedure D(i) should be the smallest id of vertices in the graph that i is connected to (through an undirected path). ================================================================ PROBLEM 2: READERS-WRITER LOCK The locks we have examined in class provide universal mutual exclusion, meaning that no two threads, regardless of their use of a shared data structure, can hold the lock at the same time. If two threads wish to read the data structure, and not modify it in any way, these two reads will be serialized by such a lock, even though they could safely proeed in parallel. In this problem you will implement what is called a multiple reader, single writer lock which can be held by multiple readers, but only a single writer. A good place for background on such locks is Wikipedia: http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock Q1. Implement a class ReadersWriterLock which implements such a lock. You may use any algorithm or X10 constructs you like. Your class should be called ReadersWriterLock and implement the following two public methods: public def lock(i:Int, w:Boolean) { ... } // i: thread ID of requesting thread // w: flag indicating write Multiple reader threads may hold this lock, but when one thread is writing, no other thread may read or write. Q2. Place a comment block at the top of your ReadersWriterLock.x10 and prove that your code has the following three properties. P1: No thread shall starve attempting to acquire the lock. P2: Concurrent reads may proceed in parallel. P3: Writes are mutually exclusive with all other accesses. Q3. Implement a main method (public static def main(argv:Array[String]{self.rank==1}) {...}) for your class that tests out the function of your lock. ================================================================ PROBLEM 3: MATCHER Implement the body of the match method with the signature: class Matcher(n:Int) { def match(i:Int):Int { ... } } A match(x) should return with a value of y only when there has in fact been a simultaneous invocation of match(y), and it is the case that (x+y)%n == 1. The match(y) invocation is also required to return with x (the "match"). The code should not deadlock. If there are match(x) and match(y) invocations s.t. (x+y)%n==1 (and there are no other interfering match calls), then both should return. That is, match calls that can pair up, *should* pair up. The code should also handle the case in which there are multiple oustanding match(...) invocations with the same argument value. A match(x) invocation should pair up with exactly one match(y) invocation. That is, if simultaneously there are two match(x) and three match(y) invocations (where (x+y)%n==1), then one match(y) invocation should not return until and unless there is a match(z) invocation such that (z+y)%n==1.