浅谈NoC

又到五一劳动节，谨以此文献给天朝的IC打工人，祝ICer们节日快乐！

老夫聊发少年狂，左牵黄，右擎苍，锦帽貂裘，千骑卷平冈。

为报倾城随太守，亲射虎，看孙郎。

酒酣胸胆尚开张，鬓微霜，又何妨？

持节云中，何日遣冯唐？

会挽雕弓如满月，西北望，射天狼。

扯远了，回到正题。随着近些年SoC的设计规模越来越大，片上网络（NoC，Network on Chip）逐渐被大家关注。

今天简单聊聊关于NoC的几个重要话题：

拓扑（topology），即如何连接每个节点
路由（routing），即数据如何在节点之间的传递路径
流量控制（flow control），即如何控制数据在源节点和目的节点传递
微架构（microarchitecture），即路由器的架构设计

其它的一些，比如死锁/服务质量（QoS）等，包含在以上的话题中探讨。

拓扑

片上网络的拓扑结构决定了互连网络中节点和通道之间的连接和布局。因此，拓扑结构对于互连网络的延迟和吞吐率影响很大。另外，拓扑结构直接决定了逻辑设计和物理实现的难度。

总线和交叉开关是比较简单的拓扑。但是这两种拓扑结构的可扩展性（scalability）有限，因此只适用于设计规模不大的SoC。

对于大规模的SoC设计，往往采用的是交换拓扑（switched topology）。在交换拓扑中，组件通过路由器和链路进行连接。从一个节点路由至下一个节点被称为一“跳（hop）”。从消息的源节点到目的节点需要的跳的总次数被称为"跳数"。

当前，在SoC设计中比较常见的NoC拓扑结构有ring，mesh，torus等，如下图所示。这些拓扑结构属于直连拓扑，即每个终端节点都与一个路由器连接，所有路由器既是网络流量的产生和汇入端，又是流量的中转站。

拓扑的选择非常重要，它决定了互连网络的时延，带宽，成本等特性。衡量NoC拓扑结构有几个指标：

节点度（degree）：节点度表示每个节点拥有的链路数量。节点度是一个可以有效衡量网络开销的指标，节点度越大，则节点路由器的端口越多。比如上图中，ring结构中的每个节点都有两条链路以连接左右相邻的两个节点，所以ring结构的节点度是2；mesh结构中每个节点的度是不同的，中间节点的度是4，四个顶点节点的度是2，而其它边沿节点的度是3；torus结构中的每个节点有四条链路以链接相邻的四个节点，所以torus结构的节点度是4。
网络直径（diameter）：网络直径指的是任意两个节点之间的最短路径组成的集合中的最大值，也就是源节点到目的节点的最短路径中的最大跳数值。在没有链路竞争的前提下，网络直径可以作为衡量拓扑中最大延迟的指标。比如上图中，ring结构的网络直径为5；mesh结构的网络直径为6；torus的网络直径为4。
对分带宽（bisection bandwidth）：对分带宽是指将网络划分为两个相同部分后，两部分之间的通信带宽。对分带宽限制了系统从一端移动到另一端的总数据量，因此可以有效的反应网络在最坏工作情况下的性能。比如上图中，ring结构的对分带宽是2；mesh结构的对分带宽是4；torus的对分带宽是8。
平局距离（average distance）：平局距离通过将所有节点对之间的距离之和除以节点对的数量来计算。平局距离可以衡量任意两个节点间的期望距离。比如上图中，假设路由采用最短路径，ring结构的平局距离是10/4；mesh结构的平局距离是8/3；torus结构的平局距离是8/4。

除去上述的三种拓扑结构，还有几种NoC拓扑，如butterfly，fat tree等，如下图。这几种拓扑结构属于非直连拓扑。在非直连拓扑中，节点分为终端节点和交换节点，终端节点是流量的源或目的地，交换节点只是流量的中转站，也就是说终端节点和交换节点是分离的，这与直连拓扑不同。

