目录

  1. 互连网络的基本概念
  2. 互连函数
  3. 互连网络的特性参数
  4. 互连网络的结构
  5. 重点对比与提示

1 互连网络的基本概念

1.1 什么是互连网络

互连网络是由开关元件按照一定的拓扑结构和控制方式构成的连接网络，用来实现计算机系统中各类结点之间的通信。这里的结点可以是处理器、存储模块，也可以是其他输入输出设备。

从抽象角度看，互连网络完成的是一种从输入结点到输出结点的连接或映射。若某个处理器需要访问某个存储模块，或一个处理单元需要把数据发送给另一个处理单元，互连网络就负责建立相应的通信路径。

互连网络可以理解为计算机系统中“部件之间怎么连、数据怎么走”的机制。它直接影响系统的并行通信能力、扩展能力、带宽、延迟、成本和可靠性。

1.2 描述互连网络的四个角度

可以从定时方式、交换方法、控制策略、拓扑结构四个方面描述互连网络。

描述角度 分类 含义 典型特点
定时方式 同步 全系统使用统一时钟 控制简单，典型如 SIMD 阵列处理机
定时方式 异步 各处理机独立工作，无统一全局时钟 更灵活，但同步和通信控制更复杂
交换方法 线路交换 通信期间源结点到目的结点的物理通路一直保持连接 延迟稳定，资源占用时间长
交换方法 分组交换 信息被分成多个包分别传输，到达目的端后再重组 链路利用率高，适合共享网络
控制策略 集中控制 一个全局控制器接收通信请求并设置开关 易于统一调度，但控制器可能成为瓶颈
控制策略 分散控制 无全局控制器，网络内部局部处理请求和设置开关 扩展性较好，但控制逻辑更复杂
拓扑结构 静态拓扑 结点之间有固定专用通路，运行中不改变 结构固定，适合规则通信
拓扑结构 动态拓扑 可根据需要设置开关，重新组合连接路径 灵活，适合多种通信模式

关键辨析：静态互连网络强调“固定连接”，动态互连网络强调“通过开关动态改变连接状态”。线路交换强调“通信期间占用整条物理通路”，分组交换强调“包独立进入网络”。

2 互连函数

2.1 互连函数的作用

每一种互连网络都可以用一组互连函数来描述。设网络共有 \(N\) 个输入和 \(N\) 个输出，输入端编号为

\[ x=0,1,\cdots,N-1 \]

互连函数 \(f(x)\) 表示输入端 \(x\) 连接到输出端 \(f(x)\)。因此，互连函数本质上描述的是一个输入编号到输出编号的映射关系。

有些互连函数可以用循环表示法表示：

\[ (x_0\ x_1\ x_2\ \cdots\ x_{j-1}) \]

其含义是：

\[ f(x_0)=x_1,\quad f(x_1)=x_2,\quad \cdots,\quad f(x_{j-1})=x_0 \]

其中 \(j\) 称为该循环的长度。例如循环 \((0\ 2\ 4\ 6)\) 表示 \(0\to2,\ 2\to4,\ 4\to6,\ 6\to0\)。

下面介绍五个常用的互联函数。

2.2 交换函数

交换函数实现的是：把输入端二进制地址编码中的第 \(k\) 位取反，其余各位保持不变。若输入编号写成

\[ x=x_{n-1}x_{n-2}\cdots x_{k+1}x_kx_{k-1}\cdots x_1x_0 \]

则交换函数可写为：

\[ E_k(x)=x_{n-1}x_{n-2}\cdots x_{k+1}\overline{x_k}x_{k-1}\cdots x_1x_0 \]

当 \(N\) 为结点数，\(n=\log_2N\) 时，共有 \(n\) 种交换函数。交换函数主要用于构造立方体互连网络和各种超立方体互连网络。

以 \(N=8\) 为例，结点编号用三位二进制表示，即 \(x=x_2x_1x_0\)，则有三个常用立方体互连函数：

\[ C_0(x_2x_1x_0)=x_2x_1\overline{x_0} \]

\[ C_1(x_2x_1x_0)=x_2\overline{x_1}x_0 \]

