几种BC网络上完全二叉树的嵌入研究

发布时间：2017-12-11 08:12

  本文关键词：几种BC网络上完全二叉树的嵌入研究

  更多相关文章： 互连网络 图嵌入 完全二叉树 莫比乌斯立方体 奇偶立方体 局部扭立方体

【摘要】：并行计算在教育、科研、石油、生物、气象等相关领域发挥着日益重要的作用。多处理器互连网络(简称互连网络)在很大程度上决定了并行计算系统的性能。因此,互连网络及其性质的研究是并行处理领域中的一个重要课题。互连网络可以表示为一个简单图,其中顶点代表处理器,边代表处理器之间的通信链路。在互连网络的设计和分析中,图嵌入能力是衡量一个互连网络性能优劣的重要指标。给定两个图G和H,由G到H的一个嵌入定义为由G到H的一个单射。图G和图H分别称为嵌入的客图和主图。理想的互连网络(主图)应该拥有优秀的图嵌入能力,使得拥有规则任务图(客图)的并行算法能够在该网络上高效的执行。扩张、膨胀、拥塞和负载是衡量图嵌入性能的常用指标,图嵌入的最优性能求解问题是NP难问题。由于完全二叉树具有优越性能和广泛应用,因此将其作为客图嵌入互连网络具有十分重要的研究意义。尽管完全二叉树到一般互连网络以最优性能嵌入的求解问题是NP难问题,但在一些特殊互连网络中以最优性能嵌入完全二叉树已经得到解决。迄今为止,关于将完全二叉树嵌入多种互连网络如网孔、星图、网格、蝶网等的研究已经取得了较多成果。超立方体作为一种常用的互连网络得到了众多研究者的青睐,其具有许多优越性质比如低直径、高连通性、对称性、递归构造性等。然而,完全二叉树不能以最优性能嵌入超立方体,却能以最优性能嵌入某些超立方体变型,如交叉立方体和折叠立方体。超立方体及其若干变型均具有一一对应连接和可递归构造性质,研究者依据这两个性质将它们归结为一类互连网络——BC网络。然而,关于将完全二叉树嵌入BC网络的研究成果相对较少。本文中,我们主要研究几种BC网络——莫比乌斯立方体、奇偶立方体和局部扭立方体上完全二叉树的嵌入问题。我们证明了完全二叉树能以最优性能嵌入莫比乌斯立方体和奇偶立方体,以及以较优性能嵌入和容错嵌入局部扭立方体。具体包括以下内容:1.n维莫比乌斯立方体(M_n)上完全二叉树的嵌入与交叉立方体不同的是,M_n是由两个不同构的子莫比乌斯立方体组成(n≥5)。因此,在M_n上嵌入完全二叉树将面对更复杂的情形。我们研究了M_n上完全二叉树以最优性能嵌入的问题,取得了如下研究结果:(1)证明了莫比乌斯立方体中满足的一个重要性质——由不相交子立方体构成的立方体对同构于子莫比乌斯立方体。(2)基于M_n上存在同构立方体对的性质,提出了一种对M_n上的完全二叉树嵌入进行类型划分的构造方法。(3)证明了完全二叉树能以扩张1、负载1、拥塞1和膨胀趋近于1嵌入M_n。2.n维奇偶立方体(PQ_n)上完全二叉树的嵌入与M_n上完全二叉树的嵌入方法不同,我们给出了PQ_n上完全二叉树以最优性能嵌入的证明方法。进一步,我们还设计了相应的嵌入算法和模拟实验,取得了如下研究结果:(1)证明了完全二叉树能以扩张1、负载1、拥塞1和膨胀趋近于1嵌入PQ_n。(2)给出了时间复杂度为O(Nlog N)的完全二叉树嵌入算法,其中N为PQ_n的顶点个数,并给出了算法的正确性证明。(3)设计了在PQ_n上嵌入完全二叉树的模拟实验。3.n维局部扭立方体(LT Q_n)上完全二叉树的容错嵌入随着互连网络规模的不断增大,处理器和通信链路将不可避免地出现故障。因此,我们有必要去评估互连网络的容错嵌入能力。我们研究了LTQ_n上完全二叉树的嵌入以及容错嵌入问题,取得了如下研究结果:(1)证明了以任意顶点为根的完全二叉树能以扩张2、负载1、拥塞1和膨胀1嵌入LTQ_n。(2)证明了当LTQ_n上的任意一个顶点发生故障时,LTQ_n上嵌入的完全二叉树能以扩张2和拥塞2动态重建。(3)证明了当LTQ_n上的任意两个顶点发生故障时,LTQ_n上嵌入的完全二叉树能以扩张3和拥塞3动态重建。(4)证明了当LTQ_n上的故障顶点数超过两个时,在给定的限制条件下LTQ_n上嵌入的完全二叉树能以扩张3和拥塞3动态重建。
【学位授予单位】：苏州大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前9条

1 王琦;;顺序二叉树和右(左)完全二叉树的一些性质[J];河北工学院学报;1986年03期

2 宋丽华,张福增,赵永升;完全二叉树的实时判别方法[J];烟台师范学院学报(自然科学版);2004年01期

3 朱涛;;基于遍历二叉树的方法判断完全二叉树[J];红河学院学报;2005年06期

4 白亚兰;师海忠;;完全二叉树到星连通圈网络的嵌入[J];甘肃科学学报;2014年03期

5 陈磊,沈复兴;完全二叉树理论的模型及性质[J];北京师范大学学报(自然科学版);2004年02期

6 师海忠;牛攀峰;乔韵璇;;完全二叉树到冒泡排序网络的嵌入[J];工程数学学报;2012年03期

7 王世琪;;完全二叉树理论的可数模型及其胞腔性[J];南京大学学报数学半年刊;2007年02期

8 李志敏;罗里波;李祥;;完全二叉树理论的计算复杂度[J];数学学报;2008年02期

9 ;[J];;年期

中国重要报纸全文数据库 前1条

1 ;系统设计师考试《数据结构》试题分析（上）[N];中国电脑教育报;2004年

中国博士学位论文全文数据库 前1条

1 刘钊;几种BC网络上完全二叉树的嵌入研究[D];苏州大学;2016年

中国硕士学位论文全文数据库 前4条

1 杨帆;BO-AUC多类分类评估方法的研究[D];安徽工业大学;2011年

2 范广臣;基于完全二叉树SVM烧结工况多类识别的研究与实现[D];东北大学;2009年

3 罗玉;基于XML数据库查询优化技术的研究[D];西南交通大学;2014年

4 刘舒眉;Narayana数的组合解释，，对称性及其推广[D];华东师范大学;2014年

本文编号：1277717