以上介绍的都是规则拓扑，对应的还有不规则拓扑。比如在一些异构计算SoC中会有多种不同的处理器类型，这时候NoC拓扑结构就需要做针对性的优化。

路由

在片上网络中，节点间的数据传输通常采用分组转发的方式。

在给定网络拓扑的情况下，路由算法决定分组从一个节点行进到另一个节点的路径。确定路由算法时要考虑几个方面：一是路径多样性，路径多样性提高了对非正常流量状况的恢复能力，带来更高的网络带宽利用率；二是确保没有死锁。

在ring拓扑中，分组只能根据最短路径，向左或向右行进，也就是说ring拓扑没有路径多样性。

在mesh拓扑中，一种当前流行的路由算法是“维度序（dimension-ordered）”路由，它要求分组再进入下一个维度前完成再上一个维度的传输。比如，可以要求分组必须先沿着X轴方向（向西或向东）行进，然后才能沿着Y轴方向（向南或向北）行进，并且一旦开始向南或向北行进以后就不可以返回到向西或向东行进了，也称为X-Y序，相反的还有Y-X序。以下图为例，源节点是节点00，目的节点是22，则消息的路径必须为00->10->20->21->22，即图中的红色箭头所指示；如果源节点是31，目的节点是13，则路径为绿色箭头所指示。

可以看出，维度序路由损失了路径多样性。在mesh拓扑中，维度序是最小的和确定性的路由算法，易于实现。维度序的缺点是其确定性可能会导致某些端口的争用；另一个缺点是某些端口的利用率比其他端口高，从而导致端口和链路资源的利用率不均衡；第三个缺点是容错能力不足，如果发生端口或链路故障，整个系统可能会停滞。维度序的一个优点是天然的会限制Y维度到X维度的所有转向，一次不会产生死锁。

有多种方法可以改善维度序路由的路径多样性。

01-turn路由，在两个维度序的路由算法中随机选择一个：X-Y序或Y-X序。

勇士路由（valiant routing）是对维度序路由的一种改进，发送端首先使用维度序路由将分组发送到随机选择的中间节点，然后从中间节点再次使用维度序路由将分组发送到目标节点。勇士路由算法提供了路径多样性，因为中间节点是随机选择的。但是勇士路由可能是非最小的，则取决于中间结点的选择。如果期望最小路由，可以将中间节点限制到能保证最小路由的节点，但是代价是损失了路径多样性。

在mesh拓扑中，也可以使用自适应路由，分组可以绕过拥塞进行路由。自适应路由的目标是减少出现非正常流量模式的概率。自适应路由一般不依赖于网络的全局状态，而是倾向于考虑局部信息，通常是下一个路由器的缓冲区占用率。但是，适应局部信息并不能保证自适应的高效，可能会产生“活锁（live lock）”，可以通过限制分组转向次数来避免活锁的产生。参考下图，从源节点31到目的节点13，其中节点12与节点13之间和节点22与节点32之间发生了拥塞。分组数据将会在节点11/12/22/21之间循环，即产生活锁。

另外，实现自适应路由需要路由器具有可编程性，这就需要在路由器中添加路由表，并基于目的节点查表。实现方式可以有多种。可以是源节点中的路由表决定了整个路由路径；也可以是每个中间节点的路由表指示去往目的节点的下一个端口信息，整个路径选择是沿着路径中的每个路由器做出的。自适应路由能够提供更多的路径多样性，且可以周期性的更新路由表以适应网络流量变化。但是路由器的逻辑设计难度会加大。

Torus拓扑与mesh很相近，不再多说。

简单分析完路由算法在路径多样性上的考量，我们再来看看“死锁（dead lock）”问题。片上网络的死锁有很多种，比如有协议级死锁，路由死锁等。我们这里只分析路由死锁。

片上网络中的路由死锁指的是分组停滞，即无法在一组链路上继续发送分组。路由死锁产生的原因是输入端口的缓冲区容量有限，同时缓冲区空间的获取存在着循环依赖关系。如下图所示，四个路由器的输入缓冲区全部被占满，无法接收相连路由器的分组消息，死锁发生。

