Article

Free access

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

Authors:

Gleb Naumovich,

George S. AvruninAuthors Info & Claims

SIGSOFT '98/FSE-6: Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering

Pages 24 - 34

https://doi.org/10.1145/288195.288213

Published: 01 November 1998 Publication History

PDF eReader

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

[1]

D. Callahan and J. Subhlok. Static analysis of low-level synchronization. In Proceedings of the SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging, pages 100-111,1988.

Digital Library

Google Scholar

[2]

E. Duesterwald and M. L. Soffa. Concurrency analysis in the presence of procedures using a data flow framework. In Proceedings of the ACM SIGSOFT Fourth Workshop on Softvare Testing, Analysis, and Verification, pages 36-48, Victoria, B.C., October 1991.

Digital Library

Google Scholar

[3]

M. Dwyer. Data Flow Analysis for Verifying Correctness Properties of Concurrent Programs. PhD thesis, University of Massachussetts, Amherst, 1995.

Digital Library

Google Scholar

[4]

M. Dwyer and L. Clarke. Data flow analysis for verifying properties of concurrent programs. In ACM SIGSOFT' 94 Software Engineering Notes, Proceedings of the Second ACM SIGSOFT Symposium on Foundations of Software Engineering, pages 62-75, December 1994.

Digital Library

Google Scholar

[5]

M. Hecht. Flow Analysis of Computer Programs. North-Holland, New Yorki 1977.

Digital Library

Google Scholar

[6]

S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. In Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, pages 104- 115, Oct. 1995.

Digital Library

Google Scholar

[7]

T. J. Marlowe and B. G. Ryder. Properties of data flow frameworks. Acta Informatica, 28(2):121-163, 1990.

Digital Library

Google Scholar

[8]

S. Masticola and B. Ryder. Non-concurrency analysis. In Proceedings of the Twelfth of Symposium on Principles and Practices of Parallel Programming, San Diego, CA, May 1993.

Digital Library

Google Scholar

[9]

S. P. Masticola. Static detection of deadlocks in polynomial time. PhD thesis, Rutgers University, 1993.

Digital Library

Google Scholar

[10]

S. P. Masticola, T. J. Marlowe, and B. G. Ryder. Lattice frameworks for multisource and bidirectional data flow problems. ACM Transactions on Programming Languages and Systems, 17(5):777- 803, September 1995.

Digital Library

Google Scholar

[11]

G. N. Naumovich, L. A. Clarke, L. J. Osterweil, and M. B. Dwyer. Verification of concurrent software with FLAVERS. In Proceedings of the 19th International Conference on Software Engineering, pages 594-595, May 1997.

Digital Library

Google Scholar

[12]

R. N. Taylor. Complexity of analyzing the synchronization structure of concurrent programs. Acta Informatica, 19:57-84, 1983.

Digital Library

Google Scholar

Cited By

View all

Zhang YDhawal ONandivada VChiba SUgawa TLaemmel RPereira JMosses P(2024)Reducing Write Barrier Overheads for Orthogonal PersistenceProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695646(210-223)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695646
Gopalakrishnan AVerbrugge C(2022)Reordering Under the ECMAScript Memory Consistency ModelLanguages and Compilers for Parallel Computing10.1007/978-3-030-95953-1_14(198-214)Online publication date: 16-Feb-2022
https://doi.org/10.1007/978-3-030-95953-1_14
Bora UVaishay SJoshi SUpadrasta R(2021)OpenMP aware MHP Analysis for Improved Static Data-Race Detection2021 IEEE/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC)10.1109/LLVMHPC54804.2021.00006(1-11)Online publication date: Nov-2021
https://doi.org/10.1109/LLVMHPC54804.2021.00006
Show More Cited By

Index Terms

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

Recommendations

May-happen-in-parallel analysis of X10 programs
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

