【作者】 韩月娟；

【导师】 钱培德； 樊建席；

【作者基本信息】 苏州大学 ， 计算机应用技术， 2013， 博士

【摘要】 高性能并行计算机是一个国家综合科技实力的体现,在科研、教育、石油、气象等相关领域发挥着日益重要的作用。在并行处理领域,研究并行计算机系统中处理器或者处理机连接的方式(互连网络)是一个很重要的课题。一个互连网络可以用一个简单图G=(V,E)来表示,其中V代表顶点集合,而E代表边集。互连网络拓扑结构的性质对于并行计算机的性能至关重要。互连网络的一个重要性能指标是其它己存在的网络拓扑结构能否嵌入该网络。图嵌入问题描述如下：给定一个主图G2=(V2,E2)和一个客图G1=(V1,E1),将客图G1嵌入到主图G2中就是找到G1中的每个顶点到G2中一个顶点的一个单射,以及G1中的每条边到G2中某一条路径的映射。衡量嵌入效率的两个重要指标是扩张(Dilation)和膨胀(Expansion)。性能良好的互连网络作为主图时应该具有理想的嵌入能力,从而能够使客图上的并行算法在其上能够高效地迁移并运行。随着互连网络规模的增大,互连网络中的处理器(处理机)或通信链路出现故障的可能性也随之变大。当故障发生时,我们需要找到故障并修复它。系统级故障诊断就是识别发生故障的处理器(处理机)或通信链路的过程。系统级故障诊断可以在不增加额外投入的情况下,提高系统的可靠性和可用性。系统级故障诊断按照测试策略可分为非自适应性诊断和自适应性诊断。在自适应性诊断中,测试分配是根据之前的测试结果动态分配的,这种方式比非自适应性诊断增加了诊断的效率,可避免不必要的测试。图的直径是图中任意两个顶点之间最短路径的最大值。直径是衡量网络通信性能的一个重要指标,它决定了任意顶点对间最大的通信延迟。根据图的直径的定义,我们可知,当删除边或者增加边时,可能会影响顶点之间的距离,进而影响图的直径。其中,删除边可以表示边故障的情形。互连网络直径的改变可以影响其通信性能,因此研究删除边或者增加边对图直径的影响是一个有意义的课题。超立方体是一种研究较多、总体性质较好的互连网络拓扑结构。局部扭立方体(Locally Twisted Cube)是超立方体的一种重要变型,它是超立方体的强有力的竞争者,其直径约为超立方体的一半。令LT Qn表示n维局部扭立方体。本文研究局部扭立方体中的以下几个内容：网孔嵌入性,树嵌入性,自适应性诊断和删除边或增加边时直径的改变问题。1.本文证明了局部扭立方体具有很好的网孔嵌入性质：(1)对于任意的整数n≥1,一个2×2n-1的网孔可以扩张1和膨胀1嵌入LTQn。(2)对于任意的整数n≥4,两个4×2n-3的顶点互不相交网孔可以扩展1和膨胀2嵌入LTQn。(3)对于任意的整数n≥3,一个4×(2n-2-1)网孔可以扩张2嵌入LTQn。前两个结果在扩张方面是最优的,因为其扩张为1。2×2n-1网孔嵌入的膨胀为1,因此该嵌入在膨胀方面也是最优的。此外,对于任意的整数p≥1和q≥1,本文还给出了局部扭立方体中2p×2q网孔嵌入的分析。2.本文证明了局部扭立方体具有很好的树嵌入性质：(1)对于任意的整数n≥2,一棵具有2n-1个顶点的完全二叉树可以扩张2嵌入LTQn。(2)对于任意的整数n≥1,LTQn中以任意顶点为根可以扩张1嵌入k阶二项树Bk(k为整数,且0≤k≤n)。3.本文研究了局部扭立方体的自适应性诊断：本文证明对于任意的整数n≥3,LTQn在至多n个顶点出错的情况下,可以在至多4轮并行测试中被自适应性诊断。然后,本文给出了LTQn的自适应性诊断算法描述及其分析。4.本文研究了删除边或增加边时直径的改变问题,得到了以下3个结论：(1)对于任意的整数n≥2,我们找到了使LTQn直径变大,至少需要删除的边数(用ch-(LTQn)表示)。对于n=2,n=3和任意的奇数n≥7,ch-(LTQn)=1。对于n=5和n=6,ch-(LTQn)=n-1。对于n=4和任意的偶数n≥8,ch-(LTQn)=2。(2)对于任意的整数n≥2,当使LTQn直径变大至少需要删除的边被删除时,我们找到了LTQn直径的增加值(用diam+(LT Qn)表示),diam+(LT Qn)=1。(3)对于任意的整数n≥4,使LTQn直径减小,至少需要增加边的上界为2n-1。更多还原

【Abstract】 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.更多还原