死锁对片上网络来说是致命的，在没有死锁恢复机制的情况下，会直接导致片上网络瘫痪。可以通过超时检测和重新发送的机制来打破死锁，但是这治标不治本。

如果能够通过路由算法消除死锁，可能会是更好的选择。早在多年前，就有人通过“通道依赖关系图（channel dependency graph，CDG）”给出了理论指导。整个CDG的推导挺麻烦的，感兴趣的同学可自行学习，我们只记住结论就好：对于给定的互连网络和路由算法，死锁不会发生的充分必要条件是其CDG中没有环（cycle）出现。因此，片上网络的架构设计师需要通过路由算法来规避路由死锁。

如果对mesh中的路由转向不加以限制，必然会形成CDG环，只有通过加以限制来打破CDG环才能避免死锁。转向限制路由算法是一种较为流行的应用于mesh拓扑的技术。维度序（X-Y序）路由限制了Y维度到X维度的所有转向，也就是说维度序路由限制了所有8个转向中的4个（X向路由转到Y向路由以后不能再转回到X向），仅保留4个转向是合法的，因此维度序路由可以避免死锁。

下图展示了三种无死锁的转向模型路由算法。在西向优先算法中，限制先北后西转向的同时，限制先南后西，也就是说分组必须先向西行进；在北向最后算法中，限制先北后西转向的同时，限制先北后东，也就是说一旦分组向北行进，就只能继续向北，不能再转向东或西；在负向优先算法中，禁止所有从正向到负向的转向（先北后西和先东后南）。

转向限制路由算法不仅提高了路径多样性，还允许两个节点间的非最小路径，也就说分组可以绕过故障链路或者拥塞链路。

除了路由算法，还可以在另外一个维度上解决死锁问题，想办法在死锁发生后及时处理。一种解决方案是冗余通道，在路由器中添加冗余通道，在正常情况下不适用冗余通道。一旦发生了死锁，利用冗余通道“逃生”。实现冗余通道的代价是成本增高，因为需要实现双倍的链路和缓冲区。一个折中的办法是仅实现多路缓冲区作为多个信道，这些信道分时复用同一个链路。这样做是基于一个事实，路由死锁发生是因为路由器输入端口的缓冲区容量有限，同时缓冲区空间的获取存在着循环依赖关系，而此时链路是空闲的。这些信道被称为“虚拟通道（virtual channel）”。下图是虚拟通道的示例，路由器有两个通道VC1和VC2，其中VC1用于常规路由，VC2用作逃生通道（escape channel）。当分组被阻塞时，将分组从VC1转移到VC2。需要注意的是，必须利用一定的机制确保逃生通道不能出现死锁。

流量控制

考虑到数据传输将通过不止一条链路时，有两种网络交换策略。一种是电路交换（circuit switching），另一种是分组交换（packet switching）。电路交换是在传送数据前，发送端首先发送命令以建立到接收端的连接，传输路径上的路由器将为消息传输预留适当的输入和输出端口以及端口之间的连接。电路交换的优势是：连接建立后，消息传送速度非常快。电路交换的劣势是：第一，由于建立连接导致的延迟；第二，一旦连接建立，如果不立即使用，会使连接的利用率下降；第三，如果新的连接与已有的连接冲突，需要等已有连接释放，这会导致其他通信或连接的延迟。因此，电路交换并不适合超大规模SoC设计。

下图是一个电路交换的示例，数据从节点0传输到节点8，其电路交换的路径是0->1->2->5->8。S表示电路建立请求；A表示电路建立确认；D表示有效数据。从图中可以看出，需要经过若干cycle才能真正传输有效数据，而且整条路径的利用率偏低（灰色区域代表当前节点此刻空闲）。

