Modeling Data-Parallel Programs with the Alignment-Distribution Graph

We present an intermediate representation of a program called the Alignment-Distribution Graph that exposes the communication requirements of the program. The representation exploits ideas developed in the static single assignment form of programs, but is tailored for communication optimization. It serves as the basis for algorithms that map the array data and program computation to the nodes of a distributed-memory parallel computer so as to minimize completion time. We describe the details of the representation, explain its construction from source text, show its use in modeling communication cost, outline several algorithms for determining mappings that approximately minimize residual communication, and compare it with other related intermediate representations of programs