《MIMD计算机》PPT课件_第1页
《MIMD计算机》PPT课件_第2页
《MIMD计算机》PPT课件_第3页
《MIMD计算机》PPT课件_第4页
《MIMD计算机》PPT课件_第5页
已阅读5页,还剩337页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

+,2020/4/27,1,计算机体系结构,主讲:陈付龙,第8章MIMD计算机,多指令流多数据流(MultipleInstructionStreamMultipleDataStream,简称MIMD),它使用多个控制器来异步地控制多个处理器,从而实现空间上的并行性。,概念回顾,1966年,MichaelFlynn根据指令和数据流的概念对计算机的体系结构进行了分类,这就是所谓的Flynn分类法。Flynn将计算机划分为四种基本类型,即SISD、MIMD、SIMD、MISD。,概念回顾:SISD,传统的顺序执行的计算机在同一时刻只能执行一条指令(即只有一个控制流)、处理一个数据(即只有一个数据流),因此被称为单指令流单数据流计算机(SingleInstructionSingleData,SISD)。,概念回顾:SIMD,在执行向量操作时,一条指令可以同时对多个数据(组成一个向量)进行运算,这就是单指令流多数据流(SingleInstructionMultipleData,SIMD)的概念。因此,我们将向量计算机称为SIMD计算机。,概念回顾:MISD,多指令流单数据(MultipleInstructionSingleData,MISD)计算机。在这种计算机中,各个处理单元组成一个线性阵列,分别执行不同的指令流,而同一个数据流则顺次通过这个阵列中的各个处理单元。这种系统结构只适用于某些特定的算法。,概念回顾:MIMD,多个处理单元都是根据不同的控制流程执行不同的操作,处理不同的数据,因此,它们被称作是多指令流多数据流计算机,即MIMD(MultipleInstructionMultipleData,MIMD)计算机。,比较,相对而言,SIMD和MISD模型更适合于专用计算。在商用并行计算机中,MIMD模型最为通用,SIMD次之,而MISD最少用。PII的MMX指令采用的是SISD,高性能服务器与超级计算机大多属于MIMD。SIMD计算机的单个节点含有PU,共享全局的CU,在不同的数据上,执行的是相同的指令(操作),实现指令级的并行,不够灵活。MIMD计算机的单个节点含有PU和CU,这些节点通过互联网络连接起来,在统一的操作系统控制之下,实现指令级、任务级、作业级的并行。,按照Flynn分类法归纳的计算机体系结构图谱,主要内容,8.1多处理机/计算机系统概述8.2多处理机的Cache一致性8.3SMP8.4MPP8.5Cluster8.6其它新并行技术,8.1多处理机系统概述,MIMD机器的崛起源于两个因素:(1)MIMD的灵活性。在合适的软硬件支持下,MIMD可以作为高性能单用户机使用,也能同时运行多个任务,或者是高性能多任务的组合。(2)MIMD可由具有价格/性能比优势的微处理器建成。事实上,目前几乎所有的多处理器计算机使用和工作站、小型单处理器服务器一样的微处理器芯片。,MIMD计算机硬件,多个处理机(CPU,含有PU和CU)/计算机(含有CPU和I/O)互联网络不只是外围设备共享,而且要用多个指令不见分别控制,通过机间复杂互联网络实现通信。,MIMD计算机软件,算法上,不局限于向量数组处理,还要挖掘和实现更多通用算法中的隐含性系统管理上,更多依靠软件(操作系统)手段有效解决资源分配和管理问题,特别是处理机管理和进程调度。,8.1.1多处理机系统模型,(1)两台处理机的模型,处理机1,处理机2,K个任务,M-K个任务,K(M-K)次通信,每个任务均与其余任务通信一次同一台处理机上任务间通信不计,R/C对时间的影响,T,K,T,K,通信时间,执行时间,总处理时间,最好情况,最好情况,结论:当通信任务很少时,任务平均分配较好;反之,任务分配给一台处理机最好,处理机1,处理机2,处理机N,互联网络,每个任务均与其余任务通信一次同一台处理机上任务间通信不计,总的处理时间最小的情况,(3)通信开销为线性函数的模型,处理机1,处理机2,处理机N,互联网络,每个处理机与其余处理机通信一次,平均分配法的时间开销,(4)机间通信可以多路同时进行的模型,每台处理机都有通信链路与其他处理机相连,通信操作可以与任务本身重叠。任意一个时刻一个处理机只能与另外一个处理机通信,处理机1,处理机2,处理机N,互联网络,平均分配法的时间开销,结论,()多处理机体系结构所需额外开销,包括调度、对共享资源的竞争、同步和处理机之间通信等;。()当处理机台数增加时,额外开销时间也增加。有时,额外开销的增加可能比处理机数目的线性增加更快。()值比较越大,即任务粒度越大,越有利于计算过程。()为了使价格和性能都比较合理,处理机数目存在一个极大值,依赖于机器的体系结构、基本技术(特别是通信技术)和具体的应用问题。,8.1.2多处理机系统的特点,多台处理机,通过共享主存或通讯网进行通讯,在软件,硬件各级相互作用,协同求解问题,实现指令间,到作业,任务级的并行。并行处理机属SIMD结构,较适合向量处理;多处理机属MIMD结构,可进行更高层次的并行处理。,结构与通用性,SIMD:单指令流系统,PU间的互连比较规整,互连的PU数量大,并行操作相同,一个CU,控制、数据通讯简单,专用。通用性较差;MIMD:多指令流系统,采用更灵活多变的结构,实现复杂的互连模式,互连的PU数量少并行操作不同,多个CU,控制、数据通讯复杂,通用性较强。,程序并行性,SIMD:操作级并行(数据并行),识别:隐式识别和向量指令,支持:编译程序和硬件;MIMD:任务级并行(数据、功能并行),识别:显式指令、编译程序、OS和硬件等,支持:专用指令,OS对任务的分派和调度。,并行任务派生,SIMD:向量指令表示及控制,隐式并行、效率低;MIMD:专用指令表示及控制,显式并行、效率高。,进程同步,SIMD:单一CU控制,自然同步;MIMD:多个CU控制,需采取特殊措施同步(等待、信号灯等)。,资源分配和任务调度,MIMD:软件手段(排队器、触发等)分配及调度。SIMD:屏蔽手段,无需调度;,效率,MIMD:同时多路执行,效率高。,8.1.3MIMD计算机分类,MIMD体系结构多处理机系统基于共享存储器系统中只有唯一的地址空间,所有的处理器共享该地址空间。唯一的地址空间并不意味着在物理上只有一个存储器。共享地址空间可以通过一个物理上共享的存储器来实现,也可以通过分布式存储器并在硬件和软件的支持下实现。多计算机系统基于消息传递每个处理器有自己的存储器,该存储器只能被该处理器访问而不能被其它处理器直接访问,这种存储器称为局部存储器或私有存储器。当处理器A需要向处理器B传送数据时,A把数据以消息的形式发送给B。,多处理机系统,Symmetricmultiprocessing(SMP)DistributedSharedMemory(DSM),SMP,对称多处理机(SymmetricMultiprocessor)最主要的特征是系统的对称性,即每个处理器可以以同等代价访问各个共享存储器。显然,SMP的访存模型一定是均匀访存模型(UMA)的。优点是并行度很高,但是由于系统总线的带宽是有限的,故处理器的数目是受限的。,SMP体系结构,CPU,Cache,CPU,Cache,CPU,Cache,系统总线或交叉开关,I/O,SM,SM,SM,DSM,分布式共享内存(DSM),也被视为一种分散的全域地址空间(DistributedGlobalAddressSpace),属于计算机科学的一种机制,可以透过硬件或软件来实作。分布式共享内存主要使用在丛集电脑中,丛集电脑中的每一个网络结点(node)都有非共享的内存空间与共享的内存空间。该共享内存的位置空间(addressspace)在所有结点是一致的。简单说,同一时间下在结点A读取0 x00001234会和结点B读取0 x00001234得到一样的值。典型系统KerrighedOpenSSIMOSIXTreadMarksDIPC,DSM体系结构,CPU,Cache,互联网络,M,CPU,Cache,HUB,Router,CPU,Cache,M,CPU,Cache,HUB,Router,多计算机系统,MassiveParallelProcessor(MPP)ParallelVectorProcessors(PVP)ClusterofWorkstation(COW),MPP,大规模并行处理机(MassivelyParallelProcessor)是由多个由微处理器,局部存储器及网络接口电路构成的节点组成的并行计算体系;节点间以定制的高速网络互联。大规模并行处理机是一种异步的多指令流多数据流,因为它的程序有多个进程,它们分布在各个微处理器上,每个进程有自己独立的地址空间,进程之间以消息传递进行相互通信。,MPP体系结构,CPU,Cache,互联网络,M,CPU,Cache,局部总线或互联网络,NIC,I/O,CPU,Cache,M,CPU,Cache,局部总线或互联网络,NIC,I/O,I/O,PVP,平行向量处理机最大的特点是系统中的CPU是专门定制的向量处理器(VP)。系统还提供共享存储器以及与VP相连的高速交叉开关。PVP的机器实例有CrayC-90/CrayT-90/NECSX-4。,COW,工作站机群每一个节点都是一个完整的工作站,特别地,大规模并行处理机(MPP)可以近似的看成为一个没有本地磁盘的COW。COW的网络接口是松耦合的,即它是接到I/O总线上而不是像MPP那样直接接到处理器存储总线上的。,8.2多处理机的Cache一致性,Cache一致性问题?如何解决?,8.2.1Cache一致性问题,单处理机:Cache一致性问题只存在于Cache与主存之间,即使有I/O通道共享Cache亦可通过全写法或回写法较好地加以解决;多处理机:由于每一个处理机都有一个Cache,因此在写操作时,必须保证各Cache之间的数据一致性。,在多处理器系统中,多个Cache中,对应的copy内容应该一致,如下图:,Memory,Cache,P,Cache,P,Cache,P,这几个copy应该一致,问题的提出,导致多处理机系统中cache内容不一致的因素,(1)可写数据的共享。一台处理机采用全写法或回写法修改某一个数据块时,引起其它处理机的cache中同一副本的不一致。(2)输入输出活动。如果输入输出处理机直接接在系统总线上,也会导致cache不一致。(3)进程迁移。进程迁移就是把一个尚未执行完的进程调度到另一个空闲的处理机中去执行。为提高整个系统的效率,有的系统允许进程迁移,使系统负载平衡。这将引起cache的不一致。,(1)共享可写数据的不一致性(sharingofwritabledata),P1,P2,更新前,x,x,x,处理机,Cache,sharedmemory,P1,P2,写通过,x,x,x,P1,P2,写回,x,x,x,(2)进程迁移的不一致性,右图为:包含共享变量x的进程原来在P1上运行,并对x进行了修改(但采取写回策略,所以暂时没有修改Memory),由于某种原因迁移到P2,修改过的x仍在P1的Cache中,P2运行时从Memory中得到x,这个x其实是“过时”的,所以造成了不一致。中间图为:P2中运行的进程对x进行了修改,采取写通过策略,所以把Memory中的x也修改为x,由于某种原因该进程迁移到P1,但P1的Cache中仍为x,所以造成不一致。,(3)I/O操作(绕过Cache的I/O操作),PU1,PU2,x,x,存储器,PU1,PU2,写通过,x,x,P1,P2,写回,x,x,x,x,x,x,x,I/O,存储器,输入,存储器,输出,Cache,总线,中间图为:当I/O处理机将一个新的数据x写入主存储器时,绕过采用写通过策略的cache,则C1和共享存储器之间产生了不一致。右图为:直接从主存储器输出数据时(绕过Cache),采用写回策略的高速缓存产生不一致性。,8.2.2解决Cache一致性问题,以硬件为基础以软件为基础,靠软件的作用来限制一些公用的可写数据存放到cache中。在编译时,通过编译程序分析,把数据分为能用cache的(cacheable)和不能用cache的(non-cacheable)两部分,不能用cache的数据只能存在主存中。为了尽量提高工作效率,并不是把所有要写入的数据都归入不能用cache的数据之列,编译程序在分析时,要看一下可写数据是否在哪一段时间里可以安全地存入cache,哪一段时间里不允许写到cache中。使它在安全的期间使用cache存放,等到这段安全时期终了时,再把这个可写数据在cache中的副本作废,并规定不能用cache。这种方法比较简单,实际是避开了在CACHE中实现可写数据的共享问题,影响系统性能。,以软件为基础的办法,硬件为基础方法,(1)监听cache协议法(snoopycacheprotocol)(2)基于cache目录表法(directoryscheme),(1)监听cache协议法,各个处理机中的cache控制器都有一个监听部件,随时都在监视着其它cache的行动。当一个处理机写入本身cache中某一个数据块时,同时也写入主存,这个操作,起到了向总线上的其它处理机发送保持一致命令的作用,通知这些处理机,就应把这个副本作废或更新,以此来达到cache的一致性。把数据块作废的办法叫写作废法(weite-invalidate),把数据块更新的办法叫写更新法(write-update)当处理机数目很多,不采用总线结构时,监视协议法很困难。将采用目录表法,两种设计Cache一致性协议策略,写无效(writeinvalidate)任一处理器写它的私有Cache时,它都使所有其它的Cache中的副本失效。对Write-through,它也更新memory中的副本(最终是一个Cache中的副本和memory中的副本是有效的)。对Write-back,它使memory中的副本也失效(最终只有一个Cache中的副本是有效的)。写更新(writeupdate)任一处理器写它的私有Cache时,它都立即更新所有其它的Cache中的副本。对Write-through,它也更新主存储器中的副本。对Write-back,对存储器中副本的更新延迟到这个Cache被置换的时刻。,下图表示数据块x在共享存储器和三台处理机的Cache中的副本一致的情形。,x,共享存储器,Cache,P1,x,P2,x,x,P3,总线,处理机,下图表示P1进行写无效操作后的情形。写通过:,x,I表示无效,P1,I,P2,x,I,P3,写回:,x,I表示无效,P1,I,P2,I,I,P3,下图表示P1进行写更新操作后的情形(写通过)。,x,I表示无效,P1,x,P2,x,x,P3,写无效的问题主要开销在两个方面:(1)作废各Cache副本的开销;(2)由作废引起缺失造成的开销,即处理机需要访问已经作废的数据时将引起Cache的缺失。写更新的问题由于更新时,所有的副本均需要更新,开销很大。后果:如果一个处理机经常对某个块连续写,且各处理处理机间对共享块的竞争较小,这时写无效策略维护一致性的开销是很小的。如发生严重竞争,即处理机之间对某个地址的共享数据竞争,将产生较多的作废,引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去,产生颠簸现象,当缓存块比较大时,这种颠簸现象更为严重。,(2)基于cache目录表法,这种方法要在主存中建立一个目录表,记录各公用的数据块都存放在哪几个处理机的cache中。表的每一项中记录一个数据块的使用情况,内容包括有几个指示器,指示器指出这个数据块的副本放在哪几个处理机的cache中,还有指示位表示是否已有cache向这个数据块写入过新内容等。有了这个目录表,当一个处理机写入本身的cache时,只需要有选择地通知存有这个数据块的处理机的cache即可。使其内容或废除或更新。有三种目录表全映射目录表法有限目录表法链式目录表法,当处理机台数增加时,一般不用总线结构,而采用多级互联网络。多级互连网络实现广播功能代价很大。为什么需要广播功能?把一致性命令,如Write-invalidate,Read-invalidate等命令要发送给所有的Cache。能不能只发送给存放该副本的Cache?基于目录的协议的基本思想,1)基于目录的一致性协议的基本思想,目录的结构,目录里放什么有关Cache副本驻留在哪里的信息:所有共享数据块的所有Cache副本的地址表。每个目录项(每个数据结构)包含若干个指向这个块(每个数据块有个目录项)的Cache副本地址的指针以及一个重写位(用来说明是否有一个Cache允许把有关的数据写入)。基于目录的Cache一致性协议是依靠一个目录来记录系统之中哪些处理机的Cache中有指定存储块的副本。当一台处理机希望写某个共享块时,通过目录向有该块的副本的那些处理机“点对点”的发无效信号,使所有其它的副本无效。,目录的方式,集中目录方式(中心目录)1976年Tang提出。用一个中心目录存放所有Cache目录的副本,它能提供为保证一致性所需要的所有信息。缺点:容量非常大,必须采用联想方法来检查,冲突多,检索时间长。分布式目录1978年Censier和Feautrier提出。每个存储模块维护各自的目录,目录中记录着每个存储块的当前信息。当前信息指明哪些Cache有该存储块的副本。,三种目录,全映射(fullmap)目录:存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本,即每个目录项包含N个指针(N是处理机数目)。有限(limited)目录:每个目录项有固定数目的指针(小于N)。链式(chained)目录:将目录分布到各个Cache(其余同全映射目录)。,A.目录项结构目录项中有N个处理机位(对应N台处理机)和一个重写位,如下图所示:,目录项:,重写位(1位),处理机位(N位),处理机位表示相应处理机的Cacheblock的状态(存在或不存在)。有一个也只有一个处理机位为“1”,那么该处理机可以对该块进行写操作。,全映射目录,Cache的每个块有两个状态位:有效位有效块是否允许写,有效,1位,Cache的状态位应该和目录项的状态一致。,1位,允许写,目录项:,重写位(1位),处理机位(N位),Cache状态位:,我们来看三台处理机(三个Cache)的例子。a)C1,C2,C3都没有单元X的副本,SharedMemory,x:,c,0,0,0,data,C1,P1,C2,P2,C3,P3,B.目录的三种情况,b)C1,C2,C3同时请求X单元的副本,这时目录项中的三个指针(处理机位)被置一,表示这些Cache中已有数据副本。目录项的重写位被置为未写(c)状态,表示无一处理机允许写入该数据块。,SharedMemory,x:,c,1,1,1,data,x:,P1,x:,P2,x:,P3,C1,C2,C3,c)C3请求对该块的写允许权时出现第(3)种情形,重写被置成D状态,且有一个指针指向C3的数据块。,SharedMemory,x:,D,0,0,1,data,P1,P2,x:,P3,C1,C2,C3,data,P3向C3发出写请求时:(1)C3检测出包含单元X的块是有效的,但Cache中的块允许位状态表示不允许处理机对该块进行写操作。(2)C3向包含单元X的存储器模块发出写请求,并暂停P3工作。(3)该存储器模块发出一个无效请求给C1和C2(根据目录项的内容发几个无效信号)(4)C1和C2收到无效请求后,把相应位置1,表示含单元X的块已无效,并发送一个回答信号给请求的存储器模块。(5)存储器模块收到回答信号后,将重写位置1,清除指向C1、C2的指针,发出允许信号给C3。(6)C3收到写允许信号后,修改Cache的状态并激活处理机P3。,C.第二种情况第三种情况的过程,假设存储器大小和处理机台数N成正比,即台数增加时,存储器的模块数也增加,所以数据块的个数也和N成正比。另外目录项的大小也和处理机台数N成正比,所以目录的总所占空间和N2成正比。即:目录项数*项大小=O(N2)太大不便于扩展。,D.目录所占空间,解决目录过大的问题。任意一个数据块在Cache中同时存在的副本数量有一定限制,那么目录大小的增加不会超过一个常数。,有限目录,有限目录中指针不是每台处理机一位,而是针对处理机的二进制标识符进行编码,所以指针占log2N位存储器。在全映射方式中,每个处理机对应一个指针,所以N台处理机一共用了N位,而有限目录中只用log2N位,设N=16,则log216=4。如果允许两个指针,则需要8位。所以目录的存储容量为O(Nlog2N),比全映射容易扩充。,除了多于i个Cache请求读一个特定的数据块的情况外,有限目录协议与全映射协议类似。,如果多处理机系统中的处理机具有局部性,即在任何给定的时间间隔内,只有一小部分处理机访问某个给定的存储器字,那么有限目录足以应付这个小的工作处理机组了。,用目录指针链来跟踪共享数据副本。两种方法,单链法与双链法。数据块共享副本的数目并无限制。所占的空间及可扩展性同有限目录。它的工作原理如下过程所示。,链式目录,a)P1要读单元X,则memory发送一份副本给C1,同时送给C1一个链结束指针(CT:ChainTermination),存储器也保存指向C1的指针。,SharedMemory,x:,c,data,P1,P2,P3,C1,C2,C3,x:,CT,data,b)当P2要读单元X时,存储器送一份副本给C2,同时送给C2一个指向C1的指针,存储器保存指向C2的指针。,SharedMemory,x:,c,data,P1,P2,P3,C1,C2,C3,x:,CT,data,x:,data,c)重复以上步骤,所有Cache都得到单元X的副本。d)如果P3要对单元X进行写操作,它必须沿着链发送一个数据无效信息。为了保证顺序一致性,在有链结束指针的处理机回答无效信号之前,存储器模块不给P3写允许权。无效命令从一个Cache到一个Cache顺序进行,不象snoopy协议那样同时发送给所有Cache。,e)替换:假设C1到CN都有单元X的副本,还假设单元X和单元Y都映射到同一个高速缓存块(直接映射法)。如果处理机Pi要读单元Y,它首先必须把X所在的块从Cache中去掉,这可以采用两种方法:1)沿着链发一个消息使Ci+1的指针指向Ci-1,这样使Ci从链中去掉(这时Ci中存放Y了)。2)使Ci+1到CN中的单元X无效(这时Ci中存放Y了)。,目录占用的存储容量:指针的尺寸以处理机数目的对数关系增长(这和有限目录相同)log2N,每个Cache块的指针数目与处理机个数无关。,8.2.3集中共享存储器式多处理器体系结构的Cache一致性,(1)实施一致性的基本机制,多处理器的一致性和I/O的一致性问题,虽然起源相近,但有不同的特征,使得解决方法也不相同。在I/O情况下多重数据拷贝很少发生,而一个运行于多处理器上的程序可能需要在若干个Cache中保留同一数据的拷贝。在一致性的多处理器中,Cache提供了共享数据项的迁移(migration)和复制(replication)两种功能。我们称一致性Cache提供了迁移功能。因为一个数据项可以移到一个本地Cache中,并且在本地Cache使用该数据项是透明的;这也减少了访问一个异地共享数据的延时。一致性Cache还提供了复制共享数据的手段,使共享数据能被同时读取,这是因为Cache拷贝了在本地Cache中的数据项。复制功能降低了访问延时和读取共享数据项时的竞争。支持迁移和复制对访问共享数据的性能来说至关重要。,多处理器维护一致性的协议被称为Cache一致性协议(cache-coherenceprotocols)。实现Cache一致性协议的关键是跟踪每一个共享数据块的状态。有两类协议分别使用不同的技术跟踪共享状态:1.基于目录(directorybased)的协议物理存储器内数据块的共享状态只保留在一个称为目录的地方。2.监听(snooping)协议包含有物理存储器数据块的备份的Cache也含有该数据块的共享状态的备份,即不集中保存状态。Cache通常连在一条共享存储器的总线上,所有Cache控制器监控或监听(snoop)总线以确定它是否含有总线上所请求的数据块的一个备份。监听协议已广泛的应用在使用微处理器和将Cache连接到单个共享存储器的多处理器系统中,因为这些协议可以使用已有的物理连接存储器总线来检查Cache的状态。,(2)两种监听协议,有两种方法来维护处理器的一致性:写时无效协议(writeinvalidateprotocol)写时更新协议(writeupdateprotocol)写时无效协议概念:在多处理器结构中,一个处理器数据在对一个数据项进行写操作时,其它处理器对这个数据项拷贝值作无效处理,即保证处理器能进行独占访问。因为写操作要求作独占访问,那么读处理器所拥有的任何拷贝必须作为无效处理(这也是该协议名称的由来)。当发生读操作时,就会出现Cache失配,必须取得数据的新拷贝。,写时无效协议,对于写操作,我们要求写处理器作独占访问,防止其它处理器同时写该数据项。如果两个处理器真的同时企图写同一个数据项,则二者之一将成功,另一个处理器的拷贝值作为无效处理。另一处理器要想完成它的写操作,必须得到该数据的新的拷贝,即修改过的值。因此,这个协议强制实行写操作的串行化。为了理解写时无效协议是如何保证处理器一致性的,现讨论一次写操作后紧跟另一处理器的一次读操作的情况,表8-3表示一个写时无效协议的工作过程,这里采用监听总线和回写Cache。,表一个工作在监听总线上的回写Cache的写时无效协议的工作过程,表分析:1.开始时表中存储单元X的初值为0,没有一个Cache拥有X的值。表的空格表示无动作,或Cache中无备份值,CPU栏和存储器栏的值是指处理器和总线动作结束后的值。2.当CPUA和B分别读X的值时,都先失配,然后把X的值分别读到各自的Cache中。3.CPUA要将1写入X,它先把“1”写入自己的Cache中,并将CPUB的Cache中拥有的X值的备份作无效处理,此时“1”还未回写到存储器中,而在此时CPUB请求对X的读操作,CPUB读操作失配,这一情况被在总线上监听的CPUA监听到,故由它提供X新值,同时更新CacheB和存储器中X单元的值。,写时更新协议,另一种可保证处理器一致性的协议则是当数据项被改写时,修改它在所有Cache中的备份,这种协议称为写时更新(writeupdate)或写时广播(writebroadcast)协议。为了保证该协议对带宽需求加以控制(根据定义当数据项被改写时,修改它在所有Cache中的备份),需要跟踪检查Cache中的字是否是共享的,也就是检查它是否包含在其它Cache中,如果该字不是一个共享字,则无必要广播到其它Cache中,即无必要更新其它Cache。,写时更新协议表表示了一个写时更新协议操作的例子。表存储单元的初值为0,开始时没有一个Cache拥有X的值。CPU栏和存储器的值是指处理器和总线的动作结束后的值。表中的空格表示无动作或无备份值。当CPUA进行写时广播时,CacheB和存储器中X单元的值同时被更新。,2.2两种监听协议,表一个工作在监听总线上的回写Cache的写时更新协议的工作过程,两种监听协议的性能比较,在这些协议出现后的十几年里,写时无效一直占据主导地位,原因在于两种协议性能的差异,其表现在三个方面:1.对同一字进行多次写操作而中间无读操作情况下,在写时更新协议中要求作多次写广播,但在写时无效协议中只需要作一次最初的无效处理。2.对于多个字的Cache数据块,在写时更新协议中需要对每一个写入的字都进行写广播,而在写时无效协议中只需在写第一个字时作一次无效处理。写时无效协议可以对Cache块进行操作,而写时更新协议必须对单个字进行操作(当写字节时则是对字节操作)。3.一个处理器对一个字的写操作到另一个处理器对该被写值的读操作之间的间隔在写时更新机制中比较短,因为被写的数据立即就在读处理器的Cache中被修改了(假设读操作的处理器含有该数据的拷贝)。而在写时无效协议中,读处理器首先被无效处理,然后再读取该数据,处理器将停顿到该数据能被到为止,再返回给读处理器。,由于总线和存储器带宽通常是基于总线的多处理器考虑最多的因素,写时更新协议对带宽需求较高,因而写时无效协议几乎成为所有现实的选择。写时更新协议还会引起存储器连贯性问题。在处理器个数很少时(2-4个),处理器是紧耦合的,因此更新所需的高的带宽要求是可以接受的。然而,从处理器性能提高和带宽需求相应增加的趋势,可以预计更新机制将更新机制将很少被采用。,(3)基本实现技术,在一台小规模机器中实现写无效协议的关键是使用总线来完成无效化机制。为完成无效化机制,处理器只要访问总线,并在总线上广播将被无效处理器的地址。所有处理器不断监听总线上的地址,处理器不断检查总线上的地址是否它们自己的Cache中,如果是在Cache中,则相应的数据被无效处理。被总线强制实行的访问串行化也强制实施了写操作的串行化,因为当两个处理器对同一单元竟争写操作时,其中一个必须先得到总线访问权。首先得到总线访问权的处理器将使其它处理器的拷贝被无效处理,这就使写操作严格串行化了。这种机制意味着对共享数据项的写操作只有在它得到总线访问权时才能完成。,除了对被写Cache块的其它拷贝进行无效操作外,我们还需要在Cache失配时能找到有效数据项。在直写(write-through)Cache中,很容易找到一个数据项的最近写入的值,因为所有被写的数据总是被送回到存储器去,从那里可以得到一不管数据项的最近的值。但是,对回写(write-through)Cache,找到最近的数据值的问题要复杂一些,因为一个数据项的最新值可能在cache中而不是在存储器中。幸好,回写Cache可以使用写操作同样的监听机制处理cache失配:每个处理器监听总线上的每个地址,如果一个处理器发现它含有所请求Cache的最新拷贝,它就对读请求作出反应,提供该Cache块,并终止存储器访问。虽然复杂性略有提高,但回写Cache对存储器带宽要求较低,所以在多处理器中被普遍采用。因此,我们集中讨论回写Cache的实现。,普通Cache的标志(tag)域可以用来实现监听过程,另外每个数据块的有效(valid)位使得无效处理易于实现。对读失配(readmisses),不论是由无效处理产生的还是其它事件产生的,都很容易实现,因为它们仅依赖于监听功能。对写操作我们需要知道该数据块有没有被其它Cache所拷贝,因为如果没有被其它Cache拷贝,则写操作不必在回写Cache中被放到总线上去。不发送写操作则既减少写操作所花时间又降低了带宽需求。,为了跟踪检查一个Cache数据块是否共享,我们可以给每个Cache块增加一个状态位,正如我们采用有效位和“脏”(dirty)位一样,增加一个位可以表明该块是否共享,从而使我们可以确定一个写操作是否要生成无效操作。当对一个共享状态的块进行写操作时,Cache在总线上生成一次无效操作,并将该块标记为私有。对该数据块,处理器将不再发送无效信号。含有Cache块的唯一备份的处理器称为该Cache块的拥有者(owner)。当无效操作信号送出时,拥有者的Cache块状态由共享变成非共享的(或独占的)。如果后来的另一处理器请求该Cache块,则状态又必须重新设为共享,因为监听的Cache能看到所有的失配事件,它知道非共享块何时已被另一处理器所请求,并将状态改为共享。,因为每个总线周期要检查Cache地址的tag域,这可能会干扰CPU对Cache的访问。存在两种减少这种潜在干扰的技术:复制tag域或使用具蕴涵(inclusion)特性的多级Cache。这里离CPU近的Cache是离CPU远的Cache的一个子集。如果tag域被复制,则CPU操作和监听行为可以并行地进行。当然,在发生Cache失配时处理器需要作出判断并更新这两套tag域。类似地,如果监听过程发现了一个匹配的tag域,它需要作出判断并访问两套Cache的tag域,或许还需要访问Cache数据阵列去检索数据块的备份。这样,带复制tag处理器只有在它访问Cache,并且监听过程同时检测到Cache中有备份时,才需要停顿下来,而且,监听动作只有在处理Cache失配时才会被推迟进行。,如果CPU使用具蕴涵特性的多级cache,则一级Cache的每一项也在二级Cache中,这样,监听行为可以直接对二级Cache进行,而大多数处理器操作则直接对一级Cache进行。如果监听过程在二级Cache中命中,则它必须仲裁一级Cache作出判断以更新状态,可能还需要检索数据,这时通常需要停顿处理器。由于许多多处理器采用多级Cache来降低单个处理器多带宽的要求,所以这种方案在很多设计中被采纳。有时候着一方案甚至可用于复制二级Cache的tag域以进一步减少CPU操作和监听行为之间的竞争。,我们可能已经想到,Cache一致性会有许多不同的实现方案,这取决于采用的是写时无效还是学时更新机制,Cache是回写的还是直写的,何时进行更新,是否具有拥有关系,以及拥有关系是如何记录的等等。表总结了一些监听Cache一致性协议,并标明了使用或曾使用过这些协议的机器。,5种监听协议,(4)协议实例,基于总线的一致性协议一般通过在每个处理器节点里加设一个有限状态控制器来实现。该控制器对来自处理器和总线的请求作出反应,改变选中的Cache数据块的状态,通过总线访问数据或使它无效。表8-6表明对节点中处理器-Cache模块生成的和从总线来的请求的处理,Cache一致性机制在接到处理器和总线来的请求后,将根据请求的类型和所指定的Cache数据块的状态作出响应。为简单起见,我们解释的协议不区分共享Cache块的写命中和写失配:在这两种情况下,我们均将该访问认作是写失配。当写失配消息送到总线上时,任何拥有该Cache块备份的处理器将标记该块为无效。若是回写Cache,如果该数据块只存在于一个Cache中,那个Cache也将回写该数据块。将共享块写命中作为Cache失配处理减少了总线周期的类型,并简化了控制器。,一致性协议中对从处理器和总线来的请求的处理,基于从CPU请求的Cache状态转换,无效,共享(只读),互斥(读/写),无效,共享(只读),互斥(读/写),基于从CPU请求的Cache状态转换,CPU读,总线上“读失配”,总线上“写失配”,CPU写,CPU读失配写回块,CPU写失配回写Cache块总线上出现“写失配”,总线上放读失效,CPU读失效,该块写失配,该块写失配,回写块:放弃存储器访问,该块读失配,图一个回写Cache的写时无效Cache一致性协议的工作过程,CPU写命中、读命中,回写块:放弃存储器访问,图表示采用写时无效协议和回写Cache时单个Cache块的有限状态图。图中圆圈表示被处理器或总线请求选中的Cache块所处的状态。圈中用括号加注的表示那些不导致状态转换的CPU对Cache的访问。沿着箭头线用体字标注的是导致状态转换的条件,而黑体斜字表示状态转换所产生的总线动作。导致状态转换的激励动作是针对Cache中的数据块的,而不是针对Cache中某一地址的。因此,在共享状态中读失配是针对该Cache数据块的失配,而不是针对另一地址。为简单起见,我们重画了协议的三个状态得到左右两张图,左边代表CPU请求读写时的状态转换,右边则是基于总线请求的状态转换图。当出现总线操作事件时,所有含有总线操作事件所指数据块的Cache将按右图动作。按Cache一致性协议规定:当访问一个在所有Cache中均已被清除的数据块而出现读失配时,将由主存储器提供数据。在协议实现时,这两张状态图是合并在一起的。,2.4协议实例,该Cache协议的所有状态都是一个单处理器Cache所必需的,它们分别对应于无效、有效且干净(clean)和脏(dirty)状态,图8-3左半图中所有箭头线所表示的状态改变也是单处理器中回写Cache所需要的;具有Cache一致性的多处理器与单处理器唯一不同的是控制器必须在写命中一个共享Cache块时生成一个写失配。图8-3右半图中的箭头线所表示的状态改变只是一致性Cache所需要的,因而不会在一个单处理器Cache控制器中出现。,无效,共享(只读),互斥(读/写),写回块,块写失配,CPU写命中、读命中,CPU写失配,回写数据,总线上,“写失配”,CPU写,CPU读失配,写回块,块读失配写回块,总线上,“读失配”,CPU读失配,CPU读命中,总线上,“写失配”;CPU写,该块写失配,CPU读,总线上“读失配”,图8-4Cache一致性状态图,事实上,每个Cache只有一个有限状态机,其外部激励来自相连的CPU或是总线。图8-4表示图8-3左、右半图的状态变化合在一起形成每个Cache块的单一状态图。为了理解该协议为什么能工作,我们可以看到任何有效的Cache块要么在多个Cache中处于共享状态,要么在某个Cache中处于互斥读/写状态。任何向互斥读/写状态的转换(这是处理器写该块所导致的),都要送一个写失配信号到总线上,使其它所有Cache作废该块的拷贝。另外,如果某一些Cache中该块的拷贝处于互斥读/写状态,则那个Cache产生一个回写(writeback),回写要提供所需地址。最后,如果在总线读一个处于互斥读/写状态的数据块时发生读失配,那么拥有该数据块的Cache要把该块的状态改为共享(shared),强制随后对该块的写操作申请对该块互斥读/写的所有权。图8-4中细体字所标注的动作将处理总线上的读/写失配操作,本质上是协议的监听部分。黑体标注的则是本地处理器引起状态转换的动作。该协议中保留的另一特性,也就是大多数其它协议所具备的特性是处于共享状态的任何存储器数据块总是在存储器中保留最新值。这使实现得以简化,正如我们将在8.4节中看到的那样。,虽然我们介绍的简单Cache协议是正确的,它作了一些省略。这中间最重要的是协议假设所有操作是原子的(atomic),就是说,一个操作可以不被其它操作打断而完成。例如,上述协议假设检测到写失配、请求总线并得到响应是一原子操作。事实却不是这样。类似地,如果我们使用一条分离的总线,那么读失配也不是原子的。这时需要修改协议使其达到正确,非原子(nonatomic)动作还引入了协议死锁(deadlock)的可能性。前面已经讲过,该一致性协议事实上比实际使用的协议要简单。因为作了两个简化。,第一,假定该协议中任何进入互斥读/写状态的操作都会在总线上产生一个写失配,并且我们假定发出请求的Cache总是用返回内容填充该块,这就简化了实现。大部分实用的协议分别处理写失配和写命中的,后者在Cache块最初处于共享状态时可能出现。这些失配被称为所有权(ownership)失配或更新(upgrade)失配,因为它们牵涉到块状态的改变,但不需要实际取数据。为了支持这样的状态改变,协议在写失配上附加一个无效处理操作(invalidateoperation),加了这样的操作后,协议的实现会变得复杂些。第二个简化在于很多机器是分别处理真正共享的Cache块和以干净(clean)状态只存在于一个Cache中的数据块,增加这一“干净和私有”状态可在写这样的数据块时消除总线操作事件的必要性。另一种广泛使用的增强功能是允许其它Cache在访问共享块失配时提供数据。,8.2.4分布共享存储器式多处理器体系结构,基本目录的Cache一致性协议基础目录协议示例基于目录的一致性协议性能,支持共享存储器的可扩展并行计算机(scalablemachine)有直接支持和不支持Cache一致性的两种方案。采用简单硬件的往往不支持Cache一致性,而把重点放在可扩展存储器系统上。许多公司都生产了这种类型的计算机,CrayT3D是其中最著名的一种。,CrayT3D在这种计算机中,存储器分布在并行计算机的各节点上,各节点再通过一个网络连接起来,节点中的控制器分析所存取的存储单元地址,判断是直接在本节点的存储器中存取还是要启动一次远程的存取,如果是后者,就发一个消息到拥有此存储单元的节点,通过此节点进行存取。优点这样的系统引入了Cache,但避开了Cache的一致性问题。系统只在Cache中存放每个节点独自使用的专用数据,而不存放共享数据,当然仍然可以通过软件把共享数据存入Cache:软件可以把数据从地址空间共享区拷贝到本地专用数据存放区,Cache的一致性则由软件负责。这样做的好处是几乎不需要硬件支持。但若增加一个块拷贝的硬件功能会使软件运行得更有效率,否则远程访问时每次只能存取一个字或两个字。,缺点首先,编译器很难实现透明的Cache一致性维护,只有那些结构化非常好的循环级并行(loop-levelparallelism)程序才能在现有的技术手段下实现透明的Cache一致性维护,而对于不规则的问题或者是需要用到动态数据及指针的程序(包括操作系统),目前还无法做到基于编译器的由软件维护的Cache一致性。根本的困难在于基于软件的Cache一致性维护算法必须是一个保守算法,即每个可能被共享的数据块必须像它真的被共享了一样的可以对待,这就导致了多余的开销,因为编译器不能准确地预测数据的共享;而要求应用程序的编程者来处理一致性问题是不可行的,因为可能需要的交互操作是很复杂的。,缺点其次,没有Cache一致性,计算机就失去了只用存取存储器中一个字的时间来存取Cache数据块中几个字的好处。每次访问从远程存储器一个字一个字地存取的方式,使计算机无法利用共享数据所具有的空间局部性的好处。在存储器间提供DMA可以改善这一状况,但这会付出的时间(DMA的使用常常必须经过操作系统)或者金钱(需要专用硬件和缓冲器)上的高昂代价;另外,DMA仅在需要传递大块数据时才是有用的。,缺点最后,如果能保证Cache的一致性,就可以有效地实施一些减少延时的手段,如预取等,没有Cache一致性就无法实施这些有效的手段。这些缺点造成了存取远程节点上的存储器与存取本地存储器所需时间的重大差异。比如,在CrayT3D上,对本地存储器的访问只需2个时钟周期的延时,并且可以进行流水线操作;而对其它节点上存储器的存取则需150个时钟周期。,结论因此,对

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论