LANS Publications

"Data-Flow Analysis for MPI Programs"

M. M. Strout, B. Kreaseck, and P. Hovland

Preprint ANL/MCS-P1220-0105

Preprint Version: [pdf]

Message passing via MPI is widely used in single-program, multiple-data (SPMD) parallel programs. Data-flow analysis frameworks that respect the semantics of message-passing SPMD programs are needed to obtain more accurate and in some cases correct analysis results for such programs. We qualitatively evaluate various approaches for performing data-flow analysis on SPMD MPI programs and present a method for performing interprocedural data-flow analysis on the MPI-ICFG representation. The MPI-ICFG is an interprocedural control-flow graph (ICFG) augmented with communication edges between possible send and receive pairs. We discuss in detail two analyses that potentially benefit from propagating information over communication edges: reaching constants and activity analysis. Constants can be shared in SPMD programs without communicating them: therefore, performing reaching constants over the MPI-ICFG is useful mainly for illustrative purposes. Activity analysis is a domain-specific analysis used to reduce the computation and storage requirements for automatically differentiated MPI programs. Our experimental results show that activity analysis performed over the MPI-ICFG has a convergence rate comparable to a more conservative version of the analysis performed on an ICFG. Also, using the MPI-ICFG data-flow analysis framework improves the precision of activity analysis and significantly reduces memory requirements for the automatically differentiated versions of some parallel benchmarks, including some of the NAS Parallel Benchmarks.