摘要

本文主要讨论如何使用Benes网络完成排列的置换操作，介绍Benes网络的构造，以及具体的路由方式。

置换排列

这里的排列指一个n个不同元素的序列，不同的顺序代表不同的排列。比如$[1,2,3,4]$和$[2,1,4,3]$是两个不同的排列。

这里我们考虑如何利用Benes网络，从一个排列变为另一个排列。

矩阵乘法的角度看置换排列

从数学的角度来看，这是一个矩阵的乘法问题，也就是将排列当作一个向量，然后乘以一个置换矩阵，就可以得到另外一个排列。

比如，我们需要将$a=[1,2,3,4]$置换为$b=[2,1,4,3]$. 这时，我们需要一个置换矩阵$P$.使得$b=a\times P.$

我们观察到$b$中的第一个元素是$a$中的第二个元素，而$b$中的第一个元素是$P$的第一列和$a$的内积，因此，置换矩阵$P$的第一列第二行的元素为1，第一列中的其他元素为0. 如此类推，可以得到置换矩阵
$$P=\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right].$$

假设排列的长度为$n$，那么显然，需要$n\times n$的置换矩阵，而乘法的复杂度是$O(n^2)$.

从交换原理的角度看置换排列

从交换原理来看，置换排列其实是一个路由问题。输入为$a$，经过交换网络后，变为$b$. 在$a[i]=b[j]$时，就是$a[i]$的目的地址为$b[j]$.

由于我们希望可以完全并行的穿过整个交换机，那么交换机的拥塞应该为1.也就是在任意一步，不会存在两个元素跑到同一个节点。我们知道Benes网络具有这个特点。一个层数为$2\log n-1$的Benes可以完成$n$维向量的重新排列。

Benes网络的构造

Benes网络的构造是通过递归构造的。Benes网络的输入节点和输出节点一样多，一般为2的幂次。我们用$B_2$表示输入节点为2的Benes网络。则$B_2$为

然后$B_4$的基本构造是由两个$B_2$，然后再加上$4$个输入节点和$4$个输出节点。然后上面的两个输入节点连接到下面$B_2$的节点。下面的两个输出节点连到上面的一个$B_2$.对称构造输出节点。如图所示：

$B_8$是使用两个$B_4$，加上8个输入节点和8个输出节点构造：

Benes路由方法

Benes的路由和构造的过程相反，首先从两边填充路由信息，然后逐步向中间填充。

下面是填充路由信息的具体算法步骤：

0：将输入和输出分别填充到输入节点和输出节点；

1：对于输入节点来说，由于不能存在拥塞，所以，具有相同目的地的节点不能在下一步的同一个子网中出现。而对于输出节点来说，可以由同一个节点到达的输出节点的不能来自于同一个子网络。而我们注意到，去掉输入和输出后的Benes网络是两个完全分开的Benes网络，中间不存在连接。因此，可以将不可以在同一个子网中的节点连接起来，构造一个图；

2：对第1步形成的图2着色，每一个颜色走一个子Benes网络，从而可以填充下一步的输入节点；

3：根据填好的下一步输入节点，和当前的输出节点，填充子Benes网络的输出节点。

4：重复1-3步，直到填充完所有的节点路由信息。

下面，我们给出一个$B_8$网络路由的例子，输入为$[1,2,3,4,5,6,7,8]$，输出为$[2,6,5,8,4,7,1,3]$.

首先，填充第一列和最后一列：

根据输入节点，我们知道，1-5，2-6，3-7，4-8 不能输入到同一个子Benes网络中；

根据输出节点，我们知道，2-4，6-7，5-1，8-3 不能来自同一个子Benes网络。

因此，我们得到一个顶点为 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } \{1,2,3,4,5,6,7,8\} {1,2,3,4,5,6,7,8}，边为 { 1 − 5 , 2 − 6 , 3 − 7 , 4 − 8 , 2 − 4 , 6 − 7 , 5 − 1 , 8 − 3 } \{1-5, 2-6, 3-7, 4-8, 2-4, 6-7, 5-1, 8-3\} {1−5,2−6,3−7,4−8,2−4,6−7,5−1,8−3}的图。

我们对图进行2着色：

然后，我们根据着色结果填充下一步的输入，蓝色的根据网络输入到上面的$B_4$网络，橙色的输入到下面的$B_4$网络：

然后根据下一步的输入，我们知道需要填充的下一步输出中，2，5，7，8 一定来自上面的$B_4$网络，1，6，3，4 一定来自下面的$B_4$网络。

我们根据当前的输出，填充$B_4$网络的输出：

下面，我们继续填充上面一个$B_4$网络，下面的$B_4$填充的方法是相同的。

上面一个$B_4$网络的输入为$[5,2,7,8]$，输出为$[2,7,5,8]$。

得到边为 { 5 − 7 , 2 − 8 , 2 − 5 , 7 − 8 } \{5-7,2-8,2-5,7-8\} {5−7,2−8,2−5,7−8}的图，然后进行2着色：

填充$B_2$网络的输入：

因此，2，7一定来自下面的$B_2$网络，5，8 一定来自上面的$B_2$网络：

下面是完整的路由图：

使用Benes网络，每一层我们只需要两种旋转，再加上选择，就可以完成路由，从而实现置换重排。

参考文献

[1] https://blog.csdn.net/qq_19830591/article/details/127789767