멀티 스레드 프로그램에서의 자료경합의 동적 분석을 위한 필터링 기술 연구
A Study on Filtering Techniques for Dynamic Analysis of Data Races in Multi-threaded Programs
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we introduce three monitoring filtering techniques which reduce the overheads of dynamic data race detection. It is well known that detecting data races dynamically in multi-threaded programs is quite hard and troublesome task, because the dynamic detection techniques need to monitor all execution of a multi-threaded program and to analyse every conflicting memory and thread operations in the program. Thus, the main drawback of the dynamic analysis for detecting data races is the heavy additional time and space overheads for running the program. For the practicality, we also empirically compare the efficiency of three monitoring filtering techniques. The results using OpenMP benchmarks show that the filtering techniques are practical for dynamic data race detection, since they reduce the average runtime overhead to under 10% of that of the pure detection.
Abstract
In this paper, we introduce three monitoring filtering techniques which reduce the overheads of dynamic data race detection. It is well known that detecting data races dynamically in multi-threaded programs is quite hard and troublesome task, because the dynamic detection techniques need to monitor all execution of a multi-threaded program and to analyse every conflicting memory and thread operations in the program. Thus, the main drawback of the dynamic analysis for detecting data races is the heavy additional time and space overheads for running the program. For the practicality, we also empirically compare the efficiency of three monitoring filtering techniques. The results using OpenMP benchmarks show that the filtering techniques are practical for dynamic data race detection, since they reduce the average runtime overhead to under 10% of that of the pure detection.
참고문헌 (19)
- Netzer, Robert H. B, "What are Race Conditions?: Some Issues and Formalizations", Proceeding of Letters on Programming Languages and Systems, LOPLAS 1992, pp.74~88 (1992), ACM
- E. Farchi, "Concurrent Bug Patterns and How to Test Them", Proceeding of the 17th International Symposium on Parallel and Distributed Processing, IPDPS 2003, 7 (2003), IEEE
- U. Banerjee, "A Theory of Data Race Detection", Proceedings of the 2006 workshop on Parallel and distributed systems: testing and debugging, PADTAD 2006, pp.69~78 (2006), ACM
- N. G. Leveson, "An Investigation of the Therac-25 Accidents", IEEE Computer, 26(7), pp.18~41 (1993)
- Final Report on the August 14, 2003 Blackout in the United States and Canada: Causes and Recommendations, "U. S. A", U.S.-Canada Power System Outage Task Force, ~ (2003)
- D. Callahan, "Static Analysis of Low-level Synchronization", SIGPLAN Not, 24(1), pp.100~111 (1988), ACM
- C. E. McDowell, "A Practical Algorithm for Static Analysis of Parallel Programs", Journal of Parallel and Distributed Computing, 6(3), pp.515~536 (1989), Springer-verlag
- D. Engler, "RacerX: Effective, Static Detection of Race Conditions and Deadlocks", Proceedings of the nineteenth ACM symposium on Operating systems principles, SOSP 2003, pp.237~252 (2003), ACM
- Ha, O.-K, "Case Study of Dynamic Detectors for Data Races", Proceeding of International Conference on Electronic Engineering and Computer Science (EECS 2013), IERI Procedia, 4, pp.174~180 (2013)
- C. Flanagan, "FastTrack: Efficient and Precise Dynamic Race Detection", Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, pp.121~133 (2009), ACM
- Ha, O.-K, "An Efficient Algorithm for On-the-fly Data Race Detection Using an Epoch-Based Technique", Journal of Scientific Programming (2015)
- T. Elmas, "Goldilocks: A Race and Transaction-aware Java Runtime", Proceedings of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI 2007, pp.245~255 (2007), ACM
- A. Jannesari, "Helgrind+: An Efficient Dynamic Race Detector", Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing, IPDPS 2009, pp.1~13 (2009), IEEE
- Ha, O.-K, "Effective Monitoring Memory Operations for Dynamic Race Detection through Hierarchical Filtering Method", International Journal of Multimedia and Ubiquitous Engineering, 9(4), pp.199~208 (2014)
- Ha, O.-K, "On-the-fly Detection of Data Races in OpenMP Programs", Proceeding of the 2012 Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD'2012), pp.1~10 (2012), ACM, Minneapolis
- Park, S.-W, "A Loop Filtering Technique for Reducing Time Overhead of Dynamic Data Race Detection", Proceeding of the 8th International Conference on Database Theory and Application (DTA 2015), pp.29~32 (2015), IEEE
- H. Patil, "Pinplay: A Framework for Deterministic Replay and Reproducible Analysis of Parallel Programs", Proceeding of the 8th annual IEEE, 2010, 2~11[DOI]
- A. R. Bernat, "Anywhere, Any-time Binary Instrumentation", Proceedings of the 10th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools, PASTE 2011, pp.9~16 (2011), ACM
- A. J. Dorta, "The OpenMP Source Code Repository", Proceedings of the 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing, pp.244~250 (2005)