Minimum Wirelength Embeddings Of Two Hierarchical Networks Into Linear Arrays And Binary Trees

Graph embedding is a technology that maps a guest graph into a host graph,which can implement functions such as structural simulation,processor allocation,algorithm porting,and network expansion.Graph embedding has a wide range of applications in parallel and distributed systems,Network-on-Chips,multimedia networks,and network virtualization.In parallel and distributed systems,the interconnection network formed by connecting components determines the communication capability,fault tolerance,and hardware cost of the system.An ideal interconnection network should have excellent embeddability.When designing and selecting the interconnection network for parallel and distributed systems,its graph embedding capability should be fully considered.When designing Network-on-Chip,graph embedding techniques can be used to optimize the communication mode as well as to reduce wiring costs.Wirelength of the embedding represents the total length of physical wires between components,which is a comprehensive indicator not only of layout cost but also of communication overhead(e.g.,communication time and communication delay).Smaller wirelength means less wiring costs,shorter communication time,and lower communication latency.Therefore,the graph embedding problem with minimum wirelength is worth studying.Hierarchical cubic network is a kind of hierarchical interconnection network with excellent comprehensive properties.It takes advantage of communication localization to design the network,which reduces link cost.And it adopts a multi-level network structure(lower-level networks for local communication and higher-level networks for remote communication),thus providing good communication performance.In addition,hierarchical cubic network has excellent fault tolerance by duplicating the higher-level networks or using alternate interfaces and nodes.Hierarchical folded cube is another kind of hierarchical interconnection network with good communication capability and fault tolerance.It is obtained by adding some edges to hierarchical cubic network and has a smaller diameter than hierarchical cubic network of the same dimension.Linear arrays and complete binary trees are widely used as host graphs in graph embedding with simple structure,good scalability,and easy implementation.This thesis solves the embedding problems of hierarchical cubic networks into linear arrays and k-rooted complete binary trees with minimum wirelength,as well as the embedding problems of hierarchical folded cubes into linear arrays and complete binary trees with minimum wirelength.The main work is as follows.1.Embedding of hierarchical cubic networks into linear arraysThis thesis first solves the edge isoperimetric problem of hierarchical cubic networks,and proposes embedding hel of hierarchical cubic networks into linear arrays as well as the corresponding embedding algorithm.It is proved theoretically that embedding hel has the minimum wirelength.And this thesis gives the exact minimum wirelength by calculating the total length of all paths under the mapping.In addition,the linear physical layout algorithm of hierarchical cubic network is proposed and the corresponding number of tracks is given.Finally,it is verified from simulation experiments that embedding hel has the minimum wirelength,shorter communication delay,and queuing delay.2.Embedding of hierarchical cubic networks into k-rooted complete binary treesThis thesis first gives the optimal set of hierarchical cubic networks,and proposes embedding het of hierarchical cubic networks into k-rooted complete binary trees(k≥1)as well as the corresponding embedding algorithms.It is proved theoretically that embedding het of hierarchical cubic networks into 1-root complete binary trees has the minimum wirelength,and the exact minimum wirelength by calculating the sum of edge congestion is given.Further,this thesis proves that embedding het also has the minimum wirelength in the embedding of hierarchical cubic networks into k-rooted complete binary trees(k>1),and gives the minimum wirelength.Finally,It can be found from simulation experiments that embedding het is more advantageous in terms of wiring cost and communication performance.3.Embeddings of hierarchical folded cubes into linear arrays and complete binary treesThis thesis first solves the optimal set problem of hierarchical folded cubes,and proposes embedding fel and embedding algorithms of hierarchical folded cubes into linear arrays and complete binary trees with minimum wirelength,respectively.It is proved theoretically that embedding fel has the minimum wirelength when hierarchical folded cube is embedded into the linear array or complete binary tree.And the exact minimum wirelengths are calculated based on the vertex congestion.Finally,the network cost and packing density of the hierarchical folded cube are analyzed through simulation experiments.In addition,the graphical presentation interface of embedding fel is given.By comparing the metrics,it is verified that embedding fel not only has the minimum wirelength but also has advantages in reducing communication delay and queuing delay.In summary,this thesis investigates the minimum wirelength embeddings of two hierarchical networks into linear arrays and binary trees,i.e.,the minimum wirelength embeddings of hierarchical cubic networks into linear arrays and k-rooted complete binary trees,and the minimum wirelength embeddings of hierarchical folded cubes into linear arrays and complete binary trees.The corresponding embedding schemes with minimum wirelength as well as the exact minimum wirelengths are given.It is verified through simulation experiments that the proposed embedding schemes in this thesis are more advantageous in terms of wiring cost and communication performance.