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

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101994
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:33 AM
Last modification on : Wednesday, November 20, 2019 - 7:24:04 AM

File

RR1998-30.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101994, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

17

Files downloads

46