Abstract
The increase in the number and complexity of parallel programs has led to a need for better approaches for synchronization error detection and debugging of parallel programs. This paper presents an efficient and precise algorithm for the detection of nondeterminacy (race conditions) in parallel programs. Non determinacy exists in a program when the program yields different outputs for different runs with the same input. We limit our attention to nondeterminacy due to errors in synchronization and to race conditions due to these unsynchronized accesses to shared variables. A directed acyclic graph called a task graph is used to represent the accesses to shared variables in a parallel program with edges representing guaranteed ordering. The algorithm proposed here constructs an augmented task graph, and then uses a modification of depth-first search to classify the edges in the augmented task graph. The edges are analyzed and the nodes that are guaranteed to execute before an event are linked to these events by edges representing guaranteed ordering among events. This ordering is used to detect any race conditions in parallel programs.
Supported in part by an NSF Young Investigator Award CCR-9457768, an NSF grant CCR-9210422, and by the Louisiana Board of Regents through contract LEQSF (1991–94)-RD-A-09.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Allen, T. R. and D. A. Padua, “Debugging Fortran on a Shared Memory Machine,” Proc. Intl. Conf. Parallel Processing, pp. 721–727, St. Charles, IL, Aug. 1987.
Balasundaram, V. and K. Kennedy, “Compile-time Detection of Race Conditions in a Parallel Program,” Proc. 3rd Intl. Conf. Supercomputing, pp. 175–185, Jun. 1989.
Bernstein, A. J., “Analysis of Programs for Parallel Processing,” Proc. IEEE Trans. on Electronic Computers, EC-15(5), pp. 757–763, Oct. 1966.
Callahan, D., K. Kennedy and J. Subhlok, “Analysis of Event Synchronization in a Parallel Programming Tool,” Proc. 2nd Symposium on the Principle and Practice of Parallel Programming, pp. 21–30, Mar. 1990.
Callahan D. and J. Subhlok, “Static Analysis of Low-Level Synchronization,” Proc. SIGPLAN Workshop on Parallel and Distributed Debugging, pp. 100–111, May. 1988.
Choi, J., B. P. Miller and R. H. B. Netzer “Techniques for Debugging Parallel Programs with Flowback Analysis,” ACM Trans. Programming Languages and Systems, pp. 491–530, Vol. 13, No. 4, Oct. 1991.
Emrath, P. A., S. Ghosh and D. A. Padua, “Event Synchronization Analysis for Debugging Parallel Programs,” Proc. Supercomputing 89, ACM Press, New York pp. 580–588, 1989.
Emrath, P. A., S. Ghosh and D. A. Padua, “Detecting Nondeterminacy in Parallel Programs,” IEEE Software, pp. 69–77, Jan. 1992.
Emrath, P. A. and D. A. Padua, “Automatic Detection of Nondeterminacy in Parallel Programs,” Proc. SIGPLAN Workshop on Parallel and Distributed Debugging, pp. 89–99, May. 1988.
Even, Shimon, Graph Algorithms, Computer Science Press, 1976.
Ghosh, S., “Automatic Detection of Nondeterminacy and Scalar Optimizations in Parallel Programs,” Ph.D. Thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1992.
Helmbold, D. P., C. E. McDowell and J. Wang, “Analyzing Traces for Anonymous Synchronization,” Proc. Intl. Conf. Parallel Processing, pp. 70–77, St. Charles, IL, Aug. 1990.
Helmbold, D. P., C. E. McDowell and J. Wang, “Determining Possible Event Orders by Analyzing Sequential Traces,” IEEE Trans. Parallel and Distributed Systems, pp. 827–839, Vol. 4, No. 7, Jul. 1993.
Hood, R., K. Kennedy and J. Mellor-Crummey, “Parallel Program Debugging with On-the-fly Anomaly Detection,” Proc. Supercomputing 90, New York pp. 74–81, Nov. 1990.
McDowell, C. E. and D. P. Helmbold, “Computing Reachable States of Parallel Programs,” Proc. ACM/ONR Workshop on Parallel and Distributed Debugging, pp. 89–99, May. 1991.
Miller, B. P. and J. Choi, “A Mechanism for Efficient Debugging of Parallel Programs,” Proc. ACM SIGPLAN Conf. on Programming Lang. Design and Implementation, pp. 135–144, Jun. 1988.
Netzer, R. H. B., “Race Condition Detection for Debugging Shared-Memory Parallel Programs,” Ph.D. Thesis, Dept. of Computer Science, University of Wisconsin-Madison, 1991.
Netzer, R. H. B. and S. Ghosh, “Efficient Race Condition Detection for Shared-Memory Programs with Post/Wait Synchronization,” Proc. Intl. Conf. Parallel Processing, Aug. 1992.
Netzer, R. H. B. and B. P. Miller, “On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions,” Proc. Intl. Conf. Parallel Processing, II-93-II-97, Aug. 1990.
Netzer, R. H. B. and B. P. Miller, “What are Race Conditions? Some Issues and Formalizations,” ACM Letters on Programming Languages and Systems, Vol. 1 No. 1, Mar. 1992.
Ramanujam, J. and Ashvin Mathew, “Detection of Nondeterminacy in Parallel Programs,” Technical Report 94-01-03, Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, Jan. 1994.
Schonberg, E., “On-the-fly Detection of Access Anomalies,” Proc. ACM SIGPLAN Conf. on Programming Lang. Design and Implementation, pp. 285–297, Jul. 1989.
Tarjan, R., “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing, Vol. 1, pp. 146–160, 1972.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ramanujam, J., Mathew, A. (1995). Analysis of event synchronization in parallel programs. In: Pingali, K., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1994. Lecture Notes in Computer Science, vol 892. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0025886
Download citation
DOI: https://doi.org/10.1007/BFb0025886
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58868-9
Online ISBN: 978-3-540-49134-7
eBook Packages: Springer Book Archive