摘  要： 针对阵列处理单元之间互连传输拥塞的问题，设计了一种在二维结构中互连的虚通道路由器模型。采用改进的自适应XY路由算法，智能地分配虚通道空闲资源，从逻辑上减少拥塞和等待时间，多路选择器交叉开关完成数据传输。通过ASIC设计，完成虚通道路由器硬件电路，应用Modesim工具进行仿真，达到网络互连传输的目的。

　　关键词： 网络互连；虚通道路由器；路由算法；ASIC设计

　　随着SoC（System-on-Chip）技术研究的深入，IP核数不断增加，以总线结构为通信技术的系统芯片面临着功耗、延迟、可靠性等方面的问题[1]。单芯片多处理器（CMP）采用共享总线方式通信，也同样面临着带宽限制、信号延迟等问题。一些研究机构借鉴网络通信中的思路，提出基于网络互连的NoC（Network-on-Chip）系统芯片架构，其优势就是降低SoC的功耗和制造费用、提高性能等。

　　当前，以网络互连为基础的高性能的阵列处理器系统芯片成为人们研究的热点。根据计算机体系结构的发展，共有10种体系结构模型[2]。它们以指令流、数据流与构令流计算为基础，完成算法到体系结构的时间、空间映射。一种新型的基于指令流的统一体系结构模型Unified-ISA[2]被提出，使得所有的电路设计问题统一到基于指令流计算的SIMD PE阵列上的程序设计问题。SIMD PE阵列中处理元PE之间数据传输的问题正是网络互连中路由传输的问题。

1 2D Mesh拓扑结构基本原理

　　NoC内集成了大量的资源IP核，拓扑结构解决的是互连网络中各个资源IP节点的分布与衔接。按照不同的系统性能需求，可以有不同的拓扑结构解决方案，如规则的2D Mesh网状结构、蜂窝结构、树状结构等。

　　2D Mesh是NoC互连网络中最简单、最直观、应用最广的一种拓扑结构，如图1所示的4×4网格，除了边界节点外，每个节点都连接着1个IP核单元和4个临近的路由单元，每个节点对应一个物理坐标编号（x，y），每个节点能够将数据从源地址传送到目的地址（一个或多个）。IP核可以是处理器核、DSP核、专用硬件资源或各种硬件资源的集合等。

　　在NoC网络中完成数据传输除了拓扑结构元素外，还有另一个重要元素——路由算法[1，3-5]。路由算法解决的是数据传输过程中找到最佳的传输路径，而简单、灵活、健壮、低耗、稳定的算法，正是提高传输性能的关键。

　　现实中路由算法有很多，每种算法对路由和资源的影响各不相同，具体分为无关路由（oblivious）和自适应路由（adaptive）。无关路由分为确定性XY路由和随机路由，自适应路由有伪自适应XY路由、转弯模型、DyXY路由等。

　　本设计中的算法结合了转弯、XY-XY、DyXY等路由算法的思想，解决了数据包传输中的拥塞阻塞问题。从XY路由进行演化，用目的地址与当前网络物理地址进行比较，遍历所有的可能转向。例如目的地址为（X，Y），当前网络地址为（X0，Y0），两者比较就有9种情况。根据每条数据链路的当前传输状况，可以调整数据的方向，比如向右方向数据较多时，如果目的地址是在右下方向，则可以先调整方向转弯向下走，以减少拥塞。在具体设计过程中数据传输方向不会往回走，只会朝着目标前进，可以避免回环死锁现象。另外在路由逻辑中还可以仲裁均衡每个方向的平等性。

2 虚通道路由器总体设计模型

　　虚通道路由器软核是应用于片上网络（NoC）的一个包交换型路由器，是NoC的重要基础部件。其体系结构框图如图2所示。

　　5个相同的端口输入模块（Input）分别为东、南、西、北4个方向和一个IP核方向，每个端口有多个虚通道，每个虚通道由不同深度的缓存模块构成，用同步FIFO或异步FIFO实现。5个缓存结构设计相同，便于复用。2D Mesh结构中一个路由的输出方向最多为4个（不会回头），所以虚通道数[6]可以为4。

