Alignment and distribution is NOT (always) NP-hard. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1998

Alignment and distribution is NOT (always) NP-hard.

(1) , (1) , (1)
1

Résumé

In this paper, 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, 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.
Dans ce rapport, un algorithme efficace est présenté et évalué pour résoudre simultanément l'alignement des tableaux et la distribution des données et des calculs. Nous revisitons les travaux précédents de Li et Chen, et nous montrons que leur recherche d'un alignement ne doit pas être conduite sans préserver le parallélisme potentiel. En d'autres termes, l'alignement optimal peut séquentialiser les calculs quelle que soit la distribution choisie ensuite. Nous présentons un algorithme efficace qui tient compte simultanément de l'alignement et de la distribution des données et des calculs. La bonne nouvelle est que plusieurs instances du problème d'alignement/distribution ont une complexité polynomiale alors que l'alignement lui-même est NP-complet.
Fichier principal
Vignette du fichier
RR1998-30.pdf (292.27 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101994 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101994 , version 1

Citer

Vincent Boudet, Fabrice Rastello, Yves Robert. Alignment and distribution is NOT (always) NP-hard.. [Research Report] LIP RR-1998-30, Laboratoire de l'informatique du parallélisme. 1998, 2+18p. ⟨hal-02101994⟩
30 Consultations
846 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More