On-Chip-Network之routing

在确定网络拓扑之后，路由算法用来决定消息将通过网络的哪条路径到达目的地。

路由算法的目标是将流量均匀地分布在由网络拓扑提供的路径上，以avoid hotspots and minimize contention，从而减少网络延迟和提高吞吐量。所有这些性能目标必须在严格遵守实现复杂性约束的同时实现：路由电路可能会延长关键路径的延迟，并增加router的area footprint。虽然路由电路的能量开销通常很低，但选择的具体route会直接影响hop count，从而极大地影响能量消耗。此外，路由算法所启用的路径多样性也有助于提高网络故障时的恢复能力。

路由算法的类型

        在本节中，我们简要讨论各种类型的路由算法。路由算法包括一般分为三类：确定性（deterministic）、无意识性（oblivious）和自适应性（adaptive）。

deterministic

        虽然目前已经提出了许多路由算法，但片上网络中最常用的路由算法是根据维度进行路由（dimension-ordered routing，简称DOR）算法。维度排序路由是确定性路由算法的一个例子，其中从节点a到B的所有消息都将始终遍历相同的路径。使用DOR，消息逐维遍历网络，在切换到下一个维度之前到达与其目的地匹配的坐标。在图4 - 1所示的mesh这样的二维拓扑结构中，X-Y维有序路由首先沿x维发送分组，然后沿y维发送分组。从（0,0）到（2,3）的分组首先在X维度上遍历2跳，到达（2,0），然后在y维度上遍历3跳到达目的地。

oblivious

        另一类路由算法是不经意路由算法（oblivious routing algorithm），消息从A到B经过不同的不经意路由路径，但选择这条路径时不考虑网络拥塞。例如，router可以在发送消息之前在备选路径中随机选择。图4 - 1展示了一个例子，从（0,0）到（2,3）的消息可以通过任意一个随机发送Y-X路由或X-Y路由。

        确定性路由是不经意路由的一个子集。

adaptive

        更复杂的路由算法可以是自适应的，其中消息自适应路由从A到B的路径取决于网络流量情况。例如，一条消息最初可能沿着X-Y路线，在（1,0）的东出口链路上发现拥塞。由于这种拥塞，消息会选择使用北面的出站链路前往目的地（见图4 - 1）。

        路由算法也可以分为最小路由算法和非最小路由算法。最小路由算法只选择从源到目的需要最少跳数的路径。非最小路由算法允许选择可能增加源和目标之间跳数的路径。在没有拥塞的情况下，非最小路由会增加延迟，并且由于消息要traverse额外的router和link，功耗也会增加。在拥塞的情况下，选择一条非最小路由来避开拥塞链路，result in lower latency for packets.。

        在详细介绍确定型、不经意型和自适应型路由算法之前，我们先讨论路由算法可能发生的死锁。

避免死锁

在选择或设计路由算法时，不仅要考虑其对时延、功耗、吞吐量和可靠性的影响，而且大多数应用还要求网络无死锁。当多个消息的路径中存在一个knotted cycle时，就会发生死锁。

（knotted cycle: 在自适应路由中，循环是死锁发生的必要条件而不是充分条件，因为可能存在一个循环，但存在一个走出这个循环的方法，比如通过一条逃生路径。打结循环更精确地定义了死锁情况。）

图4 - 2展示了4条gridlocked（deadlocked）消息，它们在等当前被别人使用的links，这就导致了任何消息都不能继续前进。从南边输入端口进入router A的数据包正在等待通过东边输出端口离开，但另一个数据包在等待router B通过南边输出端口离开时，却紧紧抓住了这条链路，而这条链路又被另一个等待在router C离开的数据包所持有。
Deadlock freedom可以通过以下两种方式解决：

路由算法，通过preventing cycles来解决；
flow control protocol，通过防止router缓冲区以循环的方式被获取和持有来解决；

前者将在本章讨论，后者将在5.6章讨论

Deterministic DOR

        路由算法可以用which turns are permitted来描述。

        图4.3a展示了二维网状网络中所有可能的turns，而图4.3b展示了DOR X-Y路由所允许的更有限的turn。

        允许所有turn会导致循环的资源依赖，从而导致网络死锁。为了防止这种循环依赖，某些turn应该被禁止。可以看到，在图4 - 3b中没有任何循环。具体来说，向东或向西传播的信息可以转向北方或南方；但是，向北和向南行驶的信息不允许转弯。在图4 - 2的四个转弯中有两个是不允许的，所以循环是不可能的。

        或者，可以使用Y-X路线，当消息向北或向南旅行时，允许向东或向西turn，但一旦消息是向东或向西旅行，就不允许进一步turn。取决于网络的维度，即沿着X或Y是否有更多的节点，这些路由算法之一将更好地平衡负载与均匀随机流量，因为信道负载在节点较少的维度更高。

        DOR既简单又无死锁；然而，它消除了mesh网络中的路径多样性，从而降低了吞吐量。使用DOR，每个src-dst pair之间只存在一条路径。如果缺乏路径多样性，路由算法将无法绕过网络中的故障或避开拥塞区域。由于路由的限制，DOR不能很好地实现网络的负载均衡。

