基于纵向优先多播路由算法的片上网络路由器设计

史媛芳，李润丰

（1.安徽国防科技职业学院 机电工程系 安徽 六安 237011；2.合肥工业大学 计算机与信息学院，安徽 合肥 230009）

基于纵向优先多播路由算法的片上网络路由器设计

史媛芳1，李润丰2

（1.安徽国防科技职业学院 机电工程系 安徽 六安 237011；2.合肥工业大学 计算机与信息学院，安徽 合肥 230009）

设计了一种支持多播通信技术的简单片上路由器，采用“纵向优先”的多播路由算法和虫孔交换技术，实现同时向指定区域内多个节点发送数据的功能。通过仿真验证了算法有效可用，在节约网络资源、提高系统工作效率方面，具有实用性。

片上网络；多播通信；多播路由器；纵向优先

20世纪90年代末期，传统的片上系统（SoC）的总线架构已不能应对随着半导体技术发展而出现的一些问题，比如可扩展性、时间同步和并行通信等，为了弥补这些不足，研究机构正式提出了片上网络（NoC）的概念。当前，国内外对片上网络技术的研究范围主要集中在体系结构、操作系统、设计方法、设计工具及应用服务等领域［1］。随着集成电路技术的不断发展，芯片越来越多地由第三方提供的IP核集成，形成具有众核的大规模集成电路；而对芯片中众多的IP核进行快速有效的测试，会遇到许多问题，如测试时间过长与测试功耗过大的问题。研究表明，合理使用并行测试的方法则能有效地解决这些问题［2］。将网络通信技术运用在NoC芯片测试中是目前芯片测试的主要手段。NoC的数据传送方式主要是单播通信和多播通信，多播通信技术的出现是多核并行处理的需求［3］。在数据传输与芯片测试中，片上路由器实现了网络互连、网络处理和网络管理的功能，它是NoC设计中最重要的部分，也是实现高性能NoC的关键［4］。

1 多播路由器设计

片上网络路由器的设计过程主要涉及输入存储、路由算法、虚拟通道仲裁、交叉开关和链路控制技术等几方面的问题。

1.1 总体结构设计

本文所设计的路由器是一个可以实现多播通信的简单的片上路由器，它运用基于“纵向优先”思想的X-Y路由策略，采用虫孔交换技术，通过建立虚电路的方式进行数据的传送，传送方向是一个指定大小的矩形区域。路由器由输入控制及路由仲裁器、交叉选择开关、输出缓冲及控制器三大部分组成。其中：输入控制及路由仲裁器用来接收数据，解析目的地址，同时选择传输方向；交叉选择开关根据路由仲裁器发来的方向传送数据包；输出缓冲及控制器则负责发送数据。

本方案涉及“东、西、南、北、本地”五个方向的数据输入和数据输出。图1为路由器的总体结构框架及主要引脚图。由图1可以看出，5×5的交叉选择开关将从5个方向输入的数据传送到不同的方向，实现路由最基本的存储和转发功能。图中的L、E、W、S、N分别表示本地、东、西、南、北。

图1 路由器的总体结构

由于方案采用的路由是基于虫孔交换技术的，因此，在输出端口设置了一个输出缓存（buffer），这个缓存的大小设为数据流控制单位的大小，即一个微片的大小。当某个路由阻塞时，未发出的微片就存储在这个缓存中，同时阻止上一个路由向本路由发送数据。

1.2 多播路由器的关键技术

设计路由器还要包括数据包格式、路由协议和转发策略各个方面。其中，路由策略包括确定性路由和自适应路由两大类。前者使用较多的是维序路由，主要包括X-Y路由和E-code路由两大类；后者中最常用的是自适应X-Y路由。由于片上网络面积和功耗等条件的制约，要求路由算法不能过于复杂，因此，简单无死锁的X-Y路由最为常用，即先在X方向、再在Y方向上传送数据，只要源节点和目的节点固定，数据包的传输路径也就固定了［5］。

