交换超立方网的自适应性无死锁路由算法

摘要

交换超立方网是一种新提出来的互连网络.首先,利用图论的方法研究了交换超立方网的拓扑性质,引入了相似子网的概念,得出相似子网和超立方体同构的结论；然后,利用将物理通道分成两条虚拟通道的方法,给出了一种交换超立方网的自适应性路由算法,并从理论上证明了该算法的无死锁性.%The exchanged hypercube is a novel interconnection network. Firstly, the method of graph theory is employed to analyze the topological property of the exchanged hypercube, the concept of similar subnet is defined and the result that the hypercube and the similar subnet are isomorphic is obtained. Secondly, an adaptive routing algorithm is proposed by using the technique of dividing a physical channel into two virtual channels. Finally, the theoretical analysis shows that the algorithm is deadlock-free.