第5章存储系统.

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