ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2014, Vol. 51 ›› Issue (8): 1854-1862.doi: 10.7544/issn1000-1239.2014.20121097

• 网络技术 • 上一篇    下一篇

Torus网络中移动气泡流控及其自适应路由实现

王永庆,谢伦国,付清朝   

  1. (国防科学技术大学计算机学院 长沙 410073) (wangyongqing73@gmail.com)
  • 出版日期: 2014-08-15
  • 基金资助: 
    基金项目:国家“八六三”高技术研究发展计划基金项目(2012AA01A301,2013AA014301);国家“九七三”重点基础研究发展计划基金项目(2011CB309705)

Moveable Bubble Flow Control and Adaptive Routing Mechanism in Torus Networks

Wang Yongqing, Xie Lunguo, Fu Qingchao   

  1. (College of Computer, National University of Defense Technology, Changsha 410073)
  • Online: 2014-08-15

摘要: 在torus网络中气泡流控是一种有效、实用的死锁避免技术.关键气泡机制使用虚跨步技术,只需要使用一个报文缓冲区就可以避免torus网络中的环内死锁,但是可能存在阻塞.首先提出了伪报文协议,然后结合伪报文协议设计了移动气泡流控策略,克服了关键气泡不能移动时引起的阻塞.伪报文协议基于简单的请求-应答,移动气泡流控则使用传统的信用传输方法.采用该机制,路由器只需要最少两条虚通道,每条虚通道最少一个报文空间就可以实现无死锁完全自适应路由.通过对经典路由器进行适当修改,给出了实现移动气泡流控的方法.采用模拟器比较了各种气泡流控的性能,结果表明,移动气泡流控性能超出传统的气泡机制,而加入自适应机制后的性能明显高于其他非自适应方法,不仅降低了延迟,吞吐率也提高20%以上,最大幅度甚至达100%.

关键词: 流控, k-ary n-cube, 关键气泡机制, 死锁, 虚跨步

Abstract: Bubble flow control is an efficient and buffer occupancy-based technique to avoid deadlock in torus networks. Critical bubble scheme can avoid intra-dimension deadlock with just one packet buffer by marking and tracking as “critical” a certain number of free packet-sized buffers, but has a risk of blocking. A false packet protocol and the design of a non-blocking moveable bubble scheme are presented to solve the block induced by critical bubble. False packet protocol adopts simple request-acknowledge, and the whole scheme is implemented on typical credit flows, and no other special requirement is needed. Unlike the typical bubble scheme, which is locally aware, this scheme is also an efficient implementation of a globally-aware flow control mechanism. Combing an escape channel based on moveable bubble scheme and a fully adaptive channel brings a fully adaptive router with minimal two virtual channels, with one packet buffer per virtual channel. To show the advantage of this scheme, the performance of various bubble-based schemes is compared. Network simulation results show that the moveable bubble scheme outperforms traditional bubble scheme, whereas adaptive scheme performs apparently better than the other non-adaptive methods. It avoids blocking, leads to much lower average packet latency, and displays a throughput improvement of more than 20%, maximally up to 100%.

Key words: flow control, k-ary n-cube, critical bubble scheme, deadlock, virtual cut-through

中图分类号: