01
—
背景
NoC（Network on Chip）片上网络，目的是为片上系统SoC提供高效通信方式。SoC的通信一般基于总线BUS结构，但随着芯片内部集成IP数量和种类越来越多，此时各处理器（包括同构或异构处理器内核）和IP之间的互联成为了SoC综合性能的关键。
一般来说，核数小于等于8个的处理器被称为多核处理器，具有更多核数的处理器被称为众核处理器。高效众核处理器的SoC设计面临着三个关键挑战：
并行编程模式层：通常应用程序开发者希望使用隐藏硬件实现的编程模式，即软件开发不依赖底层硬件实现细节，从而降低编程难度并提高程序可移植性；而体系结构设计者希望使用感知硬件特色的编程模式，这样能够有效利用底层硬件特色提升性能。
片上网络互连层：传统的总线BUS和交叉开关等结构存在可扩展性差、带宽较低、延迟较大、功耗较高等缺陷。NoC将报文交换思想引入芯片内部通信机制，现已成为众核处理器事实上的片上通信标准。
逻辑电路实现层：功耗过大。需要底层路由器，网络上缓存和拓扑进行高效的低功耗设计和实现。
综上，NoC的设计包括了从底层路由器和拓扑结构的逻辑实现，到网络层路由和流控机制设计，再到片上网络与高层编程模型的协同优化。实际上，NoC研究的就是各种互联结构，及对应的路由、流控或调度算法，并将他们与上层编程和下层实现结合起来。
02
—
拓扑结构
拓扑结构对网络整体性能和开销有至关重要的影响。它决定了网络节点和链路的物理分布及他们之间的连接关系；决定了传输跳数和每跳链路长度，影响到延迟和功耗；决定了节点之间的可用传输路径条数，影响到流量和带宽。
拓扑结构应该能较好的映射到二维集成电路表面，目前有三种典型拓扑结构，前文有过介绍：
环网结构简单，易于实现路由和流控机制；但平均跳数高且可扩展性差。
可以通过配置多个环网缓解这些局限。
网格网络更易避免死锁；但中间区域易饱和成为系统瓶颈。
可以设计非对称拓扑结构，给中间区域更多的连线资源。
环网（Ring）
网格（Mesh）
Torus
Torus网络有利于均衡网络利用率，降低网络跳数和延迟；但死锁机制更为复杂。
拓扑结构的研究主要聚焦在以下几个方面：
降低报文传输延迟：
可以在一个路由器上聚集多个处理核；该方法缺点会增加路由器端口数，提高实现复杂度；
可以在非邻居节点间添加物理快速链路；缺点一样会增加路由器端口数，提高实现复杂度；
使用片外扁平蝴蝶网络（Flattened Butterfly）：在每个维度上采用全相连结构，缺点为长链路会增加流控机制复杂度;
提高网络饱和吞吐率：
使用异构Mesh网络：给易堵塞的中间区域路由配置更宽链路；
使用混合网络：局部通信使用Ring网络，全局通信使用Mesh网络；
自适应调整链路方向或带宽；
降低网络面积和功耗
03
—
路由算法
一旦确定了片上网络的拓扑结构，路由算法负责为报文计算源节点到目的节点之间的传输路径。路由算法有很多分类标准：
基于传输路径长度，可分为：
最短路由：源节点和目的节点之间的最短传输路径；
非最短路由：例如Valiant算法，先将报文传输到随机选择的中间节点上，之后再从这个中间节点传输到目的节点；
基于传输路径条数，可分为：
确定性路由：源节点和目的节点之间只提供一条传输路径，例如XY维序路由算法；先沿X方向传输到目的节点X位置，再沿Y方向传输到目的节点；
非确定性路由：提供多条传输路径，基于是否考虑网络状态，可以分为：
非感知路由：例如O1Turn算法，XY维序路由和YX维序路由路径中随机选择一条；
自适应路由：计算传输路径时考虑网络状态，如果监测到节点拥塞会选择其他网络节点传输。自适应路由也可分为：
部分自适应路由：通过限制报文传输的部分转向避免死锁；
完全自适应路由：允许报文使用源节点和目的节点之间的所有传输路径。
支持较高网络性能要求路由算法提供较高的路径多样性，同时能有效避免网络拥塞。完全自适应路由算法允许报文使用最短路径，且路径多样性高于部分自适应路由算法和确定性路由算法，因此，算法优化大多在完全自适应路由基础上展开研究：
DyAD算法：根据网络负载动态调整采用确定性路由算法或自适应路由算法；
DyXY算法：使用专用线路传输邻居路由器状态，根据网络拥塞状态沿着X或Y维度发送报文；
NoP算法(Neighbors on Path)：使用边带网络传输两跳之外节点的状态，基于邻居节点的相邻节点的状态选择输出端口；
RCA算法(Regional Congestion Awareness)：使用边带网络传输网络拥塞信息，基于同一行或列的所有路由器状态选择输出端口；
超前路由和端口预选择：在上一跳路由器计算本级路由器的可能输出端口，在报文到达前一个时钟周期选择一个合适的输出端口。
04
—
流控机制
流控机制为报文分配网络资源，包括链路带宽、路由器缓存和控制状态等，目前有3种主要的流控方式：
存储转发：接收到一个完整报文之后才申请下一跳路由器的缓存和链路；
虚切通：下游路由器空闲缓存能容纳整个报文时，向下游路由器发送头切片（以报文为粒度）；
虫孔交换：下游路由器有空闲时，向下游路由器发送切片（以切片为粒度），链路空闲时也不能被其他报文使用；
虚通道：独立控制的先进先出缓存队列，链路空闲时允许后续报文越过当前被阻塞的报文，提高物理链路利用率；
流控机制的研究主要聚焦在以下几个方面：
降低硬件开销：
BLESS无缓存流控：以切片为粒度路由，多个切片竞争端口时只有一个切片能获得端口授权，其他切片将进行错误路由；
SCARAB流控：多个切片竞争端口时只有一个切片能获得端口授权，其他切片将被丢弃，同时返回一个NACK消息通知源节点重新发送切片；
自适应流控：根据网络状态动态使用无缓存流控或有缓存流控，具有较低负载的路由器关闭缓存电源，可以降低功耗；
MinBD：在基准无缓存路由器上增加一个旁路缓存，可以提高网络饱和吞吐率；
降低报文传输延迟：
快速虚通道设计：预先分配多个路由器上的缓存资源；
令牌流控机制：将路由器的缓存占用状态广播给邻近路由器，使报文可以旁路掉多个路由器的流水段；
层次交换设计：将长报文划分成多个切片组，在一个切片组内维持交叉开关分配结果，即维持当前端口输入输出的配对；
虫孔切通交换机制：允许多个报文以切片为粒度混合存储在一条虚通道内部；
消除网络中的死锁：
气泡流控：限制占用最后一个报文大小的空间缓存单元以消除网络死锁；
关键气泡：将环网中的一个气泡标志为关键气泡，并限制关键气泡只能被已处于环网中的报文占用，从而避免网络死锁；
虫孔气泡：将气泡流控的设计思想扩展到虫孔交换网络，使用三种不同颜色标识缓存使用状态，并在环网中剩余一个切片大小的空闲缓存单元；
预防流控：优先级仲裁将已注入的报文赋予更高优先级；预防槽旋转机制在环网中保持一个报文大小的空闲缓存单元。
05
—
总结
本文介绍了NoC的基本概念和相关研究方向，包括了拓扑结构，路由算法和流控机制三个方面。没有完美的算法，工程师应该了解各种方法的设计思想和优缺点并在实际设计中加以均衡。例如我们前面所介绍的Cache一致性的片上网络中，路由器是基于报文是单切片报文这一特性所设计的，不需要缓存和保序，可以显著降低电路功耗和缓存面积。