计算机系统机构ppt第8章课件.ppt

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

1、第第8章章 并行处理机并行处理机8.1 并行处理机模型并行处理机模型8.2 并行处理机结构并行处理机结构8.3 并行处理机实例并行处理机实例8.4 并行处理机算法举例并行处理机算法举例1/7/20231计算机系统结构 第八章 并行处理机两种并行性概念：两种并行性概念：(1)同时性并行Simultaneity：两个或两个以上事件在同一时刻发生。(2)并发性并行Concurrency：两个或两个以上事件在同一时间间隔内发生。三条技术途径：三条技术途径：(1)资源重复：重复设置多个部件来提高速度。(2)时间重叠：流水线(3)资源共享：分时系统，分布式系统8.1 并行处理机模型并行处理机模型1/7/2

2、0232计算机系统结构 第八章 并行处理机1.并行处理机的定义：并行处理机的定义：多个处理部件多个处理部件PU按照一定方式互连，在同按照一定方式互连，在同一个控制部件一个控制部件CU控制下，对各自的数据完成控制下，对各自的数据完成同一条指令规定的操作。从同一条指令规定的操作。从CU看，指令是串看，指令是串行执行的，从行执行的，从PU看，数据是并行处理的。看，数据是并行处理的。并行处理机也称为阵列处理机，按照按照佛林分类法，它属于SIMD处理机。2.并行处理机的主要应用领域：并行处理机的主要应用领域：用于高速向量或矩阵运算。1/7/20233计算机系统结构 第八章 并行处理机3.并行处理机的操作

3、模型可用五元组来表示：并行处理机的操作模型可用五元组来表示：M(N，C，I，M，R),其中：N为为PE个数个数。如IlliacIV有64个PE。C为控制部件为控制部件CU执行的指令集执行的指令集，包括标量指令和程序控制指令。I为所有为所有PE并行执行的指令集并行执行的指令集，包括ALU、数据传送等操作M为屏蔽操作集为屏蔽操作集，将PE划分为允许操作和禁止操作两个子集R是数据寻径集是数据寻径集，互连网络中PE间通信所需要的各种模式1/7/20234计算机系统结构 第八章 并行处理机4.H.J.Siegel提出的并行处理机模型提出的并行处理机模型 1/7/20235计算机系统结构 第八章 并行处理

4、机8.2 并行处理机结构并行处理机结构8.2.1 并行处理机的基本结构并行处理机的基本结构8.2.2 分布存储器并行处理机分布存储器并行处理机8.2.3 共享存储器并行处理机共享存储器并行处理机8.2.4 并行处理机的特点并行处理机的特点1/7/20236计算机系统结构 第八章 并行处理机8.2.1 并行处理机的基本结构并行处理机的基本结构一台并行处理机由五个部分组成：一台并行处理机由五个部分组成：多个处理单元多个处理单元PEPE，多个存储器模块多个存储器模块M M，一个控制器一个控制器CUCU，一个互连网络一个互连网络ICNICN，一台输入输出处理机一台输入输出处理机IOPIOP。并行处理机

5、有两种典型结构：并行处理机有两种典型结构：分布存储器并行处理机，分布存储器并行处理机，共享存储器并行处理机。共享存储器并行处理机。1/7/20237计算机系统结构 第八章 并行处理机8.2.2 分布存储器并行处理机分布存储器并行处理机目前的大部分并行处理机属于基于分布式存储器模型。分布式存储器并行处理机比较容易构成MPP(Massively Parallel Processor)，可以有几十万个处理部件PE。CU是控制部件。对于标量指令，在CU中直接执行；对于向量指令，CU把它广播到各个PE中去执行。在CU中通常有一个较大容量的存储器，用来存放程序和共享数据。1/7/20238计算机系统结构

6、第八章 并行处理机IOP是输入输出处理机，或称为主机。在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作。IOP可以是一台通用计算机。分布式存储器并行处理机必须依靠并行算法来提高PE的利用率。因此，应用领域有限，可以认为是一种专用计算机。数据在局部存储器中的分布是一个很关键的问题。标量指令与向量指令可以并发执行。1/7/20239计算机系统结构 第八章 并行处理机 分布式存储器并行处理机的结构框图分布式存储器并行处理机的结构框图1/7/202310计算机系统结构 第八章 并行处理机8.2.3 共享存储器并行处理机共享存储器并行处理机共享多体并行存储器SM通过互

