Optimal broadcast in all-port wormhole-routed hypercubes
Ching-Tien Ho, Ming-Yang Kao
ICPP 1994
We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires approximately [Formula Omitted] element transfers in sequence for K elements per node, compared to K element transfers for previously known algorithms. For a binary cube of n = 2 dimensions the new algorithm degenerates to yield a complexity of [Formula Omitted] element transfers, which is optimal. The new algorithm is optimal to within a multiplicative factor of [Formula Omitted] with respect to the best known lower bound for any routing strategy. We show that the minimum number of element transfers for minimum path length routing is A″ with concurrent communication on all channels of every node of a binary cube. © 1995 IEEE
Ching-Tien Ho, Ming-Yang Kao
ICPP 1994
Jehoshua Bruck, Robert Cypher, et al.
Theoretical Computer Science
Ching-Tien Ho, Larry Stockmeyer
IPDPS 2002
Ching-Tien Ho, Jehoshua Bruck, et al.
IEEE TC