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

Abstract : The classical redistribution problem aims at optimally scheduling communications when reshuf-fling from an initial data distribution to a target data distribution. This target data distribution is usually chosen to optimize some objective for the algorithmic kernel under study (good computational balance or low communication volume or cost), and therefore to provide high efficiency for that kernel. However, the choice of a distribution minimizing the target objective is not unique. This leads to generalizing the redistribution problem as follows: find a re-mapping of data items onto processors such that the data redistribution cost is minimal, and the operation remains as efficient. This paper studies the complexity of this generalized problem. We compute optimal solutions 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.
Type de document :
Article dans une revue
Parallel Computing, Elsevier, 2016, 52, pp.20. 〈10.1016/j.parco.2015.09.005〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01254167
Contributeur : Equipe Roma <>
Soumis le : lundi 11 janvier 2016 - 19:05:39
Dernière modification le : mardi 16 janvier 2018 - 15:59:31
Document(s) archivé(s) le : mardi 12 avril 2016 - 11:41:13

Fichier

paper-revision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julien Herrmann, George Bosilca, Thomas Hérault, Loris Marchal, Yves Robert, et al.. Assessing the cost of redistribution followed by a computational kernel: Complexity and performance results. Parallel Computing, Elsevier, 2016, 52, pp.20. 〈10.1016/j.parco.2015.09.005〉. 〈hal-01254167〉

Partager

Métriques

Consultations de la notice

323

Téléchargements de fichiers

70