Detecting concurrently executed pairs of statements using an adapted MHP algorithm

ABSTRACT

Information about which pairs of statements in a program can be executed concurrently is important for improving the accuracy of dataflow analysis, optimizing programs, and detecting errors. This paper presents a new method named Concurrent Control Flow Graph for representing concurrent Ada 95 programs in a simple and precise way. Based on this method, we develop an Adapted MHP algorithm that can statically detect all pairs of statements that may be executed concurrently. This algorithm checks not only whether a rendezvous can be triggered, but also whether it can be finished. Although this algorithm generates a conservative superset of the perfect pairs of statements, it is more precise than many existing methods.

REFERENCES

• 1: 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
• 2: Chen, Z. , and Xu, B. Dependence Analysis and Static Slices of Concurrent Programs. ICYCS'99, Nanjing, China, 239-242,1999
• 3: Zhenqiang Chen , Baowen Xu , Hongji Yang , Kecheng Liu , Jianping Zhang, An Approach to Analyzing Dependency of Concurrent Programs, Proceedings of the The First Asia-Pacific Conference on Quality Software (APAQS'00), p.39, October 30-31, 2000
• 4: Chen, Z. , and Xu, B. Detecting All Pairs of Statements in Parallel Programs, NCYCS'2000, Nanjing, China, 265-269.
• 5: Zhenqiang Chen , Baowen Xu, Slicing concurrent java programs, ACM SIGPLAN Notices, v.36 n.4, p.41-47, April 1, 2001 [doi>10.1145/375431.375420]
• 6: Evelyn Duesterwald , Mary Lou Soffa, Concurrency analysis in the presence of procedures using a data-flow framework, Proceedings of the symposium on Testing, analysis, and verification, p.36-48, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120811]
• 7: ISO/IEC 8652:1995(E). Ada Reference Manual-Language and Standard Libraries.1995.
• 8: Jens Krinke, Static slicing of threaded programs, ACM SIGPLAN Notices, v.33 n.7, p.35-42, July 1998
• 9: Bangqing Li , Baowen Xu , Huiming Yu, Transforming Ada serving tasks into protected objects, Proceedings of the 1998 annual ACM SIGAda international conference on Ada, p.240-245, November 08-12, 1998, Washington, D.C., United States
• 10: Stephen P. Masticola , Barbara G. Ryder, Non-concurrency analysis, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.129-138, May 19-22, 1993, San Diego, California, United States
• 11: Gleb Naumovich , George S. Avrunin, A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.24-34, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 12: Gleb Naumovich , George S. Avrunin , Lori A. Clarke, An efficient algorithm for computing MHP information for concurrent Java programs, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.338-354, September 06-10, 1999, Toulouse, France
• 13: Taylor, R. N. Complexity of analyzing the synchronization structure of concurrent programs. Acta Informatica, 19:57-84, 1983.
• 14: Xu, B. Reverse Program flow Dependency Analysis and Applications. Chinese J. Computers, 16(5): 385-392, 1993.
• 15: Xu, B. An Overview of Ada95. Journal of Computer Research and Development, 34(1): 53-57, 1997.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

General Terms:
Algorithms, Experimentation

Keywords:
Concurrent program, MHP algorithm, control flow graph, program analysis