第四章 存储系统 4.3.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4.3,高速缓存,4.3,高速缓冲存储器,Cache,主存与,CPU,的速度差距,瓶颈,严重限制了计算机系统速度的提高：,CPU,访,zz,存速度与,CPU,处理速度较之主存访问速度相差一,zz,个数量级,(,10,倍以上,),！解决办法之一是使用高速,zz,的缓冲存储器,Cache,置于,Memory,与,CPU,之间。,Cache,，,这是目前用得最多的最有效的提高存储,zz,速度的主要方法。,Cache,通常由质量优良的半导体存储器组成,它,zz,与主存数据交换以,“块”为单位进行,块定长含若干,zz个字,(,字节,),。如,IBM370,机块大为,32,字节。,CPU,MEMORY,Cache,L1-Cache,地址,变换,将现行程序的一个逻辑块,Map,到,Cache,中，,CPU,在访问主存同时，访问,Cache,，若,Cache,中有所需地址，称之,命中,，访问之。如果,Cache,无欲访地址,谓之,不命中,，则对主存读写，同时把读写单元所在的整个块,Map,到,Cache.,为下步程序执行使用。,4.3.1 Cache,工作原理,Cache,在读时,Cache,利用,程序访问局部性规律：,在程序执行的过,zz,程中，近期被访问过的信息项可能马上被再次访问,zz,被访问过的地址的邻近地址可能紧接着被访问。,策略,:,将现程序运行所需的主存,的“一块”,内容,Copy,zz,(,Map,),到,Cache,CPU,访存时同时访问,Cache,访问速,zz,度高。通常,可以在,Cache,中找到,CPU,所需内容。除,zz,非运行到转移指令,或者这,块,内容运行完毕,下一步,zz,需要的内容不在,块内,才从主存读入新的一,块,继续,zz,满足,CPU,执行下一段程序之需。,工作在,“读”,状况下,Cache,工作原理概说：,Cache,读流程,含,RA,的块,在,Cache?,在主存找含,RA,的块,从,CPU,获地址,RA,Start,Done,读,Cache,中,RA内容,将块,Map,到,Cache,将,RA,字送,CPU,计算该块的,Cache,行,Y,N,“,Cache,读”,的操作流程图,Cache flowchart,I,s block,containing RA,in cache?,Access M for block,Containing RA,Get RA from CPU,Start,Done,Fetch RA word,&del,i,ver to CPU,Load M block,into cache line,Deliver RA,word to CPU,Allocate cache line,for M block,Y,N,Operation Flowchart,of,“,Cache Read,”,Note,：,RA,Address,of a word to be read,.,M,Main Memory,P.119 Fig 4.15,Cache,系统示意,块号,B,字,W,主存,-,Cache,地址变换机构,Cache,行号,L,字,W,Cache,满？,M.M,Cache,替换,机构,主存地址,调出块,调进块,Y,N,与处理机交换数据,主存地址,命中,失,效,Cache,地址,Cache,系统,图,4.41,Cache-M,系统,结构,来自处理机的主存地址,策,略,Cache,的容量很小，保存的只是主存内容的一个,子集,，且,Cache,与主存的,数据交换,是,以块为单位,的,为了把信息放到,Cache,中，必须应用某种函数把主存地址定位到,Cache,中，这称为,地址映射,CPU,执行程序时，会将程序中的主存地址变换成,Cache,地址，这个变换过程叫做,地址变换,Cache,的地址映射方式有,全相联映射、直接映射和组相联映射,假设某台计算机,主存,容量为,l MB,，被分为,2048,块，每块,512B,；,Cache,容量为,8KB,，被分为,16,块，每块也是,512B,以此为例介绍三种基本的地址映射方法,4.3.2,地址映像与变换,1.,全相联映射,全相联映射的,Cache,组织,主存中任何一块都可以映射到,Cache,中的任何一块位置上,举例,全相联映射方式,比较灵活，主存的各块可以映射到,Cache,的任一块中，,Cache,的利用率高,块冲突概率低,只要淘汰,Cache,中的某一块，即可调入主存的任一块,由于,Cache,比较电路的设计和实现比较困难，这种方式只适合于小容量,Cache,采用,全相联算法,全相联,Map,块号,块号,块号,块号,L,1,L,0,L,i,L,M,-,1,W,0,W,1,W,k-1,W,0,W,1,W,k-1,W,0,W,1,W,k-1,B,0,B,N,-,1,B,1,块号,B,字,W,比较,块内地址,主存地址,失效,命中,2.,直接映射,直接映射的,Cache,组织,主存中的一个块只能映射到,Cache,的某一特定块中去,例如，主存的第,0,块、第,16,块、,、第,2032,块，只能映射到,Cache,的第,0,块；,而主存的第,1,块、第,17,块、,、第,2033,块，只能映射到,Cache,的第,1,块,举例,直接映射是,最简单,的地址映射方式,硬件简单，成本低，地址变换速度快,不够灵活，,Cache,的存储空间得不到充分利用,每个主存块只有一个固定位置可存放，容易产生冲突，使,Cache,效率下降，因此只适合大容量,Cache,采用,例如，如果一个程序需要重复引用主存中第,0,块与第,16,块，最好将主存第,0,块与第,16块同时复制到,Cache,中,但由于它们都只能复制到,Cache,的第,0,块中去，即使,Cache,中别的存储空间空着也不能占用,因此这两个块会不断地,交替装入,Cache,中，导致命中率降低,直接相联算法,区号,区号,区号,区号,L,1,L,0,L,i,L,M,-,1,B0,B1,B7,B0,B1,B7,B0,B1,B7,E,0,E,N,-,1,块号,B,字,W,比较,直接,Map,块内地址,区号,E,E,1,主存地址,失效,命中,Cache,地址,3.,组相联映射,组相联映射实际上是直接映射和全相联映射的,折中,方案,主存和,Cache,都分组,主存中一个组内的块数与,Cache,中的分组数相同,组间采用直接映射,组内采用全相联映射,将,Cache,分成,u,组，每组,v,块,主存块存放到哪个组是固定的,至于存到该组哪一块则是灵活的,例如，,主存分为,256,组，每组,8,块,Cache,分为,8,组，每组,2,块,举例,组相联映射方式,主存中的各块与,Cache,的组号之间有固定的映射关系,但可自由映射到对应,Cache,组中的任何一块,例如,主存中的第,0,块、第,8,块,均映射于,Cache,的第,0,组，但可映射到,Cache,第,0,组中的第,0,块或第,1,块；,主存的第,1,块、第,9,块,均映射于,Cache,的第,1,组，但可映射到,Cache,第,1,组中的第,2,块或第,3,块,常采用的组相联结构,Cache,每组内有,2,、,4,、,8,、,16,块，称为,2,路、,4,路、,8,路、,16,路组相联,Cache,组相联结构,Cache,是前两种方法的,折中,方案,适度,兼顾二者的优点,尽量,避免二者的缺点,得到,普遍采用,绝大多数计算机的,Cache:,n,4,想一想：相联度一定是越大越好？,n,路组相联：每组中有,n,个块,(,n,M,/,G,),n,称为相联度。,相联度越高，,Cache,空间的利用率就越高，,块冲突概率就越低，失效率也就越低。,全相联,直接映象,组相联,n,(,路数,),G,(,组数,),M,M,1,1,1nM,1GM,组相联算法,组相联,Mapping,B1,B0,B3,E,0,E,k,E,1,B2,G0,G1,G0,G1,B1,B0,B3,B2,B1,B0,B3,B2,B1,B0,B3,B2,B1,B0,B3,B2,B1,B0,B3,B2,组号,G,块号,B,字,W,组号,G,块号,B,字,W,区号,E,Cache,地址,比较,主存地址,hit,E+B,B 1,L0,L1,L2,L3,L0,L1,L2,L3,块内地址,G0,G1,miss,替换问题,*,4.3.3,替换算法及其实现,因为,程序访问局部性规律,程序运行极大可能使用一片连续的存储字,块。,这个,块,已经,Map,到,Cache,的某个,行,。,程序运行时就是访问的就是此行。当此行内容使用完毕,程序需要访问新的行,这就需要将主存相应的,新块,Map,为,Cache,相应的,新行,。,新块,Map,到,Cache,的哪一行？也就是,替换,谁？这是个难题。通常,不替换刚刚使用过的那些行。因为“局部性规律”，刚刚访问过的内容可能马上被再次访问。保留它们以备访问。,替换,有多种算法，目的是使,Cache,有较高的效率,。,三种替换算法,下面一些算法多半是从试验得出的：,1,.,随机算法：,zz,当有替换需要，由硬件随机数发生器产生一个随机,zz,数,经非常简单的硬件计算为被替换行号,此行即被,zz,新的块替换。,2.,FIFO,法：,zz,在地址变换表中设置一个历史位,可判断哪是最先,zz,被主存的块,Map,的行,先进入者先被替换。,3.,LRU,法：,zz,选择最近没有使用过的行作为被替换者。,写回,Cache,CPU,访问,Cache,包括读,/,写。写时极可能修改被访字内容,这意味着程序运行的结果,必须写回主存。,Cache,作为主存的临时替代者,对程序运行的结果必须忠实写回主存，于是就有了写回策略。方法主要有：,1,.,写直达法,：,CPU,对,Cache,写命中时,Cache,与主存内容,zz,同时修改,此法维护了,Cache,与主存内容一致。,2.,写回法,：,CPU,对,Cache,写命中时,只修改,Cache,不修,zz,改主存。当此行被替换时将此行写回主存,3.,写一次法,：,CPU,对,Cache,写命中第一次时同时改写,zz,zz,Cache,和主存，以后的命中采用写回法。,*,4.3.4 Cache,的写策略,1.,命中率,H,C,：,N,次访问,Cache,，成功,(,命中,),次数占总访问次数的百分比。,例如访问,1000,次,有,950,次成功,，则,H,C,=,95%,一般情况有：访问,N,次,有,N,1,次命中,N,2,次不命中，,则,H,C,(,N,N,1,+,N,2,),2.,Cache,存储系统等效访问时间,T,A,：,ZXZ,T,A,T,C,H,C,+T,M,(,1,H,C,),T,C,H,C,+T,M,F,C,.,式中,T,C,：,命中时访问,cache,字的时间,；,F,C,=1,H,C,=,失效率,；,T,M,：,失效时访问,cache,字的时间,(,包括访问主存字并将该字所在的主存块,map,至,Cache,的时间,).,N,1,N,1,+,N,2,*,4.3.5 Cache,性能的评估,Cache,评估,3,3.,Cache,存储,系统的加速比,S,P,：,在没有,cache,的情况下,主存字的访问时间为,T,M,，设置,Cache,后,存储系统等效访问字时间,为,T,A,，,则,S,P,可以看出加速比是命中率,H,C,和时间比,T,C,/,T,M,的函数,要提高,Sp,的只有提高命中率,(,即降低失效率,F,C,),Cache,性能的评估,1,(,1,H,C,)+,H,C,T,C,/,T,M,T,M,T,C,H,C,+T,M,(,1,H,C,),T,M,T,A,改善,Cache,经验告诉我们,提高,Sp,较好的方法有：,1,.,适当的,Cache,容量：实,验表明,L2 Cache,容量在,128k,有,到,1M;L1,在,16k 32k,。,有很好的命中率。,2.,选用好的相联法：,Cache,和主存的,map,采用组相联方,有,式有很好的命中率。,3.,使用,Victim,（牺牲者）,Cache,：,zz,在,Cache,和下一级存储器之间,增设一个全相联的小,Victim,Cache,它存放刚刚被替换的那些块,当发生失效，在访问下一级存储器前先检查,Victim,Cache,中有否所需的块,若有,则,Map,该块入,Cache,能有效提高命中率。,提高,Cache-,Mem,存储系统加速比,