Communication-Sensitive Static Dataflow for Parallel Message Passing Applications
Author:
- Greg BronevetskyGBGreg Bronevetsky
- 1 March 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-12
Abstract
Message passing is a very popular style of parallel programming, used in a wide variety of applications and supported by many APIs, such as BSD sockets, MPI and PVM. Its importance has motivated significant amounts of research on optimization and debugging techniques for such applications. Although this work has produced impressive results, it has also failed to fulfill its full potential. The reason is that while prior work has focused on runtime techniques, there has been very little work on compiler analyses that understand the properties of parallel message passing applications and use this information to improve application performance and quality of debuggers.This paper presents a novel compiler analysis framework that extends dataflow to parallel message passing applications on arbitrary numbers of processes. It works on an extended control-flow graph that includes all possible inter-process interactions of any numbers of processes. This enables dataflow analyses built on top of this framework to incorporate information about the application's parallel behavior and communication topology. The parallel dataflow framework can be instantiated with a variety of specific dataflow analyses as well as abstractions that can tune the accuracy of communication topology detection against its cost. The proposed framework bridges the gap between prior work on parallel runtime systems and sequential dataflow analyses, enabling new transformations, runtime optimizations and bug detection tools that require knowledge of the application's communication topology. We instantiate this framework with two different symbolic analyses and show how these analyses can detect different types of communication patterns, which enables the use of dataflow analyses on a wide variety of real applications.Keywords
This publication has 12 references indexed in Scilit:
- Concurrency Analysis for Shared Memory Programs with Textually Unaligned BarriersLecture Notes in Computer Science, 2008
- Model Checking Nonblocking MPI Programs2007
- Practical Model-Checking Method for Verifying Correctness of MPI ProgramsLecture Notes in Computer Science, 2007
- Data-Flow Analysis for MPI Programs2006
- STAR-MPI2006
- Transformations to Parallel Codes for Communication-Computation Overlap2005
- MPI‐CHECK: a tool for checking Fortran 90 MPI programsConcurrency and Computation: Practice and Experience, 2003
- Rose Compiler Support for Object-Oriented FrameworksParallel Processing Letters, 2001
- Communication Topology Analysis for Concurrent ProgramsLecture Notes in Computer Science, 2000
- Analyzing the communication topology of concurrent programs1995