计算机系统结构08SIMD计算机（并行处理机）课件.ppt

《计算机系统结构08SIMD计算机（并行处理机）课件.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构08SIMD计算机（并行处理机）课件.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 并行处理机并行处理机(SIMD)8.1 并行处理机模型并行处理机模型 8.2 并行处理机结构并行处理机结构 8.3 并行处理机实例并行处理机实例 8.4 并行处理机算法举例并行处理机算法举例 18.1 并行处理机模型两种并行性概念：两种并行性概念：同时性并行同时性并行Simultaneituy:两个或两个以上两个或两个以上事件在同一时刻发生。事件在同一时刻发生。并发性并行并发性并行Concurrency：两个或两个以上两个或两个以上事件在同一时间间隔内发生。事件在同一时间间隔内发生。三条技术途径：三条技术途径：(1)资源重复：重复设置多个部件来提高速度。资源重复：重复设置多个部件

2、来提高速度。(2)时间重叠：流水线时间重叠：流水线(3)资源共享：分时系统，分布式系统。资源共享：分时系统，分布式系统。21、并行处理机的定义：、并行处理机的定义：多个处理部件多个处理部件PU按照一定方式互连，按照一定方式互连，在同一个控制部件在同一个控制部件CU控制下，对各自的数控制下，对各自的数据完成同一条指令规定的操作。从据完成同一条指令规定的操作。从CU看，看，指令是串行执行的，从指令是串行执行的，从PU看，数据是平行看，数据是平行处理的。处理的。并行处理机也称为阵列处理机，按照佛并行处理机也称为阵列处理机，按照佛林分类法，它属于林分类法，它属于SIMD处理机。处理机。2、并行处理机的

3、主要应用领域；、并行处理机的主要应用领域；用于高速向量、矩阵等运算。用于高速向量、矩阵等运算。33.并行处理机的操作模型可用五元组来表示：并行处理机的操作模型可用五元组来表示：M=(N,C,I,M,R),其中：其中：(1)N为为PE个数。如个数。如llliacIV有有64个个PE。(2)C为控制部件为控制部件CU执行的指令集，包括标量指执行的指令集，包括标量指令和程序控制指令。令和程序控制指令。(3)I为所有为所有PE并行执行的指令集，包括并行执行的指令集，包括ALU、数据传送等操作。数据传送等操作。(4)M为屏蔽操作集，将为屏蔽操作集，将PE划分为允许操作和禁止划分为允许操作和禁止操作两个子

4、集。操作两个子集。(5)R是数据寻径集，互连网络中是数据寻径集，互连网络中PE间通信所需要间通信所需要的各种模式。的各种模式。44.H.J.Siegel提出的并行处理机模型58.2 并行处理机结构8.2.1 并行处理机的基本结构并行处理机的基本结构8.2.2 分布存储器并行处理机分布存储器并行处理机8.2.3 共享存储器并行处理机共享存储器并行处理机8.2.4 并行处理机的特点并行处理机的特点68.2.1 并行处理机的基本结构一台一台并行处理机由五个部分组成：并行处理机由五个部分组成：多个处理单元多个处理单元PE，多个存储器模块多个存储器模块M，一个控制器一个控制器CU，一个互连网络一个互连网

5、络ICN，一台输入输出处理机一台输入输出处理机IOP。并行处理机有两种典型结构：并行处理机有两种典型结构：分布存储器并行处理机分布存储器并行处理机;共享存储器并行处理机。共享存储器并行处理机。78.2.2 分布存储器并行处理机分布存储器并行处理机8(1)比较容易构成比较容易构成MPP(massively Parallel Processor),可以有几十万个处理机部件可以有几十万个处理机部件PE。(2)CU是控制部件。对于标量指令，在是控制部件。对于标量指令，在CU中直接执行：中直接执行：对于向量指令，对于向量指令，CU把它广播到各个把它广播到各个PE中去执行。中去执行。(3)在在CU中通常有

6、一个较大容量的存储器，用来存放中通常有一个较大容量的存储器，用来存放程序和共享数据。程序和共享数据。(4)IOP是输入输出处理机，或称为主机。在是输入输出处理机，或称为主机。在IOP上安上安装操作系统，它除了负担输入输出工作外，还负责装操作系统，它除了负担输入输出工作外，还负责程序编辑、编译和调试等工作。程序编辑、编译和调试等工作。IOP可以是一台通可以是一台通用计算机。用计算机。(5)必须依靠并行算法来提高必须依靠并行算法来提高PE的利用率。因此，应的利用率。因此，应用领域有限，可以认为是一种专用计算机。用领域有限，可以认为是一种专用计算机。(6)数据在局部存储器中的分布是一个很关键的问题。

