TY - GEN
T1 - Nearly logarithmic-time parallel algorithms for the class of ±2b ASCEND computations on a SIMD hypercube
AU - Nassimi, David
PY - 1992
Y1 - 1992
N2 - Recently, we have studied two important classes of algorithms requiring ±2b communications: ±2b-descend, and ±2b-ascend. Let N = 2n be the number of PEs in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. In [5], we developed an efficient O(n) algorithm for the descend class. In [6], we obtained a simple O(n2/log n) algorithm for the ascend class, requiring O(log n) words of local memory per PE. In this paper, we present 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, which is discussed only briefly here, runs in O(n√n/log n) time and requires O(log n) space per PE.
AB - Recently, we have studied two important classes of algorithms requiring ±2b communications: ±2b-descend, and ±2b-ascend. Let N = 2n be the number of PEs in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. In [5], we developed an efficient O(n) algorithm for the descend class. In [6], we obtained a simple O(n2/log n) algorithm for the ascend class, requiring O(log n) words of local memory per PE. In this paper, we present 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, which is discussed only briefly here, runs in O(n√n/log n) time and requires O(log n) space per PE.
UR - http://www.scopus.com/inward/record.url?scp=0026995430&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026995430&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0026995430
SN - 0818626720
T3 - Proceedings of the International Conference on Parallel Processing
SP - 122
EP - 129
BT - Proceedings of the International Conference on Parallel Processing
PB - Publ by IEEE
T2 - Proceedings of the 6th International Parallel Processing Symposium
Y2 - 23 March 1992 through 26 March 1992
ER -