Oblivious Routing

        使用oblivious routing算法，routing pass的选择与网络状态无关。通过不使用有关网络状态的信息，这些路由算法可以做的比较简单；



        Valiant的随机路由算法是oblivious routing的一个例子。

要使用  Valiant  算法将数据包从源s路由到目的地d ，需要随机选择一个中间目的地d 。
数据包首先从s路由到d ，然后从 d路由到d。
通过先路由到随机选择的中间目的地，然后再路由到最终目的地，Valiant  的算法能够在整个网络中实现流量负载平衡；
这种随机化使任何流量模式看起来都是均匀随机的。
Valiant  算法的负载平衡是以牺牲局部性为代价的；例如
通过路由到中间目的地，网格上近邻流量的局部性被破坏。
跳数增加，这反过来又增加了平均数据包延迟和数据包在网络中消耗的平均能量。
此外， Valiant算法不仅破坏了局部性，最大通道负载也可能加倍，network bandwidth减半。

        Valiant  的路由算法可以限制为仅支持最小路由，方法是将路由选择限制为最短路径以保持局部性。在k-ary n-cube拓扑中，中间节点d必须位于最小象限内；最小的n  维子网络，以 s和d为界定此象限的角节点。

        Valiant的路由无论考虑最小选择还是非最小选择d ‘，都可以使用DOR从s到d ’，从d '到d。如果使用DOR，虽然不会利用所有路径，但比直接从s到d的DOR能达到更好的负载均衡。图4.4展示了使用Valiant算法和最小oblivious路由选择的路由路径。

        在图4 - 4a中，Valiant算法随机选择了一个中间目的地d '。随机选择会破坏局部性并显著增加跳数；在这里，跳数从3跳增加到9跳。为了保持局部性，可以使用最小不经意路由，如图4 - 4b所示。此时，d '只能被选择在由s和d构成的最小象限内，保持最小跳数为3。一个可能的选择被突出显示（这个源-目标对可能有两个其他路径，如虚线所示）。

        Valiant’s routing algorithm和minimal oblivious routing在与X-Y路由结合使用时是无死锁的。oblivious routing algorithm会导致deadlock的一个例子是，randomly chooses between X-Y or Y-X routes，because all four turns from Figure 4.2 are possible leading to potential cycles in the link acquisition graph.

Adaptive routing

        更复杂的路由算法可以是自适应的，即消息从  A  到 B  取决于网络流量情况。例如，一条消息可以沿着  XY 路线，看到  (1,0)  的东出站链路拥堵，因此选择走北出站链路链接到目的地（见图4.1）;

        可以利用本地或全局信息来制定自适应路由决策。自适应路由算法通常依赖本地路由器信息（如队列占用率和排队延迟）来衡量拥塞并选择链路。flow control则通过back pressure的方式，allow congestion information to propagate from the congestion site back through the network.



上图中显示了从一个node, 到另一个node, 可能的最小路径，这里显示了9条path；自适应算法只是用最短路径，可以增加路径多样性的同时，进行负载平衡和fault tolerance；

        自适应路由可以限制在源点和目的地之间采取最短路径。另一种选择是employ misrouting，允许数据包被定向到非最短路由的方向，从而产生非最短路径。当允许misrouting时，活锁（livelock）成为需要考虑的问题。如果没有保证数据包向前传输的机制，活锁可能会发生，因为数据包会一直被misrouting，从而无法到达目的地。我们可以通过限制每个数据包的misrouting次数来解决这个问题，并为多次被misrouting的数据包分配更高的优先级。misrouting会增加跳数，但可以通过避免拥塞（排队延迟）来减少端到端的包延迟。

        采用完全自适应路由算法时，可能会出现死锁问题。例如，图4.1所示的自适应路由是oblivious routing的子集，可能导致死锁。Planar-adaptive routing通过限制自适应性仅限于两个维度，从而限制了处理死锁所需的资源。Duato提出了允许完全路由自适应性的flow control techniques，同时确保无死锁。第5章将讨论无死锁的流控制。

        自适应路由的另一个挑战是inter-message ordering，因为一致性协议所需的。如果消息必须以源发出消息时，相同的顺序到达目的地，自适应路由可能会出现问题。可以使用在目的地重新排序消息的机制，或在路由中可以限制给定类别的消息的发送顺序以防止re-ordering。



