《并行处理机》PPT课件.ppt

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

1、第第 8 8 章章 并行处理机并行处理机8.1 并行处理（并行处理（SIMD）机原理）机原理8.2 并行处理机算法并行处理机算法 8.3 并行处理机举例并行处理机举例 并行处理机是通过重复设置大量相同的处理单元并行处理机是通过重复设置大量相同的处理单元PEPE（Processing ElementProcessing Element），将它们按一定的方式互连，在统），将它们按一定的方式互连，在统一的控制部件一的控制部件CUCU（Control UnitControl Unit）控制下，对各自分配来的不）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。它依靠操作一级同数据并行地完

2、成同一条指令所规定的操作。它依靠操作一级的并行处理来提高系统的速度。的并行处理来提高系统的速度。并行处理机的控制部件中进行的是单指令流，因此与高并行处理机的控制部件中进行的是单指令流，因此与高性能单处理机一样，指令基本上是串行执行，最多加上使用性能单处理机一样，指令基本上是串行执行，最多加上使用指令重叠或流水线的方式工作。指令重叠或流水线的方式工作。指令重叠是将指令分成两类，把只适合串行处理的控制指令重叠是将指令分成两类，把只适合串行处理的控制和标量类指令留给控制部件自己执行，而把适合于并行处理和标量类指令留给控制部件自己执行，而把适合于并行处理的向量类指令播送到所有处理单元，控制让处于活跃的

3、那些的向量类指令播送到所有处理单元，控制让处于活跃的那些处理单元去并行执行。因此这是一种标量控制类指令和向量处理单元去并行执行。因此这是一种标量控制类指令和向量类指令的重叠执行。类指令的重叠执行。8.1.1 并行处理机的原理和基本构成并行处理机的原理和基本构成并行处理机分类并行处理机分类 并并行行处处理理机机根根据据存存贮贮器器采采用用的的组组成成方方式式不不同同分分成成两两种种基基本本构成。构成。（1）分布存贮的并行处理机）分布存贮的并行处理机 各个处理单元设有局部存贮器存放分布式数据，只能被各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器

4、本处理单元直接访问。此种局部存贮器称为处理单元存贮器（Processing Element Memory）PEM。在控制部件。在控制部件CU内设内设有一个用来存放程序的主存贮器有一个用来存放程序的主存贮器CUM。整个系统在。整个系统在CU统一统一控制下运行系统程序的用户程序。执行主存中的用户程序指控制下运行系统程序的用户程序。执行主存中的用户程序指令播送给各个令播送给各个PE，控制，控制PE并行地执行。并行地执行。（2）共享存贮的并行处理机。）共享存贮的并行处理机。每每个个PE没没有有局局部部存存触触器器，存存储储模模块块以以集集中中形形式式为为所所有有PE共共享享。互互连连网网IN受受CU控

5、控制制，具具有有双双向向性性采采用用分分布布式式存存贮贮器组成基本结构。器组成基本结构。ICNICNPEPE0 0PEPE1 1PEN-PEN-1 1MM0MM0MM1MM1MMN-1MMN-1CUCUSCSCI/O-CHI/O-CHI/I/O OS SM MPEM0PEM0PE0PE0PEM1PEM1PE1PE1PEMN-PEMN-1 1PEMN-PEMN-1 1ICNICNCUCUCUMCUMI/OI/O接接口口D DSCSC（A A）具有共享存贮器并行处理机结构）具有共享存贮器并行处理机结构（B B）分布存贮器并行处理机结构）分布存贮器并行处理机结构共享共享-分布存储器分布存储器 并行处

6、理机的特点并行处理机的特点 并并行行处处理理机机的的单单指指令令流流多多数数据据流流处处理理方方式式和和由由它它产产生生的的特特殊殊结结构构是是以以诸诸如如有有限限差差分分、矩矩阵阵、信信号号处处理理、线线性性规规划划等等一一系系列列计计算算问问题题为为背背景景发发展展起起来来的的。这这些些计计算算问问题题的的共共同同特特点点是是可可以以通通过过各各种种途途径径把把它它们们转转化化成成为为对对数数组组或或向向量量的的处处理理，而而并并行行处处理理机机正正好好利利用用多多个个处处理理单单元元对对向向量量或或数数组组所包含的各个分量同时计算，所包含的各个分量同时计算，从而获得很高的处理速度。从而获

