策略通道 片上网络的动态虚通道分配策略

　　摘要:针对片上网络(NoC)的传统的静态虚通道分配不能很好适应非平衡的业务负荷问题,本论文提出了NoC动态虚通道分配策略。在静态虚通道分配基础上,动态分配虚通道通过实时监测节点端口的包流量的方向,决定分配给该端口的虚通道数目。动态虚通道资源可以在所有端口间共享,并根据通信业务需求动态调度。在二维mesh NoC上的仿真表明,动态虚通道分配策略不仅节约了存储器资源,而且对NoC传输延时有一定的改善。
　　关键字:片上网络;虚通道;动态虚通道分配
　　
　　Dynamic virtual channel allocation for network-on-chip
　　
　　SHEN Hui, LING Xiang
　　(National Key Laboratory of Science and Technology on Communications of UESTC,Chengdu 611731,China)
　　
　　Abstract: Since the static virtual channel (VC) allocation can not well resolve the problem of imbalanced traffic load in network-on-chip (NoC), this paper proposes a dynamic virtual channel allocation algorithm for NoC architectures. Compared with the static VC allocation scheme, the dynamic VC allocation algorithm assigns the virtual channels by real-timely monitoring the packet flow directions of every node ports.Thus the VC resources can be shared among all input ports and assigned according to the traffic demand. Simulation results show that this proposed dynamic VC allocation scheme saves the memory resources significantly, and reduces NoC propagation delay to some extent.
　　Keywords: network-on-chip; virtual channel; dynamic virtual channel allocation
　　
　　1引言
　　
　　 随着深亚微米工艺水平的提高,特征尺寸逐渐减小,使得片上资源间的互连通信成为片上系统(SOC)设计中制约时延与功耗的关键因素。因此,片上网络(NoC)通信成为提高片上系统通信效率的解决方案。和传统的片上总线通信相比,片上网络设计具有几个优点:①由于可重用性设计,片上网络具有良好的可扩展性;②物理链路的链路长度和延时都可以得到更好的控制。
　　 片上网络中,缓存(buffer)会消耗大量的功耗,为了有效地节约缓存,NoC一般采用虫洞路由方式。此外,NoC的通信延时也是其设计中的一个重要指标。NoC中存在队头阻塞(HOL)现象,由于下一级路由器输入队列资源被某方向的数据流持续占用,虽然其它方向的通路空闲,当前路由器队列中的包头仍无法通过下一级路由器的空闲方向。图1a中,如果A-B-C通道阻塞,路由器B的P0端口将被占用,使得F-A-B-D通道也无法传输。当包头阻塞发生时,导致很大的传输延时,采用虚通道(VC)技术可以解决HOL问题。当某端口中一个VC中的数据发生阻塞时,其它VC的数据可以继续沿着其它链路方向传递。见图1b,如果A-B-C通道阻塞,节点F的数据包可以通过节点B的另一个VC通道传送到节点D。因此,整个系统的吞吐率将会得到提高,平均包延时会得到降低。
　　 在虫孔路由中,增加路由器输入端口上虚通道的数量会提高系统性能。但片上资源是有限的,过多地分配虚通道会导致资源浪费,且对于通信量比较轻的链路起到的作用很有限,只有高负载的链路可通过增加VC来获利。因此必须合理地分配虚通道以便用最小的资源消耗获得最大的性能提高,这就要求进行实时的动态VC分配。
　　 本文提出了一种动态虚通道的片上路由器结构,通过判断数据包的下一跳的方向来决定是否需要分配或回收动态虚通道,提高VC的利用率。
　　
　　2片上网络结构
　　
　　NoC mesh网络结构如图2所示。它由路由器(R)、链路、网络接口(NI)和本地子系统组成。路由器是网络的核心部件;本地子系统包括处理单元(PE)与私有存储器,处理单元通过局部总线访问私有存储器,通过NI连接NoC网络,经NoC网络访问共享存储器。PE间的数据传送路径经过PE-->NI-->路由器-->路由器-->NI-->PE。NoC通常采用全局异步局部同步(GALS)机制,整个传输路径被不同的时钟域所分隔。
　　虫洞路由方式中;包头进入路由器选择了前进方向之后,建立传递路径、占用资源,这个数据包的后续微片(flit)将会沿着包头所确定的路径向前传递,当整个数据包传递结束后,才释放资源。
　　具体的交换过程主要包括三种基本操作:路由计算(Route Computing,RC)、虚通道分配(Virtual- Channel Allocation)和交叉开关传输(Crossbar Traversal, CT) 。
　　
　　3静态VC分配
　　虚通道包含一组能缓存一个或多个flit的buffer和这些flit的状态信息。同一端口的几条虚通道共享同一条物理通道。每个路由器有P个输入端口和P个输出端口,每个输入端口支持V条虚通道。来自不同源的数据包按照时分复用的方式经过节点间链路分配到V个虚通道中。如果某一虚通道上的数据发生了阻塞,该端口上另一虚通道上的数据仍然可以通过该物理通道继续向前传输,从而提高了吞吐率,且减少了传输时延。
　　静态分配虚通道的步骤包括:
　　 1)计算路由。当某一数据包的第一个flit到达路由器时,路由计算单元根据包头的路由信息得知下一跳的节点编号,根据这个节点编号找出通往下一跳的输出端口。
　　 2)虚通道分配。每一个数据包都会检测它们所要访问的下一跳路由器输入端口的VC 资源的占用情况。当检测到下一跳路由器输入端口有可用的buffer空间,输入VC就会请求通过路由器的交换矩阵(crossbar)访问输出通道。每一个时钟周期,交换分配逻辑电路接收这些请求并产生对交换矩阵的控制信号。
　　 3)交换矩阵传输。Flit只有在获得准许之后才能通过交换矩阵到达特定的输出端口。
　　 在静态均衡分配VC的情况下,给每个节点、每个端口分配相同数目的虚通道,增加端口的虚通道的数目会使得平均传输包延时得到降低。但每个节点各个端口发送或接收的包流量是不一致的,若给每个端口分配相同数目的虚通道会造成严重的资源浪费。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　
　　4动态VC分配
　　
　　在静态VC分配基础上,如果某端口虚通道需求较大,可以进一步动态地分配VC给需要的端口。这不仅保证了VC分配的实时性,而且提高了缓存资源利用率。
　　动态VC分配的过程要比静态VC分配复杂一些。除了保留路由计算、虚通道分配和交叉开关传输过程,还要增加动态VC控制过程,执行动态VC的分配、建立、拆除操作。
　　动态分配虚通道的路由器结构如图3示。
　　 一个路由节点每个输入端口各有m个固定分配的虚通道。每个路由器还配有n个可以动态分配的虚通道,路由器的每个输出端口都会有一张方向表,用来记录进入下一级路由器的下一跳端口名称。在图4中,A节点的PE向节点C发送数据包i,根据XY路由,数据包由节点B的P0端口进入,P1端口输出;若此时节点F也向节点D发送数据包j,则必须经过节点A的P2端口,此时,P2端口检测其配置的方向表,发现到North方向的路径标志为有效(表示已经存在从节点A到节点C的虚通道链路),而到East的标志为无效(表示尚未建立从节点A到节点D的虚通道链路),则告知节点A,节点A向节点B的动态VC分配控制器发出“动态VC请求”,若节点B反馈“请求成功”,则节点A的P2端口将其P2方向上到East方向的标志设为有效。此时,数据包j通过节点A的静态VC通道、节点B的动态VC通道传递到目的节点D。当数据包传输完毕则节点B释放自己的动态VC资源,同时节点A将自己的East方向上的标志设为无效,表示释放该链接。
　　 动态VC分配虽然节省了存储器资源,但它必须增加节点间的交互信号。如节点A的输出端P2和节点B的输入端P0之间必须要增加交互信号,以满足动态虚通道建立以及拆除的请求信号、响应信号等的必要交互。
　　每个路由器中有一张动态虚通道状态表分别记录可动态分配的VC的状态。下表即为路由节点动态虚通道状态表,分别记录了每个动态输入虚通道指向本地某个输入端口、所连接的上一节点、上一节点的输出端口、上一节点与之相连的输入动态/静态虚通道的标号,以及动态虚通道的状态(忙、空闲、预忙)。动态虚通道状态记录表如表1所示。
　　在当前路由器的输入端口监测数据包的下一跳的方向,若有新的传输方向出现,则通过动态VC请求信号线向下一级路由器的动态VC控制单元发出“申请动态VC请求”。下一级路由器的动态VC控制单元检测输入端的动态虚通道是否有处于空闲状态中的;若有,则将该输入动态VC的状态设为预忙状态,并将其是否可提供动态输入虚通道以及最终提供的动态输入虚通道的编号反馈给当前路由器。当前路由器检测到下一级路由器反馈的信号,若下一级告知其可以分配动态VC,则开始路由仲裁进行包传递,建立从当前路由器输入端口经本地输出端口到下一级路由器输入端口的动态虚通道的链接。下一跳路由器此时将其输入动态虚通道的状态设为忙状态。当下一级路由器检测到该数据包的包尾时,将动态输入虚通道状态设置为空闲,释放链接。当下一个数据包要求建立链接时,再次进行上述VC分配过程。
　　
　　5仿真实验及结果
　　
　　本研究中路由器设计采用SystemC作为基本描述和集成语言。SystemC 是一种开源的基于C++ 语言的硬件设计和验证语言。它使得设计者可以采用成熟的软件设计技术(比如面向对象的设计)来进行系统仿真和验证。SystemC仿真速度快,具有软硬件协同仿真能力。
　　本文采用基于systemC的MSNS仿真器[9],网络结构采用4×4的二维mesh结构,虫洞交换机制。静态VC路由结构链路带宽为Gbps;动态VC路由结构链路带宽为Gbps,比静态结构多消耗25%的带宽资源。包长采用确定长度64Byte和32Byte,flit大小为1Byte。路由采用XY维序路由算法。在泊松分布业务注入率情况下,对典型的静态分配(V=2)和动态分配虚信道(m=1,n=2)路由器结构进行时延和吞吐率的比较。
　　泊松分布两个相邻的注入时刻之间的时间间隔服从参数为λ的指数分布。可由指数分布的概率密度函数得到注入时间间隔的随机数。
　　 F(x)=f(y)dy=1-e,x≥00,x 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　[5] Vassos Soteriou, Rohit Sunkam Ramanujam,et all. High-Throughput Distributed Shared-Buffer NoC Router[J].IEEE COMPUTER ARCHITECTURE LETTERS, VOL. 8, NO. 1, JANUARY-JUNE 2009:21-24.
　　[6] Vestias M.,Neto H.. Area and Performance Optimization of a Generic Network-on-Chip Architecture[J], Symposium on Integrated Circuits and Systems Design, SBCCI’06,2006:68-73.
　　[7] Tehran, Iran The Effect of Virtual Channel Organization on the Performance of Interconnection
　　(下转第49页)
　　Networks Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05) 1530-2075/05
　　[8] Low-latency virtual-channel routers for on-chip networks Mullins, R.; West, A.; Moore, S.;Computer Architecture, 2004. Proceedings. 31st Annual International Symposium on19-23 June 2004 Page(s):188-197
　　[9] Z. Li, X. Ling, J. Hu, “A Novel Network-on-Chip Simulation Framework for Parallel Software-Defined Radio". Presented at the International Workshop on Software Radio Technology 2008, Beijing, China.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文