• 互联函数
  • 互联网络的参数与性能指标
  • 静态互连网络
  • 动态互连网络

互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中节点之间的相互连接。

  • 节点：处理器、存储模块或其他设备。
  • 在拓扑上，互连网络为输入节点到输出节点之间的一组互连或映射。
  • SIMD 计算机和 MIMD 计算机的关键组成部分。
  • 3 大要素：互连结构，开关元件，控制方式。

7.1 互连函数

7.1.1 互连函数

互连函数：通过数学表达式建立输入端号与输出端号的连接关系。即在互连函数 f 的作用下，输入端 x 连接到输出端$f(x)$。

  • 互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。
  • 互连函数 f(x)有时可以采用循环表示
    • ${x0, x_1, … x{j-1}}~\to~f(x0)=x_0, f(x_1)=x_2, …, f(x{j-1})=x_0$
    • $j$称为循环的长度。
    • 互连函数表示为$f(x{n-1}x{n-2}…x_1x_0)$
    • $x=x{n-1}x{n-2}…x_1x_0$，其中$n=log_2N$。

7.1.2 几种基本的互连函数

恒等函数：$I(x{n-1}x{n-2}…x1x_0)=x{n-1}x_{n-2}…x_1x_0$
交换函数：实现二进制地址编码中第 k 位互反的输入端与输出端之间的连接。

  • 主要用于构造立方体互连网络和各种超立方体互连网络。
  • 该函数有 n 种
  • 立方体互连函数：当$N=8$，即$n=3$时。
N=8的立方体交换函数

均匀洗牌函数

  • 将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。也称为混洗函数。直观的来说是将原地址乘 2 取模。
  • $ \sigma(x{n-1}x{n-2}…x1x_0)=x{n-2}x{n-3}…x_1x_0x{n-1} $
  • 第 k 个子函数$\sigma_(k)$：把 s 作用于输入端的二进制编号的低 k 位。将低 k 位左移一位。
  • 第 k 个超函数$\sigma^(k)$：把 s 作用于输入端的二进制编号的高 k 位。将高 k 位左移一位。
  • $\sigma^{(n)}=\sigma_{(n)}=\sigma$
  • $\sigma^{(1)}=\sigma_{(1)}=f$
  • 若存在函数使$f(x)\times g(x)=I(x)$则称为$g(x)$是$f(x)$的逆函数。
  • 逆均匀洗牌函数

碟式函数

  • 把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。
  • $\beta(x{n-1}x{n-2}…x1x_0)=x_0x{n-2}…x1x{n-1}$
  • 第 k 个子函数$\beta_{(k)}$：将输入端第 k 位（编号 k-1）与编号 0 交换。
  • 第 k 个超函数$\beta^{(k)}$：将输入端第 n-k 位与编号 n-1 交换。
  • $\beta^{(n)}=\beta_{(n)}=\beta$
  • $\beta^{(1)}=\beta_{(1)}=f$

移数函数

  • 将各输入端都错开一定的位置（模 N）后连到输出端。
  • $\alpha(x)=(x\pm k)~mod~N$

PM2I 函数

  • 一种移数函数，将各输入端都错开一定的位置（模 N）后连到输出端。
  • $PM2_{+i}=(x+2^imod)N$
  • $PM2_{-i}=(x-2^imod)N$
  • 该函数互联网络具有 2n 个不同的互连函数。

7.2 互连网络的结构参数与性能指标

7.2.1 互连网络的结构参数

  • 网络通常是用有向边或无向边连接有限个节点的图来表示。
  • 互连网络的主要特性参数有：
    • 网络规模 N：节点个数，连接的部件数量
    • 节点度 d：与节点连接的边数（通道数）
    • 节点距离：从一个节点出发到另一个节点终止所需要跨越的边数的最小值
    • 网络直径 D：距离的最大值
    • 等分宽度 b：把 N 个节点切成节点数相同的两半需要的切除边数的最小值
      • 线等分宽度：$B=b\times w$
      • w 为通道宽度
      • 反映了网络最大流量

