Compile-Time Estimation of Communication Costs in Multicomputers
Abstract
An important problem facing numerous research projects on parallelizing compilers for distributed memory machines is that of automatically determining a suitable data partitioning scheme for a program. Any strategy for automatic data partitioning needs a mechanism for estimating the performance of a program under a given partitioning scheme, the most crucial part of which involves determining the communication costs incurred by the program. In this paper, we describe a methodology for estimating the communication costs at compile-time as functions of the numbers of processors over which various arrays are distributed. We also describe a strategy, along with its theoretical basis, for making program transformations that expose opportunities for combining of messages, leading to considerable savings in the communication costs. For certain loops with regular dependences, the compiler can detect the possibility of pipelining, and thus estimate communication costs more accurately than it could otherwise. These results are of great significance to any parallelization system supporting numeric applications on multicomputers. In particular, they lay down a framework for effective synthesis of communication on multicomputers from sequential program references.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 22, 1991
- Accession Number
- ADA236601
Entities
People
- Manish K. Gupta
- Prithviraj Banerjee
Organizations
- University of Illinois Urbana–Champaign