\[ C_2(x_2x_1x_0)=\overline{x_2}x_1x_0 \]

也就是说，\(C_0\) 翻转最低位，\(C_1\) 翻转中间位，\(C_2\) 翻转最高位。立方体网络中的一条边通常连接两个只相差一位的结点，因此交换函数天然对应立方体的不同维度。

例子：输入结点 \(3\) 的二进制编号是 \(011\)。若使用 \(C_1\)，翻转中间位，得到 \(001\)，所以 \(C_1(3)=1\)。

2.3 均匀洗牌函数与逆均匀洗牌函数

均匀洗牌函数把输入端分成数目相等的两半，然后像均匀混洗扑克牌那样交叉连接到输出端。从二进制编号角度看，它等价于把输入编号循环左移一位：

\[ S(x_{n-1}x_{n-2}\cdots x_1x_0)=x_{n-2}x_{n-3}\cdots x_1x_0x_{n-1} \]

逆均匀洗牌函数是均匀洗牌函数的逆函数，等价于把输入编号循环右移一位：

\[ S^{-1}(x_{n-1}x_{n-2}\cdots x_1x_0)=x_0x_{n-1}x_{n-2}\cdots x_1 \]

在多级互连网络中，均匀洗牌常作为级间互连模式。例如 \(8\times8\) Omega 网络中，每一级之间采用均匀洗牌模式。

例子：\(N=8\) 时，输入 \(5\) 的二进制是 \(101\)。均匀洗牌左移一位后得到 \(011\)，即十进制 \(3\)，所以 \(S(5)=3\)。

2.4 碟式函数

碟式函数把输入端二进制编号的最高位与最低位互换，中间各位保持原顺序。其表达式为：

\[ B(x_{n-1}x_{n-2}\cdots x_1x_0)=x_0x_{n-2}\cdots x_1x_{n-1} \]

它与反位序函数不同：碟式函数只交换最高位和最低位，而不是完全倒置所有位。

例子：\(N=8\) 时，输入 \(3\) 为 \(011\)。最高位 \(0\) 和最低位 \(1\) 互换，得到 \(110\)，即 \(6\)，所以 \(B(3)=6\)。

2.5 反位序函数

反位序函数把输入端二进制编号的位序完全颠倒：

\[ R(x_{n-1}x_{n-2}\cdots x_1x_0)=x_0x_1\cdots x_{n-2}x_{n-1} \]

反位序常出现在需要按位倒序访问数据的场景中。例如某些并行算法或快速傅里叶变换相关的数据重排会使用类似思想。

例子：\(N=8\) 时，输入 \(3\) 为 \(011\)，反位序后为 \(110\)，即 \(6\)。输入 \(5\) 为 \(101\)，反位序仍为 \(101\)，所以 \(R(5)=5\)。

2.6 PM2I 函数

PM2I 函数是一类循环移数函数，其含义是把输入端编号循环移动 \(2^i\) 个位置。它分为正向和反向两类： \[ PM2_{+i}(x)=x+2^i\pmod N \]

\[ PM2_{-i}(x)=x-2^i\pmod N \]

其中：

\[ 0\le x\le N-1,\quad 0\le i\le n-1,\quad n=\log_2N \]

因此，PM2I 互连网络共有 \(2n\)​ 个互连函数。比如：\(PM2_{+1}(x)=x+2^1 \pmod 8=x+2 \pmod 8\)，意思就是：每个结点都连到“往后数 2 个位置”的结点。

当 \(N=8\) 时，\(n=3\)，所以共有 \(6\) 个函数。循环表示如下：

函数 循环表示 含义
\(PM2_{+0}\) \((0\ 1\ 2\ 3\ 4\ 5\ 6\ 7)\) 每次加 \(1\)
\(PM2_{-0}\) \((7\ 6\ 5\ 4\ 3\ 2\ 1\ 0)\) 每次减 \(1\)
\(PM2_{+1}\) \((0\ 2\ 4\ 6)(1\ 3\ 5\ 7)\) 每次加 \(2\)
\(PM2_{-1}\) \((6\ 4\ 2\ 0)(7\ 5\ 3\ 1)\) 每次减 \(2\)
\(PM2_{\pm2}\) \((0\ 4)(1\ 5)(2\ 6)(3\ 7)\) 加或减 \(4\) 结果相同

