支持虚拟电路机制的包连接电路路由器

侯 宁， 贺 伟， 宋宇鲲

（1.河南城建学院 电气与信息工程学院，河南 平顶山 467000；2.合肥工业大学 微电子设计研究所，安徽 合肥 230009）

片上网络（network on chip，NoC）是1999年前后几个研究小组提出的一种全新的片上互连通讯架构［1－2］。与总线、交叉开关等传统架构相比，NoC在可扩展性、可重用性、设计效率、通讯带宽等方面具有优势［3－5］。至今，NoC已经成为多核处理器互连通讯架构的事实标准。

路由器是NoC的核心部件，而交换机制是决定路由器行为特征的最重要因素。虫孔交换和电路交换资源消耗较少，是NoC路由器最常采用的2种交换机制，而且各有优缺点。虫孔交换是一种无连接的交换方式，常与虚拟通道流控机制结合使用，链路利用率很高，但是支持虚拟通道的虫孔交换路由器不能保证报文切片连续到达。电路交换是一种面向连接的交换方式，链路建立后传输延迟确定，能够保证报文切片连续到达，但是链路利用率较低，并且建立和撤销链路的延迟不能忽视。

相比于支持虚拟通道的虫孔交换机制，电路交换较低的链路利用率影响了其在NoC中的使用。但是电路交换可保证报文切片连续到达，这对于大量、连续数据传输的强实时应用，以及具备向量计算能力的运算节点来说非常重要。

本文研究了不同通讯特征下，电路交换路由器和支持虚拟通道的虫孔交换路由器的通讯性能差异，并针对电路交换路由器链路利用率低的不足，提出虚拟电路机制，提高路由器通讯性能。

1 2种交换机制路由器分析

包连接电路（packet connected circuit，PCC）路由器是2003年瑞典林雪平大学SoCBUS项目提出的一种典型的电路交换路由器［6］。它使用携带路由信息的报文切片建立传输链路，以电路交换的方式传输数据，传输结束后撤销电路。虫孔交换路由器具有通道缓存，采用虫孔交换方式。针对通道缓存的管理和调度问题，研究者提出了多种不同结构的支持虚拟通道的虫孔交换路由器［7－9］。本文以基本结构支持虚拟通道的虫孔交换路由器（virtual channel router，VCR）为研究对象，其中虚拟通道数量和单个通道缓存深度均为4。

采用C＋＋语言分别建立PCC和VCR的周期精确2DMesh NoC仿真器，网络维度均为8×8。交通发生器（traffic generator，TG）产生随机分布通讯，分析不同注入率、不同报文长度（packet length，PL）下2种交换机制路由器的通讯性能。为保证仿真准确性warm－up周期数为4×107，随后开始统计。仿真总周期数为108。

不同PL下，VCR和PCC平均切片延迟随注入率变化曲线如图1所示。由图1可知，PL增加使VCR和PCC平均切片延迟逐渐逼近：PL＝16时，PCC平均切片延迟2倍于VCR；PL＝1 024且注入率小于0.1flit／（node×cycle）时，PCC平均切片延迟接近VCR。

图1 2种交换机制路由器通讯性能曲线

PCC平均延迟大幅降低的原因在于，一方面，PL增加，建链后传输的切片数量增加，建链的额外延迟占报文传输延迟的比重降低，平均切片延迟减少；另一方面，随着PL增加，统计周期内待传输报文的数量减小，拥塞次数降低，链路利用率提高，平均切片延迟减少。相比之下，VCR的虚拟通道机制能够有效地提高链路利用率，平均切片延迟始终维持在较低水平。

从VLSI实现角度分析，PCC不需要缓冲区，面积较小，0.18μm工艺下，5端口的PCC面积仅为0.06mm2；VCR需要缓冲区，面积较大，相同或更好工艺下，面积大于1mm2，VCR面积是PCC的十几倍。

综合考虑通讯性能和资源消耗，得出如下结论：电路交换路由器面积很小，PL较大（大于512）且注入率较低（小于0.1flit／（node×cycle））时，通讯性能可以接受，但PL较小（小于16）或注入率较高（大于0.15flit／（node×cycle））时通讯性能很差；支持虚拟通道的虫孔交换路由器面积较大，但通讯性能优异。

2 虚拟电路工作原理

2.1 动因

PCC传输报文需要4个阶段：① 带有路由信息的头切片由源节点发出，逐级经过路由到达目的节点；② 应答信号由目的节点发出，沿头切片经过的反向路径到达源节点，建链完毕；③ 体切片传输；④ 源节点撤销链路。建链过程中，PCC逐级锁定链路，一旦头切片拥塞，已锁定链路不能再由其他报文使用，造成链路闲置，降低链路使用率。本文定义这种现象为建链阻塞（setup link block，SLB）问题。

SLB问题实例如图2所示。报文A建链失败，头切片缓冲在路由器4中，持续请求south方向链路。由于报文A锁定路由器3和4间的链路，报文B的头切片不能使用该链路，使报文B建链失败，而报文A建链成功前，路由器3和4间的链路一直空闲。

图2 SLB问题实例

SLB问题类似于队列头（head－of－line，HoL）阻塞问题［10］。VCR的虚拟通道流控机制［11］有效地缓解了HoL问题。与虚拟通道思想类似，本文提出虚拟电路（virtual circuit，VC）缓解SLB问题。

2.2 工作原理

2项措施使VC能够缓解SLB问题：① 报文头切片不再锁定链路，而由应答信号Ack锁定；② 设置多个头切片寄存器并共享链路。VC缓解SLB问题的原理如图3、图4所示。

在图3中，报文A的头切片拥塞时，空闲的头切片寄存器可以缓存后继报文B的头切片，并且由于头切片不再锁定链路，路由器3与4间链路仍能使用，使路由器1～5中同时存在报文A和报文B建立的2条VC。图4中，报文B的头切片到达目的节点并触发应答信号Ack；Ack反向逐级锁定链路，报文B的VC成为传输链路，建链成功；同时，报文A的VC仍存在，头切片继续请求路由器4的south方向链路。

图3 报文A和B分别建立2条虚拟电路

图4 报文B的虚拟电路成为物理链路

多个端口同时收到Ack信号的情形如图5所示。

图5 多个端口同时收到Ack信号

设计确保公平性的轮转仲裁机制，决定可以继续锁定链路的Ack信号。仲裁失败的Ack信号被锁存，直到链路释放后进行下一次仲裁。

VC缓解了SLB问题，提高链路利用率，但SLB问题仍存在。支持VC后SLB问题的变化如图6所示。报文A和报文B的头切片共用路由器4与1间链路，分别建立VC并触发Ack信号。报文A的Ack信号经仲裁成功锁定路由器4与1间链路。报文B的Ack信号锁存在路由器1中，但也同时锁定了路由器1与2和路由器2与3间链路，造成2条链路闲置。此时，报文C的头切片只能缓存在路由器2中，持续请求east方向链路，造成新的SLB问题。

图6 支持虚拟电路后SLB问题的变化

3 实验与分析

3.1 通讯性能实验

下面仿真分析支持虚拟电路机制的包连接电路路由器（packet connected circuit router with virtual－circuit mechanism，VCPCC）的通讯性能。

采用C＋＋语言建立VCPCC的周期精确2D Mesh NoC仿真器，VCPCC的每个端口支持4条虚拟链路，其余实验条件和预加载通讯特征与前述相同。

对于不同PL，VCPCC、PCC和VCR 3种路由器的平均切片延迟随注入率变化曲线如图7所示。

图7 3种路由器通讯性能曲线

不同PL下，在注入率为0.15flit／（node×cycle）时，VCPCC平均切片延迟与PCC相比降低的比率见表1所列。平均来说，VCPCC平均切片延迟比PCC降低约26.3%。VCPCC和PCC饱和注入率分别在0.20flit／（node×cycle）和0.15flit／（node×cycle）左右。VCPCC饱和注入率比PCC提高约25.0%。

由前述分析可知，电路交换路由器急需提升短报文传输时的通讯性能。不同PL下，在注入率为0.15flit／（node×cycle）时，以平均切片延迟为指标，VCPCC和PCC分别达到VCR通讯性能的比率见表2所列。VCPCC的通讯性能已经全面接近VCR，即使对于短报文（PL＝16）传输，VCPCC的通讯性能也可以达到VCR的80.0%。

表1 VCPCC与PCC相比平均切片延迟降低比率

表2 VCPCC和PCC分别达到VCR通讯性能的比率 %

测试虚拟电路数目（VCLN）对VCPCC通讯性能的影响。实验中设置VCLN的值为2、4、8，PL＝512，其他测试条件不变。测试结果如图8所示。

图8 虚拟电路数目对通讯性能影响

对于短报文（PL＝16）传输，VCLN由2增至4时，VCPCC通讯性能改善较大，但VCLN继续增加后，VCPCC通讯性能改善有限；长报文（PL＝512）传输时，增大VCLN对VCPCC通讯性能改善不大。这是由于链路一旦锁定，后续的头切片即被阻塞，不能继续建立VC。考虑VC的资源开销，VCPCC中VCLN设置为2个较为适宜。

