交换超立方网的无死锁虫洞路由算法  

Deadlock-free wormhole routing algorithm of exchanged hypercube

作　　者：梁锦叶[1] 梁家荣[2] 苏树海[1] 

机构地区：[1]桂林理工大学,广西桂林541004 [2]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机应用研究》2014年第6期1764-1767,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61363002);国家教育部"新世纪优秀人才支持计划"专项基金资助项目(NCET-06-0756)

摘　　要：针对交换超立方网络通信中所出现的死锁及延迟问题,提出了一种基于虫洞路由的无死锁算法。引入交换超立方网的s-导出子网和t-导出子网的的概念,证明了s-导出子网和t-导出子网分别同构于s维超立方体网络和t维超立方体网络。通过把交换超立方网分解成若干个s-导出子网和t-导出子网,利用虚通道技术和虫洞路由策略设计了交换超立方网络的最短路径路由算法。理论分析证明,所提出的最短路径路由算法是无死锁的,且有效地减少了交换超立方网络通信的延迟。This paper proposed a deadlock-free routing algorithm based on wormhole for the problems of deadlock and time-delay on the communication of the exchanged hypercube.Firstly,it defined the concept of s-exporting subnet and the concept texporting subnet for the exchanged hypercube,proved that the s-exporting subnet and the t-exporting subnet for the exchanged hypercube are isomorphic to the s dimensions hypercube and the t dimensions hypercube,respectively.Then,decomposing the exchanged hypercube into the s-exporting subnets and the t-exporting subnets and employing virtual channel technique and wormhole routing strategy,presented a shortest path routing algorithm for the exchanged hypercube,which theoretically proved to be deadlock-free and to reduce effectively the delay in the communication of the exchanged hypercube.

关 键 词：交换超立方网 无死锁路由 虚拟通道 导出子网 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]