| High performance parallel computers are comprehensive reflection of a national scientific technology strength, which are becoming more and more important in the areas of scientific research, education, petroleum, meteorology and so on. The connection patterns of processors(interconnection network) in parallel computers are critical to the performance of parallel computers. An interconnection network can be represented by a simple graph G =(V(G), E(G)), where V(G) represents the vertex set and E(G) represents the edge set. In the parallel computing domain, it is an important research topic to study interconnection networks and their properties. The alternating group graph, the WK-recursive network and the locally twisted cube are fundamental interconnection structures, which have many superior properties. So they have been widely concerned by researchers.Embeddability is an important property of an interconnection network, and graph embedding has important application in transplanting parallel algorithms and other aspects.Graph embedding problem can be modeled as follows: 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 G1 to a node of G2, and a mapping from each edge of G1 to a path in G2. Two common measures of the embedding e?ciency 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 e?ciently. Paths and meshes are two fundamental interconnect networks in parallel computing, thus many parallel algorithms are designed on the structure of paths and meshes. It is an important research direction to study embedding various kinds of paths and meshes into host graphs.This thesis studies the embedding problems in the alternating group graph, the WKrecursive network and the locally twisted cube. Two guest graphs studied in this thesis are node-disjoint paths and meshes. The specific studies are as follows.1. The problem of embedding node-disjoint path covers in the alternating group graph.This thesis proves that the alternating group graph has good path embedding property:in the n-alternating group graph(AGn), for any two distinct nodes μ and ν, there exist m node-disjoint paths for any integer n ≥ 3 with 1 ≤ m ≤ 2n- 4 whose union covers all the nodes of AGn. Since any node of AGnhas exactly 2n- 4 neighbors, 2n- 4 is the maximum number of node-disjoint paths can be constructed in AGn. The dilation and expansion of this embedding are 1, that is this embedding is optimal on those two parameters.2. The problem of embedding node-disjoint path covers in the WK-recursive network.This thesis proves that the WK-recursive network has good path embedding property:in the d base t level WK-recursive network(K(d, t)), for any two distinct nodes μ and ν,there exist m node-disjoint paths whose union covers all vertices of K(d, t) for d ≥ 4, t ≥ 1and 1 ≤ m ≤ d- 1. Since the connectivity of K(d, t) is d- 1, d- 1 is the maximum number of node-disjoint paths can be constructed in K(d, t). The dilation and expansion of this embedding are 1, that is this embedding is optimal on those two parameters.3. The problem of embedding 3D meshes in the locally twisted cube.This thesis proves that the locally twisted cube has good mesh embedding property: in the n-dimensional locally twisted cube(LT Qn), this thesis proves two major results:(1) For any integer n ≥ 4, two node-disjoint 3D meshes of size 2 × 2 × 2n-3can be embedded into LT Qnwith dilation 1 and expansion 2.(2) For any integer n ≥ 6, four node-disjoint meshes of size 4×2×2n-5can be embedded into LT Qnwith dilation 1 and expansion 4. The obtained results are optimal in the sense that the dilations of the embeddings are 1.
|
PDF Full Text Request