第四章 互联网络

互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中节点之间的相互连接。
互连网络己成为并行处理系统的核心组成部分，对整个计算机系统的性价比有着决定性的影响
三大要素：互连结构，开关元件，控制方式

互联类型

  • WAN

  • LAN

  • SAN

    Storage or system area work

互连网络

交换函数（Exchange）

Ek(xn−1xn−2xn−3...x2x1x0)=xn−1xn−2‾xn−3...x2x1x0E_k(x_{n-1}x_{n-2}x_{n-3}...x_2x_1x_0) = x_{n-1}\overline{x_{n-2}}x_{n-3}...x_2x_1x_0

把网络输入数组中的第k位（从低位开始）进行反转，如E(1110) = 1010, 15输入对10输出

image-20240613211745584

立方体（Cube）

image-20240613163725285

对立方体网可以使用交换函数，如

Cube0（010）= 011 （x轴）

Cube1（101）= 111 （z轴）

Cube2（000）= 100 （y轴）

可以发现，用交换函数构成的互连网络的结点度为n，网络直径为n

全混洗函数（Shuffle）

S(xn−1xn−2...x2x1x0)=xn−2...x2x1x0xn−1S(x_{n-1}x_{n-2}...x_2x_1x_0) = x_{n-2}...x_2x_1x_0x_{n-1}​

就是进行循环左移

逆混洗

S−1(xn−1xn−2...x2x1x0)=x0xn−1xn−2...x2x1S^{-1}(x_{n-1}x_{n-2}...x_2x_1x_0) = x_0x_{n-1}x_{n-2}...x_2x_1

就是进行循环右移

子混洗

S(k)(xn−1xn−2...xkxk−1xk−2...x2x1x0)=xn−1xn−2...xkxk−2...x2x1x0xk−1S_{(k)}(x_{n-1}x_{n-2}...x_{k}x_{k-1}x_{k-2}...x_2x_1x_0) = x_{n-1}x_{n-2}...x_{k}x_{k-2}...x_2x_1x_0x_{k-1}

最低k位进行局部的循环左移（注意，不包含序号为k的位，因为最右边是0）

超混洗

S(k)(xn−1xn−2...xn−kxn−k−1...x2x1x0)=xn−2...xn−kxn−1xn−k−1...x2x1x0S^{(k)}(x_{n-1}x_{n-2}...x_{n-k}x_{n-k-1}...x_2x_1x_0) = x_{n-2}...x_{n-k}x_{n-1}x_{n-k-1}...x_2x_1x_0

最低k位进行局部的循环左移（注意，不包含序号为k的位，因为最右边是0）

image-20240613213439291

注意：只用全混洗函数无法实现任意节点之间的互连

通常使用全混洗函数+交换函数构成互连网络

蝶式函数（Butterfly）

B(xn−1xn−2...x2x1x0)=x0...x2x1xn−1B(x_{n-1}x_{n-2}...x_2x_1x_0) = x_{0}...x_2x_1x_{n-1}

最高位与最低位互换

子蝶式

B(k)(xn−1xn−2...xkxk−1xk−2...x2x1x0)=xn−1xn−2...xkx0xk−2...x2x1xk−1B_{(k)}(x_{n-1}x_{n-2}...x_kx_{k-1}x_{k-2}...x_2x_1x_0) = x_{n-1}x_{n-2}...x_kx_0x_{k-2}...x_2x_1x_{k-1}

最低k位进行局部的最高位与最低位互换

超蝶式

B(k)(xn−1xn−2...xn−k...x2x1x0)=xn−kxn−2...xn−k−1...x2x1x0B^{(k)}(x_{n-1}x_{n-2}...x_{n-k}...x_2x_1x_0) = x_{n-k}x_{n-2}...x_{n-k-1}...x_2x_1x_{0}

最高k位进行局部的最高位与最低位互换

反位序函数（Reserval）

R(xn−1xn−2...x2x1x0)=x0x1...xn−2xn−1R(x_{n-1}x_{n-2}...x_2x_1x_0) = x_{0}x_1...x_{n-2}x_{n-1}

就是倒序

子反位序

超反位序

image-20240614001021008 image-20240614001034487

和全混洗函数一样，蝶式函数也无法实现任意函数之间的互连

移数函数

a(x)=(x±k) mod Na(x) = (x\pm k)\ mod\ N

N为节点数，k为移动位数

+k就为左移，-k就为右移

image-20240614001802252

PM2i函数

PM2+i(x)=(x+2k) mod NPM2_{+i}(x) = (x+ 2^k)\ mod\ N

PM2−i(x)=(x−2k) mod NPM2_{-i}(x) = (x- 2^k)\ mod\ N

移数函数可以实现任意节点的网络互连。

  • PM2I函数互连网络共有2n个互连函数，n=logN

image-20240614005614217

IIIiac网采用PM2I函数，具体为PM2±0PM2_{\pm 0} 与PM2±n2PM2_{\pm \frac{n}{2}}

image-20240614110349962

静态互连网络

image-20240614132836501

对上述表格中的一些项的解释：

2D网格、Illiac网、2D环网

image-20240614133929192

超立方体

image-20240614140328461

带环立方体（k-CCC）

image-20240614175239872

k元n维立方体

image-20240614175352561

动态互连

总线网络

总线系统实际上是一组导线和插座用于处理与总线相连的处理机、存储模块和外围设备间的数据业务
在多个请求情况下,总线仲裁逻辑必须每次能将总线服务分配或重新分配给一个请求,按分时工作原理进行工作-争用总线/时分总线

