计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机

第八章 SIMD计算机(并行处理机) 8.1 SIMD计算机模型 8.2 SIMD计算机基本结构 8.3 SIMD计算机实例 8.4 SIMD计算机的应用** 8.5 连续模型的结构向何处发展**

第八章 SIMD计算机(并行处理机) 两种并行性概念 同时性并行Simultaneity: 两个或两个以上事件在同一时刻发生 并发性并行Concurrency: 两个或两个以上事件在同一时间间隔内发生 三条技术途径 资源重复：通过重复设置多个处理部件来提高速度 时间重叠：流水线 资源共享：分时系统，分布式系统

8.1 并行处理机模型 并行处理机定义 多个PE按照一定方式互连，在同一个CU控制下，对各自的数据完成同一条指令规定的操作 从CU看，指令串行执行，从PE看，数据并行处理 并行处理机也称为阵列处理机 以单一控制部件控制下的多个处理单元构成的阵列 按照Flynn分类法，属于SIMD计算机 主要应用领域----高速向量或矩阵运算

H·J·Siegel提出的并行处理机模型 并行处理机的操作模型 P0 M0 PE0 P1 M1 PE1 P2 M2 PE2 Pn-1 Mn-1 PEn-1 互连网络 CU …… H·J·Siegel提出的并行处理机模型

并行处理机的操作模型 并行处理机的操作模型可用五元组来表示 M=(N，C，I，M，R) N为PE个数 如Illiac IV有64个PE C为由控制部件CU直接执行的指令集 包括标量指令和程序控制指令 I为所有PE并行执行的指令集 包括算术运算、逻辑运算、数据寻径、屏蔽及其它每个活动的PE对它的数据所执行的局部操作 M为屏蔽操作集 每种屏蔽将PE划分为允许操作和禁止操作两个子集 R是数据寻径集 互连网络中PE间通信所需要的各种设置模式

MasPar MP-1的操作特性 (1)是一台具体的SIMD机器, N=1024至16384。实际PE数目与机器配置有关 (2)CU执行标量指令，译码后的向量指令广播到PE阵列，并控制PE间的通信 (3)每个PE都是基于Load/Store结构的RISC处理机，PE从CU接受指令，能执行整数运算和标准浮点运算 (4)屏蔽指令设在每个PE中，并由CU连续监控。它能在运行时动态地使每个PE处于置位或复位状态 (5)有一个X-Net网格网络和一个全局多级交叉开关寻径器，实现CU和PE之间、X-Net的8个近邻之间和全局寻经器的通信

3种SIMD计算机 MP-1 每个PE装有1位逻辑单元、4位整数ALU、64位尾数部件和16位指数部件 MP-1是中粒度并行处理机 每个PE比较简单，可将几个PE 做在一个芯片 MP-1的每个芯片有32个PE，每个PE有40个32位寄存器 32个PE用X-Net网络互相连接，是一种对角线双级链路扩展的4-邻网 CM-2 在一个芯片上将16个PE连成网格网络 每个16-PE网的芯片安置在12维超立方体的顶角 16×2^12=2^16=65536个PE组成了整个SIMD阵列 DAP 610 在一个芯片上实现一个64-PE的网格网络 再由这些芯片上小网格互相连接组成一个大网格(64×64)

3种SIMD计算机 PE数从DAP 610的4096到MasPar MP-1的16384和CM-2的65536 PE都带有浮点加速器 PE有细粒度和中粒度之分 CM-2与DAP610都是细粒度、位片式SIMD计算机 MP-1是中粒度SIMD机

表8.1 3种SIMD计算机 Active Memory Technology DAP600 系列 1K位/PE方形网格互连成4096PE的细粒度、位片SIMD阵列，正交4-邻位链接，20GIPS和560Mflops峰值性能 由主机VAX/VMS或UNIX Fortran-plus 或DAP上APAL提供，主机的Fortran77或C; 与Fortran90标准有关的Fortran-plus Thinking Machines公司CM-2 65536个PE排成10维超立方体, 每个PE可有1M位存储器, 32个PE共享FPU选件, 峰值速度28Gflops和持续速度5.6Gflops 由VAX, Sun或Symbolics 360主机驱动, PARIS支持的Lisp编译器、Fortran90、C*和*Lisp 系统型号 SIMD计算系统 结构和性能 语言、编译器 和软件支持 MasPar MP-1系列 1024~16384个PE, 26GIPS或1.3Gflops; 每个PE带16KB本地存储器, X-Net网格加一个多级交叉开关互连网 Fortran77, MasPar Fortran (MPF)和MasPar并行应用语言; X窗口UNIX/OS, 符号调试程序, 可视化和动画制作程序

8.2 并行处理机的基本结构 并行处理机有两种典型结构 分布式存储器结构 共享存储器结构 一台并行处理机由五个部分组成 多个处理单元PE 多个存储器模块M 一个控制器CU 一个互连网络ICN 一台输入输出处理机IOP

8.2.1分布式存储器结构 目前的大部分并行处理机基于分布式存储器模型 比较容易构成MPP(Massively Parallel Processor，大规模并行处理机),几十万个PE 必须依靠并行算法来提高PE的利用率, 应用领域很有限 CU是控制部件，执行标量指令，并把向量指令广播到各个PE CU中通常有一个较大容量的存储器 IOP是输入输出处理机，或称为主机 在IOP上安装操作系统，负担输入输出工作，还负责程序的编辑、编译和调试等工作 数据在局部存储器LM中的分布是一个很关键的问题 标量指令与向量指令可并发执行

图8.2 分布式存储器的SIMD计算机 LM0 互连网络 …… PE0 CU LM1 PE1 LMn-1 PEn-1 IOP

分布式存储器的SIMD计算机 包含重复设置的多个同样的处理单元PE 通过数据寻径网络以一定方式互相连接 每个PE有各自的本地存储器LM 在统一的阵列控制部件CU作用下，实现并行操作 程序和数据通过主机装入控制存储器 通过控制部件的是单指令流，指令的执行顺序与单处理机一样，基本上是串行执行 指令送到控制部件进行译码 标量操作或控制操作，直接由与控制部件相连的标量处理机执行 向量操作，广播到所有PE并行执行

分布式存储器的SIMD计算机 数据分布存放在所有PE的本地存储器 PE通过数据寻径网络互连 数据寻径网络执行PE间的通信 如移数、置换和其它寻径操作 控制部件通过执行程序来控制数据寻径网络 PE的同步由控制部件的硬件实现 所有PE在同一个周期执行同一条指令 用屏蔽逻辑来决定任何一个PE在给定的指令周期执行或不执行指令 SIMD机器的主要差别在于PE间互相通信的数据寻径网络不同 4-邻连接网格结构在过去最受欢迎 Illiac IV由64个有本地存储器的PE组成、PE间通过8×8环绕连接网格实现互连 Goodyear MPP和AMT DAP610用两维网格实现 CM-2实现的嵌在网格中的超立方体和MasPar MP-1实现的X-Net加多级交叉开关的寻径器都由网格演变而来

8.2.2 共享存储器结构 共享的多体并行存储器SM通过互连网络与各处理单元PE相连 存储模块的数目等于或略大于处理单元的数目 灵活、高速的互连网络在存储器与处理单元间传送数据 存储模块之间合理分配数据 大多数向量运算中都能以存储器的最高频率进行，而最少受存储冲突的影响 共享存储器并行处理机模型在处理单元数目不太大的情况下很理想 Burroughs Scientific Processor (BSP)采用了这种结构 16个PE通过一个16×17的对准互连网络(ch03p146)访问17个共享存储器模块 存储器模块数与PE数互质可实现无冲突并行访问存储器

图8.3 共享存储器的SIMD计算机 PE0 互连网络 …… CU PE1 PEn-1 IOP SM0 SM1 SMk-1

不同存储方案的比较 互连网络的存在是必要的 共享存储器方案中，是存储器与处理单元之间的必由之路 分布存储器方案中，处理单元所需数据在大多数情况下都由本地存储器提供，处理单元间的数据传送必不可少 图8.2中，各处理单元PE之间可经两条途径相互联系 一条直接通过数据寻径网络 另一条是数据从LM读至阵列控制部件，然后通过公共数据总线"广播"到全部PE 处理单元数目很多的并行处理机中，PE之间的直接数据通路很有限，这决定了系统的固定结构和专用处理机的性质。这种局限性需要从互连网络的研究中得到解决

与向量处理机的比较 与第六章的向量处理机相比，共同之处是都执行向量指令 SIMD计算机对向量的分量进行算术、逻辑、数据寻径和屏蔽操作 位片SIMD计算机中的向量是二进制向量。在字并行SIMD计算机中向量的分量是4字节或8字节的数 SIMD处理机的指令须使用长度为n的向量操作数，其中n是PE的个数 SIMD指令与流水线向量处理机的指令类似，不同之处是多PE的空间并行性代替了流水线的时间并行性 数据寻径指令包括置换、广播、选播以及循环和移数操作 在任何指令周期，屏蔽操作可允许或禁止某些PE参加运算 SIMD结构的所有I/O动作都由主机承担 主机和阵列控制部件间有一个专用的控制存储器，是一个存放程序和数据的中间存储器 启动程序之前，把划分好的数据集合分布到本地存储器或共享存储器模块 主机管理大容量存储器或计算结果的图形显示 在控制部件的协调下，标量处理机与PE阵列并发地运算

