Show simple item record

dc.contributor.advisor Sarkar, Vivek
dc.creatorRaman, Raghavan
dc.date.accessioned 2013-07-24T19:44:42Z
dc.date.accessioned 2013-07-24T19:44:45Z
dc.date.available 2013-07-24T19:44:42Z
dc.date.available 2013-07-24T19:44:45Z
dc.date.created 2012-12
dc.date.issued 2013-07-24
dc.date.submitted December 2012
dc.identifier.urihttps://hdl.handle.net/1911/71681
dc.description.abstract With the advent of multicore processors and an increased emphasis on parallel computing, parallel programming has become a fundamental requirement for achieving available performance. Parallel programming is inherently hard because, to reason about the correctness of a parallel program, programmers have to consider large numbers of interleavings of statements in different threads in the program. Though structured parallelism imposes some restrictions on the programmer, it is an attractive approach because it provides useful guarantees such as deadlock-freedom. However, data races remain a challenging source of bugs in parallel programs. Data races may occur only in few of the possible schedules of a parallel program, thereby making them extremely hard to detect, reproduce, and correct. In the past, dynamic data race detection algorithms have suffered from at least one of the following limitations: some algorithms have a worst-case linear space and time overhead, some algorithms are dependent on a specific scheduling technique, some algorithms generate false positives and false negatives, some have no empirical evaluation as yet, and some require sequential execution of the parallel program. In this thesis, we introduce dynamic data race detection algorithms for structured parallel programs that overcome past limitations. We present a race detection algorithm called ESP-bags that requires the input program to be executed sequentially and another algorithm called SPD3 that can execute the program in parallel. While the ESP-bags algorithm addresses all the above mentioned limitations except sequential execution, the SPD3 algorithm addresses the issue of sequential execution by scaling well across highly parallel shared memory multiprocessors. Our algorithms incur constant space overhead per memory location and time overhead that is independent of the number of processors on which the programs execute. Our race detection algorithms support a rich set of parallel constructs (including async, finish, isolated, and future) that are found in languages such as HJ, X10, and Cilk. Our algorithms for async, finish, and future are precise and sound for a given input. In the presence of isolated, our algorithms are precise but not sound. Our experiments show that our algorithms (for async, finish, and isolated) perform well in practice, incurring an average slowdown of under 3x over the original execution time on a suite of 15 benchmarks. SPD3 is the first practical dynamic race detection algorithm for async-finish parallel programs that can execute the input program in parallel and use constant space per memory location. This takes us closer to our goal of building dynamic data race detectors that can be "always-on" when developing parallel applications.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectStructured parallelism
Data races
Program analysis
dc.title Dynamic Data Race Detection for Structured Parallelism
dc.contributor.committeeMember Mellor-Crummey, John
dc.contributor.committeeMember Zhong, Lin
dc.date.updated 2013-07-24T19:44:45Z
dc.identifier.slug 123456789/ETD-2012-12-260
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Raman, Raghavan. "Dynamic Data Race Detection for Structured Parallelism." (2013) Diss., Rice University. https://hdl.handle.net/1911/71681.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record