Event synchronization analysis for debugging parallel programs

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].

REFERENCES

• Alli85: FX/Series Architecture Manual Concurrency Supplement, Alliant Computer Systems Corp., April 1985.
• 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.
• Bane88: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• CaSu88: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• Cray87: Cray X.MP Multitasking Programmer's Reference Manual, Cray Research, Inc., 1987.
• EmPa88: Perry A. Emrath , David A. Padua, Automatic detection of nondeterminacy in parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.89-99, May 05-06, 1988, Madison, Wisconsin, United States
• GPHL88: M. D. Guzzi , J. P. Hoeflinger , D. A. Padua , D. H. Lawrie, Cedar Fortran and other Vector and parallel Fortran dialects, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.114-121, November 12-17, 1988, Orlando, Florida, United States
• IBM88: IBM Parallel FORTRAN Language and Library Reference, IBM Corp., March 1988.
• 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.
• MiCh88: Barton P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.141-150, May 05-06, 1988, Madison, Wisconsin, United States
• MiPa87: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• PCF88: PCF Fortran: Language Definition, The Parallel Computing Forum, August 1988.
• Scho89: D. Schonberg, On-the-fly detection of access anomalies, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.285-297, June 19-23, 1989, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Design, Performance