局部扭曲立方体容错路由策略.研究

《局部扭曲立方体容错路由策略.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆盔堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：脊砟签字日期：加]年f月刁日学位论文版权使用授权书本学位论文作者完全了解重废太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借

2、阅。本人授权重鏖太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密()，在——年解密后适用本授权书。本学位论文属于不保密(＼力。(请只在上述一个括号内打“4”)学位论文作者签名：r水币签字日期：绷年j月纠日导师签名：‰小椒签字日期：l,o-1年，月2,1Et重庆大学硕十学位论文1绪论1．1引言人们总是追求更高性能的计算能力，并行计算机则是实现高性能计算能力的有效技术途径。近年来，在国防、太空、汽车制造业和科学领域都出现了大量具有巨大挑战的应用问题，

3、它们要求计算机具有每秒万亿次级浮点运算(teraflops)，甚至更高级别的计算能力。高性能商用微处理器技术取得了迅猛的发展，为并行计算机的实现提供了前所未有的、坚实的物质基础，使高性能大规模计算机的实现成为可能。但是，多处理机系统的规模越来越大，系统中出现处理机故障或处理机间的边故障的可能性也随之增加，这就要求系统有一定的容错和检错能力，以保证系统的正确运行。因此系统的可靠性很大程度上依赖于它的容错能力，容错能力的好坏往往直接影响到系统的性能。这样就需要我们设计较好的容错路由策略，尽可能多地记录系统中存在的最优

4、通路的信息，使得当系统中存在故障的情况下实现更有效的容错路由，达到提高整个系统性能的目的。最理想的容错路由算法应当是，只要源、目的节点间存在通路就可以把消息沿最短通路传递到目的节点的算法。目前，互连网络为多计算机系统中处理器单元之间的通信提供了一种有效的机制，互连网络的拓扑结构决定着多处理机系统中处理器单元之间协同工作的能力。因此，选择或设计一种高效、可靠的多处理器互连拓扑结构对组建多计算机系统是非常重要的。同时，基于多计算机系统互连网络拓扑结构容错路由算法的研究也已经成为一个很重要的课题。1．2互连网络拓扑结构

5、介绍互连网络按几何形状分为两大类：规则网和不规则网。规则网又分为静态网和动态网两种。所谓静态网是指网络拓扑结构中各节点间有专用的链路，这些链路是固定连接的不能重新组合。而动态网是指网络拓扑结构中，各节点间的链路可以通过设置网络的开关来重新组合。当前互连网络拓扑结构有很多种，常见的网络拓扑结构有：线性列阵形网(1inearmary)，环形F*Cring)、网格形网(mesh)、树形网(tree)、蜂窝网(honeycomb)、超立方体形(hypercube)、扭曲立方体(twistedcube)、Mobius立方体

6、(Mobiuscube)、交叉立方体(crossedcube)、总线形l网(bus)、全互连网、蝶形网(butterflynetwork)、洗牌交换(shuffle．exchange)、交叉开关网(eross．barswitchnetwork)、Benes网、STARAN网、数据交换网等等。在图1．1中列出了部分拓扑结构。重庆大学硕十学位论文1绪论(g)全互连网(e)二叉树(f)超立方体(h)总线型网(i)交叉开关网图1．1网络拓扑结构超立方体p】互连拓扑结构是一种在实践中得到广泛应用的互连网络模型之一。例如，I

7、ntelCM一2【4】，iPSC／I。iPSC／2c5l以及nCUBE[6】等机器采用的都是超立方体结构。这是因为基于超立方体的互连网络有很多优秀的性质，比如：对称性，可递归构建性，更重要的是基于超立方体的互连网络具有较强的容错性。然而，对于一个具有2“个结点，连通度是n的网络拓扑结构来说，节点总数对数级的网络直径并不是最优的，也就是说，在保证连通度和节点总数不变的前提下，可以设计出网络直径更小的互连拓扑结构，这就促使人们展开了对超立方米一众

8、

9、警硷重庆大学硕士学位论文1绪论体变体及其性质的研究，如：平衡超立方体

10、t7J(TheB加cedHypercube)、环立方体鹏](Cube—Connected．Cycle)、超级立方体一](Supercube)、扭曲立方体【1川(TwistedCube)、局部扭曲立方体【111(LocallyTwistedCube)、莫比乌斯立方体[12,131(MObiusCube)、交叉立方体114,15](CrossedCube)、超级交叉立方体【1