E-2D Torus网络结构中的无死锁路由算法  

Deadlock Free Routing Algorithms in E-2D Torus

作　　者：顾华玺[1] 邱智亮[1] 涂小行[1] 刘亚社[1] 

机构地区：[1]西安电子科技大学综合业务网国家重点实验室,华为技术有限公司,陕西西安710071,广东深圳5181297

出　　处：《小型微型计算机系统》2005年第7期1140-1144,共5页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2002AA103062)和(2003AA103520)资助

摘　　要：研究了太比特路由器核心交换网络拓扑的一种新结构-E-2Dtorus网络.该网络具有简单,对称,可扩展等优势.提出了适用于该网络结构的两种路由算法NPN(NoPositivetoNegative)和IDO(ImprovedDimensionOrder).部分自适应的NPN和确定性的IDO都是无死锁,无活锁且最短的路由算法.同时给出了无死锁无活锁的证明.最后,在8×8的E-2Dtorus网络上对路由算法进行仿真,结果表明E-2Dtorus是一种有潜力的网络拓扑结构,两种路由算法具有良好的性能.Research is carried on a novel switching fabric E-2D torus network, which is the core of the terabit router. E-2D torus has many advantages such as simple rectangular structure, scalability and so on. Attention is focused on designing the routing algorithms NPN(No Positive to Negative)and IDO(Improved Dimension Order). Both partially adaptive NPN and deterministic IDO are minimal, deadlock and livelock free. Proof of deadlock freedom and livelock freedom is presented. Finally, the simulation is carried out on (8,8) E-2D torus network to evaluate the performance. The results show that E-2D torus network is potentially an attractive interconnection network topology and NPN and IDO are of good performance.

关 键 词：无死锁 无活锁 互连网络 虚信道 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]