Research On HCH-cube Interconnection Networks And Their Properties

The parallel processing system is one of the research focuses on computer science. Interconnection network is a fundamental part of parallel processing system. Network topology is a crucial factor for the interconnection network since it determines the performance of the whole network. The research and production of new parallel processing systems depend on the research of new interconnection network structures and their properties. It is a multi-target optimization for interconnection network system designing. There are many different and often conflicting performance considerations in designing an interconnection network. These considerations include: small network diameter, strong connectivity, limited number of connections per processor, uniformity of symmetry of processor connection, embedding, expansibility, diagnosability, faulty tolerance, efficient processor layout, regularity and simple message routing algorithm between processor.Many interconnection network topologies have been proposed in the literature for connecting hundreds or thousands of processing elements. Hypercube topology has enjoyed popularity due to many of its attractive properties, including small diameter, strong connectivity, symmetry. But the hypercube is not the best topology on all aspects. Some variants of the Hypercube have better properties than the hypercube. Among these variants the Crossed cube has drawn a great deal of attention from the researchers due to its superior properties over the hypercube on diameter, Hamilton connectivity, simulating binary tree and cycle. However the crossed cube has not the superior properties as the hypercube in some aspects such as symmetry.The hypercube and the crossed cube have both merits and demerits. We hope there is an interconnection network which has both the hypercube's and the crossed cube'smerits to attain more superior properties. This paper gives a kind of connection--thehyper connection between the nodes of the hypercube and nodes of the crossed cube. Thus, a new interconnection network called a HCH-cube is obtained by using this kind of connection. And the following properties of the cube are studied: diameter, smallest vertex degree, vertex connectivity, link connectivity, cycle embedding, Hamilton connectivity, and diagnosability under comparison diagnosis model.First, this paper proves that the diameter of n dimension HCH-cube is n for1 n 3 and +2 for n 4, that is, its diameter is at most the crossed cube'sdiameter added 2(the diameter of n dimension crossed cube is). Obviously itsdiameter is about half of that of the hypercube. Then it is proved that the smallest vertex degree, vertex connectivity and link connectivity are all n, which is holding the best connectivity the same as the hypercube and the crossed cube. Following that, it is proved that it overcomes the disadvantage of the hypercube with respect to simulatingcycles, for n 2 and n 3 , there is any cycle of length l ( 4 / 2n ) in n dimensional HCH-cube. Then the relative algorithm was also given. The time complexity of this algorithm is O(l). Further, it is proved that for n 4, there is at leastone Hamilton path between any two vertexes, that is, the HCH-cube is Hamilton-connected while the hypercube is not Hamilton-connected. So the HCH-cube has the same property as the crossed cube on Hamilton connectivity. Then the relative algorithm that how to construct the Hamilton path between any two vertexes in n dimensional HCH-cube was also given. The time complexity of this algorithm isO(N), N = 2n is the number of vertexes in n dimensional HCH-cube. At last, weshow that for n 4, the diagnosability of n dimensional HCH-cube is n under comparison diagnosis model the same as the hyper cube and the crossed cube.On the other hand, n dimensional HCH-cube has both performance of n -1 dimensional hypercube and that of n -1 dimensional crossed cube, because the hypercube and the crossed cube are all its sub-networks.