第一章基本概念第二章指令系统及CPU组成第三章存储系统.ppt
《第一章基本概念第二章指令系统及CPU组成第三章存储系统.ppt》由会员分享,可在线阅读,更多相关《第一章基本概念第二章指令系统及CPU组成第三章存储系统.ppt(83页珍藏版)》请在三一文库上搜索。
1、2019年4月7日,1,第一章 基本概念 第二章 指令系统及CPU组成 第三章 存储系统 第四章 输入输出系统 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机,计算机组成与系统结构,2019年4月7日,2,两个或两个以上处理机(包括PU和CU),通过高速互连网络连接起来,在统一的操作系统管理下,实现指令以上级(任务级、作业级)并行。 按照Flynn分类法,多处理机系统属于MIMD计算机。 9.1 多处理机结构 9.2 多处理机性能模型 9.3 多处理机的Cache一致性 9.4 多处理机实例 9.5 多处理机并行算法,第九章 多处理机,2019年
2、4月7日,3,9.1 多处理机结构,多处理机系统由多个独立的处理机组成,每个处理机都能够独立执行自己的程序。它有多种分类方法: 以松散偶合多处理机和紧密偶合多处理机两种类型结构说明多处理机的基本结构和特点。 9.1.1 松散偶合多处理机 9.1.2 紧密偶合多处理机 9.1.3 多处理机系统的特点,2019年4月7日,4,多处理机系统有多种分类方法: 按照处理机之间的连接程度:紧密偶合和松散偶合多处理机 按照是否共享主存储器:共享存储器和分布存储器多处理机 按照处理机是否相同:同构型和异构型多处理机 按照处理机的个数:大规模并行处理机MPP和对称多处理机SMP 按照PE与IOP之间互连方式:
3、对称型:每个IOP能够连接到所有PE上 非对称型:每个IOP只与一个PE连接。 冗余对称型:一个PE与多个IOP连接。 按照存储器的访问方式: 均均存储器,UMA模型 非均均存储器,NUMA模型 只有Cache,COMA模型 多向量处理机,机群系统(Cluster)等也称为多处理机系统。,2019年4月7日,5,处理机之间的连接频带比较低 通过输入输出接口,处理机之间互为外围设备进行连接。 例如,IBM公司的机器都可以通过通道到通道的连接器CTC (Channel To Channel)把两个不同计算机系统的IOP连接起来。 通过并行口或串行口把多台计算机连接起来。 例如,用串行口加一个MOD
4、EL拨号上网,也可以直接连接;多台计算机之间的连接需要有多个接口。 通过Ethernet网络接口连接多台计算机。 速度达10Mb、100Mb、1Gb,Mynet已经达到1.28Gb和2.56Gb。 当通信速度要求更高时,可以通过一个通道和仲裁开关CAS (Channel and Arbiter Switch)直接载存储器总线之间建立连接。 在CAS中有一个高速的通信缓冲存储器。,9.1.1 松散偶合多处理机,2019年4月7日,6,2019年4月7日,7,2019年4月7日,8,处理机之间共享主存储器,通过高速总线或高速开关连接。 每个CPU能够访问任意一个存储器模块 通过映象部件MAP把全局
5、逻辑地址变换成局部物理地址 通过互连网络寻找合适的路径,并分解访问存储器的冲突 多个输入输出处理机IOP也连接在互连网络上,输入输出设备与CPU共享主存储器。 处理机个数不能太多,一般几个到十几个。 紧密偶合方式要求有很高通信频带。可以采用如下措施: (1)采用高速互连网络 (2)增加存储模块个数,一般nm,取12倍之间。 (3)每个存储模块再分成多个小模块,并采用流水线方式工作。 (4)每个CPU都有自己的局部存储器LM。 (5)每个CPU设置一个Cache。,9.1.2 紧密偶合多处理机,2019年4月7日,9,2019年4月7日,10,2019年4月7日,11,1、结构灵活 并行处理机:
6、专用,PE数很多(几千个),固定有限的通信 多处理机: 通用,几十个, 高速灵活的通信 2、程序并行性 并行处理机的并行性存在于指令内部,识别比较容易。 多处理机的并行性存在于指令外部,在多个任务之间,识别难度较大。 一个简单的例子: Y = A+B*C*D/E+F。 用两个处理机: CPU1:B*C, A+F, A+B*C*D/E+F CPU2:D/E, B*C*D/E,,9.1.3 多处理机系统的特点,2019年4月7日,12,3、并行任务派生 并行处理机把同种操作集中,由指令直接启动各PE同时工作。 多处理机用专门的指令来表示并发关系,一个任务开始执行时能够派生出与它并行执行的另一些任务
7、。 如果任务数多于处理机数,多余的任务进入排队器等待。 4、进程同步 并行处理机仅一个CU,自然是同步的。 多处理机执行不同的指令,工作进度不会也不必保持相同。先做完的要停下等待。有数据相关和控制相关也要停下等待。 要采取特殊的同步措施来保持程序所要求的正确顺序。 5、资源分配和进程调度 并行处理机的PE是固定的,用屏蔽改变实际参加操作的PE数目。 多处理机执行并发任务,需用处理机的数目不固定,各处理机进出任务的时刻不相同,所需共享资源的品种、数量随时变化。 资源分配和进程调度问题,对整个系统的效率有很大的影响。,2019年4月7日,13,引起峰值性能下降的原因: (1)由于处理机之间通信而产
8、生的延迟。 (2)一台处理机与其它处理机同步所需的开销。 (3)当没有足够多任务时,一台或多台处理机处于空闲状态。 (4)由于一台或多台处理机执行无用的工作。 (5)系统控制和操作调度所需的开销。 研究多处理机的目的: 单处理机的速度提高很快,为什么还要研究多处理机? 提前5年得到速度高10倍的机器。 或用1/10的价格获得一台高性能的机器。 在某些适合进行并行处理得应用领域,可以达到: 提前10年得到速度高100倍的机器。 或用1/100的价格获得一台高性能的机器。,9.2 多处理机性能模型,2019年4月7日,14,并行性在很大程度上依赖于R/C比值, 其中:R代表程序执行时间,C代表通信
9、开销。 通常:R/C比值小,并行性低。R/C比值大,并行性高。 如果把作业分解成较大的块,就能得到较大的R/C比值, 但是所得到的并行性比最大可能的并行性要小得多。 R/C比值是衡量任务粒度(Task Granularity)大小的尺度。 粗粒度(Coarsegrain)并行:R/C比值比较大,通信开销小。 细粒度(Finegrain)并行:R/C比值比较小,通信开销大。 细粒度并行需要的处理机多,粗粒度并行需要的处理机少。 细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。在极端情况下,一个小任务只完成一个操作。指令级并行。,2019年4月7日,15,目标:由M个任务组成的
10、程序,在N台处理机组成的系统上运行,求最短执行时间? 为了简单起见,基本模型仅考虑由两台处理机组成的系统。 总处理时间Rmax(MK,K)C(MK)K 其中:R:每个任务的执行时间, C:通信开销, K:任务分配参数。 直观看: 当通信时间比较小时,把M个任务平均分给两台处理机, 当通信时间很大时,把M个任务分配给一台处理机。,9.2.1 基本模型,2019年4月7日,16,2019年4月7日,17,通信时间: C(M-K)K是一个开口向下的二次函数, 任务执行时间是两根相交的直线。 当通信时间比较大时,总时间的最小值发生的两个端点, 当通信时间比较小时,总时间的最小值发生的中点。 结论: (
11、1)总时间的最小值只可能出现在中点或两个端点, (2)如果总时间的最小值发生在中点 即M个任务平均分给两台处理机,必须满足: M R R M/2 + C M/2 M/2 R/C M/2 总时间最短的结论: 当R/CM/2时,把所有任务分配给同一台处理机,K0; 当R/CM/2时,把任务平均地分配给两台处理机,KM/2。,2019年4月7日,18,M个任务分配给N台处理机,求总处理时间的最小值。 实际的最小值发生在极端分配情况下,或者将所有的任务集中在一台处理机上,或者将任务平均分配给所有处理机。 先讨论平均分配方法: 个任务平均分给台处理机(P): 11个任务平均分给台处理机(P):,9.2.
12、2 N台处理机系统的基本模型,2019年4月7日,19,M个任务平均分配给N台处理机的最佳分配方法: 有 台处理机,每台分给 个任务; 如果M/N0,则: 另有1台处理机分得剩下的 个任务; 剩下的 台处理机不分配任何任务。 例如:101个任务平均分给50台处理机: 有33台处理机,每台分给3个任务; 另有台处理机分给个任务; 剩下的16台处理机不分配任务。,2019年4月7日,20,假设Ki个任务分给了第台处理机: 第一项求出N台处理机中最大执行时间; 第二项计算出Ki与(MKi)任务之间两两通信的开销时间; 第二项是关于Ki的二次函数。 其中,Ki最多有3个取值: 、 、0 当 M 是 N
13、 的倍数时, 当R/CM/2时采用平均分配方法, 当R/CM/2时采用集中分配方法。,2019年4月7日,21,多处理机系统的加速比: 一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比 当M是N的倍数时,有: 如果M和N较小,R/C较大,即分母中的第一项远大于第二项,则加速比与处理机台数N成正比。 当处理机台数N很大,加速比 ,趋近于一个常数。这时如果再增加处理机,性能的提高很小。,2019年4月7日,22,每个任务要和其它所有任务通信,而通信的内容相同。 把M个任务分配给N台处理机时, 当M是N的倍数时,总处理时间RMNCN 很明显,这个函数有一个极
14、小值。 (RMNCN)N0 解得: 因此得到最小的总处理时间: 这种模型的加速比为: 当M是N的倍数时,该多处理机系统的最大加速比为:,9.2.3 通信开销为线性函数的模型,2019年4月7日,23,由于通信与计算可以在两个独立的功能部件中进行,因此,能够采用重叠或流水线方式并行进行。 一个理想模型,通信与计算完全重叠。 对于两台处理机的系统: 当R/CM/2时,执行时间与通信时间的交点就是总处理时间的最小值; 当R/CM/2时,采用平均分配方法,在这一点运行时间足够长,完全能够屏蔽通信时间。,9.2.4 通信与计算完全重叠的模型,2019年4月7日,24,2019年4月7日,25,直线与二次
15、曲线的交点是关键点:R(MK)C(MK)K 即:KR/C (其中:1KM/2) 总处理时间R(MR/C), 两台处理机系统的加速比在1与2之间; 当R/CM/2,即把任务平均分配给两台处理机时,加速比最大;当R/C逐渐减为1时,加速比也逐渐减为1,最优分配变得越来越不均衡了。 至于N台处理机的系统: 当N比较大时,近似为: 处理机数目N由下面一个关于R/C和M的函数式 给出。,2019年4月7日,26,通信链路随的增加而增加,让每台处理机与别的任何一台处理机都有专门的链路相连。 当任务数M是处理机数N的倍数时,尽可能平分任务可以使总处理时间达到最小: 把处理机台数作为自变量,这个函数有一个极大
16、值。 由于分母大于1,因此总处理时间的极大值出现在2时, 当=2时,随着处理机台增加,总处理时间肯定减小。,9.2.5 具有多条通信链的模型,2019年4月7日,27,为了验证N台处理机是否比一台处理机效果更佳: 相等点在: 在相等点参数R/C与N成反比例,N越大,允许的粒度越小;N台处理机的总性能等价于一台处理机。 总结上面几个模型,可以得出如下结论: (1)多处理机系统结构所需的额外开销,包括调度,对共享资源的竞争,同步,处理机之间通信等。 (2)当处理机台数增加时,额外开销时间也增加。实际上,额外开销的增加可能比处理机数目的线性增加更快。 (3)R/C比值越大,越有利于计算过程。如果采用
17、粗粒度,能够获得较大的R/C比值;但是并行程度将大为降低。 (4)为了使价格和性能都比较合理,处理机数目存在一个极大值,这个值主要依赖于机器的系统结构、基本技术(尤其是通信技术)和具体的应用问题。,2019年4月7日,28,在并行处理机和多处理机系统中,采用局部Cache会引起Cache与共享存储器之间的一致性问题。 出现不一致性问题的原因有三个: 共享可写的数据 进程迁移 I/O传输。 9.3.1 问题由来 9.3.2 监听协议 9.3.3 基于目录的协议,9.3 多处理机的Cache一致性,2019年4月7日,29,1、写共享数据引起的不一致性 使用多个局部Cache时,可能发生Cache
18、不一致性问题: 当P1把X的值写为X之后,如果P1采用写通过方式,内存中的内容也变为X,但是P2处理机Cache中的内容还是X。 如果P1采用写回策法,内存中的内容还是X,当P2处理机要读X时,读到的是X而不是X。,9.3.1 问题由来,2019年4月7日,30,2、进程迁移引起的数据不一致性 P1和P2中都有共享数据X的拷贝,P2修改了X,并采用写通过方式,所以内存中的X修改成了X。如果该进程迁移到P1上,P1的Cache中仍然是X。 P1中有共享数据X的拷贝,而P2中没有该共享数据,P1进程对X进行了修改,如果该进程迁移到了P2上,P2运行时从内存中读到是X。,2019年4月7日,31,3
19、、I/O造成数据不一致性 如果P1和P2在各自的局部Cache中都有X的拷贝,当I/O将一个新数据X写入存储器时就导致存储器和Cache的数据不一致。 如果两个局部Cache中都有X的拷贝,并采用写回方式,当P1把X修改成X之后;输出部件读X,存储器把X传给输出部件 一种解决I/O操作引起数据不一致性的方法是把I/O处理机分别连接到各自的局部Cache上。,2019年4月7日,32,有两类解决Cache不一致性问题的协议: 在总线互连的多处理机系统中,通常采用监听协议。 在其他多处理机系统中,通常采用基于目录协议。 1、两种监听协议 使用监听协议,有两种方法: 方法一:写无效(Write In
20、validate)策略,在本地Cache的数据块修改时使远程数据块都无效。 方法二:写更新(Write Update)策略,在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache 采用写无效或写更新策略与Cache采用写回方式(Write Back)还是写通过方式(Write Through)无关。 如果Cache采用的写通过方式,在使远程数据块无效或更新其他Cache的同时,还要同时修改共享存储器中的内容。,9.3.2 监听协议,2019年4月7日,33,由于写更新策略在本地Cache修改时需要通过总线把修改过的数据块广播给所有含该数据块的其他Cache,增加了总线
21、的负担。 大部分多处理机系统使用写无效策略。,2019年4月7日,34,2、采用写通过方式的Cache 数据块有两种状态: 有效和无效。 有效表示该数据块内容正确, 两种状态的转换如下图: 采用写通过方式的Cache状态图 RL、WL表示本地处理机对Cache的读和写操作, RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。,2019年4月7日,35,3、采用写回方式的Cache 只读状态表示整个系统中有多个数据块拷贝是正确的, 读写状态表示数据块至少被修改过一次,存储器中相应数据块还没有修改,即在整个系统中只有一个数据块拷贝是正确的。 对于只读的数据块,本地的和远程的读操作都是
22、安全的,本地的写操作将使状态转移为读写,远程的写操作将使之变为无效。 对于读写状态的数据块,本地的读、写操作都是安全的,而远程的读操作将数据块传递给远程处理机的Cache,使两个Cache都转移至只读状态,远程写操作使远程处理机Cache转移至读写状态,而本地Cache转移至无效状态。 对于无效状态,本地读操作,使状态转移至只读;本地写操作,使状态转移至读写,同时使其他Cache中相应数据块的状态转移为无效状态;其他操作不会引起从无效状态向其他状态的转移。,2019年4月7日,36,RL:本地处理机对Cache的读操作 WL:本地处理机对Cache的写操作 RR:远程处理机对Cache中相同内
23、容数据的读操作 WR:远程处理机对Cache中相同内容数据的写操作,2019年4月7日,37,4、写一次(Write-Once)协议 方法:第一次写Cache采用写通过方式,以后采用写回方式。 整个系统中只有一份正确的拷贝。 为了区分第一次写,把“读写”状态分为:“保留(Reserved)”和“重写(Dirty)”。共有4种状态 (1) 有效(Valid, 相当于写回方式中的只读): (2) 无效(Invalid):在Cache中找不到或Cache中的数据块已作废。 (3) 保留(Reserved):数据从存储器读入Cache后只被写过一次, Cache和存储器中的拷贝都是正确。 (4) 重写
24、(Dirty):Cache中的数据块被写过多次,而且是唯一正确的 数据块,此时存储器中的数据块也不是正确的。 写一次协议的主要优缺点: 优点:减少大量的无效操作,提高了总线效率。 缺点:当主存储器的内容无效时,读缺失引起的总线读操作必须禁止访问主存储器,而大多数总线不支持这种操作。 IEEE Futurebus+总线支持该操作。,2019年4月7日,38,写一次协议的状态图 RL:本地处理机对Cache的读操作 WL:本地处理机对Cache的写操作 RR:远程处理机对Cache中相同内容数据的读操作 WR:远程处理机对Cache中相同内容数据的写操作,2019年4月7日,39,CPU读Cach
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 基本概念 第二 指令系统 CPU 组成 第三 存储系统
链接地址:https://www.31doc.com/p-2554643.html