虫孔交换技术是将发送的消息，也就是数据包，分割为若干个微片，分别缓存在路由器中。每个数据包的头微片包含控制路由信息，剩余的微片以流动的方式在向前“蠕动”，如果遇到阻塞，流动中的微片则存储在阻塞发生时所在的节点里面［5-6］。此时，每个路由器只需缓存当前微片，以及阻塞发生时暂时存储进来的几个微片就可以了，而不需要缓存整个数据包。这样，路由器所需缓存空间就可大大缩小［5］。

1.3 纵向优先多播路由算法策略

当数据微片到达目标顶点时，目标顶点会将数据微片复制并向矩形区域内的X和Y方向同时发送。从X方向接收到微片的路由节点重复上一个顶点的发送方向，而从Y方向接收到微片的路由节点只需向Y方向发送即可，直到发送到矩形区域的边界为止。这样便能用最短的时间将数据微片传送到矩形区域的每个节点，而不会造成数据的重传和回传。

图2为纵向优先多播路由算法实例图。图2是一个7×4 Mesh网络NoC，数据包由A节点进入，需要传送到虚线框中的每个节点。通过比较A节点与该矩形四个顶点（即B、D2、D1和H）的路径距离，系统确定A点离B点最近，因此将微片传送到B节点。B节点将微片向右方和下方传送，即向C2和C1传送。当微片到达C2时，C2判断微片是由X方向传送来的，因此C2将数据微片复制后，继续向下方和右方传送；而微片到达C1时，因为微片是由Y方向传送而来，所以C1只将微片向下方发送。这样便做到了在最短的时间内让矩形区域内的所有节点都能接收到数据。

图2 “纵向优先的多播路由算法”实例图

1.4 多播路由器各部件设计

1.4.1 数据包格式设计

本文设计的多播路由器具有将同一个数据包发送到指定大小矩形区域内的IP核的功能。如IP核需要这些数据则接收，不需要则自动抛弃。因此数据包格式必须满足矩形区域范围地址均可到达的条件。

微片分为头微片、中间微片和尾微片三种，通过前两位标志位区分，即“01”表示这个微片是头微片，“10”表示中间微片，“11”表示尾微片。其中头微片用来传送目的地址信息，它让路由器可识别到微片所要送达的目的地。路由识别后由交叉开关负责把微片送到正确的输出端口。紧接着标志位的八位为目的矩形对角线上一个顶点的地址，后八位为该对角线上另一顶点的地址，这样可以确定唯一一个矩形区域；如果后八位全是“1”，则表示本数据包只有一个目的地址。中间微片和尾微片的任务是传送具体数据，它们的前两位也为标志位，后16位是数据位。尾微片还可用来表示数据已经传送完毕。

1.4.2 输入控制及路由仲裁器设计

输入控制器是数据进入路由器经过的第一道关卡，而路由仲裁器则是用来解析数据头微片，找出目的地址和传送方向的关键部件。图3为输入控制及路由仲裁器的引脚示意图。

由图3可见，此部分主要有11条信号线，其中：“clk”是时钟信号；“rst”是复位信号；“ads”是发送数据前注入的当前路由器的地址信息，共8位，它用当前路由在网络中的X和Y坐标来表示地址，“ads”的前四位表示X方向坐标，后四位表示Y方向坐标，注入“ads”信号后，当前的路由地址不会再改变；“DataX_in”是上一个路由发来的数据信息；“ReqX_in”是上一个路由发来的请求发送数据信号；“AckX_out”是当前路由器给上一个路由器发送的应答信号，表示数据已经收到；“DataX_sel”是输入控制器向交叉选择开关发送的数据信息；“ReqX_sel”是输入控制器向交叉选择开关发送的请求信号；“AckX_sel”则是交叉开关回复的应答信号；“Select”是路由仲裁器发给交叉开关的方向选择信号，此信号共5位，分别表示“本地、东、西、南、北”五个方向，当需要向某一个或几个方向传送数据时，该方向所对应的表示位置为“1”，否则为“0”，例如需要同时向“本地、南、北”三个方向传送数据，则置Select为“10011”；“Keep_sel”是地址保持信号，从头微片到达至尾微片到达始终置为“1”，起到保持虚电路的功能。