例子：

\[ PM2_{+1}(2)=2+2^1\pmod 8=4 \]

ILLIAC IV 阵列计算机是一个典型例子。它采用 \(PM2_{\pm0}\) 和 \(PM2_{\pm n/2}\) 构成互连网络，用于实现处理单元之间的上下左右连接。可以把它理解为：用不同步长的循环移位连接，把一维编号组织成二维阵列上的邻接关系。

3 互连网络的特性参数

互连网络通常可以用图表示：结点代表处理器、存储模块或交换部件，边代表通信链路。评价一个互连网络时，不能只看“能否连接”，还要看通信距离、带宽、成本、扩展性和对称性等指标。

3.1 网络规模

网络规模指网络中结点的个数，表示该网络可以连接多少个部件。规模越大，系统可扩展性越好，但布线、控制和成本也通常更高。

3.2 结点度

结点度是与某个结点相连的边数。对于有向网络，还可分为：

  • 入度：进入该结点的边数。
  • 出度：从该结点发出的边数。

结点度越大，说明一个结点可以直接连接更多邻居，通信选择更多，平均距离可能更短。但结点度增大也意味着端口数量和硬件复杂度增加。

3.3 距离与网络直径

两个结点之间的距离是从一个结点到另一个结点所需跨越边数的最小值。

网络直径是任意两个结点之间距离的最大值。网络直径越小，最坏情况下通信经过的中间结点越少，延迟通常越低。因此需要强调：网络直径应当尽可能小。

3.4 线长

结点之间的线长指两个结点之间连线的实际物理长度。线长不仅影响布线成本，也影响信号传播延迟和可靠性。理论拓扑中边数相同的网络，在实际硬件实现时可能因为线长差异而表现不同。

3.5 等分宽度

等分宽度是把网络切成相等两半时，沿切口需要切断的边数或通道数的最小值，通常记为 \(b\)。它主要反映网络的最大流量能力。

如果等分宽度很小，说明网络中存在容易拥塞的“窄口”。例如线性阵列的等分宽度为 \(1\)，一旦两半之间大量通信，唯一跨越切口的链路就容易成为瓶颈。

3.6 对称性

如果从任意结点看出去，网络拓扑结构都是相同的（比如 \(K_5\)，Peterson图），则称为对称网络。对称网络的优点是结构规则、实现较容易、编程也更容易，因为每个结点面对的局部通信环境一致。

4 互连网络的结构

互连网络通常分为两大类：静态互连网络和动态互连网络。

静态互连网络中，各结点之间有固定连接通路，运行过程中不能改变。它更像是“把线提前接好”。动态互连网络由交换开关构成，可以按程序运行需要动态改变连接状态，更像是“运行时通过开关选择路径”。

4.1 静态互连网络

4.1.1 线性阵列

线性阵列是一种一维网络，\(N\) 个结点用 \(N-1\) 条链路连成一行。（有点像链表）

它的参数特点是：

参数 数值或特点
端结点度 \(1\)
中间结点度 \(2\)
网络直径 \(N-1\)
等分宽度 \(b=1\)

线性阵列结构非常简单、成本低，但网络直径随 \(N\) 线性增长，远距离通信要经过很多中间结点，扩展后性能容易下降。

4.1.2 环和带弦环

环是在一维线性阵列的基础上，用一条附加链路把两个端结点连接起来构成的。环可以单向工作，也可以双向工作。（有点像环状链表）

环的特点是：

类型 结点度 直径 特点
单向环 \(2\) 或按方向理解为入出各一条 \(N\) 只能沿一个方向绕行
双向环 \(2\) \(N/2\) 可选择较短方向，直径更小

环是对称网络，每个结点看到的局部连接形式相同。

带弦环是在环的基础上，每个结点再增加一条或两条额外链路。增加的链路越多，结点度越高，网络直径越小。它体现了一个重要规律：增加连接可以降低通信距离，但会提高硬件复杂度和成本。