7、连网络与各处理单元PE相连。存储模块的数目等于或略大于处理单元的数目。为了实现无冲突访问，存储模块的个数为质数。在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储器冲突的影响。1/7/202311计算机系统结构 第八章 并行处理机共享存储器模型的处理单元数目一般不多，几个至几十个。Burroughs Scientific Processor(BSP)采用了这种结构。16个PE通过一个1617的对准互连网络访问17个共享存储器模块。存储器模块数与PE数互质可以实现无冲突并行访问存储器。对互连网络的要求很

8、高。1/7/202312计算机系统结构 第八章 并行处理机 共享存储器并行处理机的结构框图共享存储器并行处理机的结构框图1/7/202313计算机系统结构 第八章 并行处理机8.2.4 并行处理机的特点并行处理机的特点 并行处理机的主要特点如下：并行处理机的主要特点如下：1.速度快，而且潜力大速度快，而且潜力大2.模块性好，生产和维护方便模块性好，生产和维护方便3.可靠性高，容易实现容错和重构可靠性高，容易实现容错和重构4.效率低效率低与流水线处理机、向量处理机等比较。依靠的是资源重复，而不是时间重叠，它的每个处理单元要担负多种处理功能，其效率要低一些。1/7/202314计算机系统结构 第八

9、章 并行处理机5.潜力大潜力大 主要依靠增加PE个数，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。6.依赖于互连网络和并行算法依赖于互连网络和并行算法 互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。7.需要有一台高性能的标量处理机需要有一台高性能的标量处理机 如果一台机器的向量处理速度极高，但标量处理速度只是每秒一百万次，那么对于标量运算占10的题目来说，总的有效速度就不过是每秒一千万次。1/7/202315计算机系统结构 第八章 并行处理机8.3 并行处理机实例并行处理机实例IlliacIV 是最先采用SIMD结构的并行处理机。随后一个方向是用位片

10、PE制造的并行处理机，如Goodyear MPP、AMT/DAP610和TMC/CM-2CM-5是以SIMD模式运行的同步MIMD计算机另一方向是字宽运算PE的中粒度SIMD计算机并行处理机的两个发展方向：保保留留阵阵列列结结构构，但但每每个个处处理理单单元元的的规规模模减减小小，如一个bit。去去掉掉阵阵列列结结构构和和分分布布存存储储器器。Burroughs公司的BSP是代表。1/7/202316计算机系统结构 第八章 并行处理机8.3.1 IlliavIV 并行处理机并行处理机1963年，美国西屋电器公司提出“Slotnick，The SOLOMON Computer，Simultane

11、ous Operation linked Ordinal Modular Network”。1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，运算速度为1GFLOPS。Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用了4倍的经费，只达到1/20的速度。只实现了8864个PE，只达到50MFLOPS。IlliacIV的影响非常大。它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表。1/7/202317计算机系统结构 第八章 并行处理机IlliacIV由三大部分组成由三大部分组成IlliacIV处理机阵列：包括

12、88 PE、PEM和互连网络。阵列控制器CU。输入输出处理机：一台标准的Burroughs B6700计算机。1/7/202318计算机系统结构 第八章 并行处理机1.阵列控制器阵列控制器阵列控制器CU实际上是一台小型计算机。对阵列处理单元实行控制和完成标量操作。对阵列处理单元实行控制和完成标量操作。标量操作与各标量操作与各PE的数组操作可以重叠执行。的数组操作可以重叠执行。控制器的功能有以下五个方面：(1)对指令进行译码，并执行标量指令；(2)向各PE发出执行数组操作指令的控制信号；(3)产生并向所有处理单元广播公共的地址；(4)产生并向所有处理单元广播公共的数据；(5)接收和处理PE、I/

13、O操作以及B6700产生的陷阱中断信号。1/7/202319计算机系统结构 第八章 并行处理机2.输入输出系统输入输出系统IlliacIV的输入输出系统包括：磁盘文件系统DFS，I/O分系统，一台B6700处理机组成。I/O分系统由三个部分组成：输入输出开关IOS，控制描述字控制器CDC，输入输出缓冲存储器BIOM。1/7/202320计算机系统结构 第八章 并行处理机3.IlliacIV处理阵列处理阵列IlliacIV处理阵列由64个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。每一个PUi只和它的东、西、南、北四个近邻：PUi+1 mod 64、PUi-1 mod 64、PU

