TY - GEN

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

AU - Nassimi, David

AU - Tsai, Yuh Dong

PY - 1991/1/1

Y1 - 1991/1/1

N2 - We identify an important class of parallel computations, called ±2b - 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 6, 6 = logN - 1,.,0, computes the new value of each A[i] as a function of A[i], A[i+2b] and A[i-2b]. We obtain a general algorithm for implementing any computation in this class in O(logN) time on a SIMD hypercube. Our general descend algorithm results in an efficient O(log N) implementation of Batcher's odd-even merge algorithm on a hypercube. The best previously known implementation of odd-even merge on a SIMD hypercube requires O(log2 N) time.

AB - We identify an important class of parallel computations, called ±2b - 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 6, 6 = logN - 1,.,0, computes the new value of each A[i] as a function of A[i], A[i+2b] and A[i-2b]. We obtain a general algorithm for implementing any computation in this class in O(logN) time on a SIMD hypercube. Our general descend algorithm results in an efficient O(log N) implementation of Batcher's odd-even merge algorithm on a hypercube. The best previously known implementation of odd-even merge on a SIMD hypercube requires O(log2 N) time.

UR - http://www.scopus.com/inward/record.url?scp=84943675164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84943675164&partnerID=8YFLogxK

U2 - 10.1109/IPPS.1991.153749

DO - 10.1109/IPPS.1991.153749

M3 - Conference contribution

T3 - Proceedings - 5th International Parallel Processing Symposium, IPPS 1991

SP - 2

EP - 9

BT - Proceedings - 5th International Parallel Processing Symposium, IPPS 1991

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 5th International Parallel Processing Symposium, IPPS 1991

Y2 - 30 April 1991 through 2 May 1991

ER -