Research On The Properties Of The Locally Twisted Cube

High performance parallel computers are becoming more and more important in the ar-eas of scientific research, education, petroleum, meteorology and so on. In the parallel com-puting domain, it is an important research topic to study the connection pattern(interconnection network) of processors or process computer units in the parallel computer system. An inter-connection network can be represented by a simple graph G=(V, E), where V represents the vertex set and E represents the edge set. The topology properties of interconnection networks are important to the performance of parallel computers.One of the critical performance factors of interconnection network is whether other existing networks can be embedded into this one. This can be modeled by the following graph embedding problem:given a host graph G2=(V2, E2) and a guest graph G1=(V1, E1), which represent the network where other networks are to be embedded and the network to be embedded, respectively. The problem becomes finding an injective mapping from each node of G1to a node of G2, and a mapping from each edge of G1to a path in G2. Two common measures of the embedding efficiency are dilation and expansion. A good interconnection network is supposed to possess ideal graph embedding ability as host graph, such that parallel algorithms in guest graphs can be migrated and executed on this network efficiently.When the system scale becomes bigger, the faulty probability of the processors or links in the system becomes higher. When the fault occurs, we need to find the fault and repair it. The fault location is a more difficult problem. System-level fault diagnosis is to find the faulty processors or links. System-level fault diagnosis can improve the system reliability and usability without adding extra system input costs. System-level fault diagnosis can be divided into non-adaptive diagnosis and adaptive diagnosis by the test strategy. In adaptive diagnosis, the test allocations are dynamically decided by the previous test results, which can increase the efficiency of diagnosis compared to the non-adaptive diagnosis, and avoid the unnecessary tests.The diameter of a graph is the maximum value of the shortest path length between any two nodes in graph. One of the critical performance factors of an interconnection network is the diameter, which determines the maximum communication time between any pair of nodes. By the definition of graph diameter, we know that deleting edges from a graph or adding edges to a graph may affect the distance between nodes, and then the diameter of the graph will be changed, where deleting edges can denote the scenario of edge faults. The change of graph diameter can affect its communication performance, thus, it is a meaningful topic to study the diameter variability arising from the deletion of edges or the addition of edges in a graph.The hypercube network Qn has been proved to be one of the most popular interconnec-tion networks. The locally twisted cube is an important variant of hypercube. It has many attractive features as compared to the hypercube, for instance, the diameter is only about half of that of Qn. Let LT Qn denote the n-dimensional locally twisted cube.This thesis will study the following properties of the locally twisted cube:mesh em-bedding property, tree embedding property, adaptive diagnosis problem and the diameter variability problem arising from the deletion of edges or the addition of edges. The major contributions are listed as follows.1. The locally twisted cube is proved to have good mesh embedding property:(1) For any integer n≥1, a2x2n-1mesh can be embedded in LTQn with dilation1and expansion1.(2) For any integer n≥4, two node-disjoint4x2n-3meshes can be embedded in LTQn with dilation1and expansion2.(3) For any integer n≥3, a4x (2n-2-1) mesh can be embedded in LTQn with dilation2.The first two results are optimal in the sense that the dilations of all embeddings are1. The embedding of the2x2n-1mesh is also optimal in terms of expansion. We also present the analysis of2p x2q mesh embedding in locally twisted cubes.2. The locally twisted cube is proved to have good tree embedding property:(1) For any integer n≥2, we show that a complete binary tree with2n-1nodes can be embedded into LTQn with dilation2.(2) For any integer n≥1, a binomial tree Bk(0≤k≤n) can be embedded into LTQn with any node as its root with dilation1.3. Adaptive diagnosis in the locally twisted cube is studied in this thesis.This thesis proves that for any integer n≥3, LTQn can be adaptively diagnosed using at most4parallel testing rounds, with at most n faulty nodes. The proof and algorithm description of adaptive diagnosis in LTQn also have been proposed. 4. Diameter variability problems arising from the deletion of edges and addition of edges in LTQn are investigated. Three results are obtained about diameter variability prob-lems:(1) For any integer n≥2, we find the least number of edges (denoted by ch-(LT Qn)), whose deletion from LT Qn causes the diameter to increase. For n=2,n=3and any odd integer with n≥7, ch-(LTQn)=1. For any integer with n=5and n=6, ch-(LTQn)=n-1. For n=4and any even integer with n≥8, ch-(LTQn)=2.(2) For any integer n≥2, we find the exact augmentation value of the diameter of LTQn, when edges(ch-(LTQn)) are deleted from LTQn(denoted by diam+(LTQn)), diam+(LTQn)=1.(3) For any integer n≥4, the least number of edges whose addition to LTQn will decrease the diameter is at most2n-1.