Research And Design Of Novel Network Structures Based On The Hypercube

With fast development of VLSI and parallel computers, the parallel computer systems not only in the requirement of computing powers need the speed of processors more and more quickly, but also in the scale of solving problems need the number of processors more and more. In order to accelerate the speed of solving problems and enhance the scale of solving applications, based on the original interconnection network structures the scientific researchers propose and implement high dimensional interconnection network structures. Parallel computing means an application task can be decomposed into small tasks, which are assigned to different computers in a parallel computer system. Each computer executes a part of the task cooperating with other computers. In the field of parallel computing, the topology of interconnect networks has been caught popular attentions by scientific research personnel. Because the interconnection network structure is key factor of parallel computer systems and it affects the performance of communication in parallel computer systems closely, in the field of parallel computing the topology of interconnect networks has been caught popular attentions by scientific research personnel. Thus, the research on the interconnect network structures of parallel computer systems has very important theoretical and practical significance.Because interconnect networks have the problems of big hardware cost, high communication overhead cost and poor performance of dimensional expandability. In this paper we present and analyze two new interconnection networks, Exchanged Crossed Cube and Extend Folded Cube. We prove that these two topologies have better properties than Hypercube and other variations of the basic Hypercube, such as smaller diameter and lower cost factor. It means the time of communication is shorter, the distance between vertices is smaller and parallel computers' hardware cost is lower. Furthermore, they maintain several attractive properties including recursive structure, symmetry, easy partitionability, strong connectivity, etc. For these two new designs, we propose optimal routing and broadcasting algorithms, which are developed and proven to be more efficient than those of the conventional networks.