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

research-article

Efficiently Detecting Races in Cilk Programs That Use Reducer Hyperobjects

Authors:

I-Ting Angelina Lee,

Tao B. SchardlAuthors Info & Claims

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

Pages 111 - 122

https://doi.org/10.1145/2755573.2755599

Published: 13 June 2015 Publication History

Abstract

A multithreaded Cilk program that is ostensibly deterministic may nevertheless behave nondeterministically due to programming errors in the code. For a Cilk program that uses reducers, a general reduction mechanism supported in various Cilk dialects, such programming errors are especially challenging to debug, because the errors can expose the nondeterminism in how the Cilk runtime system manages a reducer. We identify two unique types of races that arise from incorrect use of reducers in a Cilk program and present two algorithms to catch them. The first algorithm, called the Peer-Set algorithm, detects view-read races, which occur when the program attempts to retrieve a value out of a reducer when the read may result a nondeterministic value, such as before all previously spawned subcomputations that might update the reducer have necessarily returned. The second algorithm, called the SP+ algorithm, detects determinacy races, instances where a write to memory location occurs logically in parallel with another access to that location, even when the raced-on memory locations relate to reducers. Both algorithms are provably correct, asymptotically efficient, and can be implemented efficiently in practice. We have implemented both algorithms in our prototype race detector, Rader. When running Peer-Set, Rader incurs a geometric-mean multiplicative overhead of 2.32 over running the benchmark without instrumentation. When running SP+, Rader incurs a geometric-mean multiplicative overhead of 16.76.

References

[1]

M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for Java. ACM TOPLAS, 28(2):207--255, Mar. 2006.

Digital Library

[2]

R. Agrawal and S. D. Stoller. Type inference for parameterized race-free java. In B. Steffen and G. Levi, editors, Verification, Model Checking, and Abstract Interpretation, volume 2937 of LNCS, pp. 149--160. Springer Berlin Heidelberg, 2004.

[3]

M. A. Bender, J. T. Fineman, S. Gilbert, and C. E. Leiserson. On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs. In SPAA '04, pp. 133--144, 2004.

Digital Library

[4]

C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In PACT '08, October 2008.

Digital Library

[5]

R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM, 1999.

Digital Library

[6]

C. Boyapati and M. Rinard. A parameterized type system for race-free Java programs. In OOPSLA '01, pp. 56--69. ACM, 2001.

Digital Library

[7]

V. Cavé, J. Zhao, J. Shirako, and V. Sarkar. Habanero-Java: the new adventures of old X10. In PPPJ '11, pp. 51--61, 2011.

Digital Library

[8]

G.-I. Cheng, M. Feng, C. E. Leiserson, K. H. Randall, and A. F. Stark. Detecting data races in Cilk programs that use locks. In SPAA '98, 1998.

Digital Library

[9]

J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI '02, pp. 258--269. ACM, 2002.

Digital Library

[10]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, third edition, 2009.

Digital Library

[11]

J. Devietti, B. P. Wood, K. Strauss, L. Ceze, D. Grossman, and S. Qadeer. RADISH: Always-on sound and complete race detection in software and hardware. In ISCA '12, pp. 201--212. IEEE Computer Society, 2012.

Digital Library

[12]

A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In PPoPP '90, pp. 1--10, 1990.

Digital Library

[13]

D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In SOSP '03, pp. 237--252. ACM, 2003.

Digital Library

[14]

J. Erickson, M. Musuvathi, S. Burckhardt, and K. Olynyk. Effective data-race detection for the kernel. In OSDI '10, 2010.

Digital Library

[15]

M. Feng and C. E. Leiserson. Efficient detection of determinacy races in Cilk programs. TOCS, 1999.

[16]

C. Flanagan and S. N. Freund. Fasttrack: efficient and precise dynamic race detection. In PLDI '09, pp. 121--133, Dublin, Ireland, 2009. ACM.

Digital Library

[17]

M. Frigo. A Cilk++ program for the knapsack challenge. https://software.intel.com/en-us/courseware/249567, 2009.

