NOC总线(2)

1. NoC的路由

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

1.1 确定性XY路由算法

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

1.2 odd_even路由算法

odd_even路由算法是一种适用于mesh结构的部分自适应路由算法，对信号发生转弯的位置进行约束来防止死锁的产生。如果节点所在的Y坐标为奇数，该列称为奇数列；如果该列的Y坐标为偶数，该列称为偶数列。用E/S/W/N分别代表东南西北，NW表示从北到西的转弯。为了避免死锁发生，这种算法约束了一些转弯。例如：

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

1.3 DyAD路由算法

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

1.4 DyXY路由算法

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

1.5 Weight-based Table routing

这是一种更复杂的路由方法，其中每个可能的路径或链接都分配有一个权重值。路由决策基于这些权重值，数据包倾向于选择权重最高（或最低）的路径。权重可以根据许多因素进行分配，例如路径长度、拥塞状况或能耗。这种方法可以提供比XY routing更好的性能，但设计和实现更复杂，且可能需要更多的硬件资源。

1.6 NoC失效的一些情况

死锁（Deadlock）: 死锁是指在多任务系统中，两个或多个任务相互等待对方释放资源，导致任务无法继续进行的现象。可以通过控制流量来解决。

        活锁：是指一个数据包在其目的节点周围环绕传输，但无法到达目的节点。可以通过采用最短路径的方法解决。
        饥饿（Starvation）: 在NoC系统中，饥饿是指某些任务或数据包由于其他高优先级的任务或数据包不断占用资源，导致无法获得足够的资源来完成它们的操作。可以通过合理的资源分配策略解决。
        拥塞（Congestion）: 当数据包在NoC中的流量超过网络的处理能力，就可能会发生拥塞。这可能会导致数据包的延迟增加，甚至可能导致数据丢失。
        路由问题（Routing Issues）: 不正确或低效的路由策略可能会导致数据包在到达目的地之前需要经过更多的跳数，从而增加了传输延迟并降低了网络性能。
        在实际应用中，还需要根据特定的NoC结构来选择适合的路由算法。

2. NoC的交换

NoC的交换技术是动态分配传输线路和接口资源的方式，主要包括电路交换和包交换两种方式。

2.1 电路交换

电路交换是指在发送数据前，需要先在源节点与目的节点之间建立物理链路，然后进行数据传输，数据可以利用物理信道的整个带宽进行传送，而其它设备将无法使用这些物理链路，直到数据传输结束后链路才被释放。

优点：由于路径确定，并且独占物理通道，具有较高的数据传输效率和通信质量。
缺点：无法适应网络的实际变化情况，缺乏灵活性，链路利用率低，建立和释放连接浪费时间，不适合突发数据传输。电路交换方式适合于数据传输频繁，或者通信模式相对静态的场合。

2.2 包交换

包交换模式是将数据封装成包，每个数据由包头和数据部分组合而成。根据包头的信息，通过路选择策略，一级一级的可以将数据转发到目的地。
优点：不需要建立和释放链路花费附加时间；在数据传输过程中可以动态分配带宽，逻辑上属于同一连接的数据包可能通过不同的路径进行传输，信道利用率高，吞吐量高；而且链路故障具有容错能力，适合突发数据的传输。

缺点：在交换结点中存储整个数据包需要很大的缓存器，这会增加的面积成本；另外假如路由策略的选择不当，可能出现不同的数据包同时征用链路，会造成拥塞和死锁。
目前主要有三种包交换技术：存储转发（store and forward，SAF）、虚直通（virtual cut through，VCT）和虫孔（Wormhole）交换技术。

2.2.1 存储转发交换技术SAF

SAF交换技术是最简单的包交换方式，需要足够的缓存空间存储整个数据包，当且仅当路由器收到整个数据包后才能将其转发出去，增大了数据包的延迟。SAF需要较大的缓存空间，需要更大的数据带宽，并且延时较大。改进的办法是不需要等待数据包完整收到就将其转发出去。