7、得很高的处理速度。并行并行VS流水流水，资源重复，资源重复，Vs 时间重叠；时间重叠；同时性，同时性，VS 并发性并发性;其设备利用率却可能没有多个单功能流水线部件那样高。其设备利用率却可能没有多个单功能流水线部件那样高。只只有有在在硬硬件件价价格格有有了了大大幅幅度度下下降降及及系系统统结结构构有有了了较较大大改改进进的的情情况况下下，并并行行处处理理机机才能具有较好的性能价格比。才能具有较好的性能价格比。第 6 章 并行处理机和相联处理机 第第 8 8 章章 并行处理机并行处理机8.1 并行处理（并行处理（SIMD）机原理）机原理8.2 并行处理机算法并行处理机算法 8.3 并行处理机举例

8、并行处理机举例 处理单元阵列处理单元阵列 由由6464个个PUPUi i构成构成,每个每个PuPui i包括包括(PEPEi i和和PEMPEMi i)由由6464个结构完全相同的处理单元个结构完全相同的处理单元PEPEi i 构成，每个处理单元构成，每个处理单元P PE Ei i字长字长6464位，位，PEMPEMi i为隶属于为隶属于PEPEi i的局部存储器，每个存储器有的局部存储器，每个存储器有2K2K字，全部字，全部PEPEi i由由CUCU统一管理，统一管理，PEPEi i都有一根方式位线，用来向都有一根方式位线，用来向CUCU传送每个传送每个PEPEi i的方式寄存器的方式寄存器

