摘要
针对交换超立方网络通信中所出现的死锁及延迟问题,提出了一种基于虫洞路由的无死锁算法。引入交换超立方网的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.
出处
《计算机应用研究》
CSCD
北大核心
2014年第6期1764-1767,共4页
Application Research of Computers
基金
国家自然科学基金资助项目(61363002)
国家教育部"新世纪优秀人才支持计划"专项基金资助项目(NCET-06-0756)
关键词
交换超立方网
无死锁路由
虚拟通道
导出子网
exchanged hypercube
deadlock-free routing
virtual channel
exporting subnet