Compile-time estimation of communication costs on multicomputers

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. The authors describe a methodology for statically estimating the communication times as certain functions of the array sizes and the numbers of processors over which various arrays used are distributed. This work also lays down a framework for effective synthesis of communication on multicomputers from sequential program references