Efficient implementations of a class of +or-2/sup b/ parallel computations on a SIMD hypercube
David Nassimi, Y.-D. Tsai · 2002
The authors identify an important class of parallel computations, called +or-2/sup 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/sup b/) and A(i-2/sup 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/sup 2/ N) time.>