一、超立方体多处理机系统中基于扩展最优通路矩阵的容错路由(论文文献综述)
马良[1](2016)在《超立方体网络上与距离相关的容错性研究》文中认为随着计算机科学和信息化网络技术的发展,高性能计算机在社会各个领域发挥着日益重要的作用。高性能计算机的性能在很大程度上取决于其系统内部处理器之间的连接方式(互连网络)。互连网络的拓扑结构及其性质的研究是并行计算领域的研究重点之一。互连网络一般可以用一个简单图G=(V(G),E(G))来表示,其中V(G)表示图G中的顶点集合,代表互连网络中的处理器,E(G)表示图G中的边集合,代表处理器之间的链路。随着互连网络规模的不断扩大,网络中处理器和链路的数目也逐渐增多,处理器或链路发生故障的概率也会随之增加。在网络发生故障的情况下网络中某些特性能否继续保持,这就是网络的容错性,它是衡量互连网络性能的一项关键指标。超立方体网络是多处理器系统中一种常用的互连网络,它具有很多优越的性质,例如直径较小、结构对称、递归构造、可扩展性强等。基于该网络,研究者们已经提出了许多性能优越的超立方体变型网络,例如交叉立方体、扭立方体、莫比乌斯立方体等。因此,超立方体网络已成为多处理器系统中最基础也最重要的网络模型之一。本文在结合理论分析的基础上,就超立方体网络的容错性提出了新的测量方法,并且在该方法的限制条件下,研究了超立方体网络上的条件连通度,容错单播路由算法以及容错哈密顿性质。主要研究内容如下:1.本文提出一种与距离相关的新的条件(边)连通度――(g,d,k)-条件(边)连通度。与其他条件连通度相比,(g,d,k)-条件(边)连通度的要求更符合实际情况,并且允许存在更多的故障顶点(边)。它为研究超立方体等网络的容错性提供了新的衡量指标。2.本文研究了超立方体网络上某些特定的(g,d,k)-条件(边)连通度,包括κ1,1,k(Qn),κ1,d,2(Qn),λ1,1,1(Qn)和λ1,d,2(Qn)。这些结果为后续研究超立方体网络上其他(g,d,k)-条件(边)连通度提供了参考,也为在超立方体变型网络等其他网络上研究(g,d,k)-条件(边)连通度提供了方法上的指导。3.本文在(1,1,1)-条件连通的情况下提出了一种基于局部信息的容错单播路由算法,该算法通过构建长度不超过3的跨越路径来选择用于路由的维度。本文分析了该算法的时间复杂度以及空间复杂度,并且和现有的几种单播路由算法从成功率,运行时间,路径长度等方面进行了比较。4.本文结合(g,d,k)-条件边连通的概念,提出了一种新的条件容错哈密顿性质:f-(g,d,k)条件边容错哈密顿。本文证明,当n≥4时,n维超立方体是(4n-13)-(3,0,0)条件边容错哈密顿的,并且这一结果是最优的。最后,对本文工作进行了总结,并对后续的研究工作进行了展望。
王洪伟[2](2013)在《超立方体网络中多播路由优化策略研究》文中提出超立方体是一种具有优良性质的拓扑,它具有高度冗余通信路径与强容错通信能力、结构对称引入的自嵌入性、便于增加节点的可扩展性、网络寻路算法简洁性等优点。并且其它多种类型拓扑网络均可以便捷的与之相结合形成复合型拓扑,从而该型拓扑成为了高性能并行计算机系统设计中最具吸引力的网络模型之一。应用超立方体作为拓扑连接方式的并行计算机系统性能在很大程度上取决于其所采用的多播路由策略,其主要包括多播通信策略,容错多播通信策略和不相交路径多播通信策略。多播操作产生的通信量在众多并行计算机运算环境中的全部通信量中占相当大比重,设计能够提供高效通信服务的多播通信策略是提高系统通信效率和计算机整体可靠性的有效途径。而并行计算机规模扩大带来计算节点增多,系统中出现计算节点或通信链路故障频率也随之变高,因而在存在部分节点故障和连接故障情况下为了保证系统连续正确运行,设计产生通信信息量尽量小的容错多播通信策略是一个重要挑战性问题。不相交路径路由策略从目标节点数量上分为单目标节点和多目标节点两类,单目标节点不相交路径路由是增大节点间网络带宽并提高容错能力的综合解决方案,而多目标节点不相交路径通信可以看作是以路径不相交为约束条件的多播通信,他们为网络及系统可靠性提供了更高层次保障。如何在容错能力,通信效率,通信开销等方面对这三种通信策略进行优化成为超立方体网络路由策略研究的热点问题。本文的主要研究内容如下:以减少基于树型拓扑多播策略通信开销为目标,提出了一个超立方体网络基于逐层聚簇策略的启发式多播树构造算法(LWC-MT)。利用树型拓扑多播方案生成过程的分析结论及分簇模型,LWC-MT采用了以聚簇代价沿着最小增长方向进行聚簇操作的方法,对多播树建立过程进行了优化。仿真实验结果也表明,该算法在通信开销上优于现存算法。以在保证一定容错通信能力条件下减小多播通信开销为目标,提出了一种容错多播路由策略(FT-MT)和基于局部k维子立方连通超立方体网络的分布式容错多播路由策略(DFT-MT)。FT-MT利用近优容错路径存储模型构造容错多播方案,在保证容错能力的同时,得到了降低多播方案总体网络通信开销的优化结果。DFT-MT针对局部k维子立方连通超立方体网络,实现了对近优容错路径存储模型局部化管理和分布式存储,规避了近优容错路径存储模型在更新过程中的大量信息交换开销。模拟实验结果显示在确保满足局部k维子立方连通约束条件下,算法产生的通信开销优于相关文献中的方法。针对基于路径的多播通信中大量目标节点情况下对路径长度进行优化的问题,提出了一种基于极大目标节点分布密度的多播路径构造策略(MDPMP)和基于蚁群的多播路径构造算法(AMPA)。MDPMP利用目标节点分布密度不均匀性质进行子立方体划分,从而构造多播路径。仿真实验数据显示出在目标节点较多情形下,算法输出路径长度优于相关文献中的策略。为获得更短的多播路径,引入蚁群算法来求取子立方体划分问题(其为组合优化问题)的优化解,并以此建立多播路径,仿真实验数据表明路径长度得到了减小。进一步,论文通过把MDPMP和AMPA相结合的方式给出了分布式蚁群优化策略,有效缓解了蚁群算法引入较大计算时间复杂度问题。实验获得的数据显示,相对于源节点计算路由策略,分布式优化算法对优化结果的影响在可接受范围之内。以减小节点不相交路径通信策略的路径长度为目标,提出了一种一对多目标节点不相交容错优化路径算法和一对一不相交容错双路径算法。一对多目标节点不相交容错优化路径算法利用近优容错路径存储模型优化生成多条不相交路径,其在最长路径上限和平均路径长度两方面均优于已有算法。然后,基于一对一节点不相交多路径的特点,即在大多数情况下两条不相交路径提供了比较充分容错能力和接近扩展一倍的网络带宽,并且其求解效率也明显高于求解多于两条不相交路径,在此条件下,给出了一对一节点不相交容错双路径算法,该算法生成两条不相交路径中至少一条是两点之间经过近优容错路径矩阵充分优化的路径。
章毅[3](2012)在《K-Ary N-Cubes网络中离性能无死销多播路算法研究》文中研究指明互连网络是构成高性能并行多处理器计算机系统和决定系统通信性能的关键部分。K元N立方体是人们最早研究且仍是目前最重要的互连网络拓扑结构之一。在K元N立方体中,每一维上,每一个结点物理上都只与临结点相连。这是K元N立方体一个重要优势,使得硬件实现容易,并具有可扩展性。由于硬件上的优势和理论的普遍性K元N立方体己成为多处理器体系结构的研究焦点。多播路由技术一直是当前K元N立方体互连网络领域内的前沿和重点研究课题,因此,展开对K元N立方体网络多播路由技术的有关理论与应用技术方面的研究有非常重要的理论意义和实际意义。本文针对K元N立方体网络,提出了一种无死锁新的多播路由算法MRIFF(Multicast Routing Based on Independent Flit Flow)。在MRIFF算法中为了使得微片能够携带额外的确定它们归属的标识信息,微片的流动相互独立。附加的信息用于避免死锁。MRIFF算法允许一旦中间结点的连接准备好传送时结点发送微片。MRIFF多播路由算法消除了增加死锁避免,检测和恢复机制的必要,但是需要更大的输出缓冲。最后,利用OPNET对所提多播路由算法在不同流量模式下进行了模拟实验。模拟结果表明提出的新多播路由算法相比已有的同类算法,如DOR (dimension order routing), HTA (hardware tree-based routing), DFMR (deadlock-free multicast routing algorithm)在平均消息延迟、平均通信开销、平均负载等方面性能要优于其它协议。本文的研究工作对K元N立方体网络多播路由设计与研究具有重要的理论和实践意义。
李银,梁家荣,伍华健[4](2009)在《Torus网络中基于标志位的容错路由》文中提出针对Torus结构的多处理机系统中容错路由的问题,提出标志位概念,给出一个基于标志位的容错路由算法。存储于Torus网络中各节点的标志位记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路。标志位的赋值可以通过与邻节点间的信息交换完成。
张玫[5](2009)在《超立方体网络容错模型及其路由算法研究》文中指出随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一,各种拓扑结构的互连网络,如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互连网络中,处理器之间的有效通信是衡量系统性能的一个重要标准。当处理器数目逐渐增多时,其发生故障的可能性也随之增加,不同处理器之间信息传递过程中的容错性便成为一个非常关键的问题。因此,如何设计新的网络容错模型以便容纳更多的错误结点,以及如何设计高效的容错路由算法以便保证无故障处理器间正确可靠的信息传递是至关重要的。超立方体网络是多处理机系统中常见的一种互连网络,这种网络拓扑结构由于具有直径小、可扩展性强、结构对称、网络寻路算法简单等优点,且多种拓扑结构的互连网络都可以很容易的嵌入其中,因而成为最重要和最具吸引力的网络模型之一。本文基于LIP容错模型和局部连通性,对超立方体网络的容错性和路由算法进行研究,主要研究内容如下:1.给出了超立方体网络及其k维子立方体的概念,同时结合LIP的相关概念和性质,给出了对求解LIP长度的程序的改进,并根据程序的运行结果进行了分析。2.结合第二章最长导出路LIP的概念,提出了超立方体中基于LIP的广播容错路由算法。该算法是基于“超立方体中至少存在一条无故障结点的LIP”的前提条件的,在此条件满足的情况下,超立方体是全局连通的,且该算法能容许大量的错误结点(2n-1甚至更多),在容错性上有了很大提高。3.基于LIP容错模型和超立方体中的4维子立方体,提出超立方体网络中的一种单播容错路由算法。该算法在必要的搜索时间内,在具有大量错误结点的超立方体网络中找出连接两个正确结点的路径,并且该算法是基于局部信息的,因而具有很好的实际意义。本文在超立方体网络容错模型及路由算法方面作了一些探索工作,取得了一定的结果,但还有大量工作需要研究。首先,进一步研究超立方体网络中的LIP容错模型,给出LIP长度的近似或精确计算公式,以便更好的进行容错分析;其次,深入研究并行计算机互连网络尤其是超立方体网络中的各种容错路由算法,以便结合LIP容错模型,提出更加优越的容错路由算法;再次,对各种容错路由算法进行网络模拟,比如用NS2进行模拟,通过模拟结果对路由算法进行更加深入的分析。
王福龙,苑召国,梁丽萍[6](2008)在《超立方体中基于安全矩阵的容错路由》文中指出超立方体网络拓扑结构是多处理机系统中常见的一种。随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大。针对超立方体结构的容错路由设计在信息传输过程中出现迂回的情况,提出了安全矩阵(safety matrices,简称SMs)这一概念,给出了一种建立SMs的方法及其容错路由算法。n维超立方体每个结点所需的存储开销为n2个字,安全矩阵记录了局部更多的信息。与传统的路由算法相比,该算法可以避免信息在传输过程中出现迂回和死锁,使路径达到最优。
苑召国,郭大昌[7](2008)在《超立方体中基于极大安全链路矩阵的容错路由》文中研究说明超立方体网络拓扑结构是多处理机系统中常见的一种.随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全链路矩阵(maximum safety-link matrices,MSLMs)这一概念,给出了一种建立MSLMs及其容错路由算法.通过n-1轮邻结点的信息交换,用矩阵的形式记录最优通路;与已有的容错路由算法相比,极大安全链路矩阵解决了如何用矩阵的形式来记录最多最优通路数的问题.
苑召国[8](2008)在《具有大量错误结点的超立方体网络基于矩阵容错路由算法的设计与讨论》文中进行了进一步梳理超立方体网络拓扑结构是多处理机系统中常见的一种,并且在Internet上具有广泛的应用,因此基于超立方体网络的容错性成为研究的焦点。随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大。论文在介绍相关基本概念及国内外相关研究现状的基础上,首先针对传统的容错路由算法进行了分析,并找出传统路由算法在解决迂回与死锁问题上的缺点,提出了安全矩阵容错路由算法,针对传统路由算法只能搜索最优通路而不能记录最优通路的条数,提出了极大安全链路矩阵容错路由算法,并对搜索结果进行了数据分析。本文具体做了以下两方面的工作:(1)论文针对超立方体结构的容错路由设计在信息传输过程中出现迂回和死锁的情况,提出了安全矩阵(safety matrices,简称SMs)这一概念,给出了一种建立SMs的方法及其容错路由算法,并对安全矩阵的相关性质进行了证明。n维超立方体每个结点所需的存储开销为n2个字,安全矩阵记录了局部更多的信息。与传统的路由算法相比,该算法可以避免信息在传输过程中出现迂回和死锁,使路径达到最优。(2)论文针对超立方体结构的多处理机系统中存在链路故障的情况,在信息的传输过程中传统的路由算法只能判断源结点与目的结点之间是否存在最优通路而不能记录最优通路的条数,提出了用于最优通路记录的极大安全链路矩阵(maximum safety-link matrices,简称MSLMs)这一概念,给出了一种建立MSLMs及其容错路由算法,并对极大安全链路矩阵的相关性质和定理进行了证明。通过n-1轮邻结点的信息交换,用矩阵的形式记录最优通路;与已有的容错路由算法相比,极大安全链路矩阵解决了如何用矩阵的形式来记录最多最优通路数的问题。并且在超立方体中含有的错误结点或错误联接越多,极大安全链路矩阵的形式就越简单。
田绍槐,陆应平,张大方[9](2007)在《基于NPV广义超立方体最佳容错路由算法(英文)》文中认为在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1)定义广义超立方体系统;(2)在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3)提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4)提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.
张涌逸[10](2007)在《具有扩展的局部连通性的超立方体网络中的容错路由》文中研究指明在n—维超立方体中,去掉一个结点u的n个邻接点,u将和其余的结点不连通,所以一般认为n—维超立方体的容错度是n–1,即对于任一结点v的n个相邻结点,允许其中n–1个结点发生故障,此时,n—维超立方体仍然保持连通。然而这是一种极端的情况,使用该方法作为n—维超立方体的容错度存在很多不足,在n—维超立方体网络中,n个故障结点正好是某一正确结点的相邻结点的概率非常低,因此,上面用于确定容错度的方法与实际情况是有差距的。为了提高系统的容错路由能力,人们做了大量的工作。王国军等人在在更一般的形式下针对大量错误结点给出了两个基于两类局部连通性容错路由算法,但错误结点数不超过超立方体网络Hn结点数的一半。本文在局部连通性的基础上,提出了针对超立方体网络Hn的扩展的局部k—维子立方体连通性以及扩展的局部子立方体连通性概念;证明了具有扩展的局部k—维子立方体连通性或扩展的局部子立方体连通性的Hn中正确结点间是连通的;基于扩展的局部子立方体连通性的超立方体网络Hn给出了单播容错路由算法;基于扩展局部k—维子立方体连通性的超立方体网络Hn给出了单播、广播、多播容错路由算法。由模拟实验结果知相对基于局部连通性路由算法而言基于扩展局部连通性路由算法提高了网络的容错性和通用性。
二、超立方体多处理机系统中基于扩展最优通路矩阵的容错路由(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、超立方体多处理机系统中基于扩展最优通路矩阵的容错路由(论文提纲范文)
(1)超立方体网络上与距离相关的容错性研究(论文提纲范文)
摘要 |
Abstract |
第一章 绪论 |
1.1 研究背景 |
1.1.1 并行计算 |
1.1.2 互连网络 |
1.2 研究现状 |
1.3 研究内容及意义 |
1.4 文章组织结构 |
第二章 相关知识 |
2.1 基本概念和符号表示 |
2.2 超立方体及其性质 |
2.2.1 超立方体的定义 |
2.2.2 超立方体的性质 |
2.3 本章小结 |
第三章 超立方体上的(g, d, k)-条件(边)连通度 |
3.1 (g, d, k)-条件(边)连通度的定义 |
3.2 超立方体上的(1, 1, k)-条件连通度 |
3.3 超立方体上的(1, d, 2)-条件连通度 |
3.4 超立方体上的(1, 1, 1)-边条件连通度 |
3.5 超立方体上的(1, d, 2)-边条件连通度 |
3.6 本章小结 |
第四章 超立方体上的条件容错单播路由算法 |
4.1 超立方体上的容错路由算法的研究现状 |
4.2 (1, 1, 1)-条件连通下的容错单播路由算法 |
4.3 算法复杂度分析 |
4.4 模拟实验 |
4.5 本章小结 |
第五章 超立方体上的条件容错哈密顿性质 |
5.1 相关性质和引理 |
5.2 超立方体上新的条件容错哈密顿性质 |
5.3 本章小结 |
第六章 总结与展望 |
6.1 总结 |
6.2 展望 |
参考文献 |
攻读硕士学位期间发表的论文和参与的科研项目 |
致谢 |
(2)超立方体网络中多播路由优化策略研究(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 课题背景及研究的目的和意义 |
1.2 互连网络拓扑的发展与超立方体网络 |
1.2.1 并行计算互连网络概述 |
1.2.2 从线性阵列到 Petersen 网络 |
1.2.3 超立方体网络的定义、性质及其扩展 |
1.3 超立方体网络的三个关键通信问题 |
1.3.1 通信问题概述 |
1.3.2 容错通信问题 |
1.3.3 聚合通信与多播通信问题 |
1.3.4 不相交多路径通信问题 |
1.4 研究现状与挑战 |
1.4.1 容错通信模型 |
1.4.2 多播通信与容错多播通信 |
1.4.3 不相交多路径通信 |
1.5 本文的主要研究内容与组织结构 |
第2章 基于逐层聚簇的多播树路由优化策略 |
2.1 引言 |
2.2 多播树路由策略的相关研究工作 |
2.3 基于逐层聚簇的多播树路由算法 |
2.3.1 多播树模型分析与分簇模型的提出 |
2.3.2 基于逐层聚簇的多播树算法 |
2.3.3 算法示例 |
2.3.4 性能与时间复杂度 |
2.3.5 仿真实验及结果分析 |
2.4 本章小结 |
第3章 基于近优容错路径存储模型的容错多播优化策略 |
3.1 引言 |
3.2 容错多播路由算法相关研究工作 |
3.3 近优容错路径存储模型与容错多播路由算法 |
3.3.1 近优容错路径存储模型 |
3.3.2 近优容错路径存储模型更新算法 |
3.3.3 基于近优容错路径存储模型的多播路由算法 |
3.3.4 算法示例 |
3.3.5 时空复杂度分析 |
3.4 子立方体间-子立方体内分级存储模型与多播路由策略 |
3.4.1 局部连通性容错模型及其性质 |
3.4.2 基本思想 |
3.4.3 子立方体间-子立方体内分级容错存储模型 |
3.4.4 邻接子立方体连通矩阵更新算法 |
3.4.5 单播容错路由算法 |
3.4.6 多播容错路由算法 FTMRA |
3.4.7 算法示例 |
3.4.8 时间复杂度分析 |
3.5 算法的模拟实验与分析 |
3.5.1 近优容错路径存储模型的单播容错路由算法 FTMA |
3.5.2 FTMT 算法和 FTMRA 算法仿真 |
3.6 本章小结 |
第4章 基于目标节点密度信息的多播路径优化策略 |
4.1 引言 |
4.2 多播路径构建策略相关研究工作 |
4.3 基于极大目标节点密度子立方体划分的多播路径构造算法 |
4.3.1 目标节点分布密度与多播路径附加通信量关系 |
4.3.2 基于极大目标节点密度子立方体划分的多播路径算法 |
4.3.3 算法示例 |
4.3.4 仿真实验 |
4.3.5 算法时间复杂度分析 |
4.4 基于蚁群的多播路径优化算法 |
4.4.1 蚁群算法优化原理与多播路径求解问题 |
4.4.2 子立方体优化划分问题 |
4.4.3 基于蚁群优化的多播路径构造算法 |
4.4.4 分布式蚁群优化算法 DAMPA |
4.4.5 算法复杂度分析 |
4.4.6 仿真实验与参数选择 |
4.5 本章小结 |
第5章 基于近优容错路径存储模型的节点不相交优化路径构造策略 |
5.1 引言 |
5.2 节点不相交多路径构造算法相关工作 |
5.2.1 Node to node 节点不相交多路径研究成果 |
5.2.2 Node to set 节点不相交多路径研究成果 |
5.3 基于近优容错路径存储模型的不相交路径策略设计思想 |
5.4 NODE TO SET节点不相交容错优化路径 |
5.4.1 Node to set 节点不相交路径的相关定理及性质 |
5.4.2 近优容错路径矩阵的扩展和性质 |
5.4.3 Node to set 节点不相交容错优化路径路由算法 |
5.4.4 算法正确性与时间复杂度分析 |
5.4.5 最长路径长度上确界与平均路径长度分析 |
5.4.6 DMPA 算法示例 |
5.5 NODE TO NODE节点不相交容错优化路径 |
5.5.1 Node to node 问题到 node to set 问题的转换 |
5.5.2 Node to node 不相交容错优化双路径算法 |
5.5.3 DSM2PF 算法示例 |
5.5.4 路径长度与时间复杂度分析 |
5.6 本章小结 |
结论 |
参考文献 |
攻读博士学位期间发表的论文及其它成果 |
致谢 |
个人简历 |
(3)K-Ary N-Cubes网络中离性能无死销多播路算法研究(论文提纲范文)
摘要 |
ABSTRACT |
第一章 绪论 |
1.1 课题研究背景 |
1.2 互连网络 |
1.2.1 操作方式 |
1.2.2 控制策略 |
1.2.3 交换技术 |
1.2.4 拓扑结构 |
1.2.5 基于总线的动态互连网络 |
1.2.6 基于交换的互连网络 |
1.2.7 静态互连网络 |
1.2.8 消息传递系统 |
1.2.9 连网络的多播路由 |
1.2.10 路由的潜在问题 |
1.3 国内外研究现状 |
1.4 论文的组织结构 |
第二章 相关研究 |
2.1 相关概念 |
2.2 软件多播路由 |
2.3 列路径多播路由 |
2.4 双重路径和多重路径多播路由 |
2.5 限制组多播路由 |
2.6 硬件基于树多播路由 |
2.7 超立方体中多播路由 |
2.8 超立方体中容错多播路由 |
2.9 本章小结 |
第三章 MRIFF多播路由算法 |
3.1 微片结构 |
3.2 结点结构 |
3.3 MRIFF算法路由 |
3.4 MRIFF最佳路径过程 |
3.5 确认机制,传播与转播 |
3.6 检测和控制输出队列拥塞 |
3.7 MRIFF算法转换功能 |
3.8 MRIFF的执行复杂性 |
3.9 本章小结 |
第四章 性能研究 |
4.1 实验工具及性能参数设置 |
4.2 实验结果分析 |
4.3 本章小结 |
第五章 总结与展望 |
5.1 总结 |
5.2 展望 |
参考文献 |
致谢 |
(4)Torus网络中基于标志位的容错路由(论文提纲范文)
1 概述 |
2 预备知识 |
3 标志位赋值及性质 |
3.1 标志位的赋值算法 |
3.2 标志位的性质 |
4 路由算法和实验结果 |
4.1 路由算法 |
4.2 性能分析与实验结果 |
5 结束语 |
(5)超立方体网络容错模型及其路由算法研究(论文提纲范文)
摘要 |
ABSTRACT |
第一章 绪论 |
1.1 课题的研究背景 |
1.2 课题的研究意义 |
1.3 国内外相关研究现状 |
1.4 本文的主要工作 |
第二章 超立方体网络及LIP导出嵌入模型 |
2.1 超立方体网络简介 |
2.2 LIP导出嵌入模型 |
2.2.1 相关的定义和记号 |
2.2.2 超立方体网络LIP导出嵌入模型 |
2.2.3 LIP的性质 |
2.3 对求解LIP程序的改进 |
2.3.1 求解LIP的算法及原程序 |
2.3.2 改进程序 |
2.3.3 程序的运行结果及分析 |
第三章 基于LIP的广播容错路由算法 |
3.1 引言 |
3.2 算法的前提条件 |
3.3 算法思想 |
3.4 算法描述 |
3.5 算法分析与评价 |
3.5.1 算法的可行性分析 |
3.5.2 算法的容错性分析 |
第四章 基于LIP和4维子立方体的单播容错路由算法 |
4.1 概述 |
4.2 局部连通性 |
4.2.1 局部连通性定义 |
4.2.2 局部连通性隐含的全局连通性 |
4.3 单播容错路由算法 |
4.3.1 算法的前提条件 |
4.3.2 算法思想 |
4.3.3 算法描述 |
4.3.4 算法分析 |
4.3.4.1 算法的可行性分析 |
4.3.4.2 算法的容错性分析 |
4.3.4.3 算法的复杂性分析 |
4.3.4.4 为何选择4维子立方体 |
第五章 结束语 |
5.1 本文的主要内容 |
5.2 进一步的研究工作 |
参考文献 |
附录一 求Hypercube中LIP的改进程序 |
附录二 当n=7时的两条LIP |
攻读硕士学位期间发表的论文 |
攻读硕士学位期间参与的科研项目 |
致谢 |
(6)超立方体中基于安全矩阵的容错路由(论文提纲范文)
1 安全矩阵 |
1.1 预备知识 |
1.2 安全矩阵 |
2 路由算法 |
2.1 传统路由算法 |
2.2 安全矩阵路由算法 |
3 结束语 |
(7)超立方体中基于极大安全链路矩阵的容错路由(论文提纲范文)
1 极大安全链路矩阵 |
1.1 预备知识 |
1.2 极大安全链路矩阵 |
1.3 SVs、ESVs、OPMs、EOPMs、MSPMs与MSLMs数据对比示例 |
2 路由算法与性能分析 |
3 结论 |
(8)具有大量错误结点的超立方体网络基于矩阵容错路由算法的设计与讨论(论文提纲范文)
中文摘要 |
ABSTRACT |
目录 |
CONTENTS |
第一章 绪论 |
1.1 研究内容及意义 |
1.1.1 研究内容 |
1.1.2 课题研究意义 |
1.2 基本概念介绍 |
1.3 超立方体网络结构的扩展与容错性研究 |
1.3.1 基于结构特性的扩展 |
1.3.2 基于应用特性的扩展 |
1.4 基于超立方体的容错性及容错路由算法的研究与进展 |
1.4.1 网络容错模型 |
1.4.2 单播容错路由算法的研究 |
1.4.3 广播容错路由算法的研究 |
1.4.4 并行容错路由算法的研究 |
1.5 本文的主要工作及结构安排 |
第二章 安全系数和安全向量模型 |
2.1 安全系数模型的算法 |
2.2 安全系数算法的局限与改进 |
2.3 安全向量算法模型 |
2.4 安全向量算法的局限与改进 |
第三章 安全矩阵的定义与路由算法 |
3.1 安全矩阵 |
3.1.1 安全矩阵的定义 |
3.1.2 安全矩阵的性质 |
3.2 安全矩阵路由算法的提出 |
3.2.1 传统的路由算法 |
3.2.2 安全矩阵路由算法 |
3.3 本章小结 |
第四章 极大安全链路矩阵的定义与路由算法 |
4.1 极大安全链路矩阵 |
4.2 路由算法与性能分析 |
4.3 本章小结 |
结论 |
参考文献 |
攻读硕士学位期间所发表学术论文情况 |
致谢 |
(9)基于NPV广义超立方体最佳容错路由算法(英文)(论文提纲范文)
1 Introduction |
2 Related Work |
3 Preliminaries and Notations |
4 Node Path Vectors (NPV) |
4.1 Definition of node path vectors |
4.2 Example of NPV calculation |
4.3 Properties of NPV |
5 Reducing NPV’s Calculation Complexity |
6 Optimal Fault-Tolerant Routing Scheme (OFTRS) |
6.1 Algorithm for generating NPV |
6.2 Optimal fault-tolerant routing scheme based on NPV |
7 Evaluation |
8 Conclusions |
(10)具有扩展的局部连通性的超立方体网络中的容错路由(论文提纲范文)
中文摘要 |
ABSTRACT |
第一章 绪论 |
1.1 基本概念及性质 |
1.2 本课题的意义 |
1.3 超立方体网络中容错路由的当前现状 |
1.4 本课题的创新点 |
1.5 论文的结构 |
第二章 超立方体网络中基于扩展子立方体连通性的容错模型 |
2.1 具有扩展局部k—维子立方体是连通的超立方体网络中的容错模型 |
2.2 具有扩展局部子立方体是连通的超立方体网络中的容错模型 |
2.3 结论 |
第三章 超立方体网络中基于扩展的局部连通性的单播路由算法 |
3.1 基于扩展局部k—维子立方体连通的n—维超立方体网络中的单播路由算法 |
3.2 基于扩展局部子立方体连通的n—维超立方体网络的单播路由算法 |
3.3 结论 |
第四章 基于扩展局部k—维子立方体连通的超立方体网络中广播容错路由 |
4.1 基于扩展局部k—维子立方体连通的超立方体网络中广播容错路由算法 |
4.2 基于扩展局部k—维子立方体连通的超立方体网络中广播容错路由算法分析 |
4.3 结论 |
第五章 基于扩展局部k—维子立方体连通的超立方体网络中的多播容错路由 |
5.1 基于扩展局部k—维子立方体连通的超立方体网络中的多播容错路由算法 |
5.2 结论 |
第六章 实验、结论与展望 |
6.1 实验 |
6.2 结论 |
6.3 展望 |
参考文献 |
发表论文和参加科研情况说明 |
致谢 |
四、超立方体多处理机系统中基于扩展最优通路矩阵的容错路由(论文参考文献)
- [1]超立方体网络上与距离相关的容错性研究[D]. 马良. 苏州大学, 2016(02)
- [2]超立方体网络中多播路由优化策略研究[D]. 王洪伟. 哈尔滨工业大学, 2013(01)
- [3]K-Ary N-Cubes网络中离性能无死销多播路算法研究[D]. 章毅. 中南大学, 2012(03)
- [4]Torus网络中基于标志位的容错路由[J]. 李银,梁家荣,伍华健. 计算机工程, 2009(11)
- [5]超立方体网络容错模型及其路由算法研究[D]. 张玫. 山东师范大学, 2009(10)
- [6]超立方体中基于安全矩阵的容错路由[J]. 王福龙,苑召国,梁丽萍. 科学技术与工程, 2008(08)
- [7]超立方体中基于极大安全链路矩阵的容错路由[J]. 苑召国,郭大昌. 广东工业大学学报, 2008(01)
- [8]具有大量错误结点的超立方体网络基于矩阵容错路由算法的设计与讨论[D]. 苑召国. 广东工业大学, 2008(09)
- [9]基于NPV广义超立方体最佳容错路由算法(英文)[J]. 田绍槐,陆应平,张大方. 软件学报, 2007(07)
- [10]具有扩展的局部连通性的超立方体网络中的容错路由[D]. 张涌逸. 天津大学, 2007(04)
标签:立方体论文; 路由算法论文; 距离向量路由算法论文; 矩阵管理论文; 策略路由论文;