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.