Determinacy Detection and Race Detection

6.895 Theory of Parallel Systems Lecture 4 Debugging Multithreaded Programs Lecture Summary 1. Determinacy Races This section introduces the concept of a determinacy race in parallel programs, and provides two examples of Cilk programs where such races occur. 2. Introduction to the Nondeterminator This section introduces the Nondeterminator, discusses its performance, and describes how Cilk pro- grams can be represented using series-parallel directed acyclic graphs and series-parallel parse trees. 3. The SP-Bags Algorithm This section presents the SP-Bags algorithm, the algorithm used by the Nondeterminator to detect determinacy races in Cilk programs. 4. Nondeterminator Correctness This section presents a proof of correctness for the SP-Bags algorithm for the Nondeterminator. 1 Determinacy Races In a parallel program, two threads running concurrently may want to access the same memory location. If the order of the accesses is not well defined, this conflict is a determinacy race, which can lead to incorrect program behavior. This section defines a determinacy race and analyzes two Cilk programs that have determinacy races.   1.1 A Cilk Program with a Determinacy Race In this section, we provide an example of a simple Cilk program with a determinacy race. We consider the following Cilk program:   int x; cilk void foo(void) { x++; return; } cilk int main(void) { x = 0; spawn foo(); spawn foo(); sync; printf("x is %d\n", x); return 1; } (a) Thread 1 Thread 2 read z read z write z write z (b) Thread 1 Thread 2 read z read z write z read z write z Figure 1: Two possible execution interleavings of the spawned threads in our simple Cilk program: (a) At the end of this sequence, the value of z is 2. (b) At the end of this sequence, the value of z is 1.   If a thread updates a location while another thread is concurrently accessing the location, then we say that a determinacy race occurs. In the example program, the two threads that are spawned are both trying to modify the value of z.   Each increment of z involves both a read and a write to z's memory location. Figure 1 shows two possible ways the executions of the two threads can overlap. Depending on how these read and write operations are interleaved, at the end of the program, z may have a value of 1 or 2.   1.2 Determinacy Races in Cilk In this section, we formally define a determinacy race in the context of Cilk programs. Definition 1 (Determinacy Race) A Cilk program contains a determinacy race if two logically parallel threads access the same shared location and one of the accesses is a write. We can have read/write races or write/write races, as illustrated in Figure 2.   read read write write read/write race write/write race Figure 2: Two types of determinacy races. In general, a determinacy race can cause a multithreaded parallel program to act nondeterministically. In most cases, programmers intend to write deterministic code, so a determinacy race is usually a bug. However, it is still possible for a correct program to be nondeterministic. Suppose that the code in Section 1.1 has another procedure bar that decrements a z, and assume that we are somehow guaranteed that both foo and bar execute atomically, so that operations from the two procedures are never interleaved. Then, if we spawn one thread executing foo and another executing bar, there is a determinacy race because we do not know which thread executes first. The resulting program is nondeterministic, but in this case we really do not care because the order of execution does not matter that is, the resulting value in z is the same either way, making the output of the program deterministic.   The following definition summarizes the difference between these two situations: