Improving parallel program execution time with message consolidation

Introduces a technique for optimizing interprocessor communication in programs for distributed memory multiprocessors. Our basic approach is to combine messages with the explicit goal of reducing the overall execution time, taking into account direct and indirect dependencies among the concurrent units. We first establish that combining messages between a pair of isolated processors is not necessarily useful in reducing the overall execution time of the program because of complex interprocessor dependencies. The conditions under which message combining is profitable are then established. We then search for such conditions along chains of dependencies that exist across several processors and combine messages that satisfy these conditions