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

Deadlock-free wormhole routing algorithm of exchanged hypercube

针对交换超立方网络通信中所出现的死锁及延迟问题,提出了一种基于虫洞路由的无死锁算法。引入交换超立方网的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.