1、第八章 并行处理机和多处理机,并行处理机又叫SIMD计算机。它是单一控制部件控制下的多个处理单元构成的阵列，所以又称为阵列处理机。多处理机是由多台独立的处理机组成的系统。并行处理机结构和实例多处理机结构和实例,并行处理计算机模型并行处理机定义：多个PU按照一定方式互连，在同一个CU控制下，对各自的数据完成同一条指令规定的操作。从CU看，指令是串行执行的，从PU看，数据是并行处理的。并行处理机也称为阵列处理机。按照佛林分类法，它属于SIMD计算机。并行处理机的应用领域：主要用于高速向量或矩阵运算中。,8.1 并行处理机结构和实例,下图是H.J.Siegel提出的SIMD计算机的操作模型,并行处理
2、机的操作模型可用五元组来表示：M(N，C，I，M，R), 其中： N为PE个数。如IlliacIV有64个PE。 C为由控制部件CU直接执行的指令集，包括标量指令和程序控制指令。I为所有PE并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。M为屏蔽操作集，每种屏蔽将PE划分为允许操作和禁止操作两个子集。 R是数据寻径集，说明互连网络中PE间通信所需要的各种设置模式。,并行处理机的基本结构两种SIMD计算机的基本结构：分布存储器并行处理机共享存储器并行处理机一台并行处理机由五个部分组成：多个处理单元PE多个存储器模块M一个控制器CU一个互
3、连网络ICN一台输入输出处理机IOP,目前的大部分并行处理机是基于分布式存储器模型的系统。比较容易构成MPP（Massively Parallel Processor）,几十万个PE。必须依靠并行算法来提高PE的利用率。因此，应用领域很有限。CU是控制部件，执行标量指令，并把向量指令广播到各个PE中。在CU中通常有一个较大容量的存储器。IOP是输入输出处理机，或称为主机。在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作。数据在局部存储器中的分布是一个很关键的问题。标量指令与向量指令可以并发执行。,1、分布存储器结构,共享的多体并行存储器 SM 通过互连网络与
4、各处理单元PE相连。存储模块的数目等于或略大于处理单元的数目。同时在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储冲突的影响。共享存储器模型的处理单元数目一般不多，几个至几十个。Burroughs Scientific Processor (BSP)采用了这种结构。16个PE通过一个1617的对准互连网络访问17个共享存储器模块。存储器模块数与PE数互质可以实现无冲突并行访问存储器。,2. 共享存储器并行处理机,PE0,互连网络,CU,PE1,PEn-1,IOP,SM0,SM1,SMk-1,并行处理
5、机的主要特点如下：速度快，特别适于高速数值计算。SIMD依靠的是资源重复，而不是时间重叠。它依靠增加PE个数，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。依赖于互连网络和并行算法。互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。需要有一台高性能的标量处理机。如果一台机器的向量处理速度极高，但标量处理速度只是每秒一百万次，那么对于标量运算占10的题目来说，总的有效速度就不过是每秒一千万次。SIMD基本上是一台向量处理专用计算机。尽管它有一个功能很强的控制部件实际上起作标量处理机的作用，但仍然必须和一台高性能单处理机配合工作，使后者担负系统的全部管理功能。
6、,并行处理机的特点,IlliacIV 是最先采用SIMD结构的并行机随后一个方向是用位片PE制造的并行机，如Goodyear MPP、AMT/DAP 610和TMC/CM-2。CM-5是以SIMD模式运行的同步MIMD计算机。另一方向是用字宽运算PE的中粒度SIMD计算机。并行处理机的两个发展方向：保留阵列结构，但每个处理单元的规模减小，如一个bit。去掉阵列结构和分布存储器。Burroughs公司的BSP是典型代表。 GF-11是由IBM Watson实验室研制、作科学模拟研究用的。MasPar MP1是中粒度并行处理机的典型代表。下面介绍并行处理机的两种典型代表：采用阵列结构分布存储器的I
7、lliacIV并行处理机去掉阵列结构和分布存储器BSP并行处理机。,并行处理机实例,1963年，美国西屋电器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，每个PE每240ns处理一个64位的浮点数，每个局部存储器PEM为2K?64位，总的运算速度为1GFLOPS。美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用了4倍的经费，只达到1
8、/20的速度。只实现了8?864个PE，只达到50MFLOPS。IlliacIV系统的影响非常大。它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表。IlliacIV系统由三大部分组成。IlliacIV处理机阵列，阵列控制器，一台标准的Burroughs B6700计算机。,1 IlliacIV 阵列处理机,1、IlliacIV处理阵列IlliacIV处理阵列由8864个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。每一个PUi只和它的东、西、南、北四个近邻直接连接。PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64南
9、北方向上同一列的PU连成一个环，东西方向上构成一个闭合螺线。采用闭合螺线最短距离不超过7步。而普通网格最短距离不超过8步。例如：从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,普通网格必须8步：PU0 PU1 PU2 PU3 PU4 PU12 PU20 PU28 PU36或 PU0 P
10、U8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 闭合螺旋线只要7步：PU0 PU63 PU62 PU61 PU60 PU52 PU44 PU36或 PU0 PU63 PU55 PU47 PU39 PU38 PU37 PU36或 ,2、阵列控制器阵列控制器CU实际上是一台小型控制计算机。对阵列处理单元实行控制和完成标量操作。标量操作与各PE的数组操作可以重叠执行。控制器的功能有以下五个方面：(1) 对指令进行译码，并执行标量指令；(2) 向各处理单元发出执行数组操作指令所需的控制信号；(3) 产生和向所有处理单元广播公共的地址；,(4) 产生和向所有处理单元广播公共
11、的数据；(5) 接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。2、输入输出系统IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成。I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部分组成。,试在含一个PE的SISD机和在含m个PE的且连接成一线性环的SIMD机上计算下列求内积的表达式。假定完成每次ADD操作需2个单元时间，完成每次MULTIPLY操作需4个单位时间，沿双向环在相邻PE间移数需1个单位时间。（1）SISD计算机上计算s需多少时间？（2）SIMD计算机上计算s需多少时间？（3）用SIMD
12、机计算s相对于用SISD机计算的加速比是多少？,习题8.6,（1）在SISD计算机中计算s需要串行计算n次乘法和n-1次加法。共需要时间： 算法如下： S=A1*B1 For i=2 to n DoS=S+Ai*Bi Enddo（2）在SIMD计算机上计算采用如下的算法：（假设mn）首先，把向量中的n对元素尽量平均地分配到m个处理器中，每个处理器最多分配n/m+1对，最少分配n/m对，最多经过4（n/m+1）+2n/m 时间，所有n个处理器上都得到了一个局部和，对这m个处理器,解答,构成的线性环做累加运算。若采用两路7线性累加的方法共用做加法m/2次,数据传递m/2次，共用时间4（n/m+1）
13、+2n/m+3m/2 = 6n/m+ 3m/2+4。若用递归累加的方法，假设m 是2的p次幂。做p次并行的加法，移位1+2+4+ + m/2 = m-1 次。用时2p+（m-1）。总共用时为 4（n/m+1）+2n/m+2log m +（m-1） = 6n/m+ m+2log m +3进一步分析：当2logm 16时 并行累加比两路线性累加更优。反之，当m 16 时，两路线性累加更快。其根本原因就是并行累加算法节省了加法时间，但是花费更多的数据传送时间。,算法描述如下:Par：For j=1 to m DoS(j)=A1j*B1jFor 2 to n/m DoS(j)=S(j)+Aij*Bij
14、EnddoS(j)=S(j)+S(j+1)S(j)=S(j)+S(j+2)S(j)=S(j)+S(j+4) S(j)=S(j)+S(j+n/m)Enddo,（3）加速比当采用两路线性累加的方法时加速比为：若m = n，做乘法的时间变为4，则加速比简化为当采用递归并行累加时加速比为：当m = n 时，做乘法的时间变为4，则加速比简化为,分析其原因，可以看出，线性互连网络的传输开销在这里是制约加速比增长的最大障碍，无论采用何种并行算法，一个数据从线性环形网络中的一个节点传递到最远的节点的最短时间为m/2，这个时间是无法改进的，并且随着处理节点的增多成为最主要的时间开销。相对而言，加法和乘法随着处理
15、单元的增多，所占的时间比例越来越小。,8.2多处理机结构和实例,两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。按照Flynn分类法，多处理机系统属于MIMD计算机。多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。,多处理机结构由若干台独立的计算机组成，每台计算机能够独立执行自己的程序。Flynn称这种结构为多指令流多数据流（MIMD）结构。多处理机系统中的处理机之间按某种形式互连，从而实现程序之间的数据交换和同步。多处理机系统中每台处理机都有寄存器、运算器、逻辑部件、访问存储器和I/O的通
16、道。还有一种多处理机系统中每台处理机有自己的存储器和I/O设备。,多处理机结构,互连网络,处理机1,处理机2,处理机N,存储器,存储器,存储器,I/O,I/O,具有通过互连网络共享存储器和I/O的多处理机系统,每个处理机都拥有自己的存储器和I/O的多处理机系统,1、结构灵活性并行处理机：专用，PE数很多（几千个），固定有限的通信多处理机： 通用，几十个，高速灵活的通信2、程序并行性并行处理机的并行性存在于指令内部，识别比较容易。多处理机的并行性存在于指令外部，在多个任务之间，识别难度较大。一个简单的例子：Y = A+B*C*D/E+F用两个处理机：CPU1： CPU2： B*C， D/E， A
17、+F， B*C*D/E A+B*C*D/E+F,多处理机系统的特点,3、并行任务派生并行处理机把同种操作集中在一起，由指令直接启动各PE同时工作。 多处理机用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务，如果任务数多于处理机数，多余的任务进入排队器等待。4、进程同步并行处理机仅一个CU，自然是同步的 多处理机执行不同的指令，工作进度不会也不必保持相同,先做完的要停下来等待。有数据相关和控制相关也要停下来等待,要采取特殊的同步措施来保持程序所要求的正确顺序。5、资源分配和进程调度并行处理机的PE是固定的，采用屏蔽手段改变实际参加操作的PE数目多处理机执行并发任务
18、，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化提出资源分配和进程调度问题，它对整个系统的效率有很大的影响。,引起峰值性能下降的原因是：(1) 因处理机间通信而产生的延迟(2) 一台处理机与其它处理机同步所需的开销(3) 当没有足够多任务时，一台或多台处理机处于空闲状态(4) 由于一台或多台处理机执行无用的工作(5) 系统控制和操作调度所需开销研究多处理机的目的：提前5年得到速度高10倍的机器。 或用1/10的价格获得一台高性能的机器。如果设计得好，在某些适合进行并行处理得应用领域，可以达到：提前10年得到速度高100倍的机器 或用1/100的
19、价格获得一台高性能的机器。,多处理机性能模型,并行性在很大程度上依赖于R/C比值，其中：R代表程序执行时间，C代表通信开销。通常：R/C比值小，并行性低。R/C比值大，并行性高如果把作业分解成较大的块，就能得到较大的R/C值，但是所得到的并行性比最大可能的并行性要小得多。R/C比值是衡量任务粒度(Granularity)大小的尺度在粗粒度（Coarsegrain）并行情况下，R/C比值比较大，通信开销小在细粒度（Finegrain）并行情况下，R/C比值比较小，通信开销大细粒度并行性需要的处理机多，粗粒度并行性需要的处理机少。细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。
20、在极端情况下，一个小任务只完成一个操作。,1.基本模型,在两台处理机情况每个任务的执行时间为R个单位时间两个任务不在同一台处理机上时，通信开销为C个单位时间K个任务给一台处理机M-K个任务给另一台处理机总处理时间=Rmax(M-K，K)+C(M-K)K结论：当R/CM/2时，把任务平均分给两台处理机能使总处理时间最小。,2.N台处理机系统的基本模型,将Ki个任务分配给第i台处理机。推广前面的式子：,分析任务均分给N台处理机和任务集中在一台处理机的总处理时间差，有：如果R/C比临界值M/2大，将任务平均分配给尽可能多的处理机进行处理，能获得最短处理时间。如果R/C比临界值M/2小，即使有很多台处
21、理机可供使用，也不可能比用一台处理机处理全部任务快。,并行系统的加速比是一个计算问题在一台处理机上的运行时间与在并行系统上的运行时间的比值，可近似如下：,多处理机的Cache一致性（自己看）,多处理机系统主要有四大类：(1) 多向量处理机系统：如CRAY YMP-90, NEC SX-3和FUJITSU VP-2000(2) SMP (Symmetry MultiProcessors)对称多处理机;SMP (Shared Memory MulptiProcessors)共享存储多处理机 如SGI Challenge，Sun SparcCenter 2000(3) MPP (massively
22、parallel processing)大规模并行处理机如Intel Paragon, CM-5, Cray T3D(4) Cluster 机群系统（NOW或COM）,多处理机实例,科学计算中的重大课题要求提供3T性能：(1) 1 Teraflops计算能力(2) 1 Terabyte主存储器(3) 1 Terabyte/s 输入输出频带宽度目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大。科学计算中的重大课题：全球气候预报, 基因工程 ,飞行动力学 ,海洋环流, 流体动力学, 超导建模, 半导体建模, 量子染色动力学, 视觉采用的关键技术：VLSI, 可扩展技术, 共享虚拟存储技术
23、,大规模并行处理机(MPP),虚拟共享存储器(Shared Virtual Memory)也称为共享分布存储器(Distributed Shared Memory)；物理上分布存储器，逻辑上共享存储器。虚拟共享存储器的优点：编程容易, 系统结构灵活可扩充性好, 有较好的软件移植性与消息传递方式相比，程序运行效率高，主要原因：(1) 数据块缓存在本地 (内存或Cache中), 可以多次使用(2) 通信时间分散，提高了并行性(3) 扩大存储空间，减少换页操作虚拟共享存储器实现途径：(1) 硬件实现, 利用Cache技术。需要增加专用硬件(2) 操作系统和库实现，通过虚拟存储机制取得共享和一致性。在
24、松耦合的分布存储多处理机上，不需要增加任何硬件(3) 编译实现，自动将共享访问转换成同步和一致原语。大多数系统采用途径(1)和(2)，或这两种途径结合实现,SMP称为共享存储多处理机 (Shared Memory mulptiProcessors),也称为对称多处理机 (Symmetry MultiProcessors)有三种模型：(1) UMA多处理机均匀存储器存取模型 (Uniform Memory Access)存储器被所有处理机均匀共享所有处理机对所有存储单元具有相同的存取时间每台处理机有局部Cache外围设备可以共享(2) NUMA多处理机非均匀存储器存取 (Nonuniform M
25、emory Access)模型存储器访问时间随存储单元的位置不同而变化。共享存储器在物理上是分布在所有处理机中的本地存储器。所有局部存储器地址空间的集合就组成了全局地址空间。,对称多处理机 (SMP),处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟。(3) COMA多处理机只有Cache的存储器结构 (Cache-Only Memory Architecture) 模型；COMA是一种只用Cache的多处理机系统实际上，COMA模型是NUMA模型的一种特例，后者分布存储器换成了Cache在每个处理机结点上没有主存储器，全部Cache组
26、成了全局虚拟地址空间远程Cache访问通过分布Cache目录进行共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。,1、机群系统的组成机群系统是利用高速网络将一组高性能工作站或高档PC机连接起来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。Cluster、NOW、COW从结构和结点间的通信方式来看，属于分布存储系统。机群系统中的主机和网络可以是同构的，也可以是异构的。微处理机技术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式正成为当前研究的热点。(1)微处理器的性能不断提高。(2)网络技术的进步使得松散耦合系统
27、的通信瓶颈逐步得到缓解。,机群系统 (Cluster),(3)并行编程环境的开发使得新编并行程序或改写串行程序更为容易。2、机群系统的特点(1)系统开发周期短。(2)用户投资风险小。(3)系统价格低。(4)节约系统资源。UC Berkeley计算机系100多台工作站的使用情况调查表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右。(5)系统扩展性好。(6)用户编程方便。,3、机群系统的关键技术(1)高效的通信系统在用户空间实现通信协议精简通信协议Active Message通信机制(2) 并行程序设计环境PVM(Parallel Virtual Machine)开始
28、于1989年夏天,美国橡树岭国家实验室(ORNL)；是一套并行计算工具软件，支持多用户及多任务运行；支持多种结构的计算机，工作站、并行机以及向量机等；支持C、C+和Fortran语言；自由软件，使用非常广泛；编程模型可以是SPMD或MPMD；具有容错功能，当发现一个结点出故障时，自动将之删除MPI(Message Passing Interface)在1992年11月至1994年元月产生。,能用于大多数并行计算机、计算机机群和异构网络环境，支持C和Fortran两种语言,编程模型采用SPMD,Express：美国Parasoft公司推出；能在不同的硬件环境上运行；支持C和Fortran两种程序
29、设计语言。Linda：美国Yale大学与科学计算协会共同研制；通过函数扩充现并行程序的设计；支持C-Linda、Fortran-Linda等(3) 并行程序设计语言在多处理机系统中，必须用并行程序设计语言编写程序。或者把已经用串行语言编写的程序转换成并行语言程序之后，才能在多处理机系统上运行。把传统串行语言程序转换成并行语言程序的过程称为并行编译。有两种并行编译方式：全自动并行编译与半自动并行编译：全自动并行编译是方向，但实现起来很困难。半自动并行编译又称为交互式并行编译。程序员通过多次与机器对话，找到串行程序中可以并行执行的部分。,并行编译器生成代码的形式有多种： 并行高级语言程序、并行中间
30、语言程序、并行目标语言程序(4) 负载平衡技术一个大任务可分解为多个子任务，把多个子任务分配到各个处理结点上并行执行的技术称为负载平衡技术对于由异构处理结点构成的并行系统，相同的负载在各结点上的运行时间可能不同。因此，准确的负载定义应是负载量与结点处理能力的比值负载平衡技术的核心就是调度算法，即将各个任务比较均衡地分布到不同的处理结点上并行计算，从而使各结点的利用率达到最大。负载平衡技术分为静态和动态两大类：静态方法是在编译时针对用户程序的各种信息（任务的计算量和通信关系等）及并行系统本身的状况（网络结构、各结点计算能力等）对用户程序中的并行任务作出静态分配决策。,动态方法是在程序运行过程中实
31、现负载平衡的。它通过分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。动态负载平衡的算法简单，实时控制，但增加了系统的额外开销。(5)并行程序调试技术用并行程序设计语言编写程序，比用串行程序设计语言更容易出错，因此，在多处理机系统中，用并行程序设计语言编写程序更加依赖于并行调试工具。并行程序调试的主要困难：并行程序的执行过程不能重现。(6)可靠性技术在多处理机上运行的程序通常比较大，程序执行时间很长（几十个小时或几十天）。如果在程序执行过程中出现偶然故障（如电源掉电、磁盘满、某一台处理机故障等），则整个运算过程要从头开始。定时设置检查点，保存现场信息。当出现故障时，只要回复到上一个检查点，不必从头开始执行。,
