高速缓冲存储器.ppt

《高速缓冲存储器.ppt》由会员分享，可在线阅读，更多相关《高速缓冲存储器.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3 高速缓冲存储器（Cache）n工作原理和基本结构 n地址映象与变换 nCache存储器的LRU替换算法的硬件实现 nCache存储器的透明性及性能分析 为什么要使用Cache?n用以弥补主存速度的不足。nCPU速度与主存速度相差很大（例如，一般的DRAM的工作速度比CPU慢100倍以上。nCache工作速度很高，可以将其集成到CPU内。高性能CPU通常用两级Cache,一级在CPU内，其容量比较小，速度很快，第二级在主板上，容量比较大，速度比第一级低5倍左右。nCache全部用硬件调度对所有程序员都是透明的。nCache与主存储器之间以块为单位进行数据交换。块的大小通常以在主存储器的一个存

2、储周期内可以访问到的数据长度为限。存储系统两级存储器速度比Cache虚拟存储器要达到的目标提高速度扩大容量实现方法全部硬件软件为主硬件为辅310倍105倍页(块)大小116字1KB16KB等效存储容量主存储器虚拟存储器透明性对系统和应用程序员仅对应用程序员不命中时处理方式 等待主存储器任务切换Cache存储系统与虚拟存储系统比较块号块内地址主存-Cache地址映象变换机构块号块内地址Cache主存Cache替换策略来自处理机主存地址Cache地址访主存替换Cache访主存装入Cache去处理机直接通路单字宽多字宽单字宽已装不进还可装入不命中命中高速缓冲存储器Cache基本结构 n把主存和Cac

3、he机械等分成相同大小的块（行），块比页小得多；n访问Cache的时间时访问主存时间的1/4到1/10；nCache和CPU是同类型的半导体器件；nCache-主存间的地址映像和变换，以及替换、调度算法用硬件实现，对应用程序员透明，也对系统程序员透明；基本结构（续）nCache在物理位置上靠近CPU，不在主存，减少传输延迟；n除Cache到处理机的通路外，还设有主存到处理机的通路，因此，Cache既是Cache-主存存储层次中的一级，又是处理机和主存的一个旁视存储器；n有Cache的主存系统都采用多体交叉存储器；n应尽量提高Cache的访主存的优先级；地址映象与变换 n地址映象：是将每个主存块

4、按某种规则（算法）装入（定位于）Cache,并建立主存地址与Cache地址之间的对应关系。n地址变换：是主存块按照这种映象关系装入Cache后,每次访Cache，如何将主存地址变换成Cache地址。n在选取地址映象方法要考虑的主要因素：n地址变换的硬件容易实现；n地址变换的速度要快；n主存空间利用率要高；n发生块冲突的概率要小四种方式n全相联映象与变换 n直接映象与变换 n组相联映像与变换 n段相联映象 全相联映象与变换n定义及规则n映象规则：主存中的任意一块都可以映象到Cache中的任意一块。n如果Cache的块数为Cb，主存的块数为Mb，映象关系共有：CbMb种。n用硬件实现非常复杂n在虚

5、拟存储器中，全部用软件实现n相联目录表法n变换过程，如下图。n特点：n冲突概率低n空间利用率高n地址变换复杂块0Cache块1块Cb-1块0块1块i块Mb-1主存储器全相联映象方式有效位块号B块内地址主存地址目录表（由相联存储器组成，共Cb个字）主存块号BB块号b块内地址wCache块号bb相联比较命中Cache地址直接映象与变换n定义及规则n映象规则：主存中一块只能映象到Cache的一个特定的块中。n计算公式：bB mod Cb，其中：b为Cache的块号，B是主存的块号，Cb是Cache的块数。n整个Cache地址与主存地址的低位部分完全相同。n变换过程，如下图。n特点：n硬件简单n冲突概

6、率高n出现大量空闲块n很少使用。块0Cache块1块Cb-1块0块Cb-1主存储器直接相联映象方式块Cb块2Cb-1块Mb-Cb块Mb-1区0区1区Me-1n地址变换过程n用主存地址中的块号B去访问区号存储器n把读出来的区号与主存地址中的区号E进行比较n比较结果相等,且有效位为1,则Cache命中n比较结果相等,有效位为0,表示Cache中的这一块已经作废n比较结果不相等,有效位为0,表示Cache中的这一块是空的n比较结果不相等,有效位为1,表示原来在Cache中的这一块是有用的有效位区号E块内地址w1主存地址区表存储器区号E(按地址访问)E块号b块内地址w命中Cache地址块号B相等比较块

