片上网络路由器的交叉开关设计实现_华为路由器型号

　　摘要:交叉开关是片上网络路由器的关键部分。交叉开关的设计可以采用三态触发器或多路复用器实现。本文针对几种不同形式的交叉开关实现方案,比较了其面积和功耗的开销,同时设计了基于iSLIP算法的交叉开关调度机制。通过基本逻辑门搭建的多路复用器实现的交叉开关相比于采用三态门实现的交叉开关,在功耗、面积上有较大优势。采用iSLIP算法实现的片上网络交叉开关,具有最高的工作频率上限。
　　关键字:片上网络,交叉开关,分布式多路复用器,iSLIP算法
　　中图分类号:TN919文献标识码:A
　　
　　The design and implementation of crossbar switches
　　of network-on-ship routers
　　
　　FU Zhi-zhou,LING Xiang
　　(National Key Laboratory of Science and Technology on Communications of UESTC Chengdu,611731,China)
　　
　　Abstract: The crossbar switch is one of the most important components in the router of network-on-chips. The crossbar switches could be design based on the tristate gates, or the multiplexers. This paperintroduces different ways to implement the crossbar switch, and compares the power consumption and area cost for these implementations. Furthermore, we implement the virtual channel scheduling mechanism of crossbar based on iSLIP algorithm. The crossbar which is implemented by multiplexer have more advance in power consumption and area cost than the tri-state-gate-based crossbar. The NoC crossbar implemented based on iSLIP algorithm has the maximum frequency than others.
　　Key words: network-on-chips, crossbar switch, distributed multiplexer, iSLIP algorithm
　　
　　1引言
　　
　　片上网络(NoC)中路由器的设计结构中,交叉开关(crossbar switch)是关键的核心模块,交叉开关是在仲裁器以及控制模块的协同操作下对来自不同输入端口数据选择相应的输出端口方向。片上网络路由器中,输入端口控制器从数据包头部中提取出路由信息,通过路由查找表获得输出端口信息,然后反馈给仲裁器,当路由和仲裁确定以后,交叉开关将数据包中的一个数据微片从输入端口传送到输出端口。交叉开关的带宽、功耗和面积等在很大程度上影响片上网络路由器的性能,交叉开关需要具有高速性能并提供有效的竞争解决方案[2]。
　　文献[3]中介绍了一种称为FLEXBR的Crossbar Switch路由结构。借鉴文中的思路,我们这里给出了一种交叉节点式的Crossbar。文献[4]中提出的分布式Crossbar不能够保证输入端口的公平性,我们在这里也设计实现了以多路复用器作为基本模块的交叉开关。此外,本文利用文献[1]中提出的iSLIP算法设计了符合片上网络的路由器的Crossbar结构,在输入端口的和输出端口分别利用了仲裁器,确保了数据包传输过程中的公平性。
　　本文对三种不同结构的crossbar进行设计实现,同时分析了三种结构的性能,包括工作频率、资源开销等。
　　
　　2交叉节点式交叉开关
　　
　　在参考文献[5]中给出了传统的数据包交换Crossbar结构,借鉴这种结构我们设计了基于交叉节点式的交叉开关,这种结构中利用了三态门控制数据通路的连通性。在图1中给出了基于交叉节点方式的片上网络crossbar,输入节点和输出节点通过在交叉结点处建立互连而实现选择性的连通。图1中给出的是5×5的基于交叉节点的交叉开关。这里有5个输入端口和5个输出端口,对应着5条输入线和5条输出线,在每个交叉节点处,输入和输出进行互连。这时采用的数据交换方式为交叉开关方式,数据从输入端口进入后,通过交换结构的调度,从输出端口输出。
　　交叉节点交换器将n个输入端口和m个输出端口直接进行互连,而无需中间过程。多数crossbar是成正方形的,即m = n;也有crossbar 的m≠n。交叉节点由三态门决定,而三态门的控制电平可以由相应的仲裁器或控制逻辑决定,一旦交叉节点处于激活状态时,输入便连接到相应的输出端口,例如图1中虚线框处的cross point处于激活状态时,由East端口输入的数据便可送出到North端口。
　　 图1中三态门的控制信号构成一个控制矩阵,矩阵中每一列元素状态可以采用独热码进行编码。由于独热码在硬件实现时相比较其他的编码方式能够减少设计中的资源开销,可以减少控制各个端口动态方向所使用的寄存器数量。经过仲裁以后得到控制矩阵中的独热码,改变数据流的传输顺序,将突发错误随机化,提高纠错编码的有效性。当三态门的控制信号为高时选择相应输入端口的数据输出,否则输出为高阻状态。如果某一列元素中出现多个高电平,那么在输出线中会出现对总线竞争的情况,即多个输入端口争用一个输入端口,这时可考虑在相应输入端口增加缓冲单元,依据仲裁机制延迟数据传向输出端口。
　　
　　3基于多路复用器的交叉开关
　　
　　在采用多路复用器设计crossbar时,可以采用基本的逻辑门来设计输入端口的选通电路,如图2中,5端口的crossbar每个端口的选通电路采用基本的逻辑与、或门实现。对输入的数据采用并行处理,提高数据的吞吐量。Input(0:4)为来自5个不同输入端口的串行数据,经过选通电路,由Select的选通信号作用下根据路由查找表,从数据头部获得目的地址将数据送达相应输出端口。Select选通信号由调度器以及Round-robin仲裁器决定。此设计将串并转换电路与选通电路结合起来,减少数据的处理以及链路的传输时间。串行数据中每个端口经过与门的选通,再经过或门进行或运算便可传递到输出端口。Select选通信号在Roun-robin的控制下可以灵活改变各个输入端口的数据的优先权,在调度器的控制下改变数据流的传递方向。
　　 图2显示的是以基本逻辑门为单元搭建的crossbar模块,设计中也可以采用多路复用器的模块实现不同端口的选通;图3描述了基于多路复用器的crossbar,由控制信号控制多路复用器的选通,实现相应端口信号的选通,为每个多路复用的输入端口信号选通与相应的输出端口连接,从而建立switch的互连。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　 在试验结果的分析中表明:这种同步多路复用器形式的交叉开关适用于较低操作频率的路由器设计方案中。
　　
　　4基于i-SLIP算法的交叉开关设计
　　
　　i-SLIP算法使用多次迭代找出路径以尽可能多地利用输入和输出端口,直到再也找不到相匹配的输入和输出端口。在设计中我们采用了5端口的路由器,并且每一端口有4个虚通道(virtual channel),这样一个路由器共有20个虚通道,每个虚通道都能够接收数据包并通过路由器传送。当有多个虚通道请求同一输出信道时,我们需要有虚拟信道的分配机制以解决拥塞和能够保证完整的数据包传输过程的分配问题。
　　 虚拟信道的分配问题可以看作输入/输出之间的匹配问题,并且分为3个阶段,请求、授予、接受。为了更容易解释我们仲裁器的优先权的定义和机制。所有的输入输出在初始时刻都是不匹配的,在每次迭代的三个阶段中,输入和输出之间的匹配以并行的方式进行,三个阶段的过程如下:
　　 (1)请求阶段,如图4(a),每个有待发送数据的未能匹配的输入端口向输出端口发出请求;
　　 (2)在图4中(b)授予阶段,每个未匹配的输出端口依据轮询仲裁调度中的优先权指针,选择下一个请求输入端口。有两个输入虚拟信道分别请求输出虚拟信道2和4(1,3请求2,3,4请求4),由于当前仲裁器的优先权指针g2=1,输出端口2授予给输入端口1,然后仲裁器的优先权需要更新。
　　 (3)接受阶段,如图4中(c)所示,每个输出端口选择至多一个输出端口,由于输入端口1中优先权指针=1,将输入端口1接受输出端口1,当仲裁完成后,输入和输出之间建立了匹配的关系,同时更新仲裁优先权。
　　利用iSLIP算法,因为设计的片上网络路由器是五个端口并且假设每个端口的虚拟信道数量是4,我们给出一种数据的请求传送方式:在这里我们假设每个物理信道上的接受和授予仲裁器的均采用轮询仲裁器,并且设定优先权为1>2>3>4, I>II>III>IV,输入和输出端口的仲裁器的初始优先权均如此。
　　 在请求阶段(图5),East输入端口的虚拟信道1、2、3、4分别请求West输出端口的I,IV信道、North端口的II信道、south端口的IV信道,其余各个物理信道上的虚拟信道请求类似。
　　在授予阶段,根据输出端口授予仲裁器的初始优先权,将输出端口的物理信道中虚拟信道与输入端口中的虚拟信道建立互连关系。由于有三个输入虚拟信道请求输出端口West的I、II、IV虚拟信道,这样依据输出物理信道中授予仲裁器的优先权,将虚拟信道I授予给Ei的输入虚拟信道1。其他物理端口信道按照同样的道理操作。
　　在接受阶段(图7),物理信道Ei的输入虚拟信道1接受物理信道Wo 的虚拟信道I的授予。而在物理信道Wi中两个虚拟信道2、3都接受到输出虚拟信道授予信号反馈,因而依据接受仲裁器(accept arbiter)的优先权,虚拟信道2的优先权高,而将输入2与South输出II相连。
　　
　　5仿真结果以及数据分析
　　
　　我们分析并且比较了几种不同形式的crossbar设计,对基于三态门实现的crossbar、多路复用器实现的crossbar、以及iSLIP算法实现时5输入端口的Crossbar在ASIC面积,cells数量和时钟频率等几个方面进行的分析、验证。下面就几种方案进行分析比较:
　　 经过Design Compiler综合,比较三种不同的实现方案,基于多路复用器、基于三态门和采用iSLIP算法实现的Crossbar使用的cells数量相接近,但采用iSLIP算法时占用的面积较大,而利用iSLIP算法实现的Crossbar时钟频率相较前两者更要高一些。图中给出的iSLIP算法的数据是在每个端口数量虚拟信道数量为5时的情况。
　　如果在FPGA上实现,相比较而言,使用iSLIP算法实现片上网络互连时,占用的资源相比于另外两种方式要多一些。此外基于iSLIP算法时考虑到各个物理信道中的虚拟信道的数量,并且基于轮询调度算法的基础增强了各个虚拟信道的公平性。
　　接下来我们分析使用iSLIP算法时,虚拟信道数量变化时的Crossbar的性能以及功耗情况。在采用三维片上网络拓扑结构或者butterfly拓扑结构时,每个端口需要更多的虚通道。当每个端口虚信道数为5时,可以达到的最大工作频率为139.104MHz;当每个端口虚信道数量为8时,最大工作频率为116.844MHz,工作频率下降19.05% 。当端口虚信道数为5时,交叉开关功耗303mW,端口虚信道数为8的功耗317mW,功耗略有增加。仿真表明采用iSLIP算法时,随着各端口虚拟信道数量的增加,硬件实现的最高时钟频率下降,资源开销增加,详见图9。
　　 如果采用ASIC实现,选用SMIC 0.18um工艺库,DC综合后得到面积以及功耗结果见图10。由图可见,随虚拟信道数量增加,基于iSLIP实现的功耗、面积开销增加。
　　 在仲裁的设计实现部分,我们可以采用轮询仲裁器,也可以采用Matrix形式的仲裁器来进行实现,本文只讨论了简单轮询仲裁机制。在i-SLIP算法中输入端口的优先权更新与输出端口的优先权更新是相互独立的,提高了传输过程中VC调度的公平性。
　　
　　6总结
　　
　　本论文讨论了片上网络路由器中的核心部分crossbar的实现结构,并且采用iSLIP算法对片上网络交叉开关进行了设计实现。综合结果表明,采用iSLIP算法实现的crossbar占用了较大的面积,但相比于另外两种实现方式,交换处理速度更快,并且在输入端采用的轮询仲裁具有更好的公平性。此外随着虚拟信道端口数目的增加,资源开销增加的同时工作时钟有所下降。
　　本论文中提到的基于iSLIP算法设计Crossbar时,在输入、输出端采用的是基于轮询仲裁的Round-robin方式。还可以采用具有固定优先权的仲裁(fixed-priority arbitration)或者matrix-arbiter等不同的仲裁方式进行设计实现,这些将在未来的研究中分析。同时,输入端口虚拟信道的分布问题也是需要进一步深入研究。
　　
　　参考文献
　　[1] Nick McKeown.The iSLIP Scheduling Algorithm for Input-Queued Switches IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 7, NO. 2, APRIL 1999,188-200
　　[2] Sundar Iyer and Nick McKeown.Techniques for Fast Shared Memory Switches, STANFORD HPNG TECHNICAL REPORT TR01-HPNG-081501
　　[3] Jacob Changy_ , Srivaths Raviz, and Anand Raghunathanz FLEXBAR: A crossbar switching fabric with improved performance and utilization
　　[4] Kangmin Lee, Se-Joong Lee, and Hoi-Jun Yo0,A Distributed Crossbar Switch Scheduler for On-Chip Networks,IEEE 21x13C USTOM INTEGRATED CIRCUITS CONFERENCE, 671-674.
　　[5] Kees Goossens, Lotfi Mhamdi Iria Varela Sen??n Internet-Router Buffered Crossbars Based on Networks on Chip, 2009 12th Euromicro Conference on Digital System Design / Architectures, Methods and Tools,365-374
　　[6] David Bafumba-Lokilo, Yvon Savaria, Jean-Pierre David,Generic Crossbar Network on Chip for FPGA MPSoCs 269-272
　　[7] Deng Pan, Kia Makki, and Niki PissinouFair. Queueing based Packet Scheduling for Buffered Crossbar Switches IEEE "GLOBECOM" 2009
　　[8] Paolo Meloni§, Srinivasan Murali,Routing Aware Switch Hardware Customization for Networks on Chips.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文