Research On Key Techniques Of Deterministic Multiprocessing Targeting Multithreading Programs

The popularity of multi-core platform expands the demand for multi-threaded programs. However, multi-threaded programs are notoriously hard to write, test and debug. One of the key reasons is that multi-threaded programs are nondetermnistic. Same input may lead to different behavious, depending on how the threads interleaved. Determnistic Multiprocessing always enforces the same thread interleaving for the same input, which improves the credibility of testing and eases the reproducing of concurrency bugs. Among several implementation ways of Determnistic Multiprocessing, the Deterministic Exection, which is based on runtime system, can guarantee determinism for legacy nondeterministic programs. Strongly deterministic execution guarantees determinism at the presence of data races, while weakly deterministic execution provides determinism only for data-race-free programs.However, current deterministic execution systems are still unpractical. For example, strongly deterministic execution is costly and weakly deterministic execution requires developers to fix data races in advance. In this dissertation, a number of efficient and scalable deterministic techniques are proposed in light of the different characteristics of development stage and execution stage.1. A false positive pruning technique for static data race detection. Static data-race detection is a powerful tool by providing clues for dynamic approaches to only instrument certain memory accesses. However, static data-race analyses suffer from high false positive rate. A key reason is that static analyses overestimate the set of shared objects a thread can access. We propose thread specialization to distinguish threads statically. By fixing the number of threads as well as the ID assigned to each thread, a program can be transformed into a simplified version. Static data-race analysis on this simplified program can infer the range of addresses accessed by each thread more accurately. To further reduce false positive rates, we propose three optimizations. Lazy Adjusting lazily adjusts the values of dynamically allocated multi-dimensional arrays, which are thread escapable and may be assigned with any possible value. Code Region Analysis and Phase Analysis prune false positives due to ignoring of happens-before relationships. On average, the combination of our approaches prunes false positives by 77.8% and reduces dynamic instrumentation points by 57.9%.2. A hybrid program analysis for strongly deterministic execution. Strongly deterministic multithreading provides determinism for multithreaded programs even in the presence of data races. A common way to guarantee determinism for data races is to isolate threads by buffering shared memory accesses. Unfortunately, buffering all shared accesses is prohibitively costly. We propose an approach called DRDet to efficiently make data races deterministic. DRDet leverages the insight that, instead of buffering all shared memory accesses, it is sufficient to only buffer memory accesses involving data races. DRDet uses a sound data-race detector to detect all potential data races. These potential data races, along with all accesses which may access the same set of memory objects, are flagged as data-race-involved accesses. Unsurprisingly, the imprecision of static analyses makes a large fraction of shared accesses to be data-race-involved. DRDet employs two optimizations which aim at reducing the number of accesses to be sent to query alias analysis. We implement DRDet on Core Det, a state-of-the-art deterministic multithreading system. Our empirical evaluation shows that DRDet reduces the overhead of Core Det by an average of 1.6X, without weakening determinism and scalability.3. A weakly deterministic execution technique without global synchronization. Existing weakly deterministic execution systems usually introduce additional global synchronization to executions, which reduces the performance and scalability of weak determinism. To solve this problem, we propose a new thread execution mode called Token-Free Mode. Threads in the Token-Free Mode will give up the tokens assigned to them, thus avoid the blocking of other threads waiting for tokens. Based on this technique, we implement a weakly deterministic execution system called LBDR(Load-Balanced Deterministic Runtime). LBDR uses Token-Free Mode to avoid serialization, without any global synchronization. Experimental results show that LBDR outperforms the state-of-the-art design by an average of 1.17 x.4. A deterministic execution technique for pipeline parallelism. Most existing deterministic multithreading systems are costly on pipeline parallel programs due to load imbalance. In this dissertation, we propose a Load-Balanced Deterministic Runtime(LBDR) for pipeline parallelism. LBDR deterministically takes some tokens from non-synchronization-intensive threads to synchronization-intensive threads. Experimental results show that LBDR outperforms the state-of-the-art design by an average of 22.5%.