7、数据在局部存储器中的分布是一个很关键的问题。(7)标量指令与向量指令可以并发执行。标量指令与向量指令可以并发执行。98.2.3 共享存储器并行处理机共享存储器并行处理机10(1)共享并行存储器共享并行存储器SM通过互连网络与各处理单通过互连网络与各处理单元元PE相连。相连。(2)存储模块的数目等于或大于处理单元的数目。存储模块的数目等于或大于处理单元的数目。为了实现无冲突访问，存储模块的个数为质数。为了实现无冲突访问，存储模块的个数为质数。(3)在存储模块之间合理分配数据，通过灵活、在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的高速的互连网络，使存储器与处理单元

8、之间的数据传送在大多数向量运算中能以存储器的最数据传送在大多数向量运算中能以存储器的最高频率进行，而最少受存储器冲突的影响。高频率进行，而最少受存储器冲突的影响。(4)处理单元数目一般不多，几个至几十个。处理单元数目一般不多，几个至几十个。(5)Burroughs Scientific Processor(BSP)采用这种采用这种结构。结构。16个个PE通过一个通过一个16*17的对准互连网络的对准互连网络访问访问17个共享存储模块。个共享存储模块。(6)对互连网络的要求很高。对互连网络的要求很高。118.2.4 并行处理机的特点 并行处理机的主要特点如下：并行处理机的主要特点如下：(1)速度

9、快，速度快，而且潜力大而且潜力大(2)模块性好模块性好，生产和维护方便，生产和维护方便(3)可靠性高可靠性高，容易实现容错和重构，容易实现容错和重构(4)效率低。效率低。与流水线处理机，向量处理机等比与流水线处理机，向量处理机等比较。依靠是资源重复，而不是时间重叠，较。依靠是资源重复，而不是时间重叠，所以其效率要低一些。所以其效率要低一些。12(5)潜力大潜力大 主要依靠增加主要依靠增加PE个数，与流水线处理机主个数，与流水线处理机主要依靠缩短时钟相比，其提高速度的潜力要大要依靠缩短时钟相比，其提高速度的潜力要大得多。得多。(6)依赖于互连网络和并行算法依赖于互连网络和并行算法 互连网络决定了

10、互连网络决定了PE之间的连接模式，也之间的连接模式，也决定了并行处理机能够适应的算法。决定了并行处理机能够适应的算法。(7)需要有一台高性能的标量处理机需要有一台高性能的标量处理机 如果一台机器的向量处理速度极高，但标如果一台机器的向量处理速度极高，但标量处理速度只是每秒一百万次，那么对于标量量处理速度只是每秒一百万次，那么对于标量运算占运算占10%的题目来说，总的有效速度就不过的题目来说，总的有效速度就不过每秒一千万次。每秒一千万次。138.3 并行处理机实例 llliaclV是采用是采用SIMD结构的并行处理机。结构的并行处理机。随后一个方向是位片随后一个方向是位片PE制造的并行处理机，制

11、造的并行处理机，如如Goodyear MPP、AMT/DAP610和和TMC/CM-2、CM-5是以是以SIMD模式运行同步模式运行同步MMID计算机。计算机。另一方向是字宽运算另一方向是字宽运算PE的中粒度的中粒度SIMD计算机计算机并行处理机的两个基发展方向：并行处理机的两个基发展方向：(1)保留阵列结构，但每个处理单元的规模减小，保留阵列结构，但每个处理单元的规模减小，如一个如一个bit.(2)去掉阵列结构和分布存储器。去掉阵列结构和分布存储器。Burroughs公司公司的的BSP处理机是典型代表。处理机是典型代表。148.3.1 lllialv并行处理机(1)1963年，美国西屋电器公

12、司提出年，美国西屋电器公司提出“Slotnick,The SOLOMON Compuer,Simultaneous Operation linked Ordinal Modular Network”.(2)1966年美国国防远景研究规划局年美国国防远景研究规划局ARPR与伊利诺与伊利诺依依大学签定合同。原计划：大学签定合同。原计划：256PE，运算速度为运算速度为1GFLOPS。(3)Burroughs公司和伊利诺依大学于公司和伊利诺依大学于1972年共同设年共同设计和生产，计和生产，1975年实际投入运行。用了年实际投入运行。用了4倍的经倍的经费，只达到费，只达到1/20的速度。只实现了的速

