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

A Deadlock-free Routing Algorithm for Locally Twisted Cubes

作　　者：唐荣旺[1] 杨小帆[1] 朱策[1] 苏伟[1] 陈文斌[1] 

机构地区：[1]重庆大学计算机学院,重庆400030

出　　处：《重庆大学学报（自然科学版）》2006年第4期95-100,共6页Journal of Chongqing University

基　　金：重庆市自然科学基金资助项目(CSTC2005BB2191)

摘　　要：局部扭曲立方体是一种新提出来用于并行计算的互连网络.经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁.针对原有算法的特点,提出了一种新的无死锁路由算法并给出了无死锁证明.利用将物理通道分成2条虚拟通道进而形成2个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生.同时,利用一个局部扭曲立方体可由2个低维子立方体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性.The n-dimensional locally twisted cube （LTQn） is a newly introduced intereonneetion 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 LTQn consists of one n - 1-dimensional hypercube （ Qn-1 ） and one n - 1-dimensional 2-twisted cube （Qn-1, 2 ）, the authors 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 or in the Qn-1,21.

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

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