【计算机体系结构】Banyan Network

本文在介绍Banyan网络之前，先介绍一下最基本的CrossBar网络。

CrossBar网络

如下图所示，Crossbar网络是互连网络中最一般的形式，是最严格意义下的无阻塞开关网络。Crossbar网络由$N$个输入节点和$N$个输出节点构成，共有$N^2$个交叉点，通过控制每个节点开关的状态，可以实现任意输入与输出之间的无阻塞连接，且每个输出通道都可以独立输出任意一个输入通道的数据。CrossBar网络的缺点是当节点数$N$增加时，Crossbar网络的开关数也会迅速增加，网络复杂度迅速增大。因此，CrossBar网络的可扩展性较差。

switch是构成CrossBar网络的基本单元，每个switch有两种状态：“BAR”代表直通状态，“CROSS”表示交换状态。这两种状态如下图所示：

即，如果输入端口$i$和输出端口$i$直连（$i=0,1$），那么状态就是Bar，如果输入端口0连接输出端口1，输入端口1连接输出端口0，那么状态就是Cross，意味着交叉。

Banyan-network

如图所示，Banyan网络由多级构成，级数等于$lo{g}_2^N$，其中$N$为节点数。可以看到，Banyan网络的每一级，都是由$N/2$个switch构成的，如果以switch为基本单元，那么上图的Banyan网络可以由下图表示：

图中方框所表示的2x2 xbar就是一个switch单元，当switch单元的控制信号为1时，switch处于cross状态，为0时则处于bar状态。
下面来看Banyan网络的一个有趣的功能，即它可以实现数据的汇聚和散射。考虑以下场景：数据分离（去无效数据），且汇聚有效数据（按照原始的相对顺序排列）

假设数据分离场景有如下约束与需求：
1、 输入数据总位宽一定（例如固定256bit=32bit×8）.
2、 输入数据可以被均分为一系列数据量相同的最小单元（例如上图中数据单元的位宽是32bit）.
3、 无效数据可以在输入数据的任意位置.
4、 数据输出时，输入有效数据在低位密排，且输入有效数据的相对位置保持不变.

我们仍旧以上图为例，来阐述Banyan网络是如何实现数据的汇聚和散射的。在上图中，每一个节点（图中的圆圈）表示一个数据，圆圈的颜色是白色，表示该数据无效，因而需要被去除，圆圈的颜色不是白色，表示数据有效，需要汇聚。在上图中，只有数据2，4，6，7是有效的，其余数据均是无效的，因此，对这个8个数据做汇聚后：

• 数据2应该落在位置0；
• 数据4应该落在位置1；
• 数据6应该落在位置2；
• 数据7应该落在位置3；

假设每个数据都携带一个valid信号(1bit)，每个源数据的位置为src_idx(3bit, 0~7)，那么：

1. 对于节点$i$，根据下面的式子计算它的目的节点位置：
   $$dst\_idx=valid[0]+valid[1]+...+valid[i-1]$$
2. 根据节点自身的位置src_idx和1中计算得到的目的节点位置dst_idx，计算路由信息：
   $$routing\_ctrl=src\_idx\oplus dst\_idx$$
   其中符号$\oplus$表示按位异或。
3. 每个节点，根据2中计算得到的路由信息routing_ctrl路由到指定的目的节点（stage i的控制信号为routing_ctrl[i]）。

例如，在上图中，源节点4需要路由到目的节点1，则它的路由控制信息routing_ctrl为3'b100^3'b001=3'b101：

• 在stage0，routing_ctrl[0]=1，所以向下走，路由到stage1的第3个switch；
• 在stage1，routing_ctrl[1]=0，所以向上走，路由到stage2的第1个switch；
• 在stage2，routing_ctrl[2]=1，所以向上走，路由到输出节点1；

并且，我们可以看到，在进行数据的汇聚时，Banyan网络是单向无阻塞的，如果采用逆Banyan移位网络（如下图所示），则会出现路由冲突。

注：该网络的路由信息为dst_idx，xbar的控制信息为0表示走输出端口0，为1表示走输出端口1。例如上图中的目的节点为3=3'b011，因此先从stage0的第2个xbar的端口0出，然后再从stage1的第0个xbar的端口1出，最后从stage2的第1个xbar的端口1出，最后达到目的节点3。这里，dst_idx[i]控制stage {2-i}的xbar。

附：数据汇聚工程代码链接