4.1.3 全连接网络

全连接网络中，每个结点都与其他所有结点直接相连。对于 \(N\) 个结点，每个结点度为 \(N-1\)。（有点像完全图）

示例为 \(N=16\)，因此结点度为 \(15\)，直径为 \(1\)。全连接网络的通信距离最短，任意两个结点都可直接通信，但链路数量极多，硬件成本和布线复杂度非常高，不适合大规模系统。

4.1.4 循环移数网络

循环移数网络是在环的基础上增加跨距为 \(2\) 的整数幂的附加链路。一般地，若 \[ |j-i|=2^r,\quad r=0,1,2,\cdots,n-1,\quad n=\log_2N \]

则结点 \(i\) 与结点 \(j\) 相连。

对应参数为：

\[ \text{结点度}=2n-1 \]

\[ \text{直径}=n/2 \]

当 \(N=16\) 时，\(n=4\)，所以结点度为 \(7\)，直径为 \(2\)。循环移数网络通过增加不同跨度的连接，让结点可以用较少跳数到达较远位置。

4.1.5 树形与星形

树形网络具有分层结构。以完全平衡二叉树为例，一棵 \(k\) 层完全平衡二叉树有： \[ N=2^k-1 \]

个结点。其参数特点是：

\[ \text{最大结点度}=3 \]

\[ \text{直径}=2(k-1) \]

树形网络的优点是层次清晰、扩展自然；缺点是靠近根部的结点和链路可能成为通信瓶颈。

星形网络可以看作一种两层树。所有外围结点都连接到中心结点。其特点是：

参数 特点
中心结点度 \(N-1\)
网络直径 \(2\)
可靠性 较差，中心结点失效会导致整个系统瘫痪

星形网络用一个中心换取较短通信路径，但中心结点负载大、可靠性风险高。

4.1.6 胖树形

胖树形是在普通树形结构基础上增强上层通信能力的树形网络。普通树越靠近根部，汇聚的通信越多，容易形成瓶颈；胖树则通过在高层使用更宽的链路或更多通道，使靠近根部的带宽更大。

二叉胖树表现为：越靠近上层，连接通道越“粗”或越多，用来承载来自多个子树的聚合通信。需要抓住它的核心思想：胖树不是改变树的层次性，而是增强树上层的通信带宽，缓解根部瓶颈。

4.1.7 网格形与环网形

网格形网络把结点排列成规则的二维或高维网格。以 \(3\times3\) 网格为例：角结点、边结点、内部结点的度不同，因此网格形网络一般是不对称的。

对 \(N=n^k\) 个结点的 \(k\) 维网格网络，内部结点度为：

\[ 2k \]

网络直径为：

\[ k(n-1) \]

网格结构适合空间邻近通信，例如二维阵列计算或图像处理中的局部邻域操作。

环网形网络把环形和网格形结合起来：沿阵列的每行和每列都有环形连接，并且可以扩展到高维。它相比普通网格更对称，因为边界被“首尾相接”。

对于一个 \(n\times n\) 的二元环网：

\[ \text{结点度}=4 \]

\[ \text{直径}=2\lfloor n/2\rfloor \]

其中 \(\lfloor n/2\rfloor\) 表示不超过 \(n/2\) 的最大整数。

4.1.8 超立方体

超立方体是一种二元 \(n\) 维立方体结构。一个 \(n\) 维超立方体由

\[ N=2^n \]

个结点组成。每个结点可以用 \(n\) 位二进制编号表示，两个结点若编号只相差一位，则它们之间有一条链路。（有点像格雷码）

构造 \(n\) 维立方体的方法是：把两个 \((n-1)\) 维立方体中相对应的结点用链路连接起来。三维立方体以及由两个三维立方体组成四维立方体的方式，可以体现这种递归构造。

超立方体的关键参数为：

\[ \text{结点度}=n \]

\[ \text{网络直径}=n \]

因为两个 \(n\) 位二进制编号最多有 \(n\) 位不同，每经过一条边可以改变一位，所以最远距离为 \(n\)。这也是交换函数与超立方体结构紧密相关的原因。

4.2 动态互连网络

