Nearly Logarithmic-Time Parallel Algorithms for the Class of ±2b ASCEND Computations on a SIMD Hypercube

Recently, we studied two important classes of algorithms requiring ±2^b communications: ±2^b-descend, and ±2^b-ascend. Given an N-element input A[0 : N - 1], where N = 2ⁿ, the descend class consists of n iterations. For b = n - 1, n - 2, …, 0, iteration b computes the new value of each A [i] as a function of the previous-iteration values of A[i], A[i + 2^b mod N], and A[i - 2^b mod N]. (Batcher′s odd-even merge falls into this class.) The ascend class is similar except that the iterations are for b = 0, 1, …, n - 1. Let N = 2ⁿ be the number of processors in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. For the descend class, we developed an efficient O(n) algorithm on a SIMD hypercube. And for the ascend class, we obtained a simple O(n²/log n) algorithm, requiring O(n) words of local memory per processor. In this paper, we develop two new algorithms for the ascend class on a SIMD hypercube. The first algorithm runs in O(n^1.5) time and requires O(1) space per PE. The second algorithm runs in [formula] time and requires O(log n) space per PE.