2.2.2 虚直通交换技术VCT

VCT交换技术与SAF技术不同之处在于，VCT交换时，数据包头部一旦到达即可被转发，无需等待数据包完全到达。一旦做出路由决策并且输出通道是空闲的，路由器就可以马上转发随后的数据部分。当网络不存在延迟时，VCT交换技术效率很高，可以及时转发，但当网络拥塞时，路由器需要缓存整个数据包，缓存空间要占用很大的片上系统面积。

2.2.3 虫孔交换技术

虫孔交换中，数据被分为若干流控单元flits。第一个流控单元成为Head flits，带有数据包的目的地址等控制性信息，最后一个称为Tail flits。当路由器收到Head flits时，路由器根据其中的目标地址计算输出端口，端口空闲则将数据按流控单元依次转发出去，数据传输结束则释放端口。当Head flits被阻塞时，后面的数据也依次被阻塞，分别缓存在相邻的几个路由器中。相比之前的两种策略，虫孔交换技术的路由器志向需要几个flits的缓存空间，不需要缓存整个数据包的缓存空间。但分段存储数据更容易造成链路阻塞，更容易出现死锁。

综上，不同的NoC路由算法和交换技术各有优劣，我们需要根据特定的NoC结构，综合考虑多种因素选择合适的交换方式以提高传输质量，降低传输延迟。

3. 数据包packets格式：message -> packets -> flit -> phits

message是一组连续的比特流，想从源router传送到目的地router。将一个message分为若干packets，每个packets是routing路由和sequencing排序的基本单位。packet分为具有固定格式的flit组，包含header、body、tail。

message：从程序员的角度来看，message是一个信息单元，通信的目的是要完整传递这个message。大小仅受用户内存空间的限制。
packet：是最小的通信单元，控制状态被分配给一个数据包。包含路由信息（例如，目标地址）和其标头中的排序信息。它的大小是数百或数千字节或单词的数量级。它由header flit和data flit迁移组成。数据包可能被分成小段。
Flit：是bandwidth 和storage allocation的基本单位。flit没有任何路由或序列信息，必须沿着整个所在的packet顺序传播。根据 NoC 链路宽度，packets被分解为一个或多个flits。
Head flit, body flit, tail flit, head/tail flit.
Head flit allocates channel state for a packet，and tail flit deallocates it，tail标记数据包的结尾。
header flit里有destination adderss和sequence number。
Phit： (physical transfer digits) 是在一个时钟周期内通过通道传输的单位。

4. Router architecture

NoC中的路由器是一种专门为芯片级通信而设计的高度优化组件。它们基于特定的路由算法，使用多个输入/输出端口和缓冲区来实现数据传输和路由选择。路由器的设计目标是提供高性能、低延迟和可靠的通信，在大规模集成电路中支持高度并行的处理单元间的通信需求。

4.1 Router的内部结构

一个典型的基于“Message Passing” Systems的NoC路由器Router的结构如图所示，他由InputUnit（输入单元）、OutputUnit（输出单元）、Routing Computation（路由计算器）、Switch Allocator（开关分配器）、Virtual Channel Allocator（虚拟通道分配器）、Crossbar（横梁交叉开关矩阵）组成。

4.1.1 Input Unit（输入单元）

输入单元主要负责接收来自其他节点的数据。这里面可能包括多个虚拟通道（Virtual Channels），每一个VC都有独立的缓存队列。输入单元由输入缓冲器（input buffer）和相关的链路控制逻辑组成。输入缓冲器由 SRAM 单元或寄存器构建。缓冲槽被组织成若干个队列，每个队列是一个VC。

4.1.1.1 VC 虚拟通道

VC用于在同一物理连接中复用传输的技术，它可以有效地减少网络阻塞，提高带宽利用率。

一个VC里存了一组flit吗？还是一个flit的一部分？