针对输入控制器部分，可用循环的状态转换图来实现。路由选择算法则使用前文提到的“纵向优先多播路由算法”。

图3 输入控制器和路由仲裁器信号及引脚示意图

1.4.3 交叉选择开关设计

交叉选择开关是整个多播路由中最为重要的模块之一，它负责将输入控制及路由仲裁器输送来的数据根据其路由信息转发到一个或多个不同的端口，即实现多播通信功能。本文交叉开关的设计部分解决了实现在内部向多端口传输数据的问题。

开关设计输入和输出端口各五个，本文只选取其中一个输入端口与一个输出端口进行分析。图4所示为交叉选择开关的部分引脚与信号线。

图4中，“DataL_sel”是本地（Local）输入控制及路由仲裁器发来的数据信号；“ReqL_sel”为请求信号；“SelectL”为路由选择信号，模块根据这个信号来进行输出端口的选择；“KeepL_sel”为虚电路保持信号，如果此信号为“1”，则不检测新的路由选择信号；“AckL_sel”为应答信号；“Data_que”为交叉开关发送给输出缓冲器的数据信息；“ReqL_que”为请求信号；“AckL_que”为应答信号。

图4 交叉选择开关的部分引脚与信号线

1.4.4 输出缓冲及控制器设计

输出缓冲及控制器是用于控制数据输出和缓存的重要模块。此模块结构和输入控制模块结构类似，不同的是“DataX_que”表示交叉开关发送来的数据信息，“ReqX_que”表示交叉开关发送来的请求信号，“AckX_que”表示应答信号，“DataX_out”表示输出控制器向下一个路由发送的数据信息，“ReqX_out”表示向下一个路由发送的请求信号，“AckX_in”表示下一个路由发来的应答信号。

2 实验仿真

2.1 单个路由仿真

本文运用Modelsim仿真软件和Synplify综合工具，来验证所设计的路由器的逻辑功能。将5个输入控制与路由仲裁器、1个交叉选择开关、5个输出缓冲及控制器组合起来便构成了一个简单的、支持多播功能的路由器。对其进行数据输入，并观察它是否从正确的端口输出。由于路由涉及的引脚多，本文仅选取几个重要的引脚信号波形图，图5所示即为单个路由的部分仿真波形图。

从图5中可以看出，该路由地址为“00000000”，当本地方向发来请求信号时，经过解析头微片看到，目的矩形顶点地址是“00010001”和“00000000”，可知该数据包的目的地址是位于对角线顶点“00010001”和“00000000”的矩形区域，也就是“00000000”“00010000”“00000001”“00010001”四个节点。经判断后得出传送方向为东和南。在图5中可以看到，东和南的输出端口正确输出了数据。

图5 单个多播路由器仿真波形图

2.2 多个路由仿真

本文用4个路由与4个简单的IP核组成一个2×2的NoC网络。路由的地址用坐标表示，分别用（0，0）、（0，1）、（1，0）、（1，1）代表。IP核是为了验证路由的正确性而设置的一个简单的装置，只具备接收数据并在内部缓存中存储数据的功能。

对这个简单的支持多播技术的NoC网络进行编程测试。路由1输入数据，目的路由节点是路由2和路由4组成的矩形区域。本文分别截取仿真过程中数据流经的路由1、路由2、路由4、IP2和IP4的波形图来说明数据在NoC网络的传输过程。同样，这里也只列出几种主要的信号波形。

