Ali Jannesari
Walter F. Tichy
ABSTRACT
Multi-core chips enable parallel processing for general purpose applications. Unfortunately, parallel programs may contain synchronization defects. Such defects are difficult to detect due to nondeterministic interleavings of parallel threads. Current tools for detecting these defects produce numerous false alarms, thereby concealing the true defects. This paper describes an extended race detection technique based on a combination of lockset analysis and the happens-before relation. The approach provides more accurate warnings and significantly reduces the number of false positives, while limiting the number of false negatives. The technique is implemented in Helgrind+, an extension of the open source dynamic race detector Helgrind. Experimental results with several applications and benchmarks demonstrate a significant reduction in false alarms at a moderate runtime increase.
- The SPLASH-2 Programs: Characterization and Methodological Considerations, Santa Margherita Ligure, Italy, 1995.Google Scholar
- C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. Technical report, January 2008.Google Scholar
- J.-D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Trans. Program. Lang. Syst., 13(4):491--530, 1991. Google ScholarDigital Library
- J.-D. Choi and S. L. Min. Race frontier: reproducing data races in parallel-program debugging. SIGPLAN Not., 26(7):145--154, 1991. Google ScholarDigital Library
- M. Christiaens and K. D. Bosschere. Trade, a topological approach to on-the-fly race detection in java programs. In JVM'01: Proceedings of the JavaTM Virtual Machine Research and Technology Symposium on JavaTM Virtual Machine Research and Technology Symposium, pages 15--15, Berkeley, CA, USA, 2001. USENIX Association. Google ScholarDigital Library
- E. M. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith. Counterexample-guided abstraction refinement. In Computer Aided Verification, pages 154--169, 2000. Google ScholarDigital Library
- A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. SIGPLAN Not., 26(12):85--96, 1991. Google ScholarDigital Library
- O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded java program test generation. In JGI '01: Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, page 181, New York, NY, USA, 2001. ACM Press. Google ScholarDigital Library
- D. Engler and K. Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. SIGOPS Oper. Syst. Rev., 37(5):237--252, 2003. Google ScholarDigital Library
- J. Gilchrist. Parallel bzip2 (pbzip2):data compression software, 2007.Google Scholar
- J. J. Harrow. Runtime checking of multithreaded applications with visual threads. In Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, pages 331--342, London, UK, 2000. Springer-Verlag. Google ScholarDigital Library
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- S. Lu, J. Tucek, F. Qin, and Y. Zhou. Avio: Detecting atomicity violations via access-interleaving invariants. IEEE Micro, 27(1):26--35, 2007. Google ScholarDigital Library
- F. Mattern. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel and Distributed Algorithms.Google Scholar
- N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, University of Cambridge, UK, 2004.Google Scholar
- N. Nethercote and J. Seward. Valgrind: A program supervision framework. 2003.Google Scholar
- N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. SIGPLAN Not., 42(6):89--100, 2007. Google ScholarDigital Library
- R. H. B. Netzer and B. P. Miller. What are race conditions?: Some issues and formalizations. ACM Lett. Program. Lang. Syst., 1(1):74--88, 1992. Google ScholarDigital Library
- H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. In VM'04: Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, pages 10--10, Berkeley, CA, USA, 2004. USENIX Association. Google ScholarDigital Library
- R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. SIGPLAN Not., 38(10):167--178, 2003. Google ScholarDigital Library
- V. Pankratius, C. Schaefer, A. Jannesari, and W. F. Tichy. Software engineering for multicore systems: an experience report. In IWMSE '08: Proceedings of the 1st international workshop on Multicore software engineering, pages 53--60, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- E. Pozniansky and A. Schuster. Multirace: efficient on-the-fly data race detection in multithreaded c++ programs: Research articles. Concurr. Comput.: Pract. Exper., 19(3):327--340, 2007. Google ScholarDigital Library
- B. Richards and J. R. Larus. Protocol-based data-race detection. In SPDT '98: Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, pages 40--47, New York, NY, USA, 1998. ACM. Google ScholarDigital Library
- M. Ronsse and K. D. Bosschere. Recplay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17(2):133--152, 1999. Google ScholarDigital Library
- P. Sack, B. E. Bliss, Z. Ma, P. Petersen, and J. Torrellas. Accurate and efficient filtering for the intel thread checker race detector. In ASID '06: Proceedings of the 1st workshop on Architectural and system support for improving software dependability, pages 34--41, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst., 15(4):391--411, 1997. Google ScholarDigital Library
- J. Seward. bzip2: A free data compressor, 2007.Google Scholar
- Valgrind-project. Helgrind: a data-race detector, 2007.Google Scholar
- C. von Praun and T. R. Gross. Object race detection. SIGPLAN Not., 36(11):70--82, 2001. Google ScholarDigital Library
- Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. SIGOPS Oper. Syst. Rev., 39(5):221--234, 2005. Google ScholarDigital Library
Index Terms
- On-the-fly race detection in multi-threaded programs
Recommendations
What are race conditions?: Some issues and formalizations
In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause ...
Sound predictive race detection in polynomial time
POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesData races are among the most reliable indicators of programming errors in concurrent software. For at least two decades, Lamport's happens-before (HB) relation has served as the standard test for detecting races--other techniques, such as lockset-based ...
Sound predictive race detection in polynomial time
POPL '12Data races are among the most reliable indicators of programming errors in concurrent software. For at least two decades, Lamport's happens-before (HB) relation has served as the standard test for detecting races--other techniques, such as lockset-based ...
Comments