高速缓冲存储器.ppt

3 高速缓冲存储器（Cache）,工作原理和基本结构 地址映象与变换 Cache存储器的LRU替换算法的硬件实现 Cache存储器的透明性及性能分析,为什么要使用Cache?,用以弥补主存速度的不足。CPU速度与主存速度相差很大（例如，一般的DRAM的工作速度比CPU慢100倍以上。Cache工作速度很高，可以将其集成到CPU内。高性能CPU通常用两级Cache,一级在CPU内，其容量比较小，速度很快，第二级在主板上，容量比较大，速度比第一级低5倍左右。Cache全部用硬件调度对所有程序员都是透明的。Cache与主存储器之间以块为单位进行数据交换。块的大小通常以在主存储器的一个存储周期内可以访问到的数据长度为限。,Cache存储系统与虚拟存储系统比较,基本结构,把主存和Cache机械等分成相同大小的块（行），块比页小得多；访问Cache的时间时访问主存时间的1/4到1/10；Cache和CPU是同类型的半导体器件；Cache-主存间的地址映像和变换，以及替换、调度算法用硬件实现，对应用程序员透明，也对系统程序员透明；,基本结构（续）,Cache在物理位置上靠近CPU，不在主存，减少传输延迟；除Cache到处理机的通路外，还设有主存到处理机的通路，因此，Cache既是Cache-主存存储层次中的一级，又是处理机和主存的一个旁视存储器；有Cache的主存系统都采用多体交叉存储器；应尽量提高Cache的访主存的优先级；,地址映象与变换,地址映象：是将每个主存块按某种规则（算法）装入（定位于）Cache,并建立主存地址与Cache地址之间的对应关系。地址变换：是主存块按照这种映象关系装入Cache后,每次访Cache，如何将主存地址变换成Cache地址。在选取地址映象方法要考虑的主要因素：地址变换的硬件容易实现；地址变换的速度要快；主存空间利用率要高；发生块冲突的概率要小,四种方式,全相联映象与变换 直接映象与变换 组相联映像与变换 段相联映象,全相联映象与变换,定义及规则映象规则：主存中的任意一块都可以映象到Cache中的任意一块。如果Cache的块数为Cb，主存的块数为Mb，映象关系共有：CbMb种。用硬件实现非常复杂在虚拟存储器中，全部用软件实现,相联目录表法变换过程，如下图。特点：冲突概率低空间利用率高地址变换复杂,直接映象与变换,定义及规则映象规则：主存中一块只能映象到Cache的一个特定的块中。计算公式：bB mod Cb，其中：b为Cache的块号，B是主存的块号，Cb是Cache的块数。整个Cache地址与主存地址的低位部分完全相同。,变换过程，如下图。特点：硬件简单冲突概率高出现大量空闲块很少使用。,地址变换过程用主存地址中的块号B去访问区号存储器把读出来的区号与主存地址中的区号E进行比较比较结果相等,且有效位为1,则Cache命中比较结果相等,有效位为0,表示Cache中的这一块已经作废比较结果不相等,有效位为0,表示Cache中的这一块是空的比较结果不相等,有效位为1,表示原来在Cache中的这一块是有用的,提高Cache速度的一种方法：把区号存储器与Cache合并成一个存储器直接映象方法的主要优点：硬件实现很简单,不需要相联访问存储器访问速度也比较快,实际上不做地址变换直接映象方式的主要缺点:块的冲突率较高,组相联映像与变换,定义及规则：各组之间是直接映象，组内各块间是全相联映象。变换过程，如下图。讨论：S=nv时，全相联映像；S=0时，直接映像；当主存空间和Cache空间确定时，q+s已确定；s值大，组内页数多，冲突概率小，变换复杂；s值小，组内页数少，冲突概率大，变换简单；,组相联映象方式的优点：块的冲突概率比较低块的利用率大幅度提高块失效率明显降低组相联映象方式的缺点：实现难度和造价要比直接映象方式高地址变换过程：用主存地址的组号G按地址访问块表存储器把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较如果有相等的，表示Cache命中如果没有相等的，表示Cache没有命中,段相联映象,减少相联目录表的容量，降低成本，提高地址变换速度。组间全相联，组内直接映象。,替换算法的实现,常采用LRU算法，LRU算法是堆栈型算法由于Cache的调块时间是微秒级，不能采用程序换道替换算法全部采用硬件途径实现,堆栈法,比较对法,让各个块成对组合，用一个触发器的状态表示该比较对内两块访问的远近次序，再经门电路就可找到LRU块。适用于组内块数较少的组相联映像Cache。,替换算法的设计要考虑的问题,如何对每次访问进行纪录（适用位法、堆栈法、比较对法所用的记录方法都不同）如何根据所纪录的信息来判定近期内哪一块是最久没有被访问过的Cache替换算法的主要特点：全部用硬件实现,Cache存储器的透明性及性能分析,Cache的透明性 Cache的取算法 Cache存储器性能分析,Cache的透明性和一致性问题,由于Cache存储器的地址变换和块替换算法全由硬件实现，因此Cache-主存存储层次对应用程序员和系统程序员都是透明的。本节讨论的内容仅限于单处理机、单存储器造成Cache与主存的不一致的原因：由于CPU写Cache，没有立即写主存由于IO处理机或IO设备写主存,Cache的透明性,写回法（抵触修改法，WB）：是在CPU执行写操作时，信息只写入Cache，仅当需要被替换时，才将以被写入过的Cache块先送回主存，然后再调入新块。写直达法（直达法，WT）：利用Cache主存存储层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。,写回法与写直达法的优缺点比较,可靠性，写直达法优于写回法与主存的通信量,写回法少于写直达法例如：写操作占总访存次数的20,Cache命中率为99%,每块4个字。当Cache发生块替换时,有30%块需要写回主存,其余的因未被修改过而不必写回主存。则对于WT法,写主存次数占总访存次数的20%。而WB法为(1-99%)*30%*4=1.2%。因此,WB法与主存的通信量要比WT法少10多倍。,写回法与写直达法的优缺点比较,控制的复杂性：写直达法比写回法简单硬件实现的代价：写回法要比写直达法好采用何种算法与适用场合有关单处理机（节省成本）：写回法共享主存的多处理机（保证信息交换可靠）：写直达法,写Cache的两种方法：不按写分配法：在写Cache不命中时，只把所要写的字写入主存。按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。,Cache的取算法,按需取进法：出现Cache块失效时，才将要访问的字所在的块（行）取进。预取法恒预取：只要访问到主存第i块的某个字，不论Cache是否命中，恒发预取命令。不命中时预取：近当访问第i块不命中时，才预取命令。采用预取法并非能提高命中率，其他因素块的大小预取开销,说明,采用缓冲器技术是减少预取干扰的好办法模拟结果表明恒预取法使不命中率降低75%-80%不命中率时预取法使不命中率降低30%-40%但前者所引起的Cache、主存间传输量的增加要比后者大得多。,Cache存储器性能分析,不命中率与Cache的容量、组的大小和快的大小的关系Cache-主存存储层次的等效速度与命中率的关系推导Cache的容量对机器速度的关系,块的大小、组的大小与Cache容量对Cache命中的影响,块的大小、组的大小及Cache容量增大时都能提高命中率,Cache-主存存储层次的等效速度与命中率的关系推导,设：tc 为Cache的访问时间，tm为主存周期，Hc为访Cache的命中率。则：Cache的等效存储周期 ta=Hc tc+(1-Hc)tm 因为：主存与CPU之间有直接通路，因此CPU对第二级的访问时间就是tm。,（续）,速度提高倍数是：因为Hc总小于1，可以令,分析,由于 因此 不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache-主存存储层次后，速度能提高的最大值是有限的，不会超过,举例,Hc=0.5,=1 的最大值2Hc=0.75,=3 的最大值4Hc=1,举例,由于Cache的命中率一般比0.9大的多，可达0.996，因此接近于所期望的tm/tcHc受Cache容量的影响很大。容量为4kb时，Hc=0.93容量为8kb时，Hc=0.97,举例,因此在tm/tc=0.12时4KB的Cache，速度的倍数是8KB的Cache，速度的倍数是增加4KB容量，带来层次速度的提高：,Cache的容量对机器速度的关系,机器速度的单位是MIPS(每秒执行百万条指令)主存采用多体交叉存取,续,主存速度和CPU周期一定时，Cache容量变化，机器速度变化。Cache容量4KB，CPU拍宽10ns，主存周期1s，机器速度约为5MPIS同样条件下，Cache容量增加到64KB，机器速度可能达15MPIS没有Cache时，机器速度可能只有2MIPS,续,Cache容量的增大，可以显著降低对主存速度的要求要达到机器速度为15MIPS，对于10ns的CPU拍宽、4KB容量的Cache，要求主存访问周期为200nsCache容量增达到64KB时，主存周期可以降低到1s,4 Cache-主存-辅存存储层次,在大部分计算机系统中，既有虚拟存储器，也有Cache存储系统。存储系统可以有多种构成方法不同的构成只是实现技术不同,存储系统的几种组织方式,两个存储系统的组织方式：物理地址Cache存储系统；目前的大部分处理机均采用这种两级存储系统,存储系统的几种组织方式（续）,一个存储系统组织方式：虚拟地址Cache存储系统；如Intel公司的i860等处理机采用这种组织方式。,全Cache系统。没有主存储器，Cache磁盘存储系统。,主存保护（选讲）,小结,存储系统与存储体系并行主存频宽的分析存储体系的性能参数虚拟存储器的管理方式四种地址映像与变换的含义与区别Cache的工作原理,