research-article

Parallelizing data race detection

Authors:

Benjamin Wester,

David Devecsery,

Satish NarayanasamyAuthors Info & Claims

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

Pages 27 - 38

https://doi.org/10.1145/2451116.2451120

Published: 16 March 2013 Publication History

Abstract

Detecting data races in multithreaded programs is a crucial part of debugging such programs, but traditional data race detectors are too slow to use routinely. This paper shows how to speed up race detection by spreading the work across multiple cores. Our strategy relies on uniparallelism, which executes time intervals of a program (called epochs) in parallel to provide scalability, but executes all threads from a single epoch on a single core to eliminate locking overhead. We use several techniques to make parallelization effective: dividing race detection into three phases, predicting a subset of the analysis state, eliminating sequential work via transitive reduction, and reducing the work needed to maintain multiple versions of analysis via factorization. We demonstrate our strategy by parallelizing a happens-before detector and a lockset-based detector. We find that uniparallelism can significantly speed up data race detection. With 4x the number of cores as the original application, our strategy speeds up the median execution time by 4.4x for a happens-before detector and 3.3x for a lockset race detector. Even on the same number of cores as the conventional detectors, the ability for uniparallelism to elide analysis locks allows it to reduce the median overhead by 13% for a happens-before detector and 8% for a lockset detector.

References

[1]

S. Adve. Data races are evil with no exceptions. Communications of the ACM, 53 (11): 84, November 2010.

Digital Library

[2]

S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In Proc. 1991 International Symposium on Computer Architecture, pages 234--243.

Digital Library

[3]

U. Banerjee, B. Bliss, Z. Ma, and P. Petersen. A theory of data race detection. In 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, pages 69--78.

Digital Library

[4]

H.-J. Boehm and S. V. Adve. Foundations of the C

[5]

concurrency memory model. In Proc. 2008 ACM Conference on Programming Language Design and Implementation, pages 68--78.

[6]

H.-J. Boehm and S. V. Adve. You Don't Know Jack About Shared Variables or Memory Models. Communications of the ACM, 55 (2): 48--54, February 2012.

Digital Library

[7]

M. D. Bond, K. E. Coons, and K. S. McKinley. Pacer: Proportional detection of data races. In Proc. 2010 ACM Conference on Programming Language Design and Implementation, pages 255--268.

Digital Library

[8]

S. Chen, B. Falsafi, P. B. Gibbons, M. Kozuch, T. C. Mowry, R. Teodorescu, A. Ailamaki, L. Fix, G. R. Ganger, B. Lin, and S. W. Schlosser. Log-Based Architectures for General-Purpose Monitoring of Deployed Code. In 2006 Workshop on Architectural and System Support for Improving Software Dependability.

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 Proc. 2002 ACM Conference on Programming Language Design and Implementation, pages 258--269.

Digital Library

[10]

J.-D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Transactions on Programming Languages and Systems, 13 (4): 491--530, October 1991.

Digital Library

[11]

J. Chung, M. Dalton, H. Kannan, and C. Kozyrakis. Thread-Safe Dynamic Binary Translation Using Transactional Memory. In Proc. 2008 Symposium on High Performance Computer Architecture, pages 279--289.

[12]

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 Proc. 2012 International Symposium on Computer Architecture, pages 201--212.

Digital Library

[13]

T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: A race and transaction-aware Java runtime. In Proc. 2007 ACM Conference on Programming Language Design and Implementation, pages 245--255.

Digital Library

[14]

J. Erickson, M. Musuvathi, S. Burckhardt, and K. Olynyk. Effective data-race detection for the kernel. In Proc. 2010 Symposium on Operating Systems Design and Implementation, pages 151--162.

Digital Library

[15]

C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Australian Computer Science Communications, 10 (1): 56--66, February 1988.

[16]

C. Flanagan and S. N. Freund. FastTrack: Efficient and precise dynamic race detection. In Proc. 2009 ACM Conference on Programming Language Design and Implementation, pages 121--133.

Digital Library

[17]

A. Itzkovitz, A. Schuster, and O. Zeev-Ben-Mordehai. Toward integration of data race detection in DSM systems. Journal of Parallel and Distributed Computing, 59 (2): 180--203, November 1999.