Adaptive Turn Model Routing

        我们在第4.3节中介绍了转模型路由，并讨论了如何通过X-Y routing消除四个turns中的两个（如图4.3所示）。在这里，我们将解释如何更广泛地应用turn model来生成无死锁的自适应路由算法。adaptive turn model模型路由算法在保持一定路径多样性和可适应性的同时，消除了实现无死锁所需的最小转弯数。

        对于dimension order routing，二维mesh中  8  个可用转弯中仅允许  4  个可能的转弯。turn model routing通过允许8个转弯中的6个转弯增加了算法的灵活性。每个循环中仅消除一个转弯。

      图4.6说明了三种可能的路由算法。从所有可能的转弯开始（如图4.6a  所示），消除了从北向西的转弯；消除后，可以得出图4.6所示的三种路由算法。

图4.6a显示了西向优先算法；除了消除从北向西的转弯外，还消除了从南向西的转弯。换句话说，消息必须先沿西方向传输，然后才能沿任何其他方向传输。
北向后算法（图4.6b）消除了从北向西和从北向东的转弯。一旦消息转向北方，就不允许进一步转弯；因此，必须最后转向北方。
最后，图4.6c消除了从北向西和从东向南的转弯，以创建Negative-First algorithm。消息首先沿负方向（西和南）传输，然后才允许沿正方向（东和北）传输。

        所有这三种转弯模型路由算法都是无死锁的。图4.7说明了一种无效的可能的转弯消除方法；从北向西的消除方法与从西向北的消除方法相结合可能会导致死锁。图4.7b描述了死锁循环，该循环可能由使用图  4.7a  中指定的转弯的一组消息导致。

Odd-even turn model路由建议根据当前节点位于奇数列还是偶数列来消除两次转弯。例如，

当数据包正在穿过偶数列中的节点时，禁止从东到北和从北到西进行两次转弯。
对于穿越奇数列节点的数据包，禁止从东向南和从南向西转弯。

有了这些限制，奇偶转弯模型就不会出现死锁，前提是不允许180°转弯。奇偶转弯模型比其他转弯模型算法（如“西优先”）具有更好的适应性。

使用“West-First”，位于起点西侧的目的地没有灵活性；
使用odd-even routing，则可以根据给定列允许的转弯次数灵活调整。

在图4.8 中，我们将负向优先转弯模型路由应用于两个不同的源目的地对。在图4.8a 中，显示了 (0,0) 和 (2,3) 之间的三条可能路线（可能更多）；允许从北向东和从东向北转弯，从而实现很大的灵活性。然而，在图4.8b 中，算法只允许一条路径从 (0,3) 路由到 (2,0)。路由算法不允许消息从东向南转弯。

负向路线必须首先完成，导致此源目的地对没有路径多样性。如该示例所示，转弯模型路线比维度顺序路线提供了更大的灵活性和适应性，但它仍然有一定的限制性。

Multicast Routing

到目前为止，我们重点关注unicast（即一对一）路由算法。然而，经常会出现一个核心需要向多个核心发送相同消息的情况。这称为broadcast（如果需要向系统中的所有核心发送信号）或multicast（如果需要向系统中的一部分核心发送信号）。在共享内存缓存一致性系统中，基于广播和基于有限目录的一致性协议中都可以看到这种示例。在消息传递系统中，MPI_Bcast 等例程需要这样做。multicast的一种简单实现是简单地发送多个单播，每个目的地一个。但这会大大增加网络中的流量，导致网络延迟和吞吐量不佳;

已经有一些支持multicast routing on-chip的提案。Virtual Circuit Tree Multicasting (VCTM) 在每个router上添加small routing tables。对于每个multicast ，在multicast 之前，每个目的地都会发送一个unicast setup packet，以配置沿XY路由的路由表。同一multicast目的地集的所有设置数据包都带有唯一的 VCT ID，该 ID 对应于路由表中的索引。Each setup packet appends its output port to the VCTID entry in the routing table，从而设置multicast flit 应从哪个方向分叉。所有后续到此目的地的multicast 都将注入此 VCT ID，并在网络中的路由器上进行适当分叉。

Whirl 是一种针对广播优化的路由算法，它试图动态创建负载平衡的广播树，允许广播使用不同的链路组合，从而提高链路利用率和吞吐量。在这两种设计中，路由器都需要支持从多个方向分叉同一个flit。

Routing On Irregular Topologies

本章中对路由算法的讨论假设了规则拓扑，例如圆环或网格。在上一章中，我们探讨了使用不规则拓扑对由异构节点组成的 MPSoC 的功耗和性能优势。