7.2.2 性能指标

通信时延：指从源节点到目的节点传送一条消息所需的总时间，它由以下 4 部分构成：

  • 软件开销：在源节点和目的节点用于收发消息的软件所需的执行时间。
    • 取决于节点处理消息的软件内核
  • 通道时延：通过通道传送消息所花的时间。
    • 通信时延 = 消息长度 / 通信带宽
    • 有瓶颈的通道带宽决定
  • 选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销。
    • 与路径的节点数相关
  • 竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。

网络时延

  • 通道时延与选路时延的和
  • 由网络硬件特征决定，与程序星为和传输状态无关

端口宽带

  • 对于互连网络中的任意一个端口来说，其端口带宽是指单位时间内从该端口传送到他端口的最大信息量。
  • 在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽同。
  • 非对称网络的端口带宽则是指所有端口带宽的最小值。

聚集带宽：网络从一半节点到另一半节点，单位时间内能够传送的最大信息量。
等分带宽：与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量。

7.3 静态互联网络

互连网络通常可以分为两大类：

  • 静态互连网络：各节点之间有固定的连接通路、且在运行中不能改变的网络。
  • 动态互连网络：由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。

线性阵列

  • 一种一维的线性网络，其中 N 个节点用 N-1 个链路连成一行。
  • 端节点的度：1
  • 其馀节点的度：2
  • 直径：N－1
  • 等分宽度 b=1

环和带弦环

  • 环
    • 用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。
    • 对称性
    • 节点的度：2
    • 双向环的直径：N/2
    • 单向环的直径：N
    • 环的等分宽度 b=2
  • 带弦环
    • 增加的链路越多，节点度就越高，网络直径就越小
  • 全连接网络

循环移数网络

  • 通过在环上每个节点到所有与其距离为 2 的整数幂的节点之间都增加一条附加链而构成。
  • 即如果$|j-i|=2^r$，则 j 与 i 连接。
    • 节点度：2n-1
    • 直径：n/2
    • 网络规模：$N=2^n$

树形和星形

  • 树形可靠性较差，具有较高的节点度

胖树形

网格形和环网形

  • 网格形
    • 对于$n\times n$的网格
      • 内部节点的度 d=4
      • 边节点的度 d=3
      • 角节点的度 d=2
      • 网络直径 D=2（n-1）
      • 等分宽度 b=n
    • 一个由$N=n^k$个节点构成的 k 维网格形网络（每维 n 个节点）的内部节点度 d=2k，网络直径 D=k(n-1)
  • Illiac 网络
    • 把 2 维网格形网络的每一列的两个端节点连接起来，再把每一行的尾节点与下一行的头节点连接起来，并把最后一行的尾节点与第一行的头节点连接起来。
    • 对于$n\times n$的网格
      • 所有节点的度 d=4
      • 网络直径 D=n-1
      • Illiac 网络的直径只有纯网格形网络直径的一半。
      • 等分宽度：2n
  • 环网形
    • 把 2 维网格形网络的每一行的两个端节点连接起来，把每一列的两个端节点也连接起来。
    • 将环形和网格形组合在一起，并能向高维扩展。
    • 一个 n×n 的环网形网
      • 节点度：4
      • 网络直径：2×(n/2)
      • 等分宽度 b=2n

超立方体

  • 一个二元 n-立方体由$N=2^n$个节点组成，它们分布在 n 维上，每维有两个节点。
  • 为实现一个 n-立方体，只要把两个（n－1）立方体中相对应的节点用链路连接起来即可。共需要 2n-1 条链路。
  • n-立方体中节点的度都是 n，直径也是 n，等分宽度为 b=N/2 。

带环立方体（3-CCC）

  • 把 3-立方体的每个节点换成一个由 3 个节点构成的环而形成的。
  • 带环 k-立方体（简称 k-CCC）
    • k-立方体的变形，它是通过用 k 个节点构成的环取代 k-立方体中的每个节点而形成的。
    • 网络规模为 N=k×2k
    • 网络直径为 D=2k-1+k/2
    • 比 k-立方体的直径大一倍
    • 等分宽度为 b=N/（2k）