8.2.3 并行处理机的特点 并行处理机的主要特点 速度快，而且潜力大 模块性好，生产和维护方便 可靠性高，容易实现容错和重构 效率低(与流水线处理机、向量处理机等比较) 通常作为专用计算机，很大程度上依赖于并行算法 依靠的是资源重复，而不是时间重叠，每个处理单元要担负多种处理功能，效率要低一些 依靠增加PE个数，与流水线处理机主要依靠缩短时钟周期相比，提高速度的潜力要大得多 依赖于互连网络和并行算法 互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法 需要有一台高性能的标量处理机 如果一台机器的向量处理速度极高，但标量处理速度只是每秒一百万次，那么对于标量运算占10%的题目来说，总的有效速度就不过是每秒一千万次

1 高速数值计算 SIMD计算机与流水线向量处理机一样，特别适于高速数值计算 以有限差分、矩阵、信号处理、线性规划等计算问题为背景而发展起来 这些问题的共同特点是能够通过各种途径归结为数组和向量处理 SIMD计算机效率取决于计算程序向量化的程度 与按多指令流多数据流方式工作的多处理机相比，具有较固定的结构，直接与一定的算法相联系 通过改进系统结构和制定并行算法，使可能适应的计算问题类型尽量广一些、多一些 应该把系统结构的研究和算法的研究结合起来

2 利用大量处理单元对向量各个分量同时进行运算 SIMD计算机利用大量处理单元对向量所包含的各个分量同时进行运算，是它获得很高处理速度的主要原因 与同样擅长于向量处理的流水线向量处理机相比，SIMD计算机依靠的并行措施是资源重复，而不是时间重叠 每个处理单元要担负多种处理功能，相当于流水线向量处理机的多功能流水线部件(如在TI ASC机中)，效率比多个单功能流水线部件(如在Cray-1机中)要低一些 在硬件价格大幅度下降，系统结构的不断改进，SIMD计算机才具有较好的性能价格比 SIMD计算机主要依靠增多处理单元的个数提高运算速度，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多 如果有很好的互连网络相配合，则多处理单元的功能和灵活性将会更强一些 如时钟周期为160ns、包含16个处理单元的BSP SIMD计算机取得的运算速度，能与时钟周期为12.5ns、包含12条单功能流水线的Cray-1流水线向量处理机相当

3 SIMD计算机的互连网络 SIMD计算机机与流水线向量处理机的另一区别是互连网络 是由多处理单元这一特点所决定 目前的SIMD计算机采用的互连网络还比较简单，但它是SIMD计算机最有特色的一个组成部分 互连网络规定处理单元的连接模式, 决定SIMD计算机能适应的算法类别，对整个系统的各项性能指标产生重要的影响 是SIMD计算机结构的研究重点，是多处理机的重要组成部分

4 实际有效速度的其他决定因素 以向量处理为主的SIMD计算机除向量运算速度以外，整个系统的实际有效速度的另外两个决定因素 一是标量运算速度 二是编译过程的开销 提高SIMD计算机处理标量和短向量的能力很重要 流水线的向量处理机处理短向量时，流水线建立和排空时间的比例加大 SIMD计算机中短向量对速度影响较小，但降低了处理效率 如果某一台机器的向量处理速度极高，甚至是不受限制的，但标量处理速度只是每秒一百万次浮点运算，那么对于标量运算占10%的题目来说，总的有效速度就不过是每秒一千万次浮点运算 编译时间，与系统结构，与机器语言有密切的关系 要提高SIMD计算机的通用性，建立一个具有向量化功能的高级语言编译程序十分必要

5 SIMD计算机基本上是一台向量处理专用计算机 有一个功能很强的控制部件起着标量处理机的作用 仍须有一台高性能单处理机担负系统的全部管理功能 根据功能专用化的原则组成一个异构型多计算机系统 向量处理部件是系统的主体 高性能单处理机可视为它的前端机，用来分担部分功能，以便充分发挥主体的向量处理效率 流水线向量处理机则有一些不同 有些向量处理机接到主机上执行主机的一些有关操作或子程序，分担主机的部分功能，提高主机的有效运算速度, 起着后端处理机的作用，不能被认为是系统的主体 在流水线向量处理机中，CDC STAR100、和Cray-1等巨型计算机本身被认为是完整的通用计算机系统 AP120B、IBM3838等专用浮点数组处理机是后端处理机

