计算机系统结构--第5章剖析

1/154▲5.1存储器的层次结构5.2Cache基本知识5.3降低Cache失效率的方法5.4减少Cache失效开销5.5减少命中时间5.6主存5.7虚拟存储器5.8进程保护和虚存实例5.9AlphaAXP21064存储层次第5章存储层次2/154▲1.从用户的角度来看，存储器的三个主要指标：容量、速度和价格（指每位价格）2.人们对这三个指标的要求容量大、速度快、价格低3.三个要求是相互矛盾的速度越快，每位价格就越高；容量越大，每位价格就越低；容量越大，速度越慢。5.1存储器的层次结构5.1.1从单级存储器到多级存储器3/154▲5.1存储器的层次结构4.解决方法采用多种存储器技术，构成所谓的存储层次。演示Ⅰ演示Ⅱ(局部性原理)多级存储层次4/154▲5.1存储器的层次结构C，H，TA假设：S──容量TA──访问时间C──每位价格下面仅考虑由M1和M2构成的两级存储层次：M1的参数：S1，TA1，C1M2的参数：S2，TA2，C25.1.2存储层次的性能参数5/154▲5.1存储器的层次结构1.每位价格C2.命中率H和失效率F命中率：CPU访问存储系统时，在M1中找到所需信息的概率。N1──访问M1的次数N2──访问M2的次数失效率：F＝1－H212211SSSCSCC＋＋＝211NNNH＋＝6/154▲5.1存储器的层次结构3.平均访问时间TATA＝HTA1＋（1－H）（TA1＋TM）＝TA1＋（1－H）TM或TA＝TA1＋FTM分两种情况来考虑CPU的一次访存：当命中时，访问时间即为TA1（命中时间）当不命中时，情况比较复杂。不命中时的访问时间为：TA2＋TB＋TA1＝TA1＋TMTM＝TA2＋TB失效开销TM：从向M2发出访问请求到把整个数据块调入M1中所需的时间。传送一个信息块所需的时间为TB。7/154▲5.1存储器的层次结构从主存的角度来看“Cache－主存”层次：弥补主存速度的不足“主存－辅存”层次：弥补主存容量的不足1.“Cache—主存”层次主存与CPU的速度差距“Cache-主存”层次2.“主存－辅存”层次5.1.3“Cache－主存”和“主存－辅存”层次8/154▲5.1存储器的层次结构1980年以来存储器和CPU性能随时间而提高的情况（以1980年时的性能作为基准）9/154▲5.1存储器的层次结构两种存储层次10/154▲5.1存储器的层次结构存储层次CPU对第二级的访问方式比较项目目的存储管理实现访问速度的比值(第一级和第二级)典型的块(页)大小失效时CPU是否切换“Cache－主存”层次“主存－辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现主要由软件实现几比一几百比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其他进程“Cache－主存”与“主存－辅存”层次的区别11/154▲5.1存储器的层次结构1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映像规则）2.当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）3.当发生失效时，应替换哪一块？（替换算法）4.当进行写访问时，应进行哪些操作?（写策略）5.1.4存储层次的四个问题12/154▲1.存储空间分割与地址计算2.Cache和主存分块5.2Cache的基本知识5.2.1映象规则1.全相联映象全相联：主存中的任一块可以被放置到Cache中的任意一个位置。举例对比：阅览室位置──随便坐特点：空间利用率最高，冲突概率最低，实现最复杂。13/154▲5.2Cache的基本知识14/154▲5.2Cache的基本知识2.直接映象直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。举例（循环分配）对比：阅览室位置──只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现最简单。对于主存的第i块，若它映象到Cache的第j块，则j＝imod(M)（M为Cache的块数）15/154▲设M=2m，则当表示为二进制数时，j实际上就是i的低m位:ji：m位5.2Cache的基本知识16/154▲5.2Cache的基本知识3.组相联映象组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。举例组相联是直接映象和全相联的一种折中18/154▲5.2Cache的基本知识组的选择常采用位选择算法若主存第i块映象到第k组，则k＝imod（G）（G为Cache的组数）设G＝2g，则当表示为二进制数时，k实际上就是i的低g位:低g位以及直接映象中的低m位通常称为索引。ki：g位19/154▲5.2Cache的基本知识n路组相联：每组中有n个块(n＝M/G)。n称为相联度。相联度越高，Cache空间的利用率就越高，块冲突概率就越低，失效率也就越低。绝大多数计算机的Cache:n≤4想一想：相联度一定是越大越好？全相联直接映象组相联n(路数)G(组数)MM111＜n＜M1＜G＜M20/154▲5.2Cache的基本知识当CPU访问Cache时，如何确定Cache中是否有所要访问的块？若有，如何确定其位置？1.通过查找目录表来实现目录表的结构主存块的块地址的高位部分，称为标识。每个主存块能唯一地由其标识来确定5.2.2查找算法主存地址：块内位移索引标识块地址21/154▲5.2Cache的基本知识只需查找候选位置所对应的目录表项2.并行查找与顺序查找提高性能的重要思想：主候选位置(MRU块)（前瞻执行）3.并行查找的实现方法相联存储器单体多字存储器＋比较器举例：４路组相联并行标识比较（比较器的个数及位数）４路组相联Cache的查找过程直接映象Cache的查找过程22/154▲5.2Cache的基本知识23/154▲5.2Cache的基本知识1.所要解决的问题：当新调入一块，而Cache又已被占满时，替换哪一块？直接映象Cache中的替换很简单因为只有一个块，别无选择。在组相联和全相联Cache中，则有多个块供选择。2.主要的替换算法有三种随机法优点：实现简单先进先出法（FIFO）5.2.3替换算法24/154▲5.2Cache的基本知识最近最少使用法LRU选择近期最少被访问的块作为被替换的块。（实现比较困难）实际上：选择最久没有被访问过的块作为被替换的块。优点：失效率低。LRU和随机法的失效率的比较25/154▲5.2Cache的基本知识LRU和随机法分别因其失效率低和实现简单而被广泛采用。26/154▲5.2Cache的基本知识1.“写”在所有访存操作中所占的比例统计结果表明，对于一组给定的程序：load指令：26％store指令：9％“写”在所有访存操作中所占的比例：9％/(100％＋26％＋9％)≈7％“写”在访问Cache操作中所占的比例：9％/(26％＋9％)≈25％5.2.4写策略27/154▲5.2Cache的基本知识2.“写”操作必须在确认是命中后才可进行3.“写”访问有可能导致Cache和主存内容的不一致4.两种写策略写策略是区分不同Cache设计方案的一个重要标志。写直达法执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。写回法（也称为拷回法）执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。(设置“修改位”)28/154▲5.2Cache的基本知识5.两种写策略的比较写回法的优点：速度快，所使用的存储器带宽较低。写直达法的优点：易于实现，一致性好。6.采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写停顿。减少写停顿的一种常用的优化技术：采用写缓冲器29/154▲5.2Cache的基本知识7.“写”操作时的调块按写分配(写时取)写失效时，先把所写单元所在的块调入Cache，再行写入。不按写分配(绕写法)写失效时，直接写入下一级存储器而不调块。8.写策略与调块写回法──按写分配写直达法──不按写分配30/154▲5.2Cache的基本知识1.失效率与硬件速度无关容易产生一些误导2.平均访存时间平均访存时间＝命中时间＋失效率×失效开销5.2.6Cache的性能分析31/154▲5.2Cache的基本知识1.平均访存时间＝命中时间＋失效率×失效开销2.可以从三个方面改进Cache的性能：降低失效率减少失效开销减少Cache命中时间3.下面介绍17种Cache优化技术8种用于降低失效率5种用于减少失效开销4种用于减少命中时间5.2.7改进Cache的性能32/154▲1.三种失效(3C)强制性失效(Compulsorymiss)当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。(冷启动失效，首次访问失效)容量失效(Capacitymiss)如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。5.3降低Cache失效率的方法33/154▲5.3降低Cache失效率的方法冲突失效(Conflictmiss)在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。(碰撞失效，干扰失效)2.三种失效所占的比例图示I(绝对值)图示Ⅱ(相对值)34/154▲5.3降低Cache失效率的方法35/154▲5.3降低Cache失效率的方法36/154▲5.3降低Cache失效率的方法可以看出：相联度越高，冲突失效就越少；强制性失效和容量失效不受相联度的影响；强制性失效不受Cache容量的影响，但容量失效却随着容量的增加而减少；表中的数据符合2:1的Cache经验规则，即大小为N的直接映象Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。37/154▲5.3降低Cache失效率的方法减少三种失效的方法强制性失效：增加块大小，预取（本身很少）容量失效：增加容量（抖动现象）冲突失效：提高相联度（理想情况：全相联）许多降低失效率的方法会增加命中时间或失效开销38/154▲5.3降低Cache失效率的方法1.失效率与块大小的关系对于给定的Cache容量，当块大小增加时，失效率开始是下降，后来反而上升了。原因：一方面它减少了强制性失效；另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突失效。Cache容量越大，使失效率达到最低的块大小就越大。5.3.1增加Cache块大小39/154▲5.3降低Cache失效率的方法40/154▲5.3降低Cache失效率的方法各种块大小情况下Cache的失效率块大小（字节）Cache容量（字节）1K4K16K64K256K1615.05%8.57%3.94%2.04%1.09%3213.34%7.24%2.87%1.35%0.70%6413.76%7.00%2.64%1.06%0.51%12816.64%7.78%2.77%1.02%0.49%25622.01%9.51%3.29%1.15%0.49%41/154▲5.3降低Cache失效率的方法2.增加块大小会增加失效开销例5.4假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节。即，经过42个时钟周期，它可提供16个字节；经过44个时钟周期，可提供32个字节；依此类推。请问对于表5.6中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？解解题过程1KB、4KB、16KBCache:块大小＝32B64KB、256KBCache:块大小＝64B42/154▲5.3降低Cache失效率的方法各种块大小情况下Cache的平均访存时间块大小（字节）失效开销（时钟周期）Cache容量（字节）1K4K16K64K2