答：一个虚拟通道可以存储一个或多个完整的flit（flow control digit）。

增加虚拟通道的数量会有以下一些可能的影响

        增加硬件复杂性和成本：每个虚拟通道都需要其自身的缓冲区和状态机来处理存储和转发数据包。因此，增加虚拟通道的数量将会增加设计的复杂性和硬件成本。
        提高并行性和带宽：更多的虚拟通道意味着可以同时处理更多的数据包，从而提高系统的并行性和带宽。
        改善网络性能：更多的虚拟通道可以提供更多的路由选择，从而改善网络的性能，特别是在网络拥塞的情况下。
        可能会增加功耗：由于每个虚拟通道都需要处理和转发数据包，增加虚拟通道的数量可能会增加系统的功耗。
        延迟可能会有所增加：虚拟通道分配器在决定哪个数据包使用哪个虚拟通道时可能需要更多的时间，这可能会增加数据包的传输延迟。

4.1.2 Output Unit（输出单元）

        每个路由器的Output Unit都会维护一个credit计数器或寄存器，用于记录每个目标路由器Input Unit的剩余credit。当一个数据包从Output Unit发送并被目标路由器的Input Unit成功接收和处理后，目标路由器会返回一个credit给源路由器，源路由器的Output Unit会相应地更新credit寄存器，增加对应目标路由器Input Unit的credit计数。输出单元会根据虚拟通道的调度策略，如循环调度或优先级调度，来决定下一个从哪个虚拟通道中取出数据。输出单元通过多个寄存器跟踪下游 VC 的状态。
        “input_vc”寄存器是下游VC被分配到的输入VC，VC进到从这个地方后出去到后续的Router。
当 1 位“idle”寄存器的值为“真”时，下游 VC 收到最后分配的数据包的尾部迁移，现在可以重新分配给其他数据包。
        “credits”寄存器记录credits数额

4.1.3 Routing Computation（路由计算器）

路由计算器根据预先定义的路由算法（如XY路由或者自适应路由等）来决定每一个数据包的下一个路由路径。这个过程通常依赖于数据包的目的地址和当前的网络状况。计算是根据head flit携带的目的地位置进行的，它为数据包产生输出端口和输出VC。

4.1.4 Switch Allocator（开关分配器）

开关分配器用于决定在下一个时钟周期中，哪个输入单元的数据包将被分配到哪个输出单元。它需要协调可能的冲突，例如，当多个输入单元想要发送数据到同一个输出单元的时候。他控制着Crossbar。

4.1.5 Virtual Channel Allocator（虚拟通道分配器）

虚拟通道分配器用于管理输入单元中虚拟通道的使用。当一个数据包从一个输入单元的虚拟通道准备转移到另一个输出单元的虚拟通道时，需要虚拟通道分配器进行协调和分配。开关分配器（Switch Allocator）在决定给某个输出端口分配哪个输入端口的数据包时，就需要考虑这个输出端口剩余的信用（Credit）。只有当输出端口有足够的信用来接收新的数据包，开关分配器才会分配数据包到这个输出端口。Routing Computation 完成后，head flit 请求输出 VC。VC 分配器收集来自所有输入 VC 的请求，然后将输出 VC 分配给请求输入 VC。它保证一个输出VC最多分配给一个输入VC，并且每个输入VC最多被授予一个输出VC。

4.1.6 Crossbar（横梁交叉开关矩阵）

交叉开关一般用多个多路复用器来实现。这些多路复用器的控制信号由开关分配器生成。交叉开关矩阵是路由器的核心，它连接了所有的输入单元和输出单元，在每一个时钟周期中，根据Switch Allocator的决定，会建立或断开特定的输入单元到输出单元的连接。

4.2 流水线

流水线确保通过网络有效地路由数据包或消息。

