一种基于局部扭曲立方体的无死锁路由算法

局部扭曲立方体是一种新提出来用于并行计算的互连网络.经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁.针对原有算法的特点,提出了一种新的无死锁路由算法并给出了无死锁证明.利用将物理通道分成2条虚拟通道进而形成2个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生.同时,利用一个局部扭曲立方体可由2个低维子立方体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性.

A Deadlock-free Routing Algorithm for Locally Twisted Cubes

The n-dimensional locally twisted cube(LTQ_(n)) is a newly introduced interconnection network for parallel computing.First, the authors illustrate that there exists deadlock in the minimal routing algorithm.Second,by employing the common virtual network dividing technique,a new routing algorithm is presented,which is proved to be deadlock-free.By exploring the property that one LTQ_(n) consists of one n-1-dimensional hypercube(Q_(n-1)) and one n-1-dimensional 2-twisted cube(Q_(n1,2)),the authors apply the existing adaptive routing strategies for Q_(n-1) and Q_(n-1,2) to induce an adaptive routing scheme for LTQ_(n).So the algorithm can route adaptively in the Q_(n-1)0 or in the Q_(n-1,2)1.