Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2018, Vol. 58 Issue (12): 1051-1058    DOI: 10.16511/j.cnki.qhdxxb.2018.22.043
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
蔡源1, 罗伟2, 向东1
1. 清华大学 软件学院, 北京 100084;
2. 国网湖南省电力公司 信息通信公司, 长沙 410004
Routing algorithm based on a column-partition turn model for a network-on-chip
CAI Yuan1, LUO Wei2, XIANG Dong1
1. Software Department, Tsinghua University, Beijing 100084, China;
2. Information and Communication Company, State Grid Hunan Electric Power Company, Changsha 410004, China
全文: PDF(3044 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 针对现有的判断片上网络路由算法是否含有死锁的方法都比较复杂,以及传统转弯模型存在不足的问题,提出了一种更简单更直观的判断路由算法是否包含死锁的算法,并证明了该算法的正确性,然后提出了一种列分转弯模型。列分转弯模型能实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径部分自适应路由,并且不需要额外的虚拟通道。该模型会在网络节点处限制某些转弯,从而避免死锁,类似于奇偶转弯模型。模拟实验结果表明:基于该模型的路由算法与基于奇偶转弯模型的路由算法相比,在不同的流量模式下平均延迟都有所降低,饱和点有所上升,从而提高了整个网络的性能。
E-mail Alert
关键词 转弯模型虚跨步交换二维mesh网络无死锁部分自适应路由    
Abstract:Existing methods cannot easily determine whether a routing algorithm for a network-on-chip contains a deadlock and the traditional turn model has serious limitations. This paper presents a simple, intuitive algorithm to determine whether the routing algorithm is deadlock-free. This paper gives a proof of the algorithm's correctness. Then, a column-partition turn model is given to implement deadlock-free minimal partially adaptive routing for a virtual cut-through (VCT)-switched 2-D mesh without extra virtual channels. This algorithm avoids deadlocks by restricting the locations for certain turns, which is similar to the odd-even turn method. Simulations show that this routing algorithm reduces the average latency and increases the saturation points compared to routing algorithms based on the odd-even turn model for various traffic patterns. Therefore, this column-partition turn model improves the performance of the whole network.
Key wordsturn model    virtual cut-through switching    2-D mesh    deadlock-free    partially adaptive routing
收稿日期: 2018-04-28      出版日期: 2018-12-13
通讯作者: 向东,教授,     E-mail:
蔡源, 罗伟, 向东. 基于列分转弯模型的片上网络路由算法[J]. 清华大学学报(自然科学版), 2018, 58(12): 1051-1058.
CAI Yuan, LUO Wei, XIANG Dong. Routing algorithm based on a column-partition turn model for a network-on-chip. Journal of Tsinghua University(Science and Technology), 2018, 58(12): 1051-1058.
链接本文:  或
  图1 算法isDeadlockFree
  图2 奇偶转弯模型无死锁的证明过程
  图3 算法route
  图4 列分转弯模型禁止的转弯
  图5 基于列分转弯模型的算法在5×5mesh 网络中路由示例
  图6 均匀和转置流量模式下算法性能比较
  图7 热点流量模式下算法性能比较
[1] XU Y, DU Y, ZHAO B, et al. A low-radix and low-diameter 3D interconnection network design[C]//Proceedings of the 15th International Symposium on High Performance Computer Architecture. Raleigh, USA, 2009:30-42.
[2] 李晨, 马胜, 王璐, 等. 三维片上网络体系结构研究综述[J]. 计算机学报, 2016, 39(9):1812-1828. LI C, MA S, WANG L, et al. A survey on architecture for three-dimensional networks-on-chip[J]. Chinese Journal of Computers, 2016, 39(9):1812-1828. (in Chinese)
[3] XIANG D. Deadlock-free adaptive routing in meshes with fault-tolerance ability based on channel overlapping[J]. IEEE Transactions on Dependable and Secure Computing, 2011, 8(1):74-88.
[4] KHAN H U R, SHI F, JI W X, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29):3363-3371.
[5] XIANG D, ZHANG Y L, PAN Y, et al. Deadlock-free adaptive routing in meshes based on cost-effective deadlock avoidance schemes[C]//Proceedings of International Conference on Parallel Processing. Xi'an, China, 2007:41-48.
[6] ALLEN F, ALMASI G, ANDREONI G, et al. Blue gene:A vision for protein science using a petaflop supercomputer[J]. IBM Systems Journal, 2011, 40(2):310-327.
[7] MUKHERJEE S S, BANNON R, LANG S, et al. The Alpha 21364 network architecture[J]. IEEE Micro, 2002, 22(1):26-35.
[8] DALLY W, TOWLES B. Principles and practices of interconnection networks[M]. San Francisco, USA:Morgan Kaufmann, 2003.
[9] DUATO J, YALAMANCHILI S, NI L. Interconnection networks:An engineering approach[M]. San Francisco, USA:Morgan Kaufmann, 2002.
[10] VERBEEK F, SCHMALTZ J. A decision procedure for deadlock-free routing in wormhole networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8):1935-1944.
[11] GLASS C J, NI L M. The turn model for adaptive routing[J]. Journal of the ACM, 1994, 41(5):874-902.
[12] CHIU G M. The odd-even turn model for adaptive routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7):729-738.
[13] DUATO J. A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(8):841-854.
No related articles found!
Full text



版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持