A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel

Full text

Pdf (1.08 MB)

Source

Foundations of Software Engineering archive
Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering table of contents

Lake Buena Vista, Florida, United States

Pages: 24 - 34

Year of Publication: 1998

ISBN:1-58113-108-9

Also published in ...

Authors

Gleb Naumovich	Laboratory for Advanced Software Engineering Research, Department of Computer Science, University of Massachusetts at Amherst, Amherst, MA
George S. Avrunin	Laboratory for Advanced Software Engineering Research, Department of Computer Science, University of Massachusetts at Amherst, Amherst, MA

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 45, Citation Count: 23

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/288195.288213 What is a DOI?

ABSTRACT

Information about which pairs of statements in a concurrent program can execute in parallel is important for optimizing and debugging programs, for detecting anomalies, and for improving the accuracy of data flow analysis. In this paper, we describe a new data flow algorithm that finds a conservative approximation of the set of all such pairs. We have carried out an initial comparison of the precision of our algorithm and that of the most precise of the earlier approaches, Masticola and Ryder's non-concurrency analysis [8], using a sample of 159 concurrent Ada programs that includes the collection assembled by Masticola and Ryder. For these examples, our algorithm was almost always more precise than non-concurrency analysis, in the sense that the set of pairs identified by our algorithm as possibly happening in parallel is a proper subset of the set identified by non-concurrency analysis. In 132 cases, we were able to use reachability analysis to determine exactly the set of pairs of statements that may happen in parallel. For these cases, there were a total of only 10 pairs identified by our algorithm that cannot actually happen in parallel.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	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]
	3	Matthew Barbour Dwyer , Lori A. Clarke, Data flow analysis for verifying correctness properties of concurrent programs, 1995
	4	Matthew B. Dwyer , Lori A. Clarke, Data flow analysis for verifying properties of concurrent programs, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.62-75, December 06-09, 1994, New Orleans, Louisiana, United States
	5	Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
	6	Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.104-115, October 12-15, 1995, Washington, D.C., United States
	7	T. J. Marlowe , B. G. Ryder, Properties of data flow frameworks: a unified model, Acta Informatica, v.28 n.2, p.121-163, Dec. 1990 [doi>10.1007/BF01237234]
	8	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
	9	Stephen P. Masticola, Static detection of deadlocks in polynomial time, Rutgers University, New Brunswick, NJ, 1993
	10	Stephen P. Masticola , Thomas J. Marlowe , Barbara G. Ryder, Lattice frameworks for multisource and bidirectional data flow problems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.5, p.777-803, Sept. 1995 [doi>10.1145/213978.213989]
	11	Gleb Naumovich , Lori A. Clarke , Leon J. Osterweil , Matthew B. Dwyer, Verification of concurrent software with FLAVERS, Proceedings of the 19th international conference on Software engineering, p.594-595, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253489]
	12	R. N. Taylor. Complexity of analyzing the synchronization structure of concurrent programs. Acta Informatica, 19:57-84, 1983.

CITED BY 23

	Gleb Naumovich , Lori A. Clarke , Jamieson M. Cobleigh, Using partial order techniques to improve performance of data flow analysis based verification, ACM SIGSOFT Software Engineering Notes, v.24 n.5, p.57-65, Sept. 1999
	G. Ramalingam, Context-sensitive synchronization-sensitive analysis is undecidable, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.416-430, March 2000
	Gleb Naumovich , George S. Avrunin , Lori A. Clarke, An efficient algorithm for computing MHP information for concurrent Java programs, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.338-354, Nov. 1999
	Gleb Naumovich , George S. Avrunin , Lori A. Clarke, Data flow analysis for checking properties of concurrent Java programs, Proceedings of the 21st international conference on Software engineering, p.399-410, May 16-22, 1999, Los Angeles, California, United States
	Dean F. Sutherland , Aaron Greenhouse , William L. Scherlis, The code of many colors: relating threads to code and shared state, ACM SIGSOFT Software Engineering Notes, v.28 n.1, January 2003
	Gleb Naumovich, Using the observer design pattern for implementation of data flow analyses, ACM SIGSOFT Software Engineering Notes, v.28 n.1, January 2003
	Jamieson M. Cobleigh , Lori A. Clarke , Leon J. Osterweil, The right algorithm at the right time: comparing data flow analysis algorithms for finite state verification, Proceedings of the 23rd International Conference on Software Engineering, p.37-46, May 12-19, 2001, Toronto, Ontario, Canada
	Jong-Deok Choi , Andreas Zeller, Isolating failure-inducing thread schedules, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Radu Rugina , Martin C. Rinard, Pointer analysis for structured parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.1, p.70-116, January 2003
	Jens Krinke, Context-sensitive slicing of concurrent programs, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
	Ahmed Bouajjani , Javier Esparza , Tayssir Touili, A generic approach to the static analysis of concurrent programs with procedures, ACM SIGPLAN Notices, v.38 n.1, p.62-73, January 2003
	Mikhail Sosonkin , Gleb Naumovich , Nasir Memon, Obfuscation of design intent in object-oriented applications, Proceedings of the 3rd ACM workshop on Digital rights management, October 27-27, 2003, Washington, DC, USA
	Hongmin Lu , Yuming Zhou , Jiangtao Lu , Baowen Xu, A compile-time optimization framework for Ada rendezvous, ACM SIGPLAN Notices, v.39 n.2, February 2004
	Eran Yahav, Verifying safety properties of concurrent Java programs using 3-valued logic, ACM SIGPLAN Notices, v.36 n.3, p.27-40, March 2001
	Zhenqiang Chen , Baowen Xu , Huiming Yu, Detecting concurrently executed pairs of statements using an adapted MHP algorithm, ACM SIGAda Ada Letters, v.XXI n.4, December 2001
	Jianbin Tan , George S. Avrunin , Lori A. Clarke , Shlomo Zilberstein , Stefan Leue, Heuristic-guided counterexample search in FLAVERS, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	Matthew B. Dwyer , Lori A. Clarke , Jamieson M. Cobleigh , Gleb Naumovich, Flow analysis for verifying properties of concurrent software systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.4, p.359-430, October 2004
	Zhenqiang Chen , Baowen Xu , Jianjun Zhao, An overview of methods for dependence analysis of concurrent programs, ACM SIGPLAN Notices, v.37 n.8, August 2002
	Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005
	Jamieson M. Cobleigh , George S. Avrunin , Lori A. Clarke, Breaking up is hard to do: An evaluation of automated assume-guarantee reasoning, ACM Transactions on Software Engineering and Methodology (TOSEM), v.17 n.2, p.1-52, April 2008
	Gregor Snelting , Torsten Robschink , Jens Krinke, Efficient path conditions in dependence graphs for software safety analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.15 n.4, p.410-457, October 2006
	Shivali Agarwal , Rajkishore Barik , Vivek Sarkar , Rudrapatna K. Shyamasundar, May-happen-in-parallel analysis of X10 programs, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Jianbin Tan , George S. Avrunin , Lori A. Clarke, Heuristic-Based Model Refinement for FLAVERS, Proceedings of the 26th International Conference on Software Engineering, p.635-644, May 23-28, 2004