片上网络NoC（5）——非直连拓扑

一、前言

二、概念阐述

三、交叉开关

四、蝶形网络

五、clos网络

六、fat tree网络

6.1 clos网络的折叠过程

七、总结

一、前言

本文继续介绍片上网络的拓扑，在之前的文章中，我们已经介绍了片上网络的拓扑指标和直连拓扑的相关内容，这些将是继续阅读本文的基础：

片上网络NoC（3）——拓扑指标https://ztzhang.blog.csdn.net/article/details/136106748?spm=1001.2014.3001.5502片上网络NoC（4）——直连拓扑https://ztzhang.blog.csdn.net/article/details/136109452?spm=1001.2014.3001.5502 本文中，我们将详细介绍片上网络中的非直连拓扑。

二、概念阐述

非直连拓扑指的是所有终端节点通过一个或多个中间交换节点（switch node）相连的网络拓扑。与直连拓扑中每个节点既是终端节点又是交换节点不同，非直连拓扑中终端节点与交换节点是彼此分离的。只有终端节点是流量的源（发出新的流量）或目的地（处理输入的流量而不向下继续传递），中间交换节点只是流量的中转站（将流量从输入送到指定的输出）。

三、交叉开关

最简单的非直连拓扑是交叉开关（crossbar），一个交叉开关通过 n×m 个简单的交换节点连接了n个输入和m个输出。其中，n个输入和m个输出进行全连接，每个输入都连接到所有的m个输出。这种结构是非阻塞的，因为它总是可以将发送方与特定的接收方直接连起来。

四、蝶形网络

蝶形（bufferfly）网络是非直连拓扑的典型例子，可以描述为k-ary n-fly。该网络具有 $k^{n}$ 个终端节点和n级交换节点，每级含 $k^{n-1}$ 个交换节点。换句话说，k是交换节点的入度/出度，n是交换节点的级数。（入度/出度指的是输入/离开交换节点的链路数，由于蝶形网络中交换节点的输入、输出链路数相等，所以节点的入度、出度也相等，为节点度的一半。）

下图是一个2-ary 3-fly的蝶形网络：

我们不妨假设左侧的圆形节点为源节点，右侧的圆形节点为目的节点，这样的圆形节点可以统称为终端节点。中间的方形节点则为交换节点。

蝶形网络最大的缺点是缺失路径多样性并缺少对网络局部性的利用。

五、clos网络

经典的 clos 结构是一个三段的网络，每一阶段由若干数量的 crossbar 开关组成。通常使用三元组（m, n, r）来表示一个 clos 的参数：

m 是中间阶段 switch 的数量。
n 是每个input/output switch 的端口数量。
r 是 input、output 阶段 switch 的数量。

每个中间级的switch 会和所有的 input switch 和 output switch 相连。

第一阶段的 r 个 input switch 是 n x m 的 crossbar，每个 switch 将各自 n 个输入端口连接到 m 个 middle switch 上。
第二阶段的 m 个 middle switch 是 r x r 的 crossbar，每个 switch 将 r 个 input switch 与 r 个 output switch 相连。
第三阶段的 r 个 output switch 是 m x n 的 crossbar，每个 switch 将 m 个 middle switch 与 n 个输出端口相连。

六、fat tree网络

fat tree网络在逻辑上是一个二叉树结构，物理上各个节点内部的布线资源不同，距离根节点越近的节点内部的连线资源越多。

从另一个角度来说，一个fat tree网络可以由clos网络折叠而成，因为fat tree网络实际是clos网络在根节点处将自己对折，因此fat tree网络逻辑上是一个5级的clos网络（即信号从输入路由到输出需要最多5跳）。

根节点处存在多个可以连接左右两边的节点，因此fat tree网络具有路径多样性。在fat tree网络中，消息先沿着树结构向上路由，直到找到目的地节点的祖先节点，之后向下路由到指定目的节点。这种路由方式使fat tree 网络可以很好地利用节点之间的局部性。尽管更高层级的节点之间的链路更宽，我们始终认为fat tree 网络中每一个交换节点的逻辑上的度为4。

6.1 clos网络的折叠过程

一个clos网络可以交换内部各个节点的位置，并沿着中间级交换节点折叠，使输入级与输出级完全重合，输入终端节点和输出终端节点完全重合，然后将重合的节点合并为同一个节点，并将节点之间的连接由单向变为双向，从而得到折叠的 clos 网络，折叠过程如下图所示。

一个 clos 网络可以通过从中线折叠的方式，将输入级和输出级交换节点共享。前文中的fat tree结构就展示的是一个 5 级 clos 网络被折叠后的样子，我们依然可以用三元数组（2,2,4）来表示它，而这样的网络的中间级又是由3 级参数为（2,2,2) 的clos网络构成的。这个clos网络沿着最上面一行的交换节点进行折叠。