并行计算机网络中的导出嵌入及其路由算法研究

发布时间：2020-04-01 11:42

【摘要】： 随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一,各种拓扑结构的互连网络,如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互连网络中,处理器之间的有效通信是衡量系统性能的一个重要标准。当处理器数目逐渐增多时,其发生故障的可能性也随之增加,不同处理器之间信息传递过程中的容错性便成为一个非常关键的问题。因此,如何找出一种新的网络容错模型以便容纳更多的错误节点,以及如何设计高效的容错路由算法以便保证无故障处理器间正确可靠的信息传递是至关重要的。超立方体网络是多处理机系统中常见的一种互连网络,这种网络拓扑结构由于具有直径小、可扩展性强、结构对称、网络寻路算法简单等优点,且多种拓扑结构的互连网络都可以很容易的嵌入其中,因而成为最重要和最具吸引力的网络模型之一。本文即是从上述两个方面,对超立方体网络的容错性和路由算法进行研究,主要研究内容如下: 1.提出一种新的并行计算机网络容错模型-LIP导出嵌入模型,包括与LIP相关的概念、性质、优点,给出了超立方体网络中求LIP的算法;针对此算法,文中给出了其C++实现程序,并求出了当维数n=6,7时LIP长度的精确值。 2.为了更好的分析超立方体网络的容错性,提出更为优越的容错路由算法,文章给出了超立方体网络中LIP容错模型的上下界估计,并给出一个非常有意义的猜想,而且结合程序结果对上下界及猜想进行了验证。结果表明,LIP不仅具有较好的容错性,而且还能保证超立方体网络的全局连通性,具有较好的实际意义。 3.基于文中提出的LIP容错模型,结合路由选择能力的概念,提出一种超立方体网络单播容错路由算法,该算法在“超立方体网络中至少存在一条无故障节点的LIP”的条件下,所能容纳的坏节点数多于2n-1,达到指数数量级;此外,该算法的最少步数为H(s, d),极坏情况为ρ(Q n) +1,且算法达到极坏情况的可能性是非常小的,因此,算法在一定程度上是比较优越的。本文在超立方体网络容错模型及路由算法方面作了一些探索工作,取得了一定的结果,但还有大量工作需要研究。特别是要进一步研究超立方体网络中的LIP容错模型,
【图文】：

节点,超立方体,维数,超立方体网络

(...)0 1 1=nX xxx和 (...)0 1 1=nY yyy之间有边当且仅当 X 和Y 仅有一位分量不同即iix ≠ y，而jjx = y，{}j ∈ ( n) i，其中 0 ≤ i ≤n 1，{ }( n )= 0,1,...,n 1，并称该边为i边。图 3.3 便是 3 维超立方体的示例，图中有32 ＝8 个节点和3132 ＝12 条边还标识出了节点的编号（从 000 到 111）。3.2 超立方体网络 LIP 导出嵌入模型上面我们给出了 LIP 导出嵌入的定义，接下来我们根据具体图例来看一下在图 3.3 所示的 3 维超立方体中，按照图 3.2 规定的维数顺序（维数顺序可任指定，它只影响节点的编号，并不影响问题的实质），000-> 001-> 011-> 111 000-> 100-> 110 均为导出路，而 000-> 001-> 011-> 111->110 和 000-> 100110-> 111-> 011 均为最长导出路(LIP)。
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2006
【分类号】：TP338.6;TP393.02

【引证文献】