Efficient implementations of a class of ±2b parallel computations on a SIMD hypercube

The authors identify an important class of parallel computations, called ±2^b-descend, with an efficient implementation on a hypercube. Given the input A[0:N-1], a computation in this class consists of log N iterations. Iteration b, b=log N-1, . . ., 0, computes the new value of each A[i] as a function of A[i], A[i+2^b] and A [i-2^b]. They obtain a general algorithm for implementing any computation in this class in O(log N) time on a SIMD hypercube. Their general descend algorithm results in an efficient O(log N) implementation of the Batcher odd-even merge algorithm on a hypercube. The best previously known implementation of odd-even merge on a SIMD hypercube requires O(log² N) time