论文部分内容阅读
Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.首先证明n(n≥3)维交叉立方体网络不存在无死锁的最短路径路由算法,然后利用虚通道技术将一条物理通道分成三条逻辑通道,并在此基础上提出一种基于虫洞路由的最短路径路由算法,其时间复杂度为O(n).理论证明了算法是无死锁的.
Crossed cubes proposed by Efe are a variant of the hypercube Some of the properties of crossed cubes are better than hypercubes, for example, their diameters are almost half the size of hypercubes.Firstly, we prove that n (n≥3) dimension Crossover cube network does not exist without deadlock shortest path routing algorithm, and then use the virtual channel technology will be a physical channel is divided into three logical channels, and based on this proposed a wormhole routing based routing algorithm, the shortest path routing time complexity Is O (n). The theory proves that the algorithm is deadlock-free.