Digital Library

[18]

K. Kelsey, T. Bai, C. Ding, and C. Zhang. Fast Track: A software system for speculative program optimization. In Proc. 2009 International Symposium on Code Generation and Optimization, pages 157--168.

Digital Library

[19]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21 (7): 558--565, July 1978. ISSN 0001-0782.

Digital Library

[20]

D. Lee, B. Wester, K. Veeraraghavan, S. Narayanasamy, P. M. Chen, and J. Flinn. Respec: Efficient online multiprocesor replay via speculation and external determinism. In Proc. 2010 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 77--90.

Digital Library

[21]

N. G. Leveson and C. S. Turner. An Investigation of the Therac-25 Accidents. IEEE Computer, 26 (7): 18--41, July 1993.

Digital Library

[22]

B. Lucia, L. Ceze, K. Strauss, S. Qadeer, and H.-J. Boehm. Conflict exceptions: Simplifying concurrent language semantics with precise hardware exceptions for data-races. In Proc. 2010 International Symposium on Computer Architecture, pages 210--221.

Digital Library

[23]

D. Marino, M. Musuvathi, and S. Narayanasamy. LiteRace: Effective sampling for lightweight data-race detection. In Proc. 2009 ACM Conference on Programming Language Design and Implementation, pages 134--143.

Digital Library

[24]

F. Mattern. Virtual time and global states of distributed systems. In Proc. 1988 International Workshop on Parallel and Distributed Algorithms.

[25]

A. Muzahid, D. Suárez, S. Qi, and J. Torrellas. SigRace: Signature-based data race detection. In Proc. 2009 International Symposium on Computer Architecture, pages 337--348.

Digital Library

[26]

S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically Classifying Benign and Harmful Data Races Using Replay Analysis. In Proc. 2007 ACM Conference on Programming Language Design and Implementation, pages 22--31.

Digital Library

[27]

N. Nethercote and J. Seward. Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. In Proc. 2007 ACM Conference on Programming Language Design and Implementation, pages 89--100.

Digital Library

[28]

N. Nethercote and J. Seward. How to shadow every byte of memory used by a program. In Proc. 2007 ACM Conference on Virtual Execution Environments, pages 65--74.

Digital Library

[29]

R. H. B. Netzer. Optimal Tracing and Replay for Debugging Shared-Memory Parallel Programs. In 1993 ACM/ONR Workshop on Parallel and Distributed Debugging.

Digital Library

[30]

E. B. Nightingale, D. Peek, P. M. Chen, and J. Flinn. Parallelizing security checks on commodity hardware. In Proc. 2008 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 308--318.

Digital Library

[31]

A. Nistor, D. Marinov, and J. Torrellas. Light64: Lightweight hardware support for data race detection using systematic testing of parallel programs. In Proc. 2009 International Symposium on Microarchitecture, pages 541--552.

Digital Library

[32]

K. Poulsen. Tracking the blackout bug. Technical report, SecurityFocus, April 2004. http://www.securityfocus.com/news/8412.

[33]

E. Pozniansky and A. Scheuster. Efficient on-the-fly data race detection in multithreaded C++ programs. In Proc. 2003 ACM Symposium on Principles and Practice of Parallel Programming, pages 179--190.

Digital Library

[34]

M. Prvulovic and J. Torrellas. ReEnact: Using thread-level speculation mechanisms to debug data races in multithreaded codes. In Proc. 2003 International Symposium on Computer Architecture, pages 110--121.

Digital Library

[35]

P. Ratasaworabhan, M. Burtscher, D. Kirovski, B. Zorn, R. Nagpal, and K. Pattabiraman. Detecting and tolerating asymmetric races. In Proc. 2009 ACM Symposium on Principles and Practice of Parallel Programming, pages 173--184.

Digital Library

[36]

M. Ronsse and K. D. Bosschere. RecPlay: A fully integrated practical record/replay system. ACM Transactions on Computer Systems, 17 (2): 133--152, May 1999. ISSN 0734--2071.

Digital Library

[37]