[18]

M. Frigo, P. Halpern, C. E. Leiserson, and S. Lewin-Berlin. Reducers and other Cilk++ hyperobjects. In SPAA '09, pp. 79--90, 2009.

Digital Library

[19]

M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the Cilk-5 multithreaded language. In PLDI '98, 1998.

Digital Library

[20]

GCC 4.8. GCC 4.8 release series changes, new features, and fixes. https://gcc.gnu.org/gcc-4.8/changes.html, 2014.

[21]

Intel Corporation. Intrinsics for low overhead tool annotations. https://www.cilkplus.org/open_specification/intrinsics-low-overhead-tool-annotations-v10, Nov. 2011.

[22]

Intel Corporation. Intel® Cilk™ Plus Language Extension Specification, Version 1.1. Intel Corporation, 2013. Document 324396-002US.

[23]

Intel Corporation. An introduction to the Cilk Screen race detector. https://software.intel.com/en-us/articles/an-introduction-to-the-cilk-screen-race-detector, Apr. 2013.

[24]

I.-T. A. Lee, S. Boyd-Wickizer, Z. Huang, and C. E. Leiserson. Using memory mapping to support cactus stacks in work-stealing runtime systems. In PACT '10, pp. 411--420. ACM, 2010.

Digital Library

[25]

I.-T. A. Lee, A. Shafi, and C. E. Leiserson. Memory-mapping support for reducer hyperobjects. In SPAA '12, pp. 287--297, 2012.

Digital Library

[26]

C. E. Leiserson. The Cilk++ concurrency platform. Journal of Supercomputing, 51(3):244--257, March 2010.

Digital Library

[27]

C. E. Leiserson and T. B. Schardl. A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). In SPAA '10, June 2010.

Digital Library

[28]

D. McCrady. Avoiding contention using combinable objects. Microsoft Developer Network blog post, Sept. 2008.

[29]

J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of Supercomputing'91, pp. 24--33, 1991.

Digital Library

[30]

M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI '06, pp. 308--319. ACM, 2006.

Digital Library

[31]

R. H. B. Netzer and B. P. Miller. What are race conditions? ACM LOPLAS, 1(1):74--88, March 1992.

Digital Library

[32]

I. Nudler and L. Rudolph. Tools for the efficient development of efficient parallel programs. In ICCSE, 1986.

[33]

R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPoPP '03, pp. 167--178. ACM, 2003.

Digital Library

[34]

OpenMP Architecture Review Board. OpenMP application program interface, version 4.0. http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf, 2013.

[35]

E. Pozniansky and A. Schuster. MultiRace: Efficient on-the-fly data race detection in multithreaded c++ programs: Research articles. Journal of CCPE, 19(3):327--340, Mar. 2007.

Digital Library

[36]

P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: Practical static race detection for c. ACM TOPLAS, 33(1):3:1--3:55, Jan. 2011.

Digital Library

[37]

R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Efficient data race detection for async-finish parallelism. In Runtime Verification, volume 6418 of LNCS, pp. 368--383. 2010.

Digital Library

[38]

R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Scalable and precise dynamic datarace detection for structured parallelism. In PLDI '12, pp. 531--542, 2012.

Digital Library

[39]

J. Reinders. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O'Reilly Media, Inc., 2007.

Digital Library

[40]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic race detector for multi-threaded programs. In SOSP '97, Oct. 1997.

Digital Library

[41]

K. Serebryany and T. Iskhodzhanov. Threadsanitizer: Data race detection in practice. In WBIA '09, pp. 62--71. ACM, 2009.

Digital Library

[42]

J. Shirako, D. M. Peixotto, V. Sarkar, and W. N. Scherer. Phaser accumulators: a new reduction construct for dynamic parallelism. In IPDPS '09, 2009.

Digital Library

[43]

C. von Praun and T. R. Gross. Object race detection. In OOPSLA '01, pp. 70--82. ACM, 2001.

Digital Library

[44]

