Software and Hardware Support for Data-Race Exceptions

Thesis (Ph.D.)--University of Washington, 2014Some researchers have proposed data-race exceptions to mitigate the ill effects of data races in shared-memory multithreaded programs. Data-race exceptions make every data race an explicit fail-stop error at run-time. Implementing data-race exceptions naturally requires accurate dynamic data-race detection with low performance overhead, yet existing data- race detectors compromise either accuracy or performance. Hardware data-race detectors solutions are fast, but inaccurate. Accurate software data-race detectors slow execution by several times. This dissertation presents three new systems to bring accurate and fast language-level data-race exceptions closer to feasibility. Race Detection in Software and Hardware (RADISH) accelerates an accurate software data-race detection algorithm by mapping common cases to highly-optimized hardware support. By falling back to software support in rare cases, RADISH maintains full accuracy for low-level programs while achieving good performance. We show RADISH's accuracy via its equivalence to a canonical accurate software algorithm for data-race detection. Low-level Abstractable Race Detection (LARD) virtualizes accurate low-level data-race detectors, such as RADISH, to support accurate data-race detection for high-level languages. Experimental evaluation shows that existing low-level data-race detectors are inaccurate on high-level programs in practice, while our LARD implementation is accurate and preserves the performance of the low-level data-race detector. Fast Instrumentation Bias (FIB) is a cooperative synchronization protocol designed to reduce the overheads of pure-software accurate dynamic data-race detection. Analysis barriers--the code inserted before each memory access in the program to check and update analysis metadata--may execute concurrently. If barriers are not atomic, they may fail to detect true data races. Existing implementations either allow non-atomic barriers, sacrificing guaranteed accuracy, or employ pessimistic synchronization to ensure barrier atomicity and analysis accuracy. FIB exploits analysis invariants to guarantee barrier atomicity with no synchronization in the common case, at the cost of expensive synchronization in rare cases. Experimental evaluation shows that FIB is faster than a highly optimized conventional implementation of barrier atomicity on several benchmarks and slower on others, varying with the rate of updates to shared data. Conservative dynamic thread-escape analysis can lower overheads of both implementations while maintaining accuracy