Ruwase, Chen, Gibbons, and Mowry}Ruwase10O. Ruwase, S. Chen, P. B. Gibbons, and T. C. Mowry. Decoupled Lifeguards: Enabling Path Optimizations for Dynamic Correctness Checking Tools. In Proc. 2007 ACM Conference on Programming Language Design and Implementation, pages 245--255.

Digital Library

[38]

O. Ruwase, P. B. Gibbons, T. C. Mowry, V. Ramachandran, S. Chen, M. Kozuch, and M. Ryan. Parallelizing Dynamic Information Flow Tracking. In Proc. 2008 ACM Symposium on Parallelism in Algorithms and Architectures, pages 35--45.

Digital Library

[39]

P. Sack, B. E. Bliss, Z. Ma, P. Petersen, and J. Torrellas. Accurate and efficient filtering for the Intel Thread Checker race detector. In Proc. 2006 Workshop on Architectural and System Support for Improving Software Dependability, pages 34--41.

Digital Library

[40]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15 (4): 391--411, November 1997.

Digital Library

[41]

K. Serebryany and T. Iskhodzhanov. ThreadSanitizer: Data race detection in practice. In Proc. 2009 Workshop on Binary Instrumentation and Applications, pages 62--71.

Digital Library

[42]

J. Sevcik and D. Aspinall. On Validity of Program Transformations in the Java Memory Model. In Proc. 2008 European conference on Object-Oriented Programming, pages 27--51.

Digital Library

[43]

M. Süßkraut, T. Knauth, S. Weigert, U. Schiffel, M. Meinhold, and C. Fetzer. Prospect: A compiler framework for speculative parallelization. In Proc. 2010 International Symposium on Code Generation and Optimization, pages 131--140.

Digital Library

[44]

K. Veeraraghavan, P. M. Chen, J. Flinn, and S. Narayanasamy. Detecting and surviving data races using complementary schedules. In Proc. 2011 ACM Symposium on Operating Systems Principles, pages 369--384.

Digital Library

[45]

K. Veeraraghavan, D. Lee, B. Wester, J. Ouyang, P. M. Chen, J. Flinn, and S. Narayanasamy. DoublePlay: Parallelizing sequential logging and replay. In Proc. 2011 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 15--26.

Digital Library

[46]

E. Vlachos, M. L. Goodstein, M. A. Kozuch, S. Chen, B. Falsafi, P. B. Gibbons, and T. C. Mowry. ParaLog: Enabling and Accelerating Online Parallel Monitoring of Multithreaded Applications. In Proc. 2010 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 271--284.

Digital Library

[47]

C. von Praun and T. R. Gross. Object race detection. In Proc. 2001 ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 70--82.

Digital Library

[48]

S. Wallace and K. Hazelwood. SuperPin: Parallelizing dynamic instrumentation for real-time performance. In Proc. 2007 International Symposium on Code Generation and Optimization, pages 209--220.

Digital Library

[49]

S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In Proc. 1995 International Symposium on Computer Architecture, pages 24--36.

Digital Library

[50]

M. Xu, M. D. Hill, and R. Bodik. A regulated transitive reduction (RTR) for longer memory race recording. In Proc. 2006 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 49--60.

Digital Library

[51]

Y. Yu, T. Rodeheffer, and W. Chen. RaceTrack: Efficient detection of data race conditions via adaptive tracking. In Proc. 2005 ACM Symposium on Operating Systems Principles, pages 221--234.

Digital Library

[52]

P. Zhou, R. Teodorescu, and Y. Zhou. HARD: Hardware-assisted lockset-based race detection. In Proc. 2007 Symposium on High Performance Computer Architecture, pages 121--132.

Digital Library

[53]

C. Zilles and G. Sohi. Master/slave speculative parallelization. In Proc. 2002 International Symposium on Microarchitecture, pages 85--96.

Digital Library

Cited By

Yang YHeath DKolesnikov VDevecsery D(2022)EZEE: Epoch Parallel Zero Knowledge for ANSI C2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00015(109-123)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00015
Kamath ABasu A(2021)iGUARDProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483545(49-65)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483545
Liu SSeemakhupt KWei YWenisch TKolli AKhan SLarus JCeze LStrauss K(2020)Cross-Failure Bug Detection in Persistent Memory ProgramsProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378452(1187-1202)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378452
Show More Cited By

