几类规则互连网络的嵌入与容错嵌入研究

发布时间：2024-03-17 14:13

　　并行计算系统的性能很大程度上取决于相应互连网络的有效性。人们通常用图来表示互连网络,图中的结点代表并行计算系统中的处理器,图中的边代表处理器之间的通信链接。在互连网络的设计和分析中,图嵌入能力是一个重要的性能指标。理想的互连网络(主图)应该拥有优秀的图嵌入能力,使得拥有规则任务图(客图)的并行算法能够在这个网络上高效的执行。 随着并行计算系统的规模不断增大,系统中将不可避免地出现故障处理器和故障通信链接。理想情况下,系统应该继续运行而不致崩溃,当然系统性能会有所下降。因此,我们非常有必要去评估互连网络的容错能力。尤其需要指出的是,互连网络的容错图嵌入能力是并行计算中一个很重要的研究课题。 前人关于图嵌入的研究工作通常把圈、路径、树、网孔和环绕等作为客图,因为它们代表了许多并行算法的任务图结构。本文中,我们研究将这些常见客图嵌入或者容错嵌入到一些著名互连网络中,其主要内容安排如下。 (1)第一章对并行计算机互连网络领域进行简要介绍,并给出互连网络和图嵌入相关的图论基础知识。 (2)第二章主要研究蜂窝环网络的容错哈密尔顿性问题。蜂窝环网络是一类很有前景的并行计算机互连网络,它的结点度是传统...

【文章页数】：106 页

【学位级别】：博士

【部分图文】：

图1.2三个笛卡尔乘积图

数的圈称为偶圈,长度为k的圈称为k-圈。phic)：两个图G和H是同构的，记为G),使得(x,y)∈E(G)(θ(x),θ(y))∈E(Htransitive)：如果对于图G中任意两个结点θ(x)=y....

图2.2两个广义蜂窝环Fig.2.2Twogeneralizedhoneycombtori

图2.2两个广义蜂窝环Fig.2.2Twogeneralizedhoneycombtori下面我们引入一些符号，以帮助我们标记广义蜂窝环中的路径和圈。给定广义蜂窝环GHT(m,n,d)的两个相邻结点(i,j)和(k,l)，我们用(i,j)→来表示路径(....

图2.3递归构造的无故障哈密尔顿圈

图2.3递归构造的无故障哈密尔顿圈.3Fault-freehamiltoniancyclesproducedbyrecursiveco窝环的容错哈密尔顿性们假设六角形蜂窝环中某个6-圈上距离为3，我们称这个6-圈为故障6-圈。我们的任务就造无故障哈密尔顿....

图2.11GHT(2,12,8)–{(0,0),(1,0)}中的无故障哈密尔顿圈

hamiltoniancycleofGHT≤k≤2d1,2≤h≤2(2,k+h1)的路径+h1)→(1,k+h1),kh+1)的路径h+1)→(1,kh+1)窝环G....

本文编号：3931149