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 -