7.4 动态互连网络

7.4.1 总线网络

由一组导线和插座构成，经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。

  • 每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。
  • 多个功能模块之间争用总线或时分总线
  • 特点：结构简单、成本低、带宽窄

一种由总线连接的多处理机系统

  • 系统总线在处理机、I/O 子系统、主存储器以及辅助存储设备（磁盘、磁带机等）之间提供了一条公用通路。
  • 系统总线通常设置在印刷电路板底板上。处理器板、存储器板和设备接口板都通过插座或电缆插入底板。

带宽窄的解决

  • 多总线是设置多条总线，有两种做法：
    • 为不同的功能设置专门的总线
    • 重复设置相同功能的总线
  • 多层次的总线是按层次的架构设置速度不同的总线，使得不同速度的模块有比较适合的总线连接。

7.4.2 交叉开关网络

单极开关网络

  • 交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接。
  • 带宽和互连特性最好。
  • 一个 n×n 的交叉开关网络，可以无阻塞地实现$n!$种置换。
  • 对一个 n×n 的交叉开关网络来说，需要 n2 套交叉点开关以及大量的连线。当 n 很大时，交叉开关网络所需要的硬件数量非常巨大。

C.mmp 多处理机的互连结构

  • 用 16×16 的交叉开关网络把 16 台 PDP-11 处理机与 16 个存储模块连在一起
  • 最多可同时实现 16 台处理机对 16 个不同存储模块的并行访问
    • 每个存储模块一次只能满足一台处理机的请求
    • 当多个请求要同时访问同一存储模块时，交叉开关就必须分解所发生的冲突，每一列只能接通一个交叉点开关。
    • 为了支持并行（或交叉）存储器访问，可以在同一行中接通几个交叉点开关。

7.4.3 多级互联网络

多级互连网络的构成

  • MIMD 和 SIMD 都采用多级互联网络 MIN（Multistage Interconnection Network）
  • 一种通用的多级互连网络
    • 由 a×b 开关模块和级间连接构成的通用多级互连网络结构
    • 每一级都用了多个 a×b 开关
      • a 个输入和 b 个输出
      • 在理论上，a 和 b 不一定相等，然而实际上 a 和 b 经常选为 2 的整数幂，即 a＝b＝2k，k≥1。
    • 相邻各级开关之间都有固定的级间连接
  • 最简单的开关模块：2x2 开关
  • 各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。
    • 控制方式：对各个开关模块进行控制的方式。
      • 级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态。
      • 单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态。
      • 部分级控制：第 i 级的所有开关分别用 i＋1 个信号控制，0≤i≤n－1，n 为级数。
    • 常用的级间互连模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等

多级立方网络

  • 多级立方体网络包括 STARAN 网络和间接二进制 n 方体网络等。
    • 两者仅在控制方式上不同，在其他方面都是一样的。
    • 都采用二功能（直送和交换）的 2×2 开关。
    • 当第 i 级（0≤i≤n-1）交换开关处于交换状态时，实现的是 Cubei 互连函数。
  • 一个 N 输入的多级立方体网络有 log2N 级，每级用 N/2 个 2×2 开关模块，共需要 log2N×N/2 个开关。
一个8个入端的多级立方体网络
  • STARAN 网络采用级控制和部分级控制。
    • 采用级控制时，所实现的是交换功能；
    • 采用部分级控制时，则能实现移数功能。
  • 间接二进制 n 方体网络则采用单元控制。
    • 具有更大的灵活性。

Omega 网络

一个8×8的Omega网络
  • 一个 N 输入的 Omega 网络
    • 有$log_2N$级，每级用 N/2 个 2×2 开关模块，共需要$Nlog_2N/2$个开关。
  • 每个开关模块均采用单元控制方式。
  • 不同的开关状态组合可实现各种置换、广播或从输入到输出的其他连接。