Abstract
We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NP-complete to detect race conditions in programs that use polynomial number of semaphores [10]. We show in this paper that it remains NP-complete even if the programs are allowed to use only two semaphores, which settles the open question raised in [10]. The proof uses a technique that simulates a graph with any number of semaphores by a graph with only two semaphores.
For the case of single semaphore, Lu et al. [8] give the previously only-known polynomial-time algorithm that runs in time O(n1.5 p), where p is the number of processors and n is the total number of semaphore operations executed. Their algorithm, however, detects only a special class of race conditions. In this paper we cope with the general race-condition detection problem and give an O(np log n) -time algorithm.The output of our algorithm is a compact representation of size Θ(np), from which one can determine in constant time whether a race condition exists between two given operations. Our algorithm is near-optimal in that the time it takes is only O(log n) times the time required simply to write down the output.
The detailed version of this extended abstract can be located at the following URL: http://www.cs.brown.edu/people/hil/research/publication/mhb.ps.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdel-Wahab, H. M., “Scheduling with Application to Register Allocation and Deadlock Problems”, U. of Waterloo, PhD Thesis, 1976.
Abdel-Wahab, H.M. & Kameda, T., “Scheduling to Minimize Maximum Cumulative Cost Subject to Series-parallel Precedence Constraints”, Operations Research 26 (1978), 141–158.
Abdel-Wahab, H. M. & Kameda, T., “On Strictly Optimal Schedules for the Cumulative Cost-Optimal Scheduling Problem”, Computing 24 (1980), 61–86.
Emrath, P. A., Ghosh, S. & Padua, D. A., “Event Synchronization Analysis for Debugging Parallel Programs”, Supercomputing '89 (1989), 580–588.
Garey, M. R. & Johnson, D. S., “Computers and Intractability—A Guide to the Theory of NP-Completeness”, 1979.
Helmbold, D. P. & McDowell, C. E., “A Class of Synchronization Operations that Permit Efficient Race Detection”, U. of California at Santa Cruz Technical Report (1993).
Helmbold, D. P., McDowell, C. E. & Wang, J-Z., “Analyzing Traces with Anonymous Synchronization”, Int. Conf. on Parallel Processing (August 1990), II70-II77.
Lu, H-I., Klein, P. N. & Netzer, R. H. B., “Detecting Race Conditions in Parallel Programs that Use One Semaphore”, Workshop on Algorithms and Data Structures 3 (1993), 471–482.
Netzer, R. H. B. & Ghosh, S., “Efficient Race Condition Detection for Shared-Memory Programs with Post/Wait Synchronization”, Int. Conf. on Parallel Processing (1992), II242–II246.
Netzer, R. H. B. & Miller, B. P., “On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions”, Int. Conf. on Parallel Processing (1990), II93–II97.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klein, P.N., Lu, HI., Netzer, R.H.B. (1996). Race-condition detection in parallel computation with semaphores (extended abstract). In: Diaz, J., Serna, M. (eds) Algorithms — ESA '96. ESA 1996. Lecture Notes in Computer Science, vol 1136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61680-2_74
Download citation
DOI: https://doi.org/10.1007/3-540-61680-2_74
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61680-1
Online ISBN: 978-3-540-70667-0
eBook Packages: Springer Book Archive