片上网络路由器的交叉开关设计实现

1、片上网络路由器的交叉开关设计实现摘要 :交叉开关是片上网络路由器的关键部分。 交叉开 关的设计可以采用三态触发器或多路复用器实现。本文针对 几种不同形式的交叉开关实现方案 ,比较了其面积和功耗的 开销 ,同时设计了基于 iSLIP 算法的交叉开关调度机制。 通过 基本逻辑门搭建的多路复用器实现的交叉开关相比于采用 三态门实现的交叉开关 ,在功耗、面积上有较大优势。采用 iSLIP 算法实现的片上网络交叉开关 ,具有最高的工作频率上 限。关键字 :片上网络 ,交叉开关 ,分布式多路复用器 ,iSLIP 算 法中图分类号 :TN919 文献标识码 :AThe design and implemen

2、tation of crossbar switches of network-on-ship routersFU Zhi-zhou,LING Xiang(National Key Laboratory of Science and Technology onCommunications 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

3、 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

4、 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, di

5、stributed multiplexer, iSLIP algorithm1 引言片上网络 (NoC) 中路由器的设计结构中 ,交叉开关 (crossbar switch) 是关键的核心模块 ,交叉开关是在仲裁器以 及控制模块的协同操作下对来自不同输入端口数据选择相 应的输出端口方向。 片上网络路由器中 ,输入端口控制器从数 据包头部中提取出路由信息 ,通过路由查找表获得输出端口 信息 ,然后反馈给仲裁器 ,当路由和仲裁确定以后 ,交叉开关将 数据包中的一个数据微片从输入端口传送到输出端口。交叉 开关的带宽、功耗和面积等在很大程度上影响片上网络路由 器的性能 ,交叉开关需要具有高速性能并提供

6、有效的竞争解 决方案 2 。文献3中介绍了一种称为 FLEXBR 的 Crossbar Switch 路由结构。 借鉴文中的思路 ,我们这里给出了一种交叉节点式 的Crossbar。文献4中提出的分布式 Crossbar不能够保证输 入端口的公平性 ,我们在这里也设计实现了以多路复用器作 为基本模块的交叉开关。此外,本文利用文献 1 中提出的iSLIP算法设计了符合片上网络的路由器的Crossbar结构,在输入端口的和输出端口分别利用了仲裁器,确保了数据包传输过程中的公平性。本文对三种不同结构的crossbar进行设计实现，同时分析了三种结构的性能 , 包括工作频率、资源开销等。2 交叉节点式

7、交叉开关在参考文献5中给出了传统的数据包交换Crossbar结构,借鉴这种结构我们设计了基于交叉节点式的交叉开关,这种结构中利用了三态门控制数据通路的连通性。在图 1 中给出了基于交叉节点方式的片上网络crossbar输入节点和输出节点通过在交叉结点处建立互连而实现选择性的连通。图 1 中给出的是5X 5的基于交叉节点的交叉开关。这里有5个输入端口和 5个输出端口 ,对应着 5条输入线和 5条输出线 , 在每个交叉节点处 ,输入和输出进行互连。这时采用的数据交换方式为交叉开关方式 ,数据从输入端口进入后 ,通过交换结 构的调度 ,从输出端口输出。交叉节点交换器将n个输入端口和m个输出端口直接进

8、 行互连 ,而无需中间过程。 多数 crossbar 是成正方形的 ,即 m = n;也有crossbar的m工n。交叉节点由三态门决定 ，而三态门 的控制电平可以由相应的仲裁器或控制逻辑决定,一旦交叉节点处于激活状态时 ,输入便连接到相应的输出端口,例如图1 中虚线框处的 cross point 处于激活状态时 ,由 East 端口输入 的数据便可送出到 North 端口。图 1 中三态门的控制信号构成一个控制矩阵 ,矩阵中每 一列元素状态可以采用独热码进行编码。由于独热码在硬件 实现时相比较其他的编码方式能够减少设计中的资源开销 , 可以减少控制各个端口动态方向所使用的寄存器数量。经过 仲

9、裁以后得到控制矩阵中的独热码 ,改变数据流的传输顺序 , 将突发错误随机化 ,提高纠错编码的有效性。 当三态门的控制 信号为高时选择相应输入端口的数据输出,否则输出为高阻状态。如果某一列元素中出现多个高电平,那么在输出线中会出现对总线竞争的情况 ,即多个输入端口争用一个输入端口 ,这时可考虑在相应输入端口增加缓冲单元,依据仲裁机制延迟数据传向输出端口。3 基于多路复用器的交叉开关在采用多路复用器设计 crossbar 时,可以采用基本的逻辑 门来设计输入端口的选通电路,如图 2 中,5 端口的 crossbar 每个端口的选通电路采用基本的逻辑与、或门实现。对输入的 数据采用并行处理，提高数据

10、的吞吐量。Input(0:4)为来自5个 不同输入端口的串行数据，经过选通电路，由Select的选通信 号作用下根据路由查找表 ,从数据头部获得目的地址将数据 送达相应输出端口。 Select 选通信号由调度器以及 Round-robin 仲裁器决定。 此设计将串并转换电路与选通电路 结合起来 ,减少数据的处理以及链路的传输时间。串行数据中每个端口经过与门的选通 ,再经过或门进行或运算便可传递 到输出端口。 Select选通信号在 Roun-robin的控制下可以灵 活改变各个输入端口的数据的优先权 ,在调度器的控制下改 变数据流的传递方向。图2显示的是以基本逻辑门为单元搭建的crossbar

11、模块,设计中也可以采用多路复用器的模块实现不同端口的选通 ; 图3描述了基于多路复用器的crossbar,由控制信号控制多路复用器的选通 ,实现相应端口信号的选通 ,为每个多路复用的输入端口信号选通与相应的输出端口连接,从而建立 switch的互连。本文为全文原貌 未安装 PDF 浏览器用户请先下载安装 原 版全文 在试验结果的分析中表明 :这种同步 多路复用器形式的交叉开关适用于较低操作频率的路由器 设计方案中。4 基于 i-SLIP 算法的交叉开关设计i-SLIP 算法使用多次迭代找出路径以尽可能多地利用输 入和输出端口 ,直到再也找不到相匹配的输入和输出端口。 在 设计中我们采用了 5端

12、口的路由器 ,并且每一端口有 4 个虚通 道 (virtual channel), 这样一个路由器共有 20 个虚通道 ,每个虚 通道都能够接收数据包并通过路由器传送。当有多个虚通道 请求同一输出信道时 ,我们需要有虚拟信道的分配机制以解 决拥塞和能够保证完整的数据包传输过程的分配问题。虚拟信道的分配问题可以看作输入 /输出之间的匹配问 题,并且分为 3 个阶段 ,请求、授予、接受。为了更容易解释 我们仲裁器的优先权的定义和机制。所有的输入输出在初始 时刻都是不匹配的 ,在每次迭代的三个阶段中 ,输入和输出之 间的匹配以并行的方式进行 ,三个阶段的过程如下 :(1) 请求阶段 如图4(a)，每

13、个有待发送数据的未能匹配的 输入端口向输出端口发出请求 ;在图4中(b)授予阶段，每个未匹配的输出端口依据轮 询仲裁调度中的优先权指针 ,选择下一个请求输入端口。 有两 个输入虚拟信道分别请求输出虚拟信道 2和 4(1,3请求 2,3,4 请求4),由于当前仲裁器的优先权指针g2=1,输出端口 2授予给输入端口 1,然后仲裁器的优先权需要更新。接受阶段 如图4中(c)所示，每个输出端口选择至多 一个输出端口 ,由于输入端口 1 中优先权指针 =1,将输入端口 1 接受输出端口 1,当仲裁完成后 ,输入和输出之间建立了匹配 的关系 , 同时更新仲裁优先权。利用 iSLIP 算法,因为设计的片上网

14、络路由器是五个端口 并且假设每个端口的虚拟信道数量是 4,我们给出一种数据的 请求传送方式 :在这里我们假设每个物理信道上的接受和授 予仲裁器的均采用轮询仲裁器,并且设定优先权为1234,IIIIIIIV ,输入和输出端口的仲裁器的初始优先权均如此。在请求阶段(图5),East输入端口的虚拟信道1、2、3、4分别请求 West输出端口的l,IV信道、North端口的II信道、 south端口的IV信道，其余各个物理信道上的虚拟信道请求类 似。在授予阶段 ,根据输出端口授予仲裁器的初始优先权 ,将输出端口的物理信道中虚拟信道与输入端口中的虚拟信道 建立互连关系。 由于有三个输入虚拟信道请求输出端

15、口 West 的 I、II 、IV 虚拟信道 ,这样依据输出物理信道中授予仲裁器 的优先权 ,将虚拟信道 I 授予给 Ei 的输入虚拟信道 1。其他物 理端口信道按照同样的道理操作。在接受阶段 (图 7),物理信道 Ei 的输入虚拟信道 1 接受物 理信道 Wo 的虚拟信道 I 的授予。而在物理信道 Wi 中两个 虚拟信道 2、 3 都接受到输出虚拟信道授予信号反馈,因而依据接受仲裁器(accept arbiter)的优先权，虚拟信道2的优先权 高，而将输入2与South输出II相连。5 仿真结果以及数据分析我们分析并且比较了几种不同形式的crossbar设计，对基于三态门实现的 crossb

16、ar、多路复用器实现的 crossbar、以及 iSLIP算法实现时5输入端口的 Crossbar在ASIC面积,cells 数量和时钟频率等几个方面进行的分析、验证。下面就几种 方案进行分析比较 :经过 Design Compiler 综合,比较三种不同的实现方案 , 基于多路复用器、基于三态门和采用 iSLIP 算法实现的 Crossbar使用的cells数量相接近，但采用iSLIP算法时占用的 面积较大，而利用iSLIP算法实现的Crossbar时钟频率相较前 两者更要高一些。图中给出的 iSLIP 算法的数据是在每个端口数量虚拟信道数量为 5 时的情况。如果在 FPGA 上实现 ,相比

17、较而言 ,使用 iSLIP 算法实现片 上网络互连时 ,占用的资源相比于另外两种方式要多一些。此外基于 iSLIP 算法时考虑到各个物理信道中的虚拟信道的数 量,并且基于轮询调度算法的基础增强了各个虚拟信道的公 平性。接下来我们分析使用 iSLIP 算法时 ,虚拟信道数量变化时 的 Crossbar 的性能以及功耗情况。在采用三维片上网络拓扑 结构或者 butterfly 拓扑结构时 ,每个端口需要更多的虚通道。 当每个端口虚信道数为5 时 ,可以达到的最大工作频率为139.104MHz; 当每个端口虚信道数量为 8 时,最大工作频率为 116.844MHz, 工作频率下降 19.05% 。当

18、端口虚信道数为 5 时,交叉开关功耗303mW,端口虚信道数为8的功耗317mW, 功耗略有增加。 仿真表明采用 iSLIP 算法时 ,随着各端口虚拟 信道数量的增加 ,硬件实现的最高时钟频率下降 ,资源开销增 加,详见图 9。如果采用ASIC实现，选用SMIC 0.18um工艺库，DC综 合后得到面积以及功耗结果见图1 0。由图可见 ,随虚拟信道数量增加 ,基于 iSLIP 实现的功耗、面积开销增加。在仲裁的设计实现部分 ,我们可以采用轮询仲裁器 ,也 可以采用 Matrix 形式的仲裁器来进行实现 ,本文只讨论了简 单轮询仲裁机制。 在 i-SLIP 算法中输入端口的优先权更新与输出端口的

19、优先权更新是相互独立的 ,提高了传输过程中 VC 调度的公平性。6 总结本论文讨论了片上网络路由器中的核心部分 crossbar 的 实现结构 ,并且采用 iSLIP 算法对片上网络交叉开关进行了设 计实现。综合结果表明 ,采用 iSLIP 算法实现的 crossbar 占用 了较大的面积 ,但相比于另外两种实现方式 ,交换处理速度更 快,并且在输入端采用的轮询仲裁具有更好的公平性。此外随着虚拟信道端口数目的增加 ,资源开销增加的同时工作时钟 有所下降。本论文中提到的基于 iSLIP 算法设计 Crossbar 时 ,在输 入、输出端采用的是基于轮询仲裁的 Round-robin 方式。还 可

20、以采用具有固定优先权的仲裁 (fixed-priority arbitration) 或 者 matrix-arbiter 等不同的仲裁方式进行设计实现 , 这些将在 未来的研究中分析。 同时 ,输入端口虚拟信道的分布问题也是 需要进一步深入研究。参考文献1 Nick McKeown.The iSLIP Scheduling Algorithm for Input-Queued Switches IEEE/ACM TRANSACTIONS ONNETWORKING, VOL. 7, NO. 2, APRIL 1999,188-2002 Sundar Iyer and Nick McKeown.Techniques for Fast Shared Memory Switches, STANFORD HPNG TECHNICAL REPORT TR01-HPNG-0815013 Jacob Changy_ , Srivaths Raviz, and Anand Raghunathanz FLEXBAR: A crossbar switching fabric with improved performance and utilization4 Kangmin Lee, Se-Joong Lee, and Hoi-Jun Yo0,A