14、i+8 mod 64、PUi-8 mod 64直接连接。南北方向同一列PU连成一个环，东西方向构成一个闭合螺线。闭合螺线网络直径为闭合螺线网络直径为7步，步，环形网格的直径为环形网格的直径为8步。步。1/7/202321计算机系统结构 第八章 并行处理机1/7/202322计算机系统结构 第八章 并行处理机例如：从PU0到PU36，采用环行网格必须8步：PUPU0 0PUPU1 1PUPU2 2PUPU3 3PUPU4 4PUPU1212PUPU2020PUPU2828PUPU3636或 PUPU0 0PUPU8 8PUPU1616PUPU2424PUPU3232PUPU3333PUPU343

15、4PUPU3535PUPU3636 或 如果采用闭合螺旋线，只需要如果采用闭合螺旋线，只需要7 7步：步：PUPU0 0PUPU6363PUPU6262PUPU6161PUPU6060PUPU5252PUPU4444PUPU3636或PUPU0 0PUPU6363PUPU5555PUPU4747PUPU3939PUPU3838PUPU3737PUPU3636 或 对于nn个单元的阵列，网络直径为n-1n-1。1/7/202323计算机系统结构 第八章 并行处理机二维闭合螺旋线网格网二维闭合螺旋线网格网 结点度为4，网络直径为n-1。1/7/202324计算机系统结构 第八章 并行处理机8.3.

16、2 BSP处理机处理机BSP（Buroughs Scientific Processor）计算机是由美国宝来公司和伊利诺依大学于1979年制造的。BSP是共享存储器并行处理机的典型代表。BSP由5个部分组成：控制处理机、并行处理机、文件存储器、并行存储器模块、对准网络。1/7/202325计算机系统结构 第八章 并行处理机1.并行处理机并行处理机17个存储模块，每个模块512K字，周期160ns5级流水线：级流水线：(1)从17个存储模块中读出数据(2)通过输出对准网络把数据送入16个并行处理部件(3)16个并行处理部件并行处理机数据(4)通过输入对准网络把数据从并行处理部件送到并行存储器(5

17、)把接收到的数据写入并行存储器时钟周期160ns，向量运算速度向量运算速度50MFLOPS。1/7/202326计算机系统结构 第八章 并行处理机1/7/202327计算机系统结构 第八章 并行处理机2.控制处理机控制处理机控制处理机主要用来控制并行处理机。控制处理机主要用来控制并行处理机。提供与系统管理机相连的接口。执执行行存存放放在在控控制制存存储储器器中中的的操操作作系系统统和和用用户户程程序的标量部分。序的标量部分。把全部的向量指令及成组的标量指令送给并行处理机。控制维护单元是系统管理机与控制处理机之间的接口，用来进行初始化、监控命令通信和维护。1/7/202328计算机系统结构 第八

18、章 并行处理机3.文件存储器文件存储器计算任务文件从系统管理机加载到文件存储器，由控制处理机执行。文件存储器是在BSP直接控制下的唯一外围设备。程序执行过程中所产生的暂存文件和输出文件，在将它们送给系统管理机输出给用户之前是存在文件存储器中的。文件存储器的数据传输率较高，大大地缓解了I/O受限问题。1/7/202329计算机系统结构 第八章 并行处理机4.对准网络对准网络对准网络采用全交叉开关实现对准网络采用全交叉开关实现。数数据据从从一一个个源源广广播播至至几几个个目目的的地地，几几个个源源寻寻找找一个目的地时能分解冲突。一个目的地时能分解冲突。存存储储器器模模块块和和对对准准网网络络的的组

19、组合合实实现现了了无无冲冲突突访访问并行存储器问并行存储器。对准网络还可以实现快速傅里叶变换、数据压缩和扩展操作。1/7/202330计算机系统结构 第八章 并行处理机5.无访问冲突存储系统无访问冲突存储系统只有数组存取和I/O访问并行存储器。等等效效存存储储周期为周期为10ns。两次算术运算中需要用到三个变量，产生一个结果，共访问存储器4次，并行存储器和浮点运算之间的频带保持完全平衡频带保持完全平衡。对于长向量来，中间结果存在寄存器中，每次运算只需要一个操作数。因此并行存储器有足够的频宽留给输入和输出信息用。实实现现一一维维向向量量和和二二维维矩矩阵阵的的行行、列列、对对角角线线和和反对角线

