Document Type
Working Paper
Date
1998
Keywords
communication, optimizations, message vectorization, distributed memory machines, paralellism, data-flow analysis, global optimizations
Language
English
Disciplines
Computer Sciences
Description/Abstract
Reducing communication overhead is extremely important in distributed-memory message-passing architectures. In this paper, we present a technique to improve communication that considers data access patterns of the entire program. Our approach is based on a combination of traditional data-flow analysis and a linear algebra framework, and works on structured programs with conditional statements and nested loops but without arbitrary goto statements. The distinctive features of the solution are the accuracy in keeping communication set information, support for general alignments and distributions including block-cyclic distributions and the ability to simulate some of the previous approaches with suitable modifications. We also show how optimizations such as message vectorization, message coalescing and redundancy elimination are supported by our framework. Experimental results on several benchmarks show that our technique is effective in reducing the number of messages (an average of 32% reduction), the volume of the data communicated (an average of 37% reduction), and the execution time (an average of 26% reduction).
Recommended Citation
Kandemir, Mahmut; Banerjee, P.; Choudhary, Alok; and Ramanujam, J., "A Global Communication Optimization Technique Based on Data-Flow Analysis and Linear Algebra" (1998). Electrical Engineering and Computer Science - All Scholarship. 24.
https://surface.syr.edu/eecs/24
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
