Abstract

Abstract—Avoiding routing deadlock is an important compo­ nent of an interconnection network. For large-scale systems with high-radix topologies that leverage non-minimal adaptive routing, virtual channels (VCs) are commonly used to prevent routing deadlock. However, VCs in large-scale networks can be costly because of deep buffers and restrict VC usage. In this work, we propose BoomGATE for deadlock avoidance in large-scale networks. In particular, BoomGATE consists of two components Restricted Intermediate-node Non-minimal Routing (RINR) al­ gorithm and opportunistic flow control (OFC) which both exploit the low-diameter characteristics of high-radix networks while maximizing path diversity within the topology. We identify how routing deadlock in fully-connected topologies are caused by non­ minimal routes and propose to restrict the non-minimal routing to ensure deadlock freedom without additional virtual channels. We also propose an algorithm that ensures path diversity is loadbalanced across all nodes in the system. However, since path diversity is restricted with the RINR algorithm, complement RINR algorithm with opportunistic flow control (OFC) where “illegal routes” are allowed if and only if sufficient buffer can be guaranteed to ensure cyclical dependency does not occur. We propose both a static and dynamic OFC implementation. We evaluate the performance of BoomGATE and demonstrate there is minimal performance loss compared to global adaptive routing, while reducing the amount of buffers required by 50%.

避免路由死锁是互连网络的重要组成部分。对于使用非最小自适应路由的高基数拓扑的大规模系统，虚拟通道(VCs)通常用于防止路由死锁。然而，大规模网络中的风险投资可能代价昂贵，因为有很深的缓冲区和限制vc的使用。在这项工作中，我们提出BoomGATE来避免大规模网络中的死锁。值得一提的是，BoomGATE由两个部分组成——受限中间节点非最小路由(RINR)算法和机会流控制(OFC)算法，它们都利用了高基数网络的低直径特性，同时最大化了拓扑中的路径多样性。我们确定了全连接拓扑中的路由死锁是如何由非最小路由引起的，并提出了限制非最小路由以确保死锁自由而不需要额外的虚拟通道。我们还提出了一种保证路径多样性在系统中所有节点负载均衡的算法。然而，由于RINR算法限制了路径的多样性，当且仅当保证有足够的缓冲区以确保不发生循环依赖时，使用机会流控制(opportunistic flow control, OFC)的RINR算法才允许“非法路由”。我们提出了静态和动态OFC实现。我们评估了BoomGATE的性能，并证明与全局自适应路由相比，它的性能损失最小，同时所需的缓冲区数量减少了50%

看一下这篇文章introduction的第一段：
互连网络是大规模系统中的重要部分->
拓扑是互连网络的关键组件->
由于引脚带宽不断增长，最近更多的是利用高阶路由器来实现高阶拓扑+举例（至此引出高阶拓扑）->
这些高阶拓扑已经被应用到很多实际系统中+举例（强调高阶拓扑的重要性）->
高阶拓扑的一个特性是全连接+举例说明->
本文就是要在高阶拓扑中利用全连接的特性来避免死锁而不需要额外的VC

平衡，遗忘非最小全局自适应路由

Routing Deadlock:

​ Deadlock is defined as occurring in the network if and only if there exists one or more cyclic dependency in channel dependency graph (CDG) of the network.

1. Question?

2. Method?

RINR

bRINR

sOFC

dOFC

  1. 我们通过新的路由算法和流量控制，提出BoomGATE -避免死锁的高基数路由器，不需要额外的VCs。
  2. 我们提出一类非最小的全局自适应路由(RINR)，其中非最小路由受到限制，并增强RINR以实现均衡的RINR，其中非最小路由的路径多样性在所有节点之间均衡。
  3. 我们提出了一种新的流量控制——机会流控制(OFC)，它可以在不造成死锁的情况下利用非法路由，并在缓冲区未充分利用bRINR时实现更高的性能。
  4. 我们评估了我们提出的路由算法和流量控制的性能，并证明了与全局自适应路由相比，性能退化是最小的，同时减少了大规模系统路由器所需的缓冲区数量

死锁定义：

路由死锁是由于对网络资源[16]的依赖造成的。死锁的理论定义是:当且仅当网络[15]的信道依赖图(CDG)中存在一个或多个循环依赖时，才会发生在网络中。

通常两种方法：避免死锁和死锁恢复

避免：需要额外得资源 VC

恢复：需要牺牲性能，假定死锁不经常发送

RINR

定理:如果非最小路由用RINR实现全局自适应路由，那么在全连通拓扑中，路由算法只需1vc就不会死锁。

全局自适应路由[51]包括最小路由和非最小路由。

情形一:最小路由:最小路由只遍历一个网络通道，不会导致路由死锁。

案例二:非最小路由:基于通道依赖图(CDG)[15]，如果在通道资源中没有周期性依赖，则可以避免死锁。如果所有资源都是严格有序的，那么死锁就会被避免。通过只使用合法的非最小路由，网络访问通道中的所有非最小路由将严格按照递增的顺序排列，从而不会出现周期性的通道依赖关系。

对于网络规模为N的情况，每个节点使用RINR路由算法的非最小路由的平均数目为2 (N - 2)。

对于2跳非最小路由，为了通过路由限制来保证避免死锁，需要避免所有可能的死锁。可能造成死锁的节点(或通道)的最小数目是3。因此，被选择的3个通道的不同可能组合是NP3，因为在死锁中顺序很重要。对于每一个死锁的可能性，3个路径中的1个必须被禁用-因此，3个NP3非最小路径被RINR禁用(或者允许| NP3路径)。由于网络中源-目的路由数量为N(N - 1)，平均非最小路由(H avg_nonmin)为

算法2

前半部分(从第5行开始)表示如何对C1通道重新编号。每个禁用路由(第7行)都会有效地减少中间节点的数量，而启用路由(第8行)会增加特定非最小路径的中间节点数量。f o r循环执行最终修改一行和一列，如表V(a)所示。

算法的后半部分(第12行)描述了如何重新编号C2通道以负载平衡非最小路径多样性。类似地，一次f o r循环执行会导致如表V(b)所示的修改。

实际意义：RINR/bRINR为大规模网络中的非最小全局自适应路由提供了一个实用的替代方案，因为使用了基于表的路由，同时使用了最小和非最小的路由表[37]。然而，由于路由表的条目有限，并不是所有的非极小路由都能被利用。因此，与其随机生成中间节点来填充表，不如根据bRINR路由算法来填充非极小路由表中的非极小路径–将任何性能影响降到最低，同时避免了对额外VC的需求，并且可以在目前的大规模系统中轻易实现。路由表通常由一个单独的管理系统（例如Cray系统中的硬件监管组件[9]）管理，该系统负责更新/维护路由表，可以利用它来平衡路径的负载，同时最大限度地减少VC的需求。

3. Answer?

Introduction

1.为什么研究这个课题?

2.目前这个课题研究到了哪个阶段?

3.作者的理论基于哪些假设?

Conclusion

1.文章的缺陷

2.关于该课题，作者的构思?

image-20210622090815582