1、第一章第一章 基本概念基本概念第二章第二章 指令系统及指令系统及CPUCPU组成组成第三章第三章 存储系统存储系统第四章第四章 输入输出系统输入输出系统第五章第五章 标量处理机标量处理机第六章第六章 向量处理机向量处理机第七章第七章 互连网络互连网络第八章第八章 并行处理机并行处理机第九章第九章 多处理机多处理机计算机组成与系统结构计算机组成与系统结构2022-10-19 两个或两个以上处理机两个或两个以上处理机(包括包括PUPU和和CU)CU)，通过高速互连网，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并
2、行。级（任务级、作业级）并行。按照按照Flynn分类法，多处理机系统属于分类法，多处理机系统属于MIMD计算机。计算机。9.1 9.1 多处理机结构多处理机结构9.2 9.2 多处理机性能模型多处理机性能模型9.3 9.3 多处理机的多处理机的CacheCache一致性一致性9.4 9.4 多处理机实例多处理机实例9.5 9.5 多处理机并行算法多处理机并行算法第九章第九章 多处理机多处理机2022-10-199.1 9.1 多处理机结构多处理机结构 多处理机系统由多个独立的处理机多个独立的处理机组成，每个处理机都能够独立执行自己的程序。它有多种分类方法：以松散偶合多处理机松散偶合多处理机和紧
3、密偶合多处理机紧密偶合多处理机两种类型结构说明多处理机的基本结构和特点。9.1.1 9.1.1 松散偶合多处理机松散偶合多处理机9.1.2 9.1.2 紧密偶合多处理机紧密偶合多处理机9.1.3 9.1.3 多处理机系统的特点多处理机系统的特点2022-10-19 多处理机系统多处理机系统有多种分类方法：按照处理机之间的连接程度：紧密偶合紧密偶合和松散偶合多处理机松散偶合多处理机按照是否共享主存储器：共享存储器共享存储器和分布存储器多处理机分布存储器多处理机按照处理机是否相同：同构型同构型和异构型多处理机异构型多处理机按照处理机的个数：大规模并行处理机大规模并行处理机MPPMPP和对称多处理机
4、对称多处理机SMPSMP 按照PE与IOP之间互连方式：对称型对称型：每个IOP能够连接到所有PE上非对称型非对称型：每个IOP只与一个PE连接。冗余对称型冗余对称型：一个PE与多个IOP连接。按照存储器的访问方式：均均存储器，UMAUMA模型模型非均均存储器，NUMANUMA模型模型只有Cache，COMACOMA模型模型 多向量处理机多向量处理机，机群系统机群系统（Cluster）等也称为多处理机系统。2022-10-19 处理机之间的连接频带比较低处理机之间的连接频带比较低通过输入输出接口，处理机之间互为外围设备进行连接。例如，IBM公司的机器都可以通过通道到通道的连接器CTC(Chan
5、nel To Channel)把两个不同计算机系统的IOP连接起来。通过并行口或串行口通过并行口或串行口把多台计算机连接起来。例如，用串行口加一个MODEL拨号上网，也可以直接连接；多台计算机之间的连接需要有多个接口。通过通过Ethernet网络接口网络接口连接多台计算机。速度达10Mb、100Mb、1Gb，Mynet已经达到1.28Gb和2.56Gb。当通信速度要求更高时，可以通过一个通道和仲裁开关CAS(Channel and Arbiter Switch)直接载存储器总线之间建立连接。在CAS中有一个高速的通信缓冲存储器。9.1.1 9.1.1 松散偶合多处理机多处理机2022-10-1
6、9 通通 过过 输输 入入输输 出出接接 口口 连连接接 的的 多多处处 理理机机CPU0CPU1CPUn-1LM0LM1IOP0IOP1互 连 网 络LMn-1IOPn-12022-10-19 模块0 模块n-1通通过过消消息息传传送送系系统统连连接接的的松松散散偶偶合合多多处处理理机机CPU0CPUn-1LM0IOP0互连网络LMn-1IOPn-1CASCAS2022-10-19 处理机之间共享主存储器，通过高速总线或高速开关连接。处理机之间共享主存储器，通过高速总线或高速开关连接。每个CPU能够访问任意一个存储器模块通过映象部件MAP把全局逻辑地址变换成局部物理地址通过互连网络寻找合适的
7、路径，并分解访问存储器的冲突 多个输入输出处理机IOP也连接在互连网络上，输入输出设备与CPU共享主存储器。处理机个数不能太多处理机个数不能太多，一般几个到十几个。紧密偶合方式要求有很高通信频带要求有很高通信频带。可以采用如下措施：(1)采用高速互连网络(2)增加存储模块个数，一般nm，取12倍之间。(3)每个存储模块再分成多个小模块，并采用流水线方式工作。(4)每个CPU都有自己的局部存储器LM。(5)每个CPU设置一个Cache。9.1.9.1.2 紧密偶合多处理机多处理机2022-10-19 紧紧密密偶偶合合多多处处理理机机模模型型CPU0CPU1CPUn-1MAPMAPIOP0IOP1
8、CPU-MM-IOP 互连网络MAPIOPd-1MM0MM1MMm-12022-10-19 带带 有有 二二 维维 共共 享享 存存 储储 器器 和和 局局 部部 C a ch e 及及 存存 储储 器器 的的 多多 处处 理理 机机C P U0C P U1C P Up-1M A PM A PIO P0IO P1C P U-M M 互 连 网 络M A PIO Pd-1C P U-IO P 互 连 网 络L ML MC acheC acheC acheM M0，0M M0，n-1M M1，0M M1，n-1M Mm-1，0M Mm-1，n-1L M2022-10-191 1、结构灵活、结构灵活
9、并行处理机：专用，PE数很多(几千个)，固定有限的通信多处理机：多处理机：通用通用，几十个，几十个，高速灵活的通信高速灵活的通信2 2、程序并行性、程序并行性并行处理机的并行性存在于指令内部，识别比较容易。多处理机的并行性存在于指令外部并行性存在于指令外部，在多个任务之间，识别难度较大。一个简单的例子：Y=A+B*C*D/E+F。用两个处理机：用两个处理机：CPU1：B*C，A+F，A+B*C*D/E+FCPU2：D/E，B*C*D/E，9.1.3 9.1.3 多处理机系统的特点多处理机系统的特点2022-10-193 3、并行任务派生、并行任务派生 并行处理机把同种操作集中，由指令直接启动各
10、PE同时工作。多处理机用专门的指令来表示并发关系用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务。如果任务数多于处理机数，多余的任务进入排队器等待。如果任务数多于处理机数，多余的任务进入排队器等待。4 4、进程同步、进程同步 并行处理机仅一个CU，自然是同步的。多处理机执行不同的指令，工作进度不会也不必保持相同。先做完的要停下等待。有数据相关和控制相关也要停下等待。要采取特殊的同步措施来保持程序所要求的正确顺序。要采取特殊的同步措施来保持程序所要求的正确顺序。5 5、资源分配和进程调度、资源分配和进程调度 并行处理机的PE是固定的，用屏蔽改变实际参加操作的PE数
11、目。多处理机执行并发任务，需用处理机的数目不固定，各处理机进出任务的时刻不相同，所需共享资源的品种、数量随时变化。资源分配和进程调度问题资源分配和进程调度问题，对整个系统的效率有很大的影响。2022-10-19 引起峰值性能下降的原因：引起峰值性能下降的原因：(1)由于处理机之间通信而产生的延迟。(2)一台处理机与其它处理机同步所需的开销。(3)当没有足够多任务时，一台或多台处理机处于空闲状态。(4)由于一台或多台处理机执行无用的工作。(5)系统控制和操作调度所需的开销。研究多处理机的目的：研究多处理机的目的：单处理机的速度提高很快，为什么还要研究多处理机？单处理机的速度提高很快，为什么还要研
12、究多处理机？提前5年得到速度高10倍的机器。或用1/10的价格获得一台高性能的机器。在某些适合进行并行处理得应用领域，可以达到：提前提前1010年得到速度高年得到速度高100100倍的机器。倍的机器。或用或用1/1001/100的价格获得一台高性能的机器。的价格获得一台高性能的机器。9.2 多处理机性能模型2022-10-19 并行性在很大程度上依赖于并行性在很大程度上依赖于R/CR/C比值比值，其中：R代表程序执行时间，C代表通信开销。通常：R/C比值小，并行性低。R/C比值大，并行性高。如果把作业分解成较大的块，就能得到较大的R/C比值，但是所得到的并行性比最大可能的并行性要小得多。R/C
13、R/C比值是衡量任务粒度（比值是衡量任务粒度（Task GranularityTask Granularity）大小的尺度。）大小的尺度。粗粒度(Coarsegrain)并行：R/C比值比较大，通信开销小。细粒度(Finegrain)并行：R/C比值比较小，通信开销大。细粒度并行需要的处理机多，粗粒度并行需要的处理机少。细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。在极端情况下，一个小任务只完成一个操作。指令级并行指令级并行。2022-10-19 目标：目标：由由M个任务组成的程序，在个任务组成的程序，在N台处理机组成的系统上运台处理机组成的系统上运行，求最短执行时间？行
14、，求最短执行时间？为了简单起见，基本模型仅考虑由两台处理机组成的系统。总处理时间总处理时间Rmax(MK，K)C(MK)K 其中：R：每个任务的执行时间，C：通信开销，K：任务分配参数。直观看：当通信时间比较小时，把M个任务平均分给两台处理机，当通信时间很大时，把M个任务分配给一台处理机。9.2.1 9.2.1 基本模型基本模型2022-10-19 时时间间 时时间间 总的处理时间100 总的处理时间 50 90 80 40 70 60 通信时间 30 50 40 20 执行时间 30 20 10 通信时间 10 执行时间 0 0 10 20 30 40 50 0 10 20 30 40 50
15、 任任务务分分配配参参数数 k 任任务务分分配配参参数数 k ()最佳分配参数 K0 ()最佳分配参数 KM/22022-10-19 通信时间：通信时间：C(M-K)K是一个开口向下的二次函数，任务执行时间是两根相交的直线。当通信时间比较大时，总时间的最小值发生的两个端点，当通信时间比较小时，总时间的最小值发生的中点。结论：结论：(1)总时间的最小值只可能出现在中点或两个端点总时间的最小值只可能出现在中点或两个端点，(2)如果总时间的最小值发生在中点 即M个任务平均分给两台处理机，必须满足：M R R M/2+C M/2 M/2 R/C M/2 总时间最短的结论：总时间最短的结论：当当R/CM
16、/2时，把所有任务分配给同一台处理机，时，把所有任务分配给同一台处理机，K0；当当R/CM/2时，把任务平均地分配给两台处理机，时，把任务平均地分配给两台处理机，KM/2。2022-10-19 M个任务分配给个任务分配给N台处理机，求总处理时间的最小值。台处理机，求总处理时间的最小值。实际的最小值发生在极端分配情况下，或者将所有的任务集实际的最小值发生在极端分配情况下，或者将所有的任务集中在一台处理机上，或者将任务平均分配给所有处理机。中在一台处理机上，或者将任务平均分配给所有处理机。先讨论平均分配平均分配方法：个任务平均分给台处理机（P）：11个任务平均分给台处理机（P）：9.2.2 9.2
17、.2 N N台处理机系统的基本模型台处理机系统的基本模型方案P1P2P3执行时间通信时间 总处理时间一2112R5C2R+5C二二2 22 20 02 2R R4 4C C2 2R R+4 4C C方案P1P2P3P4P5执行时间 通信时间 总处理时间一322223R48C3R+48C二332213R47C3R+47C三三3 33 33 32 20 03 3R R4 45 5C C3 3R R+4 45 5C C2022-10-19 M个任务平均分配给个任务平均分配给N台处理机的最佳分配方法：台处理机的最佳分配方法：有 台处理机，每台分给 个任务；如果M/N0，则：另有1台处理机分得剩下的 个
18、任务；剩下的 台处理机不分配任何任务。例如：101个任务平均分给50台处理机：有33台处理机，每台分给3个任务；另有台处理机分给个任务；剩下的16台处理机不分配任务。NMM/NM/NMM/mod1/NMMN2022-10-19 假设Ki个任务分给了第台处理机：第一项求出N台处理机中最大执行时间；第二项计算出Ki与（MKi）任务之间两两通信的开销时间；第二项是关于Ki的二次函数。其中，Ki最多有3个取值：、0 当 M 是 N 的倍数时，当当R/CR/CM/2M/2时采用平均分配方法，时采用平均分配方法，当当R/CR/CM/2M/2时采用集中分配方法。时采用集中分配方法。)(2)(21221Nii
19、NiiikMCNMRkMkCNMR总处理时间NM/NMM/mod)11(22NMCNRM总处理时间2022-10-19 多处理机系统的加速比：一个计算问题在一台处理机上运行时间与在多处理机系统一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比上运行时间的比值称为多处理机系统的加速比当M是N的倍数时，有：如果M和N较小，R/C较大，即分母中的第一项远大于第二项，则加速比与处理机台数N成正比。当处理机台数N很大，加速比 ，趋近于一个常数。这时如果再增加处理机，性能的提高很小。21)222）（加速比NMCRNCRNMMCNRMRM)(2122NiikMCNMR
20、RM加速比CMR22022-10-19 每个任务要和其它所有任务通信，而通信的内容相同。把M个任务分配给N台处理机时，当M是N的倍数时，总处理时间RMNCN 很明显，这个函数有一个极小值。(RMNCN)N0 解得：因此得到最小的总处理时间：这种模型的加速比为：当M是N的倍数时，该多处理机系统的最大加速比为：9.2.3 9.2.3 通信开销为线性函数的模型通信开销为线性函数的模型CNNMR总处理时间CRMCN RMCCRMCCCRMCRM2/总处理时间的最小值CRMCRMCRM22最大加速比CNNMRRM加速比2022-10-19 由于通信与计算可以在两个独立的功能部件中进行，因此，由于通信与计
21、算可以在两个独立的功能部件中进行，因此，能够采用重叠或流水线方式并行进行。能够采用重叠或流水线方式并行进行。一个理想模型，通信与计算完全重叠。对于两台处理机的系统：当当R/CM/2时，执行时间与通信时间的交点就是总处理时间时，执行时间与通信时间的交点就是总处理时间的最小值；的最小值；当当R/CM/2时，采用平均分配方法，在这一点运行时间足够时，采用平均分配方法，在这一点运行时间足够长，完全能够屏蔽通信时间。长，完全能够屏蔽通信时间。9.2.4 9.2.4 通信与计算完全重叠的模型通信与计算完全重叠的模型)(2,(122NiikMCNMRMax总处理时间2022-10-19 时时间间 时时间间
22、50 50 40 通信时间 40 总处理时间最小 30 30 20 执行时间 20 执行时间 10 总处理时间最小 10 通信时间 0 0 10 20 30 40 50 0 10 20 30 40 50通通信信与与计计算算完完全全重重叠叠的的模模型型2022-10-19 直线与二次曲线的交点是关键点：R(MK)C(MK)K即：KR/C（其中：1KM/2）总处理时间总处理时间R（MR/C），），两台处理机系统的加速比在1与2之间；当R/CM/2，即把任务平均分配给两台处理机时，加速比最大；当R/C逐渐减为1时，加速比也逐渐减为1，最优分配变得越来越不均衡了。至于N台处理机的系统：当N比较大时，近
23、似为：处理机数目N由下面一个关于R/C和M的函数式 给出。CMR/11加速比)11(22NCMNRM2NMCRCMRN22022-10-19 通信链路随通信链路随的增加而增加，让每台处理机与别的任何一台的增加而增加，让每台处理机与别的任何一台处理机都有专门的链路相连。处理机都有专门的链路相连。当任务数M是处理机数N的倍数时，尽可能平分任务可以使总处理时间达到最小：把处理机台数作为自变量，这个函数有一个极大值。由于分母大于1，因此总处理时间的极大值出现在2时,当当=2=2时，随着处理机台时，随着处理机台增加，总处理时间肯定减小。增加，总处理时间肯定减小。9.2.5 9.2.5 具有多条通信链的模
24、型具有多条通信链的模型）（总处理时间NiikMNCNMR1222)11(22NNCMNRM总处理时间CMRNNMCNMCNRMNNCMNRMN21202220)11(22(322222022-10-19 为了验证N台处理机是否比一台处理机效果更佳：相等点在：在相等点参数R/C与N成反比例，N越大，允许的粒度越小；N台处理机的总性能等价于一台处理机。总结上面几个模型，可以得出如下结论：总结上面几个模型，可以得出如下结论：(1)多处理机系统结构所需的额外开销多处理机系统结构所需的额外开销，包括调度，对共享资源的竞争，同步，处理机之间通信等。(2)当处理机台数增加时，额外开销时间也增加当处理机台数增
25、加时，额外开销时间也增加。实际上，额外开销的增加可能比处理机数目的线性增加更快。(3)R/CR/C比值越大，越有利于计算过程比值越大，越有利于计算过程。如果采用粗粒度，能够获得较大的R/C比值；但是并行程度将大为降低。(4)为了使价格和性能都比较合理，处理机数目存在一个极大值为了使价格和性能都比较合理，处理机数目存在一个极大值，这个值主要依赖于机器的系统结构、基本技术（尤其是通信技术）和具体的应用问题。)11)(2(2NNCMNRMRMNMCR22022-10-19 在并行处理机和多处理机系统中，采用局部在并行处理机和多处理机系统中，采用局部CacheCache会引会引起起CacheCache
26、与共享存储器之间的一致性问题。与共享存储器之间的一致性问题。出现不一致性问题的原因有三个：出现不一致性问题的原因有三个：共享可写的数据共享可写的数据进程迁移进程迁移I/OI/O传输。传输。9.3.1 9.3.1 问题由来问题由来9.3.2 9.3.2 监听协议监听协议9.3.3 9.3.3 基于目录的协议基于目录的协议9.3 9.3 多处理机的多处理机的CacheCache一致性一致性2022-10-191 1、写共享数据引起的不一致性写共享数据引起的不一致性 使用多个局部使用多个局部Cache时，可能发生时，可能发生Cache不一致性问题：不一致性问题：当P1把X的值写为X之后，如果P1采用
27、写通过方式，内存中的内容也变为X，但是P2处理机Cache中的内容还是X。如果P1采用写回策法，内存中的内容还是X，当P2处理机要读X时，读到的是X而不是X。9.3.1 9.3.1 问题由来问题由来处理机 Cache 总线 共享 存储器 更新之前 写通过方式 写回方式P1P2XXXP1P2XXXP1P2XXX2022-10-192 2、进程迁移引起的数据不一致性、进程迁移引起的数据不一致性 P1和P2中都有共享数据X的拷贝，P2修改了X，并采用写通过方式，所以内存中的X修改成了X。如果该进程迁移到P1上，P1的Cache中仍然是X。P1中有共享数据X的拷贝，而P2中没有该共享数据，P1进程对X
28、进行了修改，如果该进程迁移到了P2上，P2运行时从内存中读到是X。处理机 Cache 总线 共享 存储器 更新之前 写通过方式 写回方式P1P2XXXP1P2XXXP1P2XXX2022-10-193、I/O造成数据不一致性造成数据不一致性 如果P1和P2在各自的局部Cache中都有X的拷贝，当I/O将一个新数据X写入存储器时就导致存储器和Cache的数据不一致。如果两个局部Cache中都有X的拷贝，并采用写回方式，当P1把X修改成X之后；输出部件读X，存储器把X传给输出部件 一种解决I/O操作引起数据不一致性的方法是把I/O处理机分别连接到各自的局部Cache上。处理机 Cache 总线 存
29、储器 I/O 存储器 输入 存储器 输出 更新之前 写通过方式 写回方式P1P2XXXP1P2XXXP1P2XXXXX2022-10-19 有两类解决Cache不一致性问题的协议：在总线互连的多处理机系统中，通常采用监听协议。在总线互连的多处理机系统中，通常采用监听协议。在其他多处理机系统中，通常采用基于目录协议。在其他多处理机系统中，通常采用基于目录协议。1 1、两种监听协议、两种监听协议 使用监听协议，有两种方法：方法一：方法一：写无效（写无效（Write InvalidateWrite Invalidate）策略）策略，在本地Cache的数据块修改时使远程数据块都无效。方法二：方法二：写
30、更新（写更新（Write UpdateWrite Update）策略）策略，在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache 采用写无效或写更新策略与Cache采用写回方式（Write Back）还是写通过方式（Write Through）无关。如果Cache采用的写通过方式，在使远程数据块无效或更新其他Cache的同时，还要同时修改共享存储器中的内容。9.3.2 9.3.2 监听协议监听协议2022-10-19 由于写更新策略在本地Cache修改时需要通过总线把修改过的数据块广播给所有含该数据块的其他Cache，增加了总线的负担。大部分多处理机系统使用写无效策
31、略。处理机 Cache 总线 共享 存储器 更新之前 写无效策略 写更新策略P1P2XXXP1P2XIXP1P2XXX2022-10-192 2、采用写通过方式的、采用写通过方式的CacheCache 数据块有两种状态:有效和无效有效和无效。有效表示该数据块内容正确，两种状态的转换如下图：采用写通过方式的Cache状态图RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。RL,WLRL,WL RR,WR RR 有效 无效 WR2022-10-193 3、采用写回方式的、采用写回方式的CacheCache 只读状态表示整个系统中有多个
32、数据块拷贝是正确的，读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，即在整个系统中只有一个数据块拷贝是正确的。对于只读的数据块，本地的和远程的读操作都是安全的，本地的写操作将使状态转移为读写，远程的写操作将使之变为无效。对于读写状态的数据块，本地的读、写操作都是安全的，而远程的读操作将数据块传递给远程处理机的Cache，使两个Cache都转移至只读状态，远程写操作使远程处理机Cache转移至读写状态，而本地Cache转移至无效状态。对于无效状态，本地读操作，使状态转移至只读；本地写操作，使状态转移至读写，同时使其他Cache中相应数据块的状态转移为无效状态；其他操作不会引起从
33、无效状态向其他状态的转移。2022-10-19 WLRL,WL RL,RR 读写 只读 RR WL WR WR RL 无效 RR,WR采采用用写写回回方方式式的的 C Ca ac ch he e 状状态态图图RL：本地处理机对Cache的读操作WL：本地处理机对Cache的写操作 RR：远程处理机对Cache中相同内容数据的读操作 WR：远程处理机对Cache中相同内容数据的写操作2022-10-194 4、写一次、写一次(Write-Once)(Write-Once)协议协议方法：第一次写第一次写CacheCache采用写通过方式，以后采用写回方式。采用写通过方式，以后采用写回方式。整个系统
34、中只有一份正确的拷贝。整个系统中只有一份正确的拷贝。为了区分第一次写，把“读写”状态分为：“保留（Reserved）”和“重写(Dirty)”。共有4种状态(1)有效有效(Valid,相当于写回方式中的只读)：(2)无效无效(Invalid)：在Cache中找不到或Cache中的数据块已作废。(3)保留保留(Reserved)：数据从存储器读入Cache后只被写过一次，Cache和存储器中的拷贝都是正确。(4)重写重写(Dirty)：Cache中的数据块被写过多次，而且是唯一正确的数据块，此时存储器中的数据块也不是正确的。写一次协议的主要优缺点写一次协议的主要优缺点:优点:减少大量的无效操作，
35、提高了总线效率。减少大量的无效操作，提高了总线效率。缺点:当主存储器的内容无效时当主存储器的内容无效时,读缺失引起的总线读操作必须禁止访读缺失引起的总线读操作必须禁止访问主存储器，而大多数总线不支持这种操作。问主存储器，而大多数总线不支持这种操作。IEEE Futurebus+总线支持该操作。2022-10-19 RLRL,RR RR,WR 有效 无效 WR WL RR WL WR WR RL 保留 重写 RL,WL WL写一次协议的状态图写一次协议的状态图RL：本地处理机对Cache的读操作WL：本地处理机对Cache的写操作 RR：远程处理机对Cache中相同内容数据的读操作 WR：远程处
36、理机对Cache中相同内容数据的写操作2022-10-19l CPUCPU读读CacheCache：有两种可能性。：有两种可能性。(1)数据块在Cache中存在(包括有效、保留或重写)，CPU直接读取数据。(2)Cache中的数据块处于无效状态。如果存在处于有效、保留或重写状态的相应数据块，则将其调入本地Cache；在相应数据块处于重写状态时，还要同时禁止存储器操作。如果不存在处于有效、保留或重写状态的相应数据块，则直接从存储器中读入(只有存储器中是唯一正确的拷贝)。把读入Cache中的相应数据块置为“有效”状态。2022-10-19l CPUCPU写写CacheCache：也有两种可能。：也
37、有两种可能。(1)写命中，当Cache处于“有效”状态时，采用写通过方式，把写入Cache的内容同时写入存储器，将Cache的状态转移为“保留”，将其他Cache的相应数据块状态置为“无效”；当Cache处于“保留”或“重写”态时，使用写回方式，Cache的状态转移至“重写”,其他的存有相同内容的Cache处于“无效”态。(2)写不命中，将数据块调入Cache，采用写通过方式,同时写存储器;将本地Cache的状态置为“保留”，同时将其他Cache的状态置为“无效”。2022-10-19 在非总线结构的多处理机系统中，采用基于目录的在非总线结构的多处理机系统中，采用基于目录的CacheCache
38、一致一致性协议。性协议。1 1、CacheCache目录结构目录结构 Cache目录中存放的内容是大量的指针，用以指明块拷贝的地址，每个目录项还有一个重写位，指明是否有一个Cache允许写入数据。根据Cache目录的存放形式，有集中式和分布式两种有集中式和分布式两种。根据目录的结构，目录协议分成三类：全映射全映射(Full-Map)(Full-Map)目录目录：存放全局存储器每个块的有关数据。有限有限(Limited)(Limited)目录目录：每个目录项的指针数固定。链式链式(Chained)(Chained)目录目录：把目录分布到所有Cache中。9.3.3 9.3.3 基于目录的协议基于
39、目录的协议2022-10-19 目录的使用规则目录的使用规则：当一个CPU对Cache进行写操作时，要根据Cache目录中的内容将所有其他存有相同内容的所有Cache拷贝无效，并置重写位。在CPU对Cache进行读操作时，如果读命中，泽直接读Cache即可。如果重写位为“0”，则从主存或其他Cache中读入该块，并修改目录。2022-10-192 2、全映射目录全映射目录 目录项中有目录项中有N个处理机位和一个重写位。个处理机位和一个重写位。处理机位表示相应处理机对应的Cache块的状态。只有一个处理机的重写位为“1”，则该处理机可以对该块进行写操作。Cache的每个数据块有两个状态位。一位表
40、示数据块是否有效，另一位表示有效块是否允许写。读X 读X 读X 写X (a)所 有Cache中 都 没 有X的 拷 贝 (b)三 个 处 理 机 都 有X的 拷 贝 (c)P3处 理 机 获 得 对X的 写 权P 1P 2P 3Cache1Cache2Cache3 X:共 享 存 储 器C 0 00 数 据P 1P 2P 3Cache1X：数 据Cache2X：数 据Cache3X：数 据 X:共 享 存 储 器0 1 11 数 据P 1P 2P 3Cache1Cache2Cache3X：数 据 X:共 享 存 储 器1 0 01 数 据2022-10-19 从第二种状态从第二种状态(b)转移
41、至第三种状态转移至第三种状态(c)的过程如下的过程如下：(1)Cache3发现包含X单元的块是有效的，但是不允许写(2)Cache3向包含X单元的存储器模块发写请求，并暂停P3工作(3)该存储器模块发无效请求至Cache1和Cache2(4)Cache1和Cache2接到无效请求后，将对应块置为无效态，并发回答信号给存储器模块。(5)存储器模块接到Cache1和Cache2的回答信号后，置重写位为“1”，清除指向Cache1和Cache2的指针，发允许写信号到Cache3。(6)Cache3接到允许写信号，更新Cache状态，并激活P3。优点：全映射目录协议的效率比较高效率比较高。缺点：开销与
42、处理机数目的平方成正比，开销与处理机数目的平方成正比，不具有扩展性。不具有扩展性。2022-10-193 3、有限目录有限目录 当处理机数目为N时，限制目录大小为限制目录大小为O(N log2 N)。目录指针需要对N进行二进制编码，每个指针占log2 N位，目录所占的总存储空间与（Nlog2 N）成正比。当Cache1和Cache2中都有X的拷贝时，若P3请求访问X，则必须在在Cache1和Cache2中选择一个使之无效，这种替换过程称为驱逐。有限目录的驱逐需要一种驱逐策略，驱逐策略的好坏对系统的性能具有很大的影响。驱逐策略与Cache替换策略在很多方面是相同的。2022-10-19 读X (
43、a)(b)有有限限目目录录的的驱驱逐逐P1P2P3Cache1X：数据Cache2X：数据Cache3 X:共享存储器C数据P1P2P3Cache1X：数据Cache2Cache3X：数据 X:共享存储器C数据2022-10-194.4.链式目录链式目录 通过维护一个目录指针链来跟踪共享数据拷贝。通过维护一个目录指针链来跟踪共享数据拷贝。当P1读X时，存储器送X到Cache1,同时写Cache1的一个链结束指针CT，在存储器中也保存一个指向Cache1的指针。当P2读X时，存储器送X给Cache2,同时给Cache2一个指向Cache1的指针,存储器则保存一个指向Cache2的指针。当某一个处
44、理机需要写X时,它必须沿整个目录链发送一个数据无效信息。在收到所有相关处理机的回答信号之后，存储器才给该处理机写允许权。当Cache中的数据块需要替换时，要把该Cache从目录链中删除。有如下解决办法：(1)把Cachei+1的指针指向Cachei-1。在Cachei中存放新数据块。(2)使Cachei及在链中位于其后的所有Cache中的单元X无效。(3)使用双向链。在替换时不再需要遍历整个链。但指针增加了一倍，一致性协议也更加复杂。2022-10-19 优点：不限制共享数据块的拷贝数目，又保持了可扩展性。不限制共享数据块的拷贝数目，又保持了可扩展性。指针的长度以处理机数目的对数关系增长，Ca
45、che的每个数据块的指针数目与处理机数目无关。缺点：链式目录的复杂程度超过了前两种目录。链式目录的复杂程度超过了前两种目录。读X 写X (a)(b)链链 式式 目目 录录P1P2P3Cache1X：数据Cache2Cache3 X:共享存储器C数据CTP1P2P3Cache3 X:共享存储器C数据Cache1X：数据 CTCache2X：数据2022-10-19 多处理机系统主要有四大类：多处理机系统主要有四大类：(1)多向量处理机系统：多向量处理机系统：如：CRAY YMP-90，NEC SX-3和FUJITSU VP-2000 (2)SMP(Symmetry MultiProcessors
46、)对称多处理机对称多处理机 SMP(Shared Memory mulptiProcessors)共享存储多处理机 如：SGI Challenge、Sun SparcCenter 2000 (3)MPP(massively parallel processing)大规模并行处理机大规模并行处理机 如：Intel Paragon，CM-5，Cray T3D (4)Cluster 机群系统机群系统（NOW或COM）9.4.1 大规模并行处理机（大规模并行处理机（MPP）9.4.2 对称多处理机（对称多处理机（SMP）9.4.3 机群系统（机群系统（Cluster）9.4 9.4 多处理机实例多处理
47、机实例2022-10-19 科学计算中的重大课题要求提供的性能：科学计算中的重大课题要求提供的性能：(1)Teraflops计算能力(2)Terabyte主存储器(3)Terabyte/s 输入输出频带宽度目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大。科学计算中的重大课题：全球气候预报、基因工程、飞行动力学、海洋环流、流体动力学、超导建模、半导体建模、量子染色动力学、视觉 采用的关键技术：VLSI技术、可扩展技术、共享虚拟存储技术 虚拟共享存储器(Shared Virtual Memory)也称为：共享分布存储器(Distributed Shared Memory)物理上分布存储
48、器，逻辑上共享存储器。9.4.1 9.4.1 大规模并行处理机大规模并行处理机(MPP)(MPP)2022-10-19 虚拟共享存储器的优点：虚拟共享存储器的优点：编程容易，编程容易，系统结构灵活，系统结构灵活，可扩充性好，可扩充性好，有较好的软件移植性。有较好的软件移植性。与消息传递方式相比：程序的运行效率高程序的运行效率高，主要原因：(1)数据块缓存在本地（内存或Cache中），可以多次使用。(2)通信时间分散，提高了并行性。(3)扩大存储空间，减少换页操作。虚拟共享存储器实现途径：(1)硬件实现硬件实现，利用Cache技术。需要增加专用硬件。(2)操作系统和库实现操作系统和库实现，通过虚
49、拟存储机制取得共享和一致性。在松耦合的分布存储多处理机上，不需要增加任何硬件。(3)编译实现编译实现，自动将共享访问转换成同步和一致原语。大多数系统采用途径(1)和(2)，或这两种途径结合实现。2022-10-19 处处 理理 机机 结结 点点 控控制制处处理理机机 I/O 接接口口控控 制制 网网 格格数数 据据 网网 格格诊诊断断网网格格NIPMNIPMNIPMNIPMNIPMNINII/OI/O1、同步、同步MIMD机器机器 SIMD与与MIMD的优点结合在一起。的优点结合在一起。CM-5同时支持SIMD与MIMD两种并行计算方式。数据并行可以采用数据并行可以采用SIMD、多、多SIMD
50、或同步或同步MIMD模式。模式。32到16384个处理器结点，每个结点有一个SPARC处理机，32MB存储器，64位浮点和整数操作，128Mflops向量处理部件2022-10-19 控制处理机到几十台，根据需要配置存储器和磁盘。输入输出接口与图形设备、海量存储器及高性能网络相连。占地面积为30米30米，峰值速度超过Tflops。三个网络：三个网络：数据网络、控制网络和诊断网络数据网络、控制网络和诊断网络。数据网络提供点对点通信。控制网络提供广播、同步、扫描和系统管理功能。诊断网络从后台访问所有系统硬件，测试系统完整性，检测和隔离错误。数据网络和控制网络有很好的可扩展性，与处理机类型无关。可以
