Paper Info
Title
Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs.
Abstract
If a parallel program has determinacy race(s), different schedules can result in memory accesses that observe different values --- various race-detection tools have been designed to find such bugs. A key component of race detectors is an algorithm for series-parallel (SP) maintenance, which identifies whether two accesses are logically parallel. This paper describes an asymptotically optimal algorithm, called WSP-Order, for performing SP maintenance in programs with fork-join (or nested) parallelism. Given a fork-join program with T1 work and T∞ span, WSP-Order executes it while also maintaining SP relationships in O(T1/P + T∞) time on P processors, which is asymptotically optimal. At the heart of WSP-Order is a work-stealing scheduler designed specifically for SP maintenance. We also implemented C-RACER, a race-detector based on WSP-Order within the Cilk Plus runtime system, and evaluated its performance on five benchmarks. Empirical results demonstrate that when run sequentially, it performs almost as well as previous best sequential race detectors. More importantly, when run in parallel, it achieves almost as much speedup as the original program without race-detection.
Year
DOI
Venue
2016
10.1145/2935764.2935801
SPAA
Field
DocType
Citations 
Computer science,Parallel computing,Schedule,Work stealing,Fork–join queue,Cilk,Asymptotically optimal algorithm,Determinacy,Runtime system,Speedup,Distributed computing
Conference
8
PageRank 
References 
Authors
0.43
20
4
Name
Order
Citations
PageRank
robert utterback1161.92
Kunal Agrawal268750.08
Jeremy T. Fineman358736.10
I-Ting Angelina Lee412312.17