3.2 硬件综合结果

采用Verilog HDL语言实现5通道，单个通道包括2个VCLN，32bit位宽VCPCC的RTL建模，使用ModelSim仿真验证通过后，利用Xil－inx公司的ISE针对Virtex－6－550t器件完成逻辑综合。同时，完成了5通道，单个通道包括4个深度为4的虚拟通道，32bit位宽VCR，以及5通道、32bit位宽PCC的逻辑综合。VCPCC、PCC和VCR资源消耗对比见表3所列。

表3 VCPCC、PCC和VCR路由器资源消耗

VCPCC消耗的逻辑资源是PCC的3倍。VCPCC主要增加了VC控制逻辑、VC分配逻辑以及开关仲裁逻辑，这些逻辑主要由多路选择器和仲裁器组成。尽管VCPCC与PCC相比占用更多逻辑资源，但是VCPCC显著提升了电路交换路由器的通讯性能，并且在短报文传输时也表现良好，扩展了电路交换路由器的应用范围。

VCPCC仍然是一种电路交换路由器，不需要通道缓存。文献［12］研究表明，在70nm CMOS工艺下，典型通道缓存的漏电流功耗占路由器漏电流总功耗的70%，通道缓存面积超过路由器总面积的50%以上。通道缓存是路由器面积和功耗的主要来源。因此，与VCR相比，VCPCC在面积和功耗2个方面更具优势。

4 结 论

仿真实验表明，由于电路交换路由器的链路利用率很低，通讯性能较差，特别对于短报文传输，电路交换路由器的通讯性能极差，严重限制系统整体性能提升。针对该问题，提出支持虚拟电路机制的包连接电路路由器（VCPCC）。与一般的电路交换路由器（PCC）相比，VCPCC平均切片延迟降低约26.3%，饱和注入率提高约25.0%。更重要的是，对于短报文传输，VCPCC通讯性能可以达到VCR的80.0%，而PCC只能达到VCR的52.1%，这使得电路交换路由器基本满足短报文传输要求，应用范围更广，并能显著改善系统性能。在资源消耗方面，由于增加了虚拟电路，VCPCC消耗的逻辑资源是PCC的3倍，而由于VCPCC仍然是一种电路交换路由器，不需要通道缓存，因此在面积和功耗2个方面远小于支持虚拟通道的虫孔交换路由器（VCR）。

［1］ Guerrier P，Greiner A.A generic architecture for on－chip packet－switched interconnections［C］／／Proceedings of Design，Automation and Test in Europe，France，2000：250－256.

［2］ Benini L，De Micheli G.Networks on chip：a new SoC paradigm［J］.IEEE Computer，2002，35（1）：70－78.

［3］ 侯 宁，赵红梅，张多利，等.层次化架构嵌入式多核处理器原型设计及其编程研究［J］.合肥工业大学学报：自然科学版，2014，37（11）：1322－1327.

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

［5］ Pande P P，Grecu C，Jones M，et al.Performance evaluation and design trade－offs for network－on－chip interconnect architectures［J］.IEEE Transactions on Computers，2005，54（8）：1025－1040.

［6］ Wiklund D，Liu D.SoCBUS：switched network on chip for hard real time embedded systems［C］／／Proceedings of International Parallel and Distributed Processing Symposium，2003.doi：10.1109／IPDPS.2003.1213180.

［7］ Nicopoulos C A，Park D，Kim J.ViChaR：a dynamic virtual channel regulator for network－on－chip router［C］／／The 39th Annual IEEE／ACM International Symposium on Micro architecture，2006：333－346.

［8］ Lai Mingche，Wang Zhiying，Gao Lei，et al.A dynamically－allocated virtual channel architecture with congestion awareness for on－chip routers［C］／／Proceedings of 45th Conferences of Design Automation Conference （ACM／IEEE DAC），Anaheim，USA，2008：630－633.

［9］ 王 坚，李玉柏，蒋勇男.片上网络通信性能分析建模与缓存分配优化算法［J］.电子与信息学报，2009，31（5）：1059－1062.

［10］ Karol M J，Hluchyj M G，Morgan S P.Input versus output queueing on a space－division packet switch［J］.IEEE Transactions on Communications，1987，35 （12）：1347－1356.

［11］ Dally W J.Virtual channel flow control［J］.IEEE Transaction on Parallel and Distributed Systems，1992，3（2）：194－205.

［12］ Chen X，Peh L.Leakage power modeling and optimization in interconnection network［C］／／ACM Proceedings of International Symposium on Low Power Electronics and Design，2003：90－95.