Array Dataflow Analysis for Polyhedral X10 Programs

作者：Yuki Tomofumi^*; Feautrier Paul; Rajopadhye Sanjay; Saraswat Vijay

来源：ACM Sigplan Notices, 2013, 48(8): 23-33.

DOI：10.1145/2517327.2442520

• X10
• Parallelism
• Non-determinism
• Array Data-flow Analysis
• Polyhedral Model
• Happens-Before
• Race Detection
• Execution Partial Order

This paper addresses the static analysis of an important class of X10 programs, namely those with finish/async parallelism, and affine loops and array reference structure as in the polyhedral model. For such programs our analysis can certify whenever a program is deterministic or flags races. %26lt;br%26gt;Our key contributions are (i) adaptation of array dataflow analysis from the polyhedral model to programs with finish/async parallelism, and (ii) use of the array dataflow analysis result to certify determinacy. We distinguish our work from previous approaches by combining the precise statement instance-wise and array element-wise analysis capability of the polyhedral model with finish/async programs that are more expressive than doall parallelism commonly considered in the polyhedral literature. We show that our approach is exact (no false negative/positives) and more precise than previous approaches, but is limited to programs that fit the polyhedral model.

• 出版日期2013-8
• 单位INRIA