交换超立方网的无死锁虫洞路由算法-论文.pdf

《交换超立方网的无死锁虫洞路由算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第6期计算机应用研究Vo1．31No．62014年6月ApplicationResearchofComputersJun．2014交换超立方网的无死锁虫洞路由算法术梁锦叶，梁家荣，苏树海(1．桂林~2．z-大学，广西桂林，541004；2．广西大学计算机与电子信息学院，南宁530004)摘要：针对交换超立方网络通信中所出现的死锁及延迟问题，提出了一种基于虫洞路由的无死锁算法。引入交换超立方网的s一导出子网和￡一导出子网的的概念，证明了s一导出子网和一导出子网分别同构于s维超立方体网络和t维超立方体网络

2、。通过把交换超立方网分解成若干个s一导出子网和一导出子网，利用虚通道技术和虫洞路由策略设计了交换超立方网络的最短路径路由算法。理论分析证明，所提出的最短路径路由算法是无死锁的，且有效地减少了交换超立方网络通信的延迟。关键词：交换超立方网；无死锁路由；虚拟通道；导出子网中图分类号：TP393；TP301．6文献标志码：A文章编号：1001—3695(2014)06—1764—04doi：10．3969／j．issn．1001—3695．2014．06．038Deadlock—fleewormholeroutin

3、galgorithmofexchangedhypercubeLIANGJin—ye．LIANGJia—rong．SUShu—hai。(1．GuilinUniversityofTechnology，GuilinGuangxi541004，China；2．SchoolofComputer&ElectronicsInformation，GuangxiUniversity，Nanning530004，China)Abstract：Thispaperproposedadeadlock—freeroutingalgori

4、thmbasedonwormholefortheproblemsofdeadlockandtime—de—layonthecommunicationoftheexchangedhypercube．Firstly．itdefinedtheconceptofs—exportingsubnetandtheconceptt—exportingsubnetfortheexchangedhypercube，provedthatthes—exportingsubnetandthet-exportingsubnetforth

5、eexchangedhypercubeareisomorphictotheSdimensionshypercubeandthetdimensionshypercube，respectively．Then，decomposingtheexchangedhypercubeintothes—exportingsubnetsandthet-exportingsubnetsandemployingvirtualchanneltechniqueandwormholeroutingstrategy，presentedash

6、ortestpathroutingalgorithmfortheexchangedhypercube，whichtheoreticallyprovedtobedeadlock—freeandtoreduceeffectivelythedelayinthecommunicationoftheexchangedhypercube．Keywords：exchangedhypercube；deadlock—freerouting；virtualchannel；exposingsubnet前进。信息延迟和死锁问题是互联

7、网通信中重要的研究问题，0引言目前关于这方面的研究已取得了一些成果。例如Dally等人⋯通过引入虚拟通道的概念，把网络的物理通道分离成虚在并行计算机互联网系统中，处理器之问的通信快速和顺拟通道群来避免死锁，进而研究k-ary立方网、立方连通环网、畅是两个非常值得关注的问题。一方面，由于通信资源的有限洗牌交换网的无死锁路由算法；Daniel利用Dally等人提出性，通信延迟常常是不可避免的，因此减少通信的延迟是提高的虚拟通道技术给出了k-ary立方网的自适应和容错虫洞路并行计算机系统性能的重要手法。在并行计算机

8、系统通信模由策略；Borhani等人通过改进虫洞路由算法进一步改进了式中，尽量减少或不占用本地处理器的存储器来缓冲消息是一Daniel的结果，并给出k-ary2cubes的自适应和容错虫洞路由个不错的选择。为此，人们提出了一个所谓的虫洞路由机制。策略；Xiang把虚拟通道技术改进为通道重叠技术，给出了在虫洞路由模式下，一条消息被分割成许多的小片(flit)，消息Mesh网络的无死锁自适应路由算法；唐