互联网络

互联网络的设计目标

目的：处理单元之间、处理单元与存储分分体之间的连接关系
目标:
1)不过分复杂，以降低成本
2)灵活，满足算法和应用需求
3)传递步数越少越好
4)用基本构件组合而成，支持多级扩展

互联函数

定义：表示互连网络的出端号和入端号的一一对应关系。
简单解释：对于所有的入端0、1、…、j、…、N-1，同时存在入端j连至出端f(j)的函数对应关系:f(j)=i。

互连函数的表示

• 连线图表示

互连函数可以直接用结点间的连线图表示，但有时显得繁琐，也难以体现出连接上的内在规律。

• 二进制编码表示
  常用一种简单的函数式表示互连函数，即把所有入端x和出端f(x)都用二进制编码，从两者的二进制编码上找出其函数规律。F(dn…d1d0)=bn…b1b0

基本的单级互连网络

立方体单级网络

立方体单级网络互连函数一般式

$Cube_i$Cubei​表示$P_i$Pi​取反。

• 以上面的三维立方体结构为例：
  3种互连函数：Cube0、Cube1和Cube2，
  其连接方式
  
  Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0,1,2) 上0、1互反，其余各位不变。

特点:

• N个结点的立方体单级网络共有n=lbN种互连函数
• 单级立方体网络的最大距离为n（需要变化几次）
• 任意两个结点之间至少有n条不同的路径可走
• 当维数n＞3时称超立方体(HyperCube)网络。

PM2I单级网络

函数形式：

• 0≤j≤N-1,0≤i≤n-1,n=lbN。它共有2n个互连函数。
• 由于$PM2_{+(n-1)}=PM2_{-(n-1)}$PM2+(n−1)​=PM2−(n−1)​,因此PM2I互连网络只有2n-1种互连函数是不同的。
• PM2I单级网络的最大距离为$┌n/2┐$┌n/2┐

例子：

对于N=8的三维PM2I互连网络的互连函数，有$PM2_{+0}$PM2+0​、$PM2_{-0}$PM2−0​、$PM2_{+1}$PM2+1​、$PM2_{-1}$PM2−1​、$PM2_{±2}$PM2±2​等5个不同的互连函数

N=8的三维PM2I互连网络的互连函数

$PM2_{+0}$PM2+0​:(01234567)
$PM2_{-0}$PM2−0​:(76543210)
$PM2_{+1}$PM2+1​:(0246)(1357) 　
$PM2_{-1}$PM2−1​:(6420)(7531)
$PM2_{±2}$PM2±2​:(04)(15)(26)(37)

混洗交换单级网络

混洗交换单级网络=全混(Perfect Shuffle)+交换(Exchange)。

全混(Perfect Shuffle)

循环左移的结构， 式中,n=lbN, Pn-1Pn-2…P1P0为入端编号的二进制码。

重要特性：

• 与Cube函数不同，Shuffle函数是不可逆的。即单向性。
• 当经过n次全混后，全部N个处理单元便又恢复到最初的排列次序。
• 在多次全混的过程中，除了编号为全“0”和全“1”的处理单元外，各个处理单元都遇到了与其他多个处理单元连接的机会(不是所有单元)

交换(Exchange)

引入原因：
由于单纯的全混互连网络不能实现二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数

实线表示交换，虚线表示全混。

• 特点：在混洗交换网络中，最远的两个入、出端号是全“0”和全“1”，它们的连接，需要经过n次交换和n-1次混洗，所以混洗交换网络的最大距离为2n-1。

蝶形单级网络

二进制地址的最高位和最低位相互交换位置。