Shuffle-exchange network 的 bisection width

shuffle-exchange network是一种interconnection network，可用于并行计算中multiple processors的组织。

它的diameter比较容易看出来是 ，但是bisection width可能不那么直观，这里提供一个我个人的思路：

先把switches分成数量相等的两个集合，组成两个子网络，最容易想到的分割方法就是按最高有效位是0还是1划分，按照Figure 2.9就是把上下两行switches分开。无向边只出现在最低位相同的两个节点间，不用考虑；自环只在全0和全1的节点出现，也不用考虑；只考虑左循环移位导致的有向边。

显然，这些有向边构成了一个个环，一个环在两个子网络间产生一个出度一个入度，所以一个环增加1的bisection width，环的个数等于节点二进制编码的pattern个数，一个pattern对应一组循环移位。pattern的个数很难计算，所以我们这样来考虑，一共由n个节点，也就是由n个二进制编码，一个pattern对应的编码个数位大约是（有些pattern会比少），所以pattern的个数 ，也就是bisection width 

width shuffle exchange