Alignment and distribution is NOT (always) NP-hard

Vincent Boudet 1 Fabrice Rastello 1 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : An efficient algorithm to simultaneously implement array alignment and data/computation distribution is introduced and evaluated. We re-visit previous work of Li and Chen (J. Li and M. Chen, 1990; 1991), and we show that their alignment step should not be conducted without preserving the potential parallelism. In other words, the optimal alignment may well sequentialize computations, whatever the distribution afterwards. We provide an efficient algorithm that handles alignment and data/computation distribution simultaneously. The good news is that several important instances of the whole alignment/distribution problem have polynomial complexity, while alignment itself is NP-complete (J. Li and M. Chen, 1990)
Type de document :
Communication dans un congrès
Chyi-Nan Chen and Lionel M. Ni. ICPADS'98, Taiwan, Dec 1998, Taiwan, China. IEEE Computer Society Press, pp.648-657, 1998, 〈10.1109/ICPADS.1998.741148〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00856851
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 16:04:54
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Lien texte intégral

Identifiants

Collections

Citation

Vincent Boudet, Fabrice Rastello, Yves Robert. Alignment and distribution is NOT (always) NP-hard. Chyi-Nan Chen and Lionel M. Ni. ICPADS'98, Taiwan, Dec 1998, Taiwan, China. IEEE Computer Society Press, pp.648-657, 1998, 〈10.1109/ICPADS.1998.741148〉. 〈hal-00856851〉

Partager

Métriques

Consultations de la notice

239