P. A. Emrath
D. A. Padua
ABSTRACT
One of the major difficulties of explicit parallel programming for a shared memory machine model is detecting the potential for nondeterminacy and identifying its causes. There will often be shared variables in a parallel program, and the tasks comprising the program may need to be synchronized when accessing these variables.
This paper discusses this problem and presents a method for automatically detecting non-determinacy in parallel programs that utilize event style synchronization instructions, using the Post, Wait, and Clear primitives. With event style synchronization, especially when there are many references to the same event, the difficulty lies in computing the execution order that is guaranteed given the synchronization instructions and the sequential components of the program. The main result in this paper is an algorithm that computes such an execution order and yields a Task Graph upon which a nondeterminacy detection algorithm can be applied.
We have focused on events because they are a frequently used synchronization mechanism in parallel versions of Fortran, including Cray [Cray87], IBM [IBM88], Cedar [GPHL88], and PCF Fortran [PCF88].
- Alli85.FX/Series Architecture Manual Concurrency Supplement, Alliant Computer Systems Corp., April 1985.Google Scholar
- AlPa87.Todd R. Allen, and David A. Padua. Debugging Fortran on a Shared Memory Machine, Proceedings of the 1987 International Conference on Parallel Processing, pp. 721-727, Aug. 1987.Google Scholar
- Bane88.Utpal Banerjee. Dependence Analysis for Supercomputing, Kluwer Academic Pubfishers, 1988. Google ScholarDigital Library
- CaSu88.David Callahan, and Jaspal Subhlok. Static Analysis of Low-level Synchronization, Proceedings of the Workshop on Parallel and Distributed Debugging, pp. 100-111, May 1988. Google ScholarDigital Library
- Cray87.Cray X.MP Multitasking Programmer's Reference Manual, Cray Research, Inc., 1987.Google Scholar
- EmPa88.Perry A. Emrath, and David A. Padua. Automatic Detection of Nondeterminacy in Parallel Programs, Proceedings, Workshop on Parallel and Distributed Debugging, pp. 89-09, May 1988. Google ScholarDigital Library
- GPHL88.M. D. Guzzi, D. A. Padua, J. P. Hoeflinger, and D. H. Lawrie. Cedar Fortran and O~her Vector and Parallel Fortran Dialects, Proceedings SUPERCOMPUT- ING '88, pp. 114-121, Nov. 1988. Google ScholarDigital Library
- IBM88.IBM Parallel FORTRAN Language and Library Reference, IBM Corp., March 1988.Google Scholar
- KDLS86.D. Kuck, E. Davidson, D. Lawrie, and A. Sameh. Parallel supercomputin9 todav and the Cedar approach, Science, vol. 231, pp. 967'-974, Feb. 1986.Google ScholarCross Ref
- MiCh88.Barton P. Miller, and Jong-Deok Choi. A Mechanism for Efficient Debugging of Parallel Programs, Proceedings of the Workshop on Parallel and Distributed Debugging, pp. 141-150, May 1988. Google ScholarDigital Library
- MiPa87.S.P. Midkiff~ and D. A. Padua. Compiler Algorithms for Synchronization, IEEE transaetlons on Computers, vol. C-36, No. 12, pp. 1485-1495, Dec. 1987. Google ScholarDigital Library
- PCF88.PCF Fortran: Language Definition, The Parallel Computing Forum, August 1988.Google Scholar
- Scho89.On-The-Fly Detection of Access Anomalies, Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, pp. 285-297, June 1989. Google ScholarDigital Library
Index Terms
- Event synchronization analysis for debugging parallel programs
Recommendations
Parallel assertions for debugging parallel programs
MEMOCODE '11: Proceedings of the Ninth ACM/IEEE International Conference on Formal Methods and Models for CodesignA parallel program must execute correctly even in the presence of unpredictable thread interleavings. This interleaving makes it hard to write correct parallel programs, and also makes it hard to find bugs in incorrect parallel programs. A range of ...
Compiling data-parallel programs for clusters of SMPs: Research Articles
Compilers for Parallel ComputersClusters of shared-memory multiprocessors (SMPs) have become the most promising parallel computing platforms for scientific computing. However, SMP clusters significantly increase the complexity of user application development when using the low-level ...
Comments