第4章并行处理机.ppt

《第4章并行处理机.ppt》由会员分享，可在线阅读，更多相关《第4章并行处理机.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 并行处理机并行处理机两种并行性概念：同时性并行同时性并行Simultaneity：两个或两个以上事件在同一时刻发生并并发发性性并并行行Concurrency：两两个个或或两两个个以以上上事事件件在在同同一一时时间间间间隔隔内内发发生生实现并行的三条技术途径：实现并行的三条技术途径：资源重复资源重复：通过重复设置多个处理部件来提高速度时间重叠：流水线资源共享：分时系统，分布式系统 并行处理机采用同时性并行，资源重复技术。4.1 并行处理机模型并行处理机模型4.2 并行处理机的基本结构并行处理机的基本结构4.3 并行处理机实例并行处理机实例4.4 并行处理机算法举例并行处理机算法举例

2、14.1 4.1 并行处理机模型并行处理机模型并行处理机的定义：多多个个PU按按照照一一定定方方式式互互连连，在在同同一一个个CU控控制制下下，对对各各自自的的数数据完成同一条指令规定的操作。据完成同一条指令规定的操作。从从CU看，指令是串行执行的，从看，指令是串行执行的，从PU看，数据是并行处理的。看，数据是并行处理的。并行处理机也称为阵列处理机、SIMD处理机等并行处理机的应用领域：主要用于高速向量或矩阵运算并行处理机的操作模型可用五元组来表示：并行处理机的操作模型可用五元组来表示：M M(N(N，C C，I I，M M，R),R),其中：N N为为PEPE（处理单元）个数处理单元）个数。

3、C C为控制部件为控制部件CUCU执行的指令集执行的指令集，包括标量指令和程序控制指令。I I为所有为所有PEPE并行执行的指令集并行执行的指令集，包括ALU、数据传送等操作M M为屏蔽操作集为屏蔽操作集，将PE划分为允许操作和禁止操作两个子集R R是数据寻径集是数据寻径集，互连网络中PE间通信所需要的各种模式2M1M2MN-1M0344.2 并行处理机的基本结构并行处理机有两种典型结构：分布存储器并行处理机、共享存储器并行处理机分布存储器并行处理机、共享存储器并行处理机一台并行处理机由五个部分组成：多个处理单元多个处理单元PEPE，多个存储器模块多个存储器模块M M，一个控制器一个控制器CU

4、CU，一个互连网络一个互连网络ICNICN，一台输入输出处理机一台输入输出处理机IOPIOP。4.2.1 4.2.1 分布存储器并行处理机分布存储器并行处理机 4.2.2 4.2.2 共享存储器并行处理机共享存储器并行处理机 4.2.3 4.2.3 并行处理机的特点并行处理机的特点5 4.2.1 4.2.1 分布存储器并行处理机分布存储器并行处理机目前的大部分并行处理机是基于分布式存储器模型的目前的大部分并行处理机是基于分布式存储器模型的比比较较容容易易构构成成MPP(Massively Parallel Processor)（大量信息并行处理机）,几十万个PE。必须依靠并行算法来提高PE的利

5、用率。因此，应用领域有限。CU是控制部件，执行标量指令，并把向量指令广播到各个PE中。在CU中通常有一个较大容量的存储器。IOP是输入输出处理机，或称为主机。在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作。数据在局部存储器中的分布是一个很关键的问题。标量指令与向量指令可以并发执行。6 CUIOPLM0LM1LMn-1PE0PE1PEn-1互连网络广播总线7根据以上结构，可以看出，它包含重复设置的多个同样的处理单元PE，通过数据寻径网络（互连网络）以一定方式相连。每个PE有各自的本地存储器LM。在统一的CU作用下，实现并行操作。程序和数据通过IOP装入，由于

6、通过CU的是单指令流，所以指令的执行顺序还是和单处理机一样，基本上是串行处理。指令进行译码后，如果是标量操作，则直接由与CU直接连接的标量处理机执行。如果是向量操作，则将它广播到所有的PE并行的执行。互连网络负责PE间的通信，CU通过执行程序来控制互连网络。PE间的同步由CU的硬件实现。换句话说，所有的PE在同一周期执行同一条指令，然而可以通过用屏蔽逻辑来决定任何一个PE在给定的指令周期执行或不执行指令。84.2.2 4.2.2 共享存储器并行处理机共享存储器并行处理机共享多体并行存储器SM通过互连网络与各处理单元PE相连。存储模块的数目等于或略大于处理单元的数目。同时在存储模块之间合理分配数