head flit 到达输入端口后，首先根据其在流水线阶段的缓冲区写入(BW) 阶段输入 VC 进行解码和缓冲。
接下来，路由逻辑执行路由计算 (RC) 以确定数据包的输出端口。
head flit然后在VA阶段（Virtual Channel分配）仲裁与其输出端口对应的VC(即，在下一个路由器的输入端口的VC)。
成功分配 VC 后，头部 flit 进入开关分配 (SA) 阶段，在该阶段仲裁开关输入和输出端口。
在赢得输出端口后，然后从缓冲区中读取 flit 并进入交换机遍历 (ST) 阶段，在该阶段它遍历交叉开关。
最后，flit 在链路遍历 (LT) 阶段被传递到下一个节点。Body 和 tail flits 遵循类似的管道，只是它们不经过 RC 和 VA 阶段，而是继承由 head flit 分配的路由和 VC。tail flit 在离开路由器时，释放 head flit 保留的 VC。

4.2.1 BW: Buffer Write 缓冲区写入

在此阶段，传入的数据包或消息临时存储在输入缓冲区中。路由器的每个输入端口都有自己的缓冲区来保存传入数据。缓冲区写入阶段根据数据包的目标地址将传入数据写入适当的缓冲区。

4.2.2 RC: Route Compute 路由计算

在路由计算阶段，路由器为传入的数据包确定一个或多个适当的输出端口。它使用路由算法或表来做出此决定。路由决策基于数据包的目标地址和网络的当前状态。

4.2.3 VA: VC(Virtual Channel) Allocation 虚拟通道分配

Input VCs arbitrate for “output” VCs (Input VCs at next router) 输入 VC 仲裁
虚拟通道用于在物理链路内提供多个独立的通信路径。在VC分配阶段，路由器将输入虚拟通道分配给输出虚拟通道。这个过程允许拥塞管理，并通过允许数据包在不同的虚拟通道上同时传输来提供改进的性能。

4.2.4 SA: Switch Allocation 开关分配

Input ports arbitrate for output ports 输入端口仲裁输出端口
在交换机分配阶段，路由器的输入端口仲裁对输出端口的访问。该仲裁过程确定哪个输入端口可以使用哪个输出端口来传输其数据。目标是最大程度地减少争用并确保对网络资源的公平访问。

4.2.5 ST: Switch Traversal 切换遍历

在Switch Traversal阶段，根据交换机分配结果将数据包从输入端口转发到路由器的输出端口。遵循前面阶段确定的路由路径，将数据包定向到它们指定的输出端口。

4.2.6 LT: Link Traversal 链接遍历

最后，在链路遍历阶段，数据包遍历连接网络中路由器的物理链路。此阶段涉及通过链路实际传输数据包以到达其预定目的地。

5. 流量控制机制

Mesh_XY网络是一种基于网格结构的拓扑，通常用于多处理器系统-on-a-chip（MPSoC）或片上网络（Network-on-Chip，NoC）中。它由一个二维网格组成，其中每个节点（或处理器）与其相邻的节点直接连接。节点可以沿X轴和Y轴方向上的连接进行通信。

5.1 基于信用（credit-based）的流量控制机制

在基于信用的流量控制中，每个下游路由器都维护了一个信用计数器，用于跟踪其可用的缓冲空间。当一个数据包（或者说flit）被成功接收后，下游路由器会向上游路由器发送一个信用（credit），表示它已经释放了一个缓冲位置。当上游路由器收到信用后，它就知道可以发送一个新的数据包。

这种机制的好处是它可以避免网络拥塞和数据包的丢失。由于每个路由器都知道其下游路由器的可用缓冲空间，所以它们不会发送超出能力的数据包。

5.2 基于握手（handshaking）的流量控制机制

基于握手的流量控制，比如在AXI（Advanced eXtensible Interface）总线协议中使用的机制，是一种请求-确认协议。在这种机制中，发送者在发送数据包之前首先发送一个请求信号给接收者。如果接收者有足够的缓冲空间，它就会返回一个确认信号，然后发送者才会发送数据包。