9、D D中的方式位，使中的方式位，使CUCU能了解各能了解各PEiPEi的的状态是否活动，作为控制它们工作的依据。状态是否活动，作为控制它们工作的依据。阵列控制器阵列控制器 CU CU 相当一台小型控制计算机相当一台小型控制计算机 对处理单元阵列实现控制对处理单元阵列实现控制,(,(发控制信号发控制信号,广播公共地址广播公共地址,广播公共数据广播公共数据)对指令流进行译码控制对指令流进行译码控制,利用利用CUCU内部资源可以进内部资源可以进行标量操作行标量操作,接受和处理各类中断，其他输入输出操作。接受和处理各类中断，其他输入输出操作。I/OI/O系统系统 由磁盘文件系统由磁盘文件系统DFSDF

10、S，输入输出子系统和宿主计算机输入输出子系统和宿主计算机S/CS/C构成（驻留操作系统，编译程序，构成（驻留操作系统，编译程序，I/OI/O服务程序等）服务程序等）8.2.1 并行处理机的算法并行处理机的算法 8.2.1 并行处理机的算法并行处理机的算法 ILLIAC 的处理单元阵列结构的处理单元阵列结构 图图 8.2 ILLIAC 处理单元的互连结构处理单元的互连结构 PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0PU1PU7PU56PU57PU58在在阵阵列列处处理理机机上上，解解决决矩矩阵阵加加法法是是最最简简单单的的一一维

11、维情情形形。若若有有两两个个 88 的的矩矩阵阵A、B相相加加，所所得得结结果果矩矩阵阵C也也是是一一个个 88的的矩矩阵阵。只只需需把把A、B居居于于相相应应位位置置的的分分量量存存放放在在同同一一个个PEM内内，且且在在全全部部 64个个PEM中中，令令A的的分分量量均均为为同同一一地地址址，B的的分分量量单单元元均均为为同同一一地地址址+1，而而结结果果矩矩阵阵C的的各各个个结结果果分分量量也也相相应应存存放放于于各各PEM同同一一地地址址+2的的单单元元内内，如如图图 6.4 所所示示。这这样样，只只需需用用下下列列3条条ILLIAC 的的汇汇编编指指令令就就可可以以一一次次实实现现矩

12、矩阵阵相相加：加：SIMD处理机的算法举例处理机的算法举例-矩阵加法矩阵加法LDA ALPHA ;全部全部()由由PEMi送送PEi的累加器的累加器RGAiADRN ALPHA+1 ;全部全部(+1)与与(RGAi)进行浮点进行浮点 加，加，结果送结果送RGAiSTA ALPHA+2 ;全部全部(RGAi)由由PEi送送PEMi的的+2单元单元这里，这里，0i63。SIMD处理机的算法举例处理机的算法举例-矩阵乘矩阵乘 由由于于矩矩阵阵乘乘是是二二维维数数组组运运算算，故故它它比比循循环环加加要要复复杂杂一一些些。设设A、B和和C为为3个个 88 的的二二维维矩矩阵阵。若若给给定定A和和B，则

13、则为为计计算算C=A*B的的 64 个分量，可用下列公式个分量，可用下列公式 其中，其中，0i7 且且 0j7。在在SISD计算机上求解这个问题，计算机上求解这个问题，可执行用可执行用FORTRAN语言编写的下列语言编写的下列程序程序 DO 10 I=0,7 DO 10 J=0,7 C(I,J)=0 DO 10 K=0,710 C(I,J)=C(I,J)+A(I,K)*B(K,J)SIMD处理机的算法举例处理机的算法举例-矩阵乘矩阵乘需要经过需要经过I、J、K三重循环完成。每重循环执行三重循环完成。每重循环执行 8 次，总共需要次，总共需要512次乘、加的时间，次乘、加的时间，此外每次还应包括

14、执行循环控制、此外每次还应包括执行循环控制、判别等其他操作需花费的时间。判别等其他操作需花费的时间。以以 消消 去去 J循循 环环 为为 例例，可可 执执 行行 用用FORTRAN语言编写的程序语言编写的程序 DO 10 I=0,7 C(I,J)=0DO 10 K=0,710 C(I,J)=C(I,J)+A(I,K)*B(K,J)SIMD处理机的算法举例处理机的算法举例-矩阵乘矩阵乘如果在如果在SIMD阵列处理机上运算，则可用阵列处理机上运算，则可用 8 个处理单元并行计算矩阵个处理单元并行计算矩阵C(I，J)的某的某一行或某一列，即将一行或某一列，即将J循环或循环或I循环转化成一维的向量处理

15、，消去了一重循环。循环转化成一维的向量处理，消去了一重循环。图 矩阵乘程序执行流程图第 6 章 并行处理机和相联处理机 第第 8 8 章章 并行处理机并行处理机8.1 并行处理（并行处理（SIMD）机原理）机原理8.2 并行处理机算法并行处理机算法 8.3 并行处理机举例并行处理机举例 8.3 并行处理机举例并行处理机举例8.3.1 ILLIAC 阵列处理机阵列处理机 图 ILLIAC 的组成 8.3.1 ILLIAC 阵列处理机阵列处理机-单元互联单元互联 PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0PU1PU7PU56PU5

16、7PU58 PE的的字字长长为为64 位位，内内部部主主要要包包括括 4 个个64 位位的的寄寄存存器器，它它们们是是累累加加器器 A、操作数寄存器操作数寄存器B、数据路由寄存器数据路由寄存器R、通用存贮寄存器通用存贮寄存器S。其其运运算算部部分分有有一一个个加加法法/乘乘法法器器、逻逻辑辑部部件件以以及及分分别别用用于于算算术术、布布尔尔和和移位操作的桶形开关。移位操作的桶形开关。另另有有一一个个16位位的的变变址址寄寄存存器器X，一一个个8位位的的用用于于存存放放测测试试结结果果和和PE屏屏蔽蔽标志的方式寄存器，一个形成访存地址的地址加法器。标志的方式寄存器，一个形成访存地址的地址加法器。

17、8.3.1 ILLIAC 阵列处理机阵列处理机 在在PE中能进行中能进行64或或32位浮点运算、位浮点运算、48或或24位定点运算、位定点运算、8位字符处理、位字符处理、64位逻辑运算等。位逻辑运算等。所有所有PE都按都按CU播送来的指令工作，播送来的指令工作，但可通过屏蔽标志来确定本但可通过屏蔽标志来确定本PE是否是否活跃，即是否执行该指令。活跃，即是否执行该指令。PEMi是是依附于依附于PEi的局部存贮器，容量为的局部存贮器，容量为2 K字。字。并并行行读读写写磁磁盘盘用用作作后后援援存存贮贮器器，容容量量为为109 位位。传传送送控控制制器器将将数数据据从从磁磁盘取到盘取到PEM时，按时

18、，按CU来的要求向来的要求向B6500 发中断请求。发中断请求。缓缓冲冲I/O存存贮贮器器用用作作B6500的的缓缓冲冲。I/O接接口口用用作作处处理理单单元元阵阵列列与与I/O子子系系统统及及磁磁盘盘间间的的数数据据通通路路转转接接和和缓缓冲冲。PEM中中的的指指令令或或数数据据经经CU总总线线送送往往CU，每次可送每次可送 8 个字，即个字，即 512 位。位。8.3.1 ILLIAC 阵列处理机阵列处理机 CU经经 64 位的公共数据总线向所位的公共数据总线向所有有PE播送公用信息，经指令控制线播送公用信息，经指令控制线向所有向所有PE发送控制命令。方式位线发送控制命令。方式位线共共 6

19、4 根，每个根，每个PEi有一根，用来向有一根，用来向CU传送该传送该PEi的方式寄存器中的方的方式寄存器中的方式位。式位。8.3.2 BSP科学处理机科学处理机 图 BSP的5 级数据流水线结构示意图 图 BSP科学处理机系统组成 8.3.2 BSP科学处理机科学处理机 8.3.2 BSP科学处理机科学处理机 （1）并并行行处处理理机机：并并行行机机中中每每个个处处理理器器以以160ns的的时时钟钟周周期期进进行行向向量量计计算算。所所有有16个个算算术术单单元元AE对对不不同同的的数数据据组组（从从并并行行处处理理机机控控制制器器广广播播来来）进进行行同同一一种种指指令令操操作。作。（2）

20、控控制制处处理理器器：除除了了用用以以控控制制并并行行处处理理机机以以外外，还还提提供供了了与与系系统统管管理理机机相相连连的的接口。接口。（3）文件存储器：）文件存储器：半导体辅助存储器。半导体辅助存储器。BSP的计算任务文件从系统管理机加载到的计算任务文件从系统管理机加载到它上面。然后对这些任务进行排队，由控制它上面。然后对这些任务进行排队，由控制处理机加以执行。处理机加以执行。（4）对准网络：）对准网络：完全完全交叉开关交叉开关和用来和用来实现数据从一个源广播至几个目的地以及当实现数据从一个源广播至几个目的地以及当几个源寻找一个目的地地址时能分解冲突的几个源寻找一个目的地地址时能分解冲突

21、的硬件。这就需要在算术单元阵列和存储器模硬件。这就需要在算术单元阵列和存储器模块之间具备通用的互连特性。而存储模块和块之间具备通用的互连特性。而存储模块和对准网络的组合功能则提供了并行存储器的对准网络的组合功能则提供了并行存储器的无冲突访问能力。算术单元也利用输出对准无冲突访问能力。算术单元也利用输出对准网络来实现一些诸如数据压缩和扩展操作以网络来实现一些诸如数据压缩和扩展操作以及快速傅立叶变换算法等专用功能。及快速傅立叶变换算法等专用功能。作用：作用：（1 1）由）由1717个存储器模块并行读出个存储器模块并行读出1616个操作数；个操作数；（2 2）经对准网络）经对准网络NW1NW1将将1

22、616个操作数重新排列成个操作数重新排列成1616个处理单元所需要的次序；个处理单元所需要的次序；（3 3）将排列好的）将排列好的1616个操作送到并行处理单元完成操作；个操作送到并行处理单元完成操作；（4 4）所所得得的的1616个个结结果果经经过过对对准准网网络络NW2NW2重重新新排排列列成成1717个个存存储储器器模模块块所所需需要要的次序；的次序；（5 5）写入存储器；）写入存储器；BSP的五级数据流水线的五级数据流水线 在在BSP中，存储器中，存储器-存储器型的浮点运算是流水进行的。存储器型的浮点运算是流水进行的。BSP的流水线组织由五个功能级组成。尤其是并行处理机包括的流水线组织

23、由五个功能级组成。尤其是并行处理机包括有有16个处理单元、个处理单元、17个存储器模块和个存储器模块和2套互连网络（亦称对准套互连网络（亦称对准网络）组合在一起，就形成了一条五级的数据流水线，使连续网络）组合在一起，就形成了一条五级的数据流水线，使连续几条向量指令能在时间下重叠起来执行。几条向量指令能在时间下重叠起来执行。8.3.2 BSP科学处理机科学处理机 8.3.3 MPP位平面阵列处理机位平面阵列处理机 图 MPP并行处理机原理框图 （1）位平面结构：）位平面结构：半每一半每一个处理单元只包含一位的硬设备，个处理单元只包含一位的硬设备，内部的算术逻辑运算按照位片串内部的算术逻辑运算按照

24、位片串行进行，节省了设备和通讯带宽。行进行，节省了设备和通讯带宽。（2）网络：）网络：Illiac相似的网络相似的网络互联结构。互联结构。（3）系统控制：）系统控制：整个系统的整个系统的控制任务由程序及数据管理部件控制任务由程序及数据管理部件PDMU完成。完成。8.3.4 CM连接机连接机 图 CM-5 的组成 （1）位平面结构）位平面结构。（2）网络：）网络：立方体网络，立方体网络，PE位于立方体网络的顶角上。位于立方体网络的顶角上。（3）特点：）特点：可以进行可以进行SISD,SIMD,MIMI的切换。的切换。图 二叉胖树连接 8.3.4 CM连接机连接机 （1）CM-5的改进的改进。实用胖树形的网络连接，增大根节点通讯量。实用胖树形的网络连接，增大根节点通讯量本章重点本章重点并行处理机的基本结构和特点并行处理机的基本结构和特点ILLIAC 处理单元的互连处理单元的互连阵列处理机的算法阵列处理机的算法