[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3123939.3123946acmconferencesArticle/Chapter ViewAbstractPublication PagesmicroConference Proceedingsconference-collections
research-article
Open access

PARSNIP: performant architecture for race safety with no impact on precision

Published: 14 October 2017 Publication History

Abstract

Data race detection is a useful dynamic analysis for multithreaded programs that is a key building block in record-and-replay, enforcing strong consistency models, and detecting concurrency bugs. Existing software race detectors are precise but slow, and hardware support for precise data race detection relies on assumptions like type safety that many programs violate in practice.
We propose Parsnip, a fully precise hardware-supported data race detector. Parsnip exploits new insights into the redundancy of race detection metadata to reduce storage overheads. Parsnip also adopts new race detection metadata encodings that accelerate the common case while preserving soundness and completeness. When bounded hardware resources are exhausted, Parsnip falls back to a software race detector to preserve correctness. Parsnip does not assume that target programs are type safe, and is thus suitable for race detection on arbitrary code.
Our evaluation of Parsnip on several PARSEC benchmarks shows that performance overheads range from negligible to 2.6x, with an average overhead of just 1.5x. Moreover, Parsnip outperforms the state-of-the-art Radish hardware race detector by 4.6x.

References

[1]
Martin Abadi, Cormac Flanagan, and Stephen N. Freund. 2006. Types for safe locking: Static race detection for Java. ACM Transactions on Programming Languages and Systems 28, 2 (March 2006), 207--255.
[2]
Sarita Adve. 2010. Data races are evil with no exceptions. Commun. ACM 53, 11 (Nov. 2010), 84.
[3]
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson. 2004. On-the-fly maintenance of series-parallel relationships in fork-join multi-threaded programs. In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA '04). ACM, New York, NY, USA, 133--144.
[4]
Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. 2008. The PAR-SEC Benchmark Suite: Characterization and Architectural Implications. Technical Report TR-811-08. Princeton University.
[5]
Swarnendu Biswas, Minjia Zhang, Michael D. Bond, and Brandon Lucia. 2015. Valor: Efficient, Software-only Region Conflict Exceptions. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2015). ACM, New York, NY, USA, 241--259.
[6]
Hans-J. Boehm and Sarita V. Adve. 2008. Foundations of the C++ concurrency memory model. In Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation - PLDI '08. Tucson, AZ, USA, 68.
[7]
Michael D. Bond, Katherine E. Coons, and Kathryn S. McKinley. 2010. PACER: Proportional Detection of Data Races. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation - PLDI '10. Toronto, Ontario, Canada, 255.
[8]
Caitlin Sadowski, Stephen N. Freund, and Cormac Flanagan. 2009. SingleTrack: A Dynamic Determinism Checker for Multithreaded Programs. In Proceedings of the 18th European Symposium on Programming Languages and Systems: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009.
[9]
Joseph Devietti, Benjamin P. Wood, Karin Strauss, Luis Ceze, Dan Grossman, and Shaz Qadeer. 2012. RADISH: always-on sound and complete RAce Detection In Software and Hardware. In Proceedings of the 39th Annual International Symposium on Computer Architecture (ISCA '12). IEEE Computer Society, Washington, DC, USA, 201--212. http://dl.acm.org/citation.cfm?id=2337159.2337182
[10]
Anne Dinning and Edith Schonberg. 1991. Detecting access anomalies in programs with critical sections. In Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging (PADD '91). ACM, New York, NY, USA, 85--96.
[11]
Laura Effinger-Dean, Brandon Lucia, Luis Ceze, Dan Grossman, and Hans-J. Boehm. 2012. IFRit: interference-free regions for dynamic data-race detection. In Proceedings of the ACM international conference on Object oriented programming systems languages and applications (OOPSLA '12). ACM, New York, NY, USA, 467--484.
[12]
Tayfun Elmas, Shaz Qadeer, and Serdar Tasiran. 2007. Goldilocks: a race and transaction-aware Java runtime. In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation. 245--255.
[13]
John Erickson, Madanlal Musuvathi, Sebastian Burckhardt, and Kirk Olynyk. 2010. Effective data-race detection for the kernel. In Proceedings of the 9th USENIX conference on Operating systems design and implementation (OSDI'10). USENIX Association, Berkeley, CA, USA, 1--16. http://dl.acm.org/citation.cfm?id=1924943.1924954
[14]
Colin Fidge. 1991. Logical time in distributed computing systems. IEEE Computer 24, 8 (Aug. 1991), 28--33.
[15]
Cormac Flanagan and Stephen N. Freund. 2009. FastTrack: Efficient and Precise Dynamic Race Detection. In Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09. Dublin, Ireland, 121.
[16]
Cormac Flanagan and Stephen N. Freund. 2013. RedCard: Redundant Check Elimination for Dynamic Race Detectors. In Proceedings of the 27th European Conference on Object-Oriented Programming (ECOOP'13). Springer-Verlag, Berlin, Heidelberg, 255--280.
[17]
Cormac Flanagan, Stephen N. Freund, and Jaeheon Yi. 2008. Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs. In Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation - PLDI '08. Tucson, AZ, USA, 293.
[18]
Friedemann Mattern. 1989. Virtual Time and Global States of Distributed Systems. In Parallel and Distributed Algorithms.
[19]
Joseph L. Greathouse, Zhiqiang Ma, Matthew I. Frank, Ramesh Peri, and Todd Austin. 2011. Demand-driven Software Race Detection Using Hardware Performance Counters. In Proceedings of the 38th Annual International Symposium on Computer Architecture (ISCA '11). ACM, New York, NY, USA, 165--176.
[20]
Jeff Huang and Arun K. Rajagopalan. 2016. Precise and Maximal Race Detection from Incomplete Traces. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications.
[21]
Ruirui Huang, E. Halberg, A. Ferraiuolo, and G.E. Suh. 2014. Low-overhead and high coverage run-time race detection through selective meta-data management. In 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA). 96--107. RaceSMM.
[22]
Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558--565.
[23]
Shan Lu, Joseph Tucek, Feng Qin, and Yuanyuan Zhou. 2006. AVIO: detecting atomicity violations via access interleaving invariants, Vol. 41. 37--48.
[24]
Brandon Lucia and Luis Ceze. 2009. Finding concurrency bugs with context-aware communication graphs. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 42). New York, NY, USA, 553--563.
[25]
Brandon Lucia, Luis Ceze, Karin Strauss, Shaz Qadeer, and Hans-J. Boehm. 2010. Conflict exceptions: simplifying concurrent language semantics with precise hardware exceptions for data-races. In Proceedings of the 37th annual international symposium on Computer architecture - ISCA '10. Saint-Malo, France, 210.
[26]
Brandon Lucia, Joseph Devietti, Karin Strauss, and Luis Ceze. 2008. Atom-Aid: Detecting and Surviving Atomicity Violations. In Proceedings of the 35th Annual International Symposium on Computer Architecture (ISCA '08). Beijing, China, 277--288.
[27]
Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation (PLDI '05). New York, NY, USA, 190--200.
[28]
Jeremy Manson, William Pugh, and Sarita V. Adve. 2005. The Java memory model. In Proceedings of the 32nd ACM SIGPLAN-SIGACT sysposium on Principles of programming languages - POPL '05. Long Beach, California, USA, 378--391.
[29]
Daniel Marino, Madanlal Musuvathi, and Satish Narayanasamy. 2009. LiteRace: Effective Sampling for Lightweight Data-Race Detection. In Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09. Dublin, Ireland, 134.
[30]
Daniel Marino, Abhayendra Singh, Todd Millstein, Madanlal Musuvathi, and Satish Narayanasamy. 2010. DRFX: a simple and efficient memory model for concurrent programming languages. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation - PLDI '10. Toronto, Ontario, Canada, 351.
[31]
Hassan Salehe Matar, Ismail Kuru and Serdar TaÅ§Äśran, and Roman Dementiev. 2014. Accelerating Precise Race Detection Using Commercially-Available Hardware Transactional Memory Support. In Proceedings of the 5th Workshop on Determinism and Correctness in Parallel Programming (WODET '14).
[32]
Milos Prvulovic. 2006. CORD: Cost-effective (and nearly overhead-free) Order-Recording and Data race detection. In Proceedings of the 2006 IEEE 12th International Symposium on High Performance Computer Architecture.
[33]
Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. 2006. LogTM: Log-based transactional memory. In Proceedings of the 2006 IEEE 12th International Symposium on High Performance Computer Architecture. 254--265.
[34]
Abdullah Muzahid, Norimasa Otsuki, and Josep Torrellas. 2010. AtomTracker: A Comprehensive Approach to Atomic Region Inference and Violation Detection. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO '43). IEEE Computer Society, Washington, DC, USA, 287--297.
[35]
Abdullah Muzahid, Shanxiang Qi, and Josep Torrellas. 2012. Vulcan: Hardware Support for Detecting Sequential Consistency Violations Dynamically. In Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-45). IEEE Computer Society, Washington, DC, USA, 363--375.
[36]
Abdullah Muzahid, Dario SuÃąrez, Shanxiang Qi, and Josep Torrellas. 2009. SigRace: Signature-Based Data Race Detection. In Proceedings of the 36th annual international symposium on Computer architecture (ISCA '09). ACM, New York, NY, USA, 337--348.
[37]
Mayur Naik, Alex Aiken, and John Whaley. 2006. Effective static race detection for Java. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation (PLDI '06). ACM, New York, NY, USA, 308--319.
[38]
Adrian Nistor, Darko Marinov, and Josep Torrellas. 2009. Light64: lightweight hardware support for data race detection during systematic testing of parallel programs. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 42). ACM, New York, NY, USA, 541--552.
[39]
Marek Olszewski, Jason Ansel, and Saman Amarasinghe. 2009. Kendo: Efficient Deterministic Multithreading in Software. In Proceeding of the 14th international conference on Architectural support for programming languages and operating systems - ASPLOS '09. Washington, DC, USA, 97.
[40]
Eli Pozniansky and Assaf Schuster. 2003. Efficient on-the-fly data race detection in multithreaded C++ programs. In Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP '03). ACM, New York, NY, USA, 179--190.
[41]
Milos Prvulovic and Josep Torrellas. 2003. ReEnact: using thread-level speculation mechanisms to debug data races in multithreaded codes. In Proceedings of the 30th annual international symposium on Computer architecture (ISCA '03). ACM, New York, NY, USA, 110--121.
[42]
S. Qi, A. A. Muzahid, W. Ahn, and J. Torrellas. 2014. Dynamically detecting and tolerating IF-Condition Data Races. In 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA). 120--131.
[43]
Shanxiang Qi, Norimasa Otsuki, Lois Orosa Nogueira, Abdullah Muzahid, and Josep Torrellas. 2012. Pacman: Tolerating Asymmetric Data Races with Unintrusive Hardware. In Proceedings of the 2012 IEEE 18th International Symposium on High-Performance Computer Architecture (HPCA '12). IEEE Computer Society, Washington, DC, USA, 1--12.
[44]
Xuehai Qian, Josep Torrellas, Benjamin Sahelices, and Depei Qian. 2013. Volition: Scalable and Precise Sequential Consistency Violation Detection. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '13). ACM, New York, NY, USA, 535--548.
[45]
Daniel Sanchez and Christos Kozyrakis. 2013. ZSim: Fast and Accurate Microarchitectural Simulation of Thousand-core Systems. In Proceedings of the 40th Annual International Symposium on Computer Architecture (ISCA '13). ACM, New York, NY, USA, 475--486.
[46]
Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. 1997. Eraser: a dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems 15, 4 (Nov. 1997), 391--411.
[47]
Cedomir Segulja and Tarek S. Abdelrahman. 2015. Clean: A Race Detector with Cleaner Semantics. In Proceedings of the 42Nd Annual International Symposium on Computer Architecture (ISCA '15). ACM, New York, NY, USA, 401--413.
[48]
Aritra Sengupta, Swarnendu Biswas, Minjia Zhang, Michael D. Bond, and Milind Kulkarni. 2015. Hybrid Static-Dynamic Analysis for Statically Bounded Region Serializability. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '15). ACM, New York, NY, USA, 561--575.
[49]
Aritra Sengupta, Man Cao, Michael D. Bond, and Milind Kulkarni. 2017. Legato: End-to-end Bounded Region Serializability Using Commodity Hardware Transactional Memory. In Proceedings of the 2017 International Symposium on Code Generation and Optimization (CGO '17). IEEE Press, Piscataway, NJ, USA, 1--13. http://dl.acm.org/citation.cfm?id=3049832.3049834
[50]
Konstantin Serebryany and Timur Iskhodzhanov. 2009. ThreadSanitizer: Data Race Detection in Practice. In Proceedings of the Workshop on Binary Instrumentation and Applications (WBIA '09). ACM, New York, NY, USA, 62--71.
[51]
Abhayendra Singh, Daniel Marino, Satish Narayanasamy, Todd Millstein, and Madan Musuvathi. 2011. Efficient Processor Support for DRFx, a Memory Model With Exceptions. In Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems (ASPLOS '11). New York, NY, USA, 53--66.
[52]
Young Wn Song and Yann-Hang Lee. 2014. Efficient Data Race Detection for C/C++ Programs Using Dynamic Granularity. In Parallel and Distributed Processing Symposium, 2014 IEEE 28th International. 679--688.
[53]
Shyamkumar Thoziyoor, Naveen Muralimanohar, Jung Ho Ahn, and Norman P. Jouppi. {n. d.}. CACTI 5.1. Technical Report HPL-2008-20. Hewlett-Packard Labs. http://www.hpl.hp.com/techreports/2008/HPL-2008-20.html
[54]
David Wentzlaff, Nathan Beckmann, Jason Miller, and Anant Agarwal. 2010. Core Count vs Cache Size for Manycore Architectures in the Cloud. Technical Report MIT-CSAIL-TR-2010-008. MIT. http://hdl.handle.net/1721.1/51733
[55]
Benjamin Wester, David Devecsery, Peter M. Chen, Jason Flinn, and Satish Narayanasamy. 2013. Parallelizing Data Race Detection. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems.
[56]
James Wilcox, Parker Finch, Cormac Flanagan, and Stephen N. Freund. 2015. Array Shadow State Compression for Precise Dynamic Race Detection. In Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering (ASE '15).
[57]
Benjamin P. Wood, Luis Ceze, and Dan Grossman. 2014. Low-level Detection of Language-level Data Races with LARD. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '14). ACM, New York, NY, USA, 671--686.
[58]
Yuan Yu, Tom Rodeheffer, and Wei Chen. 2005. RaceTrack: efficient detection of data race conditions via adaptive tracking. In Proceedings of the twentieth ACM symposium on Operating systems principles (SOSP '05). ACM, New York, NY, USA, 221--234.
[59]
Tong Zhang, Dongyoon Lee, and Changhee Jung. 2016. TxRace: Efficient Data Race Detection Using Commodity Hardware Transactional Memory. In Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '16). ACM, New York, NY, USA, 159--173.
[60]
Pin Zhou, Radu Teodorescu, and Yuanyuan Zhou. 2007. HARD: Hardware-Assisted Lockset-based Race Detection. In Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture (HPCA '07). Washington, DC, USA, 121--132.

Cited By

View all
  • (2022)Efficient data race detection of async-finish programs using vector clocksProceedings of the Thirteenth International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3528425.3529101(45-54)Online publication date: 2-Apr-2022
  • (2020)SmartTrack: efficient predictive race detectionProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385993(747-762)Online publication date: 11-Jun-2020
  • (2019)Dependence-aware, unbounded sound predictive race detectionProceedings of the ACM on Programming Languages10.1145/33606053:OOPSLA(1-30)Online publication date: 10-Oct-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
MICRO-50 '17: Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture
October 2017
850 pages
ISBN:9781450349529
DOI:10.1145/3123939
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 October 2017

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. data race detection
  2. hardware support
  3. multithreaded programming

Qualifiers

  • Research-article

Funding Sources

Conference

MICRO-50
Sponsor:

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)76
  • Downloads (Last 6 weeks)11
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Efficient data race detection of async-finish programs using vector clocksProceedings of the Thirteenth International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3528425.3529101(45-54)Online publication date: 2-Apr-2022
  • (2020)SmartTrack: efficient predictive race detectionProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385993(747-762)Online publication date: 11-Jun-2020
  • (2019)Dependence-aware, unbounded sound predictive race detectionProceedings of the ACM on Programming Languages10.1145/33606053:OOPSLA(1-30)Online publication date: 10-Oct-2019
  • (2019)Semantic photo manipulation with a generative image priorACM Transactions on Graphics10.1145/3306346.332302338:4(1-11)Online publication date: 12-Jul-2019
  • (2019)Deep view synthesis from sparse photometric imagesACM Transactions on Graphics10.1145/3306346.332300738:4(1-13)Online publication date: 12-Jul-2019
  • (2019)Detecting Data Race in Network Applications using Static Analysis2019 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA.2019.00061(313-318)Online publication date: Oct-2019
  • (2018)High-coverage, unbounded sound predictive race detectionACM SIGPLAN Notices10.1145/3296979.319238553:4(374-389)Online publication date: 11-Jun-2018
  • (2018)High-coverage, unbounded sound predictive race detectionProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192385(374-389)Online publication date: 11-Jun-2018
  • (2017)Cross-Strait FrenemiesProceedings of the ACM on Human-Computer Interaction10.1145/31347501:CSCW(1-22)Online publication date: 6-Dec-2017
  • (2017)Orca: GC and type system co-design for actor languagesProceedings of the ACM on Programming Languages10.1145/31338961:OOPSLA(1-28)Online publication date: 12-Oct-2017
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media