Edgepancyclicity, pathembeddability, and t/kdiagnosability in interconnection networks
互連網絡中的邊泛圈性, 路徑可嵌入性, 及 t/k可診斷性
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution  

Supervisors/Advisors 

Award date  3 Oct 2006 
Link(s)
Permanent Link  https://scholars.cityu.edu.hk/en/theses/theses(8de4b088f94044c28ae19c33a02115f9).html 

Other link(s)  Links 
Abstract
Interconnection networks play important roles in parallel computing systems. Am ong many interconnection networks, the hypercube is one of the most popular structures. By changing some connections between the processors in hypercubes, three variants of hypercubescrossed cubes, twisted cubes, and Möbius cubes were proposed in the literature. Their diameters are about half those of the hypercubes with the same dimensions. Recently, a large family of variants of hypercubesbijective connection graphs (In brief, BC graphs), which include hy percubes, crossed cubes, twisted cubes, and Möbius cubes, were proposed. Embeddability is an important property of interconnection networks. Graph embedding is a technique in parallel computing that maps a guest graph into a host graph (usually an interconnection network). There are many applications of graph embedding, such as architecture simulation, processor allocation, VLSI layout, etc.. An important performance metric of embedding is dilation. The dilation of an embedding measures the communication delay that the host graph simulates the guest graph. Because cycles and paths are popular structures, a lot of embeddings take cycles and paths as guest graphs. There is a kind of enhanced embedding of cyclesedgepancyclicity, which refer to such a cycle embedding that a series of cycles of different lengths can be embedded in a given host graph and all these cycles pass an arbitrarily given edge in the host graph. Diagnosability is another important property of interconnection networks. Di agnosis is a process of identifying the faulty processors of the system. The maximal number of faulty nodes that a system can guarantee to diagnose is called the degree of diagnosability of the system. Pursuing high degrees of diagnosability has been an important goal in systemlevel diagnosis. Various system diagnosis strategies are based on the wellknown PMC diagnostic model. There are three diagnosis strategiesthe precise diagnosis strategy, the pessimistic diagnosis strategy, and the t/kdiagnosis strategy, based on the diagnostic model. The faultset identi fied under the precise diagnosis strategy does not contain any faultfree node, the faultset identified under the pessimistic diagnosis strategy contains at most one faultfree nodes, while the faultset identified under t/kdiagnosis strategy can con tain many faultfree nodes. In general, a system has higher degree of diagnosability under t/kdiagnosis strategy than under the other two strategies. In this thesis, we study the edgepancyclicity, pathembeddability, and t/k diagnosability of BC graphs, which include crossed cubes, twisted cubes, and Möbius cubes, etc.. For a given graph G and any two nodes u and v in G, we use dist(G, u, v) to denote the distance between u and v in G and V (G) and E(G) to denoted the node set and edge set of G, respectively. And, we use Qn, CQn, TQn, and MQn to denote the ndimensional hypercube, crossed cube, twisted cube, and Möbius cube, respectively. The original contributions of this thesis are as follows:  We study the pathembeddability and edgepancyclicity of crossed cubes. We first prove that CQn is edgepancyclic (n≥2). According to the edgepancyclicity of CQn, we then prove that a path of length l can be embedded between x and y with dilation 1 in CQn for any two distinct nodes x and y in CQn and any integer l with [n+1/2] + 1≤ l ≤2n  1 (n≥3). Furthermore, we give another style of path embedding in crossed cubesa path of length l can be embedded between x and y with dilation 1 in CQn for any two distinct nodes x and y in CQn and any integer l with dist(CQn, x, y) + 2≤ l≤ 2n  1 (n≥3). We also show the diifferences between the two styles of path embeddings in CQn. Moreover, we prove that there exist two nodes x, y2 V (CQn) such that dist(CQn, x, y) = l and any path of length l + 1 cannot be embedded between x and y with dilation 1 in CQn for any integer l with 1≤ l ≤[n+1/2]  1 (n≥3). By this result, we can conclude that [n+1/2]+1 and dist(CQn, x, y)+2 are the tight bounds on the path lengths l in the first style of path embedding and the second style of path embedding for the case 1≤dist(CQn, x, y) ≤ [n+1/2]  1, respectively.  We study the pathembeddability and edgepancyclicity of twisted cubes. We first prove that TQn is edgepancyclic (n≥3); and by the constructive proof of edgepancyclicity of twisted cubes, we give a polynomialtime algorithm for cycle embedding with edgepancyclic in twisted cubes. According to the edge pancyclicity of TQn, we then prove that a path of length l can be embedded between x and y with dilation 1 in TQn for any two distinct nodes x and y in CQn and any integer l with dist(TQn, x, y)+2≤ l≤2n  1 (n≥3). Moreover, we prove that the bound on path lengths l is tight: There exist two nodes x, y Є V (TQn) such that dist(TQn, x, y) = l and any path of length l+1 cannot be embedded between x and y with dilation 1 in TQn for any integer l with 1≤ l≤[n+1/2]  1 (n≥3). We also show that the edgepancyclicity and pathembeddability of twisted cubes are similar to those of crossed cubes, although the proof methods are di®erent from each other.  We propose a more general method to study the edgepancyclicity and path embeddability of a family of BC graphs. First, we prove that a path of length l with dist(Xn, x, y) + 2≤ l≤2n  1 can be embedded between x and y with dilation 1 in Xn for any two distinct nodes x and y in Xn, where Xn (n≥4) is an ndimensional BC graphs satisfying the three specific conditions. Furthermore, by this result, we can claim that Xn is edgepancyclic. Moreover, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also some other BC graphs.  We propose a much more general method to study the t/kdiagnosability of all the BC graphs, which include hypercubes, crossed cubes, Möbius cubes, and twisted cubes, etc.. We prove that any ndimensional BC graph is t(n, k)/k diagnosable when n≥4 and 0≤ k≤ n, where t(n, k) = (k + 1)n – 1/2 (k + 1)(k + 2) + 1. Since CQn, TQn, and MQn are specific examples of the ndimensional BC graphs, they all have the same t/kdiagnosability as Qn. As a result, the algorithms developed for diagnosis on hypercubes may also be used to diagnose the multiprocessor systems whose network topologies are based on BC graphs. We point out that all the considered embeddings are optimal in the sense that all of them have the smallest dilation 1.
 Parallel computers, Computer networks