计算机组成与系统结构课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,计算机组成与系统结构,3.4,高速缓冲存储器（,CACHE,）,计算机组成与系统结构,陈,泽,宇 副教授,第,1,章 计算机系统概论,第,2,章 运算方法和运算器,第,3,章 存储系统,第,4,章 指令系统,第,5,章 中央处理器（,CPU,）,第,6,章 总线系统,第,7,章 输入输出（,I/O,）系统,第,8,章 并行计算机系统,3.4,高速缓冲存储器（,CACHE,）,3.4.1 Cache,基本原理,3.4.2,地址映射,3.4.3,替换策略,3.4.4,写操作策略,计算机系统中，,CPU,的运行速度与主存的访问速度极不匹配,800MHz Pentium III CPU,一条指令的执行时间约为,1.25ns,，而,133MHz SDRAM,的存取时间为,7.5ns,在,83%,的时间内,CPU,都处于,等待状态,，运行效率极低,为提高,CPU,利用率，现代计算机体系结构中广泛采用,高速缓冲存储器（,Cache,）,技术,3.4.1 Cache,基本原理,程序访问的局部性,程序员通常采用模块化的程序设计方法，某一模块的程序往往集中在存储器逻辑地址空间中很小的一块范围内，且程序,地址分布,是,连续,的,CPU,在一段较短的时间内，是对连续地址的一段,很小,的主存空间,频繁,地进行,访问,，而对此范围以外地址的访问甚少,高速缓冲存储器（,Cache,）技术,利用程序访问的局部性原理，把程序中正在使用的部分（,活跃块,）存放在一个小容量的高速,Cache,中，,使,CPU,的访存操作大多针对,Cache,进行,解决高速,CPU,和低速主存之间速度不匹配的问题,，使程序的执行速度大大提高,1. Cache,的功能,Cache,是,介于,CPU,和主存之间,的小容量存储器,存取速度比主存快，接近,CPU,能高速地向,CPU,提供指令和数据，提高程序的执行速度,Cache,是主存的缓冲存储器,由高速的,SRAM,组成,所有控制逻辑全部由,硬件实现,，对程序员而言是透明的,有些,CPU,内置,Cache,，出现了两级以上的多级,Cache,系统,Cache,系统与,CPU,和主存的关系,FLASH,演示,2. Cache,的基本原理,CPU,与,Cache,之间的数据交换以,字,为单位,Cache,与主存之间的数据交换以,块,为单位,一个块由若干个定长字组成,当,CPU,读取主存中的一个字时，该字的主存地址被发给,Cache,和主存,Cache,控制逻辑依据地址判断该字当前,是否存在于,Cache,中,若在,，该字立即被,从,Cache,传送给,CPU,；,若不在,，则用主存读周期把该字,从主存,读出送到,CPU,同时把含有这个字的,整个数据块,从主存读出,送到,Cache,中,并采用一定的,替换策略,将,Cache,中的某一块替换掉（,替换算法由,Cache,管理逻辑电路来实现）,Cache,原理图,FLASH,演示,按内容寻址的,相联存储器,（表）,用于,存放,与,Cache,中数据相对应的,主存地址,可以,快速检索,、判断,CPU,读取的某个字当前是否存在于,Cache,中,3. Cache,的命中率,基于程序访问的局部性原理，,增加,Cache,使要访问的数据,绝大多数都可在,Cache,中找到,这样才能在性能上使,主存的平均读出时间尽可能接近,Cache,的读出时间,Cache,的工作效率通常用“,命中率,”来表示,命中率：,CPU,要访问的信息在,Cache,中的概率,Cache,的命中率越高，,CPU,访问主存的速度就越接近访问,Cache,的速度,通常,Cache,的容量越大，存储的块也越多，,CPU,的命中率就越高,但是，当,Cache,的容量达到一定值时，命中率并不会随着容量的增大而增加，而成本却相应增加,所以，,Cache,的容量一般是命中率与成本价格的折中,在一个程序执行期间，,设,Nc,表示,Cache,完成存取的总次数，,Nm,表示主存完成存取的总次数，,h,定义为,命中率,，则有,若,tc,表示命中时的,Cache,访问时间，,tm,表示未命中时的主存访问时间，,1-h,表示未命中率，则,Cache,主存系统的平均访问时间,ta,为：,设,e,表示,访问效率,，则有,为提高访问效率,e,，,命中率,h,越接近,1,越好,【,例,3-1】CPU,执行一段程序时，,Cache,完成存取的次数为,1900,次，主存完成存取的次数为,100,次，已知,Cache,存取周期为,50ns,，主存存取周期为,250ns,，求,Cache,主存系统的效率和平均访问时间。,【,解,】Nc=1900,，,Nm=100,，,tc=50ns,，,tm=250ns,命中率,h=Nc/(Nc+Nm)=1900/(1900+100)=0.95,平均访问时间,ta= htc+(1-h)tm,= 0.9550+(1-0.95)250 = 60ns,效率,e=tc/ta=50/60=83.3%,3.4.2,地址映射,Cache,的容量很小，保存的只是主存内容的一个,子集,，且,Cache,与主存的,数据交换,是,以块为单位,的,为了把信息放到,Cache,中，必须应用某种函数把主存地址定位到,Cache,中，这称为,地址映射,CPU,执行程序时，会将程序中的主存地址变换成,Cache,地址，这个变换过程叫做,地址变换,假设某台计算机,主存,容量为,1MB,，被分为,2048,块，每块,512B,Cache,容量为,8KB,，被分为,16,块，每块也是,512B,1.,直接映射,直接映射的,Cache,组织,主存中的一个块只能映射到,Cache,的某一特定块中去,主存的第,0,块、第,16,块、,、第,2032,块，只能映射到,Cache,的第,0,块,主存的第,1,块、第,17,块、,、第,2033,块，只能映射到,Cache,的第,1,块,直接映射是,最简单,的地址映射方式,硬件简单，成本低，地址变换速度快，,不涉及替换算法,不够灵活，,Cache,的存储空间得不到充分利用,每个主存块只有一个固定存放位置，容易产生冲突，使,Cache,效率下降，因此只适合大容量,Cache,采用,如果一个程序需要重复引用主存中第,0,块与第,16,块，最好将主存第,0,块与第,16,块同时复制到,Cache,中,但由于它们都只能复制到,Cache,的第,0,块中去，即使,Cache,中别的存储空间空着也不能占用,因此这两个块会不断,交替装入,Cache,，导致命中率降低,2.,全相联映射,全相联映射的,Cache,组织,主存中任何一块都可以映射到,Cache,中的任何一块位置上,全相联映射方式,比较灵活，主存的各块可以映射到,Cache,的任一块中，,Cache,的利用率高,块冲突概率低,只要淘汰,Cache,中的某一块，即可调入主存的任一块,由于,Cache,比较电路的设计和实现比较困难，这种方式只适合于小容量,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,是前两种方法的,折中,方案,适度,兼顾二者的优点,尽量,避免二者的缺点,得到,普遍采用,3.4.3,替换策略,Cache,工作原理要求它尽量保存最新数据,当从主存向,Cache,传送一个新块，而,Cache,中可用位置已被占满时，就会产生,Cache,替换的问题,替换问题与,Cache,的组织方式紧密相关：,对,直接映射,Cache,来说，,只要把此可用位置上的主存块换出,Cache,即可,对,全相联和组相联,Cache,来说，,从若干可用位置中选取一个，把主存块换出,Cache,1.,最不经常使用（,LFU,）算法,LFU,（,Least Frequently Used,，最不经常使用）算法,将一段时间内被访问次数最少的那个块替换出去,每块设置一个计数器，从,0,开始计数，每访问一次，被访块的计数器就增,1,当需要替换时，将计数值最小的块换出，同时将所有块的计数器都清零,将计数周期限定在对这些特定块两次替换的间隔时间内,不能严格反映近期访问情况,新调入的块很容易被替换出去,2.,近期最少使用（,LRU,）算法,LRU,（,Least Recently Used,，近期最少使用）算法,把,CPU,近期最少使用的块替换出去,需要随时记录,Cache,中各块的使用情况，以便确定哪个块是近期最少使用的块,每块设置一个计数器，,Cache,每命中一次，命中块计数器清零，其他各块计数器增,1,当需要替换时，将计数值最大的块换出,LRU,算法相对合理，但实现起来比较复杂，系统开销较大,保护了刚调入,Cache,的新数据块，具有较高的命中率,不能肯定调出去的块近期不会再被使用，所以不能算作最合理、最优秀的算法,研究表明，采用这种算法可使,Cache,命中率达到,90%,左右,3.,随机替换,最简单,的替换算法是随机替换,完全不管,Cache,的情况，简单地根据一个,随机,数,选择一块替换出去,在硬件上容易实现，且,速度,也比前两种算法,快,缺点是降低了命中率和,Cache,工作效率,3.4.4,写操作策略,由于,Cache,的内容只是主存内容的一个子集，应当与主存内容保持一致，而,CPU,对,Cache,的写入更改了,Cache,的内容,为此，可选用,写操作策略使,Cache,内容与主存内容保持一致,1,、写回法（,Write-Back,）,当,CPU,写,Cache,命中时，,只修改,Cache,的内容,，而不立即写入主存,只有当此块被换出时才写回主存,写,Cache,和写主存异步,进行，显著减少访问主存的次数,但,存在数据不一致的隐患,实现这种方法时，每个,Cache,块必须配置一个修改位，以反映此块是否被,CPU,修改过,2,、全写法（,Write-Through,）,当写,Cache,命中时，,Cache,与主存同时发生写修改,写,Cache,和写主存同步,进行,较好地维护了,Cache,与主存的内容一致性,实现这种方法时，,Cache,中的每个块无需设置修改位以及相应的判断逻辑,由于,Cache,对,CPU,向主存的写操作,没有高速缓冲功能,，从而降低了,Cache,的功效,3,、写一次法（,Write-Once,）,写一次法是基于写回法并结合全写法的写操作策略,写命中与写未命中的处理方法与写回法基本相同,只是,第一次写命中时要同时写入主存,，以便于维护系统全部,Cache,的一致性,本讲到此结束，谢谢！,