路由器微体系结构-流水线
典型处理器的逻辑流水线包括5级：取指令、译码、执行、内存操作和写回。根据时钟频率，这些逻辑分级都可以设计成物理流水线。相应地，路由器流水线可设计为：缓冲区写入(Buffer Write, BW)、路由计算(Route Computation, RC)、虚拟通道分配(Virtual-channel Allocation, VA)、开关分配(Switch Allocation, SA)、开关传输(Switch Traversal, ST)、链路传输(Link Traversal, LT)。路由器流水线如图6.16所示。图中LA-LT是指前瞻链路传输。图16a展示了一个简单的虚拟通道路由器的逻辑流水线级数。
- 在缓冲区写入(Buffer Write, BW)阶段，数据包的head flit一旦抵达输入端口，就会解码得到路由信息，根据路由信息存储到指定的VC通道中。
- 在路由计算(Route Computation, RC)阶段，路由器路由逻辑执行路由计算以确定数据包的输出端口。
- 在虚拟通道分配(Virtual-channel Allocation, VA)阶段，在确定了输出端口后，路由器根据数据包的报头仲裁其输出端口的虚拟通道（即确定下一个路由器的输入端口的虚拟通道）。
- 完成虚拟通道分配后，就会进入开关分配阶段。在该阶段路由器仲裁交叉开关的输入端口和输出端口。在flit赢得交叉开关输入端口和输出端口的仲裁后，flit就会从缓冲区读取出来按照确定的端口输入交叉端口，然后从仲裁的端口输出。
- 在链路传输(Link Traversal, LT)阶段，flit会经过路由器之间的链路 link 移动到下一个节点。body flit 和 tail flit在流水线中的RC和VA阶段不进行任何计算\分配，因为继承head flit的路由计算和虚拟通道分配结果。一旦tail flit离开路由器，由head flit预留的虚拟通道就会释放。
与具有输入虚拟通道的路由器不同的是，无虚拟通道的虫洞路由器的输入缓冲区中没有虚拟通道，所以每个输入端口仅有一个较深的缓冲区队列。没有虚拟通道所以不需要进行VA阶段，故流水线只有四级。
6.5.1 流水线的实现
逻辑虚拟通道管道由五个阶段组成。以低时钟频率运行的路由器将能够将所有五个阶段放入一个时钟周期中(因为每个时钟周期的时长较长，硬件简单)。对于激进的时钟频率，路由器架构必须采用流水线方式。实际的物理流水线取决于每个逻辑阶段的实现及其在该技术中的关键路径延迟。
路由器内传统5级流水线如图6.16a所示。其中包括BW RC VA SA ST。虽然LT不属于路由器内的流水线(发生在路由器之间的连接)，但LT是使流水线前后可以衔接的必要阶段，故将其列出。注意区分以下三点。
（1）路由器的每一个输入端口都有其专属缓冲区。所有缓冲区可以组织成1个或多个队列。只有当所有缓冲区组织成多个队列时，每个队列才叫作虚拟通道。因此虚拟通道的完整表述为“路由器输入端口x的虚拟通道 VCx”。
（2）路由器的输出端口直接连接到下一个路由器序号相同的输入端口。例如，在拓扑中，路由器0的输出端口1与路由器1的输入端口1之间存在链路，所以选定了路由器0的输出端口就等于选定了路由器1的输入端口(但模拟器中的实现与此不同，仅用于理解)。
（3）“路由器0的输出虚拟通道”并非指路由器0输出端口的虚拟通道，而是指下一跳路由器（路由器1）输入端口的虚拟通道，即路由器0的输出虚拟通道分配（VA）级进行的是下一跳路由器输入端口的虚拟通道分配（VA）。
下面以一个数据包的head fit 为例，分析这个 head flit 在各个流水线级进行的处理。假设 head flit 从输入端口2进入路由器0的虚拟通道 VC3（路由器结构如图6-1所示），并且下一跳为路由器1，则各级流水线的运算如下。
- 在缓冲区写入(Buffer Write, BW)阶段，输入路由器的flit存入缓冲区。如head flit从输入端口2进入路由器0的虚拟通道VC3。
- 在路由计算RC阶段，路由器路由逻辑执行路由计算以确定head flit的输出端口，如果是body/tail flit则不进行任何计算。如在RC级路由计算模块为head flit计算路由器0的输出端口(路由器1的输入端口)，假设计算结果为路由器0的输出端口1。
- 在虚拟通道分配(Virtual-channel Allocation, VA)阶段，在确定了输出端口后，虚拟通道分配器为head flit分配输出虚拟通道(下一跳路由器输入端口虚拟通道)，分配过程以RC级计算得到的输出端口为输入。如以输出端口1为输入，分配路由器1输入端口1的虚拟通道，假设分配VC2。
- SA级。SA级以RC计算的输出端口和VA分配的输出虚拟通道为输入。开关分配器仲裁使用交叉开关输入端口的输入虚拟通道和使用交叉开关输出端口的输入端口。如果不存在竞争则直接批准即可；若存在竞争则进行仲裁。例如head flit在SA级获得了交叉开关输入端口2(因为在路由器的输入端口2)和输出端口1(在输出端口的1)的批准。
- 在开关传输(Switch Traversal, ST)阶段，flit会按照交叉开关指定的路线传输flit。例如路由器0将head flit从路由器0的输入端口2的VC3中读取出来，并送入交叉开关的输入端口2，然后从交叉端口输出端口1中读取head flit并置于路由器0的输出端口1中。
- 链路传输(Link Traversal, LT)级，flit沿路由器之间的链路从当前路由器的输出端口传递到下一跳路由器的输入端口。例如从路由器0的输出端口1出发来到路由器1输入端口1的VC2，随后进行新一轮的流水线周期。
以上6个过程是flit在NOC中传递的全部步骤，包括五级流水线和一个额外的传输级。其中 BW->RC->VA->SA->ST 之间存在依赖关系。即RC计算的得到的输出端口是VA级的输入参数；RC和VA级结果为SA级的输入参数；只有SA批准的flit才能进入ST级别；经过ST级之后到达输出端口才能进入LT。所以在传统流水线中各级必须顺序执行。
以上是针对head flit，而body/tail flit的流水线中的RC和VA级仅起到占位的作用，不进行计算和分配，而是从head flit中继承。
如果物理流水线与逻辑阶段一样有五个阶段，则关键路径延迟最长的一级就会决定路由器的时钟频率。通常，当 VC 数量较多时关键路径位于虚拟通道分配VA，当交叉开关有很多位宽很大的输入端口时是交换机分配阶段。时钟频率也可以由整体系统时钟确定，例如由处理器流水线的关键路径决定大小。
增加物理管道阶段的数量会增加每条消息的每跳路由器延迟以及缓冲区周转时间(turnaround time)，增加缓冲区周转时间会影响所需的最小缓冲并影响吞吐量。因此，已经提出并采用很多技术减少级数来优化流水线。接下来解释针对逻辑流水线阶段的常见优化。最先进的路由器实现可以在一个周期内执行所有操作。
6.5.2 流水线的优化
所有路由器的共同目标是使多个数据流能够在共享资源（链路和缓冲区）上进行复用。为片上路由器提出了无数的流水线优化。
6.2.1 前瞻路由 lookahead routing
前瞻路由将路由计算RC与流水线其他级并行执行，从而将 RC 阶段从关键路径中删除(关键路径是整个处理流程中延迟最高的数据通路，五级流水线中的关键路径由每一级中延迟最高的数据通路串联而成，因为RC与其他级并行故流水线中不再具有RC级的数据通路，故称在关键路径中删除了RC级)。数据包的路由会在前一跳路由器中进行。
因为传统流水线中VA级以RC的结果为输入参数，因此为了将这两级并行执行，前瞻路由将flit在当前路由器中的输出端口计算提前到上一跳路由器的RC级，而当前路由器计算下一跳路由器的输出端口。通过这种方式打破VA对RC的依赖，从而实现并行。因此叫做前瞻路由lookahead routing，RC也改称为Next Route Computation(NRC)。
路由输出端口提前一跳确定并在头 flit 中进行编码，从而使传入 flits 能够在 BW 阶段之后立即进入 VA/SA级。图 6.15b 显示了具有前瞻路由的路由器管道，也称为下一个路由计算 (NRC) 或路由预计算(route pre-computation)。
6.2.2 低负荷旁路 low-load bypassing
低负载旁路从低负载的路由器中将 BW 和 SA 阶段与其他级并行，从而在关键路径中删去这两级。如果在输入的flit之前没有位于其它flit，输入的flit就可以推测地(Speculatively)进入开关传输ST级。图6.15c显示了低负荷旁路流水线的流程，在此期间，flit交叉开关建立(set up)只消耗一个时钟周期，在这个时钟周期中按照下一个时钟周期的传输需求设置交叉开关，同时分配与flit所需输出端口相对应的空闲VC，随后是ST和LT 。然而，一旦输出端口发生冲突时，flit 会被写入缓冲区 (BW)，并随后执行 SA。
图 6.16a 显示了低负载旁路的示例。在时间 1，flit A 到达南输入端口，并且输入队列中没有等待的缓冲流。前瞻路由计算在第一个周期 (1a) 中执行，并设置南输入和东输出之间的交叉连接 (1b)。在时间 2，A 穿过交叉开关并退出路由器。缓冲和分配被绕过(bypassing)。在图 6.16b 中，两个flit在时间 1 到达（A 在南输入，B 在北输入）；两者都有空的输入队列并尝试绕过管道。然而，在交叉开关设置 (1b) 期间，由于两个 flits 都尝试为东输出端口设置交叉开关，因此检测到端口冲突。所以现在两个 flits 都必须写入输入缓冲区 (1c) 并通过常规流水线。
-
补充：推测性执行
低负荷路由器指因输入flit总数少且抵达时间分散间隔长而负荷较低的路由器。在低负荷下，大多数flit输入缓冲区队列时前方没有其他flit。因此不需要存储此类flit，因为缓冲区是暂时存储无法向下传递的flit。因此当前方没有其他flit时，该flit直接跳过流水线中的BW。相反，如果有其他flit则必须通过BW级，写入缓冲区等待。
另外由于flit总数小，大多数情况下flit之间没有竞争。因此不需要仲裁即不需要开关分配，但VA是需要的。所以不存在竞争时，可直接跳过SA级，而存在时则必须通过SA级。为了判断是否存在竞争，在ST级前一级增加了建立(set up)过程来尝试直接根据flit的传输配置交叉开关。如果存在竞争则配置失败，写入缓冲区。
由于建立(set up)这一过程在正常流水线中属于ST级别，而也同时很可能失败，所以称建立为推测性执行开关传输。最终的成功推测的流水线没有缓冲区写入BW和开关分配SA，前瞻路由NRC、虚拟通道分配VA和建立setup并行执行。
6.2.3 基于推测的虚拟通道分配 Speculative VA
推测 VA通过将虚拟通道分配VA级合并到其他流水线中，从而将 VA 阶段从关键路径中删除。 Flit 在 BW 之后推测性地进入 SA 阶段，对交换机端口进行仲裁，同时尝试获取空闲 VC。(即在获得非推测的VA结果之前假定一个推测的VA的结果，并以推测的VA结果作为SA的输入来执行SA)。
如果推测成功，则flit直接进入ST流水线阶段。然而，当推测失败时，flit 必须再次经历其中一些流水线阶段，具体取决于推测失败的位置。图 6.15d 显示了具有推测的路由器流水线。在图 6.16b 中，在步骤 2 期间，在时间 2，flit A 和 B 并行执行虚拟通道和交换机分配（2a 和 2b）。报文B成功分配输出虚拟通道和交叉开关，并在时间3穿过交叉开关。报文A分配虚拟通道成功，但分配交换机失败(因为冲突)。在时间 3，A 将再次尝试分配交换机。 A 的请求现在是非推测性的，因为它已经获得了输出虚拟通道 (2a)。 从而A的请求成功，穿过交叉开关并在时间4从路由器中发出。
6.2.4 虚拟通道选择 VC selection
VC选择消除了路由器流水线中的VA阶段。进行虚拟通道选择的原因是，对于缓冲的flit来说，多个输出 VC 的成熟 VA 仲裁是不必要的，因为在每个周期中只有一个flit可以从输出端口流出。反而每个输出端口都维护一个空闲 VC ID 队列即可。
每个输出端口的 SA 获胜者被分配队列头部的 VCid虚拟通道标识。仅当其输出端口处的空闲 VC 队列非空（即下一个路由器的输入端口至少有一个空闲 VC）时，head flit 才会进入 SA。
body和tail flit可以直接进入 SA，无需进行输出端口空闲虚拟通道队列非空的检查。空闲 VC 队列的更新发生在关键路径之外(去掉了VA且VA实现简单，其处理延迟可以隐藏在其他流水线级中)。如果存在多个消息类/虚拟网络，则必须为每个虚拟网络维护其专属的空闲的 VC 队列，并且 SA 阶段可能会被扩展以容纳额外的多路复用器以在每个队列的头之间进行选择。除了没有推测之外，该流水线与基于推测 VC的虚拟通道流水线相同（图 6.15d）。
6.2.5 前瞻旁路 Lookahead bypass
前瞻旁路利用上述优化来设计单周期路由器。它将路由信息提前发送到下一跳进行分配和仲裁，因此将 BW缓冲区写入 和 SA交叉开关分配 阶段从 flit 传输的关键路径中删除。这样使flit在当前和下一跳路由器之间传输时，下一跳路由器就能根据路由信息进行开关分配(SA)。
具体实现：当flit处于当前路由器开关传输级时，向下一跳路由器发送一些数据位来实现。这些数据位称为前瞻信号(lookaheads)。这些前瞻信号就是head flit的报头所包含的信息(路由、虚拟通道标识等)，这些信息可以通过重新分配通道带宽，而不需要额外的线路。
当 flit 执行 LT 时，该flit的前瞻信号就会在下一跳路由器执行开关分配SA。因此当flit抵达下一跳路由器时，因为该flit前瞻信号已经成功完成了SA，所以flit可以直接跳过BW SA，直接进入ST。通过lookaheads成功仲裁允许其flit绕过BW和SA并直接进入ST，将其延迟减少到每跳两个周期（ST+LT）。如图 6.15e 所示。这种方法不仅可以节省延迟，还可以节省缓冲读/写功率。如果先行仲裁失败，flit 会被缓冲并通过正常的流水线。如果存在竞争性的前瞻或获得更高优先级的 flit，则只会付出额外的延迟代价(缓冲flit增加一个使用周期的额外延迟)。
图 6.17 显示了一个示例，其中两个flit在周期 1 中到达路由器。B 的先行赢得了交换机分配并选择了 VC； flit B 绕过BW，直接进入周期 2 的开关。由于 A 的先行失败，所以 flit A 被缓冲(写入缓冲区)； A在Cycle 2中进行交换机分配和VC选择，在Cycle 3中进行开关传输ST。即缓冲增加了一个额外的时钟周期。
6.2.6 前沿技术 State-of-the-art
如今可以采用现代技术来设计最先进的网络路由器，这些路由器工作在GHz的时钟频率，只需花费最先进的单周期来进行路由器中的开关分配 SA和 虚拟通道分配 VA，以及随后的周期来完成开关的传输(ST)和链路传输(LT)，这可以实现两个周期的每跳传输（无争用）。