7、据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储器冲突的影响。这种结构在PE数目不多的情况下是很理想的。共享存储器模型的处理单元数目一般不多，几个至几十个。共享存储器模型的处理单元数目一般不多，几个至几十个。Burroughs Scientific Processor(BSP)采用了这种结构。16个PE通过一个1617的对准互连网络访问17个共享存储器模块。存储器模块数与存储器模块数与PEPE数互质可以实现无冲突并行访问存储器。数互质可以实现无冲突并行访问存储器。910无论采用哪种存储方案，互连网络的存在都是必要的。在共享

8、内存方案中，它是内存与处理单元之间的必由之路。在分布内存方案中，即使处理单元所需数据在大多数情况下能由本地存储器提供，处理单元之间的数据交往仍是必不可少的。而各处理单元之间可以通过两条途径相互联系：一条是通过广播总线广播到各PE中，另一条是通过互连网络。在处理单元很多的并行处理机中，PE之间的直接数据通路是有限的。因此，互连网络的研究是解决性能的一个很重要的方面。114.2.3 4.2.3 并行处理机的特点并行处理机的特点速速度度高高，依靠增加PE个数来提高速度，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。模块性好模块性好，生产和维护方便。可靠性高可靠性高，容易实现容错和

9、重构。效效率率低低，通通常常作作为为专专用用计计算算机机，在很大程度上依赖于并行算法。它依靠的是资源重复，而不是时间重叠，它的每个处理单元要担负多种处理功能，其效率要低一些。依赖于互连网络依赖于互连网络。互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。它基本是一台向量处理专用计算机。它基本是一台向量处理专用计算机。124.3 并行处理机实例IlliacIV 是最先采用SIMD结构的并行处理机。随后一个方向是用位片PE制造的并行处理机，如Goodyear MPP、AMT/DAP610和TMC/CM-2。CM-5是以SIMD模式运行的同步MIMD计算机。另一个方向是用字宽运算P

10、E的中粒度SIMD计算机。并行处理机的两个发展方向：保留阵列结构，但每个处理单元的规模减小保留阵列结构，但每个处理单元的规模减小，如一个bit。去掉阵列结构和分布存储器去掉阵列结构和分布存储器。Burroughs公司的BSP是代表。GF-11是由IBM Watson实验室研制、作科学模拟研究用的。MasPar MP1是中粒度并行处理机的典型代表。并行处理机的两种典型代表：采用阵列结构分布存储器的IlliacIV并行处理机去掉阵列结构和分布存储器BSP并行处理机。134.3.1 4.3.1 IlliavIV IlliavIV 并行处理机并行处理机1963年，美国西屋电器公司提出“Slotnick

11、，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，每个PE每240ns处理一个64位浮点数，每个局部存储器PEM为2K64位，总的原算速度为1GFLOPS。美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用用了了4倍倍的的经经费费，只只达达到到1/20的的速速度度。只只实现了实现了8 864个个PE，只达到只达到50MFLOPS。IlliacIV系系统统的的影影响

12、响非非常常大大。它它是是并并行行处处理理机机的的典典型型代代表表，也也是是分布存储器并行处理机的典型代表。分布存储器并行处理机的典型代表。IlliacIV系统由三大部分组成。IlliacIV处理机阵列，阵列控制器，一台标准的Burroughs B6700计算机。14IlliacIVIlliacIV系统由三大部分组成系统由三大部分组成IlliacIV处理机阵列：8 X 8，包括PE、PEM和互连网络。阵列控制器CU，输入输出处理机：一台标准的Burroughs B6700计算机。151 1、阵列控制器、阵列控制器阵列控制器CU实际上是一台小型控制计算机。对对阵阵列列处处理理单单元元实实行行控控制