分组交换是将信道上的消息拆分成组，并通过路由策略选择传输路径，一级一级的把数据从源节点传输到目的节点。分组交换的优劣势和电路交换正好相反。分组交换不需要建立和释放链路，在数据传输过程中可以动态分配带宽，因此信道的利用率高，吞吐量高。分组交换的缺点是在节点中需要实现缓冲区（buffer），这会增加芯片的面积和功耗，从而提高芯片成本。另外，如果路由策略设计不当，可能会造成拥塞（congestion）和死锁的问题。在实际芯片的NoC设计中，往往采用分组交换。

在分组交换中，节点间的一次基本通信单位被称为“消息（message）”，一个message可以由多个“包（packet）”组成。Packet是节点间的基本路由单位，一个packet可以由多个flit（flow control unit）组成。通常，flit是链路级流量控制的基本数据单位，一个flit可以由一个或多个phit（physical unit）组成。在一个时钟周期内可以传输的基本数据单位被称为Phit，通常情况phit由链路的宽度确定。

以上的数据分组关系会使NoC的逻辑设计非常复杂，因此在实际设计中通常会加以约束，比如一个message只包含一个packet，或者一个packet只包含一个flit，或者一个flit只包含一个phit等。

刚刚提到过，分组交换的节点中需要实现缓冲区。根据缓冲策略的不同，可以分为：

存储-转发（store and forward）：分组必须由一个节点完全接收并存储，才能向下一个节点转发。对于存储-转发策略，流量控制基于packet的，而不是flit
直通（cut-through）：允许在分组完全到达当前路由器之前，就可以将分组的一部分转发到下一个节点，流量控制基于packet
虫洞（wormhole）：与直通类似，不同的是流量控制基于flit
虚拟通道（virtual channel）：在接收端实现多个输入队列，即虚拟通道。多个虚拟通道通过时分复用的方式共享两个路由器之间的链路。

下图是存储-转发的示例，数据仍然是从节点0向节点8传输。H表示“头”分组；B表示“体”分组；T表示“尾”分组。

下图是直通的示例，与存储-转发不同的是，节点不需要完全接收上一个节点的分组数据。

下图是虚拟通道的示例，节点的输入端有两个队列，输出链路的效率从而提高。

虚拟通道主要是为了避免死锁而提出的，但同时也能缓解流量控制中的"队首阻塞（head-of-line blocking）"。本质上，每一个虚拟通道都是路由器中的一个独立物理队列。从这一点来说，与PCIe中的虚拟通道倒是很相似。

分组交换的流量控制机制工作在链路级。需要节点间通过一定的机制来保证分组的正确传输。当接收端的缓冲区填满，必须通过反压（backpressure）机制来阻止发送端继续发送分组，反压的粒度取决于具体的流量控制协议。

典型的链路及流量控制可以使用stop/go协议，也有的文献称为on/off协议。接收端通过stop/go信号来将其输入缓冲区的状态通知给发送端。如果接收端的输入缓冲区已被占满，则发送端停止发送flit。

基于信用（credit-based）的流量控制是stop/go流量控制的一种替代机制。接收端提前将输入缓冲区能存储的flit数量，即信用值，告知发送端；发送端保存该信用值，每发送一个flit，信用值减1，当信用值为0则停止发送，等待接收端更新信用值。

路由器微架构

在前面分析过拓扑，路由算法，流量控制后，我们来看看如何实现一个路由器。

在flit到达路由器的输入端口后，首先要将flit保存到输入缓冲区；然后对头部flit进行解码得到虚拟通道的编号和输出端口；基于计算出的输出，对输出虚拟通道提出请求；由于是路由器是多输入多输出，需要全局仲裁器进行竞争仲裁，一旦仲裁完成，将flit从某个输入端口缓冲区转移到某个输出端口缓冲区。

下图是一个节点度是5的路由器，有5个输入端口和5个输出端口，分别对应东/南/西/北的路由接口和功能模块接口。

该路由器的主要逻辑模块有：

