A Study on Filtering Techniques for Dynamic Analysis of Data Races in Multi-threaded Programs (멀티 스레드 프로그램에서의 자료경합의 동적 분석을 위한 필터링 기술 연구)

Ok-Kyoon Ha (하옥균); Hongseok Yoo (유홍석)

doi:10.9708/jksci.2017.22.11.001

A Study on Filtering Techniques for Dynamic Analysis of Data Races in Multi-threaded Programs

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2017, 22(11), pp.1-7
DOI : 10.9708/jksci.2017.22.11.001
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science
Received : October 13, 2017
Accepted : November 14, 2017
Published : November 30, 2017

Ok-Kyoon Ha ¹, Hongseok Yoo ¹

¹경운대학교

Accredited

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.

KEYWORDS

Data races, Data race detection, Dynamic analysis, Monitoring filtering techniques, multi-threaded programs, Efficiency

Citation status

* References for papers published after 2023 are currently being built.

[confproc] Netzer, Robert H. B / 1992 / What are Race Conditions?: Some Issues and Formalizations / Proceeding of Letters on Programming Languages and Systems, LOPLAS 1992 / ACM : 74~88

[confproc] E. Farchi / 2003 / Concurrent Bug Patterns and How to Test Them / Proceeding of the 17th International Symposium on Parallel and Distributed Processing, IPDPS 2003 / IEEE 7

[confproc] U. Banerjee / 2006 / A Theory of Data Race Detection / Proceedings of the 2006 workshop on Parallel and distributed systems: testing and debugging, PADTAD 2006 / ACM : 69~78

[journal] N. G. Leveson / 1993 / An Investigation of the Therac-25 Accidents / IEEE Computer 26(7) : 18~41

[report] U. S. A / 2003 / Final Report on the August 14, 2003 Blackout in the United States and Canada: Causes and Recommendations / U.S.-Canada Power System Outage Task Force

[journal] D. Callahan / 1988 / Static Analysis of Low-level Synchronization / SIGPLAN Not / ACM 24(1) : 100~111

[journal] C. E. McDowell / 1989 / A Practical Algorithm for Static Analysis of Parallel Programs / Journal of Parallel and Distributed Computing / Springer-verlag 6(3) : 515~536

[confproc] D. Engler / 2003 / RacerX: Effective, Static Detection of Race Conditions and Deadlocks / Proceedings of the nineteenth ACM symposium on Operating systems principles, SOSP 2003 / ACM : 237~252

[confproc] Ha, O.-K / 2013 / Case Study of Dynamic Detectors for Data Races / Proceeding of International Conference on Electronic Engineering and Computer Science (EECS 2013), IERI Procedia 4 : 174~180

[confproc] C. Flanagan / 2009 / FastTrack: Efficient and Precise Dynamic Race Detection / Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009 / ACM : 121~133

[journal] Ha, O.-K / 2015 / An Efficient Algorithm for On-the-fly Data Race Detection Using an Epoch-Based Technique / Journal of Scientific Programming

[confproc] T. Elmas / 2007 / Goldilocks: A Race and Transaction-aware Java Runtime / Proceedings of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI 2007 / ACM : 245~255

[confproc] A. Jannesari / 2009 / Helgrind+: An Efficient Dynamic Race Detector / Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing, IPDPS 2009 / IEEE : 1~13

[journal] Ha, O.-K / 2014 / Effective Monitoring Memory Operations for Dynamic Race Detection through Hierarchical Filtering Method / International Journal of Multimedia and Ubiquitous Engineering 9(4) : 199~208

[confproc] Ha, O.-K / 2012 / 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) / ACM, Minneapolis : 1~10

[confproc] Park, S.-W / 2015 / 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) / IEEE : 29~32

[confproc] H. Patil / 2010 / Pinplay: A Framework for Deterministic Replay and Reproducible Analysis of Parallel Programs / Proceeding of the 8th annual IEEE/ACM international symposium on Code generation and optimization, CGO 2010 / ACM : 2~11

[confproc] A. R. Bernat / 2011 / Anywhere, Any-time Binary Instrumentation / Proceedings of the 10th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools, PASTE 2011 / ACM : 9~16

[confproc] A. J. Dorta / 2005 / The OpenMP Source Code Repository / Proceedings of the 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing : 244~250

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

A Study on Filtering Techniques for Dynamic Analysis of Data Races in Multi-threaded Programs

ABSTRACT

KEYWORDS

Citation status

* References for papers published after 2023 are currently being built.

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

A Study on Filtering Techniques for Dynamic Analysis of Data Races in Multi-threaded Programs

ABSTRACT

KEYWORDS

Statistics

Tools

Issue List

Citation status

KCI Citation Counts (0)

REFERENCES (19) * References for papers published after 2023 are currently being built.

Search PDF

Citation

* References for papers published after 2023 are currently being built.