交叉立方体网络的无死锁虫洞路由算法  

Deadlock-free Wormhole Routing Algorithm for Crossed Cube Network

作　　者：喻昕[1,2] 吴敏[2] 王国军[2] 

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004 [2]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《小型微型计算机系统》2010年第9期1721-1725,共5页Journal of Chinese Computer Systems

基　　金：国家杰出青年科学基金项目(60425310)资助;国家自然科学基金项目(60763013)资助;广西人才小高地创新团队计划项目资助

摘　　要：Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.首先证明n(n≥3)维交叉立方体网络不存在无死锁的最短路径路由算法,然后利用虚通道技术将一条物理通道分成三条逻辑通道,并在此基础上提出一种基于虫洞路由的最短路径路由算法,其时间复杂度为O(n).理论证明了算法是无死锁的.The crossed cube proposed by Efe is a variation of hypercube,but some properties of the former are superior to those of the latter.For example,the diameter of the crossed cube is approximately half that of the hypercube.First,the authors prove that the n（n≥3）-dimensional crossed cube network has not deadlock-free shortest path routing algorithm.second,by employing virtual channel technique to divide a physical channel into three logic channels,a shortest path routing algorithm based on wormhole routing is presented,which has a time complexity of O（n）.Theoretical analysis show that the algorithm is deadlock-free.

关 键 词：交叉立方体 超立方体 最短路径 无死锁路由 虫洞路由 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]