X10 is a modern object-oriented programming language designed for high performance, high productivity programming of parallel and multi-core computer systems. Compared to the lower-level thread-based concurrency model in the Java^TM language, X10 has ...
A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel

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 ...
A Conservative Data Flow Algorithm for Detecting All Pairs of Statements that May Happen in Parallel

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGSOFT '98/FSE-6: Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering

November 1998

248 pages

ISBN:1581131089

DOI:10.1145/288195

Chairmen:
Leon J. Osterweil
Univ. of Massachusetts at Amherst
,
William L. Scherlis
Carngie Mellon Univ., Pittsburgh, PA

ACM SIGSOFT Software Engineering Notes Volume 23, Issue 6
Nov. 1998
248 pages
ISSN:0163-5948
DOI:10.1145/291252
Chairmen:
Leon J. Osterweil
Univ. of Massachusetts at Amherst, Amherst
,
William L. Scherlis
Carngie Mellon Univ., Pittsburgh, PA
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOFT98

Sponsor:

SOFT98: Sixth International Symposium on the Foundations of Software Engineering

November 1 - 5, 1998

Florida, Lake Buena Vista, USA

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

100
Total Citations
View Citations
746
Total Downloads

Downloads (Last 12 months)124
Downloads (Last 6 weeks)20

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang YDhawal ONandivada VChiba SUgawa TLaemmel RPereira JMosses P(2024)Reducing Write Barrier Overheads for Orthogonal PersistenceProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695646(210-223)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695646
Gopalakrishnan AVerbrugge C(2022)Reordering Under the ECMAScript Memory Consistency ModelLanguages and Compilers for Parallel Computing10.1007/978-3-030-95953-1_14(198-214)Online publication date: 16-Feb-2022
https://doi.org/10.1007/978-3-030-95953-1_14
Bora UVaishay SJoshi SUpadrasta R(2021)OpenMP aware MHP Analysis for Improved Static Data-Race Detection2021 IEEE/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC)10.1109/LLVMHPC54804.2021.00006(1-11)Online publication date: Nov-2021
https://doi.org/10.1109/LLVMHPC54804.2021.00006
Terragni VPezzè M(2021)Statically driven generation of concurrent tests for thread‐safe classesSoftware Testing, Verification and Reliability10.1002/stvr.177431:4Online publication date: 4-May-2021
https://doi.org/10.1002/stvr.1774
Terragni VPezze MBianchi F(2019)Coverage-Driven Test Generation for Thread-Safe Classes via Parallel and Conflict Dependencies2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST.2019.00034(264-275)Online publication date: Apr-2019
https://doi.org/10.1109/ICST.2019.00034
Bischof SBreitner JGraf JHecker MMohr MSnelting G(2018)Low-deterministic security for low-nondeterministic programs1Journal of Computer Security10.3233/JCS-1798426:3(335-366)Online publication date: 9-Apr-2018
https://doi.org/10.3233/JCS-17984
Kroening DPoetzl DSchrammel PWachter BLo DApel SKhurshid S(2016)Sound static deadlock analysis for C/PthreadsProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970309(379-390)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970309
Sankar AChakraborty SNandivada VZaks AHermenegildo M(2016)Improved MHP AnalysisProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2897144(207-217)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2897144
Shih WYou YHuang CLee J(2014)Compiler Optimization for Reducing Leakage Power in Multithread BSP ProgramsACM Transactions on Design Automation of Electronic Systems10.1145/266811920:1(1-34)Online publication date: 18-Nov-2014
https://dl.acm.org/doi/10.1145/2668119
Bishop MConboy HPhan HSimidchieva BAvrunin GClarke LOsterweil LPeisert S(2014)Insider Threat Identification by Process AnalysisProceedings of the 2014 IEEE Security and Privacy Workshops10.1109/SPW.2014.40(251-264)Online publication date: 17-May-2014
https://dl.acm.org/doi/10.1109/SPW.2014.40
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

May-happen-in-parallel analysis of X10 programs

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

A Conservative Data Flow Algorithm for Detecting All Pairs of Statements that May Happen in Parallel