标签：入门 NOC 算法 数据包 节点 路由 路由器

NOC入门

NOC应用背景

https://blog.csdn.net/hulizhuzhenming/article/details/86579695

介绍SOC总线架构的不足，引入NOC

NoC的主题思想是将宏观网络的通讯措施应用于芯片上，每个核当做一个独立的单元，IP核经过网络接口与特定的路由器相连。由此，将IP核之间的通信转换为路由器与路由器的通信。

NoC的基本组成为：IP核、路由器、网络适配器以及网络链路，IP核和路由器位于系统层，网络适配器位于网络适配层。针对NoC的这四个基本组成，也衍生出了许多的研究方向和优化途径。有效的IP核映射及拓扑结构，能够缩短路由跳数，减少通信量，避免数据拥塞。合理的缓冲分配、可靠的交换技术、高效的路由算法以及合理的功耗管理策略可以提高通信效率，降低整体功耗。

基本名词

• 节点度：一个节点与相邻节点连接链路的数目
• 网络直径：网络中任意两个节点之间的最短路径的长度的最大值，与网络的通信延迟成线性正比关系。
• 平均最短距离：网络中任意两个IP节点之间的最小距离的和与所包含的路径数之比
• 网络规模：网络中节点的数目
• 可扩展性：网络模块的可扩展能力，扩展必须伴随着所期望的性能按比例提高。

NOC拓扑结构

2Dmesh

特点

结构简单，易于实现，可扩展性好

此时性能取决于突触在NOC中的放置，NOC中心和NOC边缘的路由器功耗不同。

2D Torus

将2D mesh的每行首位连接，每列首尾也连接，使结构每个节点在几何上等价。

torus解决了mesh中路由器端口不对称的问题，平衡了NOC的流量，提高了NOC的吞吐量。但是torus在扩展时，用来首尾连接的链路会变长，增大延时，并且难以布置。

特点

缩短了节点间的平均距离，减少了网络直径，但同时可能会因为过长的环形链路而产生额外的延迟。

3Dmesh

将多个2Dmesh叠加起来，并对应节点连接起来

特点

进一步降低网络直径和平均距离，物理实现难度大

Octagon/Spidergon结构/ring

8边形结构，可包含8个IP核，每个节点连接相邻节点和对角节点。

去掉对角连接，即为ring结构。ring结构仲裁简单，开销小。但随着core的增加，跳数和延迟也会急剧增加，并且很难扩展。

可扩展为8个以上IP核，变为Spidergon结构

Cluster mesh

一个路由连接4个IP核，简化拓扑，但容易造成数据拥塞

Crossbar

适合小规模应用。一主多从，互连线复杂，对后端是很大挑战。

star

简单高效，适合模块数量较少情况。多核情况下，连接复杂，拓展困难。

树状结构

IP为叶子节点，路由器节点作为父节点，在父节点之上可以在增加父节点，层层相扣。降低了设计难度，也降低了物理设计的复杂度。

蝶状结构

NOC路由算法

在NoC的交换信息时，需要确定从源节点到目标节点所经过的路径，这时就需要路由算法来确定该路径。路由算法分为静态路由算法和动态路由算法两种。
静态路由算法对于两节点之间的路径是固定的，结构简单，便于硬件实现，也便于保持传输数据的顺序，所以在NoC系统中被广泛的使用。但是静态路由算法在路径发生拥塞时，无法进行调整传输路径，降低数据传输效率。
动态调度算法又被称为自适应路由算法，可以根据网络流量和链路负载的变化调整路径，动态选择路径进行通信，避免了高数据传输密度下的网络拥塞。但这种算法结构复杂，不便于实现，同时在低拥塞时电路开销大，而且会出现死锁（循环等待）问题。
合理路由的算法应该解决死锁、活锁和饥饿问题。

• 死锁是指两个以上数据包被阻塞在中间路由节点，对网络资源的释放和请求间出现循环等待的情况。
• 活锁是指一个数据包在其目的节点周围环绕传输，但无法到达目的节点。
• 饥饿是指当传输过程中存在多种不同优先级的数据包，可能出现高优先级的数据包始终占用资源，使低优先级数据包无法获得资源使用权，不能到达目的节点的情况。
• 死锁问题可以通过控制流量来解决，
• 活锁问题可以通过采用最短路径的方法解决
• 饥饿问题可以通过合理的资源分配策略解决

确定性XY路由算法

确定性XY路由算法是最简单的路由算法，该算法的路径取决于源节点和目标节点的地址，是一种静态的路由算法。以2D Mesh结构为例，数据首先在X方向传输，当数据到达目的节点的同一列时，沿Y方向传输，最后到达目的节点

如（1，2）传递到（3，4），那么其路径确定为

（1，2）→（2，2）→（3，2）→（3，3）→（3，4）

自适应维序路由

一般的维序路由是在维序路由中，每个数据包一次只在一个维上路由，当在这个维上到达了恰当的坐标之后，才按由低维到高维的顺序在另外的维上路由。

而这里带有一定自适应性的维序路由则是，当数据包沿某一维（如X方向），从最低维到最高维路由的过程中发生阻塞的时候，即向另一维（Y方向）发出传送请求，如果请求得到应答则向该方向传送数据，否则又转回X方向请求，如此循环，直到请求得到应答。同时规定，不允许数据向远离目的节点的方向运动，所以这种带有一定自适应性的维序路由也是没有死锁的。

下面以4×4的2DMesh网络中的带有一定自适应性的XY路由为例，具体解释一下这种算法的路由过程。