13、制和和完完成成标标量量操操作作。标标量量操操作作与与各各PEPE的数组操作可以重叠执行。的数组操作可以重叠执行。控制器的功能有以下五个方面：(1)对指令进行译码，并执行标量指令；(2)向各处理单元发出执行数组操作指令所需的控制信号；(3)产生和向所有处理单元广播公共的地址；(4)产生和向所有处理单元广播公共的数据；(5)接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。2 2、输入输出系统、输入输出系统IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成。I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部

14、分组成。163 3、IlliacIVIlliacIV处理阵列处理阵列IlliacIV处理阵列由64个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。每一个PUi只和它的东、西、南、北四个近邻PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64直接连接。南北方向同一列PU连成一个环，东西方向构成一个闭合螺线。闭合螺线最短距离不超过闭合螺线最短距离不超过7 7步。普通网格最短距离不超过步。普通网格最短距离不超过8 8步。步。例如：从PU0到PU36的距离：采用普通网格必须8步：PU0PU1PU2PU3PU4PU12PU20PU28PU3

15、6 或 PU0PU8PU16PU24PU32PU33PU34PU35PU36 或 如果采用闭合螺旋线，只需要7步：PU0PU63PU62PU61PU60PU52PU44PU36或 PU0PU63PU55PU47PU39PU38PU37PU36 或 对于nn个单元的阵列，任任意意两两个个单单元元之之间间的的最最短短距距离离不不超超过过n-1n-1步步。17普通网格必须8步：PUPU0 0PUPU1 1PUPU2 2PUPU3 3PUPU4 4PUPU1212PUPU2020PUPU2828PUPU3636或 PUPU0 0PUPU8 8PUPU1616PUPU2424PUPU3232PUPU33

16、33PUPU3434PUPU3535PUPU3636 或 闭合螺旋线只要7步：PUPU0 0PUPU6363PUPU6262PUPU6161PUPU6060PUPU5252PUPU4444PUPU3636 或 PUPU0 0PUPU6363PUPU5555PUPU4747PUPU3939PUPU3838PUPU3737PUPU3636 或 4.3.2 4.3.2 BSPBSP处理机处理机BSP（Buroughs Scientific Processor）计算机是由美国宝来公司和伊利诺依大学于1979年制造的。BSPBSP是共享存储器结构的并行处理机的典型代表。是共享存储器结构的并行处理机的典型

17、代表。BSP由控制处理机、并行处理机、文件存储器、并行存储器模块以及对准网络等5个部分组成。1 1、并行处理机、并行处理机时钟周期160ns，向量运算速度最高可达向量运算速度最高可达5050MFLOPSMFLOPS。17个并行存储器模块，每个模块512K字，存储周期160ns。5 5级流水线：级流水线：(1)(1)从从1717个存储模块中读出数据个存储模块中读出数据(2)(2)通过输出对准网络把数据送入通过输出对准网络把数据送入1616个并行处理部件个并行处理部件(3)16(3)16个并行处理部件并行处理机数据个并行处理部件并行处理机数据(4)(4)通过输入对准网络把数据从并行处理部件送到并行

18、存储器通过输入对准网络把数据从并行处理部件送到并行存储器(5)(5)把接收到的数据写入并行存储器把接收到的数据写入并行存储器19202 2、控制处理机、控制处理机控制处理机主要用来控制并行处理机。控制处理机主要用来控制并行处理机。提供与系统管理机相连的接口。执行存放在控制存储器中的操作系统和用户程序的标量部分。执行存放在控制存储器中的操作系统和用户程序的标量部分。全部向量指令及成组的标量指令被送给并行处理机。控制维护单元是系统管理机与控制处理机之间的接口，用来进行初始化、监控命令通信和维护。3 3、文件存储器、文件存储器计算任务文件从系统管理机加载到文件存储器，由控制处理机执行。文件存储器是B

19、SP直接控制下唯一的外围设备。程序执行过程中所产生的暂存文件和输出文件，在将它们送给系统管理机输出给用户之前是存在文件存储器中的。文件存储器的数据传输率较高，大大地缓解了I/O受限问题。4 4、对准网络、对准网络对准网络采用全交叉开关实现对准网络采用全交叉开关实现。数数据据从从一一个个源源广广播播至至几几个个目目的的地地，几几个个源源寻寻找找一一个个目目的的地地时时能能分解冲突。分解冲突。存储器模块和对准网络的组合实现了无冲突访问并行存储器存储器模块和对准网络的组合实现了无冲突访问并行存储器。对准网络还可以实现快速傅里叶变换、数据压缩和扩展操作。5 5、无访问冲突存储系统、无访问冲突存储系统只