4.2.1 总线

总线是一组导线和插座，用于连接处理机、存储模块和外围设备等功能模块，完成数据传送。

总线的基本特点是：每一次只能用于一个源部件到一个或多个目的部件之间的数据传送。多个功能模块需要共享总线，因此会出现争用，通常需要仲裁或时分复用。

总线的优点是价格低、结构简单；缺点是带宽较窄、共享争用明显。随着处理器或模块数量增加，总线容易成为系统瓶颈。

4.2.2 多级互连网络

多级互连网络（Multistage Interconnection Network，MIN）常用于 MIMD 和 SIMD 计算机。它由多个级联的开关级组成，相邻各级开关之间通过固定的级间连接模式相连。

一种通用多级互连网络中，每一级有多个 \(a\times b\) 开关：

  • \(a\) 表示开关输入端个数。

  • \(b\) 表示开关输出端个数。

  • 理论上 \(a\) 与 \(b\) 不一定相等，但实际中常取 \(a=b=2^k,\ k\ge1\)。

  • 1
    2
    3
    4
    输入0 ─┐      ┌─ 输出0
    输入1 ─┤      ├─ 输出1
    	 ─┤ 开关  ├─ 
    输入a ─┘      └─ 输出b

多级互连网络的差异主要来自三个方面：

差异来源 说明
开关模块 例如 \(2\times2\) 开关、\(a\times b\) 开关
控制方式 决定各开关如何被控制
级间互连模式 决定相邻级之间如何连线

最简单的开关模块是 \(2\times2\) 开关，有四种连接方式：

方式 含义
直送 上输入到上输出，下输入到下输出
交叉 上输入到下输出，下输入到上输出
上播 上输入到上输出+下输出
下播 下输入到上输出+下输出

常见控制方式有三种：

控制方式 含义 特点
级控制 每一级所有开关共用一个控制信号 同一级开关只能处于同一种状态，控制简单但灵活性低
单元控制 每个开关都有独立控制信号 最灵活，但控制复杂
部分级控制 第 \(i\) 级所有开关分别用 \(i+1\) 个信号控制 灵活性介于两者之间

常用级间互连模式包括：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等。

4.2.3 Omega 网络

Omega 网络是一种典型多级互连网络。以一个 \(8\times8\) Omega 网络为例：

  • 共 \(3\) 级，因为 \(\log_2 8=3\)。
  • 每级有 \(4\) 个 \(2\times2\) 开关。
  • 级间互连采用均匀洗牌模式。

其均匀洗牌函数为：

\[ S(x_2x_1x_0)=x_1x_0x_2 \]

Omega 网络通过多级 \(2\times2\) 开关逐步决定数据包路径。它结构规则、成本低于全交叉开关，但并非所有连接请求都能同时无冲突完成，因此可能存在阻塞。

4.2.4 多级立方体网络

多级立方体网络采用二功能 \(2\times2\) 开关构成，其中二功能指直送和交换。它与交换函数结合，可以通过设置不同级的开关状态实现不同互连函数。

\(8\) 输入、\(8\) 输出多级立方体网络由三组开关构成：第一组 \(A,B,C,D\)，第二组 \(E,F,G,H\)，第三组 \(I,J,K,L\)。通过改变开关状态，可以得到：

开关设置 实现的变换
所有开关都直送 恒等变换
\(A,B,C,D\) 交叉，其余直送 \(C_0\) 互连函数
\(E,F,G,H\) 交叉，其余直送 \(C_1\) 互连函数
\(I,J,K,L\) 交叉，其余直送 \(C_2\) 互连函数

也就是说，不同级对应不同二进制位的交换。控制哪一级开关交叉，就相当于翻转对应位，从而实现立方体交换函数。

进一步地，通过选择不同控制方式，可以构成不同网络：

控制方式 构成的网络
级控制 交换网
部分级控制 移数网
单元控制 间接二进制 \(n\) 方体网

4.2.5 交叉开关网络

交叉开关网络是一种单级开关网络。它通过交叉点开关在源和目的之间形成动态连接，并且可以同时实现多个源-目的对之间的无阻塞连接。

它的特点是：

  • 带宽和互连特性最好。
  • 可以无阻塞地支持多个对偶连接。
  • 一个 \(n\times n\) 交叉开关网络可以无阻塞地实现 \(n!\) 种置换。

C.mmp 多处理机互连结构是一种交叉网络。图中处理机 \(P_1,P_2,\cdots,P_{16}\) 与存储模块 \(M_1,M_2,\cdots,M_{16}\) 通过交叉点连接，任一处理机理论上可以通过对应交叉点访问任一存储模块。

交叉开关的主要缺点是硬件代价高。对于 \(n\times n\) 网络，需要大量交叉点开关，因此规模很大时成本和实现复杂度会迅速上升。

5 总结与对比

5.1 静态网络参数对比

网络结构 结点度 直径 对称性/特点
线性阵列 端点 \(1\)，中间 \(2\) \(N-1\) 最简单，但直径大，等分宽度 \(b=1\)
双向环 \(2\) \(N/2\) 对称，比线性阵列直径小
带弦环 大于普通环 小于普通环 增加链路降低直径
全连接 \(N-1\) \(1\) 性能最好但成本最高
循环移数网络 \(2n-1\) \(n/2\) 用 \(2^r\) 跨距连接降低直径
完全平衡二叉树 最大 \(3\) \(2(k-1)\) 层次清晰，根部可能瓶颈
星形 中心 \(N-1\) \(2\) 中心结点是可靠性瓶颈
网格 内部 \(2k\) \(k(n-1)\) 适合局部通信，一般不对称
环网 \(4\) \(2\lfloor n/2\rfloor\) 行列成环，比网格更对称
\(n\) 维超立方体 \(n\) \(n\) 二进制编号差一位相连，结构规则

5.2 动态网络对比

网络 核心结构 优点 缺点
总线 所有模块共享一组导线 成本低，结构简单 带宽窄，争用严重
多级互连网络 多级开关加固定级间互连 成本适中，结构规则，可扩展 可能阻塞，控制较复杂
Omega 网络 多级 \(2\times2\) 开关，级间均匀洗牌 规则，适合实现置换类通信 不是完全无阻塞
多级立方体网络 \(2\times2\) 直送/交换开关加交换函数 可通过控制实现不同立方体互连 控制方式影响网络能力
交叉开关网络 单级交叉点开关矩阵 无阻塞，带宽和互连特性最好 硬件成本高，规模扩展困难

5.3 概念辨析

线路交换 vs 分组交换：线路交换在整个传输期间保持一条物理通路；分组交换把信息拆成包，包可分别进入网络，最后在目的端重组。

静态拓扑 vs 动态拓扑：静态拓扑的连接在运行中不改变；动态拓扑通过开关状态改变通信路径。

碟式函数 vs 反位序函数：碟式函数只交换最高位和最低位；反位序函数把所有位顺序完全颠倒。

网格 vs 环网：网格边界不首尾相接，因此角结点、边结点和内部结点度不同；环网把每行每列都做成环，结构更对称。

总线 vs 交叉开关：总线便宜但同一时刻共享一条通信介质；交叉开关昂贵但可以同时建立多个无阻塞连接。

5.4 常用计算

  1. 给定 \(N\)，计算 \(n=\log_2N\)。
  2. 对 \(N=8\) 或 \(N=16\)，能写出或判断 \(C_0,C_1,C_2\) 等交换函数的输出。
  3. 能根据二进制编号计算均匀洗牌、逆均匀洗牌、碟式、反位序和 PM2I 函数。
  4. 能记住并比较典型网络的结点度、直径和等分宽度。
  5. 能解释为什么全连接和交叉开关性能好但成本高，为什么总线便宜但带宽受限。

5.5 本章核心线索

本章的主线可以概括为：互连网络用拓扑和控制方式实现结点间通信；互连函数用数学映射描述输入到输出的连接；特性参数用来评价网络好坏；静态网络重在固定拓扑，动态网络重在开关控制。

从内容结构看，应优先理解互连函数的位操作、典型网络结构的参数、静态/动态网络分类，以及总线、多级网络、交叉开关网络之间的性能与成本差异。