电子学报 ›› 2013, Vol. 41 ›› Issue (11): 2113-2119.DOI: 10.3969/j.issn.0372-2112.2013.11.001

• 学术论文 •    下一篇

Torus网络中基于中心距离的完全自适应路由算法

虞志刚1, 向东2, 王新玉1   

  1. 1. 清华大学计算机科学与技术系, 北京 100084;
    2. 清华大学软件学院, 北京 100084
  • 收稿日期:2013-01-10 修回日期:2013-02-28 出版日期:2013-11-25 发布日期:2013-11-25
  • 作者简介:虞志刚 男,1989年生于安徽省宿松县.现为清华大学计算机系博士生.研究方向为并行与分布式计算、片上网络路由. E-mail:yuzg@live.com 向 东 男,1966年生于重庆市.现为清华大学软件学院教授,博士生导师,杰出青年.研究方向为集成电路测试、分布式计算、容错计算. E-mail:dxiang@tsinghua.edu.cn
  • 基金资助:
    国家自然科学基金(No.61170063,No.60910003)

Fully Adaptive Routing in Torus Networks Based on Center Distance

YU Zhi-gang1, XIANG Dong2, WANG Xin-yu1   

  1. 1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
    2. School of Software, Tsinghua University, Beijing 100084, China
  • Received:2013-01-10 Revised:2013-02-28 Online:2013-11-25 Published:2013-11-25

摘要: Torus网络凭借其优越的结构特性,引起了工业界和学术界的广泛关注.高效、无死锁的路由算法设计是互连网络研究的一个重要方面.针对Torus网络实现自适应路由所需虚通道数目多的缺点,提出了自适应路由算法Gear,该算法基于中心距离的方法来限制虚通道的使用,在虚切通交换下仅需两条虚通道即可为Torus网络提供无死锁自适应路由.通过仿真对所提算法的有效性进行了验证,结果表明,在同等情况下算法Gear的性能较经典的维序路由和Duato协议具有非常明显的优势.

关键词: Torus网络, 路由算法, 虚通道, 自适应路由

Abstract: Torus networks win lots of industrial and academic attention by virtue of the superior architecture proprieties.The design of efficient deadlock-free routing algorithms is an important aspect of interconnection networks research.Against the problem that torus networks need numbers of virtual channels to support adaptive routing, we propose an adaptive routing algorithm:Gear,which needs only 2 virtual channels to support deadlock-free adaptive routing in Virtual Cut-Through switched Torus.Gear implements fully adaptive routing by constraining the use of some special virtual channels on the concept of Center Distance.We verify the efficiency of the algorithm with simulation. The results show that,in the same circumstances,the advantage of proposed Gear over classic Dimension-Order Routing and Duato's Protocol is very apparent.

Key words: Torus networks, routing algorithm, virtual channel, adaptive routing

中图分类号: