BC网络上独立生成树构造研究

发布时间：2018-02-16 14:45

本文关键词： 互连网络地址变换维邻接关系圆排列独立生成树　出处：《苏州大学》2014年博士论文　论文类型：学位论文

【摘要】：高性能计算机在国防太空、石油勘探、生物制药、天气预报以及基础理论研究等领域发挥着日益重要的作用，其性能很大程度上取决于系统中处理器或者处理机之间连接的方式（互连网络）。在并行处理领域，互连网络及其性质的研究是一个重要课题。一个互连网络可以用一个简单图G=(V(G), E(G))来表示，其中V(G)代表G上的顶点集合，而E(G)代表G上的边集合。超立方体是常用的互连网络之一，其许多优越性质如低直径、高连通性、对称性、递归构造性等受到众多研究者的青睐。同时，超立方体具有性能优越的变型网络如交叉立方体、莫比乌斯立方体、扭立方体等。研究者依据一一对应连接和可递归构造性质，将超立方体及其若干变型归结为一类互连网络——BC网络。在互连网络中，独立生成树在信息的可靠传输、并行传输、安全分发及故障处理器的诊断等方面具有重要的作用。本文采用从特殊到一般的方法研究BC网络上独立生成树（IST）的存在性及其构造问题，包括以下内容： 1.交叉立方体上以任一顶点为根的独立生成树的串行构造（1）证明了n维交叉立方体CQn满足一个重要的地址变换性质，依据该地址变换性质给出了CQ01n1和CQn1上同构树的构造方法。（2）给出了CQn上以任一顶点为根的n棵IST的递归构造方法，证明了其正确性，并设计了时间复杂度为O(Nlog2N)的构造算法，这里N是CQn的顶点个数。 2.莫比乌斯立方体上以任一顶点为根的独立生成树的串行构造与交叉立方体不一样的是，n维莫比乌斯立方体Mn是由两个不同构的子莫比乌斯立方体M01 n1和Mn1组成，从而交叉立方体上地址变换的方法不再适用于在莫比乌斯立方体上构造IST。我们从顶点之间维邻接关系的角度进行研究，取得了如下成果：（1）结合Mn的构造规律，从顶点之间维邻接关系的角度提出了适合于在M01n1和Mn1上构造同构树的方法。（2）基于顶点之间的维邻接关系，设计了Mn上独立生成树的构造过程中扩展顶点集合和扩展顶点集合划分的选择方法，并引入非负向量来证明其上存在IST的正确性。（3）设计了时间复杂度为O(NlogN)的递归构造算法，这里N是Mn的顶点个数。其中，Mn上基于顶点之间的维邻接关系构造M01n1和Mn1中同构树的方法同样适合在CQ01n1和CQn1中构造同构树，是CQn上地址变换方法的改进方法。另外，在Mn上所设计的IST的递归构造算法的效率比CQn上的高。 3.交叉立方体上独立生成树的并行构造从交叉立方体和莫比乌斯立方体上IST的串行构造方法来看，其对应算法的时间复杂度高且IST在构造过程中存在相互依赖的缺点，如第n棵树在构造过程中依赖于前面n1棵树，因此，寻找交叉立方体的新的性质并基于其设计独立生成树的并行构造方法以提高相应算法的效率是一个很值得研究的内容。在这方面我们取得了如下研究结果：（1）证明了交叉立方体上满足一个重要性质——维扩散性质。（2）提出一个具有UUID成员和VALUE成员的树存储结构，确保树中顶点的UUID成员总是具有唯一性。（3）基于交叉立方体上维扩散性质给出了其上IST的并行构造算法。 4.莫比乌斯立方体上独立生成树的并行构造在对交叉立方体上IST的串行和并行构造方法、莫比乌斯立方体上IST的串行构造方法总结的基础上，我们进一步研究了莫比乌斯立方体上IST的并行构造问题，取得了如下研究结果：（1）从排列组合的角度，将圆排列的概念引入到IST的构造方法中。（2）首先证明了递减的圆排列能够用于并行构造莫比乌斯立方体上以任一顶点为根的IST。其次，进一步证明了任一圆排列能够用来并行构造莫比乌斯立方体和超立方体上以任一顶点为根的IST。（3）指出利用不同的圆排列构造的多组IST能够构造莫比乌斯立方体上任意两个顶点之间多组顶点不相交路径。（4）探讨了基于IST的高效诊断算法。 5. BC网络上IST的构造特殊BC网络如超立方体、交叉立方体、局部扭立方体、莫比乌斯立方体中IST的构造及其证明依赖于其特有的性质。我们研究了基于它们的共性来构造其上的IST的一个一般性方法，取得了如下结果：（1）给出了条件BC网络的定义，证明了超立方体、交叉立方体、局部扭立方体、莫比乌斯立方体等均属于条件BC网络。同时，指出了存在不属于条件BC网络的BC网络。（2）证明了利用递增的圆排列能够在O(N)时间内构造n维条件BC网络XCn上以任一顶点为根的n棵同构于n-级类二项树的IST，这里n≥2且N=2n是XCn的顶点个数。（3）针对任一BC网络，提出了维的V排列并证明了V排列能够用来构造任一n维BC网络Xn上以任一顶点为根的生成树且证明这些生成树均同构于n级二项树。同时，指出基于V排列能够构造Xn上多组两两独立的生成树。综上所述，本文首先给出了特殊BC网络交叉立方体、莫比乌斯立方体上IST的串行构造方法。然后，在总结相关串行构造方法的基础上，设计了其上IST的并行构造方法，，并进一步研究了条件BC网络和BC网络上IST的构造问题。
[Abstract]:......
【学位授予单位】：苏州大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：O157.5;TP393.4

【参考文献】