这种机制的好处是它可以精确地控制数据的发送，从而避免网络拥塞。然而，由于每次发送数据都需要先进行请求和确认，所以它的性能可能会受到一些影响。

5.3 Wormhole packet switching flow-control

Wormhole Packet Switching: 在NoC中，Wormhole路由是一种高效的数据包交换策略。在此策略中，一条消息被分割成多个小的数据包，或者称为flits（flow control digits）。这些flits会立即被发送到网络中，而不是等待整个消息都被装入缓冲区。这样可以减少数据在网络中的延迟时间。每个flit按照顺序路由，使得在路由过程中只需要很小的缓冲区。这就是它被称为“虫洞”路由的原因——数据就像是在虫洞中穿越，瞬间从一点传到另一点。
Flow-Control: 在NoC中，流量控制是一种方法，用于管理数据包的发送，以防止接收端的缓冲区溢出。Wormhole路由策略中常见的一种流量控制策略是基于信用的流量控制，其中发送节点需要从接收节点获得信用（代表其可用的缓冲区大小）才能发送flit。这样可以确保接收端的缓冲区不会溢出，从而提高整个系统的稳定性。

5.4 其他流量控制机制

除了基于信用（credit-based）和基于握手（handshaking）的流量控制机制外，还有其他的流量控制策略，这些策略在不同的网络系统和应用场景中可能会更有效。下面是一些例子：

        基于窗口（Window-based）：这种方法通常用于传输控制协议（TCP）中。发送方维护一个窗口，窗口大小表示可以发送并且没有被确认的数据包的数量。当接收方确认了一个数据包，窗口就会向前滑动，允许发送方发送更多的数据包。
        基于速率（Rate-based）：这种方法中，发送者和接收者协商一个数据的发送速率，然后发送者根据这个速率来发送数据。这种方法可以在一些高速网络中使用，例如ATM（异步传输模式）网络。
        基于反馈（Feedback-based）：这种方法中，接收方根据其当前的资源使用情况（例如，缓冲区的使用情况或处理器的使用情况）向发送方反馈信息。发送方根据这个反馈来调整其数据的发送速度。
        基于优先级（Priority-based）：在这种策略中，数据包根据其重要性或紧急性被赋予不同的优先级。网络设备根据这些优先级来决定数据包的发送顺序。

6. 网络接口 Network Interface

NI （Network Interface，网络接口，有的文献也称为Network Adapter）作为独立的硬件实体，使得具有不同数据宽度和频率的 IP 内核连接到 NoC 成为可能。换句话说，通过将计算与通信解耦，NI允许 PE模块和互连设计彼此独立。NI的设计直接影响基于 NoC 的 SoC 关键参数，例如功耗、延迟、吞吐量和硅面积。NI的架构分为：

基于buffer（包括基于 FIFO 和基于 DMA）；
基于Transaction（包括 OCP 兼容、AHP 兼容、DTL 兼容、Wishbone 兼容、VCI 兼容） , 和 AXI 兼容）。

6.1 基于FIFO的NI结构

基于FIFO的网络接口主要分为发送（TX）和接收（RX）部分。

发送部分的FIFO缓冲区用于存储要发送到网络的数据包，为网络忙碌时的数据提供了缓冲，防止丢失。接收部分的FIFO存储从网络接收的数据包。数据包在处理器或内存模块准备接收之前，先被存放在FIFO中。

6.2 符合 Wishbone 总线的NI结构

每个Tile里的计算单元或者SoC可能会用到总线，如果想了解这个SoC是怎么通过NI连接到NoC中，要了解一些总线的基本信息。

6.2.1 Wishbone 总线

Wishbone总线是由Silicon Labs开发的开放标准，广泛用于系统级集成（SoC）设计中的模块间通信。这种设计提供了一种标准化的方法，使不同的硬件模块可以通过统一的总线接口进行连接和通信。

