Research On The Embedding Of Complete Binary Trees In Several BC Networks

Parallel computing plays an increasingly important role in such areas as education,scientific research, oil exploration, biological drugs manufacturing, and weather forecast.The performance of parallel computers largely depends on the connection pattern(interconnection network) of processors or processing machines in the parallel computer system.Therefore, the study of the interconnection networks and their properties is a key subject of parallel computing. Graphically represented, an interconnection network consists of vertexes and edges, which indicate processor and communication links between processors respectively.The graph embedding ability is one of the most important indicators of an interconnection network. Given two graphs G and H, an embedding from G to H is an injective mapping Ψ. We call G the guest graph and H the host graph with respect to the embedding Ψ. An ideal interconnection network(host graph) is characterized by excellent graph embedding ability which enables efficient execution of parallel algorithms with regular task graphs on this network. There are four important metrics to measure the performance of an embedding, namely, dilation, expansion, load and congestion. To attain the embedding with optimal performance is a NP-Hard problem.Good performances and broad applications of the complete binary tree make its embedding into various interconnection architectures highly desirable. Though a NP-Hard problem with the general interconnection networks, the embeddings of complete binary trees with optimal performance into some special interconnection networks have been realized, with studies on meshes, star graphs, grids and butterfly networks being appreciably fruitful.Hypercubes, as common interconnection networks, have become a major research attraction with their lower diameter, higher connectivity, symmetry, and recursive construction, etc. Although the embedding of the complete binary tree with optimal performance into hypercubes is as yet unachievable, it has proved workable with hypercube variants,such as crossed cubes and folded cubes. Researchers group hypercubes and many of their variants into a class of interconnection networks—BC networks based on the bijective connection and recursive construction properties. However, very few studies have attempted to embed the complete binary tree into BC networks.This dissertation focuses on the embedding of complete binary trees in several BC networks— M ?bius cubes, parity cubes, and locally twisted cubes. We prove that complete binary trees can be embedded into M ?bius cubes and parity cubes with optimal performance,and that they can be embedded and fault-tolerant embedded into locally twisted cubes with better performance. The major contributions are listed as follows.1. The embedding of complete binary trees into n-dimensional M ?bius cube(Mn):Noting that the n-dimensional M ?bius cube Mnis composed of two sub-M ?bius cubes,which are not isomorphic(n ≥ 5). As a result, the embedding method of complete binary trees on Mnis more complicated than that on CQ_n. We study the embedding of complete binary trees into Mnwith optimal performance and obtain the following results:(1) We prove that M ?bius cubes possess an important property:cube couples which consist of pairwise disjoint subcubes are isomorphic to sub-M ?bius cubes.(2) Based on this property of M ?bius cubes and different types of embedding pattern,we propose a constructive method of embedding complete binary tree into Mn.(3) We prove that the complete binary tree with 2n- 1 vertices can be embedded into Mnwith dilation 1, congestion 1, load 1 and expansion tending to 1.2. The embedding of complete binary trees into n-dimensional parity cubes(PQ_n):In a more systematic approach, we not only study the embedding of complete binary trees into PQ_nwith optimal performance, but also design the related algorithms and experimental simulations. The major results are listed as follows.(1) We give an O(Nlog N) recursive algorithm which can obtain a set of complete binary trees on PQ_nand validate the correctness.(2) We prove that the complete binary tree with 2n- 1 vertices can be embedded into PQ_nwith dilation 1, congestion 1, load 1 and expansion tending to 1.(3) We devise simulation experiments to examine the the efficiency of the embedding algorithm.3. The fault-tolerant embedding of complete binary trees into n-dimensional locally twisted cubes(LT Q_n):The expansion of interconnection networks gives rise to faults in processors and communication links, which makes it essential to evaluate the fault-tolerant graph embedding ability of an interconnection network. We study the(fault-tolerant) embedding of complete binary trees into LT Q_nand obtain the following results:(1) We prove that the complete binary trees rooted at an arbitrary vertex of LT Q_ncan be embedded into LT Q_nwith dilation 2 and congestion 1.(2) We prove that with an arbitrary faulty node in LT Q_n, both the dilation and congestion values will become 2 with C BTnreconfiguration.(3) We prove that with two arbitrary faulty nodes in LT Q_n, both the dilation and congestion values will become 3 with C BTnreconfiguration.(4) We prove that with over two faulty nodes in LT Q_n, both the dilation and congestion values will become 3 with C BTnreconfiguration of the constraint.