8.3 并行处理机实例 Illiac IV 是最先采用SIMD结构的并行处理机 采用阵列结构分布存储器 一个方向是用位片PE制造的SIMD计算机 Goodyear MPP、AMT/DAP 610和TMC/CM-2 CM-5是以SIMD模式运行的同步MIMD计算机 另一方向是用字宽运算PE的中粒度SIMD计算机 BSP 是16台处理机和17个存储模块同步工作的共享存储器SIMD计算机 GF-11是IBM Watson实验室研制、作科学模拟研究 MasPar MP-1是中粒度SIMD计算机

保留阵列结构，但每个处理单元的规模减小，如1bit 去掉阵列结构和分布存储器 Burroughs公司的BSP是典型代表 并行处理机的另两个发展方向 保留阵列结构，但每个处理单元的规模减小，如1bit 去掉阵列结构和分布存储器 Burroughs公司的BSP是典型代表 Illiac IV 1968 Goodyear MPP 1980 BSP 1982 DAP 610 1987 CM2 1990 CM5 1991 IBM GF-11 MasPar MP-1

8.3.1 Illiac IV 并行处理机 1963年，美国西屋电器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network” 1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同 原计划：256个PE，每个PE每240ns处理一个64位的浮点数，每个局部存储器PEM为2Kx64位，总的运算速度为1GFLOPS 美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用了4倍的经费，只达到1/20的速度。只实现了8x8=64个PE，只达到50MFLOPS Illiac IV系统的影响非常大 是并行处理机、分布存储器并行处理机的典型代表

Illiac IV系统组成 Illiac IV系统由三大部分组成，是3种类型处理机联合组成的多机系统 Illiac IV处理机阵列(processing element array) 8x8，包括PE、PEM和互连网络 阵列控制器CU(array control unit) 处理单元阵列的控制部分，又可视为一台相对独立的小型标量处理机 一台标准的Burroughs B6700计算机 输入输出处理机和操作系统管理功能

图8.5 Illiac IV系统总框图

Illiac IV处理阵列由8x8=64个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成 每一个PUi只和它的东、西、南、北四个近邻直接连接{PUi+1 mod 64,PUi-1 mod 64,PUi+8 mod 64,PUi-8 mod 64} 南北方向上同一列的PU连成一个环，东西方向上构成一个闭合螺线 闭合螺线最短距离不超过7步。普通网格最短距离不超过8步 n×n个单元组成的阵列，任意两个单元之间的最短距离不超过n-1步 PU0到PU36的距离：采用普通网格必须8步 PU0 ® PU1 ® PU2 ® PU3 ® PU4 ® PU12 ® PU20 ® PU28 ® PU36 或PU0®PU8®PU16®PU24®PU32®PU33®PU34®PU35®PU36 或 ......(等于8步的很多，大于8步的更多) 采用闭合螺旋线，只需要7步 PU0®PU63®PU62®PU61®PU60®PU52®PU44®PU36 或PU0PU63PU55PU47PU39PU38PU37PU36 或......

图8.6 Illiac IV处理部件的连接

图8.7 Illiac IV处理单元原理框图

数组处理的运算部分 处理单元可以对64位、32 位和8位操作数进行多种算术和逻辑操作，也包括48位、24位或8位定点运算 将64个64位处理单元的硬件当作64个64位、128个32位或512个8位的处理单元发挥作用 并行加法的速度为每秒10^10次8位定点加法，或每秒150x10^6次64位浮点加法

处理单元 有6个可编程序寄存器RGA、RGB、RGR、RGS、RGX和RGM，以及加/乘算术单元AU、逻辑单元LU、移位单元SU和地址加法器ADA RGA是累加寄存器，存放第一操作数和操作结果 RGB是操作数寄存器，存放加、减、乘、除等二元操作的第2操作数 RGR是被乘数寄存器兼互连寄存器，经过东、西、南、北4个互连路径之一完成处理单元之间的数据直接传送 RGS是通用寄存器，可被程序用来暂存中间结果 4个寄存器都是64位 操作数来自4个方面：PU本身的寄存器；阵列存储器；CU的公共数据总线；PE的4个近邻 16位的RGX是变址寄存器，它利用地址加法器ADA修改指令地址，并将形成的有效地址经过存储器地址寄存器MAR输往存储器逻辑部件MLU

