Efficient and Scalable Methods for Concurrent Program Debugging

PhD Thesis Proposal Defence


Title: "Efficient and Scalable Methods for Concurrent Program Debugging"

by

Mr. Shaoming Huang


ABSTRACT:

Multicore is here to stay. To keep up with the hardware innovation, 
software developers are undertaking a revolution from sequential 
programming to concurrent programming. This revolution, however, is slow 
and challenging due to the exponential complexity in reasoning about 
concurrency. In particular, "Heisenbugs" such as data races which are 
non-deterministic pervasively infect concurrent software, making 
concurrent program debugging notoriously difficult.

In this proposal, we develop efficient and scalable methods in dealing 
with the Heisenbugs along four directions: multiprocessor deterministic 
replay, predictive trace analysis, trace simplification, and data sharing 
reduction. We first propose LEAP, a lightweight record and replay system 
that makes Heisenbugs reproducible in general multiprocessor environments. 
Underpinned by a new local-order based replay theorem, LEAP is fast, 
portable, and deterministic. As long as a Heisenbug manifests once, LEAP 
is able to deterministically reproduce it in every subsequent execution, 
and more importantly, with much lower overhead compared to the state of 
the art.

We second propose PECAN, a persuasive predictive trace analysis system 
that is able to predict Heisenbugs from normal executions. The salient 
feature of PECAN is that, in addition to predict Heisenbugs, it generates 
``bug hatching clips" that instruct the program to deterministically 
exercise the predicted bugs. With PECAN, programmers are provided with the 
full execution history and context information to understand the bug, 
which dramatically expedites the debugging process. To further address the 
schedule space explosion problem in predicting bugs, we propose 
TraceFilter, an efficient algorithm that significantly improves the 
scalability of general predictive trace analysis by removing the trace 
redundancy with respect to the Heisenbugs.

We third propose SimTrace, a static trace simplification technique that 
effectively reduces the number of thread context switches in the buggy 
trace. A simplified trace with fewer context switches greatly lessens the 
debugging effort by prolonging the sequential reasoning of concurrent 
program execution and reducing the number of places in the trace where we 
need to look for the cause of the bug. More importantly, through reasoning 
about the computation equivalence of the trace offline, SimTrace 
dramatically improves the efficiency of trace simplification. SimTrace 
scales well to traces with more than 1M events, making it attractive to 
practical use.

We fourth propose Privateer, an execution privatization technique that 
soundly privatizes a subset of shared data accesses in a vast category of 
concurrent programs - scheduler-oblivious programs. Underpinned by a 
privatization theorem, Privateer is able to reduce the data sharing in 
scheduler-oblivious programs without introducing any additional program 
behavior. Moreover, the non-deterministic thread interleavings on the 
privatized accesses are isolated without adding any synchronization. With 
Privateer, many real world Heisenbugs are fixed and a wide range of 
concurrency problems are alleviated without impairing the execution 
parallelism.


Date:                   Tuesday, 22 May 2012

Time:                   2:00pm - 4:00pm

Venue:                  Room 1504
                         lifts 25/26

Committee Members:      Dr. Charles Zhang (Supervisor)
                         Dr. Lin Gu (Chairperson)
 			Prof. Shing-Chi Cheung
 			Dr. Sunghun Kim


**** ALL are Welcome ****