7、失效比较相等且有效位为1，访问Cachen提高Cache速度的一种方法：n把区号存储器与Cache合并成一个存储器n直接映象方法的主要优点：n硬件实现很简单,不需要相联访问存储器访问速度也比较快,实际上不做地址变换n直接映象方式的主要缺点:n块的冲突率较高有效位区号E块内地址w1按地址访问的Cache区号E块号b块内地址w相等块号B相等比较访主存数据0D0数据1D1数据w-1Dw-11/w送CPU组相联映像与变换n定义及规则：各组之间是直接映象，组内各块间是全相联映象。n变换过程，如下图。n讨论：nS=nv时，全相联映像；nS=0时，直接映像；n当主存空间和Cache空间确定时，q+s已确定；

8、ns值大，组内页数多，冲突概率小，变换复杂；ns值小，组内页数少，冲突概率大，变换简单；组内块号s区号nd块内地址W主存地址块表nd区号，组内块号s相联比较(s个块)块内地址w相等Cache地址组内块号s相联比较不等组号q组内块号s组号qn组相联映象方式的优点：n块的冲突概率比较低n块的利用率大幅度提高n块失效率明显降低n组相联映象方式的缺点：实现难度和造价要比直接映象方式高n地址变换过程：用主存地址的组号G按地址访问块表存储器n把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较如果有相等的，表示Cache命中如果没有相等的，表示Cache没有命中段相联映象 n减少相联目录表的容量，

9、降低成本，提高地址变换速度。n组间全相联，组内直接映象。替换算法的实现n常采用LRU算法，LRU算法是堆栈型算法n由于Cache的调块时间是微秒级，不能采用程序换道n替换算法全部采用硬件途径实现堆栈法(块号)(块号)(块号)(块号)(块号)近期最近访问过的块号近期最久没有访问的块号需重新排序的块号都下推一行被访问的块号（经相联比较找到）比较对法n让各个块成对组合，用一个触发器的状态表示该比较对内两块访问的远近次序，再经门电路就可找到LRU块。n适用于组内块数较少的组相联映像Cache。&TABTACTBC访问B访问C访问A000111替换算法的设计要考虑的问题n如何对每次访问进行纪录（适用位法

10、、堆栈法、比较对法所用的记录方法都不同）n如何根据所纪录的信息来判定近期内哪一块是最久没有被访问过的nCache替换算法的主要特点：全部用硬件实现Cache存储器的透明性及性能分析 nCache的透明性 nCache的取算法 nCache存储器性能分析 Cache的透明性和一致性问题n由于Cache存储器的地址变换和块替换算法全由硬件实现，因此Cache-主存存储层次对应用程序员和系统程序员都是透明的。n本节讨论的内容仅限于单处理机、单存储器n造成Cache与主存的不一致的原因：n由于CPU写Cache，没有立即写主存n由于IO处理机或IO设备写主存CPUXI/OXCache主存储器CPUXI

11、/OXCache主存储器(a)CPU写Cache(b)I/O写主存Cache与主存不一致的两种情况Cache的透明性n写回法（抵触修改法，WB）：是在CPU执行写操作时，信息只写入Cache，仅当需要被替换时，才将以被写入过的Cache块先送回主存，然后再调入新块。n写直达法（直达法，WT）：利用Cache主存存储层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。写回法与写直达法的优缺点比较n可靠性，写直达法优于写回法n与主存的通信量,写回法少于写直达法n例如：写操作占总访存次数的20,Cache命中率为99%,每块4个字。当Cache发生块替换时,有

12、30%块需要写回主存,其余的因未被修改过而不必写回主存。则对于WT法,写主存次数占总访存次数的20%。而WB法为(1-99%)*30%*4=1.2%。因此,WB法与主存的通信量要比WT法少10多倍。写回法与写直达法的优缺点比较n控制的复杂性：写直达法比写回法简单n硬件实现的代价：写回法要比写直达法好n采用何种算法与适用场合有关n单处理机（节省成本）：写回法n共享主存的多处理机（保证信息交换可靠）：写直达法n写Cache的两种方法：n不按写分配法：在写Cache不命中时，只把所要写的字写入主存。n按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。n目前，在写回法中采用按写分配法

