【计算机体系结构】计算机体系结构(6) 并行处理技术(1) SIMD并行计算机、算法和互联网络_简述simd系统的互连网络设计

并行处理技术是获取高性能计算的重要手段，计算机系统结构由低向高发展的过程，就是并行处理技术不断发展的过程。与器件的发展对提高计算机性能的作用相比，并行处理技术显得更重要——器件速度的改进受物理条件约束，不可能超过光速，而并行处理技术可以通过资源的重复来实现，其发展基本上是无穷尽的。因此，从这个意义上讲，它有着更为广阔的应用前景，将起到更为重要的作用。

6.1 并行处理技术的基本概念

所谓并行性是指在数值计算、数据处理、信息处理或人工智能求解过程中，可能存在某些可以同时进行运算或操作的部分。开发并行性的目的是，为了能进行并行处理，提高计算机系统求解问题的效率。

并行性的双重含义是指同时性（或并行性）和并发性。所谓同时性是指两个或两个以上的事件在同一时刻发生，而并发性则是指两个或两个以上的事件在同一段时间间隔内发生。

并行处理则是指一种相对于串行处理的信息处理方式，它着重开发计算过程中存在的并发事件。在进行并行处理时，其每次处理的规模大小可能是不同的，这可用并行性粒度来表示。有关并行性粒度大小 $G$ 可用以下公式表示（假定系统中共有 $P$ 个处理器） ：
$$G=\frac{T_W}{T_C}=\frac{\sum _{i=1}^P{t}_{wi}}{\sum _{i=1}^P{t}_{ci}}$$ 式中，分子为所有处理器的计算时间总和，而分母表示所有处理器的通信时间总和。当 $TC$ 较大时，$G$ 就较小，表明处理粒度较细。当处理粒度较细时，显然此时处理器间的通信量将加大，相反当粒度较粗时，通信量就较小。

并行性有不同的等级，而且从不同角度观察时，会有不同的划分方法。程序执行过程通常可划分成以下 $5$ 个等级——作业级、任务级、程序级（例行程序或子程序）、指令级和指令内的操作级。前 $3$ 级为粗粒度，主要是通过多处理机或多计算机系统实现，开发手段以软件为主，其中包括并行性算法分析、任务的调度与分配等；而后 $2$ 级为细粒度，主要是在单处理机中实现，开发手段以硬件为主，其中包括标量流水、超标量流水、超流水和超长指令字等。

并行性的开发途径有时间重叠、资源重复和资源共享。

• 时间重叠：在并行性中引入时间因素。即让多个处理过程在时间上相互错开、重叠地使用同一部件，以赢得速度，如指令的流水执行方式。
• 资源重复：在并行性中引入空间因素。即通过重复设置多个功能部件来提高处理性能或可靠性，如阵列处理机。
• 资源共享：利用软件的方法，让多个用户按一定的时间顺序轮流使用一套资源，以提高系统资源的利用率。

从计算机系统结构的角度出发，根据并行性的三个途径，从计算机系统由低性能向高性能发展过程中可以看出，并行性正从两个不同的角度向同一方向发展。

• 一方面在单处理机上，通过时间重叠、资源重复和资源共享，分别向异构型多处理机系统、同构型多处理机系统和分布式处理系统方向发展。
• 另一方面在多计算机系统中，通过功能专业化、多机互连、网络化等手段，分别向异构型多处理机系统、同构型多处理机系统和分布式多处理机系统的方向发展。

例如，在指令级内部，采用了多个子部件以流水方式执行指令，以提高单台计算机的执行速度。这一思想仍可应用于多台计算机组成的系统，如在高级语言向汇编语言转换过程中，是由编译程序完成翻译的。将翻译的全过程分为编译扫描、编译分析和目标程序生成三个子过程。为了提高效率，可由三台计算机组成流水方式执行。由于这三台计算机结构可以不一样（非对称型），故这样组成的多计算机系统称为异构型多计算机系统。

按照资源重复的思想，既然在一个计算机系统内可由多个相同的处理单元构成阵列处理机，那么用多台系统结构相同的计算机，也可以组成多计算机系统，这种系统结构称为同构型（对称型）多计算机系统。

按照资源共享的思想，单处理机采用多道程序和分时操作，并发展成为分布式多计算机系统。

---

6.2 SIMD 并行计算机（阵列处理机）

本节将讨论以 SIMD 方式工作、采用资源重复的并行性措施的阵列处理机。由于历史原因，习惯上也将阵列处理机（简称“阵列机”）称为并行处理机。这里首先讨论它的基本结构，然后是它的主要特点，最后简短讨论适合于在阵列机上进行加工的并行算法。

6.2.1 阵列机的基本结构

阵列机通常由一个控制器 CU 、$N$ 个处理器单元 PE 、$M$ 个存储器模块 M 及一个互连网络部件 IN 所组成。由 CU 控制将指令广播给系统中的各个 PE ，而所有活跃的 PE 将以同步方式执行相同的指令（单指令流），它们从相应的存储模块中取得自己所需的数据对象（多数据流）。IN 用来使各个 PE 之间或是 PE 和 M 之间实现方便的通信连接。IN 有时也称为对准 Alignment 或排列 Permutation 网络。有关互连网络的问题，在下一节作进一步讨论。

为了形式化地表示阵列机的特征，可用以下的参数加以描述：
$$C=(N,F,I,M)$$ 式中，$N$ 为 PE 数；$F$ 为确定互连网络结构及连接拓扑的互连参数；$I$ 为指令集，它能进行标量、向量、数据传送通路操作和网络变换操作等；$M$ 为屏蔽方式集合，每一种方式将 PE 集合分为活跃和非活跃两类 PE 的子集。这种描述模型，为评价不同的阵列机结构提供了比较基础。

根据存储器模块是以分布方式存取还是集中方式存取，阵列机可分为两种基本结构：分布式存储器的阵列机和集中共享存储器的阵列机。

1. 分布式存储器的阵列机

分布式阵列机的基本结构如图6.1(a)所示。这种阵列机的主要结构特征如下：

• CU 中具有自己的存储器，以存放系统程序和用户程序，此外，它也可存放各个 PE 所需的共享数据。
• CU 的主要功能是对指令译码和判别它应在何处执行。对于标量或控制类指令，CU 本身中含有运算部件可以直接执行；若是向量指令，它就将此指令广播给各个 PE 去执行。
• 具有 $N$ 个相同的处理单元 PE，它由处理器 Pi 和局部存储器 Mi 组成。只要数据分配得当，各个 Pi 主要将从自己的 Mi 中获取数据进行操作。各个 PE 将通过 IN 实现相互间必要的数据交换，因此，IN 是单向的。
• 各个 PE 同步执行来自 CU 的操作命令，但是并不一定每个操作非得所有 PE 都参加，CU 将对 PE 实行屏蔽控制，只有那些未被屏蔽的活跃 PE 才可参加操作。
• CU 还控制互连网络 IN，使各个 PE 之间通过 IN ，实现相互之间必要的数据交换。当相互需要交换数据的两个 PE 不直接相连时，就需要经过它们之间的中间 PE来完成连接。
  

2. 共享存储器的阵列机

图6.2(b)中示出了这种类型的阵列机结构。与图6.2(a)中分布式存储器的阵列机结构比较，区别主要在于：

• 每个 PE 没有局部存储器。存储器模块以集中形式为所有 PE（通过 IN ）共享。
• 互连网络受 CU 控制，用来构成 PE 和 M 之间的数据交换通路。要求互连网络具有同时连接 PE 到 M 或 M 到 PE 的双向性。系统中的一个 PE ，可以与任何另一个 PE 实现数据交换（只要有任何一个存储模块，同时与这两个 PE 相连接） 。当两个需交换数据的 PE 之间没有共享的存储模块时，可能需要经过多次的传送之后，方可实现交换。

6.2.2 阵列机的主要特点

阵列机是以单指令流多数据流方式工作的，它具有以下特点：

1. 它采用资源重复方法引入空间因素，即在系统中设置多个相同的处理单元开发并行性，这与利用时间重叠的流水线处理机是不一样的。此外，它是利用并行性中的同时性、而不是并发性，所有处理单元必须同时进行相同操作。
2. 它是以某一类算法为背景的专用计算机。这是由于阵列机中通常都采用简单、规整的互连网络，实现处理单元间的连接操作，从而限定了它所适用的求解算法类别。因此，「对互连网络设计的研究」就成为阵列机研究的重点之一。
3. 阵列机的研究必须与并行算法研究密切结合，以便使它的求解算法的适应性更强一些，应用面更广一些。
4. 从处理单元来看，由于都是相同的，因而可将阵列机看成是一个同构型并行机。但它的控制器实质上是一个标量处理机，而为了完成I/O操作以及操作系统的管理，尚需一个前端机。因此，实际的阵列机系统是由上述三部分构成的一个异构型多处理机系统。

6.2.3 典型 SIMD 计算机举例

1. ILLIAC-Ⅳ阵列计算机（阵列机）

由美国宝来 Burroughs 公司和伊利诺斯大学在1965年开始研制，并于1972年由宝来公司生产的 ILLIAC-Ⅳ 阵列机，是 SIMD 并行计算机的一个典型代表。它可分为两大部分，即 ILLIAC-Ⅳ 阵列和 ILLIAC-Ⅳ 输入输出系统。实际上，它是由三种类型处理机组成的一个异构多机系统：一是专门用于数组运算的处理单元阵列；二是阵列控制器，它既是处理单元阵列的控制部分，又是一台相对独立的小型标量处理机；三是一台标准的宝来公司的 B6700 计算机，由它担负 ILLIAC-Ⅳ 输入输出系统和操作系统管理功能，如图6.2所示。

(1) ILLIAC-Ⅳ 阵列

ILLIAC-Ⅳ 阵列计算机共有 $64$ 个 PE，由控制器 CU 统一控制。系统由一台 B6700 作为宿主机进行管理，每个 PE 有自己的局存 PEM ，容量 $2K$ 字，字长 $64$ 位。每个 PE 拥有 $4$ 个 $64$ 位寄存器，分别用做累加器、操作数寄存器、数据路由寄存器和通用寄存器。此外，尚有 $1$ 个 $16$ 位变址器和 $1$ 个 $8$ 位方式寄存器，后者是用来存放 PE 屏蔽信息的。这是一种闭螺线阵列，每个 PE 只能与 $4$ 个近邻的 PE 直接相连，即PE 与 PEi - 1，PEi + 1，PEi - 8 和 PEi + 8（Mod 64） $4$ 个近邻直接相连。

因此，从一个 PE 要将数据达到另一个 PE 时，可能中间要经过若干个其他 PE 转送。传送步数 $S\le \sqrt{N}-1$ ，这里 $N$ 为 PE 数。对于 ILLIAC-Ⅳ 来讲，由于 $N=64$ ，故 $S\le 7$ 。例如，从 PE9 到 PE45 的距离以这一路径为最短：PE9 → PE1 → PE57 → PE56 → PE48 → PE47 → PE46 → PE45

ILLIAC-Ⅳ 阵列机的每一个处理单元 PE 有 $6$ 个可编程序寄存器 RGA, RGB, RGR, RGS, RGX, RGM 以及加/乘算术单元 AU 、逻辑单元 LU 、移位单元 SU 和地址加法器 ADA 等。

• RGA 是累加寄存器，存放第一操作数和操作结果。
• RGB 是操作数寄存器，存放加、减、乘、除等二元操作的第二操作数。
• RGR 是被乘数寄存器，也是互连寄存器，用于 PE 与经过东、西、南、北 $4$ 个互连通路之一的另一个处理单元之间的数据直接传送。
• RGS 是通用寄存器，程序用来暂存中间结果。上述这 $4$ 个寄存器都是 $64$ 位的。操作数来自以下 $4$ 个方面：PE 本身的寄存器、PE 的处理单元存储器 PEM ，CU 的公共数据总线 CDB ，PE 的 $4$ 个近邻处理单元。
• RGX 是 $16$ 位的变址寄存器，它利用地址加法器 ADA 修改指令地址，并将形成的有效地址经过存储器地址寄存器 MAR ，输入存储器逻辑部件 MLU 。
• RGM 是 $8$ 位的模式寄存器，RGM 中的 E 和 E1 位是“活动”标志位，用来控制 RGA, RGS 和处理单元存储器 PEM ，E 位还控制 RGX 。活动标志位的设立，使得我们可以单独控制 $64$ 个处理单元中的每一个处理单元，只有那些处于活动状态的处理单元，才执行单指令流规定的共同操作。
  RGM 的其他 $6$ 位分别是：F 和 F1 位保存运算出错（上溢、下溢）标志，G, H, I, J 位保存测试结果。RGM 经常处于 CU 的监督之下，一旦出错，就发出 CU 陷阱中断。

处理单元存储器 PEM 分属于每一个处理单元，各有 $2048\times 64$ 位存储容量，PEM 的取数时间不大于 $350ns$ 。$64$ 个 PEM 联合组成阵列存储器，存放数据和指令。

整个阵列存储器可以接受阵列控制器 CU 的访问，读出 $8$ 个字的信息块到 CU 的缓冲器中。阵列存储器也可经过 $1024$ 位的总线与 I/O 开关相连。每个 PE 只能直接访问自己的 PEM 。分布在各个 PEM 中的公共数据只能先读至 CU 后，再经 CU 的公共数据总线 CDB 广播到 $64$ 个处理单元中去。

阵列存储器的另一个特点是它具有双重变址机构：控制器 CU 实现所有处理单元的公共变址，每一个处理单元 PE 还可以单独变址。双重变址机构增加了各处理单元存储器之间数据分配的灵活性。

(2) 阵列控制器

阵列控制器 CU 实际上是一台小型控制计算机，它除了能对阵列的处理单元实行控制以外，还能利用自己的内部资源执行一整套指令，用以完成标量的运算操作。CU 的标量操作与各 PE 的数组操作是时间重叠的。

阵列控制器 CU 同处理单元阵列之间有 $4$ 条信息通路：

• CU 总线。处理单元存储器 PEM 经过 CU 总线，把指令和数据送往阵列控制器 CU，以 $8$ 个 $64$ 位字为一个信息块。这里的指令是指分布存放在 PEM 中用户程序的指令，而数据可以是处理所需要的公共数据。指令和数据先被送到 CU，再由 CU 的广播功能把它们送到各处理单元。
• 公共数据总线 Common Data Bus, CDB 。CDB 是 $64$ 位总线，用于向 $64$ 个处理单元同时广播公共数据的通路。例如，作为公共乘数的常数就不必在 $64$ 个 PEM 中重复存放，可以由 CU 的某一个寄存器送往各处理单元。另外，指令的操作数和地址部分也要经过 CDB 送来。
• 模式位线 Mode Bit Line 。每一个 PE 都可以经过模式位线，把它的模式寄存器中的状态送到 CU 中来，送来的信息中包括该处理单元的“活动”状态位。从 $64$ 个 PE 送往 CU 的模式位，在 CU 的累加寄存器中拼成一个模式字，以便在 CU 内部执行一定的测试指令，对这个模式字进行测试，并根据测试结果来控制程序的转移动作。
• 指令控制线。处理单元微操作控制信号和处理单元存储器地址、读/ 写控制信号都经过约 $200$ 条指令控制线，由 CU 送到阵列处理单元 PE 和存储器逻辑部件 MLU 。

概括起来，阵列控制器 CU 的功能有以下 $5$ 个方面：

• 对指令流进行控制和译码，执行标量操作指令。
• 向各处理单元发出执行数组操作指令所需的控制信号。
• 产生和向所有处理单元广播公共的地址部分。
• 产生和向所有处理单元广播公共的数据。
• 接收和处理由各 PE（计算出错时）、系统I/O操作以及主机 B6700 所产生的陷阱中断信号。

(3) 输入输出系统

ILLIAC-Ⅳ 输入输出系统由磁盘文件系统 DFS ，I/O分系统和 B6700 组成。磁盘文件系统 DFS 是两套大容量并行读写磁盘系统及其相应的控制器。每套磁盘系统有 $13$ 台磁盘机，总容量为 $10^9$ 位。每台磁盘机有 $128$ 道，每道有一个磁头，并行读写，数据宽度为 $256$ 位，最大传输率为 $502\times 10^{6}bit/s$，平均等待时间为 $19.6ms$ 。如果 DFS 的两个通道同时发送或接收数据，则数据宽度为 $512$ 位，最大传输率可达 $10^{9}bit/s$ 。

I/O分系统包括 $3$ 部分，即输入输出开关 IOS 、控制描述字控制器 CDC 和输入输出缓冲存储器 BIOM 。

• IOS 的功能有两个：一是开关功能，用以把 DFS 或可能连上的实时装置转接到阵列存储器，进行大批数据的I/O传送；二是作为 DFS 和 PEM 之间的缓冲，以平衡两边不同的数据宽度。
• CDC 的功能是对阵列控制器 CU 的 I/O 请求进行管理。CU 提出 I/O 请求时，CDC 将使 B6700 管理计算机中断，由 B6700 响应输入/输出请求，并通过 CDC 给 CU送回相应的响应代码，在 CU 中设置好必要的控制状态字。然后，CDC 促使 B6700 启动 PEM 的加载过程，由 DFS 向 PEM 送入程序和数据。在 PEM 加载完毕后，又由 CDC 向 CU 传送控制信号，使 CU 开始执行 ILLIAC-Ⅳ 的程序。
• BIOM 处在 DFS 和 B6700 之间，是为了使二者之间传送频宽能够匹配。B6700 存储器经 CPU 输送数据的频宽是 $80\times 10^{6}bit/s$ ，而 DFS 输送数据的频宽是 $500\times 10^{6}bit/s$ ，二者之间相差 $6$ 倍多。因此，必须设立 BIOM 作为 B6700 和 DFS 之间的缓冲。BIOM 把 B6700 的 $48$ 位字变换为 ILLIAC-Ⅳ 的 $64$ 位字，同时按双字 $128$ 位的数据宽度输送给 DFS 。实际上，BIOM 是用 4 个 PEM 做成的，总容量为 $8192\times 64$ 位。

B6700 管理计算机的基本组成是：单中央处理器（另一个 CPU 可选），$32K$ 字内存（可扩充至 $512$ 字），经由多路开关控制连接的一批外围设备（包括一台容量为 $1012$ 位的激光外存储器以及 ARPA 网络接口）。B6700 的作用是：管理 ILLIAV-Ⅳ 的全部系统资源，完成用户程序的编译或汇编，为 ILLIAC-Ⅳ 进行作业调度、存储分配、产生输入/输出控制描述字送至 CDC 、处理中断，以及提供操作系统所具备的其他服务。

2. BSP 计算机

BSP 计算机是由美国宝来公司和伊利诺斯大学于1979年制造的，它是共享存储器结构的 SIMD 计算机的典型代表。BSP 并不是一台独立运行的计算机，它是附属于系统管理机的一台后端处理机。

BSP 计算机及系统管理机的组成框图如图6.3所示。它由系统管理计算机 B7700/B7800 和 BSP 处理机两大部分组成，前者可视为后者的前端机。系统管理机负责 BSP 程序编译、与远程终端及网络的数据通信、外围设备管理等，大多数 BSP 作业调度和操作系统活动也是在系统管理机上完成。BSP 处理机由控制处理机、文件存储器、并行存储器模块以及对准网络等组成，如图6.4所示。

(1) 并行处理机

它以 $160ns$ 的时钟周期进行向量计算。所有 $16$ 个算术单元 AE 对不同的数据组（从并行处理机控制器广播来）进行同一种指令操作。大部分的算术运算能在 $2$ 个时钟周期 $320ns$ 内完成。BSP 的执行速度最高可达 $50\text{MFLOPS}$ 。

进行向量运算的数据存储在 $17$ 个并行存储器模块中。每个模块的容量可达 $512K$ 字，时钟周期为 $160ns$ 。数据在存储器模块和 AE 之间以每秒 $100$ 兆字的速率进行传输。$17$ 个存储器模块的组织形成了一个无冲突访问存储器，它容许对任意长度以及跳距不足 $17$ 倍数的向量实现无冲突存取。

$16$ 个 AE 是以 SIMD 方式、在单一微序列控制下同步工作的。在每个 AE 中，只有最原始的操作才采用硬连线方式，控制字的宽度为 $100$ 位，除实现浮点操作以外，AE 还有较强的非数值处理能力。浮点加、减和乘都能在两个时钟周期内完成。采用两个时钟周期可使存储器频宽与 AE 进行三元操作（由三个操作数产生一个结果的操作）时的频宽相平衡。浮点除要用 $1200ns$ ，是用 Newton-Raphson 迭代算法产生倒数来实现的。在每个 AE 中设有只读存储器，以给出除法和平方根迭代的第一次近似值。浮点字长为 $48$ 位，尾数为 $36$ 位有效值，阶码为 $10$ 位，以 $2$ 为底。数的精度可达到十进制 $11$ 位。AE 在关键部位设置了双字长累加器和双字长寄存器，这就能使双精度运算直接用硬件实现。AE 还可以用软件方法实现三倍精度的算术运算。可以估算得出来，在 BSP 中用FORTRAN来表达很大范围的计算问题中，其速度可达 $20～40\text{MFLOPS}$ 。

BSP 可以对下列四类操作进行并行计算：
① 16 个算术单元实现并行运算；
② 存储器的读取/存取，存储器与算术运算单元间的数据传输；
③ 在并行处理机控制器中的变址值、向量长度和循环控制计算；
④ 线性向量操作描述字在标量处理机中的生成。

(2) 控制处理机

除了用以控制并行处理机以外，还提供了与系统管理机相连的接口。标量处理机则处理存储在控制存储器中的全部操作系统和用户程序的指令。它以 $12\text{MHz}$ 的时钟频率执行用户程序的串行或标量部分，最高速度可达 $1.5\text{MFLOPS}$ 。

全部的向量指令以及某些成组的标量指令，被送给并行处理机控制器。在经过合格性检查后，控制器将它们转换为微序列，去控制 $16$ 个 AE 操作。双极型控制存储器的容量为 $256K$ 字，周期为 $160ns$ ，每个字长 $48$ 位另加 $8$ 位奇偶校验位，提供单错校正双错检测 SECDED 的能力。控制维护单元则是系统管理机与控制处理机其余部分之间的接口，用来进行初始化、监控命令通信和维护。

(3) 文件存储器

一个半导体辅助存储器。BSP 的计算任务文件从系统管理机加载到它上面。然后对这些任务进行排队，由控制处理机加以执行。文件存储器是 BSP 直接控制下惟一的外部设备，而其他的外部设备则都由系统管理机来控制。在BSP 程序执行过程中所产生的暂存文件和输出文件，在将它们送给系统管理机输出给用户之前，是存在文件存储器中的。文件存储器的数据传输率较高，大大地缓解了 I/O 受限问题。

(4) 对准网络

包含完全交叉开关，和用来实现数据从一个源广播至几个目的地、以及当几个源寻找一个目的地时能分解冲突的硬件。这就需要在算术单元阵列和存储器模块之间，具备通用的互连特性。而存储器模块和对准网络的组合功能，则提供了并行存储器的无冲突访问能力。算术单元也利用输出对准网络，实现一些诸如数据压缩和扩展操作、以及快速傅立叶变换算法等专用功能。

在 BSP 中，存储器—存储器型的浮点运算是流水进行的。BSP 的流水线组织由 $5$ 个功能级组成。$16$ 个操作数先从存储器模块中取出，通过输入对准网络送给 AE 进行处理，再将结果经输出对准网络，送给存储器模块存储起来。这几级的操作都是重叠进行的（参见图6.4）。

请注意，在物理上，输入对准和输出对准都是在一个实际对准网络中进行的，这里的划分只是对流水级的功能划分而已。除了在 $16$ 个 AE 中显示出的空间并行性，以及读取、对准和存储的流水线操作外，AE 中的向量运算还可以同标量处理机中的标量处理重叠起来。这就使得系统既适合于处理长向量和短向量，也能处理单独的标量，系统的功能很强也很灵活。

(5) 质数存储系统

BSP 并行存储器由 $17$ 个时钟周期为 $160ns$ 的存储模块组成。由于每个周期存取 $16$ 个字，因此每个字的最大有效存储周期时间为 $10ns$ 。这与算术单元完成浮点加和乘的速率很好地平衡。因为每次运算需要两个变量，算术单元中设有中间寄存器其运算速度为 $320ns/16$ 次，即 $20ns/次$ 。

由于程序和标量都存放在控制存储器中，因此只有数组存取（包括 I/O）才用到并行存储器。这样，对于三元向量来说，因为在两次算术运算中需要用到 $3$ 个变量，产生 $1$ 个结果，共访问存储器 $4$ 次，所以在并行存储器和浮点运算之间的频带保持完全平衡；对于长向量来说，由于中间结果都存在寄存器中，每次运算只需要一个操作数，因此并行存储器有足够的频宽，留给输入和输出信息使用。

---

6.3 SIMD 并行计算机算法

SIMD 并行计算机是从求解诸如有限差分、矩阵运算、信号处理、线性规划等一系列计算为背景发展起来的。下面以图像平滑算法为例，讲述该算法如何在并行机上实现。

该算法是用来平滑输入图像的灰度级，$I$ 和 $S$ 分别表示输入和输出图像。假定 $I$ 和 $S$ 均含有 $512\times 512$ 个像素。$I$ 中的每个点是一个 $8$ 位无符号整数，用来表示 $256$ 个灰度级——每个像素的灰度级是用来表示像素的黑色程度，以 $0$ 表示白色，以 $255$ 表示黑色。平滑后图像中的每个点 $S(i,j)$ 是 $I(i,j)$ 和它的 $8$ 个最邻近的像素的灰度级的平均值。$S$ 中的上、下、左、右边线上的像素，由于在 $I$ 中的相应像素没有 $8$ 个邻近像素，因而置为 $0$ 。

若用具有 $1024$ 个 PE 的阵列机来实现上述算法，可如图6.5(a)所示那样排列成 $32\times 32$ 方阵。在每个 PE 中存储一个 $16\times 16$ 的子图像块（整个 I 图像为 $512\times 512$ 像素块）。 PE0 中存储行 $0～15$ 和列 $0～15$ 的子图像块，PE1 中存储行 $0～15$ 和列 $16～31$ 的子图像块，依此类推。每个 PE 平滑自己的子图像，而所有 PE 可同时进行平滑操作。在每个 $16\times 16$ 子图像的边界处，为了计算已平滑的值，数据必须在 PE 间传送。图6.5(b)中示出了所必须传送的数据。

阵列机的每个 PE 都有类似于单处理单元的数据传送模式。要对 $512\times 512$ 图像完成平滑操作，在上述的每块为 $16\times 16$ 大小的子图像块上用并行处理方法来完成平滑，则需 $16\times 16=256$ 次并行的平滑操作。在操作过程中，总共所需的并行数据元素的传送数为 $4\times 16+4=68$ ——上，下，左，右 $4$ 边每边需 $16$ 次，而 $4$ 个对角上每个需 $1$ 次，参见图6.5(b)。

对同样大小的图像，若用串行算法来完成，虽然此时不需要进行 PE 间的数据传送，但总共却需要 $512\times 512=262144$ 次平滑操作。因此，并行算法就比串行算法快 $1024$ 倍。如果计入 PE 间传送所需时间，并假定每次并行数据传送时间相当于一次平滑操作时间，则改进倍数仍可达到：
$$262144/(256+68)=809$$ 另外，就所占比例而言，数据传送所需时间几乎可以忽略不计。

6.3.1 矩阵加

阵列处理机解决矩阵加是最简单的一维情况。两个 $8\times 8$ 的矩阵 $A,B$ 相加，所得的结果矩阵 $C$ 也是一个 $8\times 8$ 的矩阵。只需把 $A,B,C$ 居于相应位置的分量存放在同一个 PEM 内，且在全部 $64$ 个 PEM 中，让 $A,B,C$ 的各分量地址均对应取相同的地址 $\alpha ,\alpha +1,\alpha +2$ ，如图6.6所示。
这样，实现矩阵加只需用下列三条 ILLI-AC-Ⅳ 汇编指令：

LDA ALPHA 			；全部 (α) 由 PEMi 送 PEi 的累加器 (RGAi)
ADRN ALPHA + 1 		；全部 (α+1) 与 (RGAi) 浮点加, 结果送 (RGAi)
STA ALPHA + 2 		；全部 (RGAi) 由 PEi 送 PEMi 的 (α+2) 单元, 0≤i≤63
1
2
3

从这个例子可以明显看出，阵列处理机的单指令流（$3$ 条指令顺序执行）、多数据流（$64$ 个元素并行相加） 以及数组并行中的“全并行”工作特点。由于是全部 $64$ 个处理单元在并行操作，速度就提高为顺序处理的 $64$ 倍。同时也可以看出，对于具有分布式存储器的阵列处理机，能否发挥其并行性与信息在存储器的分布密切相关。而信息分布算法又与系统结构及所解题目直接相关，因此，存储单元分配算法的设计比较麻烦。

6.3.2 矩阵乘

矩阵乘是二维数组运算，比矩阵加要复杂。设 $A,B,C$ 为 $3$ 个 $8\times 8$ 的二维矩阵，给定 $A$ 和 $B$ ，计算 $C=A\times B$ 的 $64$ 个分量可用公式：
$$C_{ij}=\sum _{k=0}^7{a}_{ik}\times b_{kj}(0\le i\le 7\wedge 0\le j\le 7)$$ 在 SISD 计算机上求解，可执行用FORTRAN语言编写的下列程序：

DO 10 I = 0, 7
DO 10 J = 0, 7
C(I, J) = 0
DO 10 K = 0, 7
10 C(I, J) = C(I, J) + A(I, K) × B(K, J)
1
2
3
4
5

需经 $I,J,K$ 三重循环完成。每重循环执行 $8$ 次，共需 $512$ 次乘、加的时间，且每次还要包括执行循环控制判别等其他操作所需的时间。

如果在 SIMD 阵列处理机上运算，可用 $8$ 个处理单元并行计算矩阵 $C（I,J）$ 的某一行或某一列，即将 $J$ 循环或 $I$ 循环转化成一维的向量处理，从而消去了一重循环。以消去 $J$ 循环为例，可执行用FOR-TRAN 语言编写的下列程序：

DO 10 I = 0, 7
C(I, J) = 0
DO 10 K = 0, 7
10 C(I, J) = C(I, J) + A(I, K) × B(K, J)
1
2
3
4

让 $J=0～7$ 各部分同时在 PE0 ～ PE7 上运算，这样只需 $I,K$ 二重循环，速度可提高 $8$ 倍，即只需 $64$ 次乘、加时间。其程序流程图如图6.7所示。

需要说明的是，其执行过程虽与 SISD 的类似，但实际的解决方式是不同的。每次控制部件执行的 PE 类指令表面上是标量指令，实际上已等效于向量指令，如向量取、向量存、向量加、向量乘等，是 8 个 PE 并行地执行同一条指令。每次播送时，利用阵列处理机的播送功能，将处理单元 PEK 中累加寄存器 RGAK 的内容，经控制部件 CU 播送到全部 $8$ 个处理单元的 RGA 中去。

然而，为了让各个处理单元 PEi 尽可能只访问所带局部存储器 PEMi ，以保证高速处理，就必须要求对矩阵 $A,B,C$ 各分量在局部存储器中的分布，采用如图6.8所示的方案。

如果把 ILLIAC-Ⅳ 的 $64$ 个处理单元全部利用起来并行运算，即把 K 循环的运算也改为并行，还可以进一步提高速度，但需要在阵列存储器中重新恰当地分配数据，同时还要使 $8$ 个中间积 $A(I,K)\times B(K,J)$ 能够并行相加（其中，$0\le K\le 7$），这就要用到下面的累加和并行算法。即使如此，就 $K$ 的并行来说，速度的提高也不是 $8$ 倍，而只是 $8/{\log }_{2}8$ ，接近于 $2.7$ 倍。

6.3.3 累加和

这是一个将 $N$ 个数的顺序相加转为并行相加的问题。为得到各项累加的部分和以及最后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元才能执行相应的操作。为叙述方便取 $N=8$ ，即有 $8$ 个数 $A(I)(0\le i\le 7)$ 顺序累加。

在 SISD 计算机上可以写成下列FORTRAN程序：

C = 0
DO 10 I = 0, 7
10 C = C + A(I)
1
2
3

这是一个串行程序，需要 $8$ 次加法时间。在阵列处理机上用成对递归相加算法，只需 $lo{g}_{2}8=3$ 次加法时间即可。首先，原始数据 $A（I）$ 分别存放在 $8$ 个 PEM 的 $\alpha$ 单元中，其中 $0\le i\le 7$ 。然后，按下面的步骤求累加和：

1. 置全部 PEi 为活跃状态，$0\le i\le 7$ ；
2. 全部 $A(I)$ 从 PEMi 的 $\alpha$ 单元读到相应 PEi 的累加寄存器 RGAi 中，$0\le i\le 7$ ；
3. 令 $K=0$ ；
4. 将全部 PEi 的 RGAi 转送到传送寄存器 RGRi，$0\le i\le 7$ ；
5. 将全部 PEi 的 RGRi 经过互连网络向右传送 $2^K$ 步距，$0\le i\le 7$ ；
6. 令 $j=2K-1$ ；
7. 置 PE0 ~ PEj 为不活跃状态；
8. 处于活跃状态的所有 PEi 执行 （RGAi） :=（RGAi） +（RGRi） ，$j\le i\le 7$ ；
9. $K=K+1$ ；
10. 如 $K<3$ ，则转回步4，否则往下继续执行；
11. 置全部 PEi 为活跃状态，$0\le i\le 7$ ；
12. 将全部 PEi 的累加寄存器内容 RGAi 存入相应 PEMi 的 $\alpha +1$ 单元中，$0\le i\le 7$ 。
    

图6.9描绘了阵列处理机上累加和的计算过程。框中的数字表明各处理单元每次循环后相加的结果。图中用数字 $0～7$ 分别代表 $A(0)～A(7)$ 。画有阴影线的处理单元表示此时不活跃。另外，图中对上述第5步中 PE 的 RGRi 在右移时超出 PE7 的内容没有表示出来，这是因为若右移步距为 2K（mod 8） ，应移入 PE0 ～ PEi，而这些 PE 在第7步将要置为不活跃，所以无论它的 RGR 接受什么内容都不会对执行结果有影响。

上面的例子表明，虽然经过变换，在 IL7LIAC-Ⅳ 上可以实现累加和的并行运算，但由于屏蔽了部分处理单元，降低了它们的利用率，所以速度不是提高 $N$ 倍，而只是 $\frac{N}{{\log }_{2}N}$ 倍。

---

6.4 SIMD 计算机的互连网络

6.4.1 互连网络的设计目标

在 SIMD 计算机中，无论是处理单元之间，还是处理单元和存储模块之间，都要经互连网络来实现信息交换。因此，互连网络性能好坏对 SIMD 计算机系统的运算速度、处理单元的使用率、求解算法适应性、拓扑结构灵活性以及成本等有很大影响，所以它是 SIMD 计算机中重要的研究课题之一。

若把处理单元或存储模块看成节点，则互连网络实际是为输入和输出两组节点之间提供数据通路或映像。对于 $N$ 个输入和 $N$ 个输出来讲，由于不允许有多对一的映像（因为会造成访问冲突），由输入到输出映像共有 $N^N$ 种，如果限定为一对一映像，则只有 $N!$ 种映像。

衡量互连网络性能好坏的主要因素，是它的连接度、延时性、带宽、可靠性、成本。连接度是指一个节点与其他节点的连接程度。如果一个节点直接连接的其他节点数越多，连接度就越高，表明连接性越好。延时性是指从一个节点传送信息到任何一个节点所需的时间，通常可用节点间最大距离加以表示。

在设计互连网络时，应考虑以下四个方面的问题，这些问题是设计互连网络的重要依据，设计时必须综合考虑加以合理组合：

1. 通信工作方式：分为同步和异步两种。在同步方式中，不论是各个 PE 对数据进行并行操作、还是由控制器向处理单元广播命令，都由统一的时钟来加以同步，SIMD 并行机都采用这种方式。异步方式则不用统一时钟加以同步，各个处理单元根据需要相互建立动态连接。
2. 控制策略：分为集中和分散两种。集中式控制中，由一个统一控制器对各个互连开关状态加以控制，而分散式控制则由各个互连开关自身实行管理。一般的 SIMD 并行机都采用集中控制。
3. 交换方式：分为线路交换和分组交换两种。线路交换是在整个交换过程中，在源和目标节点之间建立固定的物理通路，适用于成批数据传送。分组交换则把要传送的一个信息分成多个分组，分别送入互连网络，这些分组可通过不同的路由到达目标节点。因此，较适合于短数据报文的传送。SIMD 并行机一般采用线路交换，因为处理单元间的连接比较紧密。MIMD 多机系统则往往采用分组交换方式。
4. 网络拓扑：分为静态和动态两种。这里的拓扑是指互连网络中的各个节点间的连接关系，通常用图来描述。静态拓扑是指在各节点间有专用的连接通路，且在运行中不能改变。动态拓扑则因设置有源开关，因而可根据需要，借助控制信号对连接通路加以重新组合。静态拓扑一维的有线性阵列结构，二维的有环形、星形、树形、网格形等，三维的有立方体等，三维以上的有超立方体等。

由以上分析可知，SIMD 系统的互连网络的设计目标是：
① 结构不要过分复杂，以降低成本；
② 互连要灵活，以满足算法和应用的需要；
③ 处理单元间信息交换所需传送步数要尽可能少，以提高速度性能；
④ 能用规整单一的基本构件组合而成，或者经多次通过、或者经多级连接来实现复杂的互连，模块性好，以便于用 VLSI 实现并满足系统的可扩充性。

6.4.2 互连函数

互连函数是反映「互连网络连接特性」的一组定义。如果将互连网络中的 $N$ 个输入节点和 $N$ 个输出节点的节点号，用十进制 $0,1,2,\dots ,N-1$ 表示，则每一个节点的地址也可用 $n={\log }_{2}N$ 位二进制表示。如某一输入节点的二进制地址为 $x_{n-1}{x}_{n-2}\dots x_1{x}_0$ ，则与此节点相连的输出节点的二进制地址，可用互连函数 $f(x_{n-1}{x}_{n-2}\dots x_1{x}_0)$ 表示。

下面讨论几种常用的互连函数及其图形表示。

1. 恒等置换函数

$N$ 个节点的恒等置换函数的表达式为：
$$I(x_{n-1}{x}_{n-2}\dots x_1{x}_0)=x_{n-1}{x}_{n-2}\dots x_1{x}_0$$ 在此表达式中，输入节点的二进制地址与输出节点的二进制地址相同。当 $N=8$ 时，其表达式为：
$$I(x_2{x}_1{x}_0)=x_2{x}_1{x}_0$$

2. 方体置换函数

$N$ 个节点的方体 Cube 置换函数有 $n={\log }_{2}N$ 个，其中第 $K(K=0,1,\dots ,n-1)$ 个函数的表达式为：
$$C_k(x_{n-1}{x}_{n-2}\dots x_{k+1}{x}_k{x}_{k-1}\dots x_1{x}_0)=x_{n-1}{x}_{n-2}\dots x_{k+1}\overline{x_k}{x}_{k-1}\dots x_1{x}_0$$ 由上式可知，方体置换是实现第 $K$ 位求反连接。

当 $N=8$ 时，共有 $n=3$ 个方体置换函数（$K=0,1,2$）分别为：
$$\begin{gathered} C_0(x_2{x}_1{x}_0)=x_2{x}_1\overline{x_0} \\ {C}_1(x_2{x}_1{x}_0)=x_2\overline{x_1}{x}_0 \\ {C}_2(x_2{x}_1{x}_0)=\overline{x_2}{x}_1{x}_0 \end{gathered}$$ 输入与输出节点的互连形式如图6.10所示。

3. 全混洗置换函数

全混洗 Shuffle 置换又称为均匀洗牌置换，其函数表达式为：
$$S(x_{n-1}{x}_{n-2}\dots x_1{x}_0)=x_{n-2}\dots x_1{x}_0{x}_{n-1}$$ 由上式可见，全混洗置换函数实现的是，将输入端二进制地址循环左移一位，即得到输出端的二进制地址。

当 $N=8$ 时的全混洗函数式为：$S(x_2{x}_1{x}_0)=x_1{x}_0{x}_2$ ，输入与输出节点互连形式如图6.11所示。

4. 交换置换函数

$N$ 个节点的交换 Exchange 置换函数的表达式为：
$$E(x_{n-1}{x}_{n-2}\dots x_1{x}_0)=x_{n-1}{x}_{n-2}\dots x_1\overline{x_0}$$ 由上式可知，交换函数实现的是输入与「最低位求反的输入二进制地址」相连接。当节点数 $N=8$ 时，其交换函数的表达式为：
$$E(x_2{x}_1{x}_0)=x_2{x}_1\overline{x_0}$$ 输入与输出节点互连形式如图6.12所示。

5. 蝶式置换函数

$N$ 个节点的蝶式 Butterfly 置换函数的表达式为：
$$B(x_{n-1}{x}_{n-2}\dots x_1{x}_0)=x_0{x}_{n-2}\dots x_1{x}_{n-1}$$ 由上式可见，蝶式置换函数实现的是将输入端二进制地址的最高位和最低位相互交换，即可得到对应的输出端地址。

当 $N=8$ 时的蝶式函数式为：
$$S(x_2{x}_1{x}_0)=x_0{x}_1{x}_2$$ 输入与输出节点互连形式如图6.13所示。

6. 子蝶式置换函数

与方体置换函数相类似，$N$ 个节点的子蝶式置换函数的表达式共有 $n={\log }_{2}N$ 个，其中第 $K(K=0,1,\dots ,n-1)$ 个函数表达式为：
$$B_k(x_{n-1}{x}_{n-2}\dots x_{k+1}{x}_k{x}_{k-1}\dots x_1{x}_0)=x_{n-1}{x}_{n-2}\dots x_{k+1}{x}_0{x}_{k-1}\dots x_1{x}_k$$ 由上式可见，第 $K$ 个子蝶式置换函数实现的是，将输入端二进制地址的第 $K$ 位与最低位相互交换，即可得到对应的输出端地址。

当 $N=8$ 时有 $3$ 个子蝶式函数式为：
$$\begin{gathered} B_0(x_2{x}_1{x}_0)=x_2{x}_1{x}_0 \\ {B}_1(x_2{x}_1{x}_0)=x_2{x}_0{x}_1 \\ {B}_2(x_2{x}_1{x}_0)=x_0{x}_1{x}_2 \end{gathered}$$ 输入与输出节点互连形式如图6.14所示。

7. 移数置换函数

移数置换是通过输入端数组循环的一定位置，得到输出端的地址，其表达式为：
$$\alpha (x)=(x+K)\mathrm{m}\mathrm{o}\mathrm{d}N(0\le x\le N-1)$$ 式中，$K$ 为常数，指移过的位置。还可把整个输入数组分成若干个子数组，在子数组内进行循环移数，称之为段内循环移数，其表达式可用两个式子表示为：
$$\begin{gathered} \alpha (x{)}_{(n-1):r}=(x{)}_{(n-1):r} \\ \alpha (x{)}_{(r-1):0}=[(x{)}_{(r-1):0}+K]\mathrm{m}\mathrm{o}\mathrm{d}{2}^r \end{gathered}$$

式中，下标 $(n-1):r$ 和 $(r-1):0$ 分别是指从 $(n-1)$ 位到 $r$ 和 $(r-1)$ 位到 $0$ 位。$N=8$ 个节点的移数置换和段内循环移数置换举例如图6.15所示。

8. PM2I 置换函数

$N$ 个节点的 PM2I（Plus-Minus，加减 $2^i$ ）置换函数共有 $2n(n={\log }_{2}N)$ 个。其基本表达式为：
$$\begin{gathered} PM{2}_{+i}(j)=j+2^i\mathrm{m}\mathrm{o}\mathrm{d}N \\ PM{2}_{-i}(j)=j-2^i\mathrm{m}\mathrm{o}\mathrm{d}N \end{gathered}$$ 式中，$0\le j\le N-1,0\le i\le n-1$ 。由于 $PM{2}_{+(n-1)}=PM{2}_{-(n-1)}$，所以 PM2I 互连函数只有 $2n-1$ 种是不相同的。

当 $N=8$ 时，PM2I 互 连 函 数 有：$PM{2}_{+0},PM{2}_{-0},PM{2}_{+1},PM{2}_{-1},PM{2}_{+2},PM{2}_{-2}$ 。其中 $PM{2}_{+2}=PM{2}_{-2}$ ，所以共有 $5$ 个互不相同的函数（用循环函数表示）如下：
P M 2 + 0   :   ( 0   1   2   3   4   5   6   7 ) P M 2 − 0   :   ( 7   6   5   4   3   2   1   0 ) P M 2 + 1   :   ( 0   2   4   6 ) ( 1   3   5   7 ) P M 2 − 1   :   ( 6   4   2   0 ) ( 7   5   3   1 ) P M 2 ± 2   :   ( 0   4 ) ( 1   5 ) ( 2   6 ) ( 3   7 )

$$\begin{aligned} &PM2_{+ 0} \ :\ ( 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7) \\ &PM2_{- 0} \ :\ ( 7\ 6\ 5\ 4\ 3\ 2\ 1\ 0) \\ &PM2_{+ 1} \ : \ ( 0\ 2\ 4\ 6) ( 1\ 3\ 5\ 7) \\ &PM2_{- 1} \ : \ ( 6\ 4\ 2\ 0) ( 7\ 5\ 3\ 1) \\ &PM2_{± 2} \ : \ ( 0\ 4) (1\ 5) ( 2\ 6) (3\ 7) \end{aligned}$$ ​PM2+0​ : (0 1 2 3 4 5 6 7)PM2−0​ : (7 6 5 4 3 2 1 0)PM2+1​ : (0 2 4 6)(1 3 5 7)PM2−1​ : (6 4 2 0)(7 5 3 1)PM2±2​ : (0 4)(1 5)(2 6)(3 7)​ 其中，$（01234567）$ 表示 $0$ 连到 $1$ ，$1$ 连到 $2$ ，$2$ 连到 $3,\dots ,7$ 连到 $0$ 。图6.16表示出 $N=8$ 个节点之间的部分连接情况。

6.4.3 互连网络的分类和结构参数

互连网络是由开关元件按照「一定的拓扑结构的控制方式」构成的网络，用来实现计算机系统内部「多个处理机或多个功能部件」之间的相互连接。

1. 互连网络的分类

从几何形状看互连网络可分为两大类：规则网和不规则网。规则网又可分为静态网和动态网，如图6.17所示。在分析这些网络时，把连接的对象（如处理机、运算部件、存储器等）称为节点，对应的单向或双向通路称为边。

• 静态网又叫直接互连网，又可进一步分为全互连网、星形网、总线、循环移数网、一维线性网、环形网、网格网、树形网、超立方体网、带环立方体网、$m$ 元 $n$ 立方体网、Paradhan 网等。
• 动态网又叫间接互连网，也可进一步分成交叉开关网、单级互连网、多级互连网。
  多级互连网又可分为阻塞网、可重排非阻塞网、非阻塞网。非阻塞网有三级 Clos 网。
  可重排非阻塞网有 Benes 网、字节分类网、Memphis 网。阻塞网又有 $\Omega$ 网、STARAN 网、间接二进制 $n$ 方体网，基准网、$\delta$ 网、数据交换网等。
  

2. 互连网络的结构参数

对于静态互连网络，在分析各种网络的拓扑结构前，先定义一些参数。一般网络是用有向边或无向边、以及连接的有限个节点组成的图来表示的。图中节点与处理机、功能部件相对应，边则与通信链路相对应。节点数称为网络的规模。

(1) 度

在互连网络拓扑图中，节点所连接的边（链路或通道） 数称为该节点的度 $k$ 。在单向通道的情况下，进入节点的通道数叫入度，从节点出来的通道数叫出度。该节点的度就是二者之和。节点的度反映了节点所需 I/O 端口数，也代表了节点的价格。网络中各节点的度的最大值叫做该网络的度，记为 $K$ 。

(2) 距离和直径

网络中，任意两节点间沿最短路径通信所经过的边数，称为这两个节点间的距离，记为 $d$ 。任意两节点间距离的最大值称为该网络的直径，记为 $D$ 。

(3) 中继量 $R$

由 $n$ 个节点组成的网络，在各节点间有 $\frac{n(n-1)}{2}$ 条通信路径组合（不是边数，而是边的组合数）。在两节点之间肯定有一条最短的通信路径，也就是两节点间的距离 $d$ 。两节点间的中继次数等于这两节点间的距离减“1”。

一个节点的中继量，是指「除自己以外的其他节点」通过自己节点的通信路径条数。网络中继量是指中继量最多的那个节点的中继量，记为 $R$ 。当然，网络中继量越大，并行处理的效果就越差（？），如果中继量大多集中在部分节点上，就会造成这些节点上的瓶颈效应，影响整个系统并行处理的效果。所以希望平均中继量 $r$ 能等于或接近最大中继量 $R$ 。

(4) 通路的方向性

在互连网络中，通信链路可以是单工的，也可以是半双工或全双工的。单工用有向图表示，半双工或全双工用无向图表示。

(5) 规则性和对称性

规则性是指网络节点互连遵循确定的规则。在规则性好的网络中，各节点连接的相邻节点数常常是相等的。任意两节点间通信的路径算法比较规则和简单。

规则性还可以用对称性来描述。在全对称互连网络中，每个节点在图中的地位是等同的。环形网络就是全对称网络。半对称网络中，只有部分节点在几何位置上与余下部分节点对称，但不存在全部节点地位等同的关系，树形网络就是半对称网络。

(6) 广播时间

广播是指一个节点同时向其他所有节点发送相同的数据，常用于管理节点向其他作业节点发送程序或发送初始数据。广播时，各处理机节点一边中继一边接收，所以，比分别向所有的节点传送数据要快得多，最好把管理节点放置在可以广播最快的位置上。广播时间是指从管理节点广播的数据，到达所有节点的传送次数，记为 $T$ 。

以上各种参数从不同的侧面影响着网络的性能，一般我们要权衡以下因素：

• 网络的功能，是指网络所支持的互连函数、中断处理、同步、消息的组合和一致性问题，可根据系统需要选择合适的功能。
• 网络的延迟，是指单位信息通过网络时最大的时间延迟。网络的延迟当然是越小越好，它与网络的直径、中继量及对称性有关。
• 网络的带宽，指通过网络的最大传输率。
• 网络的硬件复杂度，指的是开关以及连接器、仲裁及接口逻辑等的开销。这与网络的度、功能等有关。
• 网络的可扩展性，是指在网络拓扑性能保持不变的情况下，可扩充节点的能力。
• 此外，还要考虑网络节点的合理编址、路径的冗余度、节点是否为同构、通道是否有缓冲等各种因素。但这些因素往往是相互矛盾的，只能根据环境要求，统筹兼顾各种指标，寻求相对合理的方案。

下面，开始分析静态互连网络和动态互连网络的拓扑结构。

6.4.4 静态互连网络

静态互连网络是节点之间直接互连。每个开关元件固定与一个节点相连，以建立该节点与邻近节点之间的被连接通路。这种网络一旦构成以后就固定不变了，比较适合于构成「通信模式可预测的」并行处理系统和分布计算机系统。

下面我们根据网络参数、以及它们对网络通信和可扩展性的影响等几个方面，分析各种静态互连网络的拓扑结构。

1. 线性网和星形网

一维线性阵列是每个节点只与其左、右近邻节点相连（首尾例外） 的最简单连接方式，如图6.18(a)所示。一维线性阵列网络的度 $K=2$ ，直径 $D=N-1$ ，等分宽度为 $1$ ，不对称。当 $N$ 很大时，通信效率很低。

星形网络的拓扑结构如图6.18(b)所示。一主节点处理机作为主控机位于中心位置，分别与其他所有从节点处理机相连接，这些从节点之间的通信必须通过主节点进行中继。因此，主节点为系统的瓶颈，对其工作性能要求非常高。一旦主节点处理机出现故障，整个系统都将瘫痪。在星形网络的结构中，主节点度 $k=N-1$ ，从节点度 $k=1$ 。从节点间的通信距离 $d=2$ 。

2. 环网和带弦环网

如果把线性网的两端连在一起，便形成了环网，如图6.19(a)所示。环网缩短了线性阵列网的直径，而且结构也很简单。环网的节点度 $k=2$ ，单向环网的直径 $D=N-1$ ，双向环网的直径 $D=N/2$ 。如果要将网络的节点度提高，可用带弦环网来实现，如图6.19(b)所示。

3. 循环移数网和全连接网

循环移数网是把环网上的每个节点，到与其距离为 $2$ 的整数幂的节点之间增加一条链路连接而成。图6.20(a)中的带弦环网也可看成是循环移数网，图中的每一节点与其相距 $2^i$ 节点之间有一条链路。如果网络规模为 $N=2^n$ ，那么网络节点度 $k=2n-1$ ，网络直径 $D=n/2$ 。

全连接网是指当带弦环网的节点度增加到 $N-1$ 时的连接网，如图6.20(b)所示。该网络的节点度为 $N-1$ ，直径为 $1$ 。这种网络构成硬件开销较大，一般难以实现。

4. 完全二叉树形网和二叉胖树形网

$N$ 个节点的完全二叉树共有 $k$ 层，其中，$N=2^k-1$ ，如图6.21(a)所示，最大节点度为 $3$ ，网络直径是 $2(k-1)$ 。由于节点度为一常数，因此它是一种可扩展的系统结构。

二叉胖树形网络如图6.21(b)所示。二叉胖树形网是在传统的完全二叉树形网基础上提出的，那是因为传统二叉树中的根节点是网络通信中的瓶颈，为了缓解这一矛盾，在越靠近根节点的地方，增加其链路数。

5. 网格形网络

网格形网络是将邻近节点按一定规则的平面几何图形相互连接而成，如图6.22所示。图6.22(a)为四边形网格，网络的度为 $4$ 、直径为 $2\sqrt{N}$ 。图6.22(b)为六边形网格，网络的度为 $3$ 、直径为 $2\sqrt{N}$ 。图6.22 c)为闭合螺线阵列网，由于这种网首先是在 ILLIAC-Ⅳ 阵列机上实现的，故又称为 ILLIAC 网，网络的度为 $4$ 、直径为 $\sqrt{N}-1$ 。

6. 立方体网络

最基本的立方体网络是二元三立方体网络，简称立方体网络或单级立方体网络。它是一种非常有用的拓扑结构，不仅在静态互连网络中使用，在动态互连网络中也广泛应用。

立方体网络可用方体互连函数来描述。当 $N=8$ 时，共有 $n=3$ 个置换函数，它们分别为：

• $C_0(x_2{x}_1{x}_0)=x_2{x}_1\overline{x_0}$（ $x$ 方向的连接）
• $C_1(x_2{x}_1{x}_0)=x_2\overline{x_1}{x}_0$（ $y$ 方向的连接）
• $C_2(x_2{x}_1{x}_0)=\overline{x_2}{x}_1{x}_0$（ $z$ 方向的连接）

立方体网络如图6.23所示。

在图6. 23中网络共有 $8$ 个节点，每个节点处于一个三维立方体的顶点上。如果将这些节点的地址按一定规律编号，即用地址的二进制码相差一位的各对节点一一相连，便构成了图中的立方体网。立方体网络的度为 $3$ 、直径也为 $3$ 。

立方体网络的寻径算法是：对源节点和目的节点的二进制地址逐位异或，然后根据所得的结果进行寻址。例如源节点地址为 $111$ ，目的节点地址为 $100$ ，二者异或的结果是 $011$ 。如果我们将节点地址的最低位定为 $x$ 方向，中间位定为 $y$ 方向，最高位定为 $z$ 方向，那么在异或结果中，若某位为 $0$ ，表示在寻址过程中该位对应的方向上没有移动；若某位为 $1$ ，则表示在相应的方向上移动一步。在这个例子中，寻径过程是：从 $111$ 节点出发，在 $x,y$ 方向上各走一步，就到达了目的节点 $100$ 。

立方体网络的用途极广，可用于合并、$FFT$、置换、排序、卷积及矩阵等并行运算。其不足之处是网络的扩充性比较差，节点必须以 $2^N$ 来增加，才能保证扩展后的网络仍是方体结构，例如超立方体网络等。

6.4.5 动态互连网络

动态互连网络是为了达到多用或通用的目的，根据程序要求实现各种通信模式的互连网络。在动态互连网络中，各节点之间不是直接固定连接的，而是在控制信号的作用下，通过网络开关的设置来建立节点之间间接的、可变的连接通路。

动态互连网络中的单级互连网络拓扑结构，与静态互连网络拓扑结构相同——把静态网络的固定连接换成开关，便是单级互连网络，所以有人把静态网络叫单级网络，动态网络叫多级网络。交叉开关网络既是单级网络又是动态网络。

1. 互连网络中的三个参量

动态互连网络，特别是动态多级互连网络的结构可以用交换开关、连接模式（ 拓扑结构）和控制方式三个参量来描述。

(1) 交换开关

动态互连网络中的交换开关是一个有源的开关元件，它可根据控制信号的不同，工作在各种不同的状态，从而实现输入端和输出端的不同连接。开关的输入端数 $a$ 和输出端数 $b$ 可以相等，也可以不相等。当二者相等时，一般选 $a=b=2^k,k\ge 1$ 。常用的交换开关有 $2\times 2,4\times 4,8\times 8$ 等。

在这些开关中，每个输入可同时与一个或多个输出相连，但不能有两个以上的输入端与一个输出端同时相连。如果出现这种情况，就会发生冲突或争用。所谓冲突，是指要求将一个输入端连到一个输出端时，该输出端已被占用的状态。所谓争用，是指两个以上的输入端同时要求连至同一输出端的情况。当发生冲突或争用时，要采取相应的措施来解决。

现以 $2\times 2$ 开关为例说明其工作状态。如图6.24 所示，$2\times 2$ 的交换开关有四种状态：

• 直连：是上输入端与上输出端相连，下输入端与下输出端相连。
• 交换：是上输入端与下输出端相连，下输入端与上输出端相连。
• 上播：是上输入端与上、下两输出端同时相连，下输入端不用。
• 下播：是下输入端与上、下两输出端同时相连，上输入端不用。
  

(2) 连接模式

连接模式也称为网络中的拓扑结构，它是指多级互连网络的各级开关之间链路的互连模式。连接模式实现的互连函数不同，就可以构成各种不同的多级互连网络。

(3) 控制方式

控制方式是指对网络中各级开关的控制方式，一般有三种控制方式：

• 级控方式：同级开关用一个信号来控制，所有开关都处于同一种工作状态。其优点是控制简单、实现容易，但网络能实现的互连函数少。
• 单元控制：每一个开关都有单独的控制信号，同一级的开关可以处于不同的工作状态，也可以处于相同的工作状态。其优点是网络实现的互连函数多，但控制复杂，实现较困难。
• 部分级控制：用 $i+1$ 个控制信号来控制第 $i$ 级的所有开关，其中 $0\le i\le n-1$ ，$n$ 为级数。这种方式是介于上述两种控制方式之间的一种。

衡量和选择一个多级互连网络，一般从以下几个方面考虑：
① 连接特性好，即实现的互连函数多；
② 网络延时小；
③ 开关设备量少；
④ 控制简单；
⑤ 便于集成。
当然，以上几个方面有的是互相矛盾的，可根据自己的需要去综合权衡选择。

2. 单级互连网络

单级互连网络是由一级开关组成的网络，它只能实现有限的几种基本连接，如前面所述各种静态网的连接形式，但一次通过不能实现任意节点间的互连——这里的一次通过是指，从输入端到输出端能一次通过网络，无冲突地按某种置换实现数据传输。

要实现任意节点间的互连有两种办法：一是循环使用同一套单级互连网络，组成循环互连网络，所以单级互连网络又叫循环网络；二是把多套相同或不同的单级互连网络串联起来，组成多级互连网络。如果把多级互连网络再循环使用，或背靠背连接，又可组成可重排非阻塞网络。

在这一小节中，只对组成多级互连网络的「常用的几种单级互连网络」进行分析，最后介绍全连接的交叉开关网络。

(1) PM2I 单级互连网络

PM2I 网络是加减 $2^i$ 网络的简称，又叫桶形移位器或循环移数网。当 $N=8$ 时，$5$ 个互不相同的函数（用循环函数表示）如下：
P M 2 + 0 :   ( 0   1   2   3   4   5   6   7 ) P M 2 − 0 :   ( 7   6   5   4   3   2   1   0 ) P M 2 + 1 :   ( 0   2   4   6 ) ( 1   3   5   7 ) P M 2 − 1 :   ( 6   4   2   0 ) ( 7   5   3   1 ) P M 2 ± 2 :   ( 0   4 ) ( 1   5 ) ( 2   6 ) ( 3   7 )

$$\begin{aligned} &PM2_{+ 0} :\ ( 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7) \\ &PM2_{- 0} :\ ( 7\ 6\ 5\ 4\ 3\ 2\ 1\ 0) \\ &PM2_{+ 1} :\ (0\ 2\ 4\ 6) (1\ 3\ 5\ 7) \\ &PM2_{- 1} :\ (6\ 4\ 2\ 0) (7\ 5\ 3\ 1) \\ &PM2_{± 2} :\ (0\ 4) (1\ 5) ( 2\ 6) (3\ 7) \\ \end{aligned}$$ ​PM2+0​: (0 1 2 3 4 5 6 7)PM2−0​: (7 6 5 4 3 2 1 0)PM2+1​: (0 2 4 6)(1 3 5 7)PM2−1​: (6 4 2 0)(7 5 3 1)PM2±2​: (0 4)(1 5)(2 6)(3 7)​ 其互连网络的连接如图6.25所示。

在图6.25(a)中，用 $3$ 个图分别表示 $PM{2}_{\pm 0},PM{2}_{\pm 1},PM{2}_{\pm 2}$ 的互连结构。在图6.25(b) 中，用一个图综合表示 $8$ 个节点的相互连接；各节点在圆周上的边，形成 $PM{2}_{\pm 0}$ 所表示的链路；由图中两个正方形构成的 $8$ 条边，形成 $PM{2}_{\pm 1}$ 所表示的链路；而两个正方形的 $4$ 条对角线，形成 $PM{2}_{\pm 2}$ 所表示的链路。

PM2I 网络也可以用非完全交叉开关矩阵，表示为图6.26的形式，其中交叉点上有标记的地方，是可以相互连接的开关点。从某一源点，例如 $0$ 节点开始，一步就可以直接到达的节点有 $1,2,4,6,7$ 。两步就可以实现任一输入节点到任一输出节点的连接。

在 ILLIAC-Ⅳ 阵列处理机中，各处理单元之间的连接，实际上就是采用了 PM2I 互连网络中 $PM{2}_{\pm 0}$ 和 $PM{2}_{\pm 3}$ 的 $4$ 个互连函数，它是 PM2I 网络的特例。

(2) 混洗（洗牌）交换网络

混洗交换网络是由均匀洗牌（全混洗） 和交换两种互连网组成，简称 SE 网络。由于均匀洗牌网络不能实现「二进制编号为全 $0$ 或全 $1$ 的节点」与其他节点之间的连接，因此必须增加交换连接，从而形成了混洗交换网络。

$N=8$ 时的混洗交换网络连接如图6.27所示，其中 $n={\log }_{2}N$ 。图6.27(a)中虚线表示均匀洗牌，实线表示交换。可以看出，在混洗交换网络中，最远的两个输入输出端是全 $0$ 和全 $1$ ，它们的连接需要 $n-1$ 次均匀洗牌和 $n$ 次交换才能实现，所以其最大距离为 $2n-1$ 。图6.27(b)是 SE 网络的非完全交叉开关表示。

同样， SE 网络的所有节点均需使用相同的连接，即要洗牌都洗牌，要交换都交换。SE 网络也是后面的多级互连网络 $\Omega$ 网的基础。

(3) 交叉开关网络

交叉开关网络的带宽和互连特性最好。一个 $N\times N$ 的交叉开关网络的连接方式有 $N!$ 种。$N=4$ 个节点的交叉开关网络如图6.28(a)所示。在这种互连网络中，任何一个节点都有与其他节点的直接通路，所以只需经一步，就可使源节点中的数据，传送到网络中任一目标节点。$N=8$ 个节点的全交叉开关网络连接如图6.28(b)（这图绘制错了吧？）所示，共有 $N^2$ 个交叉开关。

如果交叉开关网络输入和输出端都连接处理机，则 $N\times N$ 的交叉开关网络一次最多只能连接 $N$ 个输出对（即每一行和每一列只能接通一个交叉开关）。如果输入端连接处理机，输出端连接存储器模块，则为了支持并行（或交叉）存储器访问，可以在一行和一列之间接通几个交叉开关。

交叉开关网络的优点是连接能力强，但硬件复杂性以 $N^2$ 上升，造价很高，所以适合于规模小的系统。

3. 多级互连网络

前面介绍的单级互连网络（除交叉开关互连网络外），都只能实现有限几种基本连接，不能实现任意节点对之间的连接。多级互连网络是 在空间上重复设置多套单级网络，单级网络级间采用固定的模式串联，通过动态设置各级开关的状态，实现任意输入和输出节点对之间的所需连接。

下面介绍的几种典型的多级互连网络中，分别从结构特点、控制方式和典型应用等方面进行介绍。

(1) STARAN 网络

STARAN 网络的结构特点：

• 网络规模：$N$ 个节点的网络由 $n={\log }_{2}N$ 级构成，每级开关的编号从输入端到输出端依次为 $K_0,K_1,\dots ,K_{n-1}$ ；每级的交换开关数为 $N/2$ 个，每个交换开关都是二功能的（即直连和交换）。整个网络的开关数为 $(N/2)\times {\log }_{2}N$ 个。
• 拓扑结构：$N$ 个节点的网络共有 $n+1$ 级拓扑结构（连接模式），其编号从输入端到输出端依次为 $C_0,C_1,\dots ,C_n$ ；$C_0$ 为恒等置换，$C_1\sim C_n$ 为逆混洗置换。$N=8$ 个节点的 STARAN 网络结构如图6.29所示。其中，$N=8$ 时的逆混洗置换函数表达式为：
  $$S^{-1}(x_2{x}_1{x}_0)=x_0{x}_2{x}_1$$
  

STARAN 网络的控制方式：级控和部分级控。

STARAN 网络的典型应用：交换网络和移数网络。
① 交换网络：STARAN 网络用做交换网络时，采用级控方式工作，实现的是交换函数的功能——所谓交换函数是将一组元素首尾对称地进行交换（不是前面的交换置换函数！！！）。表6.1列出了三级交换网络，在级控信号采用各种不同组合情况下，所实现的输入与输出端之间的连接。

由表6.1可以看出：

• 当控制信号为 $001$ 时，完成对这 $8$ 个处理单元（元素）的 $4$ 组 $2$ 元交换，相当于 $N=8$ 时的方体 $C_0$ 置换。其输入/输出端的对应关系为：
  
• 当控制信号为 $010$ 时，完成的功能相当于先 $4$ 组 $2$ 元交换，后 $2$ 组 $4$ 元交换。其输入/输出端的对应关系为：
  
• 当控制信号为 $111$ 时，实现的是全交换，也称为镜像交换。
• 总之，不管控制信号是什么状态，实现的都是交换函数的功能。从表中水平方向不难看出，任何输入端只要通过不同的级控信号，总可以连接到任何所需要的输出端上。

② 移数网络：当 STARAN 网络采用部分级控时，实现的是移数函数的功能，故称为移数网络。这时的控制信号和输入/输出端的连接情况列于表 6.2 中。

当采用部分级控时，按照部分级控的定义，即第 $i$ 级应有 $i+1$ 个控制信号。在 $N=8$ 的 STARAN 网络中，第 $0$ 级有 $1$ 个控制信号，控制第 $0$ 级上的 $4$ 个交换开关 $A,B,C,D$ ；第 $1$ 级有 $2$ 个控制信号，分别控制 $F,H$ 和 $E,G$ 交换开关；第 $2$ 级有 $3$ 个控制信号，分别控制 $K,L$ 和 $I$ 及 $J$ 交换开关。

一个 $N\times N$ 规模的移数网络，能够实现 $(n^2+n+2)/2$ 种移数置换。$N=8$ 时的 STARAN 移数网络能实现 $7$ 种移数置换，这 $7$ 种移数置换在 $7$ 组不同的控制信号下，完成相对应的移数功能。

(2) 间接二进制 $n$ 方体网络

间接二进制 $n$ 方体网络的结构特点：

• 网络规模：$N$ 个节点的网络由 $n={\log }_{2}N$ 级构成，每级开关的编号从输入端到输出端依次为 $K_0,K_1,\dots ,K_{n-1}$ ；每级的交换开关数为 $N/2$ 个，每个交换开关都是二功能的（即直连和交换） 。整个网络的开关数为 $(N/2)\times {\log }_{2}N$ 个。
• 拓扑结构：$N$ 个节点的网络共有 $n+1$ 级拓扑结构，其编号从输入端到输出端依次为 $C_0,C_1,\dots ,C_n$ ；$C_0$ 为恒等置换，$C_1～C_{n-1}$ 为子蝶式置换，$C_n$ 为逆混洗置换。$N=8$ 个节点的间接二进制 $n$ 方体网络结构如图6.30所示。其中，$N=8$ 时的子蝶式置换函数有 $3$ 个，表达式分别为：
  $$\begin{array}{r}{B}_0(x_2{x}_1{x}_0)=x_2{x}_1{x}_0\\ B_1(x_2{x}_1{x}_0)=x_2{x}_0{x}_1\\ B_2(x_2{x}_1{x}_0)=x_0{x}_1{x}_2\end{array}$$
  

间接二进制 $n$ 方体网络的控制方式：单元控制，即每一个交换开关有一个控制信号。

间接二进制 $n$ 方体网络的典型应用：可实现交换置换、移数置换、子移数置换、$P$ 序置换、逆 $P$ 序置换、$P$ 序加移数置换等。

(3) $\Omega$ Omega 网络

$\Omega$ 网络的结构特点：

• 网络规模：$N$ 个节点的网络由 $n={\log }_{2}N$ 级构成，每级开关的编号从输入端到输出端依次为 $K_{n-1},K_{n-2},\dots ,K_0$ ；每级的交换开关数为 $N/2$ 个，每个交换开关都是 $4$ 功能的（即直连、交换、上播和下播） 。整个网络的开关数为 $(N/2)\times {\log }_{2}N$ 个。
• 拓扑结构：$N$ 个节点的网络共有 $n+1$ 级拓扑结构，其编号从输入端到输出端依次为 $C_n,C_{n-1},\dots ,C_0$ ；$C_0$ 为恒等置换，$C_1～C_n$ 为全混洗置换。
  $N=8$ 个节点的 $\Omega$ 网络结构如图6.31所示。
  

$\Omega$ 网络的控制方式：单元控制。

$\Omega$ 网络的典型应用：恒等置换、移数置换等各种函数的变形置换；可完成数组按行、列、对角线、子块等无冲突访问。

$\Omega$ 网络的寻径算法：设网络输入端地址编号为 $S=s_{n-1}{s}_{n-2}\dots s_1{s}_0$ ，输出端地址编号 $D=d_{n-1}{d}_{n-2}\dots d_1{d}_0$ 。从输入端开始，每一级开关状态由终端地址所对应位控制。若终端地址某位为 $0$ ，则对应级上开关的输入端与上输出端相连；若某位为 $1$ ，则对应级上开关的输入端与下输出端相连。这种算法称为“终端地址控制”的寻径算法。该算法也适合于单元控制方式的间接二进制 $n$ 方体网络中的地址寻径。

例如，在图6.32所示的 $\Omega$ 网络中，如果要实现输入节点 $2$ 到输出节点 $6$ 之间的连接，寻找路径的方法是：由于终端地址为 $D=6=d_2{d}_1{d}_0=110$ ，所以用 $d_2=1$ 去控制 $K_2$ 级上的交换开关，用 $d_1=1$ 去控制 $K_1$ 级上的交换开关，用 $d_0=0$ 去控制 $K_0$ 级上的交换开关。从源端 $2$ 开始，开关 $C$ 的输入端与下输出端相连（$d_2=1$）；经 $C_2$ 级网络拓扑连至开关 $F$ ，由于 $d_1=1$ ，$F$ 开关的输入端与下输出端相连；经 $C_1$ 级网络拓扑连至开关 $L$ ，由于 $d_0=0$ ，$L$ 开关的输入端与上输出端相连；经 $C_0$ 级网络拓扑连至 $6$ 号输出节点。这样就完成了节点对 $(2,6)$ 之间的连接寻径。

对网络的源端集合到终端集合的连接，同样也可以用上述终端标记法来控制开关的状态。但由于每一个源端和终端节点对之间的连接路径是惟一的，所以不能保证所有开关的状态不发生冲突。例如，要实现 $(000,000),(100,010)$ 两对同时连接，就会发生 $K_2$ 级开关 $A$ 的冲突，如图6.32所示。

同样，也不能用 $\Omega$ 网络来实现均匀洗牌、蝶式和位序颠倒等变换，所以说 $\Omega$ 网络是一种阻塞网络。

(4) 基准网络

基准网络的结构特点：

• 网络规模：$N$ 个节点的网络由 $n={\log }_{2}N$ 级构成，每级开关的编号从输入端到输出端依次为 $K_0,K_1,\dots ,K_{n-1}$ ；每级的交换开关数为 $N/2$ 个，整个网络的开关数为 $(N/2)\times {\log }_{2}N$ 个。
• 拓扑结构：$N$ 个节点的网络共有 $n+1$ 级拓扑结构，其编号从输入端到输出端依次为 $C_0,C_1,\dots ,C_n$ ；$C_0$ 和 $C_n$ 为恒等置换，$C_1$ 是逆混洗置换，$C_2～C_{n-1}$ 为子逆混置换。
  $N=8$ 个节点的基准网络结构如图6.33所示。其中，$N=8$ 个节点时只有 $C_2$ 级为子逆混洗置换。
  

基准网络的控制方式：单元控制，可以采用终端地址标记的寻径算法。

基准网络的典型应用：一次通过基准网络可以实现位序颠倒置换，对实现 $FFT$ 很有利；二次通过基准网络可以实现任意置换。

(5) 全排列网络

前面所介绍的各种基本多级网络都能实现任意一个输入端与任意一个输出端间的连接，但要同时实现两对或多对输入、输出端间的连接时，都有可能发生争用数据传送路径的冲突。我们称有这类性质的互连网络为阻塞式网络 Blocking Network ，称无这类性质的互连网络为非阻塞式网络或全排列网络。非阻塞式网络连接的灵活性好，但连线数多、控制复杂、成本高。

如果互连网络是从 $N$ 个输入端到 $N$ 个输出端的一到一的映射，就可以把它看成是对此 $N$ 个端的重新排列，因此互连网络的功能，实际上就是用新排列来置换 $N$ 个输入端原有的排列。

阻塞式网络在一次传送中不可能实现 $N$ 个端的任意排列。大家知道 $N$ 个端的全部排列有 $N!$ 种。可是，用单元控制的 $n={\log }_{2}N$ 级间接二进制 $n$ 方体网络，每级有 $N/2$ 个开关，$n$ 级互连网络共用交换开关总数为 $(N{\log }_{2}N)/2$ 。实现输入与输出端的一对一映射，每个开关只能用直连和交换二种功能，这样所有开关处于不同状态的总数最多只有 $2^{(N{\log }_{2}N)/2}$ ，即 $N^{N/2}$ 种。当 $N$ 为大于 $2$ 的整数时，总有 $N^{N/2}<N!$ ，就是说它无法实现所有 $N!$ 种排列。以 $N=8$ 个节点的 $3$ 级互连网络为例，共 $12$ 个二功能交换开关，只有 $2^{12}=4096$ 种不同状态，最多只能控制对端的 $4096$ 种排列，不可能实现全部 $8!=40320$ 种排列，所以多对输入输出端要求同时连接时就可能发生冲突。

用两种方法可构成全排列网络：

• 一种方法是 对某个多级互连网络通行二次，每次通行时让各开关处于不同状态，就可满足对 $N$ 个端子的全部 $N!$ 种排列。因为此时全部开关的总状态数有 $N^{N/2}\times N^{N/2}=N^N$ 种，因为 $N^N>N!$ ，足以满足 $N!$ 种不同排列的开关状态要求。这种只要经过重新排列已有输入输出端对的连接，就可完成所有可能的输入与输出端对的连接、而不发生冲突的互连网络称为可重排列网络 Rearrangeable Network 。实现时，可以在上述任何一种基本多级互连网络的输出端设置锁存器，使数据在时间上顺序通行二次，这实际上就是循环互连网络的实现思路。
• 另一种方法是用 ${\log }_{2}N$ 级的 $N$ 个输入端和 $N$ 个输出端的互连网络，和它的逆网络连在一起，省去中间完全重复的一级，就可以得到总级数为 $2{\log }_{2}N-1$ 级的全排列网络。图6.34就是以三维立方体多级网络和它的逆网络连在一起，省出中间重复的一级后构成的全排列网络，称此网络为 Benes 网络。

全排列网络的开关控制算法是改进的终端标记算法。在多级混洗交换（$\Omega$）网络的终端标记寻径控制算法中规定，第 $i$ 级的开关状态用终端地址的第 $i$ 位 $d_i$ 来控制。若 $d_i=0$ ，则相应开关的输入端连接上输出端；若 $d_i=1$ ，则相应开关的输入端连接下输出端。这样，如果同一个开关的两个输入端的终端地址 $d_i$ 都等于 $0$ ，那么这个开关就会发生「两个输入端要求同时连接一个上输出端」，而发生连接冲突。同样，如果同一个开关的两个输入端的终端地址 $d_i$ 都是 $1$ ，那么这个开关就会发生「两个输入端要求同时连接一个下输出端」，而发生连接冲突。

改进的终端地址标记控制的寻径算法只用一个输入端的控制信号 $d_i$ 来控制开关的工作状态。如果用上输入端的 $d_i$ 来控制，则当 $d_i=0$ 时，开关处于直连状态；当 $d_i=1$ 时，开关处于交换状态；如果用开关的下输入端的 $d_i$ 来控制，则当 $d_i=0$ 时，开关处于交换状态，当 $d_i=1$ 时，开关处于直连状态。值得注意的是，虽然可用开关的上、下输入端控制开关的工作状态，但在一次置换中，只能采用一种控制方案。

例如，用改进终端地址标记控制的寻径算法实现在 Benes 网络上的位序颠倒置换。现采用上输入端的控制方法，分析各开关工作状态如下：

• $K_0$ 级共有 $4$ 个交换开关：开关 $1$ 的上输入端所要连接的终端地址 $d_0=0$ ，开关 $1$ 为直连工作状态；开关 $2$ 的上输入端所要连接的终端地址 $d_0=0$ ，开关 $2$ 也为直连工作状态；开关 $3$ 的上输入端所要连接的终端地址 $d_0=1$ ，开关 $3$ 为交换工作状态；开关 $4$ 的上输入端所要连接的终端地址 $d_0=1$ ，开关 $4$ 也为交换工作状态。
• $K_1$ 级上也有 $4$ 个交换开关：开关 $5$ 的上输入端通过开关 $1$ 与 $0$ 号输入端相连，它所要连接的终端地址 $d_1=0$ ，故开关 $5$ 为直连工作状态；开关 $6$ 的上输入端通过开关 $3$ 与 $5$ 号输入端相连，它所要连接的终端地址 $d_1=0$ ，故开关 $6$ 也为直连工作状态；开关 $7$ 的上输入端通过开关 $1$ 与 $1$ 号输入端相连，它所要连接的终端地址 $d_0=0$ ，故开关 $7$ 为直连工作状态；开关 $8$ 的上输入端通过开关 $3$ 与 $4$ 号输入端相连，它所要连接的终端地址 $d_1=0$ ，故开关 $8$ 也为直连工作状态。
• 同理可知，在 $K_2$ 级上，由于开关 $9$ 的上输入端通过开关 $5$ 和开关 $1$ 与 $0$ 号输入端相连，而 $0$ 号输入端所要连接的终端地址 $d_2=0$ ，开关 $9$ 为直连工作状态……依此类推，开关 $10$ 为直连工作状态；开关 $11$ 和开关 $12$ 为交换工作状态。
• $K_3$ 级上的 $4$ 个交换开关均为直连状态。
• $K_4$ 级上的 $4$ 个开关的工作状态分别为：$17,18$ 为直连工作状态，$19,20$ 为交换状态，如图6.35所示。
  

由图可知，它可以实现「输入与输出之间的位序颠倒置换」。如在该网络上要实现输入端 $3$ 与输出端 $6$ 之间的连接，源地址的二进制为 $011$ ，而终端地址为 $d_2{d}_1{d}_0=110$ ，它们之间的连接路径上所通过的开关为 $2,7,12,16,20$ 。

---

6.5 多处理机

见【计算机体系结构】计算机体系结构(6) 并行处理技术(2) 多处理机。