CRPC-TR95515-S:  A Constraint Based Communication Placement Framework

Ken Kennedy, Ajay Sethi

February, 1995

Communication placement and optimization is an important step in the
compilation of data-parallel languages. We present a framework that,
besides supporting various optimizations like message vectorization,
redundant communication elimination, message coalescing and vector
message pipelining, maximizes latency hiding by determining the safe and 
earliest placement for sends and the balanced and latest placement for 
the corresponding receives. Our framework allows machine-dependent 
resource constraints, which can effect the correctness of the placement 
and restrict the achievable communication and computation overlap, to 
influence the communication placement. We use buffer size constraint to
illustrate constraint analysis and constraint-based communication
placement. Finally, we indicate how communication optimizations can be 
incorporated into the framework.