Title :
On embedding various networks into the hypercube using matrix transformations
Author :
Hamdi, Mounir ; Song, Siang W.
Author_Institution :
Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Kowloon, Hong Kong
Abstract :
Various researchers have shown that the binary n-cube (or hypercube) can embed any r-ary m-cubes, having the same number of nodes, with dilation 1. Their construction method is primarily based on the reflected Gray code. We present a different embedding method based on matrix transformation schemes that achieves the same results. In addition, this method has a nice property that makes it suitable to be used in divide-and-conquer algorithms. Thus, it constitutes a useful tool for the design of parallel algorithms for the hypercube
Keywords :
Gray codes; divide and conquer methods; hypercube networks; matrix algebra; parallel algorithms; parallel architectures; problem solving; binary n-cube; dilation; divide-and-conquer algorithms; embedding method; hypercube; matrix transformations; parallel algorithms; r-ary m-cubes; reflected Gray code; Algorithm design and analysis; Binary trees; Computer science; Costs; Hypercubes; Multiprocessor interconnection networks; Parallel algorithms; Parallel processing; Reflective binary codes;
Conference_Titel :
Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International
Conference_Location :
Honolulu, HI
Print_ISBN :
0-8186-7255-2
DOI :
10.1109/IPPS.1996.508126