8位模式寄存器RGM E和E1位是"活动"标志位 控制RGA、RGS和阵列存储器的工作，E还控制RGX PE以32位字长运算时，E和E1是互相独立的 64个处理单元中的每一个处理单元都可以进行单独控制。只有那些处于活动状态的处理单元才执行单指令流规定的共同操作 F和F1位保存运算结果出错(上溢、下溢)标志 G、H、I、J位保存测试结果 RGM处于CU的监督之下，一旦出错，就发出CU陷阱中断 RGM处于程序员的控制之下，可根据其它几个寄存器的内容置为"活动"或"不活动"状态 有一种指令能在RGR的内容大于RGA的内容时置该处理单元为"不活动"状态。 模式寄存器在阵列处理机中是必不可少的，它对增强阵列处理机的功能和结构灵活性发挥着很大的作用

处理单元存储器PEM 处理单元存储器PEM分属每一个处理单元，各有2048×64位的存储容量和不大于350ns的取数时间 64个PEM联合组成阵列存储器，存放数据和指令 整个阵列存储器可以接受控制器的访问，读出8个字的信息块到它的缓冲器中，也可经过1024位的总线与I/O开关相连 每一个处理单元只能访问自己的存储器 分布在各个处理单元存储器中的公共数据，读至控制器后，经公共数据总线广播到64个处理单元 节省存储空间，且允许公共数据的存取与其它操作在时间上重叠 阵列存储器就如同一个二维访问存储器 把64个PEM看成列，把每一个PEM本身看成行 CU对它是按列访问，PE对它是按行访问

阵列存储器 阵列存储器的另一个特点是它的双重变址机构 控制器实现所有处理单元的公共变址 每一个处理单元内部还可以单独变址 最终的操作数有效地址对PEi来说由下式决定 ai=a+(b)+(ci) a是指令地址 (b)是CU中央变址寄存器内容 (ci)是局部变址寄存器内容 这种安排增加了各处理单元存储器之间数据分配的灵活性，对于分别处理矩阵的行和列及其它维数结构很有效 PE和PEM之间经过存储器逻辑部件MLU相连，它包含存储器信息寄存器和有关控制逻辑线路，实现PEM分别和PE、CU以及I/O之间的信息传送

2、阵列控制器 阵列控制器CU实际上是一台小型控制计算机 对阵列处理单元实行控制和完成标量操作 标量操作与各PE的数组操作可以重叠执行 控制器的功能 (1)对指令进行译码，并执行标量指令 (2)向各处理单元发出执行数组操作指令所需的控制信号 (3)产生和向所有处理单元广播公共的地址 (4)产生和向所有处理单元广播公共的数据 (5)接收和处理PE、I/O操作及B6700产生的陷阱中断信号

4条信息通路 (1) CU总线 处理单元存储器PEM经过CU总线把指令和数据送往阵列控制器，以8个64位字为一信息块 指令是指分布存放在阵列存储器中用户程序的指令 数据可以是处理所需的公共数据，先将它们送到CU，再利用CU的广播功能送到各处理单元 (2) 公共数据总线CDB (Common Data Bus) 64位总线，用作向64个处理单元同时广播公共数据的通路 作为公共乘数的常数不必在64个PEM重复存放，可由CU的某个寄存器送往各处理单元 指令的操作数和地址部分也经过CDB送来

4条信息通路 (3) 模式位线(mode bit line) 每一个单元都可经模式位线把它的模式寄存器(mode register)状态送到CU，送来的信息中包括该处理单元的"活动"状态位 只有那些处于"活动"状态的处理单元才执行单指令流所规定的公共操作 从64个处理单元送往CU的模式位在CU的累加寄存器中拼成一个模式字 在CU内部执行一定的测试指令，对模式字进行测试 根据测试结果控制要求的程序转移动作 (4) 指令控制线 处理单元微操作控制信号和处理单元存储器地址、读/写控制信号 经约200根指令控制线由CU送到阵列处理单元PE和存储器逻辑部件MLU

2、输入输出系统 Illiac IV的输入输出系统的组成 磁盘文件系统DFS I/O分系统 一台B6700处理机

磁盘文件系统DFS 两套大容量并行读写磁盘系统及其相应的控制器 每套有13台磁盘机，总容量为10^9位(=1Gb) 每台磁盘机有128道，每道一个磁头，并行读写，数据宽度为256位 最大传输率为502x10^6位/秒(=502Mb/s) 平均等待时间为19.6ms 两个通道同时发送或接收数据时，数据宽度为512位，最大传输率可达10^9位/秒(=1Gb/s)

