Research On Construction Of Independent Spanning Trees On BC Networks

High performance computers play more and more important roles in the areas of spacedefense, oil exploration, biological drugs manufacture, weather forecast, and basic theory re-search. The performance of such computers depends on the connection pattern(interconnectionnetwork) of processors or processing machines in the parallel computer system to a largeextent. In the parallel computing area, the study of the interconnection networks and theirproperties is a key subject. An interconnection network can be represented by a simple graphG=(V(G), E(G)), where V(G) represents the vertex set and E(G) represents the edge set ofG.Hypercubes are a class of interconnection networks among the common used intercon-nection networks, many advantageous properties of which such as lower diameter, higherconnectivity, symmetry, and recursive construction etc. have attracted the interest from manyresearchers. At the same time, hypercubes have variants such as crossed cubes, Mo¨biuscubes, twisted cubes, etc. Researchers ascribe hypercubes and many of their variants into aclass of interconnection networks—BC networks based on the bijective connection and re-cursive construction properties. Independent spanning trees (ISTs for short) play importantroles in reliable communication, parallel communication, secure distribution of messagesand diagnosis of the faulty processors. This thesis adopts the methods from particular togeneral to study the existence and construction of ISTs rooted at any vertex on BC networks,including the following contents:1. The serial construction of ISTs rooted at any vertex on an arbitrary crossed cube(1) We prove that the n-dimensional crossed cube CQnpossesses an important property—vertex-address-mapping, based on which, an method to construct the isomorphic spanningtree on CQ1n1based on the tree rooted at any vertex on CQ0n1is provided.(2) We give a recursive method to construct n ISTs rooted at any vertex on CQn, proveits correctness, and design an algorithm with the time complexity O(Nlog2N), where N isthe number of vertices in CQn.2. The serial construction of ISTs rooted at any vertex on an arbitrary Mo¨bius cube Noting that the n-dimensional Mo¨bius cube Mnis composed of two sub-Mo¨bius cubesM01n1and Mn1, which are not isomorphic, as a result, the constructive method of ISTs onCQnis not adequate for Mn. We focus on the dimensional relations between any adjacenttwo vertices in Mnand obtained the following results:(1) We propose the constructive method of two isomorphic trees on M0n1and M1n1,based on the dimensional-adjacent relations between any two vertices in the trees.(2) We design the select method of extensive vertex set and extensive vertex set partitionduring the construction of ISTs, based on the dimensional-adjacent relations between anytwo vertices in the trees. We also adopt non-negative vectors to prove the correctness ofISTs on Mn.(3) A recursive algorithm with the time complexity O(NlogN) is proposed, where N isthe number of vertices in Mn.The method to construct isomorphic trees on M01n1and Mn1is also adequate for theconstruction of isomorphic trees on CQ0n1and CQ1n1. Thus, the method is improved editionof the method used in crossed cubes. In addition, the efciency of the recursive algorithmdesigned for ISTs on Mnis higher than that for CQn.3. Parallel construction of ISTs on crossed cubesThe time complexity of the recursive construction of ISTs on crossed cubes and Mo¨biuscube is relatively large. At the same time, during the construction of ISTs, there exists de-pendence of ISTs, for example, the construction of the nth tree depends on the other n1trees. Finding new properties of crossed cubes based on which to design parallel construc-tion method to improve the efciency of corresponding algorithm becomes an importantresearch content. We obtain the following results:(1) We prove that crossed cubes possess an important property—dimensional expand-ing.(2) A storage structure contains the UUID domain and the VALUE domain is proposed,which can make sure that the UUID domain of each vertex is unique.(3) We provide a parallel algorithm of ISTs on crossed cubes based on the dimensionalexpanding property.4. Parallel construction of ISTs on Mo¨bius cubesBased on the recursive constructive methods for crossed cubes, Mo¨bius cubes and theparallel construction method for crossed cubes, we further study the parallel construction ofISTs on Mo¨bius cubes and obtain the following results: (1) From the perspective of permutation and combination, we adopt the concept ofcircular-dimensional permutation into the construction of ISTs.(2) We first prove that the descending circular-dimensional permutation can be used toconstruct ISTs rooted at any vertex on an arbitrary Mo¨bius cube, then prove that any circularpermutation can be used to construct ISTs rooted at any vertex on an arbitrary Mo¨bius cubeand an arbitrary hypercube.(3) We point out that diferent circular-dimensional permutations can be used to con-struct multiple disjoint paths between any two vertices in Mo¨bius cubes.(4) We study the diagnosis algorithm based on ISTs.5. Construction of ISTs on BC networksThe construction and proof of ISTs on the special BC networks such as hypercubes,crossed cubes, locally twisted cubes, Mo¨bius cubes are based on their special properties. Westudy the general method to construct ISTs based on the common property of such cubes andobtain the following results:(1) We give the definition of conditional BC networks and prove that hypercubes,crossed cubes, locally twisted cubes, Mo¨bius cube, etc. belong to condition BC networks.At the same time, we also point out there exist networks which do not belong to conditionalBC networks.(2) We prove that the ascending circular-dimensional permutation can be used to con-struct ISTs rooted at any vertex on n-dimensional conditional BC network XCnin O(N)time, where each IST is isomorphic to n-level binomial-like tree and N=2nis the numberof vertices in XCn, n≥2.(3) For any BC network, we propose the definition of V-dimensional permutation andprove that any V-dimensional permutation can be used to construct a spanning tree isomor-phic to n-level binomial tree rooted at any vertex on any n-dimensional BC network Xn. Wepoint out that there exist multiple sets of two ISTs on Xnbased on V-dimensional permuta-tions.In summary, this thesis first gives the serial construction methods of ISTs on specialBC networks such as crossed cubes and Mo¨bius cubes. Then, based on such serial serialconstruction methods, the parallel construction methods of ISTs on the above two networksare designed. Furthermore, the construction problems of ISTs on conditional BC networks and BC networks are studied.