13、度。只实现了8*8=64个个PE，只达到只达到50MFLOPS。(3)llliaclv的影响非常大。它是并行处理机的典的影响非常大。它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表。型代表，也是分布存储器并行处理机的典型代表。15llliaclV由三大部分组成llliaclV处理机阵列：包括88PE、PEM和互连网络。阵列控制CU输入输出处理机：一台标准的Burroughs B6700计算机161.阵列控制器阵列控制器 阵列控制器阵列控制器CU实际是一台小型计算机。实际是一台小型计算机。对阵列处理机单元实行控制和完成标量操作。对阵列处理机单元实行控制和完成标量操作。标量操作与各标量

14、操作与各PE的数组操作可以重叠执行。的数组操作可以重叠执行。控制器的功能有以下五个方面：控制器的功能有以下五个方面：(1)对指令进行译码，并对指令进行译码，并执行执行标量指令；标量指令；(2)向各向各PE发出执行数组操作指令的发出执行数组操作指令的控制信号控制信号；(3)产生地址产生地址,并向所有处理单元广播并向所有处理单元广播公共地址公共地址；(4)产生数据产生数据,并向所有处理单元广播并向所有处理单元广播公共数据公共数据；(5)接收和处理接收和处理PE、I/O操作以及操作以及B6700产生的陷产生的陷阱中断信号。阱中断信号。172、输入输出系统、输入输出系统 llliaclv的输入输出的系

15、统包括：的输入输出的系统包括：磁盘文件系统磁盘文件系统DFS，I/O分系统，分系统，一台一台B6700 处理机组成。处理机组成。I/O分系统由三部分组成：分系统由三部分组成：输入输出开关输入输出开关IOS 控制描述字控制器控制描述字控制器CDC，输入输出缓冲存储器输入输出缓冲存储器BIOM。183.llliaclV处理阵列处理阵列(1)llliaclV处理机阵列由处理机阵列由8*8=64个组成。每个组成。每个个PU由处理部件由处理部件PE和它的局部存储器和它的局部存储器PEM组成。组成。(2)每一个每一个 只和它东、西、南、北四个近邻只和它东、西、南、北四个近邻:mod 64、mod 64、m

16、od 64、mod 64直接连接。直接连接。(3)南北方向同一列南北方向同一列PU连成一个环，东西方向连成一个环，东西方向构成一个闭合螺线。构成一个闭合螺线。(4)闭合螺线网络直径为闭合螺线网络直径为7步，环形网络的直径步，环形网络的直径为为8步。步。1920例如：从 到 ，采用环形网络必须第8步；或 或如果采用闭合螺线，只需要7步：或或.对于NN个单元的阵列，网络直径为N-1。218.3.2 BSP处理机(1)BSP(Buroughs Scientific Processor)计算机是计算机是由美国宝来公司和伊利诺依大学研制。由美国宝来公司和伊利诺依大学研制。(2)BSP是共享存储器并行处理

17、机的典型代表。处是共享存储器并行处理机的典型代表。处理机与共享存储器之间采用理机与共享存储器之间采用全交叉开关全交叉开关连接，连接，不仅可以同时实现任结点之间的互连，还能实不仅可以同时实现任结点之间的互连，还能实现广播和多播。现广播和多播。(3)BSP由由5个部分组成：个部分组成：控制处理机、并行处理机、文件存储器、控制处理机、并行处理机、文件存储器、并行存储器模块、对准网络。并行存储器模块、对准网络。22231.并行处理机并行处理机 5级流水线：级流水线：(1)从从17个并行存储器中读出数据。个并行存储器中读出数据。(2)通过输入对准网络把通过输入对准网络把17个并行存储器中个并行存储器中读

18、出的数据送入读出的数据送入16个并行处理部件。个并行处理部件。(3)16个并行处理部件并行处理机数据。个并行处理部件并行处理机数据。(4)通过输出对准网络把数据从通过输出对准网络把数据从16个并行处个并行处理部件送到理部件送到17个并行存储器。个并行存储器。(5)把接收到的数据写入并行存储器。把接收到的数据写入并行存储器。时钟周期时钟周期160ns，向量运算速度向量运算速度50MFlops。242.控制处理机控制处理机(1)控制并行处理机工作。控制并行处理机工作。(2)执行存放在控制存储器中的操作系统和用户执行存放在控制存储器中的操作系统和用户程序中标量部分。程序中标量部分。(3)控制控制17

