skip to main content
10.1145/1229428.1229471acmconferencesArticle/Chapter ViewAbstractPublication PagesppoppConference Proceedingsconference-collections
Article

May-happen-in-parallel analysis of X10 programs

Published: 14 March 2007 Publication History

Abstract

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 JavaTM language, X10 has higher-level concurrency constructs such as async, atomic and finish built into the language to simplify creation, analysis and optimization of parallel programs. In this paper, we introduce a new algorithm for May-Happen-in-Parallel (MHP) analysis of X10 programs. The analysis algorithm is based on simple path traversals in the Program Structure Tree, and does not rely on pointer alias analysis of thread objects as in MHP analysis for Java programs. We introduce a more precise definition of the MHP relation than in past work by adding condition vectors that identify execution instances for which the MHP relation holds, instead of just returning a single true/false value for all pairs of executing instances. Further, MHP analysis is refined in our approach by using the observation that two statement instances which occur in atomic sections that execute at the same X10 place must have MHP = false. We expect that our MHP analysis algorithm will be applicable to any language that adopts the core concepts of places, async, finish, and atomic sections from the X10 programming model. We also believe that this approach offers the best of two worlds to programmers and parallel programming tools ---higher-level abstractions of concurrency coupled with simple and efficient analysis algorithms.

References

