Research On The Construction Of Completely Independent Spanning Trees On Two Kinds Of Interconnection Networks

With the continuous development of information technology,high performance computing has become the third pillar of scientific research after theoretical science and experimental science.The development level of high-performance computing reflects the comprehensive strength of a country,and occupies an indispensable and important position in various fields such as national economic construction,high-tech development and national defense construction.Among various scientific researches on high performance computing,how to improve its operating efficiency is the top priority of the development of high performance computing.Parallel computing is one of the effective means to improve system processing capacity and improve system operation efficiency.The processing units in the parallel computing system are regarded as vertices,and the connections between them are regarded as edges,which we call the interconnection network.Generally,the interconnection network can be abstracted into a simple graph G=(V(G),E(G)),where V(G)represents the set of processors in the interconnected network,and the set of edges E(G)in G represents the set of links between processors.In high performance computing systems,communication efficiency and latency of network play an important role in determining performance and scalability.Independent spanning tree can be used for reliable transmission of information,parallel distribution of information,and parallel diagnosis algorithms for faulty servers.The completely independent spanning tree is an independent spanning tree that can take any vertex as the root,so if the source node of the transmission information changes,there is no need to reconstruct the independent spanning tree.A torus network is a commonly used interconnection network in multiprocessor systems.It has many excellent properties such as symmetry,regularity,and good scalability and embedding.Dragonfly network is a topology suitable for high performance computing system,dragonfly network is a layered topology,computing nodes are connected to switches,switches are divided into multiple groups,each switch in each group is connected to each other by a link,and there is a link between any two groups.This means that each pair of switches can be connected by up to three hops apart.This thesis studies the construction of 3 completely independent spanning trees in the line graph of torus network,and gives the completely independent spanning tree partition and construction algorithm under the corresponding conditions.And the construction algorithm of completely independent spanning trees in dragonfly network under the global link of absolute link,relative link and cyclic link.The main research contents are as follows:(1)Based on the definition of the torus network and its line graph,a completely independent spanning tree partition and construction algorithm for 3*n(n≥3)torus network line graph is given,and its detailed proof is given.And based on this algorithm,the completely independent spanning tree partition and construction algorithm and proof of 3m*3n(1≤m≤n)torus network line graph are given.The time complexity of this algorithm is O(N),where N=m*n.(2)Based on the definition of dragonfly network,this thesis presents the construction algorithm of the completely independent spanning tree partition of the dragonfly network in the case of absolute links,relative links and cyclic links.Through this algorithm,the[a/2]completely independent spanning trees in the dragonfly network can be constructed.And the algorithms in the three cases are proved in detail.The time complexity of this algorithm is O(N),where N is the number of vertices.