6.2.2 一种通用的 Wishbone 总线的NI结构

实现：将flits从IP写入/读取Router。
NoC里的通信都是由一组flit组成的packets。通过组装flits数量、header flit、精确的flits数量插入flit类型，对来自IP的传入信号进行打包，并根据IP核心规范解包来自路由器的信号。
在不丢失数据的情况下，将数据从一个时钟域转移到另一个时钟域。

6.2.3 ProNoC中的NI接口

网络接口（NI）作为处理器（PT）和网络芯片路由器（NoC router）之间的包装器。下图显示了在ProNoC中的NI的结构框图。

图左边的Wishbone Bus Interface连着每个Tile里的IP；
图右边的NoC Router Interface连着每个Tile里的Router；

NI有三个Wishbone（WB）接口：一个从接口和两个主接口。
NI和内存之间的通信采用突发模式，通过连接到多通道直接内存访问（DMA）的两个主接口进行处理。
每个DMA的通道处理一个路由器的虚拟通道（VC）。当突发交易完成或者活动VC的资源不再可用时，DMA会在通道之间切换。
NI还可以选择配置32位循环冗余校验（CRC32）代码生成器，以检测接收数据包中的意外错误。
主IP可以读取NI状态寄存器，或者通过WB从接口编程NI进行读/写数据包。

为什么在ProNoC的NI的总线端口里要有一个从接口和两个主接口？
在 ProNoC 的网络接口 (NI) 的Wishbone Bus Interface有一个从接口和两个主接口。其中：

从接口：连接到这个Tile里的 IP，用于接收来自IP的请求。这些请求可能是发送数据（写操作）或者接收数据（读操作）。
主接口：连接到多通道的直接内存访问（DMA）。DMA控制器可以管理多个数据传输通道，这种设计可以提高数据传输的并行性，从而提高整体系统性能。
两个主接口：每个主接口连接一个 DMA，每个 DMA 的通道处理一个路由器的虚拟通道（VC），这样可以允许 NI 同时进行多个内存访问操作。当一个突发事务完成或者当前活动的虚拟通道的资源不再可用时，DMA会在通道间进行切换。这种方式使得NI能够以突发模式与内存进行通信，实现高效的数据传输。

如何处理一个IP的信息并转化为packet消息发送到Router？
网络接口（NI）作为 IP 核心和 NoC 路由器之间的桥梁，起着非常重要的角色。它负责接收来自 IP 核的数据，然后将这些数据打包成可以在 NoC 中发送的数据包。ProNoC里NI中的Wishbone Bus Interface和NoC Router Interface是如何处理一个IP的信息并转化为packet信息发送到Router的？

IP请求数据发送：首先，IP核（比如一个处理器或其他硬件模块）将数据和相关信息（如目标地址等）发送给 NI。这个过程通过 Wishbone Bus Interface 的从接口（slave interface）完成。
数据分组：NI 接收到这些数据后，将其分组（packetize），也就是将数据和相关信息封装成一个数据包。这个过程可能包括添加源和目标地址，生成错误检测和纠正码（如CRC），以及其他网络所需的信息。此外，根据网络的流量控制策略（如虫洞切换，虚拟切割等），可能还需要进一步将这个数据包分割成更小的分组（flit）。
数据缓存：然后，这些分组被放入一个队列（如FIFO队列）以等待发送。每个队列对应一个或多个虚拟通道（VC）。
数据发送：在适当的时间，NI 通过 Wishbone Bus Interface 的主接口（master interface）和 DMA 控制器启动对应的内存读/写操作，将数据送入 NoC Router Interface。然后，这些数据被送入相应的虚拟通道，并被发送到 NoC 路由器。
路由器处理：NoC 路由器接收到这些数据后，根据数据包的目标地址和路由算法，将其发送到目标网络接口。