Index Terms

Parallelizing data race detection
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Software and its engineering
  1. Software creation and management
    1. Designing software
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
    2. Extra-functional properties
      1. Software performance

Recommendations

Parallelizing data race detection
ASPLOS '13

Detecting data races in multithreaded programs is a crucial part of debugging such programs, but traditional data race detectors are too slow to use routinely. This paper shows how to speed up race detection by spreading the work across multiple cores. ...
Parallelizing data race detection
ASPLOS '13

Detecting data races in multithreaded programs is a crucial part of debugging such programs, but traditional data race detectors are too slow to use routinely. This paper shows how to speed up race detection by spreading the work across multiple cores. ...
CURD: a dynamic CUDA race detector
PLDI '18

As GPUs have become an integral part of nearly every pro- cessor, GPU programming has become increasingly popular. GPU programming requires a combination of extreme levels of parallelism and low-level programming, making it easy for concurrency bugs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

March 2013

574 pages

ISBN:9781450318709

DOI:10.1145/2451116

General Chair:
Vivek Sarkar
Rice University, USA
,
Program Chair:
Rastislav Bodik
University of California, Berkeley, USA

ACM SIGPLAN Notices Volume 48, Issue 4
ASPLOS '13
April 2013
540 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2499368
Issue’s Table of Contents
ACM SIGARCH Computer Architecture News Volume 41, Issue 1
ASPLOS '13
March 2013
540 pages
ISSN:0163-5964
DOI:10.1145/2490301
Issue’s Table of Contents

Copyright © 2013 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: 16 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASPLOS '13

Sponsor:

ASPLOS '13: Architectural Support for Programming Languages and Operating Systems

March 16 - 20, 2013

Texas, Houston, USA

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
766
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)4

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang YHeath DKolesnikov VDevecsery D(2022)EZEE: Epoch Parallel Zero Knowledge for ANSI C2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00015(109-123)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00015
Kamath ABasu A(2021)iGUARDProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483545(49-65)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483545
Liu SSeemakhupt KWei YWenisch TKolli AKhan SLarus JCeze LStrauss K(2020)Cross-Failure Bug Detection in Persistent Memory ProgramsProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378452(1187-1202)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378452
Qiu KZheng ZTrivedi KYin B(2020)Stress Testing With Influencing Factors to Accelerate Data Race Software FailuresIEEE Transactions on Reliability10.1109/TR.2019.289505269:1(3-21)Online publication date: Mar-2020
https://doi.org/10.1109/TR.2019.2895052
Jahić JKumar VJung MWirrer GWehn NKuhn T(2019)Rapid Identification of Shared Memory in Multithreaded Embedded Systems with Static SchedulingWorkshop Proceedings of the 48th International Conference on Parallel Processing10.1145/3339186.3339195(1-8)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3339186.3339195
Hartung MSchintke FSchutt T(2019)Pinpoint Data Races via Testing and Classification2019 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW.2019.00100(386-393)Online publication date: Oct-2019
https://doi.org/10.1109/ISSREW.2019.00100
Xiang DChakrabarty KFujiwara H(2018)Fault-Tolerant Unicast-Based Multicast for Reliable Network-on-Chip TestingACM Transactions on Design Automation of Electronic Systems10.1145/324321423:6(1-23)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3243214
Zheng LLiao XJin HHe BXue JLiu HEvripidou SStenström PO'Boyle M(2018)Towards concurrency race debuggingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243206(1-13)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243206
Chang DBhat GOgras UBakkaloglu BOzev S(2018)Detection Mechanisms for Unauthorized Wireless TransmissionsACM Transactions on Design Automation of Electronic Systems10.1145/324104623:6(1-21)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3241046
Bianchi FMargara APezze M(2018)A Survey of Recent Trends in Testing Concurrent Software SystemsIEEE Transactions on Software Engineering10.1109/TSE.2017.270708944:8(747-783)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2707089
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