I/O分系统 包括三部分 输入/输出开关IOS 控制描述字控制器CDC 输入/输出缓冲存储器BIOM IOS的功能 作为名副其实的开关，把DFS或可能连上的实时装置转接到阵列存储器，进行大批数据的I/O传送 作为DFS和PEM之间的缓冲，以平衡两边不同的数据宽度 CDC对阵列控制器的I/O请求进行管理 CDC使B6700管理计算机中断，由它响应I/O请求，并通过CDC给CU送回响应代码，在CU中设置控制状态字 然后，CDC使B6700启动PEM的加载过程，DFS向PEM送入程序和数据 PEM加载完毕后，由CDC向CU传送控制信号，使它开始执行Illiac IV的程序

I/O分系统 BIOM处在DFS和B6700之间，匹配二者之间的传送频带 把B6700的48位字变换为Illiac IV的64位字，以两个字共128位的数据宽度输送给DFS BIOM用4个PE存储器做成，总容量为8192x64位 B6700存储器经CPU输送数据的频带是80x10^6位/秒 ，DFS输送数据的频带是500x10^6位/秒，二者相比超过6倍 BIOM作为B6700和DFS间的缓冲

B6700 B6700管理计算机的基本组成部分 单中央处理器(另一CPU可选) 32K字内存(可扩充至512K字) 经过多路开关控制的一大批外围设备 一台容量为10^12位(=1Tb)的激光外存储器 ARPA网络接口 B6700的作用是管理全部系统资源 完成用户程序的编译或汇编 为Illiac IV 进行作业调度、存储分配、产生入/出控制描述字送至CDC、处理中断 提供操作系统所具备的其它服务

8.3.2 BSP计算机 BSP计算机由美国宝来公司和伊利诺依大学于1979年制造 共享存储器结构的SIMD计算机的典型代表 BSP不是一台独立运行的计算机，是附属于系统管理机的一台后端处理机 BSP承担算术运算，系统管理机提供分时服务、数据和程序文件编辑、与远程作业站终端、网络的数据通信、BSP程序的向量化编译和连接、数据长期存储以及数据库管理等功能 BSP由控制处理机、并行处理机、文件存储器、并行存储器模块以及对准网络等组成

图8.9 BSP的功能结构与流水线处理

1．并行处理机 并行处理机以160ns的时钟周期进行向量计算 所有16个算术单元AE对不同的数据组(从并行处理机控制器广播来)进行同一种指令操作 大部分的算术运算能在2个时钟周期(320ns)内完成 BSP的执行速度最高可达50MFLOPS 进行向量运算的数据存在17个并行存储器模块中，每个模块的容量可达512K字，周期时间为160ns 数据在存储器模块和AE间以每秒100M字的速率进行传输 17个存储器模块的组织形成一个无冲突访问存储器，它容许对任意长度以及跳距不是17倍数的向量实现无冲突存取 16个AE是以SIMD方式在单一微序列控制下同步工作 每个AE中，只有最原始的操作才采用硬连线方式 控制字的宽度为100位。除实现浮点操作以外，AE还有较强的非数值处理能力

PE性能提高，数量降低 浮点加、减和乘都能在两个时钟周期内完成 采用两个时钟周期可使存储器频宽与AE进行三元操作时的频宽相平衡 浮点除要用1200ns，用Newton-Raphson迭代算法产生倒数来实现 每个AE设有只读存储器，给出除法和平方根迭代的第一次近似值 浮点字长为48位，尾数为36位有效值，阶码为10位，以2为底。数的精度可达到十进制11位 AE在关键部位设置了双字长累加器和双字长寄存器，使双精度运算直接用硬件实现 AE还可用软件方法来实现三倍精度的算术运算 可估算出，BSP用Fortran来表达的很大范围的计算问题中，速度可达20到40MFLOPS

2．控制处理机 用以控制并行处理机 提供与系统管理机相连的接口 标量处理机处理存储在控制存储器中的全部操作系统和用户程序的指令 以12MHz的时钟频率执行用户程序的串行或标量部分，最高速度可达1.5MFLOPS 全部的向量指令以及某些成组的标量指令被送给并行处理机控制器。在经过合格性检查之后，控制器将它们转换为微序列，去控制16个AE操作 双极型控制存储器的容量为256K字，周期时间为160ns，每个字长48位另加8位奇偶校验位，提供单错校正双错检测(SECDED) 控制维护单元是系统管理机与控制处理机其余部分之间的接口，用来进行初始化、监控命令通信和维护

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

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

存储器-存储器型的浮点运算流水进行 BSP的流水线由5个功能级组成 16个操作数从存储器模块取出，通过输入对准网络送给AE，再将结果经输出对准网络送存储器模块 这几级的操作重叠进行 物理上输入对准和输出对准都在一个实际对准网络进行 除16个AE中的空间并行性以及读取、对准和存储的流水线操作外，AE中的向量运算可同标量处理机的标量处理重叠 BSP既适于处理长向量和短向量，也能处理单独的标量

