TY - GEN
T1 - Parallel algorithms for hypercube allocation
AU - Chang, Y.
AU - Bhuyan, L. N.
N1 - Funding Information:
*This research has been partly supported by NSF grant MIP- 9002353
Publisher Copyright:
© 1993 IEEE.
PY - 1993
Y1 - 1993
N2 - Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.
AB - Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.
UR - http://www.scopus.com/inward/record.url?scp=84938169375&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84938169375&partnerID=8YFLogxK
U2 - 10.1109/IPPS.1993.262864
DO - 10.1109/IPPS.1993.262864
M3 - Conference contribution
AN - SCOPUS:84938169375
T3 - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
SP - 105
EP - 112
BT - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th International Parallel Processing Symposium, IPPS 1993
Y2 - 13 April 1993 through 16 April 1993
ER -