Logo der Universität Wien

Buffer-safe communication optimization based on data flow analysis and performance prediction


This paper presents a novel approach to reduce communication costs of programs for distributed memory machines. Our techniques are based on uni-directional bit-vector data flow analysis that enable vectorizing and coalescing communication, overlapping communication with computation, eliminating redundant messages and amount of data being transferred both within and across loop nests. Our data flow analysis differs from previous techniques that it does not require to explicitly model balanced communication placement and loops and does not employ interval analysis. Our techniques are based on simple yet highly effective data flow equations which are solved iteratively for arbitrary control flow graphs. Moving communication earlier to hide latency has been shown to dramatically increase communication buffer sizes and can even cause runtime errors. We use P3T, a state-of-the-art performance estimator to create a buffer-safe program. By accurately estimating both the communication buffer sizes required and the implied communication times of every single communication of a program we can selectively choose communication that must be delayed in order to ensure a correct communication placement while maximizing communication latency hiding. Experimental results are presented to prove the efficacy of our communication optimization strategy.

Grafik Top
Grafik Top
Technical Report (Technical Report)
Scientific Computing
Institute for Software Technology and Parallel Systems, University of Vienna
October 1997
Official URL
Grafik Top
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna