[基于流水式电路交换的混合容错路由算法] 电路交换

　　摘要:随着芯片集成度的提高和IP核的增多,片上网络(NOC)已成为片上系统[1](soc)芯片设计的重点。当节点和链路由于网络规模的增大从而导致故障率大大增加,这样,运用容错技术提高系统的可靠性就成为NOC的设计重点.本文在对PCS的研究基础上,基于2D-mesh拓扑结构,提出了一种基于流水式电路交换机制(PCS)改进型的容错路由算法,并在OPNET仿真平台对其进行了仿真和性能分析。
　　关键词:片上网络;容错;mesh;流水式电路交换
　　
　　Based on PCS hybrid fault-tolerant routing algorithm
　　
　　LI Wang-yuan
　　(School of ComputerXidian University,Xi’an 710071,China)
　　
　　Abstract:with the improvement of chip integration and the increase of the Intellectual Property(IP) core of the chip.Network on Chip(NOC) which base on the system on chip (SOC) has already become the importance of the chip design.whith the network size increasing the fault nodes and links is significantly increased,so making the use of fault-tolerant in order to enhance the reliability of the system becomes the focus on the design of NOC.In this paper,base on Pipelined circuit switching mechanism and the 2D-mesh topology,we propose a flaut-tolerant algorithm based on PCS mechanism which is impoved.and then do perfomance comparison with OPNET.
　　Key words: Network on chip(NOC);falut-tolerant;mesh; Pipelined circuit switching
　　
　　1引言
　　
　　随着半导体工艺技术的不断进步,在单一芯片中集成上亿晶体管已经成为现实,如何有效地利用数目众多的晶体管是芯片体系结构必须回答的新问题。因循单核的发展思路,芯片设计将面临互连延迟、存储带宽、功耗极限等性能提升的瓶颈问题。因此,有必要研究新型的芯片体系架构,以适应性能增长和功耗下降同时发生这样看似矛盾的需求。多核技术的提出是一条可行的解决方案。多核能够用多个低频率核单元产生超过高频率单核的处理效能,获得较佳的性价比,片上网络[2](NOC)就是将多核采用一定的拓扑连接,通过一定的组织结构使得多核发挥最大的效能。
　　随着多核的个数的增多,系统整体出现问题的几率大大增加,多核技术面临的一个问题是如何在大规模应用中避免错误的发生,这就引入了多网络容错技术的研究。系统的可靠性变得越来越重要。NOC错误主要有两种:一是有电迁移,制作工艺和测试挑战等引起的电路老化效应导致的永久性错误;二是由串扰,噪声和瞬间错误引起的软故障。软故障不影响系统正常运行,但对系统的性能有较大的影响,硬故障具有突发性,在实际中往往采用一定的容错路由算法或添加冗余电路来实现对硬故障区域的绕道来避免。
　　目前针对片上网络的容错路由算法有基于链路状态[3]的路由算法、洪泛路由算法[4],和基于两者的混合容错路由[5]算法。
　　以上算法中,洪泛算法由于不断向网络中广播大量信息,会导致“广播风暴”,进而导致网络阻塞和延迟的增加。基于链路的容错算法会导致链路的利用率低下,链路的通信成本过高,而且还需要额外的缓存来存储链路信息,使得芯片的面积开销过大。混合型算法结合两者的优点,但它的复杂度较高且能耗较大。
　　本文以流水式电路交换机制[6](PCS)为基础,结合虫孔交换的特点,提出了一种混合型容错路由算法――基于流水式电路交换的混合容错路由算法(HR_PCS)。
　　
　　2流水式电路交换介绍
　　
　　流水式电路交换(PCS)结合了电路交换和虫孔交换的特点。PCS在开始传输数据前,头微片先建立一条可靠路径,然后发回一个应答微片,源发送端在接收到应答微片后,数据片可以流水地通过网络到达目的节点,它的优点是头微片不会阻塞在路径中,遇到阻塞时,它会回溯前一个路由器且释放先前保留的通道,然后在当前节点寻找下一个可用路径。同时由于使用的是虚通道,所以不像电路交换占用整个带宽,在建立路径时不会导致其他消息过分阻塞。
　　
　　 从图1中可以看出,头片在建立和返回应答微片时所占用的时间相当大。可以采用一定的策略来适当减小时间开销。
　　
　　3基于流水式电路交换(pcs)的
　　混合容错路由算法(HR_PCS)
　　
　　但是由于头微片在建立路径过程和返回应答过程中所消耗的时间过长,导致PCS交换中,网络延迟过大,为有效减小总延迟,可以对pcs进行改进,使得数据微片和头微片保持一定的距离K,从而减小应答微片传输的时间,进一步减小了网络的总延时。为了达到一定的容错性,并兼顾网络性能,在头片中可以设置一个绕道计数器(count),只允许头微片在遇到故障时进行一定数目的绕道,无通路时可以适当回溯,再继续寻找可用通道,这样可以使算法容忍更多的故障。
　　在路由过程中,在未遇到故障点时采用维序路由,可以节约时间开销,当遇到故障点时采用上述改进型的pcs交换,可以取得较好的吞吐性能。
　　
　　 3.1算法描述
　　 3.1.1 算法过程描述
　　设置ttl值,ttl在路由过程中递减,当递减为0时,说明路由失败,清除网络中的消息。
　　1) 数据包以维序方式路由,消息头内K值字段设为0,表示数据微片紧随头微片。
　　2) 在无故障区域内按照虫孔交换,以维序方式路由。当遇到故障区域时,或拥堵无法继续前进时,消息头切换到pcs模式,初始化K值,同时头片进行绕道寻找其他可接近路径,绕道期间,数据片不能前进。当头片在绕道限制下无法找到可接近通道时,头片回溯,发送负反馈信号,继续寻找可行通道。当有可行通路时,发送正反馈片,当通道计数器的值与K相等时,数据片发送,同时每个接收到反馈片的节点更新自己的路由表。
　　3) 如果下次再有一个消息的目的节点刚好是这些路径上的一个节点,就不需要再次完全重新搜索路由路径,只需要根据路由信息直接转发消息。
　　 3.1.2 HR_PCS算法是无死锁的
　　 证明:
　　首先在无故障域,以维序方式路由,维序本身是一种确定的无死锁的路由算法,其次当进入故障域时,头片切换为pcs状态,在头片探路过程中,使用的是虚通道且它在无法路由时可以进行有效的回溯,所以不会阻塞通道和缓冲器资源,因而不会因此产生环路,所以该过程不会产生死锁,故该算法是无死锁的路由容错算法。
　　如图2所示,S为源节点,D为目标节点。开始时,从S发出的数据以虫孔交换方式进行路由,当遇到故障点时,路由头进入搜索模式,K值初始化为2,路由头接近路由到A,此时数据片在C点的前一个节点。在A点,消息头无法继续向目的节点路由,消息头进行绕道模式,到达B,B点判断不可达后,消息头进行回溯,当回溯到C点时,消息向下进行路由,在一次绕道后,消息头可以顺利到达目的节点D,此时数据微片在距目的节点一段距离后,当收到反馈的微片后,数据片流水的传输到目的节点。
　　
　　4仿真性能分析
　　
　　以mesh拓扑结构为平台,每条通道设置三条虚信道,在均匀流量模式下对算法进行仿真,并同duato算法[7]和xy维序路由[8]算法进行对比,xy路由算法不具有容错性,对比只是为了说明不具容错性的算法和HR_PCS、duato算法在处理错误节点和拥塞时的性能差异。
　　故障模型采用节点故障和链路故障,节点失效时,与节点相连的链路和相应端口全部标记为失效,当链路失效时,将链路连接的端口标记为失效。
　　
　　从图3吞吐曲线可以看出,随着注入率的增加,XD达到处理的极限时,吞吐会明显下降,而duato和HR_PCS算法能绕过热点和错误节点区域,顺利到达目的节点,吞吐表现出较好的性能。HR_PCS在处理高负载时,吞吐性能优于duato。
　　从图4延迟曲线可以得出,在负载低于30%时,HR_PCS、duato和XD算法的时延性能差别不大,当随着负载的增加和遇到错误节点和链路、网络出现拥塞,XD算法延迟增加较快,duato算法为自适应性算法,能够绕过部分故障和热点区域。HR_PCS算法在中等负载时与duato算法性能相当,在高负载下,由于网络拥塞和故障节点的影响,在PCS阶段处理时间较长从而导致延迟加大,性能较duato算法稍差。
　　
　　5总结
　　
　　本文在基于改进PCS交换机制的基础上,结合虫孔交换机制,提出了一种混合型的认错路由算法――HR_PCS,并在OPNET平台下进行仿真,通过与xy、duato路由算法进行性能比较,得出HR_PCS算法在较高网络负载条件下,能够较好地绕过热点和错误节点区域,具有较高的吞吐性和良好的时延性。
　　
　　参考文献
　　[1]郭斌,沈艳,林永宏等.SOC技术原理与应用[M].北京:清华大学出版社,2006:15-17.
　　[2]Axel, T. Hannu. Networks on chip[M]. Kluwer Academic Publishers, 2003: 3-18.
　　[3]C. Hendrick. Routing Information Protocol[S]. RFC 1058, IETF Network working Group, June 1988. Category: Historical.
　　[4]M. Pirretti, G. M. Link, R. R. Brooks, N. Vijaykrishnan, M. Kandemir, and I. M. J, Fault tolerant algorithms for network-on-chip interconnect[C]. In Proc. of the ISVLSI, 2004.
　　[5]S. D. Mediratta, J. Draper. Characterization of a Fault-tolerant NOC Router. Circuits and Systems, 2007. ISCAS 2007[J]. IEEE International Symposium on. PP.381-384, 27-30 May 2007.
　　[6]J .Duato,Sudhakar Yalamanchili,LionelNi.Intercon- nection Networks An Engineering Approach.Elsevier Science,2004.
　　[7]J. Duato. A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks[J]. IEEE Trans on Parallel and Distributed Systems vol.4, PP.1320-1331, 1993.
　　[8]J. Duato, S. Yaiamanchili, N. Lionel. Interconnection networks: An engineering approach[M]. USA: Morgan Kaufmann Publishers Inc, 2002.