本章重点：向量流水处理机中向量指令间的并行、链接，阵列处理机互连网络、互连函数、多级互连网络。

本章难点：向量流水处理机中向量指令间的并行，阵列处理机的并行算法和多级互连网络。

目录

第一节向量的流水处理与向量流水处理机

一、向量的流水处理与向量流水处理机

流水处理

第二节阵列处理机的原理

一、阵列处理机的构形和特点

构形1：采用分布式存储器阵列处理机的构形。

构形2：采用集中式共享存储器的阵列处理机构形。

二、阵列处理机的特点

第三节SIMD计算机的互连网络

一、互连网络的设计目标及互连函数

第四节共享主存构形的阵列处理机中并行存储器的无冲突访问

第五节脉动阵列流水处理机

一、脉动阵列结构的原理

---

第一节向量的流水处理与向量流水处理机

向量处理机是由向量数据表示的处理机，分向量流水线处理机和阵列处理机两类。

向量流水处理机是以时间重叠途径开发的，而阵列处理机是以资源重复途径开发。

时间重叠：向量流水处理机；

资源重复：阵列处理机；

一、向量的流水处理与向量流水处理机

（1）虽然向量运算比标量运算更容易发挥流水线的效能，但如果处理方式选择不当也不行。选择使向量运算最能充分发挥出流水效能的处理方式，就是向量的流水处理要研究的问题。

（2）若向量的长度N太长，超出了向量寄存器组中寄存器的个数，可将向量分割成若干个组，使每组都能装得进向量寄存器组中。组内采用纵向方式处理，组间采用依次横向处理。

（3）一般可采取让多个流水线功能部件并行，流水线链接，加快条件语句和稀疏矩阵处理，加快向量的归约操作等方法来提高向量流水线处理的性能。

【例题】向量处理机是由向量数据表示的处理机，分___________和___________两类。

【答案】向量流水线处理机、阵列处理机

流水处理

下面以计算表达式 D = A * （ B + C ）

（1）横向处理方式

逐个求出结果向量的各个元素

先算：

d1＝a1×(b1＋c1)
d2＝a2×(b2＋c2)
…
dN＝aN×(bN＋cN)

逐个求D中的N个分量，先进行相加k←b1＋c1，其中k为暂存单元，然后相乘d1←k×a1 。
在每个向量元素的加乘运算中，都会发生数据相关的情况，而且当采用静态流水线时，还要进行2次
乘和加功能的转换。这样共会出现N次相关和2N次功能转换。因此，这种横向加工方式只适合于标量。
循环算法，不适合于向量流水处理。

（2）纵向处理方式

纵向（垂直）加工方式：先对所有元素执行一种相同的运算，再对所有元素执行另一种相同的运算。

先算：
k1＝b1＋c1
k2＝b2＋c2
…
kN＝bN＋cN
再算：
d1＝a1×k1
d2＝a2×k2
…
dN＝aN×kN

在两条向量指令间仅有一次数据相关，流水线功能的切换只需一次。

第二节阵列处理机的原理

一、阵列处理机的构形和特点

（1）阵列处理机的构形

阵列处理机有两种构形，差别主要在于存储器的组成方式和互连网络的作用不同。

构形1：采用分布式存储器阵列处理机的构形。

图6-1具有分布式存储器的并行处理机构形

构形2：采用集中式共享存储器的阵列处理机构形。

图6-2具有集中式共享存储器的并行处理机构形

二、阵列处理机的特点

• 基于有限差分、矩阵、信号处理、线性规划、等问题背景，共同特点是可以通过各种途径转化成对数组和向量的处理。
• 单指令数据多数据流处理
• 资源重复，不是时间重叠
• 利用并行性的同时性，而不是并发性；
• 并行处理机主要是靠增大处理单元个数，比向量流水线处理机效果好。

1）阵列处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。

2）阵列处理机利用的是资源重复，而不是时间重叠；利用并行性中的同时性，而不是并发性。它的每个处理单元要同等地担负起各种运算功能，但其设备利用率却可能没有多个单功能流水线部件那样高。

3）阵列处理机主要是靠增大处理单元个数来提高运算速度，比起向量流水线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多。

第三节SIMD计算机的互连网络

一、互连网络的设计目标及互连函数

SIMD的互连网络的设计目标是：

（1）结构不要过分复杂，以降低成本；

（2）互连要灵活，以满足算法和应用的需要；

（3）处理单元间信息交换所需的传送步数要尽可能少，以提高速度性能；

（4）能用规整单一的基本构建组合而成，或经多次通过或者经多级连接来实现复杂的互连，使模块性好，以便用VLSI实现，并满足可扩充性。

