Y. Li, S. Peng, and W. Chu (Japan)
Interconnection networks, hypercube, hamiltonian cycle,Gray code, fault-tolerant embedding
The hypercube has been widely used as the interconnec tion network (IN) in parallel computers. However, the major drawback of the hypercube is the increase in the number of communication links for each node with the increase in the total number of nodes in the system. A dual-cube DC(m) has m + 1 links per node where m is the degree of a cluster (m-cube), one more link is used for connecting to a node in another cluster. The dual cube mitigates the problem of increasing number of links in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. Em bedding a linear array or a ring into interconnection net works even when faulty-links exit is an important issue for the design of INs. In this paper, we show that a hamil tonian cycle exists in a DC(m) with up to m − 1 faulty links. This is optimal because the degree of a DC(m) is m+1. We also give efficient algorithms for constructing hamiltonian cycles in DC(m).
Important Links:
Go Back
