Alignment and distribution is NOT (always) NP-hard - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1998

Alignment and distribution is NOT (always) NP-hard

Vincent Boudet
Fabrice Rastello
Yves Robert

Résumé

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)
Fichier non déposé

Dates et versions

hal-00856851 , version 1 (02-09-2013)

Identifiants

Citer

Vincent Boudet, Fabrice Rastello, Yves Robert. Alignment and distribution is NOT (always) NP-hard. ICPADS'98, Taiwan, Dec 1998, Taiwan, China. pp.648-657, ⟨10.1109/ICPADS.1998.741148⟩. ⟨hal-00856851⟩
191 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More