【计算机系统结构】第六章：向量处理机

①向量处理机是有向量数据表示的处理机，分向量流水处理机和阵列处理机两类。向量流水处理机是以时间重叠途径开发的，而阵列处理机是以资源重复途径开发的。

②所谓V,冲突，指的是并行工作的各向量指令的源向量或结果向量使用了相同的V{。

③CRAY-1向量处理的一个显著特点是只要不出现功能部件使用冲突和源向量寄存器使用冲突，通过链接机构可使有数据相关的向量指令仍能大部分时间并行执行。

④链接技术是提高计算机整体运算速度的一个非常重要的措施。

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

是采用分布式存储器阵列处理机的构形。各处理单元有局部存储器（PEM）存放被分布的数据，只能被本处理单元直接访问。

在控制部件内还有一个存放程序和数据的主存储器，整个系统是在控制部件的控制下运行用户程序和部分系统程序的。在执行主存储器中的用户程序时，所有指令都在控制部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件自己执行，而把适合于并行处理的向量类指令“播送”给各个PE，控制处于“活跃”的那些PE并行执行。

是采用集中式共享存储器的阵列处理机构形。系统存储器是由K个存储分体（MM。～一MMA-）集中组成，经ICN为全部N个处理单元(PE一～PEy,）所共享。为使各处理单元对长度为N的向量中各个元素都能同时并行处理，存储分体个数K应等于或多于处理单元数N。各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到各个存储分体中。

1、阵列处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。这些计算问题利用多个处理单元对向量或数组所包含的各个分量同时计算，从而易于获得很高的处理速度。

①与同样擅长于向量处理的流水线处理机相比，阵列处理机利用的是资源重复，而不是时间重叠;利用的是并行性中的同时性，而不是并发性。它的每个处理单元要同等地担负起各种运算功能，但其设备利用率却可能没有多个单功能流水线部件的那样高。阵列处理机提高速度主要是靠增大处理单元数，比起向量流水处理机主要靠缩短时钟周期来说，速度提高的潜力要大得多。

②与流水线处理机不同的另一方面是阵列处理机使用简单、规整的互连网络来确定处理单元间的连接。

阵列处理机在机间互连上比固定结构的单功能流水线灵活，使相当一部分专门问题上的工作性能比流水线处理机高得多，专用性强得多。

阵列处理机实质上是由专门应对数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列的控制及标量处理的处理机和专门从事系统输入/输出及操作系统管理的处理机组成的一个异构型多处理机系统。

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

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

为反映互连特性，每种互连网络可用一组互连函数定义。如果把互连网络的N个入端和N个出端(N=2")各自用0，1，…，N-1的整数编号代表，则互连函数就是表示互连网络的出端号和入端号的一一对应关系。

互连函数可以直接用结点间的连线图表示，但有时显得烦琐，也难以体现出连接上的内在规律。因此，常用另一种简单的函数式表示，即把所有入端x和出端f(x）都用二进制编码，从两者的二进制编码上找出其函数规律。

在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结构做出抉择。

操作方式有同步、异步及同步与异步组合3种。现有的阵列处理机根据其SIMD性质，均采用同步操作方式，让所有PE按时钟同步操作。异步或组合操作方式一般多用于多处理机。

交换方法主要有线路交换、包交换及线路与包交换组合3种。网络的拓扑结构指的是互连网络入、出端可以连接的模式，有静态和动态两种。

基本的单级互连网络有:立方体单级网络、PM2I单级网络、混洗交换单级网络、蝶形单级网络。

立方体(Cube）单级网络的每个顶点（网络的结点）代表一个处理单元，共有8个处理单元，用zyx三位二进制码编号。它所能实现的入、出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编码的某一位取反的其他3个处理单元上。

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

PM2.;（j)=j+2i mod N

PM2_;(j)=j-2i mod N

式中，0≤j≤N-1，0≤i≤n-1，n=log,N。它共有2n个互连函数。对于N=8的三维PM2I互连网络的互连函数，有PM2+o、PM2-o、PM2,1、PM2-1、PM2+2等五个不同的的互连函数。

混洗交换单级网络包含两个互连函数，一个是全混，另一个是交换。图6-16表示8个处理单元间的全混连接。可以看出，其连接规律是把全部按编码顺序排列的处理单元从当中分为数目相等的两半，前一半和后一半在连接至出端时正好一一隔开。

蝶形单级网络（Butterfly）的互连函数为Butterfly (P.1Pm-2…P,P。)=PoPn-2…P1Pn-1

即将二进制地址的最高位和最低位相互交换位置。图6-18为N=8个处理单元之间用蝶形单级互连网络互连的情况。它实现的是0→0，1→4，22,3→6，4→1，5→5，6-→3，7→7的同时连接。

N=8的多级PM2I网络的结构包含n级单元间连接，每一级都是把前后两列各N=2n个单元按PM2I拓扑相互连接起来。从第1级（O≤in-1)来说，每一个入单元j (0≤j≤N-1）都有3根连接线分别通往单元j，j+2imodN和j-2imodN。

基准网络与二进制立方体网络的逆网络相似，只是在第1级的级间连接不同。它采取从输入到输出的级间互连为恒等、逆全混、子逆全混和恒等置换，所用交换单元均为二功能的，采取单元控制。

对于二维数组（结论也适用于多维数组）而言，假设主存有m个分体并行，从中访问有n个元素的数组子集。这n个元素的变址跳距对于二维数组的行、列、主对角线、次对角线都是不一样的，但要求都能实现无冲突访问。如果设m=n=4，一个4×4的二维数组直接按行存储的方案则如图6所示。

虽然同时访问某一行、主对角线或次对角线上的所有元素时，都可以无冲突地访问，但要同时访问某一列的元素时，由于它们集中存放在同一存储分体内，会产生访存冲突，因此，每次只能访问其中的一个元素，使实际频宽降低到1/4。

脉动阵列结构是由一组处理单元（PE）构成的阵列。每个PE的内部结构相同，一般由一个加法/逻辑运算部件或加法/乘法运算部件再加上若干锁存器构成，可完成少数基本的算术逻辑运算操作。阵列内所有处理单元的数据锁存器都受同一个时钟控制。运算时数据在阵列结构的各个处理单元间沿各自的方向同步向前推进，形象的称其为脉动阵列结构。

脉动阵列结构具有如下特点:

(1）结构简单、规整，模块化强，可扩充性好，非常适合用超大规模集成电路实现。

(2）PE间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均简单规整。

(3）脉动阵列中所有PE能同时运算，具有极高的计算并行性，可通过流水获得很高的运算效率和吞吐率。输入数据能被多个处理单元重复使用，大大减轻了阵列与外界的I/O通信量，降低了对系统主存和I/0系统频宽的要求。

(4）脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI是不利的。

造成脉动阵列处理机应用范围有限的关键因素是，受阵列结构的通用性及I/0带宽约束所限制的阵列结构的规模大小。发展通用脉动阵列构的途径主要有3种:

(1）通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序重新配置阵列的结构。

(2）用软件把不同的算法映像到固定的阵列结构上，该方法依赖于面向并行运算所采用的程序语言，操作系统，编详程序和软件开发工具的设计。

(3）探寻与问题大小无关的脉动处理方法，以及VLSI运算系统的分割矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相应的设置方案。