5．质数存储系统 BSP并行存储器由17个周期时间为160ns的存储模块组成 每个周期存取16个字，每个字的最大有效存储周期为10ns 与算术单元完成浮点加和乘的速率很好地平衡 每次运算需要两个变量，算术单元中设有中间寄存器其运算速度为320ns/16次=20ns/次 程序和标量都存放在控制存储器中，只有数组存取(包括I/O)才用到并行存储器 三元向量两次算术运算中需要用到3个变量，产生一个结果，共访问存储器4次，在并行存储器和浮点运算之间的频带保持完全平衡 长向量中间结果都存在寄存器中，每次运算只需1个操作数 并行存储器有足够的频宽留给输入和输出信息

5．质数存储系统 BSP并行存储器的主要革新是采用了17个存储模块 之前的巨型机普遍用多个并行存储器模块，易因访问冲突而使频带严重变窄 BSP的一个独特的性能就是它的存储系统可无冲突访问，每个存储周期送给每个PE一个有用的操作数 存储器中向量元素的间距不一定为1。因而DO循环可以有非单位增量，或者程序可以访问矩阵的行、列和对角线而无需付出额外的代价 巨型机的设计者或对使用存储器作严格的访问限制，或采用昂贵的快速存储器件，用很宽的存储器频带来获得一定程度无冲突访问的功能

5．质数存储系统 在BSP中保证无冲突访问的硬件技术 质数个存储器端口 存储器端口和AE间的完全交叉开关 特殊的存储器地址生成机构，为具体的地址模式计算出合适的地址 地址模式是指正统的串行计算机所用的那一种模式 并行存储器采用这种模式能与当前程序设计语言的所有结构完全兼容。特别是Fortran的EQUIVALENCE、COMMON以及数组参数传送都可用常规计算机上一样的方法来实现 数组元素的地址相隔是存储器模块数的整数倍时，冲突一定发生 这时所有要访问的值处于同一个存储器模块 BSP应该避免跳距为17、34、51等的情况 51是有问题的跳距。正好是列长度为50的数组的正向对角线元素存储地址的跳距

5．质数存储系统 在BSP中发生冲突，运算仍可正确进行，但速度下降到正常速度的1/16 系统记录冲突以及它们对总的运行时间影响的情况，以便在这种影响太大时使程序员采取一定的改进措施 BSP可对下列4类操作进行并行计算 (1)16个算术单元实现并行运算 (2)存储器的读取和存储及存储器和算术单元间的数据传输 (3)并行处理机控制器的变址值、向量长度和循环控制计算 (4)线性向量操作描述字在标量处理机中的生成

8.3.3 CM-2计算机 Connection Machine的CM-2是细粒度SIMD计算机 由数千个位片PE组成 峰值处理速度超过10Gflops 程序从前端开始执行，需要并行数据操作时，发送微指令到后端处理阵列 定序器(sequencer)分解这些微指令并且把它们广播给阵列中的所有数据处理器(data processor) 前端机和处理阵列间有3条交换数据计算结果的通路 广播总线(broadcasting) 全局组合总线(global combining) 标量存储器总线(scalar memory bus) 通过广播总线把数据或指令同时传送到所有数据处理器 前端机通过全局组合总线对来自各处理器的数据进行求和、最大值、逻辑或等运算 前端机每次通过标量总线从与数据处理器相连的存储器读取32位数据、或每次将32位数据写入与数据处理器相连的存储器 VAX和Symbolics机都可以用作前端机和主机

图8.11 CM-2的系统结构

1．处理阵列 CM-2是一台数据并行计算的后端机 处理阵列包含4K到64K个位片数据处理器(或PE) 数据处理器由定序器控制 定序器对来自前端机的微指令进行译码，然后把毫微指令广播到阵列中各个处理器 所有处理器可同时访问它们的存储器，以锁步方式执行广播来的指令 处理器之间通过寻径、NEWS网格(NEWS gird)或扫描机构(scanning mechanism) 相互交换数据 这些网络也与I/O接口相连 称为数据穹(data vault)的大容量存储器子系统与I/O相连 数据穹是基于磁盘的海量存储系统，用来存放程序文件和大数据库。可存储多达60G字节的数据