J. W. Voung, R. Jhala, and S. Lerner. Relay: Static race detection on millions of lines of code. In ESEC-FSE '07, pp. 205--214, Dubrovnik, Croatia, 2007. ACM.

Digital Library

[45]

M. Wimmer. Wait-free hyperobjects for task-parallel programming systems. In IPDPS '13, pp. 803--812, 2013.

Digital Library

[46]

Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: Efficient detection of data race conditions via adaptive tracking. In SOSP '05, pp. 221--234. ACM, 2005.

Digital Library

Cited By

Muller SSinger KGoldstein NAcar UAgrawal KLee IDonaldson ATorlak E(2020)Responsive parallelism with futures and stateProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386013(577-591)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386013
Xu YSinger KLee IGupta RShen X(2020)Parallel determinacy race detection for futuresProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374536(217-231)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374536
Utterback RAgrawal KFineman JLee IHollingsworth JKeidar I(2019)Efficient race detection with futuresProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295732(340-354)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295732
Show More Cited By

Index Terms

Efficiently Detecting Races in Cilk Programs That Use Reducer Hyperobjects
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Efficient Race Detection for Reducer Hyperobjects
Special Issue on SPAA 2015

A multithreaded Cilk program that is ostensibly deterministic may nevertheless behave nondeterministically due to programming errors in the code. For a Cilk program that uses reducers—a general reduction mechanism supported in various Cilk dialects—such ...
Memory-mapping support for reducer hyperobjects
SPAA '12: Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures

Reducer hyperobjects (reducers) provide a linguistic abstraction for dynamic multithreading that allows different branches of a parallel program to maintain coordinated local views of the same nonlocal variable. In this paper, we investigate how thread-...
A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers)
SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

We have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. Our PBFS program on a single processor runs as quickly as a standar. C++ breadth-first search implementation. PBFS ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

June 2015

362 pages

ISBN:9781450335881

DOI:10.1145/2755573

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Kunal Agrawal
Washington University in St. Louis, USA

Copyright © 2015 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SPAA '15

Sponsor:

SPAA '15: 27th ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2015

Oregon, Portland, USA

Acceptance Rates

SPAA '15 Paper Acceptance Rate 31 of 131 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
135
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Muller SSinger KGoldstein NAcar UAgrawal KLee IDonaldson ATorlak E(2020)Responsive parallelism with futures and stateProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386013(577-591)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386013
Xu YSinger KLee IGupta RShen X(2020)Parallel determinacy race detection for futuresProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374536(217-231)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374536
Utterback RAgrawal KFineman JLee IHollingsworth JKeidar I(2019)Efficient race detection with futuresProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295732(340-354)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295732
Agrawal KDevietti JFineman JLee IUtterback RXu CCzumaj A(2018)Race detection and reachability in nearly series-parallel DAGsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175277(156-171)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175277
Dimitrov DVechev MSarkar V(2018)Race Detection in Two DimensionsACM Transactions on Parallel Computing10.1145/32646184:4(1-22)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3264618
Xu YLee IAgrawal K(2018)Efficient parallel determinacy race detection for two-dimensional dagsACM SIGPLAN Notices10.1145/3200691.317851553:1(368-380)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178515
Xu YLee IAgrawal KKrall AGross T(2018)Efficient parallel determinacy race detection for two-dimensional dagsProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178515(368-380)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178515
Zhou QLi LWang LXue JFeng XKnoop JSchordan MJohnson TO'Boyle M(2018)May-happen-in-parallel analysis with static vector clocksProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168813(228-240)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168813
Matar HUnat D(2018)Runtime Determinacy Race Detection for OpenMP TasksEuro-Par 2018: Parallel Processing10.1007/978-3-319-96983-1_3(31-45)Online publication date: 1-Aug-2018
https://doi.org/10.1007/978-3-319-96983-1_3
Utterback RAgrawal KLee IKulkarni M(2017)Processor-Oblivious Record and ReplayACM SIGPLAN Notices10.1145/3155284.301876452:8(145-161)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3155284.3018764
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