Interconnection-Networks-ch4.md

Butterfly Networks

俩个主要的拓扑家族

蝶形网络是最基本的间接网络。

对于交换机度数为$\delta = 2k, H = \log_kN +1$的N个节点的网络，BN拥有最小的直径。

缺点：

1. no path diversity: there is exactly one route from each source node to each destination node.
2. the butterfly cannot be realized without long wires that must traverse at least half the diameter of the machine.

4.1The Structure of Butterfly Networks

k-ary n-fly

2-ary 4-fly

​ k-ary n-fly网络由$k^n$个源终端节点，n个阶段, 每个阶段$k^{n-1}$ k×k crossbar switch节点以及最后$k^n$目的地终端节点组成。

​ 关于网络中报文的走向问题。

根据每一个发出报文的终端编号可以决定不同路由路径。我们使用 n-digit radix-k number, ${d_{n−1},d_{n−2},…,d_0}$. 来表示每一条路径。

对于k-ary n-fly网络。每一级有$k^{n-1}$个路由器，所以需要有n-1比特来进行选择。前n−1个数字${d_{n−1},d_{n−2},…,d_1}$.标识交换机，最后一个数字$d_0$标识交换机上的终端也就是决定了最终出口的选择。具体的使用如下：

1. ​ 从输入节点开始，比如9这个输入节点，对应的二进制为1001；前三位为100，那么第0级交换机选择为4号。
2. 此时，d_0可以随机选择为0或者1，这是再将d_0和d_3进行交换，可以得到前三位000或者100，这样第1级交换机可以选择为1，0或者1，4.
3. 依次类推，最好已经决定输出的终端。

具体来说：第一级设置dn−1，第二级设置dn−2，依此类推，最后一级设置d0已处于正确位置，

4.2 Isomorphic Butterflies（同构）

网络K，其节点和信道集定义：$K=(N^*，C)$。

如果$K_1=(N_1,C_1),K_2=(N_2,C_2)$是同构的 ：

​ 顶点中存在一个置换$\pi$，对于边${u,v}\ \in C_1$存在${\pi(u),\pi(v)} \in C_2$

4.3 Performance and Packaging Cost

​ 对于k-ary,n-fly网络：

​ 交换节点的度$\delta _{fly}= 2k$

​ 信道二等分(N是偶数)$B_{C,fly } = \frac{N}{2}$

​

​ 信道负载

计算出两层包装层次结构下蝶形网络的通道宽度：

在均匀负载且γ= 1的情况下，理想吞吐量：

蝶形网络的目标：

​ 目标是首先获得最大的吞吐量，其次是最大程度地减少消息延迟。

为此选择最大的K

这个k值给出了最小的直径，这使得延迟的H部分最小化，同时使信道带宽最大化。这也最大限度地提高了理想的吞吐量并最小化了序列化延迟。任何小于此值的k都不会提高吞吐量，只会由于额外的跃点计数而增加延迟.

4.4 Path Diversity and Extra Stages

没有路径多样性