20、有数组存取和I/O访问并行存储器。等效存储周期为等效存储周期为1010nsns。两次算术运算中需要用到三个变量，产生一个结果，共访问存储器4次，并行存储器和浮点运算之间的频带保持完全平衡频带保持完全平衡。对于长向量来，中间结果存在寄存器中，每次运算只需要一个操作数。因此并行存储器有足够的频宽留给输入和输出信息用。实实现现一一维维向向量量和和二二维维矩矩阵阵的的行行、列列、对对角角线线和和反反对对角角线线的的无无冲冲突访问。突访问。屏蔽与数据传送寻径机制AiBiCiDiIiRiSiALUTo other PEs PEMiPEiTo CURi的输入和输出隔离Si1表示活动CU：全局变址寄存器I，屏

21、蔽寄存器M23假定一个nn元素数组AA(i,j),0=i,j=n-1,其第j列元素存储在PEMj的n个邻接单元中(如100100+n-1).程序员访问主对角线A(i,j)：CU必须产生并播送存储器有效地址100Ii=j,则100Ii=100+j对一行访问？00 01 02 0310 11 12 1320 21 22 2330 31 32 33244.4 4.4 并行处理机算法举例并行处理机算法举例参考：计算机系统结构（第二版）参考：计算机系统结构（第二版）郑纬民郑纬民 汤志忠编著汤志忠编著要发挥并行处理机的效率，特别要发挥并行处理机的效率，特别依赖于并行算法依赖于并行算法。并行算法的一个关键问

22、题是要并行算法的一个关键问题是要提高向量化的程度提高向量化的程度。在在设设计计并并行行算算法法时时，要要特特别别注注意意数数据据在在多多个个存存储储模模块块之之间间的分布的分布，要解决好访问存储器的冲突问题。，要解决好访问存储器的冲突问题。互互连连网网络络并并不不能能提提供供所所有有处处理理单单元元之之间间的的连连接接，因因此此，并并行算法要行算法要充分利用互连网络的结构充分利用互连网络的结构。4.4.1 有限差分问题有限差分问题4.4.2 矩阵乘矩阵乘4.4.3 求累加和求累加和 4.4.4 并行排序并行排序254.4.1 4.4.1 有限差分问题有限差分问题有限差分方法是一种通用和有效方法

23、：把连续方程变换成离散形式。二阶偏导数表示为差分形式：并代入原方程，则可得有限差分计算公式：其中：(x,y)为平面直角坐标，h为网格间距。IlliacIVIlliacIV的的阵阵列列结结构构特特别别适适合合计计算算这这种种在在网网格格上上定定义义的的有有限限差差分函数分函数。把内部网格点分配给各个处理单元，计算过程可以并行完成，从而可几十倍地提高处理速度。264.4.2 4.4.2 矩阵乘矩阵乘A、B、C均为88的二维矩阵，则CAB的计算公式为：在串行机上要用一个三重循环程序，乘和加分别为512次(除循环控制外)。在并行处理机上求解，FORTRAN程序如下：DO 10 IDO 10 I0 0，

24、7 7 C(I,J)=0C(I,J)=0 DO 20 K=0,7DO 20 K=0,72020C(I,J)=C(I,J)+A(I,K)*B(K,J)C(I,J)=C(I,J)+A(I,K)*B(K,J)10 CONTINUE10 CONTINUE27在并行处理机上，J循环只需一次。速度提高到8倍。PE0PE0：c c0000a a0000b b0000a a0101b b1010a a0202b b2020a a0707b b7070 PE1 PE1：c c0101a a0000b b0101a a0101b b1111a a0202b b2121a a0707b b7171 PE7 PE7：

