Complexity Results for Permuting Data and Other Computations on Parallel Processors

For a wide class of problems, we obtain lower bounds for algorithms executed on certain parallel processors. These bounds show that for sufficiently large problems many known algorithms are optimal. The central result of the paper is the following sharper lower bound for permutation algorithms. Any permutation algorithm for N data items on a P processor parallel machine without shared memory requires time on the order of NlogxP/P, where K is the maximum number of processors directly connected to a single processor. In particular, a speedup on the order of P is impossible if K is bounded.