1．处理阵列 每个处理器结点包括32个位片数据处理器、一个可选的浮点加速器和处理器之间通信的接口 每个数据处理器用3个输入和2个输出的位片ALU、锁存器和存储器接口实现 ALU可执行位串全加操作和布尔逻辑操作 每个结点有一对处理器芯片，共享一组存储器芯片 每个处理芯片有16个处理器 称为Pairs的并行指令系统包括许多毫微指令 用于存储器的装入和存储、算术和逻辑运算、寻径器控制、NEWS网格控制、超立方体接口控制、浮点运算、I/O和诊断操作 每个处理器芯片的存储器数据路径宽度是22位(16位数和6位ECC) 18位存储器地址允许32个处理器共享2^18=256K个存储器字(512K字节数据) 浮点芯片一次执行32位的操作。中间计算结果可以存入存储器供后续运算使用 整数算术运算直接由处理器以位串方式执行

两个处理器芯片、一组存储器和浮点芯片组成的CM-2处理结点

2．寻径器、NEWS网格和扫描机构 (1) 寻径器 每个处理器芯片包含一个用于处理器之间数据寻径的专门硬件 所有处理器芯片上的寻径器结点连成一个布尔n-立方体 CM-2最大配置4096个寻径器结点，连成一个12维超立方体 每个寻径器结点与12个其它寻径器结点相连接，其中包括它的对偶结点在内 同一结点上的16个处理器在发送消息给12-立方体另一顶点上的任一处理器时具有相同的能力

例 12-立方体的每个顶点上的处理器编号为0到15 4096个顶点的超立方体的寻径器编号为0到4095 第7号寻径器结点上的第5号处理器在整个系统中的编号为16x7+5=117要发送一个消息给处理器361。处理器361位于第22号结点的第9号处理器(16x22+9=361) 寻径器结点 7=(000000000111)2 寻径器结点22=(000000010110)2 这两个二进制编号在维0和维4不同 这一消息一定通过维0和维4到达它的目的结点 如果不存在争用超立方体连线现象，消息从寻径器结点7开始 沿维0方向传到寻径器结点6=(00000000110)2 再沿维4方向传到寻径器结点22 如果寻径器点7号的另一消息正在使用维0方向的连线，为避免发生通道冲突 沿维4方向传到寻径器结点23=(000000010111)2 再沿维0方向到达最终的目的结点

(2) NEWS网格 每个处理器芯片中的16个物理处理器可以排列成8x2，1x16，4x4，4x2x2或2x2x2x2等形式的网格 规定每个物理处理器有64个虚拟处理器。可想象这64个虚拟处理器在芯片中排列成8x8网格 NEWS网格基于各种不同配置网格的每个处理器都有东、南、西、北4个邻居 可选择一部分超立方体的连线把2^12个结点连成一个任意形状的二维网格，64x64是一种可能的网格形状 每个结点的内部网格与全局网格结合在一起，可把处理器排列成任意维、任何形状的NEWS网格 灵活的处理器间互连方式使数据非常有效地沿着根据应用要求而建立的专门网格进行传递

(3) 扫描机构 除通过超立方体寻径器可动态重构NEWS网格，CM-2还有专门的硬件支持对整个NEWS网格的扫描或传播 这是很有效的并行操作，在整个阵列中进行快速的数据组合和传播 对NEWS网格扫描是把通信和计算结合在一起 可沿某一维方向同时对网格的每一行扫描，求出该行的部分和、找出最大值或最小值、进行按位或、与、异或计算 扫描操作可扩展到对整个阵列的所有元素进行 传播能将一个数据传送给其它芯片上的处理器 一位二进制数只用75步就可沿着超立方体连线从一个芯片送到所有其它芯片 为便于访问，各种形式的扫描和传播操作已设计在Pairs 指令中

3. 输入输出系统 Connection Machine不但强调计算的大规模并行性，还强调计算结果的可视化 2到16条高速I/O通道用于数据和/或图象I/O操作 连接到I/O通道的外围设备包括 数据穹 CM-HIPPI系统 CM-IOP系统 VME总线接口控制器

CM-2已用于解决几乎所有MPP所面临的具有重大挑战性的应用 Connection Machine系列已用于借助相关反馈技术的文档检索、基于记忆的推理 医疗诊断系统QUACK中摸拟诊断疾病 处理工作量很大的自然语言 CM-2的其它应用还包括SPICE的VLSI电路分析和布线、计算流体动力学、信号/图象/视觉处理和集成、神经网络模拟和连接模型、动态规划，上下文无关文法分析、射线追踪图以及计算几何等问题

8.3.4 MasPar MP-1系统 略

8.4 并行处理机的应用(算法举例) 略 并行处理机的典型并行算法 主要包括有限差分问题、矩阵加、矩阵乘、累加和、递归技术、递归加倍法与循环归约法

8.5 连续模型的结构向何处发展 略