不规则拓扑在路由算法的开发中可能需要特殊考虑。不规则网络的常见路由实现依赖于source table routing或node table routing。指定路由时必须小心谨慎，以免引发死锁。例如，如果由于mesh网络中存在过大的核心而导致某些连接被移除，则Turn model routing可能不可行。Up*/Down* 路由是一种流行的无死锁路由算法，适用于不规则拓扑，该算法从根节点开始将每条链路标记为 Up 或 Down。所有 flit 只能从 Up 链路转换到 Down 链路，而不能相反，从而保证无死锁。

IMPLEMENTATION

在本节中，我们将讨论路由算法的各种实现选项。路由算法可以在源节点或每个路由器内使用查找表来实现。组合电路可以作为table-based routing的替代方案。实现有各种各样的权衡，并不是每种实现都能实现所有的路由算法。表4 - 1举例说明了如何实现这三个不同类别的路由算法。

Source Routing

将路由方式，嵌入到source端发送的packet的header中，这种方式称之为源端路由；

例如，图4.1中的 X-Y 路由可以编码为，而 YX 路由可以编码为 < E;E;N;N;N;Eject >；Y-X路由，可以编码为< N;N;N;E;E;Eject >。

在每一跳，路由器将读取路由最左边的route header，将数据包发送到指定的outgoing link，并剥离对应于当前跳跃的header的部分；

source routing有几个好处。

首先，通过在源端选择整条路由，节省了网络中每一跳的延迟，因为不需要计算或查找路由。每个router的路由硬件资源也就节省了。一旦源端确定好了路由，整个路由过程中，不需要组合路由逻辑或路由表。
其次，source routing tables可以重新配置以应对故障，并支持不规则拓扑。表中每个src-dst pair可以存储多条路由（如表4 - 2所示），每个数据包可以随机选择，以提高负载均衡。

source routing的缺点包括在每个src的network interface存储路由表和在每个分组中存储整个路由路径所需的比特开销；这些路径的长度是任意的，并且可以随着网络规模的增大而增大。对于一个5端口switch，每个路由步骤被编码为一个3位二进制数。就像数据包必须能够处理任意长度的路由路径，source table也必须被设计成有效地存储不同长度的路径。此外，source routing在源节点选择整条路由，无法利用动态的网络条件避免拥塞。但是，如前所述，可以将多条路由存储在表中，并随机选择或按给定概率选择，以改善网络中的负载分布。

Node Table-based Routing

更复杂的算法是利用routing tables at each hop来实现的，routing tables存储了数据包到达特定目的地应该采取的outgoing link。通过在每一跳（而不是在源端）访问路由信息，可以实现自适应算法，并且可以在决策中利用每一跳的网络拥塞信息;

表4.3为west-first turn model路由算法在3-ary 2-mesh上的routing table。每个node的table将由与其节点标识符相对应的行组成，每个目的地最多有两个可能的outgoing links。通过在每个节点表中实现turn model的路由算法，可以实现一定的自适应性。

与source routing相比，node-based routing需要在每个节点建立更少的routing table。每个routing table只需要存储路由信息，就可以为每个目的选择下一跳，而不是整个路径。当每个目的地包含多个输出时，基于节点的路由支持一些自适应性。

利用拥塞或故障的本地信息，可以使路由选择偏向非拥塞链路或非故障路径。
基于节点的路由表也可以被编程。通过允许路由表的变化，使得路由算法能够更好地容忍网络中的故障。

节点路由表最大的缺点是数据包延迟的增加。Source routing需要一次查找来获取数据包的整个路由路径。在基于节点的路由中，查找的延迟必须在网络的每一跳中增加;

Combinational Cirtuits

同样，消息可以编码目的地的坐标，并使用每个router的比较器来确定是接受（eject）还是转发消息。由于开销小，简单的路由算法通常以组合电路的形式在router中实现。

使用source routing时，packet中，必须要有一定的空间空间，以容纳指定整个路径所需的btis信息。而使用组合电路的路由只要求分组携带dst id。实现该路由算法所需的电路可以非常简单和执行延迟非常低。图4 - 9给出了一个基于二维网格中当前缓存占有率计算下一跳的电路示例。另外，route selection可以实现DOR，而不是based on queue lengths。

通过在组合电路中实现路由决策，该算法针对一种拓扑结构和一种路由算法。table-based的策略牺牲了通用性和可配置性。尽管使用电路计算路由路径中的下一跳速度快且简单，但与基于源的路由相比，这种计算增加了分组遍历的延迟。与节点路由一样，下一个输出必须在网络的每一跳确定。第6章会讨论，这种路由计算可以在路由器遍历中添加一个流水线阶段。