基本概念指令系统及CPU组成存储系统课件
单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第一章 基本概念,第二章 指令系统及CPU组成,第三章 存储系统,第四章 输入输出系统,第五章 标量处理机,第六章 向量处理机,第七章 互连网络,第八章 并行处理机,第九章 多处理机,计算机组成与系统结构,8/15/2024,1,第一章 基本概念计算机组成与系统结构8/24/20231,第八章 并行处理机,两种并行性概念：,,同时性并行,Simultaneity,：两个或两个以上事件在同一时刻发生,并发性并行,Concurrency,：,两个或两个以上事件在同一时间间隔内发生,三条技术途径：,,资源重复,：通过重复设置多个处理部件来提高速度,时间重叠：流水线,资源共享：分时系统，分布式系统,,8.1 并行处理机模型,8.2 并行处理机的基本结构,8.3 并行处理机实例,8.4 并行处理机算法举例,8/15/2024,2,第八章 并行处理机两种并行性概念：8/24/20232,8.1 并行处理机模型,并行处理机的定义：,,多个PU按照一定方式互连，在同一个CU控制下，对各自的数据完成同一条指令规定的操作。
从CU看，指令是串行执行的，从PU看，数据是并行处理的并行处理机也称为阵列处理机、SIMD处理机等,并行处理机的应用领域：主要用于高速向量或矩阵运算,并行处理机的操作模型可用五元组来表示：,M＝(N，C，I，M，R),,其中：,N为PE个数,如IlliacIV有64个PEC为控制部件CU执行的指令集,，包括标量指令和程序控制指令I为所有PE并行执行的指令集,，包括ALU、数据传送等操作,M为屏蔽操作集,，将PE划分为允许操作和禁止操作两个子集,R是数据寻径集,，互连网络中PE间通信所需要的各种模式,8/15/2024,3,8.1 并行处理机模型并行处理机的定义：8/24/20233,8/15/2024,4,8/24/20234,8/15/2024,5,8/24/20235,8.2 并行处理机的基本结构,并行处理机有两种典型结构：,,分布存储器并行处理机、共享存储器并行处理机,一台并行处理机由五个部分组成：,,多个处理单元PE，多个存储器模块M，一个控制器CU，,一个互连网络ICN，一台输入输出处理机IOP8.2.1 分布存储器并行处理机,8.2.2 共享存储器并行处理机,8.2.3 并行处理机的特点,8/15/2024,6,8.2 并行处理机的基本结构并行处理机有两种典型结构：8/2,8.2.1 分布存储器并行处理机,目前的大部分并行处理机是基于分布式存储器模型的,比较容易构成MPP,(Massively Parallel Processor),几十万个PE。
必须依靠并行算法来提高PE的利用率因此，应用领域有限CU是控制部件，执行标量指令，并把向量指令广播到各个PE中在CU中通常有一个较大容量的存储器IOP是输入输出处理机，或称为主机在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作数据在局部存储器中的分布是一个很关键的问题标量指令与向量指令可以并发执行8/15/2024,7,8.2.1 分布存储器并行处理机8/24/20237,8/15/2024,8,8/24/20238,8.2.2 共享存储器并行处理机,共享多体并行存储器SM通过互连网络与各处理单元PE相连存储模块的数目等于或略大于处理单元的数目同时在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储器冲突的影响共享存储器模型的处理单元数目一般不多，几个至几十个Burroughs Scientific Processor(BSP)采用了这种结构16个PE通过一个16×17的对准互连网络访问17个共享存储器模块存储器模块数与PE数互质可以实现无冲突并行访问存储器8/15/2024,9,8.2.2 共享存储器并行处理机8/24/20239,8/15/2024,10,8/24/202310,8.2.3 并行处理机的特点,速度高,，依靠增加PE个数来提高速度，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。
模块性好,，生产和维护方便可靠性高,，容易实现容错和重构效率低,，,通常作为专用计算机,，在很大程度上依赖于并行算法它依靠的是资源重复，而不是时间重叠，它的每个处理单元要担负多种处理功能，其效率要低一些依赖于互连网络,互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法需要有一台高性能的标量处理机,如果一台机器的向量处理速度极高，但标量处理速度只是每秒一百万次，则对于标量运算占10％的题目，总的有效速度就不超过每秒一千万次8/15/2024,11,8.2.3 并行处理机的特点8/24/202311,8.3 并行处理机实例,IlliacIV 是最先采用SIMD结构的并行处理机随后一个方向是用位片PE制造的并行处理机，,如Goodyear MPP、AMT/DAP610和TMC/CM-2CM-5是以SIMD模式运行的同步MIMD计算机另一个方向是用字宽运算PE的中粒度SIMD计算机并行处理机的两个发展方向：,,保留阵列结构，但每个处理单元的规模减小,，如一个bit去掉阵列结构和分布存储器,Burroughs公司的BSP是代表GF-11是由IBM Watson实验室研制、作科学模拟研究用的。
MasPar MP1是中粒度并行处理机的典型代表并行处理机的两种典型代表：,采用阵列结构分布存储器的IlliacIV并行处理机,去掉阵列结构和分布存储器BSP并行处理机8/15/2024,12,8.3 并行处理机实例IlliacIV 是最先采用SIMD结,8.3.1 IlliavIV 并行处理机,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/20的速度只实现了8,,8＝64个PE，只达到50MFLOPSIlliacIV系统的影响非常大它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表IlliacIV系统由三大部分组成。
IlliacIV处理机阵列，阵列控制器，一台标准的Burroughs B6700计算机8/15/2024,13,8.3.1 IlliavIV 并行处理机8/24/20231,IlliacIV系统由三大部分组成,IlliacIV处理机阵列：8 X 8，,包括PE、PEM和互连网络阵列控制器CU，,输入输出处理机：一台标准的Burroughs B6700计算机8/15/2024,14,IlliacIV系统由三大部分组成8/24/202314,1、阵列控制器,阵列控制器CU实际上是一台小型控制计算机对阵列处理单元实行控制和完成标量操作标量操作与各PE的数组操作可以重叠执行控制器的功能有以下五个方面：,(1) 对指令进行译码，并执行标量指令；,(2) 向各处理单元发出执行数组操作指令所需的控制信号；,(3) 产生和向所有处理单元广播公共的地址；,(4) 产生和向所有处理单元广播公共的数据；,(5) 接收和处理PE、I/O操作以及B6700产生的陷阱中断信号2、输入输出系统,IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部分组成。
8/15/2024,15,1、阵列控制器8/24/202315,3、IlliacIV处理阵列,IlliacIV处理阵列由８,,８＝64个PU组成每个PU由处理部件PE和它的局部存储器PEM组成每一个PU,i,只和它的东、西、南、北四个近邻PU,i+1,mod 64、PU,i-1,mod 64、PU,i+8,mod 64、PU,i-8,mod 64直接连接南北方向同一列PU连成一个环，东西方向构成一个闭合螺线闭合螺线最短距离不超过7步普通网格最短距离不超过8步例如：从PU,0,到PU,36,的距离：采用普通网格必须8步：,PU,0,,PU,1,,PU,2,,PU,3,,PU,4,,PU,12,,PU,20,,PU,28,,PU,36,或 PU,0,,PU,8,,PU,16,,PU,24,,PU,32,,PU,33,,PU,34,,PU,35,,PU,36,或 …,如果采用闭合螺旋线，只需要7步：,PU,0,,PU,63,,PU,62,,PU,61,,PU,60,,PU,52,,PU,44,,PU,36,或 PU,0,,PU,63,,PU,55,,PU,47,,PU,39,,PU,38,,PU,37,,PU,36,或 ……,对于n×n个单元的阵列，,任意两个单元之间的最短距离不超过n-1步,。
8/15/2024,16,3、IlliacIV处理阵列8/24/202316,普通网格必须8步：,PU,0,,PU,1,,PU,2,,PU,3,,PU,4,,PU,12,,PU,20,,PU,28,,PU,36,或,PU,0,,PU,8,,PU,16,,PU,24,,PU,32,,PU,33,,PU,34,,PU,35,,PU,36,,或 …,闭合螺旋线只要7步：,PU,0,,PU,63,,PU,62,,PU,61,,PU,60,,PU,52,,PU,44,,PU,36,,或,PU,0,,PU,63,,PU,55,,PU,47,,PU,39,,PU,38,,PU,37,,PU,36,,或 ……,8/15/2024,17,普通网格必须8步：PU0PU1PU2PU3PU4P,8.3.2 BSP处理机,BSP（Buroughs Scientific Processor）计算机是由美国宝来公司和伊利诺依大学于1979年制造的BSP是共享存储器结构的并行处理机的典型代表BSP由控制处理机、并行处理机、文件存储器、并行存储器模块以及对准网络等5个部分组成。
1、并行处理机,时钟周期160ns，,向量运算速度最高可达50MFLOPS,17个并行存储器模块，每个模块512K字，存储周期160ns5级流水线：,,(1)从17个存储模块中读出数据,(2)通过输出对准网络把数据送入16个并行处理部件,(3)16个并行处理部件并行处理机数据,(4)通过输入对准网络把数据从并行处理部件送到并行存储器,(5)把接收到的数据写入并行存储器,8/15/2024,18,8.3.2 BSP处理机8/24/202318,8/15/2024,19,8/24/202319,2、控制处理机,控制处理机主要用来控制并行处理机提供与系统管理机相连的接口执行存放在控制存储器中的操作系统和用户程序的标量部分全部向量指令及成组的标量指令被送给并行处理机控制维护单元是系统管理机与控制处理机之间的接口，用来进行初始化、监控命令通信和维护3、文件存储器,计算任务文件从系统管理机加载到文件存储器，由控制处理机执行文件存储器是BSP直接控制下唯一的外围设备程序执行过程中所产生的暂存文件和输出文件，在将它们送给系统管理机输出给用户之前是存在文件存储器中的文件存储器的数据传输率较高，大大地缓解了I/O受限问题。
8/15/2024,20,2、控制处理机8/24/202320,4、对准网络,对准网络采用全交叉开关实现,数据从一个源广播至几个目的地，几个源寻找一个目的地时能分解冲突存储器模块和对准网络的组合实现了无冲突访问并行存储器,对准网络还可以实现快速傅里叶变换、数据压缩和扩展操作5、无访问冲突存储系统,只有数组存取和I/O访问并行存储器等效存储周期为10ns,两次算术运算中需要用到三个变量，产生一个结果，共访问存储器4次，并行存储器和浮点运算之间的,频带保持完全平衡,对于长向量来，中间结果存在寄存器中，每次运算只需要一个操作数因此并行存储器有足够的频宽留给输入和输出信息用实现一维向量和二维矩阵的行、列、对角线和反对角线的无冲突访问8/15/2024,21,4、对准网络8/24/202321,8.4 并行处理机算法举例,要发挥并行处理机的效率，特别,依赖于并行算法,并行算法的一个关键问题是要,提高向量化的程度,在设计并行算法时，要特别注意,数据在多个存储模块之间的分布,，要解决好访问存储器的冲突问题互连网络并不能提供所有处理单元之间的连接，因此，并行算法要,充分利用互连网络的结构,8.4.1 有限差分问题,8.4.2 矩阵乘,8.4.3 求累加和,8/15/2024,22,8.4 并行处理机算法举例要发挥并行处理机的效率，特别依赖于,8.4.1 有限差分问题,有限差分方法是一种通用和有效方法：,,把连续方程变换成离散形式。
二阶偏导数表示为差分形式：,,,,,并代入原方程，则可得有限差分计算公式：,,,其中：(x, y)为平面直角坐标，h为网格间距IlliacIV的阵列结构特别适合计算这种在网格上定义的有限差分函数,把内部网格点分配给各个处理单元，计算过程可以并行完成，从而可几十倍地提高处理速度8/15/2024,23,8.4.1 有限差分问题8/24/202323,8.4.2 矩阵乘,A、B、C均为8×8的二维矩阵，则C＝A×B的计算公式为：,,,在串行机上要用一个三重循环程序，乘和加分别为512次(除循环控制外)在并行处理机上求解，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 CONTINUE,8/15/2024,24,8.4.2 矩阵乘8/24/202324,在并行处理机上，J循环只需一次速度提高到8倍PE0：c,00,＝a,00,b,00,＋a,01,b,10,＋a,02,b,20,……＋a,07,b,70,PE1：c,01,＝a,00,b,01,＋a,01,b,11,＋a,02,b,21,……＋a,07,b,71,……,PE7：c,07,＝a,00,b,07,＋a,01,b,17,＋a,02,b,27,……＋a,07,b,77,,PE0：c,10,＝a,10,b,00,＋a,11,b,10,＋a,12,b,20,……＋a,17,b,70,,PE1：c,11,＝a,10,b,01,＋a,11,b,11,＋a,12,b,21,……＋a,17,b,71,……,PE7：c,17,＝a,10,b,07,＋a,11,b,17,＋a,12,b,27,……＋a,17,b,77,……,PE7：c,77,＝a,70,b,07,＋a,71,b,17,＋a,72,b,27,……＋a,77,b,77,8/15/2024,25,在并行处理机上，J循环只需一次。
速度提高到8倍8/24/2,8/15/2024,26,8/24/202326,PE0：,c,00,＝a,00,b,00,＋a,01,b,10,＋a,02,b,20,……＋a,07,b,70,PE1：,c,01,＝a,00,b,01,＋a,01,b,11,＋a,02,b,21,……＋a,07,b,71,……,PE7：,c,07,＝a,00,b,07,＋a,01,b,17,＋a,02,b,27,……＋a,07,b,77,PE0：,c,10,＝a,10,b,00,＋a,11,b,10,＋a,12,b,20,……＋a,17,b,70,PE1：,c,11,＝a,10,b,01,＋a,11,b,11,＋a,12,b,21,……＋a,17,b,71,……,PE7：,c,17,＝a,10,b,07,＋a,11,b,17,＋a,12,b,27,……＋a,17,b,77,……,……,PE7：,c,77,＝a,70,b,07,＋a,71,b,17,＋a,72,b,27,……＋a,77,b,77,如果64个处理单元全部利用起来并行运算，即把K循环的运算也改为并行，则可进一步提高速度要做到这一点，需要重新在阵列存储器中恰当分配数据。
8/15/2024,27,PE0：c00＝a00b00＋a01b10＋a02b20……,8.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，log,2,N－1,10 A＝A＋SRL(A, 2**I) ；把A向量逻辑右移2,i,个PE,,在并行处理机上只需做 log,2,N 次加法8/15/2024,28,8.4.3 求累加和8/24/202328,8/15/2024,29,8/24/202329,,递归求和算法的性能分析：,运算速度提高,：,加速比为N/log,2,N倍,运算次数增加,：,从N次增加到N·log,2,N次,效率降低,：,实际效率为1/log,2,N,如：,N＝1024，速度提高100倍，运算次数增加10倍，效率只有1/10,如果N＝2,20,，即100万个数求和，速度可以提高5万倍这种方法也称为级联求和，或递归求和与流水线中采用的方法相同，它利用结合律来提高并行度。
可以利用结合律求解的递归问题还有：,求最大数，求最小数，,ａ与ｂ进行异或运算，ａ与ｂ进行逻辑或运算，,ａ与ｂ进行逻辑与运算，求ａ与ｂ的点积8/15/2024,30,递归求和算法的性能分析：8/24/202330,,本章重点：,1、并行处理的基本结构和特点,2、典型的并行处理机算法,,习题:,8.6（改为：,n,个PE）,8/15/2024,31,本章重点：8/24/202331,。