（1）路由1。图6所示是路由1的波形图。由图6可见，路由1的地址是“00000000”，数据从北边端口进来，目的地址是“00010001”和“00010000”两个节点为对角线的矩形区域，也就是路由2和路由4。由于该矩形区域是设置在路由1的右侧，因此路由仲裁得出传输方向为“01000”，即向东传送给路由2。从图6中可以看出，东端口输出正确的数据信息。

图6 路由1波形图（多播）

（2）路由2。图7所示是路由2的波形图，它的地址是“00010000”。由图7可见，它接收到路由1传来的信息后，经过分析地址信息，得出该数据包需要向两个方向发送，分别是南边和本地。由图7可见，南边的输出端口和本地的输出端口先后发送出数据。数据将发送至路由器4和IP2。

图7 路由2波形图（多播）

（3）IP2。图8所示是IP2的波形图，可以看到节点2的IP核成功接收到了路由2发来的数据。

图8 IP2波形图（多播）

（4）路由4。图9所示的是路由4的波形图。从图9中可以看到，路由4接收到路由2发来的数据信息后，解析得出该数据的目的地就是本地，因此路由选择信号为“10000”。数据发送至本地输出端口，即IP4。

图9 路由4波形图（多播）

（5）IP4。图10所示是IP4的波形图，可以看到节点4的IP核成功接收到了路由4发来的数据。

图10 IP4波形图（多播）

至此，含有两个目的地址的信息都成功传送到了目的节点，证明本文设计的路由器简单、有效。

3 结束语

在片上网络互连结构中，片上路由器用于支持报文的转发、实现数据流的路由和存储转发数据包功能，是实现高性能片上网络的关键。本文设计了一个简单的、支持多播通信的NoC路由。主要包括对数据包格式、路由仲裁器和交叉选择开关等模块的设计。该路由器能同时识别一个矩形区域内的多个目的地址，并能正确地向多个不同的目的地发送数据，实现了多播路由器的雏形。经过软件仿真，证实它可以在复杂的环境中向规定矩形区域内的目的地正确地发送数据信息，从而实现将信息向一片节点广播。

［1］ 岳峰，李润丰，陈田，等.基于随机路由的高性能片上路由器设计与仿真［J］.电子测量与仪器学报，2013（7）：669-675.

［2］ 方芳，韩银和，李晓维.热量敏感的众核芯片多播并行测试方法［J］.计算机辅助设计与图形学学报, 2010（5）：845- 851.

［3］ 方芳，董建波，韩银和，等.支持多播路径传输的片上网络并行测试方法［J］.电子测量与仪器学报，2010（10）：911-917.

［4］ 于鹏.片上网络中路由器技术的研究［D］.西安：西安电子科技大学，2011.

［5］ 董少周.NoC路由算法及仿真模型的设计与研究［D］.合肥：合肥工业大学，2009.

［6］ 朱兵.基于片上网络的通信路由方法研究［D］.合肥：合肥工业大学，2009.

【责任编辑 梅欣丽】

A New Design of Networks-on-chip Router with Longitudinal-priority-algorithm-based Multicast Routing

SHI Yuanfang1，LI Runfeng2
（1. Department of Electrical Engineering, Anhui National Defence Vocational College, Lu’an 237011, China； 2. School of Computer and Information, Hefei University of Technology, Hefei 230009, China）

In this paper, we designed a simple on-chip router to support multicast communication technology. By adopting the longitudinal-priority multicast routing algorithm and using the wormhole switching technology, sending data to multiple nodes within a designated region at the same time is achieved. Through simulated test, effective availability, this design has certain applicability in the aspects of saving network resources and raising the working efficiency of the system.

networks-on-chip； multicast communication； multicast router； longitudinal-priority

TP302

A

2095-7726（2015）03-0028-05

2015-01-01

2011年安徽省高等学校省级教学质量与教学改革工程项目

史媛芳（1984-），女，安徽寿县人，硕士，研究方向：计算机应用技术和人工智能。