25、c c0707a a0000b b0707a a0101b b1717a a0202b b2727a a0707b b7777 PE0PE0：c c1010a a1010b b0000a a1111b b1010a a1212b b2020a a1717b b7070 PE1PE1：c c1111a a1010b b0101a a1111b b1111a a1212b b2121a a1717b b7171 PE7 PE7：c c1717a a1010b b0707a a1111b b1717a a1212b b2727a a1717b b7777PE7PE7：c c7777a a7070b

26、b0707a a7171b b1717a a7272b b2727a a7777b b7777行向量跨PEM存放列向量在同一个PEM初始时Cij0CU广播同一个乘数aij给所有PE;与B的第i个行向量的所有n个元素同时相乘2829PE0：c c0000a a0000b b0000a a0101b b1010a a0202b b2020a a0707b b7070PE1：c c0101a a0000b b0101a a0101b b1111a a0202b b2121a a0707b b7171 PE7：c c0707a a0000b b0707a a0101b b1717a a0202b b2

27、727a a0707b b7777PE0：c c1010a a1010b b0000a a1111b b1010a a1212b b2020a a1717b b7070PE1：c c1111a a1010b b0101a a1111b b1111a a1212b b2121a a1717b b7171 PE7：c c1717a a1010b b0707a a1111b b1717a a1212b b2727a a1717b b7777 PE7：c c7777a a7070b b0707a a7171b b1717a a7272b b2727a a7777b b7777如果64个处理单元全部利用

28、起来并行运算，即把K循环的运算也改为并行，则可进一步提高速度。要做到这一点，需要重新在阵列存储器中恰当分配数据。304.4.3 4.4.3 求累加和求累加和把N个数的顺序相加变为并行相加。串行求和的 FORTRAN 程序如下：C(-1)0 DO 10 I0,N10 C(I)C(I-1)A(I)在并行处理机上，采用递归加法，FORTRAN 程序如下：DO 10 I=0，log2N110AASRL(A,2*I)；把A向量逻辑右移2i个PE在并行处理机上只需做在并行处理机上只需做 loglog2 2N N 次加法。次加法。3132递归求和算法的性能分析：递归求和算法的性能分析：运算速度提高运算速度提

29、高：加速比为加速比为N/logN/log2 2N N倍倍运算次数增加运算次数增加：从从N N次增加到次增加到NlogNlog2 2N N次次效率降低效率降低：实际效率为实际效率为1/1/loglog2 2N N如：N N10241024，速速度度提提高高100100倍倍，运运算算次次数数增增加加1010倍倍，效效率率只只有有1/101/10如果N220，即100万个数求和，速度可以提高5万倍。这种方法也称为级联求和，或递归求和。与流水线中采用的方法相同，它利用结合律来提高并行度。可以利用结合律求解的递归问题还有：求最大数，求最小数，求最大数，求最小数，与进行异或运算，与进行逻辑或运算，与进行异

30、或运算，与进行逻辑或运算，与进行逻辑与运算，求与的点积。与进行逻辑与运算，求与的点积。334.4.4 并行排序并行排序01452367014253670124356702134657用系列交换实现完全混洗3413460257140536270145236702134657Batcher线性阵列奇偶合并排序子序列分别有序L1：逆混洗奇左偶右L2：将长度为2的子序列合并 L3:混洗01234567L4:比较交换35Thompson&Kung M(j,2)算法1 01,00 2 02 013 2 J1 3,2 J21 3 J3 3 1 J4 324 54,54 6 46 4556 7 6,75 7

31、7 576两个长度为j的子序列分别有序J1：奇行左，偶行右J2：偶行交换J3：列排序J4：偶奇比较交换36Thompson&Kung M(j,k)算法2 4 0 185 6 3910 13 7 91015 14 12 112 4 0 15 8 3 610 13 7 914 15 11 122 0 4 15 3 8 610 7 13 914 11 15 120 2 1 45 3 8 67 10 9 1214 11 15 130 1 2 45 8 3 67 9 10 1214 15 11 130 1 2 48 5 6 38 9 10 1215 14 13 11子数组分别有序偶行交换行逆混洗M(j,2)行混洗偶行交换偶奇交换370 1 2 37 6 548 9 10 1115 14 13 12Snakelike Row-major indexing网格形连接用O(n)传送和比较步完成n2元素排序串行执行：O(n*log2n)加速比O(log2n)38