20、的无冲突访问。反对角线的无冲突访问。1/7/202331计算机系统结构 第八章 并行处理机8.4 并行处理机算法举例并行处理机算法举例8.4.1 有限差分问题有限差分问题8.4.2 矩阵乘矩阵乘8.4.3 求累加和求累加和1/7/202332计算机系统结构 第八章 并行处理机并行处理机特别并行处理机特别依赖于并行算法。依赖于并行算法。并行算法的一个关键是并行算法的一个关键是提高向量化的程度。提高向量化的程度。在设计并行算法时，要特别注意：在设计并行算法时，要特别注意：数据在多个存储模块之间的分布。数据在多个存储模块之间的分布。要解决好访问存储器的冲突问题。要解决好访问存储器的冲突问题。互互连连

21、网网络络并并不不能能提提供供所所有有处处理理单单元元之之间间的的连连接接，因因此此，并并行行算算法法要要充充分分利利用用互互连连网络的结构网络的结构。1/7/202333计算机系统结构 第八章 并行处理机8.4.1 有限差分问题有限差分问题有限差分方法是一种通用和有效方法：把连续方程变换成离散形式。二阶偏导数表示为差分形式：1/7/202334计算机系统结构 第八章 并行处理机并代入原方程，则可得有限差分计算公式：其中：(x,y)为平面直角坐标，h为网格间距。IlliacIV的阵列结构特别适合计算这种在网格上定义的有限差分函数。把内部网格点分配给各个处理单元，计算过程可以并行完成。运算速度的提

22、高可以与处理机数目成正比。1/7/202335计算机系统结构 第八章 并行处理机8.4.2 矩阵乘矩阵乘矩阵乘是典型的并行程序，非常适合在SIMD并行处理机上运行。例如：A、B、C均为88的二维矩阵，则CAB的计算公式为：在串行机上要用一个三重循环程序，乘法和加法分别为512次。1/7/202336计算机系统结构 第八章 并行处理机如果在并行处理机上求解，FORTRAN语言程序如下：DO 10 I0，7 C(I,J)=0 DO 20 K=0,720 C(I,J)=C(I,J)+A(I,K)*B(K,J)10 CONTINUE可以在8个PE的并行处理机运行，运算速度可提高8倍。也可在64个PE的

23、并行处理机上运行数据如何分布到各个局部存储器中？1/7/202337计算机系统结构 第八章 并行处理机在并行处理机上，J循环只需一次。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：c c0707a a0000b b0707a a0101b b1717a a0202b b2727a a0707b b7777 PE0PE0：c c1010a a1

24、010b 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 b0707a a7171b b1717a a7272b b2727a a7777b b77771/7/202338计算机系统结构 第八章 并行处理机1/7/2023

25、39计算机系统结构 第八章 并行处理机1/7/202340计算机系统结构 第八章 并行处理机8.4.3 求累加和求累加和把N个数的顺序相加变为并行相加。串行求和的 FORTRAN 程序如下：C(-1)0 DO 10 I0,N10 C(I)C(I-1)A(I)在并行处理机上，采用递归加法，FORTRAN 程序如下：DO 10 I=0，log2N110 AASRL(A,2*I);A向量右移向量右移2i个个PE在并行处理机上只需做在并行处理机上只需做 log2N 次加法。次加法。1/7/202341计算机系统结构 第八章 并行处理机1/7/202342计算机系统结构 第八章 并行处理机递归求和算法的

26、性能分析：递归求和算法的性能分析：运算速度提高运算速度提高：加速比为加速比为N/log2N倍倍运算次数增加运算次数增加：从从N次增加到次增加到Nlog2N次次效率降低效率降低：实际效率为实际效率为1/log2N如：N1024，速速度度提提高高100倍倍，运运算算次次数数增增加加10倍，效率只有倍，效率只有1/10如果N220，即100万个数求和，速度可以提高5万倍。这种方法也称为级联求和，或递归求和。与流水线中采用的方法类似，它利用加法结合律来提高并行度。1/7/202343计算机系统结构 第八章 并行处理机本章重点：本章重点：1.1.并行处理的基本结构并行处理的基本结构2.2.并行处理的特点并行处理的特点3.3.典型的并行处理机算法典型的并行处理机算法练习题练习题:8.3 8.68.3 8.6（改为：（改为：n n个个PEPE）8.12 8.121/7/202344计算机系统结构 第八章 并行处理机