19、个并行存储器工作。个并行存储器工作。(4)把全部的向量指令及组成的标量指令给出并把全部的向量指令及组成的标量指令给出并行处理机。行处理机。(5)控制维护单元是系统管理机与控制之间的接控制维护单元是系统管理机与控制之间的接口，用来进行初始化，监控命令通信和维护。口，用来进行初始化，监控命令通信和维护。(6)提供与系统管理机相连的接口。提供与系统管理机相连的接口。253.文件存储器文件存储器(1)计算任务文件从系统管理机家载到文计算任务文件从系统管理机家载到文件存储器，由控制处理机执行。件存储器，由控制处理机执行。(2)文件存储器是在文件存储器是在BSP直接控制下的唯一直接控制下的唯一外围设备。外

20、围设备。(3)程序执行过程中所产生的暂存文件和输程序执行过程中所产生的暂存文件和输出文件，在将它们送给系统管理机输出出文件，在将它们送给系统管理机输出给用户之前是存在文件存储器中的。给用户之前是存在文件存储器中的。(4)文件存储器的数据传输率较高，大大地文件存储器的数据传输率较高，大大地缓解了缓解了I/O受限制问题。受限制问题。264.对准网络对准网络(1)对准网络采用全交叉开关实现。对准网络采用全交叉开关实现。(2)数据从一个源广播至几个目的地，几个数据从一个源广播至几个目的地，几个源寻找一个目的地时能分解冲突。源寻找一个目的地时能分解冲突。(3)存储器模块和对准网络的组合实现了无存储器模块

