片上网络NoC（7）——流控制

一、概述

    流控制（flow control）负责管理网络缓冲区和链路的分配。它决定何时为消息分配相应的缓冲区和链路资源，以及分配资源的粒度，另外还决定如何在许多消息之间共享这些网络资源。良好的流控制协议可以在不增大资源分配开销的同时，降低小负载情况下的信息传输延迟，并通过实现消息对缓冲区和链路的有效共享来提高网络吞吐量。借助流控制，我们可以确定数据包访问缓冲区（或完全跳过缓冲区访问）和在链路中传输的频率，进而确定网络的能量和功率消耗。实现流控制协议所需要考虑的复杂因素包括：路由器微体系结构的设计及在路由器之间传输资源信息所需的布线开销。

二、消息、数据包、flit和 phit

    当一条消息被注入网络时，它首先被分段成数据包（packet)，然后每个数据包再被分成固定长度的flit(flit 是flow control unit 的缩写，为流控制中最小粒度数据单元）。例如，在多核芯片中，拥有某个数据的共享节点会向请求节点发送一个长度为128字节的缓存行，此缓存行将以消息的形式注入网络。如果128字节小于数据包的长度上限，则整个消息将被编码为单个数据包。数据包由包含目的节点地址的头flit(head flit)、包含数据主体的体flit(body flit),以及指示数据包结束的尾flit(tail flit）组成。flit 可以进一步分解为 phit(phit 是 physical transfer unit 的缩写，其为物理传输最小粒度数据单元）。phit 是对应于物理通道宽度的物理单位。

    消息是网络层面通信逻辑上的基本单位，数据包是网络层面通信物理上的基本单元。由于片上布线资源丰富，片上网络的通道往往采用较大的数据位宽，因此消息可能由单个数据包组成。在片外网络中，通道位宽受引脚位宽的限制，这种限制导致它被分解成更小块，称为phit。迄今为止，在片上网络中，由于片上通道较宽，flit都由单个phit 组成，并且作为消息的最小细分单位。
     流控制技术是根据资源分配的粒度来进行分类的。我们接下来将分别讨论以消息、数据包和flit进行操作的技术。

三、基于消息的流控制

    电路交换是一种在消息级进行控制的技术。电路交换将多跳所需要的资源（链路）预分配给整个消息。一个探测（probe）消息（也称为建立消息）将被发送到网络中，并预留从源节点向目的节点传输数据包所需的所有链路，这些链路将用于传输整个消息（或多个消息）。一旦探测消息到达目的节点（即说明已成功分配必要的链路），目的节点就会向源节点发送确认消息。源节点接收到确认消息后，链路正式建立。以上称为链路的建立阶段。之后，源节点会发送实际待传输的消息，该消息可以快速地通过预先建立的链路在网络中进行传输。一旦消息完成传输后，相关链路资源将被释放。

    异步传输模式（ATM）使用虚拟通道连接，在发送数据之前，从源节点到目的节点的网络资源必须被预留（这一点和电路交换一样）。不同的是，ATM中数据是以数据包粒度而不是消息粒度通过网络进行传输的。

四、基于数据包的流控制

    电路交换将资源分配给消息，并跨多个网络节点进行分配。但是，这样的方案存在一些不足之处；接下来，我们看看以数据包为粒度的资源分配方案。基于数据包的流控制技术首先将消息分解成为数据包，然后在链路上交织传输这些数据包，从而提高链路利用率。与电路交互不同，以下技术均需要在每个节点设置缓冲区来存储在线数据包。

4.1 存储转发流控制

    在基于数据包的技术中，消息被分解成多个数据包，并且每个数据包由网络独立处理。在存储转发流控制中，每个节点在接收到整个数据包之后才会开始将数据包转发到下一个节点，这会导致每跳都造成较高的延迟。因而存储转发流控制技术往往不适合用于对延迟又严格要求的片上网络。此外，存储转发流控制要求每个路由器都有足够大小的缓存区来暂存整个数据包，这对缓存区大小有较高的要求，使得该技术并不似乎用于片上网络。

4.2 虚拟直通流控制

    为了降低数据包在每跳处的等待延迟，虚拟直通流控制允许当前节点在接收到整个数据包之前就开始向下一个节点传输。通过这种方式，数据包经历的延迟相对于存储转发流控制将大大降低。但是，带宽和存储仍然以数据包大小为单位进行分配。只有当下游路由器有足够的缓存区空间来保存整个数据包时，数据包才会向下一个节点移动。当数据包较大时（如64字节或128字节大小的缓存行数据），面积和功耗受限的片上网络将难以提供虚拟直通流控制所需的缓冲区空间。

五、基于flit的流控制

    基于数据包的流控制技术需要大量的存储空间。为了降低对存储空间的需要，基于flit的流控制技术被提出。较低的缓冲区容量要求有助于路由器满足芯片上的面积或功率限制。

    与虚拟直通流控制一样，虫洞流控制将数据划分成不同的flit，允许当前节点在接收到整个数据包之前就将部分flit发往下游节点。对于虫洞流控制，一旦下游节点有可以容纳flit大小的缓冲区空闲，当前节点中的 flit 就可以离开缓冲区并向下游节点传输。但是，与存储转发流控制和虚拟直通流控制不同，虫洞流控制按flit分配存储和带宽，而不是按整个数据包分配存储和带宽，这允许在每个路由器中使用相对较小的flit缓冲区，即使对于大数据包也是如此。需要注意的是，虽然虫洞流控制可以有效地使用缓冲区，但它无法有效利用链路带宽。虽然虫洞流控制以 flit 为单位分配存储和带宽，但是路由器中的链路在整个数据包的传输期间将被占用。这导致当数据包被阻塞时，该数据包占用的所有物理链路仍然无法继续传输，即都处于闲置状态。因为虫洞流控制在 flit 粒度上分配缓冲区，所以由多个 flit 组成的数据包可能跨越多个路由器，一旦发生数据包的阻塞，很多物理链路都将进入闲置状态。此时在被阻塞的数据包后面排队的其他数据包就无法使用闲置的物理链路，从而降低了网络的吞吐量 。

六、虚拟通道流控制

    虚拟通道技术首先被用于避免死锁，但同时也被用于缓解流控制中的队首阻塞（head-of-line blocking）并提高吞吐量。在上述所有的流控制技术中，每个输入端口都只有一个队列，因而都可能发生队首阻塞。队首阻塞：当输入端口只有一个队列时，队列中的数据包只能按照队列顺序一一处理，因此当队首的数据包被阻塞时，队列后续的所有数据包都会被阻塞。（当队首的数据包被阻塞时，即使路由器有能够被队列后续的数据包所利用的空闲资源，队列后续的数据包仍然会被阻塞。）

    本质上，每个虚拟通道（VC）都是路由器中的一个独立的队列。多个虚拟通道通过时分复用的方法共享两个路由器之间的物理链路了。通过赋予每个输入端口多个队列（虚拟通道），可以有效减少队首阻塞。虚拟通道以时钟周期为控制粒度，进行物理链路带宽的分配。当某个虚拟通道的数据包被阻塞时，其他数据包仍然可以通过其他的虚拟通道穿过物理链路。因此，虚拟通道提高了物理链路的利用率，并提高了整体网络的吞吐量。