Parallel algorithms for the classes of ±2b DESCEND and ASCEND computations on a SIMD hypercube

Derives a simple lower bound for performing a 2^b permutation on an N-PE SIMD hypercube, proving that log N-b routing steps are needed even if one allows an arbitrary mapping of elements to processors. An algorithm for performing a 2^b permutation using exactly log N-b full-duplex routing steps that is slightly more efficient than previously known O(log N-b) algorithms, which perform the permutation as an Ω or Ω^-1 mapping, is presented. The author has also identified a general class of parallel computations called ±2^b descend, which includes Batcher´s odd-even merge and many other algorithms. An efficient algorithm for performing any computation in this class in O(log N) steps on an N-PE SIMD hypercube is given. A related class of parallel computations called ±2^b ascend is also defined. This class appears to be more difficult than ±2^b descend. A simple O(log² N/log log) N algorithm for this class on a SIMD hypercube, requiring Θ(log log N) space per processor is developed