Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


swarnendu-biswas-dissertation.pdf (1.11 MB)

ETD Abstract Container

Abstract Header

Practical Support for Strong, Serializability-Based Memory Consistency

Biswas, Swarnendu
http://orcid.org/0000-0001-6839-8586
http://rave.ohiolink.edu/etdc/view?acc_num=osu1470957618

Abstract Details

2016, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Data races are a fundamental barrier to writing correct shared-memory, multithreaded programs, and often lead to concurrency bugs. Furthermore, data races complicate programming language semantics. Current programming language and hardware memory models provide weak end-to-end consistency guarantees for executions with data races---leading to unexpected, erroneous behaviors. Researchers have argued for a stronger guarantee in the presence of concurrency errors arising from data races: programs should have fail-stop behavior and precise semantics. However, building a system that efficiently provides strong semantic guarantees for data races is complex and challenging---and has remained elusive. The complexity and risk associated with data races motivate this work. The thesis of our work is that systems should furnish programming language implementations with a mechanism that gives all executions clear, simple semantics. In this dissertation, we advocate for providing strong memory consistency based on serializability of regions as the default memory model on shared-memory systems. Prior approaches that have attempted to provide region serializability were afflicted by the high costs of either precisely tracking "last reader(s)" information at read operations or eagerly tracking all conflicts. To realize this goal, we explore efficient techniques to provide strong memory consistency based on region serializability---where regions are demarcated by synchronization operations, or they can be programmer-defined. We begin by developing a software-only technique that provides serializability of synchronization-free regions (i.e., regions demarcated by synchronization operations) by efficiently detecting region conflicts. For a given execution, our proposed technique ensures that the execution either completes successfully and the output is region serializable, or the execution terminates with an exception. The key insight in this work is that detecting read--write conflicts lazily retains necessary semantic guarantees and has better performance than eager conflict detection. Our proposed software-only technique has overheads competitive enough to provide practical semantic guarantees to a language specification. Since hardware support can speed up conflict detection, we then explore the possibility of an efficient architectural solution to provide region serializability end-to-end. We propose a novel architecture design that provides the same strong consistency guarantee for every execution by either providing region serializability or by generating a consistency exception indicating a data race that may jeopardize consistency. The key insight in our hardware design is that each core can execute largely independently from other cores, deferring actions that ensure consistency until synchronization operations and private cache evictions. The key contributions lie in its novel mechanism to detect region conflicts. Furthermore, as a result of ensuring consistency, the design can defer cache coherence until synchronization operations and evictions---unlike existing coherence protocols that ensure coherence at every instruction. Lastly, we extend the scope of providing consistency to the language-level by providing serializability of programmer-defined regions instead of synchronization-free regions. Serializability of programmer-defined regions or atomicity is a key correctness property of concurrent programs that allows programmers to reason about code regions in isolation. However, programs often fail to enforce atomicity correctly, leading to serializability violations that are difficult to detect. We present a novel sound and precise dynamic atomicity checker that checks for violations of conflict serializability efficiently. The key insight of this work lies in soundly and efficiently overapproximating cross-thread dependences, and then recovering precision with more expensive analysis only when required. Even after years of research, providing strong memory consistency based on serializability of regions has so far remained elusive. As a case in point: current high-level programming languages such as C/C++ and Java memory models provide essentially no useful guarantees about the semantics of data races. This dissertation aims to fill this critical gap in today's languages and systems by demonstrating the possibility of providing a strong memory model based on region serializability efficiently. By precisely identifying potential serializability violations, the approaches proposed in this dissertation help extend strong semantic guarantees to all program executions, including executions with data races. By precisely checking for atomicity violations, our technique presents a promising direction for providing serializability of programmer-defined regions. The software-only performance-efficient techniques presented in this work can provide the foundation to guarantee stronger semantics to all program executions in the near-future, thereby improving concurrent software development and reliability in the long-term. Our evaluation shows that the hardware-based solution can be the foundation upon which future scalable shared-memory systems are built. Overall, this dissertation significantly advances the state of the art in parallel architecture consistency and coherence.
Michael D. Bond (Advisor)
Atanas Rountev (Committee Member)
Qin Feng (Committee Member)
208 p.
Computer Science
Memory models; cache coherence; region serializability; conflict exceptions; region conflicts; data races; atomicity checking; dynamic program analysis

Recommended Citations

Citations

  • Biswas, S. (2016). Practical Support for Strong, Serializability-Based Memory Consistency [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1470957618

    APA Style (7th edition)

  • Biswas, Swarnendu. Practical Support for Strong, Serializability-Based Memory Consistency . 2016. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1470957618.

    MLA Style (8th edition)

  • Biswas, Swarnendu. "Practical Support for Strong, Serializability-Based Memory Consistency ." Doctoral dissertation, Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1470957618

    Chicago Manual of Style (17th edition)

osu1470957618
595
© 2016, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.