Data flow equations for explicitly parallel programs
Authors:
- Dirk GrunwaldDGDirk Grunwald
- Harini SrinivasanHSHarini Srinivasan
Open Access
- 1 July 1993
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 28 (7) , 159-168
Abstract
We present a solution to the reaching definitions problem for programs with explicit lexically specified parallel constructs, such as cobegin/coend or parallel_sections, both with and without explicit synchronization operations, such as Post, Wait or Advance. The reaching definitions information for sequential programs is used to solve many standard optimization problems. In parallel programs, this information can also be used to explicitly direct communication and data ownership. Although work has been done on analyzing parallel programs to detect data races, little work has been done on optimizing such programs. We show how the memory consistency model specified by an explicitly parallel programming language can influence the complexity of the reaching definitions problem. By selecting the “weakest” memory consistency semantics, we can efficiently solve the reaching definitions problem for correct programs.Keywords
This publication has 13 references indexed in Scilit:
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- PCF parallel Fortran extensionsACM SIGPLAN Fortran Forum, 1991
- Performance evaluation of memory consistency models for shared-memory multiprocessors1991
- Analysis of event synchronization in a parallel programming tool1990
- An empirical comparison of monitoring algorithms for access anomaly detection1990
- Event synchronization analysis for debugging parallel programs1989
- Compile-time detection of race conditions in a parallel program1989
- Static analysis of low-level synchronization1988
- Generating sequential code from parallel code1988
- On linearizing parallel code1985