一种新型的虫孔气泡流控实现策略  

One Novel Scheme for the Worm-Bubble Flow Control

作　　者：肖灿文[1] 张民选[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机学报》2016年第9期1858-1867,共10页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2012AA01A301;2013AA01A208)资助~~

摘　　要：气泡流控是一种实现环内无死锁路由的高效方法.该方法在超级计算机Bluegene/L中得到了成功应用.然而气泡流控只适用于虚跨步(VCT)切换网络.目前,研究人员提出了一些方法把气泡流控策略应用到虫孔切换的片上网络中.然而这些虫孔气泡流控策略需要复杂的控制信息.文中提出了一种新型的设计方法实现高效、简洁的虫孔气泡流控.首先采用支持非原子缓冲分配的多请求缓冲结构(MRIBO)代替传统的FIFO缓冲结构存储报文.MRIBO支持Flit在不同报文间乱序存储,缓冲区中的每一个Flit能够独立路由.在MRIBO存储方式下,作者设计了一种类似VCT网络的气泡流控,适用于虫孔网络的新型气泡流控策略.证明了在MRIBO方式下,新型流控策略可以保证单向环内的Flit总是可以流动,不会出现死锁,在单向环内实现了无死锁路由.基于斯坦福大学开发的BookSim模拟平台,作者测试了新型虫孔气泡流控策略的性能.通过修改源代码,在BookSim中实现了基于新型虫孔气泡的维序路由算法(WBFC)和完全适应性路由算法(Adapt-BF).作者分别比较了这两种算法和传统的基于子午线(Dateline)的维序路由算法(DOR)以及完全适应性路由算法(Adapt-DL)在不同维度的Torus网络中的报文平均延迟.模拟结果显示:这种新型虫孔气泡流控策略的性能大大优于传统的虫孔切换.其中,8-ary 2-cube Torus网络性能测试中,在uniform通信模式下,Adapt-BF算法的报文延迟相对Adapt-DL算法有近18%的减少.文章通过新型的缓冲组织结构打破了虫孔交换中报文传输的原子性,保证了Flit独立路由,所以就可以在虫孔网络中像VCT网络中处理报文一样处理Flit.在这种情况下,VCT网络中基于局部信息的Bubble流控技术可以几乎不加修改地应用到虫孔网络中.因此,这种方法简化了虫孔气泡流控的实现.The bubble flow control is an efficient way to achieve deadlock freedom within single dimension network rings. This method has been applied successfully in the supercomputer Bluegene/L. However, it is only suitable for virtual cut-through （VCT） networks. Currently, researchers propose some methods to realize the worm-bubble flow control in networks-on-chip. However, the complicated control logic hampers largely the application of the current worm- bubble flow control strategies. In this paper, one novel design is proposed to realize the efficient and concise worm-bubble flow control. At first, the multi-request input buffer organization （MRIBO） supporting non-atomic buffer allocation is adapted instead of the traditional FIFO buffer organization. Using MRIBO, it is allowed that the flits can be stored in out-order situation between the different packets and each flit can route independently. Based on MRIBO, we design one novel worm-bubble flow control strategy which is suitable for wormhole networks and similar to bubble flow control in VCT networks. We prove that the novel worm-bubble flow control can ensure that those flits can always flow and there is not deadlock in the unidirectional ring when the MRIBO is used. The performance of the novel worm-bubble flow control is analyzed on the BookSim simulator developed at the Standford University, thanks to its modular design, and the availability of a large variety of the classic network implementations. By modifying the source code, new routing algorithms were implemented in the BookSim simulator with little effort. We realize the dimension order routing algorithm （WBFC） and fully adaptive routing algorithm （Adapt-BF） based on the novel worm-bubble flow control. We then compare the average packet latencies of the two algorithms to their counterparts： the traditional dimension order routing algorithm （DOR） and the fully adaptive routing algorithm（Adapt-DL） based on dateline. Torus with different dimensions was used in simulation.

关 键 词：虫孔气泡流控 多请求缓冲结构 非原子缓冲分配 虫孔切换 死锁避免 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]