　　虚通道分配器（Vc_allactor）为路由逻辑中的主要部分，是给输入缓存中的数据分配空闲的数据信道，根据路由算法选择输出方向，提供信号给交叉开关模块。由于每个方向都有4个虚通道，多个方向向同一方向传送数据时能够充分传输，减少拥塞过程中的等待时间，增加吞吐量。但当同一方向的数据来源多于4个时，则需要交换分配器来控制，可以根据优先级或其他策略实现。

　　交叉开关模块（Crossbar）根据路由逻辑中的方向选择，完成数据的最后输出。

3 路由器模块化设计

　　为简化设计，设计中每个方向的虚通道数为1，数据包packet结构由包头数据header和包负载数据payload组成。设计中采用16 bit宽度的包数据，在一定需求的情况下可以进行扩展。有4 bit控制信息，1 bit标志位，3 bit包尺寸；6 bit源地址信息；6 bit目标地址信息，高3位为X方向地址，低3位为Y方向地址。中间片flit都是16 bit数据的包负载。数据格式如图3所示。

　　根据整个路由节点的数据流和控制流两个方向，将设计分为3大模块：输入缓存模块、逻辑控制模块和交叉开关模块。数据从输入缓存中流入，经过控制模块分配处输出方向，交叉开关根据方向选择缓存中的数据输出。

　　3.1 输入缓存模块（FIFO）

　　路由传输中，把整个消息分为若干个数据包，数据包存储在虚通道缓存中。

　　每个方向的输入模块都一样。以本地路由方向W缓存为例，如图4所示，采用ASM有限状态机实现。类似于IP网络传输中的握手机制协议，请求与应答。虚通道缓存中只有在没数据时才能接收数据，只有在目的缓存（下一级虚通道）准备好时才能输出数据。内部虚通道与路由逻辑之间也存在握手机制，只有在请求发送信号得到确认时才发送数据包头数据，否则等待。

　　由于包尺寸大小决定了FIFO的深度，并且在一次数据发送完毕后清除数据，释放缓存空间，因此不存在读空写满的现象，而且读写双方在时间上不会冲突。

　　3.2 路由逻辑控制模块（Routing Logic）

　　算法逻辑控制模块的主要任务是对数据包的输出方向进行分配控制。可分为3个小部分：包头数据译码分析、输出方向预处理和轮询仲裁输出方向。

　　算法实现大致步骤如下（*为w、s、e、n、ip的略写，下同）：

　　（1）当5个方向有传输请求syn_*，并行确认来自5个方向的发送请求ack_*；

　　（2）接收5个方向的包头目标地址数据data_head_*[5：0]；

　　（3）依据算法，目标地址与本地实际地址（X0，Y0）进行比较，遍历所有可能的输出使能方向，如图5所示，判断得到各种情况的输出使能列表*_en_list=={*_en_w，*_en_s，*_en_e，*_en_n，*_en_ip}。当接收到清除信号clear时，使能列表初始化。在数据包没有到达目标节点时，方向使能列表中有2个位为1，因此这里可以实现下一步的阻塞转弯减少拥塞。使能列表只有到达目标地址时，才只有一个位为1。

　　（4）根据使能列表（*_en_list）和本地路由所有路径的忙碌状态（w_busy_*，s_busy_*，e_busy_*，n_busy_*，ip_busy_*）进行自适应方向调整，忙状态标志来自仲裁部分，用来判断是否方向转弯操作。在空闲状态下用W>S>E>N>IP的优先规则得到预期的输出方向w_to_*，s_to_*，e_to_*，n_to_*，ip_to_*，汇总得到初步输出方向to_*={w_to_*，s_to_*，e_to_*，n_to_*，ip_to_*}。这里，会出现多个方向同时向同一个方向发出使能的情况，将进入下一步轮询仲裁。如图6所示的W方向的输出使能状态，使能列表中有2个位为1。首先判断路径是否被占用，即是否有忙信号，当有busy信号时考虑转弯调整，当2个使能方向路径都被占用时，只能等待路径的释放，这里方向使能列表一直都在。空闲状态下根据优先级W>S>E>N>IP，W向使能方向发出预期的输出使能w_to_*。

