Communication Cost Analysis for Parallel Networks
Phyllis E. Crandall, Michael J. Quinn · 1994
The recent interest in heterogeneous parallel computing and improving network speeds have given rise to a new parallel architecture, the parallel network. This parallel processing paradigm, however, poses specific challenges caused by the latency of the communications network and the workload imbalance that arises from the heterogeneity of the participating nodes. Data partitioning is of critical importance if acceptable performance is to be achieved in this environment. We mathematically characterize the communication costs for five partitioning methods for data-parallel programming: scatter, contiguous point, contiguous row, interleaved, and block decomposition. The communication patterns we consider in our analysis are broadcast, reduction, systolic, and 5-point stencil. The effects of the various partitioning methods on expected performance are analyzed in terms of problem size, number of processors, network speed, communication pattern, and bookkeeping requirements. We establish c...