输入缓冲区单元，主要作用是接收相邻节点的分组消息，其本质上就是一个FIFO。如果支持虚拟通道，则需要实现多组队列
输出缓冲区单元，主要作用是将分组消息发送给相邻节点。对于直通路由，分组的flit可以直接输出，不需要缓冲区；对于虫洞路由，流量控制是以flit为单位，需要实现输出缓冲区，以便下游路由器的输入缓冲区可用之前暂时缓冲几个flit
交叉开关单元，将数据从输入端口转移至输出端口，这部分会占用大量的布线资源
路由计算单元，负责解码flit中的路由信息，以决定flit的输出端口
虚拟通道分配器，负责输出虚拟通道的竞争问题
开关分配器，保证交叉开关端口连接到输入虚拟通道

实际设计中，路由器可以支持连接多个的功能IP接口。比如arm的CMN，采用mesh拓扑结构，其路由器有六个输入/输出端口，可以连接相邻的四个路由器和两个IP；对于边上和顶角的路由器则不需要连接四个路由器，多出来的接口可以连接更多的IP。

为了加速路由器的处理速度，通常路由器的逻辑设计采用流水线的方式，这一点与处理器的设计相似。典型的路由器流水线分为几级：

缓冲区写入（Buffer Write，BW）级：输入flit被存入缓冲区
路由计算（Route Computation，RC）级：路由计算模块解析头部flit得到输出端口信息
虚拟通道分配（Virtual-channel Allocation，VA）级：虚拟通道分配器为flit分配出虚拟通道
开关分配（Switch Allocation）级：开关分配器接受来自全部输入端口的虚拟通道的请求，如果存在竞争则对请求进行仲裁，批准一个输入虚拟通道与输出虚拟通道相连接；如果不存在竞争，则可以直接批准
开关传输（Switch Traversal，ST）级：按照指定的路线配置交叉开关传输，flit从输入端口的虚拟通道中读出，送入输出端口
链路传输（Link Traversal，LT）级：flit从当前路由器的输出端口传输到下一跳路由器的输入端口

以上过程是头部flit在路由器中的传输过程。对于非头部flit，不需要路由计算，并且要沿用头部flit的虚拟通道，所以可以省去了RC和VA两步。关于路由器流水线的优化，有大量文章可以参考。

除去逻辑设计复杂，路由器实现的另一大难点是功耗控制。在大规模SoC设计中，NoC功耗占比可能在10-30%，甚至更高。为了实现大吞吐量，直观的做法是提高时钟频率（在物理设计能够满足时序的前提下），但这无疑会带来动态功耗的线型增长。一个解决办法是在满足性能的前提下，路由器中的每个功能模块工作在不同的频率下，代价是进一步增加了逻辑设计的复杂度，因此在实际应用中很少使用这种方法。一个可行的解决办法是动态调压调频（DVFS），通过一些机制检测NoC整体的工作状况，当NoC空闲或者负载较低时，向下调节时钟频率，甚至调低供电电压。DVFS的基本概念可以参考这篇《SoC设计之功耗 -- DVFS》。但是，这种技术也有一定的局限性，首先电压调节可能延迟较大，因此对于网络流量突然变大的情况处理不够及时；其次某些SoC中，NoC整体空闲的情况可能很少发生。还有一种技术，“路由器停车（router parking）”，当与路由器连接的IP处于断电状态时，则可以将该路由器的供电切断。这种技术其实改变了NoC的拓扑结构，需要NoC支持自适应路由，以确保其它正常工作的路由器节点之间传输分组消息，不会发生死锁。

服务质量（QoS）也是NoC设计中要考虑的一个问题。不同的功能IP对于吞吐率和时延的要求不一样，可以在分组消息中加上QoS信息，这样在虚拟通道分配器和开关分配器中根据QoS策略实现基于优先级的仲裁。

今天就到这里吧，都是一些NoC的基础知识。后面有时间再写写当前主流商业NoC IP产品。

作者：老秦谈芯
文章来源：老秦谈芯

推荐阅读

更多IC设计干货请关注IC设计专栏。欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。

拓扑

路由

流量控制

路由器微架构

推荐阅读

目录