An overview of methods for dependence analysis of concurrent programs

ABSTRACT

Program dependence analysis is an analysis technique to identify and determine various program dependencies in source codes, which has been widely used in program understanding, debugging, testing, reverse engineering, and maintenance. However, there are still many difficulties to be solved when carrying out dependence analysis for concurrent programs because the execution of statements is unpredictable. This survey describes methods and research directions for dependence analysis of concurrent programs, especially about how to obtain the dependencies between concurrently executed statements, the factors leading to intransitivity among dependencies, and how to deal with the intransitivity problem. By careful comparisons, users can select a proper algorithm for their requirements.

REFERENCES

• 1: Samuel Bates , Susan Horwitz, Incremental program testing using program dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.384-396, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158694]
• 2: 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
• 3: 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]
• 4: Chun-Hung Chen , Karen Donohue , Jianwu Lin , Enver Yücesan, Efficient Approach for Monte Carlo Simulation Experiments and Its Applications to Circuit Systems Design, Proceedings of the 34th Annual Simulation Symposium (SS01), p.65, April 22-26, 2001
• 5: Zhengqiang Chen , Xu Baowen , Jianjun Zhao , Hongji Yang, Static Dependency Analysis for Concurrent Ada 95 Programs, Proceedings of the 7th Ada-Europe International Conference on Reliable Software Technologies, p.219-230, June 17-21, 2002
• 6: Jingde Cheng, Task dependence nets for concurrent systems with Ada 95 and its applications, Proceedings of the conference on TRI-Ada '97, p.67-78, November 09-13, 1997, St. Louis, Missouri, United States [doi>10.1145/269629.269637]
• 7: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 8: D. Goswami , R. Mall , P. Chatterjee, Static slicing in Unix process environment, Software—Practice & Experience, v.30 n.1, p.17-36, Jan. 2000 [doi>10.1002/(SICI)1097-024X(200001)30:1<17::AID-SPE290>3.0.CO;2-2]
• 9: Mary Jean Harrold , Brian Malloy , Gregg Rothermel, Efficient construction of program dependence graphs, Proceedings of the 1993 ACM SIGSOFT international symposium on Software testing and analysis, p.160-170, June 28-30, 1993, Cambridge, Massachusetts, United States
• 10: Mary Jean Harrold , James A. Jones , Gregg Rothermel, Empirical Studies of Control Dependence Graph Size forC Programs, Empirical Software Engineering, v.3 n.2, p.203-211, 1998 [doi>10.1023/A:1008088300124]
• 11: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 12: Susan Horwitz , Thomas Reps, The use of program dependence graphs in software engineering, Proceedings of the 14th international conference on Software engineering, p.392-411, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143156]
• 13: ISO/IEC 8652:1995(E), Ada Reference Manual-Language and Standard Libraries.
• 14: Jens Krinke, Static slicing of threaded programs, ACM SIGPLAN Notices, v.33 n.7, p.35-42, July 1998
• 15: Mangala Gowri Nanda , S. Ramesh, Slicing concurrent programs, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.180-190, Sept. 2000
• 16: 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
• 17: 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
• 18: Ohata, F., Nishimatsu, A., Inoue, K. Analyzing Dependence Locality for Efficient Construction of Program Dependence Graph. Information and Software Technology, 2000, 42: 935-946
• 19: A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
• 20: Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, System-dependence-graph-based slicing of programs with arbitrary interprocedural control flow, Proceedings of the 21st international conference on Software engineering, p.432-441, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302675]
• 21: Weiser, M. Program Slicing, IEEE Trans. Software Engineering, 1984, 16(5): 498-509.
• 22: Xu, B. Reverse Program Flow Dependency Analysis and Applications. Chinese Journal of Computers, 1993, 16(5): 385-392
• 23: Yang, H., Xu, B. Design and Implementation of A PSS/ADA Program Slicing System. Chinese J. Computer Research and Development, 1997, 34(3): 217 - 222
• 24: J. Zhao, Using Dependence Analysis to Support Software Architecture Understanding, in M. Li (Ed.), "New Technologies on Computer Software," International Academic Publishers, 1997, 135-142.
• 25: Jianjun Zhao, Multithreaded Dependence Graphs for Concurrent Java Program, Proceedings of the International Symposium on Software Engineering for Parallel and Distributed Systems, p.13, May 17-18, 1999

INDEX TERMS

Keywords:
concurrency, concurrent program dependence graph, program dependence analysis, program slicing