Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Dissertation.pdf (917.32 KB)

ETD Abstract Container

Abstract Header

Efficient Compiler and Runtime Support for Serializability and Strong Semantics on Commodity Hardware

Sengupta, Aritra
http://rave.ohiolink.edu/etdc/view?acc_num=osu149269601946527

Abstract Details

2017, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Parallel software systems often have non-deterministic behavior and suffer from reliability issues. A major deterrent to the use of sound and precise bug-detection techniques is the impractical run-time overhead and poor scalability of such analyses. Alternatively, strong memory models or program execution models could achieve software reliability. Unfortunately, existing analyses and systems that provide stronger guarantees in ill-synchronized programs are either expensive or they compromise on reliability for performance. Building efficient runtime support for enforcing strong program semantics remains a challenging problem because of the overhead incurred to implement the complex mechanisms in the underlying system. The overhead could be because of restriction on reordering of operations in the compiler or the hardware, instrumentation cost in enforcing stronger program semantics through a dynamic analysis, the cost of concurrency control or synchronization mechanisms typically required in such an analysis, and the cost of leveraging specific hardware constructs. Researchers have proposed strong memory models based on serializability of regions of code—where regions of code across threads execute in isolation with each other. The run-time cost incurred to enforce strong memory models based on serializability stems from the unbounded number of operations that are monitored by an analysis. This thesis solves this critical problem of providing region serializability at reasonable overheads and yet demonstrating its efficacy in eliminating erroneous behavior from ill-synchronized programs. Providing serializability of code regions using compiler techniques and dynamic analysis while leveraging both generic and specialized commodity hardware, at low overheads, across concurrent programs having diverse characteristics—can make enforcement of strong semantics for real-world programs practical and scalable. This work presents a memory model based on bounded regions, called dynamically bounded region serializability (DBRS) and establishes the memory model theoretically—contrasting it with other memory models. It provides a novel technique, called EnfoRSer, that enforces the memory model practically, leveraging not only dynamically bounded, but statically bounded, intra-procedural, acyclic regions of code. This technique utilizes a lightweight conflict-detection mechanism and strong compiler transformations to enforce DBRS at low overheads. Further, an additional dynamic analysis based on prior work demonstrates empirically DBRS’s potential to eliminate real-world bugs. After establishing the benefits of DBRS, this thesis provides a mechanism to reduce the instrumentation overhead of DBRS enforcement by proposing a novel technique that efficiently hybridizes per-access locks and per-region locks based on the results of static data race detection, offline profiling, and a cost-benefit model. This technique demonstrates that for programs with low inter-thread dependences and high density of memory accesses, a hybridized synchronization scheme can enforce DBRS more efficiently. The first two techniques require advanced compiler transformations and per-access instrumentation for inter-thread conflict detection and resolution. These techniques also suffer from high overheads in programs with significant conflicts—pertaining to expensive conflict resolution. To purge the limitations of the first two techniques, this work provides a more practical and efficient solution to DBRS enforcement. This approach, called Legato, overcomes these complexities and uses widely available commodity hardware transactional memory (HTM) to enforce DBRS efficiently preserving all the benefits of the memory model. Applying commodity HTM to enforce DBRS showcases a significant challenge—prohibitive “startup” and “tear-down” cost of hardware transactions. Further, the best-effort commodity HTM poses several challenges such as unknown abort location, transactions aborting for reasons other than capacity and conflict, and requiring an expensive fallback to non-speculative execution. We apply a novel technique that merges several regions into a single transaction in order to amortize the cost of starting and stopping transactions. Our approach resolves the other challenges with an algorithm based on control theory principles that enforces DBRS with lower run-time costs than our prior approaches. This technique eliminates the complexities of the previous two approaches and provides a simpler and a more efficient solution to DBRS enforcement. Overall, this dissertation proposes a memory model with strong benefits in today’s concurrent software and evaluates three distinct mechanisms to enforce the memory model—each improving on the limitations of the other. Our evaluation demonstrates that low-overhead enforcement of DBRS is indeed feasible in today’s commodity hardware that eliminates several bugs in erroneous real-world programs; hence, advancing the state of the art.
Michael Bond (Advisor)
180 p.
Computer Engineering
concurrency; memory models; data races; strong semantics; compiler transformations; static analysis; dynamic analysis; hardware transactional memory; code generation; performance optimization

Recommended Citations

Citations

  • Sengupta, A. (2017). Efficient Compiler and Runtime Support for Serializability and Strong Semantics on Commodity Hardware [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu149269601946527

    APA Style (7th edition)

  • Sengupta, Aritra. Efficient Compiler and Runtime Support for Serializability and Strong Semantics on Commodity Hardware. 2017. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu149269601946527.

    MLA Style (8th edition)

  • Sengupta, Aritra. "Efficient Compiler and Runtime Support for Serializability and Strong Semantics on Commodity Hardware." Doctoral dissertation, Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu149269601946527

    Chicago Manual of Style (17th edition)

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