TRADE: Precise Dynamic Race Detection for Scalable Transactional Memory Systems

Abstract

As other multithreaded programs, transactional memory (TM) programs are prone to race conditions. Previous work focuses on extending existing definitions of data race for lock-based applications to TM applications, which requires all transactions to be totally ordered “as if” serialized by a global lock. This approach poses implementation constraints on the STM that severely limits TM applications’ performance.

This article shows that forcing total ordering among all running transactions, while sufficient, is not necessary. We introduce an alternative data race definition, relaxed transactional data race, that requires ordering of only conflicting transactions. The advantages of our relaxed definition are twofold: First, unlike the previous definition, this definition can be applied to a wide range of TMs, including those that do not enforce transaction total ordering. Second, within a single execution, it exposes a higher number of data races, which considerably reduces debugging time. Based on this definition, we propose a novel and precise race detection tool for C/C++ TM applications (TRADE), which detects data races by tracking happens-before edges among conflicting transactions.

Our experiments reveal that TRADE precisely detects data races for STAMP applications running on modern STMs with overhead comparable to state-of-the-art race detectors for lock-based applications. Our experiments also show that in a single run, TRADE identifies several races not discovered by 10 separate runs of a race detection tool based on the previous data race definition.

References

1. M. Abadi, T. Harris, and K. F. Moore. 2010. A model of dynamic separation for transactional memory. Inf. Comput. 1093--1117.
2. A. Adl-Tabatabai, T. Shpeisman, and J. Gottschlich. Feb. 2012. Draft Specification for Transactional Features in C++. Version 1.1.
3. S. V. Adve and M. D. Hill. 1998. Weak ordering a new definition. In Proc. of the International Symposia on Computer Architecture (ISCA’98). 363--375.
4. H.-J. Boehm. 2009. Transactional memory should be an implementation technique, not a programming interface. In Proc. of the 1st USENIX Conference on Hot Topics in Parallelism. 15--15.
5. D. Christie, J. Chung, S. Diestelhorst, M. Hohmuth, M. Pohlack, C. Fetzer, M. Nowack, T. Riegel, P. Felber, P. Marlier, and E. Riviere. 2010. Dresden TM compiler (DTMC). In Proc. of the 5th ACM European Conference on Computer Systems.
6. TM compiler support in gcc 4.7. 2010. Project Web Site. Retrieved from http://gcc.gnu.org/gcc-4.7/changes.html.
7. L. Dalessandro and M. L. Scott. 2009. Strong isolation is a weak idea. In Proc. of the 4th Workshop on Transactional Computing.
8. L. Dalessandro, M. F. Spear, and M. L. Scott. 2010. NOrec: Streamlining STM by abolishing ownership records. In Proc. of the 15th Symposium on Principles and Practice of Parallel Programming.
9. R. Dias and B. C. Teixeira. 2009. Ajex: A source-to-source Java STM framework compiler. Technical Report. DI-FCT/UNL.
10. D. Dice, Y. Lev, M. Moir, and D. Nussbaum. 2009. Early experience with a commercial hardware transactional memory implementation. In Proc. of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’09).
11. D. Dice, O. Shalev, and N. Shavit. 2006. Transactional locking II. In Proc. of the 20th International Symposium on Distributed Computing.
12. A. Dinning and E. Schonberg. 1991. Detecting access anomalies in programs with critical sections. In Proc. of the 1991 ACM/ONR Workshop on Parallel and Distributed Debugging.
13. T. Elmas, S. Qadeer, and S. Tasiran. 2007. Goldilocks: A race and transaction-aware java runtime. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation.
14. C. Flanagan and S. N. Freund. 2009. FastTrack: Efficient and precise dynamic race detection. In Proc. of the Conference on Programming Language Design and Implementation. 121--133.
15. D. Grossman, J. Manson, and W. Pugh. 2006. What do high-level memory models mean for transactions? In Proc. of the Workshop on Memory System Performance and Correctness. 62--69.
16. S. Gupta, F. Sultan, S. Cadambi, F. Ivancic, and M. Rotteler. 2009. Using hardware transactional memory for data race detection. In Proc. 23rd International Parallel and Distributed Processing Symposium.
17. R. Haring. 2011. The Blue gene/Q compute chip. In The 23rd Symposium on High Performance Chips.
18. T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. 2005. Composable memory transactions. In Proc. of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’05). 48--60.
19. M. Herlihy and Y. Lev. 2009. tm db: A generic debugging library for transactional programs. In Proc. 18th International Conference on Parallel Architectures and Compilation Techniques.
20. Intel Corporation. May 2009. Intel Transactional Memory Compiler and Runtime Application Binary Interface. Document No. 318523-002US, revision 1.1.
21. K. Huang. 2003. Data-Race Detection in Transactions-Everywhere Parallel Programming. M.S Thesis, the Massachusetts Institute of Technology.
22. G. Kestor, R. Gioiosa, T. Harris, O. S. Unsal, A. Cristal, I. Hur, and M. Valero. 2011. STM2: A parallel STM for high performance simultaneous multithreading systems. In Proc. of the 2011 International Conference on Parallel Architectures and Compilation Techniques (PACT’11). 221--231.
23. G. Kestor, O. S. Unsal, A. Cristal, and S. Tasiran. 2014. T-Rex: A dynamic race detection tool for C/C++ transactional memory applications. In Proc. of the 9th European Conference on Computer Systems (EuroSys’14). ACM, New York, NY, Article 20, 12 pages. DOI:http://dx.doi.org/10.1145/2592798.2592809
24. L. Lamport. 1978. Time clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7.
25. C. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. 2005. Pin: Building customized program analysis tools with dynamic instrumentation. In Proc. of the Conference on Programming Language Design and Implementation.
26. V. Menon, S. Balensiefer, T. Shpeisman, A. Adl-Tabatabai, R. L. Hudson, B. Saha, and A. Welc. 2008. Practical weak-atomicity semantics for Java STM. In Proc. of the Annual Symposium on Parallelism in Algorithms and Architectures. 314--325.
27. C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. 2008. STAMP: Stanford transactional applications for multi-processing. In Proc. of the International Symposium on Workload Characterization.
28. M. Naik, A. Aiken, and J. Whaley. 2006. Effective static race detection for Java. In Proc. of the ACM Conference on Programming Language Design and Implementation.
29. T. Riegel, C. Fetzer, and P. Felber. 2007. Time-based transactional memory with scalable time bases. In 19th ACM Symposium on Parallelism in Algorithms and Architectures.
30. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. 1997. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15, 4.
31. M. Schindewolf, A. Cohen, W. Karl, A. Marongiu, and L. Benini. 2009. Towards transactional memory support for GCC. In GCC Research Opportunities Workshop (GROW’09).
32. D. Schonberg. 1989. On-the-fly detection of access anomalies. In Proc. of the ACM Conference on Programming Language Design and Implementation.
33. T. Shpeisman, A. Adl-Tabatabai, R. Geva, Y. Ni, and A. Welc. 2009. Towards transactional memory semantics for C++. In Proc. of the 21st Annual Symposium on Parallelism in Algorithms and Architectures.
34. Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. 2012. Sound predictive race detection in polynomial time. In Proc. of the Symposium on Principles of Programming Languages. 387--400.
35. Rochester software transactional memory runtime. 2010. www.cs.rochester.edu/research/synchronization/rstm/.
36. B. C. Teixeira, J. Lourenco, and D. Sousa. 2010. A static approach for detecting concurrency anomalies in transactional memory. In Proc. of InForum 2010.
37. C. Von Praun and T. R. Gross. 2001. Object race detection. In Proc. of the 16th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications.
38. F. Zyulkyarov, T. Harris, O. S. Unsal, A. Cristal, and M. Valero. 2010. Debugging programs that use atomic blocks and transactional memory. In Proc. of the Symposium on Principles and Practice of Parallel Computing.

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

    • Concurrent programming languages

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software notations and tools

    • General programming languages

      • Language types

        • Concurrent programming languages