假设一个数据包路由的起点为（1,4），终点为（4,1）。如果按照一般的XY路由的话，它的路由路径应该是（1,4）→（2,4)一＞（3,4）一＞（4,4）一＞（4,3）一＞（4,2）一＞（4,1）。这时如果假设数据包在节点（3,4）发生了阻塞，不能继续向（4,4）发送。如果按照原来的XY路由，数据包就不能在往下发送，被阻塞在了（3，4）中。这时如果采用的是带有一定适应性的XY路由，在向节点（4,4)发送传送请求没有被允许之后，则它就会向Y维方向上的（3,3）节点发送传送请求，被允许之后，数据包就被发往节点（3,3）了。到达（3,3）后，又会先向X维方向上的（4,3)发送请求。就这样最终的路由路径为（1,4）一＞（2,4）一＞（3,4）一＞（3,3）一＞（4,3）一＞（4,2)一＞（4,1）。

odd_even路由算法

实用于mesh结构，对信号转弯位置提出约束。

• 奇数列转弯目的禁止向西
• 偶数起始方向禁止向东
• 禁止180°转向

这样可以避免两组数据到达同一个节点，发生死锁

DyAD路由算法

Odd_even和确定性路由算法相结合。

在网络处于低负载情况下采用确定性路由算法，而当网络处于高负载时，采用odd_even自适应路由算法。路由器的每个输入端都在监控各自的信道占用率。当信道占用率超过拥塞阈值，拥塞标志位变为1，否则为0。如果标志位为1，路由器的工作模式变为odd_even路由模式。这种算法在网络低负载情况下拥有较好的时延和吞吐性能，并且在网络拥塞情况下具有较高的吞吐量。

DyXY路由算法

核心思想，通过监视其相邻节点的拥塞状况来决定路由路径的下一条。这种算法将路由器每个端口的即时队列长度作为压力值，然后用压力值来表征相邻节点的拥塞状况。算法规定数据采用最短路径进行传输，如果存在多条最短路径，则选择拥塞压力最小的一条路径。
每个路由器时刻更新所保存的相邻节点的即时压力值，在确定源节点和目的节点之后，数据沿压力值最小的一条路径传输。这也是自适应算法最基本的思路，由于节点数据实时更新，所以可能会出现死锁或活锁的情况。
在实际应用中，还需要根据特定的NoC结构来选择适合的路由算法

NOC实现

感知网络

论文参考：Link-Sharing: Regional Congestion Aware Routing in 2D NoC by Propagating Congestion Information on Idle Links

router

router设计

文献：基于拥塞超强感知的NOC路由器设计

低功耗router设计

包含五个输入通道、一个仲裁器、一个交叉开关，每个输入通道和仲裁器都包含时钟门控。

FIFO越深，可以使NOC延迟越小，但也会带来更大的面积和功耗，因此FIFO深度需要谨慎选择。图中FIFO深度选择为4.

其中arbiter时钟频率是接口时钟频率的两倍，通过握手来保证全局异步，局部同步。

文献：A Low Power and Low Area Router With Congestion-Aware Routing Algorithm for Spiking Neural Network Hardware Implementations

其他

文献：Design alternatives of Network-on-Chip (NoC) Router microarchitecture for future Communication System

a架构

这种结构对于构建大容量的交换结构十分经济，可扩展性好，但是当不同的输入端口的缓存队列都有微片要传递到同一个输出端口时，在一个时间段内，这种交换结构只允许一个被调度输出，另外的会处于阻塞状态。

b架构

缓存队列放置在输出端口的交换结构。数据到达输入端口先通过交叉开关传输到相应的输出端口的缓存队列中进行排队，即缓存功能在交叉开关传输之后。这种结构避免了由交换开关内部冲突引发的延迟，可以方便地提供吞吐量、速率以及时延等方面的服务质量保障，但是要求交叉开关具有很高的传输带宽，如果出现N个输入端口同时竞争同一个输出端口时，输出缓存需要一次性完成N次写入，交叉开关内部就需要一个加速比为N的交换结构，因此，这种结构复杂且不易扩展。

c架构

最后显示的是在交叉开关的输入和输出端口都具有缓存队列的结构。该结构是上述两种结构的一种折衷，通过适当的加速，可以避免交换开关拥塞引发的延迟，但是调度过程中需要同时考虑输入调度与输出调度，而且新加的缓存增加了路由器资源，因此该结构过于复杂。

NOC功耗控制

当并非所有core都处于活动状态时，可以主动对所在路由进行电源门控，降低静态功耗。但随着更多的路由断电，数据包被迫多走弯路，会导致更多的跳数，使动态功耗增加。所以应在静态功耗和动态功耗之间寻找平衡点，实现功耗优化。

交换技术

存储转发

路由器提供存储空间，在接收到整个数据包后，再将其转发出去，延迟较大，而且对缓存需求大。

虚拟通道

在下级路由空闲时，当前路由接收到包头就进行转发，无需等待整个包到达。但如果下级路由阻塞，此时就会跟存储转发一样，需要整个包进行缓存。

虫洞技术

将包切割，head flits带有数据包的目的地址和控制信息，body flits包含要传输的数据，tail flits包含结束信息。

路由器收到head flits时，路由器根据其中的信息计算出输出端口，在空闲时进行转发。后边的body flits和tail flits按着head flits走过的轨迹进行传输。当head flits被阻塞时，后边数据也被阻塞，分别缓存在相邻的几个路由器中。

这种分段传输，降低了对缓存的需求，但容易造成链路阻塞，出现死锁。

标签：入门,NOC,算法,数据包,节点,路由,路由器
From： https://www.cnblogs.com/icwangpu/p/16993740.html