　　（5）最后进入轮询仲裁模块[7]，没有冲突的情况下可顺利得到最终的控制方向ctrl_*和路径忙信号*_busy_*，有冲突时根据轮询优先级产生最后的输出方向控制信息。在最高优先级传输完数据时进入下一个轮询，每一个方向都有公平轮询的机会，能够避免死锁和长时间等待的情况。图7展示的是仲裁输出示意图，当前状态优先级为W>S>E>N>IP，下一个状态就为S>E>N>IP>W。

　　（6）当清除信号来临时，复位该方向的一切控制信息，如上面的输出使能方向、预处理输出方向和最终的输出控制方向。至此控制模块完成了工作。

　　3.3 交叉开关输出模块（crossbar）

　　交叉开关crossbar[8]，实现与下一级的高效通信，也是NoC系统中的一个关键技术，来获取更高的性能和效率。本设计中采用多路选择器来实现crossbar。有5个方向输入和5个方向输出。

　　根据逻辑控制模块仲裁的选通信号，5个五选一多路选择器选择输出方向。随后就是将本地缓存中的数据输出到下一级的缓存中，达到最终的传输。

　　握手机制：首先向目标方向（下一级）发送输出数据请求，得到下一级确认可以接收数据（下一级缓存为空）后，再发送读信号给缓存模块输出数据，下一状态crossbar发送写状态和数据给下一级缓存。当接收到来自本级缓存的清除信号clear后，读写都置0，这样在读写的有效控制下完成数据传输。

　　3.4 仿真验证

　　采用Modesim6.5工具仿真实现验证。首先验证路由器各个方向数据通路的流通性；其次验证拥塞状况下数据的传输状态；最后优化设计，提高性能。图8、图9显示的是拥塞状态下仿真的数据输入输出结果。

　　仿真模拟4个方向同时竞争向E传输请求，第一批E方向的数据正常向W传输，W向E的数据方向调整向N，N方向占用信道向E传输，IP向东、北方向的E、N信道都被占用，S向E传输等待。第二批S向E先占用信道，IP调整方向向N。

　　设计实现的虚通道路由器的电路模型能够实现NoC网络中的数据传输，足够的虚通道数提高并行传输的吞吐率。仿真结果显示，自适应XY分配算法能够避免死锁、活锁的现象。虚通道路由器的设计方法对后续SIMD PE阵列体系结构的研究具有指导意义。

　　参考文献

　　[1] 刘有耀.片上网络拓扑结构与通信方法的研究[D].西安：西安电子科技大学，2009.

　　[2] 沈绪榜，刘泽响，王茹.计算机体系结构的统一模型[J].计算机学报，2007，30（5）：729-736.

　　[3] 王芳莉，杜慧敏.片上网络路由算法综述[J].西安邮电学院学报，2011，16（1）：72-77.

　　[4] Liu Youyao，Gao Meng. Mesh-conneted rings topology for network-on-chip[J]. Posts and Telecommunications， 2013，20（5）：30-36.

　　[5] PUTHALL M K， SINGH V， GAUR M S， et al. C_Routing： an  adaptive hierarchical NoC routing methodology[C]. 2011 IEEE/IFIP 19th International  Conference on  VLSI and  System-on-Chip， Kowloon，Hong Kong，China， 2011.

　　[6] 张香香.片上网络虚通道分配算法研究[D].西安：西安电子科技大学，2012.

　　[7] 张哲，高小鹏，龙翔.适用于虚通道路由器的高性能round-robin仲裁器[J].北京航空航天大学学报，2007，33（6）：743-747.

　　[8] 付志洲，凌翔.片上网络路由器的交叉开关设计实现[J].中国集成电路，2010，19（9）：63-68.