HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Determining the optimal redistribution

* Corresponding author
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution \Dini to a target distribution \Dtar where each processor $P_{i}$ will host a subset $P(i)$ of data items. However, modern computing platforms are equipped with a powerful interconnection switch, and the cost of a given communication is (almost) independent of the location of its sender and receiver. This leads to generalizing the redistribution problem as follows: find the optimal permutation $\sigma$ of processors such that $P_{i}$ will host the set $P(\sigma(i))$, and for which the cost of the redistribution is minimal. This report studies the complexity of this generalized problem. We provide optimal algorithms and evaluate their gain over classical redistribution through simulations. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets $P(\sigma(i))$) that minimize the cost of redistribution followed by a simple computation kernel.
Keywords :
Document type :
Reports

Cited literature [24 references]

https://hal.inria.fr/hal-00960452
Contributor : Julien Herrmann Connect in order to contact the contributor
Submitted on : Wednesday, March 19, 2014 - 3:41:49 PM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM
Long-term archiving on: : Monday, April 10, 2017 - 1:25:06 AM

### File

RR-8499.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00960452, version 2

### Citation

Thomas Hérault, Julien Herrmann, Loris Marchal, Yves Robert. Determining the optimal redistribution. [Research Report] RR-8499, INRIA. 2014. ⟨hal-00960452v2⟩

Record views