21、和对准网络的组合实现了无冲突访问并行存储器。冲突访问并行存储器。(4)对准网络还可以实现快速富里叶变换，对准网络还可以实现快速富里叶变换，数据压缩和扩展操作。数据压缩和扩展操作。275.无访问冲突存储系统无访问冲突存储系统(1)17个存储模块，每个模块个存储模块，每个模块512K字，周期字，周期160ns，等效存储周期为等效存储周期为10ns.(2)只有数组存取和只有数组存取和I/O访问并行存储器。访问并行存储器。(3)实现一维向量和二维矩阵的行、列、对角线实现一维向量和二维矩阵的行、列、对角线和反对角线的无冲突访问和反对角线的无冲突访问(具体方法见第三章）具体方法见第三章）(4)对于三元向量

22、，两次算术运算中需要用到三对于三元向量，两次算术运算中需要用到三个变量，产生一个结果，共访问存储器个变量，产生一个结果，共访问存储器4次，次，并行存储器和浮点运算之间的频带保持完全平并行存储器和浮点运算之间的频带保持完全平衡。衡。(5)对于长向量来，中间结果存在寄存器中，每对于长向量来，中间结果存在寄存器中，每次运算只需一个操作数。因此并行存储器有足次运算只需一个操作数。因此并行存储器有足够的频宽给输入和输出信息用。够的频宽给输入和输出信息用。288.4 并行处理机算法举例(1)并行处理机特别依赖于并行算法。并行处理机特别依赖于并行算法。(2)并行算法的一个关键是提高向量化的程度。并行算法的一

23、个关键是提高向量化的程度。(3)在设计并行算法时，要特别注意：数据在多在设计并行算法时，要特别注意：数据在多个存储模块之间分布。要解决好访问存储器的个存储模块之间分布。要解决好访问存储器的冲突问题。冲突问题。(4)通常，互连网络并不能提供所有处理单元之通常，互连网络并不能提供所有处理单元之间的直接连接，因此并行算法要充分利用互连间的直接连接，因此并行算法要充分利用互连网络的结构，尽量缩短传输延时时间。网络的结构，尽量缩短传输延时时间。298.4 并行处理机算法举例8.4.1 有限差分问题有限差分问题8.4.2 矩阵乘矩阵乘8.4.3 求累加和求累加和308.4.1 有限差分问题有限差分方法是一

24、种通用和有效方法：把连续方程变换成离散形式。把二阶偏导数表示为差分形式：代入原方程，则可得有限差分公式：31其中:(x,y)为平面直角坐标.h为网络间距。llliaclV的矩阵结构特别适合计算这种网格上定义的有限差分函数。把内部网格点分配给各个处理单元，计算过程可以并行完成。加速比可以与处理机数目成正比。328.4.2 矩阵乘 矩阵乘是典型的并行程序，非常适合在矩阵乘是典型的并行程序，非常适合在SIMD并行处理机上运行。并行处理机上运行。例如：例如：A、B、C均为均为8*8的二维矩阵，则的二维矩阵，则C=A*B的计算公式：的计算公式：在串行机上要用一个三重循环程序，乘法在串行机上要用一个三重循

25、环程序，乘法和加法分别做和加法分别做512次。次。如果用如果用8个个PE并行工作，乘法和加法分别并行工作，乘法和加法分别为为64次。次。如果用如果用64个个PE并行工作，乘法和加法分别并行工作，乘法和加法分别做做8次。次。33 如果在如果在8个个PE的并行处理机上求解，的并行处理机上求解，FORTRAN语言程序如下：语言程序如下：DO 10 I=0,7 C(I,J)=0 DO 20 K=0,7 20 C(I,J)=C(I,J)+A(I,K)*B(K,J)10 COUTIUE 在在8个个PE的并行处理机运行，运算速度可的并行处理机运行，运算速度可提高提高8倍。也可在倍。也可在64个个PE的并行处

26、理机上运行。的并行处理机上运行。数据如何分布到各个局部存储器中？数据如何分布到各个局部存储器中？34在并行处理机上，在并行处理机上，J循环只需一次。循环只需一次。PE0：c00a00b00a01b10a02b20a07b70 PE1：c01a00b01a01b11a02b21a07b71 PE7：c07a00b07a01b17a02b27a07b77 PE0：c10a10b00a11b10a12b20a17b70 PE1：c11a10b01a11b11a12b21a17b71 PE7：c17a10b07a11b17a12b27a17b77 PE7：c77a70b07a71b17a72b27a7

27、7b773536378.4.3 求累加和 把把N个数的顺序相加变为并行相加。个数的顺序相加变为并行相加。串行求和的串行求和的FORTRAN程序如下：程序如下：C(-1)=0 DO 10 I=0,N 10 C(I)=C(I-1)+A(I)在并行处理机上，采用递归加法，在并行处理机上，采用递归加法，FORTRAN程序如下：程序如下：DO 10 I=0,Log2N-1 10 A=A+SRL(A,2*I);A向量右移向量右移2个个PE 在并行处理机上只需做在并行处理机上只需做log2N次加法。次加法。38在在并行处理机上求累加和的步骤：并行处理机上求累加和的步骤：第第1步：把各步：把各PE读读A(I)

28、到到RGA中；中；第第2步：步：k=0;第第3步：各步：各PE的的(RGA)转送到转送到RGR；第第4步：各步：各PE的的(RGA)经过互连网络向右转送经过互连网络向右转送2K步距步距第第5步：各步：各PE执行执行(RGA)=(RGA)+(RGR)操作；操作；第第6步：步：K:=K+1第第7步：若步：若K3，则转回第则转回第3步，否则继续往下执行；步，否则继续往下执行；第第8步：各步：各PE的的(RGA)存入局部存储器。存入局部存储器。39在在并行处理机上求累加和的计算过程。并行处理机上求累加和的计算过程。40求求递归和算法的性能分析：递归和算法的性能分析：(1)运算速度提高：加速比为运算速度

29、提高：加速比为N/log2N倍倍(2)运算次数增加：从运算次数增加：从N次增加到次增加到Nlog2N次。次。(3)效率降低：实际效率为效率降低：实际效率为1/log2N如：如：N=1024，速度提高速度提高100倍，运算次数增加倍，运算次数增加10倍，效率只有倍，效率只有1/10。如果。如果N=220 即即100万个数求和，速度可以提高万个数求和，速度可以提高5万倍。万倍。(4)这种方法也称为级联求和，或递归求和。这种方法也称为级联求和，或递归求和。(5)与流水线中采用的方法类似，它利用加法结与流水线中采用的方法类似，它利用加法结合律来提高并行度。合律来提高并行度。41第八章第八章 复习复习本章重点：本章重点：1.1.并行处理的基本结构并行处理的基本结构2.2.并行处理的特点并行处理的特点3.3.典型的并行处理机算法典型的并行处理机算法练习题练习题:8.3 8.68.3 8.6（改为：（改为：n n个个PEPE）8.128.1242