Alignment and distribution is not (always) NP-hard

In this paper, an efficient algorithm to simultaneously implement array ali gnment and data/computation distribution is introduced and evaluated. We re visit previous work of J. Li and M. Chen (in "Frontiers 90: The Third Sympo sium on the Frontiers of Massively Parallel Computation," pp. 424-433, Coll ege Park MD, Oct. 1990; and J. Parallel Distrib. Comput. 13 (1991), 213-221 ), and we show that their alignment step should not be conducted without pr eserving the potential parallelism. In other words, the optimal alignment m ay well sequentialize computations, whatever the distribution afterward. We provide an efficient algorithm that handles alignment and data/computation distribution simultaneously. The good news is that several important insta nces of the whole alignment /distribution problem have polynomial complexit y, while alignment itself is NP-complete (Li and Chen, 1990). (C) 2001 Acad emic Press.