13、，在写直达法中采用不按写分配法。Cache的取算法 n按需取进法：出现Cache块失效时，才将要访问的字所在的块（行）取进。n预取法n恒预取：只要访问到主存第i块的某个字，不论Cache是否命中，恒发预取命令。n不命中时预取：近当访问第i块不命中时，才预取命令。n采用预取法并非能提高命中率，其他因素n块的大小n预取开销说明n采用缓冲器技术是减少预取干扰的好办法n模拟结果表明n恒预取法使不命中率降低75%-80%n不命中率时预取法使不命中率降低30%-40%n但前者所引起的Cache、主存间传输量的增加要比后者大得多。Cache存储器性能分析 n不命中率与Cache的容量、组的大小和快的大小的关

14、系nCache-主存存储层次的等效速度与命中率的关系推导nCache的容量对机器速度的关系块的大小、组的大小与Cache容量对Cache命中的影响不命中率1-HcCache容量组的大小一定块的大小减小不命中率1-HcCache容量块的大小一定组的大小减小块的大小、组的大小及Cache容量增大时都能提高命中率Cache-主存存储层次的等效速度与命中率的关系推导设：tc 为Cache的访问时间，tm为主存周期，Hc为访Cache的命中率。则：Cache的等效存储周期 ta=Hc tc+(1-Hc)tm 因为：主存与CPU之间有直接通路，因此CPU对第二级的访问时间就是tm。（续）速度提高倍数是：因

15、为Hc总小于1，可以令 分析n由于 因此 n不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache-主存存储层次后，速度能提高的最大值是有限的，不会超过举例nHc=0.5,=1 的最大值2nHc=0.75,=3 的最大值4nHc=1,Hc的期望值10.50.250.751248举例n由于Cache的命中率一般比0.9大的多，可达0.996，因此接近于所期望的tm/tcnHc受Cache容量的影响很大。n容量为4kb时，Hc=0.93n容量为8kb时，Hc=0.97举例n因此在tm/tc=0.12时n4KB的Cache，速度的倍数是n8KB的Cache，速度的倍数是n增加

16、4KB容量，带来层次速度的提高：Cache的容量对机器速度的关系n机器速度的单位是MIPS(每秒执行百万条指令)n主存采用多体交叉存取机器速度(MIPS)1020302004006008001000主存访问时间(ns)无Cache 10ns4k 10ns64k 40ns16k 10ns64k 20ns64k 10nsCache CPU容量 拍宽续n主存速度和CPU周期一定时，Cache容量变化，机器速度变化。nCache容量4KB，CPU拍宽10ns，主存周期1s，机器速度约为5MPISn同样条件下，Cache容量增加到64KB，机器速度可能达15MPISn没有Cache时，机器速度可能只有2

17、MIPS续nCache容量的增大，可以显著降低对主存速度的要求n要达到机器速度为15MIPS，对于10ns的CPU拍宽、4KB容量的Cache，要求主存访问周期为200nsnCache容量增达到64KB时，主存周期可以降低到1s4 Cache-主存-辅存存储层次 n在大部分计算机系统中，既有虚拟存储器，也有Cache存储系统。n存储系统可以有多种构成方法n不同的构成只是实现技术不同Cache系统程序员看主存储器速度接近Cache的速度，存储容量是主存的容量每位价格接近主存储器Cache存储系统主存储器应用程序员看磁盘存储器速度接近主存储器的速度，存储容量是虚拟地址空间，每位价格接近磁盘存储器虚

18、拟存储系统Cache主存储器磁盘存储器一种三级存储系统Cache磁盘存储器一种新的二级存储系统存储系统的几种组织方式n两个存储系统的组织方式：物理地址Cache存储系统；目前的大部分处理机均采用这种两级存储系统CPU虚拟地址MMUCache主存储器物理地址数据或指令物理地址存储系统的几种组织方式（续）n一个存储系统组织方式：虚拟地址Cache存储系统；如Intel公司的i860等处理机采用这种组织方式。CPU虚拟地址MMUCache主存储器数据或指令物理地址数据或指令n全Cache系统。没有主存储器，Cache磁盘存储系统。主存保护（选讲）小结n存储系统与存储体系n并行主存频宽的分析n存储体系的性能参数n虚拟存储器的管理方式n四种地址映像与变换的含义与区别nCache的工作原理