基于局部扭曲立方体的多播路由算法  

A Multicast Routing Algorithm on Locally Twisted Cube

作　　者：林玮[1] 

机构地区：[1]武汉数字工程研究所,武汉430074

出　　处：《计算机与数字工程》2009年第7期30-34,63,共6页Computer & Digital Engineering

摘　　要：局部扭曲立方体是一种新提出来用于并行计算的互联网络。经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁。因此,在原有算法的基础上,提出了一种新的无死锁路由算法并给出了无死锁证明。利用将物理通道分成两条虚拟通道进而形成两个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生。同时,利用一个局部扭曲立方体可由两个低维子立文体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性。在此基础上提出了一种多播路由算法。The n-dimensional locally twisted cube （LTQ.） is a newly introduced interconnection network for parallel computing. First, we 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. consists of one n-1-dimensional hypercube （Qn-1） and one n- 1-dimensional 2- twisted cube （Qn-1,2 ）, we apply the existing adaptive routing strategies for Qn-1 and Qn-1,2 to induce an adaptive routing scheme for LTQn. So the algorithm can route adaptively in the Qn- 1 0 or in the Qn-1,2 1. And develop a multicast routing on above.

关 键 词：局部扭曲立方体 无死锁 虫孔路由 虚拟通道 虚拟网络 P-cube算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]