[1]
B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 1--11, New York, NY, USA, 1988. ACM Press.
[2]
Rajkishore Barik. Efficient computation of may-happen-in-parallel information for concurrent java programs. In 18th International Workshop on Languages and Compilers for Parallel Computing, October 2005.
[3]
David Callahan and Jaspal Sublok. Static analysis of low-level synchronization. In PADD '88: Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, pages 100--111, New York, NY, USA, 1988. ACM Press.
[4]
Philippe Charles, Christopher Donawa, Kemal Ebcioglu, Christian Grothoff, Allan Kielstra, Christoph von Praun, Vijay Saraswat, and Vivek Sarkar. X10: An object-oriented approach to non-uniform cluster computing. In OOPSLA 2005 Onward! Track, 2005.
[5]
Jong-Deok Choi, Keunwoo Lee, Alexey Loginov, Robert O'Callahan, Vivek Sarkar, and Manu Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 258--269, New York, NY, USA, 2002. ACM Press.
[6]
Evelyn Duesterwald and Mary Lou Soffa. Concurrency analysis in the presence of procedures using a data-flow framework. In TAV4: Proceedings of the symposium on Testing, analysis, and verification, pages 36--48, New York, NY, USA, 1991. ACM Press.
[7]
J. Ferrante, K. Ottenstein, and J. Warren. The Program Dependence Graph and its Use in Optimization. ACM Transactions on Programming Languages and Systems, 9(3):319--349, July 1987.
[8]
Dov Harel. A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems. Symposium on Theory of Computing, May 1985.
[9]
Ferrante J, Grunwald D, and Srinivasan H. Compile-time analysis and optimization of explicitly parallel programs. In Journal of Parallel algorithms and applications, 1997.
[10]
Jens Krinke. Static slicing of threaded programs. In Workshop on Program Analysis For Software Tools and Engineering, pages 35--42, 1998.
[11]
Jaejin Lee. Compilation Techniques for Explicitly Parallel Programs. PhD thesis, University of Illinois at Urbana-Champaign, 1999.
[12]
T. Lengauer and Robert Tarjan. A Fast Algorithm for Finding Dominators in a Flowgraph. TOPLAS, July 1979.
[13]
Lin Li and Clark Verbrugge. A practical mhp information analysis for concurrent java programs. In The 17th International Workshop on Languages and Compilers for Parallel Computing (LCPC'04), 2004.
[14]
Stephen P. Masticola and Barbara G. Ryder. A model of ada programs for static deadlock detection in polynomial times. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 97--107, New York, NY, USA, 1991. ACM Press.
[15]
Stephen P. Masticola and Barbara G. Ryder. Non-concurrency analysis. In PPOPP '93: Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 129--138, New York, NY, USA, 1993. ACM Press.
[16]
G. Naumovich, G. S. Avruin, and L. A. Clarke. Data flow analysis for checking properties of concurrent java programs. Technical Report UM-CS-1998-022, 1998.
[17]
Gleb Naumovich and George S. Avrunin. A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel. In SIGSOFT '98/FSE-6: Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, pages 24--34, New York, NY, USA, 1998. ACM Press.
[18]
Gleb Naumovich, George S. Avrunin, and Lori A. Clarke. An efficient algorithm for computing MHP information for concurrent Java programs. In Proceedings of the joint 7th European Software Engineering Conference and 7th ACM SIGSOFT Symposium on the Foundations of Software Engineering, pages 338--354, September 1999.
[19]
X10 release on SourceForge. http://x10.sf.net.
[20]
Vivek Sarkar. A Concurrent Execution Semantics for Parallel Program Graphs and Program Dependence Graphs (Extended Abstract). Springer-Verlag Lecture Notes in Computer Science, 757:16--30, 1992. Proceedings of the Fifth Workshop on Languages and Compilers for Parallel Computing, Yale University, August 1992.
[21]
Vivek Sarkar. Analysis and Optimization of Explicitly Parallel Programs using the Parallel Program Graph Representation. In Languages and compilers for parallel computing. Proceedings of the 10th international workshop. Held Aug., 1997 in Minneapolis, MN., Lecture Notes in Computer Science. Springer-Verlag, New York, 1998.
[22]
Vivek Sarkar and Barbara Simons. Parallel Program Graphs and their Classification. Springer-Verlag Lecture Notes in Computer Science, 768:633--655, 1993. Proceedings of the Sixth Workshop on Languages and Compilers for Parallel Computing, Portland, Oregon, August 1993.
[23]
Richard N. Taylor. Complexity of analyzing the synchronization structure of concurrent programs. Acta Inf., 19:57--84, 1983.
[24]
Michael J. Wolfe. Optimizing Supercompilers for Supercomputers. Pitman, London and The MIT Press, Cambridge, Massachusetts, 1989. In the series, Research Monographs in Parallel and Distributed Computing.

Cited By

View all
  • (2024)The digest framework: concurrency-sensitivity for abstract interpretationInternational Journal on Software Tools for Technology Transfer10.1007/s10009-024-00773-y26:6(727-746)Online publication date: 28-Dec-2024
  • (2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
  • (2023)Clustered Relational Thread-Modular Abstract Interpretation with Local TracesProgramming Languages and Systems10.1007/978-3-031-30044-8_2(28-58)Online publication date: 22-Apr-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming
March 2007
284 pages
ISBN:9781595936028
DOI:10.1145/1229428
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. X10
  2. activity
  3. atomic
  4. concurrent
  5. may-happen-in-parallel
  6. parallel program analysis
  7. place

Qualifiers

  • Article

Conference

PPoPP07
Sponsor:

Acceptance Rates

PPoPP '07 Paper Acceptance Rate 22 of 65 submissions, 34%;
Overall Acceptance Rate 230 of 1,014 submissions, 23%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)14
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)The digest framework: concurrency-sensitivity for abstract interpretationInternational Journal on Software Tools for Technology Transfer10.1007/s10009-024-00773-y26:6(727-746)Online publication date: 28-Dec-2024
  • (2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
  • (2023)Clustered Relational Thread-Modular Abstract Interpretation with Local TracesProgramming Languages and Systems10.1007/978-3-031-30044-8_2(28-58)Online publication date: 22-Apr-2023
  • (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
  • (2020)Escaping dependency hell: finding build dependency errors with the unified dependency graphProceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3395363.3397388(463-474)Online publication date: 18-Jul-2020
  • (2019)TapirACM Transactions on Parallel Computing10.1145/33656556:4(1-33)Online publication date: 17-Dec-2019
  • (2019)Optimizing Remote Communication in X10ACM Transactions on Architecture and Code Optimization10.1145/334555816:4(1-26)Online publication date: 11-Oct-2019
  • (2019)Compiler Optimizations for Parallel ProgramsLanguages and Compilers for Parallel Computing10.1007/978-3-030-34627-0_9(112-119)Online publication date: 13-Nov-2019
  • (2018)Parallel Cost AnalysisACM Transactions on Computational Logic10.1145/327427819:4(1-37)Online publication date: 20-Nov-2018
  • (2018)Optimizing remote data transfers in X10Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243209(1-15)Online publication date: 1-Nov-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media