总线系统与其他两种动态连接网络相比,其结构简单、实现成本低、带宽较窄

不能并行，只能一次一个请求

交叉开关

交叉点开关能在对偶(源、目的)之间形成动态连接,同时实现多个对偶之间的无阻塞连接。（并行）

带宽和互连特性最好。

  • 一个n×n的交叉开关网络,可以无阻塞地实现n!种置换。

  • 对一个n×n的交叉开关网络来说,需要n2n^2套交叉点开关以及大量的连线。

    当n很大时,交叉开关网络所需要的硬件数量非常巨大

示例：VPP500

多级互连（MIN）（重点）

  • 交换开关
  • 交换开关之间的拓扑连接
  • 对交换开关的不同控制方式

交换开关

  • a输入，b输出，就为a*b交换开关
  • 不允许有多对一映射
  • 只允许一对一映射的为置换，最常见的是2*2开关

n*n开关有nnn^n种合法状态，其中有n!n!种置换

image-20240614193334457

拓扑结构

前一级交换开关输出端与后一级交换开关输入端之间的联系方式

控制方式

  • 级控制

    同一级交换开关使用同一个信号控制

  • 单元级控制

    每个开关都有一个信号控制

  • 部分级控制

    第i级用i+1个信号控制

多级立方体网

image-20240614201840990 image-20240614202012192 image-20240614202026909
  • 使用部分级控制时，第i级有i+1个控制信号，从第0级开始，总共有1 + 2 + … + i + 1 = (i+2)(i+1)2\frac{(i+2)(i+1)}{2}个控制信号，如有3级（0，1，2）时有6个控制信号，有262^6 = 64个不同状态

一般来说，n个输入的交换网络，有log2nlog_2n级，每级有n2\frac{n}{2}个控制单元，总共需要n2log2n\frac{n}{2} log_2n个控制单元

总结

image-20240614202729040

  • 总线系统的复杂性最低,成本也是最低。其缺点是每台处理机可用的带宽较窄。
  • 交叉开关是最昂贵的,因为其硬件复杂性以n2上升,所以以其成本最高。但是交叉开关的带宽和寻径性能最好。如果网络的规模较小,它就是一种理想的选择。
  • 多级互连网络的复杂度和带宽介于总线和交叉开关之间,是一种折中方案。其主要优点是采用模块化结构,可扩展性较好。不过,其时延随网络各级数的增加而上升。另外,由于其硬件复杂度比总线高很多,所以其成本也不低。

消息传递机制

节点之间进行通信的逻辑单位是消息，当输出输入没有直接连接时，使用路由寻径

包是包含寻径目的地址信息的基本单位，由片组成（数据片、顺序号、寻径信息）

线路交换

  • 传输信息前需要先建立连接
  • 传输带宽高，时延小，缓冲区小
  • 适合于具有动态和突发性的大规模并行处理数据的传送。
  • 但频繁建立连接，耗时大

分组交换

存储转发

  • 包是信息传递的基本单位。包从源节点经过一系列中间节点到达目的节点。

  • 所经过的每个中间节点都要设置一个包缓冲器,用于保存所传递的包。当一个包到达某个中间节点时,该节点先把这个包全部存储起来,然后在出口链路可用、而且下一个节点的包缓冲器也可用的情况下,传递给下一个节点。

  • 包缓冲区大,不利于VLSI实现;

  • 网络时延大,与节点距离成正比。

虚拟直通

  • 对存储转发的改进

  • 没有必要等到信息包全部放入缓冲器后再作路由选择,只要接收到用作寻径的包头,就可作出判断。

  • 如果节点的输出链路空闲,信息包可以不必存储在该节点的缓冲器中,而是立即传送到下一个节点。
    如果整条链路都空闲,包就可以立即直达目的节点。

  • 当出现寻径阻塞时,虚拟直通方式需要将整个信息包全部存储在寻径节点中,要求每个节点都有足够大的缓冲区。不利于VLSI的实现

虫蚀方式

  • 把信息包"切割"成更小的单位——片，而且使信息包中各片的传送按流水方式进行。可以减少节点中缓冲器的容量,缩短传送延迟时间
  • 处理的最小信息单位是"片"。当一个节点把头片送到下一个节点后,那么接下来就可以把后面的各个片也依次送出
    • 一个节点一旦开始传送一个包中的头片后,这个节点就必须等待
    • 这个包的所有片都送出去后,才能传送其他包。不同包的片不能混合在一起传送

优点

  • 每个节点的缓冲器较小,易于VLSI实现;
  • 有较小的网络传输延迟;
  • 通道共享性好,利用率高:
  • 易于实现选播和广播通信模式:

缺点

  • 当消息的一片被阻塞时,整个消息的所有片都将被阻塞在所在节点,占用节点资源

消息传递机制

  • 确定性机制 - 选路预先唯一确定，只由开始和结束节点确定，不受网络情况影响
  • 自适应机制 - 根据网络情况来选路，提高网络利用率

超立方体的E-cube寻路

image-20240614204943258 image-20240614204958049

从0110到1101:

第一位0异或1 = 1，下一个节点是 0110的第一位取反0111

第二位1异或0 = 1，下一个节点是 0111的第二位取反 0101

第三位1异或1 = 0，没有变化

第四位0异或1 = 1，下一个节点是 0101第四位取反 1101，到达终点

最短路径为0110 - 0111 - 0101 - 1101，长度为3