More Web Proxy on the site http://driver.im/

research-article

Scalable and precise dynamic datarace detection for structured parallelism

Authors:

Raghavan Raman,

Eran YahavAuthors Info & Claims

PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 531 - 542

https://doi.org/10.1145/2254064.2254127

Published: 11 June 2012 Publication History

Abstract

Existing dynamic race detectors suffer from at least one of the following three limitations:

(i)space overhead per memory location grows linearly with the number of parallel threads [13], severely limiting the parallelism that the algorithm can handle;

(ii)sequentialization: the parallel program must be processed in a sequential order, usually depth-first [12, 24]. This prevents the analysis from scaling with available hardware parallelism, inherently limiting its performance;

(iii) inefficiency: even though race detectors with good theoretical complexity exist, they do not admit efficient implem entations and are unsuitable for practical use [4, 18].

We present a new precise dynamic race detector that leverages structured parallelism in order to address these limitations. Our algorithm requires constant space per memory location, works in parallel, and is efficient in practice. We implemented and evaluated our algorithm on a set of 15 benchmarks. Our experimental results indicate an average (geometric mean) slowdown of 2.78x on a 16-core SMP system.

Supplementary Material

ZIP File (pldi212.zip)

Included files: This folder includes the following files: the only high-level tex file, Figures and Building the document instructions (to create PS and PDF files): latex draft, dvips draft, ps2pdf draft.ps

Download
1.86 MB

References

[1]

Intel Cilk++ Programmer's Guide. http://software.intel.com/enus/ articles/download-intel-cilk-sdk/.

[2]

The Computer Language Benchmarks Game. http://shootout.alioth.debian.org/.

[3]

BARIK, R., ET AL. The habanero multicore software research project. In Proceeding of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications (2009), ACM, pp. 735--736.

Digital Library

[4]

BENDER, M. A., ET AL. On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs. In SPAA'04 (Barcelona, Spain, June27-30 2004), pp. 133--144.

Digital Library

[5]

BLUMOFE, R. D., ET AL. Cilk: an efficient multithreaded runtime system. In PPoPP'95 (Oct. 1995), pp. 207--216.

Digital Library

[6]

CAVE, V., ZHAO, J., SHIRAKO, J., AND SARKAR, V. Habanero-java: the new adventures of old x10. In PPPJ'11 (2011).

Digital Library

[7]

CHARLES, P., ET AL. X10: An object-oriented approach to nonuniform cluster computing. In OOPSLA 2005 Onward! Track (2005).

Digital Library

[8]

CHENG, G.-I., FENG, M., LEISERSON, C. E., RANDALL, K. H., AND STARK, A. F. Detecting data races in cilk programs that use locks. In SPAA'98 (1998), pp. 298--309.

Digital Library

[9]

CONG, J., SARKAR, V., REINMAN, G., AND BUI, A. Customizable Domain-Specific Computing. IEEE Design and Test, 2:28 (Mar 2011), 6--15.

Digital Library

[10]

DINNING, A., AND SCHONBERG, E. An empirical comparison of monitoring algorithms for access anomaly detection. In PPoPP'90 (1990), ACM, pp. 1--10.

Digital Library

[11]

DURAN, A., ET AL. Barcelona OpenMP tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp. In ICPP'09 (2009), pp. 124--131.

Digital Library

[12]

FENG,M., AND LEISERSON,C. E. Efficient detection of determinacy races in cilk programs. In SPAA'97 (1997), ACM, pp. 1--11.

Digital Library

[13]

FLANAGAN, C., AND FREUND, S. N. FastTrack: efficient and precise dynamic race detection. In PLDI '09 (2009), ACM, pp. 121--133.

Digital Library

[14]

FLANAGAN, C., AND FREUND, S. N. The roadrunner dynamic analysis framework for concurrent programs. In PASTE'10 (2010), ACM, pp. 1--8.

Digital Library

[15]

FRIGO, M., LEISERSON, C. E., AND RANDALL, K. H. The implementation of the cilk-5 multithreaded language. In PLDI'98 (1998), ACM, pp. 212--223.

Digital Library

[16]

GUO, Y., ET AL. Work-first and help-first scheduling policies for async-finish task parallelism. In IPDPS'09 (2009), IEEE Computer Society, pp. 1--12.

Digital Library

[17]

GUO, Y., ZHAO, J., CAVE, V., AND SARKAR, V. Slaw: A scalable locality-aware adaptive work-stealing scheduler. In IPDPS (2010).

Digital Library

[18]

KARUNARATNA, T. C. Nondeterminator-3: A provably good datarace detector that runs in parallel. Master's thesis, Department of Electrical Engineering and Computer Science, MIT, Sept. 2005.

[19]

LAMPORT, L. Concurrent reading and writing. Commun. ACM 20 (November 1977), 806--811.

Digital Library

[20]

LEE, J. K., AND PALSBERG, J. Featherweight x10: a core calculus for async-finish parallelism. In PPoPP'10 (2010), ACM, pp. 25--36.

Digital Library

[21]

MELLOR-CRUMMEY, J. On-the-fly detection of data races for programs with nested fork-join parallelism. In Supercomputing'91 (1991), ACM, pp. 24--33.

Digital Library

[22]

MELLOR-CRUMMEY, J. Compile-time support for efficient data race detection in shared-memory parallel programs. In PADD '93: Proceedings of the ACM/ONR workshop on Parallel and distributed debugging (1993), ACM, pp. 129--139.

