Recently, we studied two important classes of algorithms requiring ±2b communications: ±2b-descend, and ±2b-ascend. Given an N-element input A[0 : N - 1], where N = 2n, 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 + 2b mod N], and A[i - 2b 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 = 2n 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(n2/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(n1.5) time and requires O(1) space per PE. The second algorithm runs in [formula] time and requires O(log n) space per PE.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence