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

并行性的双重含义是指同时性(或并行)和并发性。所谓同时性是指两个或两个以上的事件同时发生，并发性是指两个或两个以上的事件发生在同一时间间隔内。

并行处理它指的是相对的串行处理信息处理方法，重点开发计算过程中的并发事件。并行处理时，每次处理的规模可能不同，可用并行性粒度表示。关于并行粒度的大小。 $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$ 级为细粒度，主要是在单处理机中实现，开发手段以硬件为主，其中包括标量流水、超标量流水、超流水和超长指令字等。

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

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

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

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

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

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

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

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

阵列机通常由一个控制器 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 的子集。这种描述模型，为评价不同的阵列机结构提供了比较基础。

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

分布式阵列机的基本结构如图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来完成连接。
  

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

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

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

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

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

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 还可以单独变址。双重变址机构增加了各处理单元存储器之间数据分配的灵活性。

阵列控制器 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 所产生的陷阱中断信号。

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$ 位。