Communication Cost Estimation and Global Data Partitioning for Distributed Memory Machines

Estimating communication cost involved in executing a program on distributed memory machines is important for evaluating the overheads due to repartitioning. We present a scheme which will work with reasonable efficiency for arrays with at most 3 dimensions. Hyperplane Partitioning technique given by [10] is extended to complete programs by estimating the communication cost by the scheme presented in this work. 1 Introduction Any strategy for automatic data partitioning needs a way of estimating communication cost involved when we implement the strategy on a target architecture. Many researchers have developed tools [3, 4, 5] that estimate the performance of a parallel program with explicit communication at compile-time. In [2], they employ "training sets" approach to estimate the performance of a parallel program. In [4], profiling is done to get parallel program parameters such as load distribution, communication overhead and data locality. In [9, 5], they use pattern-matching on a..