您好,欢迎访问三七文档
1/170▲第7章存储系统2/170▲7.1存储系统的基本知识7.2Cache基本知识7.3降低Cache不命中率7.4减少Cache不命中开销7.5减少命中时间7.6并行主存系统7.7虚拟存储器7.8实例:AMDOpteron的存储器层次结构3/170▲1.计算机系统结构设计中关键的问题之一:如何以合理的价格,设计容量和速度都满足计算机系统要求的存储器系统?2.人们对这三个指标的要求容量大、速度快、价格低3.三个要求是相互矛盾的速度越快,每位价格就越高;容量越大,每位价格就越低;容量越大,速度越慢。7.1存储系统的层次结构7.1.1存储系统的层次结构4/170▲7.1存储系统的基本知识4.解决方法:采用多种存储器技术,构成多级存储层次结构。程序访问的局部性原理:对于绝大多数程序来说,程序所访问的指令和数据在地址上不是均匀分布的,而是相对簇聚的。程序访问的局部性包含两个方面时间局部性:程序马上将要用到的信息很可能就是现在正在使用的信息。空间局部性:程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的。5/170▲7.1存储系统的基本知识5.存储系统的多级层次结构多级存储层次6/170▲7.1存储系统的基本知识假设第i个存储器Mi的访问时间为Ti,容量为Si,平均每位价格为Ci,则访问时间:T1T2…Tn容量:S1S2…Sn平均每位价格:C1C2…Cn整个存储系统要达到的目标:从CPU来看,该存储系统的速度接近于M1的,而容量和每位价格都接近于Mn的。存储器越靠近CPU,则CPU对它的访问频度越高,而且最好大多数的访问都能在M1完成。7/170▲7.1存储系统的基本知识下面仅考虑由M1和M2构成的两级存储层次:M1的参数:S1,T1,C1M2的参数:S2,T2,C27.1.2存储层次的性能参数M1M2(T1,S1,C1)(T2,S2,C2)8/170▲7.1存储系统的基本知识1.存储容量S一般来说,整个存储系统的容量即是第二级存储器M2的容量,即S=S2。2.每位价格C当S1S2时,C≈C2。212211SSSCSCC++=9/170▲7.1存储系统的基本知识3.命中率H命中率:CPU访问存储系统时,在M1中找到所需信息的概率。N1──访问M1的次数N2──访问M2的次数不命中率:F=1-H211NNNH+=10/170▲7.1存储系统的基本知识4.平均访问时间TATA=HT1+(1-H)(T1+TM)=T1+(1-H)TM或TA=T1+FTM分两种情况来考虑CPU的一次访存:当命中时,访问时间即为T1(命中时间)当不命中时,情况比较复杂。不命中时的访问时间为:T2+TB+T1=T1+TMTM=T2+TB不命中开销TM:从向M2发出访问请求到把整个数据块调入M1中所需的时间。传送一个信息块所需的时间为TB。11/170▲7.1存储系统的基本知识三级存储系统Cache(高速缓冲存储器)主存储器磁盘存储器(辅存)可以看成是由“Cache—主存”层次和“主存—辅存”层次构成的系统。7.1.3三级存储系统Cache主存辅存12/170▲7.1存储系统的基本知识从主存的角度来看“Cache-主存”层次:弥补主存速度的不足“主存-辅存”层次:弥补主存容量的不足1.“Cache—主存”层次主存与CPU的速度差距“Cache-主存”层次2.“主存-辅存”层次13/170▲7.1存储系统的基本知识1980年以来存储器和CPU性能随时间而提高的情况(以1980年时的性能作为基准)14/170▲7.1存储系统的基本知识两种存储层次15/170▲7.1存储系统的基本知识存储层次CPU对第二级的访问方式比较项目目的存储管理实现访问速度的比值(第一级和第二级)典型的块(页)大小不命中时CPU是否切换“Cache-主存”层次“主存-辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现主要由软件实现几比一几万比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其他进程“Cache-主存”与“主存-辅存”层次的区别16/170▲7.1存储系统的基本知识1.当把一个块调入高一层(靠近CPU)存储器时,可以放在哪些位置上?(映象规则)2.当所要访问的块在高一层存储器中时,如何找到该块?(查找算法)3.当发生不命中时,应替换哪一块?(替换算法)4.当进行写访问时,应进行哪些操作?(写策略)7.1.4存储层次的四个问题17/170▲1.存储空间分割与地址计算2.Cache和主存分块Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。主存块地址(块号)用于查找该块在Cache中的位置。块内位移用于确定所访问的数据在该块中的位置。7.2Cache基本知识主存地址:块地址块内位移7.2.1基本结构和原理18/170▲3.Cache的基本工作原理示意图来自CPU主存地址访问主存调入一块主存地址块地址块内位移Cache地址块地址块内位移主存→Cache地址变换不命中命中Cache存储体至CPU主存Cache20/170▲7.2.2映象规则1.全相联映象全相联:主存中的任一块可以被放置到Cache中的任意一个位置。对比:阅览室位置──随便坐特点:空间利用率最高,冲突概率最低,实现最复杂。7.2Cache基本知识21/170▲7.2Cache基本知识22/170▲7.2Cache基本知识2.直接映象直接映象:主存中的每一块只能被放置到Cache中唯一的一个位置。(循环分配)对比:阅览室位置──只有一个位置可以坐特点:空间利用率最低,冲突概率最高,实现最简单。对于主存的第i块,若它映象到Cache的第j块,则:j=imod(M)(M为Cache的块数)23/170▲设M=2m,则当表示为二进制数时,j实际上就是i的低m位:ji:m位7.2Cache基本知识24/170▲7.2Cache基本知识25/170▲3.组相联映象组相联:主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。组相联是直接映象和全相联的一种折衷26/170▲7.2Cache基本知识组的选择常采用位选择算法若主存第i块映象到第k组,则:k=imod(G)(G为Cache的组数)设G=2g,则当表示为二进制数时,k实际上就是i的低g位:低g位以及直接映象中的低m位通常称为索引。ki:g位27/170▲7.2Cache基本知识n路组相联:每组中有n个块(n=M/G)。n称为相联度。相联度越高,Cache空间的利用率就越高,块冲突概率就越低,不命中率也就越低。绝大多数计算机的Cache:n≤4想一想:相联度一定是越大越好?全相联直接映象组相联n(路数)G(组数)MM111<n<M1<G<M28/170▲7.2Cache基本知识当CPU访问Cache时,如何确定Cache中是否有所要访问的块?若有的话,如何确定其位置?1.通过查找目录表来实现目录表的结构主存块的块地址的高位部分,称为标识。每个主存块能唯一地由其标识来确定7.2.3查找算法主存地址:块内位移索引标识块地址30/170▲7.2Cache基本知识只需查找候选位置所对应的目录表项31/170▲7.2Cache基本知识2.并行查找与顺序查找提高性能的重要思想:主候选位置(MRU块)(前瞻执行)3.并行查找的实现方法相联存储器目录由2g个相联存储区构成,每个相联存储区的大小为n×(h+log2n)位。根据所查找到的组内块地址,从Cache存储体中读出的多个信息字中选一个,发送给CPU。32/170▲7.2Cache基本知识33/170▲7.2Cache基本知识34/170▲7.2Cache基本知识从2g组中选择一组h位g位标识索引相联比较……总容量:2g×n项组内块地址(log2n位)n个项标识存储器35/170▲7.2Cache基本知识单体多字存储器+比较器举例:4路组相联并行标识比较(比较器的个数及位数)4路组相联Cache的查找过程直接映象Cache的查找过程优缺点不必采用相联存储器,而是用按地址访问的存储器来实现。所需要的硬件为:大小为2g×n×h位的存储器和n个h位的比较器。当相联度n增加时,不仅比较器的个数会增加,而且比较器的位数也会增加。36/170▲7.2Cache基本知识37/170▲7.2Cache基本知识38/170▲7.2Cache基本知识39/170▲7.2Cache基本知识例子:DEC的AlphaAXP21064中的内部数据Cache1.简介容量:8KB块大小:32B块数:256映象方法:直接映象写缓冲器大小:4个块7.2.4Cache的工作过程2.结构图41/170▲7.2Cache基本知识3.工作过程“读”访问命中(完成4步需要2个时钟周期)Cache的容量与索引index、相联度、块大小之间的关系Cache的容量=2index×相联度×块大小把容量为8192、相联度为1、块大小为32(字节)代入:索引index:8位标识:29-8=21位“写”访问命中42/170▲7.2Cache基本知识设置了一个写缓冲器(提高“写”访问的速度)按字寻址的,它含有4个块,每块大小为4个字。当要进行写入操作时,如果写缓冲器不满,那么就把数据和完整的地址写入缓冲器。对CPU而言,本次“写”访问已完成,CPU可以继续往下执行。由写缓冲器负责把该数据写入主存。在写入缓冲器时,要进行写合并检查。即检查本次写入数据的地址是否与缓冲器内某个有效块的地址匹配。如果匹配,就把新数据与该块合并。43/170▲7.2Cache基本知识发生读不命中与写不命中时的操作读不命中:向CPU发出一个暂停信号,通知它等待,并从下一级存储器中新调入一个数据块(32字节)。写不命中:将使数据“绕过”Cache,直接写入主存。对比:AlphaAXP21264的数据Cache结构容量:64KB块大小:64字节LRU替换策略主要区别采用2路组相联采用写回法没有写缓冲器=?块内位移6标识索引块地址有效位标识数据19②…299(512块)(512块)29=?③②…③…64…2:1多路选择器CPU数据数据输入输出地址①21264牺牲缓冲器下一级存储器④45/170▲7.2Cache基本知识1.替换算法所要解决的问题:当新调入一块,而Cache又已被占满时,替换哪一块?直接映象Cache中的替换很简单因为只有一个块,别无选择。在组相联和全相联Cache中,则有多个块供选择。主要的替换算法有三种随机法优点:实现简单先进先出法FIFO7.2.5替换算法46/170▲7.2Cache基本知识最近最少使用法LRU选择近期最少被访问的块作为被替换的块。(实现比较困难)实际上:选择最久没有被访问过的块作为被替换的块。优点:命中率较高LRU和随机法分别因其不命中率低和实现简单而被广泛采用。模拟数据表明,对于容量很大的Cache,LRU和随机法的命中率差别不大。47/170▲7.2Cache基本知识2.LRU算法的硬件实现堆栈法用一个堆栈来记录组相联Cache的同一组中各块被访问的先后次序。用堆栈元素的物理位置来反映先后次序栈底记录的是该组中最早被访问过的块,次栈底记录的是该组中第二个被访问过的块,…,栈顶记录的是刚访问过的块。当需要替换时,从栈底得到应该被替换的块(块地址)。48/170▲7.2Cache基本知识近期刚访问过的块地址寄存器堆栈近期最久未访问的块地址(组内块地址)(组内块地址)(组内块地址)(组内块地址)……n个寄存器log2n位(a)用位置记录访问的先后次序(组内块地址)(组内块地址)(组内块地址)(组内块地址)……压入全部顺序下推一行被访问的块地址(经相联比较找到)(b)发生访问时所进行的操作49/170▲7.2Cache基本知识堆栈中的内
本文标题:第7章存储系统.
链接地址:https://www.777doc.com/doc-2111790 .html