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

几种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(NlogN)的完全二叉树嵌入算法,其中N为PQ_n的顶点个数,并给出了算法的正确性证明。(3)设计了在PQ_n上嵌入完全二叉树的模拟实验。3.n维局部扭立方体(LTQ_n)上完全二叉树的容错嵌入随着互连网络规模的不断增大,处理器和通信链路将不可避免地出现故障。因此,我们有必要去评估互连网络的容错嵌入能力。我们研究了LTQ_n上完全二叉树的嵌入以及容错嵌入问题,取得了如下研究结果:(1)证明了以任意顶点为根的完全二叉树能以扩张2、负载1、拥塞1和膨胀1嵌入LTQ_n。(2)证明了当LTQ_n上的任意一个顶点发生故障时,LTQ_n上嵌入的完全二叉树能以扩张2和拥塞2动态重建。(3)证明了当LTQ_n上的任意两个顶点发生故障时,LTQ_n上嵌入的