期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于2D-Mesh的容错路由算法 被引量：3

Fault-tolerant Routing Algorithm in 2D-Mesh
在线阅读 下载PDF
导出
摘要 提出一种基于2D-Mesh只使用2条虚通道的容错路由算法,少于需要4条虚通道的Boppana算法,以及需要3条虚通道的Duan算法。算法基于块故障模型,故障块可以是f-ring,也可以是f-chain。无故障时算法用最短路径路由消息,当消息被故障块阻塞时使用绕道策略进行路由。在不重叠和重叠故障区情况下分别给出算法无死锁性的证明过程。 A fault-tolerant routing algorithm for 2D-Mesh that uses only two virtual channels was presented. Previously,13oppana needs 4 virtual channels,and Duan needs 3 virtual channels. The algorithm is based on the block fault model The fault region can be f-ring and f-chain at the same time. Shortest paths are used for routing if there are no faults, while detour paths are used for blocked messages. We have proved that our algorithm is deadlock-free under the non-overlapping and overlapping situation.
作者 胥大成 樊建席 张书奎
机构地区 苏州大学计算机科学与技术学院
出处 《计算机科学》 CSCD 北大核心 2012年第3期113-117,134,共6页 Computer Science
基金 国家自然科学基金项目(60873047 61070169) 江苏省自然科学基金项目(BK2008154)资助
关键词 MESH 容错 路由 虚通道 片上网络 Mesh,Fault-tolerant,Routing,Virtual channel,NoC
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献16

  • 1Hemani A,Jantseh A,Kumar S,et al. Network on a chip:an architecture for billion transistor era[C]//NORCHIP 2000. Nov. 2000.
  • 2Dally W J, Seitz C L. The Torus Routing Chip [J]. Journal of Distributed Computing, 1986,1 (3) : 1-19.
  • 3Sarbazi-Azad H, Khonsari A, Ould-Khaoua M. Analysis of k-ary n-cubes with dimension-ordered routing[J].Future Generation Computer Systems, 2003,19 : 493-502.
  • 4Yang Y L, Funahashi A, Jouraku Am et al. Recursive Diagonal Toms: an interconnection network for massively parallel computers[J]. IEEE Transactions on Parallel and Distributed Systems, 2001,12(7) :701-714.
  • 5Karim F, Nguyen A, Dey S. An Interconnect Architecture for Networking Systems on Chips[J]. IEEE Micro, 2002,22 (5) : 36- 45.
  • 6Shih J-D. Fault tolerant wormhole routing in torus networks with overlapped block faults [J ]. IEE Proc. Comput. Digit. Teeh. ,2003,150(1).
  • 7Dally W J, Seitz C. Deadlock-free message routing in multiprocessor interconnection networks [J]. IEEE Transactions on Computers, 1987, C-36 :547-553.
  • 8Glass C J, Ni L M. The turn model for adaptive routing[C]// Proceedings of the 19^th International Symposium on Computer Architecture. May 1992 : 278-287.
  • 9Chiu G-M. The odd-even turn model for adaptive routing[J]. IEEE Trans. on Parallel and Distributed Systems, 2000,11:729-738.
  • 10Wu J. A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd-even turn model[J]. IEEE Transactions on Computers, 2003,52 : 1154-1169.

同被引文献22

  • 1Chou W,Bragg A W,Nilsson A A.The Need for Adaptive Routing in the Chaotic and Unbalanced Environment[J].IEEE Transactions on Communications,1981,29(4):481-490.
  • 2Lillevik S L.The Touchstone 30 Gigaflop Delta Prototype[C]// Proceedings of the 6th Distributed Memory Computing Conference.[S.l.]:IEEE Press,1991.
  • 3Shamaei A,Sarbazi-Azad H.An Adaptive and Fault-tolerant Routing Algorithm for Meshes[C]//Proceedings of International Conference on Computational Science and Its Applications.Berlin,Germany:[s.n.],2008.
  • 4Chalasani S,Boppana R V.Fault-tolerant Wormhole Routing Algorithms for Mesh Networks[J].IEEE Transactions on Computers,1995,44(7):848-864.
  • 5Su Chien-Chun,Shin G K.Adaptive Fault-tolerant Deadlock-free Routing in Meshes and Hypercubes[J].IEEE Transactions on Computers,1996,45(6):666-683.
  • 6Chien A W,Kim J H.Planar-adaptive Routing:Low-cost Adaptive Networks for Multiprocessors[J].Journal of the ACM,1995,42(1):92-123.
  • 7Xiang Dong,Zhang Yueli,Pan Yi.Practical Deadlock-free Fault-tolerant Routing in Meshes Based on the Planar Network Fault Model[J].IEEE Transactions on Computers,2008,58(5):620-633.
  • 8Wu Jie.A Fault-tolerant Adaptive and Minimal Routing Approach in 3-D Meshes[C]//Proceedings of the 7th International Conference on Parallel and Distributed Systems.Washington D.C.,USA:IEEE Press,2000.
  • 9Daneshtalab M,Ebrahimi M,Xu T C,et al.A Generic Adaptive Path-based Routing Method for MPSoCs[J].Journal of Systems Architecture,2011,57(1):109-120.
  • 10苑召国,郭大昌.超立方体中基于极大安全链路矩阵的容错路由[J].广东工业大学学报,2008,25(1):33-37. 被引量：1

引证文献3

二级引证文献2

计算机科学
2012年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部