Abstract
Detecting data race is an important debugging problem that should be solved in the shared-memory parallel programs. To attack this problem, considerable works have been developed in the literature. In particular, detecting data races on-the-fly is regarded as more efficient strategy. However, the time and space overhead required to perform the technique on-the-fly is still considered as a serious problem. This paper presents a practical method to improve the problem. The target model of our method for detecting data race on-the-fly is the shared-memory programs with nested fork-join parallelism. The method presented here shows that it is more efficient in the complexity of space and time over previous techniques. Thus, it makes the technique for detecting data race on-the-fly more practical. The worst-case of space and time required to apply our method to the parallel programs are O(VT) and O(T) respectively.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Audenaert, K.: Maintaining Concurrency Information for On-the-fly Data Race detection. Parallel Computing 97. North-Holland (1997) 1–8
Audenaert, K.: Clock Trees: Logical Clocks for Programs with Nested Parallelism. Tr. on software Engineering IEEE (1997) 646–658
Brad Richards, James R. Larus: Protocol-based data-race detection, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools. ACM (1998)
Choi, J., and S.L. Min: Race Frontier: Reproducing Data Races in Parallel-Program debugging. 3rd Symp. on Principles and Practice of Parallel Programming. ACM (1991) 145–154
Dinning, A., and Schonberg, E.: An Empirical Comparison of Monitoring Algorithms for Access Anomaly Detection. 2nd Symp. on Principles and Practice of Parallel Programming. ACM (1990) 1–10
Dinning, A., and Schonberg, E.: Detecting Access Anomalies in Programs with Critical Sections. Proc. Workshop on Parallel and Distributed Debugging. ACM/ONR (1991) 79–90
Jun, Y., and Koh, K.: On-the-fly Detection of Access Anomalies in Nested Parallel Loops. 3rd Workshop on Parallel and Distributed Debugging. ACM (1993) 107–117
Kim, J., and Jun, Y.: Scalable On-the-fly Detection of the First Races in Parallel Programs. 12nd Int’l. Conf. on Supercomputing. Melbourne, Australia. ACM (1998) 345–352
Kim, J., Han, D., Yu, C.: Parallel loop transformation technique for efficient race detection. Parallel and Distributed Systems, 2001. Proceedings. Eighth International Conference on. IEEE (2001) 265–272
Lamport, L.: Time, Clocks, and the Ordering of Events in Distributed System. Communications of the ACM (1978) 558–565
Mellor-Crummey, J.: On-the-fly Detection of Data Races for Programs with Nested Fork-Join Parallelism. Supercomputing ‘91. ACM/IEEE (1991) 24–33
Michiel R., Koen De Bosschere: RecPlay. Transactions on Computer Systems. ACM (1999)
Netzer, R.H.B., and Miller: Improving the Accuracy of Data Race Detection,” 3rd Symp. on Principles and Practice of Parallel Programming. ACM (1991) 133–144
Netzer, R.H.B., and Miller: Detecting data races in parallel executions. Advances in Language and Compilers for Parallel Processing. MIT (1990) 109–130
OpenMP Architecture Review Board.: OpenMP Fortran Application Program Interface, Version 2.0 (2000)
Schonberg, E.: On-the-Fly Detection of Access Anomalies. In proceedings on the SIGPLAN conference on Programming Language Design and Implementation. ACM (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ryu, EK., Ha, KS., Yoo, KY. (2002). A Practical Method for On-the-Fly Data Race Detection. In: Fagerholm, J., Haataja, J., Järvinen, J., Lyly, M., Råback, P., Savolainen, V. (eds) Applied Parallel Computing. PARA 2002. Lecture Notes in Computer Science, vol 2367. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48051-X_27
Download citation
DOI: https://doi.org/10.1007/3-540-48051-X_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43786-4
Online ISBN: 978-3-540-48051-8
eBook Packages: Springer Book Archive