Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


thesis.pdf (928.25 KB)

ETD Abstract Container

Abstract Header

Efficient, Practical Dynamic Program Analyses for Concurrency Correctness

Cao, Man
http://rave.ohiolink.edu/etdc/view?acc_num=osu1492703503634986

Abstract Details

2017, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Shared-memory parallel programs are notoriously difficult to be both scalable and correct. One of the most problematic concurrency bugs is data race. Data races are difficult to avoid, find, fix, reproduce, and eliminate. A fundamental problem is that language and hardware memory models provide few or no guarantees for executions containing data races. Researchers have developed various program analyses and runtime tools for concurrency correctness properties. Examples includes data race detectors, multithreaded record & replay, transactional memory, and enforcement of stronger memory models. However, in the presence of data races, many of these tools suffer from limitations that impede their widespread use. The first challenge in handling racy executions is the high overhead for tracking (i.e., detect or control) cross-thread dependences, which is a necessary requirement to ensure the soundness of many analyses. The second limitation is that existing work has not covered the full range of possible behaviors for racy executions in weak memory models. This thesis explores several efficient and practical dynamic program analyses that aim to overcome these two key limitations, advancing the state of the art for detecting, enforcing, and exposing issues related to concurrency correctness. We present hybrid tracking and RegPlay to address the first challenge. Hybrid tracking is a generalized framework for tracking dependences, which hybridizes pessimistic and optimistic tracking in order to get the best of both world. We build hybrid-tracking-based versions of a dependence recorder and a region serializability enforcer to demonstrate the usefulness of hybrid tracking. RegPlay shows an analysis-specifc way of optimizing dependence tracking in the context of multithreaded record & replay. RegPlay avoids recording read--write dependences and many transitively implied dependences in order to reduce run-time overhead, and enforces replay determinism by detecting and resolving violations of read--write dependences. Experiments show that hybrid tracking enables runtime support to overcome the performance limitations of both pessimistic and optimistic tracking alone, and RegPlay records much fewer dependences than existing approach while preserves replay determinism. To address the second limitation, we introduce prescient memory (PM), a novel dynamic analysis that exposes behaviors due to future values---a value written by a store that executes after the load that uses the value. A load could return a future value in a racy execution in weak memory models, but existing analyses fail to expose such behaviors. PM speculatively returns a future value at a program load, and tries to validate the speculative value at a later store. PM applies a novel approach that profiles future values and guides execution to increase the chances of successfully validating future values in real application executions. Experiments shows that PM uncovers a few previously unknown behaviors due to future values in real applications. Overall, this thesis presents three approaches that overcome limitations of existing work on concurrency correctness. These approaches advance the state of the art in terms of performance, coverage, capability, and practicality. The proposed approaches will improve the efficiency and adoption of dynamic analyses and runtime support for concurrency correctness, which will significantly strengthen software reliability and increase productivity of software development in the years to come.
Michael Bond (Advisor)
Atanas Rountev (Committee Member)
Feng Qin (Committee Member)
175 p.
Computer Engineering; Computer Science
concurrency, runtime, parallelism, correctness, bug detection, performance, data race, dynamic analysis

Recommended Citations

Citations

  • Cao, M. (2017). Efficient, Practical Dynamic Program Analyses for Concurrency Correctness [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1492703503634986

    APA Style (7th edition)

  • Cao, Man. Efficient, Practical Dynamic Program Analyses for Concurrency Correctness. 2017. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1492703503634986.

    MLA Style (8th edition)

  • Cao, Man. "Efficient, Practical Dynamic Program Analyses for Concurrency Correctness." Doctoral dissertation, Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu1492703503634986

    Chicago Manual of Style (17th edition)

osu1492703503634986
610
© 2017, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.