A global communication optimization technique based on data-flow analysis and linear algebra

Reducing communication overhead is extremely important in distributed-memor y message-passing architectures. In this article, we present a technique to improve communication that considers data access patterns of the entire pr ogram. Our approach is based on a combination of traditional data-flow anal ysis and a linear algebra framework, and it works on structured programs wi th conditional statements and nested loops but without arbitrary goto state ments. The distinctive features of the solution are the accuracy in keeping communication set information, support for general alignments and distribu tions including block-cyclic distributions, and the ability to simulate som e of the previous approaches with suitable modifications. We also show how optimizations such as message vectorization, message coalescing, and redund ancy elimination are supported by our framework. Experimental results on se veral benchmarks show that our technique is effective in reducing the numbe r of messages (an average of 32% reduction), the volume of the data communi cated (an average of 37% reduction), and the execution time (an average of 26% reduction).