二、互连网络应抉择的几个问题

（1）操作方式

（2）控制策略

（3）交换方法

（4）网络的拓扑结构

三、基本的单级互连网络

（1）立方体单级网络

图6-3三维立方体结构

图6-4立方体单级网络连接图

推广到n维的情形，N个节点的立方体单级网络共有n=log2N种互连函数，即

式中，0≤i≤n-1，Pi为入端号二进制码的第i位。当维数n＞3时，称为超立方体(HyperCube)网络。

【例题】编号为0、1、2、…、15的16个处理器，用单级互连网络互连，用Cube0互连函数时，与第10号处理器相连的处理器的编号是()

A．9   B．10

C．11 D．12

【答案】C

【解析】该题考查考生对于立方体单级网络互连函数的掌握，用Cube0互连函数时，Cube0（1010）=1011，所以与第10号处理器相连的处理器编号是11，故正确选项为C。

（2）PM2I单级网络

PM2I单级网络是“加减2i”(Plus-Minus2i)单级网络的简称。能实现与j号处理单元直接相连的是号为j±2i的处理单元，即

式中，0≤j≤N-1,0≤i≤n-1,n=log2N。因此，它共有2n个互连函数。由于总存在PM2+(n-1)=PM2-(n-1)，所以实际上，PM2I互连网络只有2n-1种不同的互连函数。

对于N=8的三维PM2I互连网络的互连函数有PM2+0、PM2-0、PM2+1、PM2-1、PM2±2等5个不同的互连函数，它们分别为：

PM2+0:(01234567)

PM2-0:(76543210)

PM2+1:(0246)(1357)

PM2-1:(6420)(7531)

PM2±2:(04)(15)(26)(37)

图6-5PM2I互连网络的部分连接图

【例题】编号为0、1、2、…、15的16个处理器，用单级互连网络互连，用PM2+1互连函数时，与第7号处理器相连的处理器的编号是()

A．8   B．9

C．10 D．11

【答案】B

【解析】该题考查考生对于PM2I单级网络互连函数的掌握，用PM2+1互连函数时，PM2+1（7）=（7+21）mod16，所以与第7号处理器相连的处理器编号是9，故正确选项为B。

（3）混洗交换单级网络

用互连函数表示为：

式中，n=log2N，Pn-1Pn-2…P1P0为入端编号的二进制码。

图6-68个处理单元的全混连接

（4）蝶形单级网络

其互连函数为： 

即将二进制地址的最高位和最低位相互交换位置。

四、基本的多级互连网络

多级互连网络就是由上述3种单级互连网络相对应组成的多级立方体互连网络、多级混洗交换网络和多级PM2I网络。

1. 交换开关是具有两个入端和两个出端的交换单元，用作各种多级互连网络的基本构件。

1）直连——i入连i出，j入连j出；

2）交换——i入连j出，j入连i出；

3）上播——i入连i出和j出，j入悬空；

4）下播——j入连i出和j出，i入悬空。

1. 控制方式是对各个交换开关进行控制的方式，以多级立方体网络为例，它可以有3种：

1）级控制——同一级的所有开关只用一个控制信号控制，同时只能处于同一种状态；

2）单元控制——每一个开关都有自己独立的控制信号控制，可各自处于不同的状态；

3）部分级控制——第i级的所有开关分别用i+1个信号控制，0≤i≤n-1,n为级数。

（1）多级立方体网络

图6-7N=8多级立方体互连网络

（2）多级混洗交换网络

多级混洗交换网络又称omega网络，如图6-8所示。

图6-8N=8多级混洗交换网络

（3）多级PM2I网络

图6-9N=8多级PM2I网络

五、全排列网络

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

当实现两对或多对入端与出端之间的连接时，都有可能因争用数据传送路径而发生冲突。我们称具有这类性质的互连网络为阻塞式网络(BlockingNetwork)。反之，不具有这类性质的互连网络为非阻塞式网络，或称为全排列网络。

图6-10多级全排列网络

第四节共享主存构形的阵列处理机中并行存储器的无冲突访问

第五节脉动阵列流水处理机

一、脉动阵列结构的原理

脉动阵列结构是由一组处理单元（PE）构成的阵列。每个PE的内部结构相同，一般由一个加法/逻辑运算部件或加法/乘法运算部件再加上若干个锁存器构成，可完成少数基本的算术逻辑运算操作。

脉动阵列结构有如下一些特点：

1)结构简单、规整，模块化强；

2)数据流和控制流的设计简单规整；

3)具有极高的计算并行性；

4)脉动阵列结构的构形与特定计算任务和算法密切相关；

二、通用脉动阵列结构