Jong-Deok Choi
Vivek Sarkar
Manu Sridharan
Skip Abstract Section
Abstract
We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3x to 30x. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.
- A. Aiken and D. Gay. Barrier inference. In Proceedings of the 25th Symposium on Principles of Programming Languages (POPL), pages 342--354, January 1998 Google Scholar
Digital Library
- B. Alpern, et.al. The Jalapeño virtual machine. IBM Systems Journal, 39(1), 2000 Google ScholarDigital Library
- D. F. Bacon, R. E. Strom, and A. Tarafdar. Guava: A dialect of java without data races. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, 2000 Google ScholarDigital Library
- B. Blanchet. Escape analysis for object oriented languages: Application to Java. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999 Google ScholarDigital Library
- J. Bodga and U. Hölzle. Removing unnecessay synchronization in Java. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999 Google ScholarDigital Library
- C. Boyapati and M. Rinard. A parameterized type system for race-free java programs. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, 2001 Google ScholarDigital Library
- M. Burke, P. Carini, J.-D. Choi, and M. Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. In 7th International Workshop on Languages and Compilers for Parallel Computing, 1994. Extended version published as Research Report RC 19546, IBM T. J. Watson Research Center, September, 1994 Google ScholarDigital Library
- G.-I. Cheng, M. Feng, C. E. Leiserson, K. H. Randall, and A. F. Stark. Detecting data races in Cilk programs that use locks. Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998 Google ScholarDigital Library
- J.-D. Choi, B. Alpern, T. Ngo, M. Sridharan, and J. Vlissides. A perturbation-free replay platform for cross-optimized multithreaded applications. In Proceedings of the 15th IEEE International Parallel & Distributed Processing Symposium, April 2001 Google ScholarDigital Library
- J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff. Escape analysis for Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 1--19, 1999 Google ScholarDigital Library
- J.-D. Choi, A. Loginov, and V. Sarkar. Static datarace analysis for multithreaded object-oriented programs. Technical report, IBM Research, 2001. Report RC22146; www.research.ibm.com/jalapeno/dejavu/Google Scholar
- J.-D. Choi and S. L. Min. Race frontier: Reproducing data races in parallel-program debugging. In Proceedings of Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, April 1991 Google ScholarDigital Library
- M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in java programs. Proceedings of the Java Virtual Machine Rsearch and Technology Symposium (JVM'01), April 2001 Google ScholarDigital Library
- A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging, published in ACM SIGPLAN Notices, 26(12):85--96, 1991 Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Type-based race detection for java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 219--232, June 2000 Google ScholarDigital Library
- E. Fredkin. Trie memory. Communications of the ACM, 3(9):490--499, September 1960 Google ScholarDigital Library
- KL Group, 260 King Street East, Toronto, Ontario, Canada. Getting Started with JProbeGoogle Scholar
- Kuck & Associates, Inc., 1906 Fox Drive, Champaign, IL 61820-7345, USA. AssureJ User's Manual, 2.0 Edition, March 1999Google Scholar
- S. L. Min and J.-D. Choi. An efficient cache-based access anomaly detection scheme. In Proceedings of 4th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 1991 Google ScholarDigital Library
- R. H. Netzer and B. P. Miller. What are race conditions? some issues and formalizations. ACM Letters on Programming Languages and Systems, 1(1):74--88, Mar. 1992 Google ScholarDigital Library
- C. v. Praun and T. Gross. Object race detection. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, 2001 Google ScholarDigital Library
- B. Richards and J. R. Larus. Protocol-based data-race detection. In Proceedings of the ACM SIGMETRICS Symposium on Parallel and Distributed Tools, pages 40--47, August 1998 Google ScholarDigital Library
- E. Ruf. Effective synchronzation removal for Java. In SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 208--218, 2000 Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997 Google ScholarDigital Library
- E. Schonberg. On-The-Fly detection of access anomalies. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 285--297, June 1989 Google ScholarDigital Library
- B. Steensgaard. Points-to analysis in almost linear time. In In Proceedings of the Twentythird Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 32--41, January 1996 Google ScholarDigital Library
- N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97--106, 1993Google Scholar
Index Terms
- Efficient and precise datarace detection for multithreaded object-oriented programs
Recommendations
Efficient and precise datarace detection for multithreaded object-oriented programs
PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementationWe present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or ...
On-the-fly race detection in multi-threaded programs
PADTAD '08: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debuggingMulti-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 ...
Fault detection in multi-threaded c++ server applications
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programmingThis paper describes experiments with the freely available tool Helgrind, results obtained by using it for debugging a server application comprising 500 kLOC. We present improvements to the run time analysis of C++ programs that result in a dramatic ...
Comments