Digital Library

[23]

OpenMP Application Program Interface v 3.0, 2008.

[24]

RAMAN, R., ET AL. Efficient data race detection for async-finish parallelism. In RV'10 (2010), Springer-Verlag, pp. 368--383.

Digital Library

[25]

RAMAN, R., ZHAO, J., SARKAR, V., VECHEV, M., AND YAHAV, E. Scalable and precise dynamic datarace detection for structured parallelism. Tech. Rep. TR12-01, Department of Computer Science, Rice University, Houston, TX, 2012.

[26]

SAVAGE, S., ET AL. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15, 4 (1997), 391--411.

Digital Library

[27]

SCHONBERG, E. On-the-fly detection of access anomalies. In PLDI'98 (1998), pp. 285--297.

Digital Library

[28]

SMITH, L. A., AND BULL, J. M. A Parallel Java Grande Benchmark Suite. In In Supercomputing'01 (2001), ACM Press, p. 8.

Digital Library

[29]

VALLEE-RAI, R., ET AL. Soot - a Java Optimization Framework. In Proceedings of CASCON 1999 (1999), pp. 125--135.

Digital Library

[30]

WINSKEL, G. The Formal Semantics of Programming Languages. MIT Press, 1993.

[31]

ZHAO, J., AND SARKAR, V. Intermediate language extensions for parallelism. In VMIL'11 (2011), pp. 333--334.

Digital Library

Cited By

Wilkins MWestrick SKandiah VBernat ASuchy BDeiana ECampanoni SAcar UDinda PHardavellas NDubach CBruening DHardekopf B(2023)WARDen: Specializing Cache Coherence for High-Level Parallel LanguagesProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580013(122-135)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580013
Thokair MZhang MMathur UViswanathan M(2023)Dynamic Race Detection with O(1) SamplesProceedings of the ACM on Programming Languages10.1145/35712387:POPL(1308-1337)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571238
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Show More Cited By

Recommendations

Scalable and precise dynamic datarace detection for structured parallelism
PLDI '12

Existing dynamic race detectors suffer from at least one of the following three limitations:

(i)space overhead per memory location grows linearly with the number of parallel threads [13], severely limiting the parallelism that the algorithm can handle;

(...
Efficient data race detection for async-finish parallelism

A major productivity hurdle for parallel programming is the presence of data races . Data races can lead to all kinds of harmful program behaviors, including determinism violations and corrupted memory. However, runtime overheads of current dynamic ...
Parallel data race detection for task parallel programs with locks
FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

Programming with tasks is a promising approach to write performance portable parallel code. In this model, the programmer explicitly specifies tasks and the task parallel runtime employs work stealing to distribute tasks among threads. Similar to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2012

572 pages

ISBN:9781450312059

DOI:10.1145/2254064

General Chairs:
Jan Vitek
Purdue University
,
Haibo Lin
Microsoft China
,
Program Chair:
Frank Tip
IBM T.J. Watson Research Center

ACM SIGPLAN Notices Volume 47, Issue 6
PLDI '12
June 2012
534 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2345156
Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '12

Sponsor:

SIGPLAN

PLDI '12: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 11 - 16, 2012

Beijing, China

Acceptance Rates

PLDI '12 Paper Acceptance Rate 48 of 255 submissions, 19%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
751
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)6

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wilkins MWestrick SKandiah VBernat ASuchy BDeiana ECampanoni SAcar UDinda PHardavellas NDubach CBruening DHardekopf B(2023)WARDen: Specializing Cache Coherence for High-Level Parallel LanguagesProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580013(122-135)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580013
Thokair MZhang MMathur UViswanathan M(2023)Dynamic Race Detection with O(1) SamplesProceedings of the ACM on Programming Languages10.1145/35712387:POPL(1308-1337)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571238
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Chabbi MRamanathan MJhala RDillig I(2022)A study of real-world data races in GolangProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523720(474-489)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523720
Bai JChen QJiang ZLawall JHu S(2022)Hybrid Static-Dynamic Analysis of Data Races Caused by Inconsistent Locking Discipline in Device DriversIEEE Transactions on Software Engineering10.1109/TSE.2021.3138735(1-1)Online publication date: 2022
https://doi.org/10.1109/TSE.2021.3138735
Wang YGao FWang LYu TZhao JLi X(2022)Automatic Detection, Validation, and Repair of Race Conditions in Interrupt-Driven Embedded SoftwareIEEE Transactions on Software Engineering10.1109/TSE.2020.298917148:1(346-363)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TSE.2020.2989171
Xu YZhou AAgrawal KLee I(2022)PINT: Parallel INTerval-Based Race Detector2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00087(850-861)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00087
Yu LJin FProtze JSarkar V(2022)Leveraging the Dynamic Program Structure Tree to Detect Data Races in OpenMP Programs2022 IEEE/ACM Sixth International Workshop on Software Correctness for HPC Applications (Correctness)10.1109/Correctness56720.2022.00012(54-62)Online publication date: Nov-2022
https://doi.org/10.1109/Correctness56720.2022.00012
Arora JWestrick SAcar U(2021)Provably space-efficient parallel functional programmingProceedings of the ACM on Programming Languages10.1145/34342995:POPL(1-33)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434299
Xu YAgrawal KLee IAgrawal KAzar Y(2021)Efficient Parallel Determinacy Race Detection for Structured FuturesProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461815(398-409)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461815
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents