Assessing the cost of redistribution followed by a computational kernel: complexity and performance results

The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution to a target data partition, where each processor will host a subset of data items. A data distribution is usually defined to minimize a particular characteristic of an algorithm (computational imbalance or communication volume or cost) and therefore to provide high efficiency for that particular operation. However, there is no single data distribution that provide this high efficiency. This leads to generalizing the redistribution problem as follows: find the optimal one-to-one mapping of the subsets of data items onto the processors for which the cost of the redistribution is minimal, and the operation remains as efficient. This paper studies the complexity of this generalized problem. We provide optimal algorithms and evaluate, through simulations, their gain over classical redistribution. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets) that minimize the cost of redistribution followed by a simple computational kernel. Finally, experimental validation of the new redistribution algorithms are conducted on a multicore cluster, for both a 1D-stencil kernel and a more compute-intensive dense linear algebra routine.