Computer Science Thesis Oral

Thesis Orals
Ph.D. Student
Computer Science Department
Carnegie Mellon University
Dataflow Analysis-Based Dynamic Parallel Monitoring
Monday, August 4, 2014 - 2:00pm to 4:00pm
8102 
Gates&Hillman Centers
Abstract:

Despite the best efforts of programmers and programming systems researchers, software bugs continue to be problematic. This thesis will focus on a new framework for performing dynamic (runtime) parallel program analysis, called dataflow analysis-based dynamic parallel monitoring. Existing dynamic analysis tools have focused on monitoring sequential programs. Parallel programs are susceptible to a wider range of errors than sequential programs, making them even more in need of online monitoring. Unfortunately, monitoring parallel applications is difficult due to inter-thread data dependences and relaxed memory consistency models.

Dataflow analysis-based dynamic parallel monitoring avoids these pitfalls without relying on strong consistency models or detailed inter-thread dependence tracking. Using insights from dataflow analysis, our frameworks enable parallel applications to be monitored concurrently without capturing a total order of application instructions across parallel threads. This thesis has three major contributions: Butterfly Analysis, Chrysalis Analysis, and extensions to both Butterfly Analysis and Chrysalis Analysis to explicitly track uncertainty.

Butterfly Analysis is the first dataflow analysis-based dynamic parallel monitoring framework. We propose a new model of thread execution, which assumes that events in the distant past on all threads have become visible but makes no assumptions on the relative ordering of more recent events on other threads. To overcome the potential state explosion of considering all possible orderings, we adapt techniques from dataflow analysis to this new domain of dynamic parallel monitoring.

In Chrysalis Analysis, we show how generalizing the Butterfly Analysis framework to incorporate explicit happens-before arcs resulting from high-level synchronization within a monitored program can drastically improve precision, while increasing the complexity of the analysis. Finally, we extend both Butterfly Analysis and Chrysalis Analysis to incorporate an uncertain state into their metadata lattice, and show how this can more precisely isolate true errors from possible errors and enable dynamic adaptations in the presence of uncertainty.

In all cases, we show that our frameworks are provably guaranteed to never miss an error and sacrifice precision only due to the lack of a relative ordering among recent events, and present experimental results on performance and precision from our implementations.

Thesis Committee:
Todd Mowry (Chair)
Phillip Gibbons
Jonathan Aldrich
Kathryn McKinley (MSR/UT Austin)

Keywords:
For More Information, Please Contact:

deb [atsymbol] cs.cmu.edu