柚子快报激活码778899分享：片上网络NoC
本文大部分内容来源于参考文献内容以及互联网，部分内容是本人理解所得，若有不当之处请指教
一、概述
随着MPSoC（multi-processor System-on-chip）的发展，片上核的数量越来越多，片上互联架构从总线结构逐渐演变为更加复杂的网络拓扑，片上网络（Network on chip，NoC）的概念也随之出现，众核处理器中各节点通过某种互联拓扑构成的网络系统即为片上系统。
片上网络的思想
芯片的片上网络和数据中的网络有一定的相似性，其将报文交换的思想引入芯片内部通信机制中；尽管如此，但二者在延迟、功耗和面积等方面有本质区别。
片上网络要与计算核一起竞争芯片宝贵的功耗和面积资源。为了在有限的功耗和面积开销下获得较高的性能，设计者更应关注片上网络的优化，包括底层逻辑实现的优化，网络层路由和流控的优化，以及面向高层编程模式的优化。
片上网络解决的问题
1）如何设计网络拓扑将一定数量的设备互联起来
2）如何保证网络通信的正确性
考虑的方向包括路由算法，路由器结构的设计避免死锁，解决活锁、饥饿、拥塞等问题； 计算节点间cache一致性问题
3）如何保证系统的设计指标
包括算力、访存延迟、访存带宽、芯片面积、功耗等。 如果在有限的面积和功耗要求下，权衡各种设计要素，以此达到目标算力，符合访存延迟和带宽。
片上网络的设计空间
片上网络的设计空间包括拓扑结构、路由算法、流控机制和路由器结构的设计。
拓扑结构
拓扑结构决定了网络节点和链路的物理分布以及它们之间的连接关系，也决定了消息的传输跳数和每跳链路长度，因此拓扑结构对延迟和功耗影响很大；同时由于拓扑结构决定了节点之间的可用传输路径条数，因此还影响了网络流量的分布，以及网络带宽和传输性能。
路由算法
一旦确定了片上网络的拓扑结构，路由算法便负责为报文计算源节点到目的节点之间的传输路径。好的路由算法有更高的饱和吞吐率，可以降低报文传输延迟，实现全局负载均衡和网络容错，在一定程度上可以避免网络拥塞和死锁。
路由算法可以根据传输路径长度分为最短路由和非最短路由，也可以根据路径条数分为确定性路由算法和非确定性路由算法，非确定性路由算法又可以根据是否考虑网络状态分为非感知路由算法和自适应路由算法。
流控机制
流控为报文分配网络资源，包括链路带宽、路由器缓存和控制状态
网络节点路由器设计
链路架构
二、NoC拓扑结构
三、NoC路由算法
虫孔路由
虫孔路由利用流水线思想将一个要传送的报文划分为多个大小相等的消息微片（即flit），并在网络上进行传输。这些flit是消息传输的最小逻辑单元。
偏转路由
供基于封包交换的网络使用的路由策略。 定义：每个数据包都有自己的首选输出口离开路由，若同时有两个或以上数据包于同一个输出口离开，偏转路由会确保仅有一个数据包被路由到指定的链路上，而其他的数据包则会被路由到非最短路由的通路上。
产生的原因：
普遍存在的微秒级拥塞整体网络利用率较低router的缓冲区较小
偏转路由主要存在以下几个方面的问题：
随着偏转网络负载的增加，偏转路由的作用快速下降。 一方面，丢包是网络拥塞的主要信息之一，许多拥塞控制算法都依赖于此，阻止路由器进行丢包推迟了此信息到达终端的时间。另一方面，路由偏转本身会造成网络利用率的进一步升高，从而加剧网络拥塞。路由偏转会导致小流（mice flows）的延迟增加。阻止丢包还会导致大流的传输窗口持续增长，这些大流的突发行为会导致小流的队头阻塞。路由偏转导致大量的数据包失序。由于进行了偏转，同一条流不同数据包的传输路径是不确定的，这大大增加数据包失序的现象。即使网络在轻负载的情况下，路由偏转也会造成大量的丢包。偏转路由算法可能选择了一个不恰当的偏转路径，导致数据包在网络中循环传输。如果这种循环路径没有被正确检测和处理，就可能导致死锁
四、NoC流量控制
流控的策略
此文讲的比较全面，且采用案例说明7。
bufferless：对于阻塞的报文不缓存，直接丢弃或者错误路由电路交换（circuit switching）：报文header 会先于 data 首先在网络中传输。在 header 经过的路径上，所有需要的资源都会被保留。如果 header 暂时不能被分配资源，原地等待直到资源空闲。当整条路径的资源都被取得后，data 开始源源不断地在这条路径上传输，直到发送结束，断开电路连接，释放全部资源。bufferable：当报文没有被分配资源时全部被缓存
bufferable
当前大部分NoC的设计都是bufferable的，但是这种设计存在几种缺点6：
buffer消耗了极大的能量增加了网络设计的复杂度，需要控制报文在buffer中摆放和输出buffer占据了极大的芯片面积
bufferless
是最简单的流控策略，当多个报文到达端口时，需进行仲裁，未获得资源的报文则被丢弃或者错误路由。
需要ACK/NAK应答机制，告知发送端接收端是否成功接收报文，若接收失败，则报文重新发送。
bufferless的流控会造成大量资源的浪费，报文的丢弃再重发会导致传输低效。
五、NoC中节点的设计
router的结构
每个网络节点包含一个计算核和一个路由器，计算核也可以是加速器或者存储控制器等其他硬件；路由器包括输入单元、交叉开关、交叉开关分配器、虚通道分配器和路由计算单元。
每个网络节点中的路由器（router）硬件结构9：
输入单元
输入单元由输入缓存和对应的控制逻辑组成。 缓存单元被组织成多个队列，每个队列是一条虚通道。
计算单元
根据报文携带的目的节点信息，计算出输出端口和输出虚通道
虚通道分配器
完成路由计算后，报文头申请输出虚通道，虚通道分配器手机所有输入虚通道的请求，并将输出虚通道分配给提出请求的输入虚通道。 虚通道分配器和交叉开关分配器都有多个仲裁器组成。
交叉开关分配器
当输入虚通道获得输出虚通道的授权后，路由器会检查授权的输出虚通道是否由空闲的缓存单元； 如果有，报文会向交叉开关分配器提出交叉开关传输的请求。
交叉开关
交叉开关通常由多个多路选择器组成，这些堕落选择器的控制信号由交叉开关分配器生成。 一旦一个报文传输到交叉开关的输出端口，交叉开关就向上有路由器反馈一个信元消息，通知已经释放了一个缓存单元。
输出单元
输出单元使用多个寄存器记录下游虚通道状态
网络中cache一致性的设计
此文8对cache对网络性能的影响阐述的比较清晰。
六、网络的堵塞
网络拥塞原因
片上网络的报文户通过时分复用和空分复用等方式共享使用片上资源，当网络处于重负载情况是，有限的片上资源无法为大量的报文提供服务，从而导致拥塞现象。
此时需通过拥塞管理机制来优化网络性能。即根据网络复杂情况动态调整报文优先级与网络资源分配方式，将网络资源有限分配给一些特殊报文使用，避免或者延迟网络进入饱和状态，达到提高网络性能的目的。
七、网络的死锁
死锁、活锁、饥饿锁、无锁在多线程、片上网络等领域概念基本一样，可参考这篇文章的描述。 多线程中死锁、活锁、饥饿锁、无锁问题
死锁的定义和原因
死锁指在系统中的多个资源彼此等待对方释放资源而无法继续执行的状态。当网络中的路由依赖形成一个环时，互相阻塞而无法前进，就发生了路由死锁。在没有死锁回复机制的情况下，死锁会导致网络瘫痪。 无死锁要求网格资源之间没有循环依赖，这些资源包括缓存和链路。
死锁产生的条件：
互斥条件：所谓互斥就是节点在某一时间内独占资源。请求与保持条件：一个节点因请求资源而阻塞时，对已获得的资源保持不放。不剥夺条件：节点已获得资源，在末使用完之前，不能强行剥夺。循环等待条件：若干节点之间形成一种头尾相接的循环等待资源关系。
活锁的定义和原因
活锁指的是在尝试解决问题时，任务或执行者没有被阻塞，但由于某些条件没有满足，导致它们不断地重复尝试、失败、再尝试、再失败。 活锁中的实体是在不断地改变状态，而不是像死锁那样表现为等待状态。活锁有可能在一定时间后自行解开，因为进程没有阻塞，但它们无法取得任何实际的进展，这通常会占用网络带宽。活锁可以看作是一种特殊的饥饿状态，即资源并没有被别人持有，但由于某些原因而无法得到。
解决死锁的方法
通过虚通道将请求分流
完全自适应算法允许报文使用源节点和目标节点间的所有传输路径，通过虚通道消除路由子函数内部的资源循环依赖，从而消除网络死锁。 通过虚通道解除死锁除了需要一个虚拟网络，还需要协议级的避免死锁方法1。
限制报文传输的部分转向消除资源循环依赖
即设计路由函数打破CDG中所有环
知乎中的死锁描述博客
参考文献
Jieming Yin, Zhifeng Lin, “Modular Routing Design for Chiplet-based Systems” ISCA.片上网络之Channel Dependency Graph（一）片上网络之Channel Dependency Graph（二）片上网络之Channel Dependency Graph（三）知乎：CoNEXT’21—Burst-tolerant Datacenter Networks with VertigoT. Moscibroda and O. Mutlu, “A case for bufferless routing in on-chip networks,” in Proceedings of the 36th annual international symposium on Computer architecture, 2009, pp. 196–207.知乎：Li Shi：《片上网络》笔记（五）：流量控制知乎：Li Shi：《片上网络》笔记（二）：系统架构与接口《片上网络原理与设计》王志英主编
柚子快报激活码778899分享：片上网络NoC
文章来源
您阅读本篇文章共花了：
发表评论