局部扭立方体上若干性质的研究

发布时间：2018-03-08 16:34

本文选题：并行计算机系统　切入点：互连网络　出处：《苏州大学》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 computer is the embodiment of a country's comprehensive strength of science and technology in scientific research, education, petroleum, meteorology and other related fields play an increasingly important role. In the field of parallel processing, research on parallel computer system processor or processor connected way (interconnection network) is a very important issue. An interconnection network you can use a simple graph G= (V, E) to said, where V represents the vertex set, and E represents the edge set. Properties of the interconnection network topology is crucial for the performance of parallel computers.
One of the most important performance index of interconnection network is the network topology can be embedded into the other existing networks. Graph embedding problem is described as follows: given a graph G2= (V2, E2) and a guest (V1, E1) G1=, passengers will be embedded into the main figure G1 in figure G2 is found for each vertex in G1 to a single shot of a vertex in G2, and each edge in G1 mapping to a path of G2. Two embedding efficiency is an important index to measure the expansion (Dilation) and expansion (Expansion). The interconnection network with good performance as the main figure should have the ideal block the ability to make the guest parallel algorithm on the graph can efficiently transfer and run on it.
With the increase of network scale, interconnection network processors (processor) or the possibility of communication link failure also increases. When a fault occurs, we need to find fault and repair it. The system level fault diagnosis is to identify faulty processors (processor) process or system level fault communication link. Diagnosis can be additional investment under the condition of not increasing, improve system reliability and availability. The system level fault diagnosis according to the test strategy can be divided into non adaptive diagnosis and adaptive diagnosis. In adaptive diagnosis, test according to the test results before the allocation is dynamically allocated, the non adaptive diagnosis increased the efficiency of diagnosis, to avoid unnecessary testing.
The diameter of a graph is the maximum map between any two vertices of the shortest path. The diameter is an important index to measure the performance of communication network, it determines the communication between any vertex maximum delay. According to the definition, the diameter of the graph we can see, when removing the edges or increase the edge, may affect the vertex the distance between and the diameter of a graph. The deleted edges can express edge fault situation. Change the interconnection network diameter can influence the communication performance, so the research delete edge or increase the impact on the edge of graph diameter is a meaningful topic.
The hypercube is a kind of more general nature better interconnection network topology. The locally twisted cube (Locally Twisted Cube) is an important variant of the hypercube, it is the hypercube strong competitor, its diameter is about half of the hypercube. Let LT Qn denote the n-dimensional locally twisted cube.
This paper studies the following contents in Locally Twisted Cube: mesh embeddedness, tree embeddedness, adaptive diagnosis and edge deletion or increase of edge time diameter.
1. this paper proves that the local twisted cube has good mesh embeddedness properties:
(1) for an arbitrary integer greater than or equal to 1 N, a 2 * 2N-1 mesh can be embedded in LTQn. 1 and 1 expansion expansion
(2) for an arbitrary integer n = 4, two * 4 2n-3 vertex disjoint mesh can be extended 1 and 2 expansion of embedded LTQn.
(3) for an arbitrary integer greater than or equal to 3 N, a 4 x 2 expansion (2n-2-1) mesh can be embedded in LTQn.
The two result is optimal in terms of expansion, because of its expansion is 1.2 * 2N-1 mesh embedding expansion is 1, so the expansion is embedded in the optimal. In addition, for an arbitrary integer P = 1 and q = 1, this paper gives the analysis of the locally twisted cube 2p * 2q mesh embedding.
2. this paper proves that the local twisted cube has good tree embedding properties:
(1) for an arbitrary integer greater than or equal to 2 N, a tree with 2N-1 vertices completely two forks tree can be embedded in LTQn. 2 expansion
(2) for an arbitrary integer n = 1, LTQn to any vertex is the root can be extended 1 embedded k order two tree Bk (k is an integer, and 0 = k = n).
3. in this paper, the adaptive diagnosis of local Twisted Cubes is studied.
We prove that for any integer n = 3, LTQn at least n vertices in case of error, can be up to 4 rounds of parallel testing by adaptive diagnosis. Then, this paper gives LTQn the adaptive diagnosis algorithm description and analysis.
4. this paper studies the problem of changing the diameter of the deleting or increasing edge, and obtains the following 3 conclusions:
(1) for an arbitrary integer greater than or equal to 2 N, we found that the LTQn diameter becomes larger, at least need to delete the number of edges (ch- (LTQn) said.) for n=2, n=3 and any odd number n = 7, ch- (LTQn) =1. for n=5 and n=6, ch- (LTQn) =n-1. for n=4 and any even number n = 8, ch- (LTQn) =2.
(2) for an arbitrary integer greater than or equal to 2 N, when the LTQn of larger diameter at least need to delete the edge is deleted, we found increased LTQn diameter (diam+ (LT Qn) said, diam+) (LT Qn) =1.
(3) for an arbitrary integer n = 4, the decrease of the diameter of LTQn increased the need for at least the upper edge of 2n-1.

【学位授予单位】：苏州大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP338.6

【参考文献】