Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

One of the major disadvantages of parallel programming with shared memory is the nondeterministic behavior caused by uncoordinated access to shared variables, known as access anomalies. Monitoring program execution to detect access anomalies is a promising and relatively unexplored approach to this problem. We present a new algorithm, referred to as task recycling, for detecting anomalies, and compare it to an existing algorithm. Empirical results indicate several significant conclusions: (i) While space requirements are bounded by &Ogr;(T × V), where T is the maximum number of threads that may potentially execute in parallel and V is the number of variable monitored, for typical programs space requirements are on average &Ogr;(V). (ii) Task recycling is more efficient in terms of space requirements and often in performance. (iii) The general approach of monitoring to detect access anomalies is practical.

REFERENCES

• 1: Todd R. Allen and David A. Padua. Debugging Fortran on a. Shared Memory Machine. In Proceedings of 1he International Conference on Parallel Processing, pages 721-717, Aug 1987.
• 2: 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
• 3: Jong-Deok Choi, Barton P. Miller, and Robert Netzer. Techniques for Debugging Parallel Programs with Flowback Analysis. Technical Report, University of Wisconson, Aug 1988.
• 4: Anne Dinning and Edith Schonberg. Aa Evaluation of Monitoring Algorithms for Access Anomaly Detection. Technical Report Ultracornputer Note #163, New York University, July 1989.
• 5: 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
• 6: Allan Gottlieb. An Overview of the NYU Ultracomputer Project. In J.J. Dongarra, editor, Experimental Parallel Computing Architectures, pages 25 - 95, Elsevier, 1988.
• 7: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 8: 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
• 9: Itzhak Nudler and L#rry Rudolph. Iadetermiaaacy Considered Harmful. 1988.
• 10: Itzhak Nudler and Larry Rudolph. Tools for the Efficient Development of Efficient Parallel Programs. In 1#t Israeli Conference on Computer System En. gineering, 1988.
• 11: 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
• 12: Marc Snir. Private correspondence. 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN
  D.4 OPERATING SYSTEMS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Languages