On-the-fly detection of access anomalies

ABSTRACT

Access anomalies are a common class of bugs in shared-memory parallel programs. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. Approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring. A general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchronization operations. The advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. In the algorithm presented, the amount of storage required at any time depends only on the number V of shared variables being monitored and the number N of threads, not on the number of synchronizations. Data compression is achieved by the use of two techniques called merging and subtraction. Upper bounds on storage are shown to be V × N2 for merging and V × N for subtraction.

REFERENCES

• All: T.R. Allen, D.A. Padua, "Debugging Fortran on a Shared Memory Machine", Proe. International Conf. on Parallel Processing, August 1987, pp. 721-727.
• App: B. Appelbe , C. E. McDowell, Developing multitasking applications programs, Proceedings of the Twenty-First Annual Hawaii International Conference on Software Track, p.94-102, January 1988, Kailua-Kona, Hawaii, United States
• Bau: Gérard M. Baudet, Asynchronous Iterative Methods for Multiprocessors, Journal of the ACM (JACM), v.25 n.2, p.226-244, April 1978 [doi>10.1145/322063.322067]
• Bur: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• Car: Alan Carle , Keith D. Cooper , Robert T. Hood , Ken Kennedy , Linda Torczon, A practical environment for scientific programming, Computer, v.20 n.11, p.75-89, Nov. 1987 [doi>10.1109/MC.1987.1663418]
• DOD: Department of Defense, Reference Manual for the Ada Programming Language, ANSi/MIL-STD-1815 A, 1983.
• Emr: 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
• Fr: P. Frankl, Private Communication, Sept, I988.
• LeB: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging parallel programs with instant replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• Mil: B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.135-144, June 20-24, 1988, Atlanta, Georgia, United States
• Nud1: I. Nudler, L. Rudolph, "Tools for the Efficient Development of Efficient Parallel Programs", First Israeli Conference on Computer Systems Engineering, May 1986.
• Nud2: i. Nudler, L. Rudolph, "indeterminacy Considered Harmful",
• Sni: M. Snir, Private Communications, March 1988.
• Tay: Richard N. Taylor, A general-purpose algorithm for analyzing concurrent programs, Communications of the ACM, v.26 n.5, p.361-376, May 1983 [doi>10.1145/69586.69587]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Ada

General Terms:
Algorithms, Languages