计算机系统结构课件：第5章 存储层次

《计算机系统结构课件：第5章 存储层次》由会员分享，可在线阅读，更多相关《计算机系统结构课件：第5章 存储层次（154页珍藏版）》请在装配图网上搜索。

1、1 1/154/154第5章 存储层次2 2/154/1545.1存储器的层次结构5.2Cache基本知识5.3降低Cache失效率的方法5.4减少Cache失效开销5.5减少命中时间5.6主存5.7虚拟存储器5.8进程保护和虚存实例5.9Alpha AXP 21064存储层次3 3/154/1541.从用户的角度来看，存储器的三个主要指标：容量、速度和价格（指每位价格）2.人们对这三个指标的要求 容量大、速度快、价格低3.三个要求是相互矛盾的q速度越快，每位价格就越高；速度越快，每位价格就越高；q容量越大，每位价格就越低；容量越大，每位价格就越低；q容量越大，速度越慢。容量越大，速度越慢。5

2、.1 存储器的层次结构5.1.1 从单级存储器到多级存储器4 4/154/1545.1 存储器的层次结构4.解决方法 采用多种存储器技术，构成所谓的存储层次。演示演示 演示演示 (局部性原理局部性原理)多级存储层次多级存储层次5 5/154/1545.1 存储器的层次结构 C，H，TA假设：S 容量 TA 访问时间 C 每位价格下面仅考虑由M1和M2构成的两级存储层次：pM M1 1的参数：的参数：S S1 1，T TA1A1，C C1 1pM M2 2的参数：的参数：S S2 2，T TA2A2，C C2 25.1.2 存储层次的性能参数6 6/154/1545.1 存储器的层次结构1.每位

3、价格C2.命中率H 和失效率F命中率：CPU访问存储系统时，在M1中找到所需信息的概率。qN N1 1 访问访问M M1 1的次数的次数qN N2 2 访问访问M M2 2的次数的次数 失效率：F1H212211SSSCSCC211NNNH7 7/154/1545.1 存储器的层次结构3.平均访问时间TA T TA A HTHTA1A1（1 1H H）（）（T TA1A1T TM M）T TA1A1（1 1H H）T TM M 或或 T TA A T TA1A1FTFTM M分两种情况来考虑CPU的一次访存：q当命中时，访问时间即为当命中时，访问时间即为T TA1A1（命中时间命中时间）q当不

4、命中时，情况比较复杂。当不命中时，情况比较复杂。不命中时的访问时间为：不命中时的访问时间为：T TA2A2T TB BT TA1A1T TA1A1T TM M T TM M T TA2A2T TB Bn失效开销失效开销T TM M：从向：从向M M2 2发出访问请求到把整个数据发出访问请求到把整个数据块调入块调入M M1 1中所需的时间。中所需的时间。n传送一个信息块所需的时间为传送一个信息块所需的时间为T TB B。8 8/154/1545.1 存储器的层次结构 从主存的角度来看q“CacheCache主存主存”层次：弥补主存层次：弥补主存速度的不足速度的不足q“主存辅存主存辅存”层次：层次

5、：弥补主存弥补主存容量的不足容量的不足1.“Cache主存”层次主存与CPU的速度差距“Cache-主存”层次2.“主存辅存”层次5.1.3“Cache主存”和“主存辅存”层次9 9/154/1545.1 存储器的层次结构19801980年以来存储器和年以来存储器和CPUCPU性能随时间而提高的情况性能随时间而提高的情况 （以（以19801980年时的性能作为基准）年时的性能作为基准）1010/154/1545.1 存储器的层次结构两种存储层次两种存储层次1111/154/1545.1 存储器的层次结构存储层次存储层次CPU对第二级的对第二级的访问方式访问方式比较项目比较项目目的目的存储管理实

6、现存储管理实现 访问速度的比值访问速度的比值(第一级和第二级第一级和第二级)典型的块典型的块(页页)大小大小失效时失效时CPU是否切换是否切换“Cache 主存主存”层次层次“主存辅存主存辅存”层次层次为了弥补主存速度的不足为了弥补主存速度的不足 为了弥补主存容量的不足为了弥补主存容量的不足主要由专用硬件实现主要由专用硬件实现主要由软件实现主要由软件实现几比一几比一几百比一几百比一几十个字节几十个字节几百到几千个字节几百到几千个字节可直接访问可直接访问均通过第一级均通过第一级不切换不切换切换到其他进程切换到其他进程“Cache“Cache主存主存”与与“主存辅存主存辅存”层次的区别层次的区别1

7、212/154/1545.1 存储器的层次结构1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映像规则）映像规则）2.当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）（查找算法）3.当发生失效时，应替换哪一块？（替换算法）（替换算法）4.当进行写访问时，应进行哪些操作?（写策略）写策略）5.1.4 存储层次的四个问题1313/154/1541.存储空间分割与地址计算2.Cache和主存分块5.2 Cache的基本知识 5.2.1映象规则 1.全相联映象 全相联：主存中的任一块可以被放置到Cache中的任意一个位置。举例对比：阅览室位置 随便坐特点：空间利用率最

8、高，冲突概率最低，实现最复杂。1414/154/1545.2 Cache的基本知识1515/154/1545.2 Cache的基本知识2.直接映象 直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。举例（循环分配）（循环分配）对比：阅览室位置 只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现最简单。对于主存的第i 块，若它映象到Cache的第j 块，则 ji mod(M)（M为Cache的块数）1616/154/154设M=2m，则当表示为二进制数时，j实际上就是i的低m位:ji：m位位5.2 Cache的基本知识1717/154/1545.2 Cache的基本知识3.

9、组相联映象 组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。举例组相联是直接映象和全相联的一种折中1919/154/1545.2 Cache的基本知识组的选择常采用位选择算法q若主存第若主存第i i 块映象到第块映象到第k k 组，则组，则 k ki i modmod（G G）（G G为为CacheCache的组数）的组数）q设设G G2 2g g，则当表示为二进制数时，则当表示为二进制数时，k k 实际上就是实际上就是i i 的低的低 g g 位位:低g位以及直接映象中的低m位通常称为索引。ki：g位位2020/154/1545.2 Cache的基本知识n 路组相

10、联：每组中有n个块(nM/G)。n 称为相联度。相联度越高，相联度越高，CacheCache空间的利用率就越高，块冲突空间的利用率就越高，块冲突概率就越低，失效率也就越低。概率就越低，失效率也就越低。绝大多数计算机的Cache:n 4想一想：想一想：相联度一定是越大越好？相联度一定是越大越好？全相联全相联直接映象直接映象组相联组相联n n(路数路数)G G(组数组数)M MM M1 11 11 1n nM M1 1G GM M2121/154/1545.2 Cache的基本知识当CPU访问Cache时，如何确定Cache中是否有所要访问的块？若有，如何确定其位置？1.通过查找目录表来实现目录表

11、的结构q主存块的块地址的高位部分，称为主存块的块地址的高位部分，称为标识标识。q每个主存块能唯一地由其标识来确定每个主存块能唯一地由其标识来确定5.2.2 查找算法 主主存存地地址址：块块内内位位移移 索索 引引 标标 识识 块块地地址址 2222/154/1545.2 Cache的基本知识只需查找候选位置所对应的目录表项2.并行查找与顺序查找提高性能的重要思想：主候选位置(MRU块)（前瞻执行）（前瞻执行）3.并行查找的实现方法相联存储器单体多字存储器比较器 q举例：举例：路组相联并行标识比较路组相联并行标识比较（比较器的个数及位数）（比较器的个数及位数）q路路组组相联相联CacheCach

12、e的查找过程的查找过程q直接映象直接映象CacheCache的查找过程的查找过程2323/154/1545.2 Cache的基本知识2424/154/1545.2 Cache的基本知识1.所要解决的问题：当新调入一块，而Cache又已被占满时，替换哪一块？直接映象Cache中的替换很简单 因为只有一个块，别无选择。因为只有一个块，别无选择。在组相联和全相联Cache中，则有多个块供选择。2.主要的替换算法有三种随机法 优点：优点：实现简单实现简单先进先出法（FIFO）5.2.3 替换算法2525/154/1545.2 Cache的基本知识最近最少使用法LRUq选择近期最少被访问的块作为被替换的

13、块。选择近期最少被访问的块作为被替换的块。（实现比较困难）（实现比较困难）q实际上：实际上：选择最久没有被访问过的块作为被替换的块。选择最久没有被访问过的块作为被替换的块。q优点：优点：失效率低。失效率低。LRU和随机法的失效率的比较2626/154/1545.2 Cache的基本知识LRULRU和随机法分别因其失效率低和实现简单而被广泛采用。和随机法分别因其失效率低和实现简单而被广泛采用。2727/154/1545.2 Cache的基本知识1.“写”在所有访存操作中所占的比例 统计结果表明，对于一组给定的程序：ql loadoad指令：指令：2626qs storetore指令：指令：9 9

14、“写”在所有访存操作中所占的比例：9 9/(100/(10026269 9)7)7“写”在访问Cache操作中所占的比例：9 9/(26/(269 9)25)255.2.4 写策略2828/154/1545.2 Cache的基本知识2.“写”操作必须在确认是命中后才可进行3.“写”访问有可能导致Cache和主存内容的不一致4.两种写策略写策略是区分不同Cache设计方案的一个重要标志。写直达法q执行执行“写写”操作时，不仅写入操作时，不仅写入CacheCache，而且也写入下，而且也写入下一级存储器。一级存储器。写回法（也称为拷回法）q执行执行“写写”操作时，只写入操作时，只写入CacheCa

15、che。仅当。仅当CacheCache中相中相应的块被替换时，才写回主存。应的块被替换时，才写回主存。(设置设置“修改位修改位”)2929/154/1545.2 Cache的基本知识5.两种写策略的比较写回法的优点：速度快，所使用的存储器带宽较低。写直达法的优点：易于实现，一致性好。6.采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写停顿。减少写停顿的一种常用的优化技术：采用写缓冲器采用写缓冲器3030/154/1545.2 Cache的基本知识7.“写”操作时的调块按写分配(写时取)写失效时，先把所写单元所在的块调入写失效时，先把所写单元所在的块调入

16、CacheCache，再行写入。再行写入。不按写分配(绕写法)写失效时，直接写入下一级存储器而不调块。写失效时，直接写入下一级存储器而不调块。8.写策略与调块写回法 按写分配写直达法 不按写分配3131/154/1545.2 Cache的基本知识例：DEC的Alpha AXP21064中的内部数据Cache1.简介容量：8 KB块大小：32 B块数：256采用不按写分配映象方法：直接映象“写”策略：写直达写缓冲器大小：4个块5.2.5 Cache的结构2.结构图3333/154/1545.2 Cache的基本知识3.工作过程“读”访问命中“写”访问命中失效情况下的操作 4.混合Cache与分离

17、Cache优缺点失效率的比较3434/154/1545.2 Cache的基本知识16 KB16 KB容量容量1 KB1 KB2 KB2 KB4 KB4 KB8 KB8 KB32 KB32 KB指令指令 Cache3.06%失失 效效 率率 的的 比比 较较64 KB64 KB128 KB128 KB数据数据 Cache混合混合 Cache2.26%1.78%1.10%0.64%0.39%0.15%0.02%24.61%20.57%15.94%10.19%6.47%4.82%3.77%2.88%13.34%9.78%7.24%4.57%2.87%1.99%1.36%0.95%3535/154/1

18、545.2 Cache的基本知识1.失效率与硬件速度无关容易产生一些误导2.平均访存时间 平均访存时间 命中时间失效率失效开销5.2.6 Cache的性能分析3636/154/1545.2 Cache的基本知识 例例5.1 5.1 假设假设CacheCache的命中时间为的命中时间为1 1个时钟周期，失效开销为个时钟周期，失效开销为5050个时钟周期，在混合个时钟周期，在混合CacheCache中一次中一次loadload或或storestore操作访问操作访问CacheCache的命中时间都要增加的命中时间都要增加1 1个时钟周期（因为混合个时钟周期（因为混合CacheCache只有一个端只

19、有一个端口，无法同时满足两个请求，会导致结构冲突），根据表口，无法同时满足两个请求，会导致结构冲突），根据表5.45.4所所列的失效率，试问指令列的失效率，试问指令CacheCache和数据和数据CacheCache容量均为容量均为1616 KBKB的分离的分离CacheCache和容量为和容量为3232 KBKB的混合的混合CacheCache相比，哪种相比，哪种CacheCache的失效率更低？的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？器引起的等待。请问上述

20、两种情况下平均访存时间各是多少？3737/154/1545.2 Cache的基本知识解解 如前所述，约如前所述，约75%75%的访存为取指令。的访存为取指令。因此，分离因此，分离CacheCache的总体失效率为：的总体失效率为：（75%75%0.64%0.64%）（）（25%25%6.47%6.47%）2.10%2.10%根据表根据表5.45.4，容量为，容量为3232 KBKB的混合的混合CacheCache的失效率略的失效率略低一些，只有低一些，只有1.99%1.99%。平均访存时间公式可以分为平均访存时间公式可以分为指令访问指令访问和和数据访问数据访问两部分：两部分：平均访存时间平均访

21、存时间指令所占的百分比指令所占的百分比（指令命中时间指令失效率（指令命中时间指令失效率失效开销）失效开销）数据所占的百分比数据所占的百分比（数据命中时间数据失效率（数据命中时间数据失效率失效开销）失效开销）3838/154/1545.2 Cache的基本知识所以，两种结构的平均访存时间分别为：所以，两种结构的平均访存时间分别为：平均访存时间平均访存时间分离分离75%75%（1+0.64%1+0.64%5050）+25%+25%（1+6.47%1+6.47%5050）（75%75%1.321.32）+（25%25%4.3254.325）0.990+1.0590.990+1.0592.052.05

22、 平均访存时间平均访存时间混合混合75%75%（1+1.99%1+1.99%5050）+25%+25%（1+1+1.99%1+1+1.99%5050）（75%75%1.9951.995）+（25%25%2.9952.995）1.496+0.7491.496+0.7492.242.24因此，尽管分离因此，尽管分离CacheCache的实际失效率比混合的实际失效率比混合CacheCache的高，但其平均的高，但其平均访存时间反而较低。分离访存时间反而较低。分离CacheCache提供了两个端口，消除了结构冲突。提供了两个端口，消除了结构冲突。3939/154/1545.2 Cache的基本知识3.

23、程序执行时间CPUCPU时间（时间（CPUCPU执行周期数执行周期数+存储器停顿周期数）存储器停顿周期数）时钟周期时间时钟周期时间其中：其中：存储器停顿时钟周期数存储器停顿时钟周期数“读读”的次数的次数读失效率读失效率读失读失效开销效开销“写写”的次数的次数写失效率写失效率写失效开销写失效开销存储器停顿时钟周期数访存次数存储器停顿时钟周期数访存次数失效率失效率失效开销失效开销 时钟周期时间失效开销失效率指令数访存次数时间executionCPIICCPU指令数 失效率 访存次数 指令数 失效次数 每条指令的平均失效次数 时钟周期时间指令数存储器停顿周期数时间executionCPIICCPU4

24、040/154/1545.2 Cache的基本知识 例例5.25.2 我们用一个和我们用一个和Alpha AXPAlpha AXP类似的机器作为第一个例子。类似的机器作为第一个例子。假设假设CacheCache失效开销为失效开销为5050个时钟周期，当不考虑存储器停顿时，所个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是有指令的执行时间都是2.02.0个时钟周期，访问个时钟周期，访问CacheCache失效率为失效率为2%2%，平均每条指令访存平均每条指令访存1.331.33次。试分析次。试分析CacheCache对性能的影响。对性能的影响。解解CPU CPU 时间时间ICIC(CPI

25、CPIexeexe )时钟周期时间时钟周期时间存储器停顿周期数存储器停顿周期数指令数指令数4141/154/1545.2 Cache的基本知识考虑考虑CacheCache的失效后，性能为：的失效后，性能为：CPUCPU时间时间有有cachecacheICIC（2.02.01.331.332%2%5050）时钟周期时间时钟周期时间 ICIC3.333.33时钟周期时间时钟周期时间实际实际CPI CPI：3.333.333.33/2.0=1.67(3.33/2.0=1.67(倍倍)CPUCPU时间也增加为原来的时间也增加为原来的1.671.67倍。倍。但若不采用但若不采用Cache,Cache,则

26、：则：CPICPI2.02.050501.331.3368.568.54242/154/1545.2 Cache的基本知识4.Cache失效对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的：CPIexecution越低，固定周期数的Cache失效开销的相对影响就越大。在计算CPI时，失效开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的失效开销较大，其CPI中存储器停顿这部分也就较大。因此Cache对于低CPI、高时钟频率的CPU来说更加重要。4343/154/1545.2 Cache的基本知识 例例5.35.3 考虑两种不同组织结构的考虑两种不同

27、组织结构的CacheCache：直接映象：直接映象CacheCache和和2 2路组相联路组相联CacheCache，试问它们对，试问它们对CPUCPU的性能有何影响？先求平均访的性能有何影响？先求平均访存时间，然后再计算存时间，然后再计算CPUCPU性能。分析时请用以下假设：性能。分析时请用以下假设：(1)(1)理想理想CacheCache（命中率为（命中率为100%100%）情况下的）情况下的CPICPI为为2.02.0，时钟周，时钟周期为期为2ns2ns，平均每条指令访存，平均每条指令访存1.31.3次。次。(2)(2)两种两种CacheCache容量均为容量均为64KB64KB，块大小

28、都是，块大小都是3232字节。字节。(3)(3)图图5.85.8说明，在组相联说明，在组相联CacheCache中，必须增加一个多路选择中，必须增加一个多路选择器，用于根据标识匹配结果从相应组的块中选择所需的数据。器，用于根据标识匹配结果从相应组的块中选择所需的数据。因为因为CPUCPU的速度直接与的速度直接与CacheCache命中的速度紧密相关，所以对于组命中的速度紧密相关，所以对于组相联相联CacheCache，由于多路选择器的存在而使，由于多路选择器的存在而使CPUCPU的时钟周期增加到的时钟周期增加到原来的原来的1.101.10倍。倍。4444/154/1545.2 Cache的基本

29、知识 (4)(4)这两种结构这两种结构CacheCache的失效开销都是的失效开销都是7070 nsns。（在实际应用。（在实际应用中，应取整为整数个时钟周期）中，应取整为整数个时钟周期）(5)(5)命中时间为命中时间为1 1个时钟周期，个时钟周期，6464 KBKB直接映象直接映象CacheCache的失效的失效率为率为1.4%1.4%，相同容量的，相同容量的2 2路组相联路组相联CacheCache的失效率为的失效率为1.0%1.0%。4545/154/1545.2 Cache的基本知识4646/154/1545.2 Cache的基本知识 解解 平均访存时间为：平均访存时间为：平均访存时间

30、命中时间失效率平均访存时间命中时间失效率失效开销失效开销 因此，两种结构的平均访存时间分别是：因此，两种结构的平均访存时间分别是：平均访存时间平均访存时间1 1路路2.02.0（0.0140.0147070）2.982.98 nsns 平均访存时间平均访存时间2 2路路2.02.01.101.10（0.0100.0107070）2.902.90 nsns 2 2路组相联路组相联CacheCache的平均访存时间比较低。的平均访存时间比较低。CPU CPU 时间时间ICIC(CPICPIexeexe每条指令的平均存储器每条指令的平均存储器 停顿周期数停顿周期数)时钟周期时间时钟周期时间 IC I

31、C(CPICPIexeexe时钟周期时间时钟周期时间 每条指令的平均存储器停顿时间每条指令的平均存储器停顿时间)4747/154/1545.2 Cache的基本知识因此：因此：CPUCPU时间时间1 1路路 ICIC(2.0(2.02 2(1.3(1.30.0140.01470)70)5.275.27ICICCPUCPU时间时间2 2路路 ICIC(2.0(2.02 21.101.10(1.3(1.30.0100.01070)70)5.315.31ICIC5.315.31ICICCPUCPU时间时间1 1路路 1.011.015.275.27ICICCPUCPU时间时间2 2路路直接映象直接映

32、象CacheCache的平均性能好一些。的平均性能好一些。4848/154/1545.2 Cache的基本知识1.平均访存时间命中时间失效率失效开销2.可以从三个方面改进Cache的性能：降低失效率减少失效开销减少Cache命中时间3.下面介绍17种Cache优化技术q8 8种种用于降低失效率用于降低失效率q5 5种种用于减少失效开销用于减少失效开销q4 4种种用于减少命中时间用于减少命中时间 5.2.7 改进Cache的性能4949/154/1541.三种失效(3C)强制性失效(Compulsory miss)q当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在CacheCache

33、中，需从中，需从下一级存储器中调入下一级存储器中调入CacheCache，这就是强制性失效。，这就是强制性失效。(冷启动冷启动失效，首次访问失效失效，首次访问失效)容量失效(Capacity miss)q如果程序执行时所需的块不能全部调入如果程序执行时所需的块不能全部调入CacheCache中，中，则当某些块被替换后，若又重新被访问，就会发生则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。失效。这种失效称为容量失效。5.3 降低Cache失效率的方法5050/154/1545.3 降低Cache失效率的方法冲突失效(Conflict miss)q在组相联或直接映象在组相

34、联或直接映象CacheCache中，若太多的块映象到中，若太多的块映象到同一组同一组(块块)中，则会出现该组中某个块被别的块替中，则会出现该组中某个块被别的块替换换(即使别的组或块有空闲位置即使别的组或块有空闲位置)，然后又被重新访，然后又被重新访问的情况。这就是发生了冲突失效。问的情况。这就是发生了冲突失效。(碰撞失效，干扰失效碰撞失效，干扰失效)2.三种失效所占的比例 图示I(绝对值)图示(相对值)5151/154/1545.3 降低Cache失效率的方法5252/154/1545.3 降低Cache失效率的方法5353/154/1545.3 降低Cache失效率的方法可以看出：q相联度越

35、高，冲突失效就越少；相联度越高，冲突失效就越少；q强制性失效和容量失效不受相联度的影响；强制性失效和容量失效不受相联度的影响；q强制性失效不受强制性失效不受CacheCache容量的影响，但容量失效却随容量的影响，但容量失效却随着容量的增加而减少；着容量的增加而减少；q表中的数据符合表中的数据符合2:12:1的的CacheCache经验规则经验规则，即大小为，即大小为N N的的直接映象直接映象CacheCache的失效率约等于大小为的失效率约等于大小为N/2N/2的的2 2路组相路组相联联CacheCache的失效率。的失效率。5454/154/1545.3 降低Cache失效率的方法减少三种

36、失效的方法q强制性失效：强制性失效：增加块大小，预取增加块大小，预取（本身很少）（本身很少）q容量失效：容量失效：增加容量增加容量（抖动现象）（抖动现象）q冲突失效：冲突失效：提高相联度提高相联度（理想情况：全相联）（理想情况：全相联）许多降低失效率的方法会增加命中时间或失效开销5555/154/1545.3 降低Cache失效率的方法1.失效率与块大小的关系对于给定的Cache容量，当块大小增加时，失效率开始是下降，后来反而上升了。原因：q一方面它减少了强制性失效；一方面它减少了强制性失效；q另一方面，由于增加块大小会减少另一方面，由于增加块大小会减少CacheCache中块的数目，中块的数

37、目，所以有可能会增加冲突失效。所以有可能会增加冲突失效。Cache容量越大，使失效率达到最低的块大小就越大。5.3.1 增加Cache块大小5656/154/1545.3 降低Cache失效率的方法5757/154/1545.3 降低Cache失效率的方法各种块大小情况下Cache的失效率 块大小（字节）Cache容量（字节）1K 4K 16K 64K 256K 16 15.05%8.57%3.94%2.04%1.09%32 13.34%7.24%2.87%1.35%0.70%64 13.76%7.00%2.64%1.06%0.51%128 16.64%7.78%2.77%1.02%0.49%

38、256 22.01%9.51%3.29%1.15%0.49%5858/154/1545.3 降低Cache失效率的方法2.增加块大小会增加失效开销 例例5.45.4 假定存储系统在延迟假定存储系统在延迟4040个时钟周期后，每个时钟周期后，每2 2个时钟周个时钟周期能送出期能送出1616个字节。即，经过个字节。即，经过4242个时钟周期，它可提供个时钟周期，它可提供1616个字个字节；经过节；经过4444个时钟周期，可提供个时钟周期，可提供3232个字节；依此类推。请问对个字节；依此类推。请问对于表于表5.65.6中列出的各种容量的中列出的各种容量的CacheCache，在块大小分别为多少时，

39、在块大小分别为多少时，平均访存时间最小？平均访存时间最小？解解 解题过程解题过程 1 1 KBKB、4 4 KBKB、1616 KB Cache:KB Cache:块大小块大小3232 B B 6464 KBKB、256256 KB Cache:KB Cache:块大小块大小6464 B B5959/154/1545.3 降低Cache失效率的方法各种块大小情况下Cache的平均访存时间 块大小（字节）失效开销（时钟周期）Cache容量（字节）1K 4K 16K 64K 256K 16427.321 4.599 2.655 1.857 1.458 32446.870 4.186 2.263 1

40、.857 1.308 64487.605 4.360 2.267 1.594 1.245 1285610.318 5.357 2.551 1.509 1.274 2567216.847 7.847 3.369 1.571 1.353 6060/154/1545.3 降低Cache失效率的方法1.采用相联度超过8的方案的实际意义不大。2.2:1 Cache经验规则 容量为N的直接映象Cache的失效率和容量为N/2的2路组相联Cache的失效率差不多相同。3.提高相联度是以增加命中时间为代价。例如：qTTLTTL或或ECLECL板级板级CacheCache，2 2路组相联：路组相联：增加增加10

41、10q定制的定制的CMOS Cache,2CMOS Cache,2路组相联：路组相联：增加增加2 25.3.2 提高相联度6161/154/1545.3 降低Cache失效率的方法 例例5.55.5 假定提高相联度会按下列比例增大处理器时钟周期：假定提高相联度会按下列比例增大处理器时钟周期：时钟周期时钟周期2 2路路 1.101.10时钟周期时钟周期1 1路路 时钟周期时钟周期4 4路路 1.121.12时钟周期时钟周期1 1路路 时钟周期时钟周期8 8路路 1.141.14时钟周期时钟周期1 1路路 假定命中时间为一个时钟周期，直接映象情况下失效开销为假定命中时间为一个时钟周期，直接映象情况

42、下失效开销为5050个个时钟周期，而且假设不必将失效开销取整。使用表时钟周期，而且假设不必将失效开销取整。使用表5.55.5中的失效率，试中的失效率，试问当问当CacheCache为多大时，以下不等式成立？为多大时，以下不等式成立？平均访存时间平均访存时间8 8路路 平均访存时间平均访存时间4 4路路 平均访存时间平均访存时间4 4路路 平均访存时间平均访存时间2 2路路 平均访存时间平均访存时间2 2路路 平均访存时间平均访存时间1 1路路 6262/154/1545.3 降低Cache失效率的方法解解 在各种相联度的情况下，平均访存时间分别为：在各种相联度的情况下，平均访存时间分别为：平均

43、访存时间平均访存时间8 8路路 =命中时间命中时间8 8路路 +失效率失效率8 8路路失效开销失效开销8 8路路 =1.14=1.14失效率失效率8 8路路5050 平均访存时间平均访存时间4 4路路 =1.12=1.12 失效率失效率4 4路路5050 平均访存时间平均访存时间2 2路路 =1.10=1.10 失效率失效率2 2路路5050 平均访存时间平均访存时间1 1路路 =1.00=1.00 失效率失效率1 1路路5050 把相应的失效率代入上式，即可得平均访存时间。把相应的失效率代入上式，即可得平均访存时间。例如，例如，1 1 KBKB的直接映象的直接映象CacheCache的平均访

44、存时间为：的平均访存时间为：平均访存时间平均访存时间1 1路路 =1.00=1.000.1330.13350507.657.65 128128 KBKB的的8 8路组相联路组相联CacheCache的平均访存时间为：的平均访存时间为：平均访存时间平均访存时间8 8路路1.141.140.0060.00650501.441.44Cache容量相联度（路）124817.65 6.60 6.22 5.44 25.90 4.90 4.62 4.09 44.60 3.95 3.57 3.19 83.30 3.00 2.87 2.59 162.45 2.20 2.12 2.04 322.00 1.80 1

45、.77 1.79 641.70 1.60 1.57 1.59 1281.50 1.45 1.42 1.44 在各种容量和相联度情况下在各种容量和相联度情况下CacheCache的平均访存时间的平均访存时间6464/154/1545.3 降低Cache失效率的方法 当当CacheCache容量不超过容量不超过1616 KBKB时，上述三个不等式成立。时，上述三个不等式成立。从从3232 KBKB开始，对于平均访存时间有：开始，对于平均访存时间有：4 4路组相联的平均访存时间小于路组相联的平均访存时间小于2 2路组相联的路组相联的;2 2路组相联的小于直接映象的路组相联的小于直接映象的;但但8 8

46、路组相联的却比路组相联的却比4 4路组相联的大。路组相联的大。6565/154/1545.3 降低Cache失效率的方法1.最直接的方法是增加Cache的容量缺点:q增加成本增加成本q可能增加命中时间可能增加命中时间2.这种方法在片外Cache中用得比较多 5.3.3 增加Cache的容量6666/154/1545.3 降低Cache失效率的方法1.一种能减少冲突失效次数而又不影响时钟频率的方法。2.基本思想在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。工作过程5.3.4 Victim Cache 6767/1

47、54/1545.3 降低Cache失效率的方法Victim Cache在存储层次中的位置 6868/154/1545.3 降低Cache失效率的方法3.作用对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。例如项数为项数为4 4的的Victim Cache:Victim Cache:能使能使4 4 KBKB CacheCache的冲突失效减少的冲突失效减少20%20%90%90%6969/154/1545.3 降低Cache失效率的方法1.多路组相联的低失效率和直接映象的命中速度2.伪相联Cache的优点命中时间小失效率低5.3.5 伪相联 Cache 优点优点缺

48、点缺点直接映象直接映象组相联组相联命中时间小命中时间小命中时间大命中时间大失效率高失效率高失效率低失效率低3.基本思想及工作原理 （动画演示）在逻辑上把直接映象在逻辑上把直接映象CacheCache的空间上下平分为两个区。对于的空间上下平分为两个区。对于任何一次访问，伪相联任何一次访问，伪相联CacheCache先按直接映象先按直接映象CacheCache的方式去处理。的方式去处理。若命中，则其访问过程与直接映象若命中，则其访问过程与直接映象CacheCache的情况一样。若不命中，的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则再到另一区相应的位置去查找。若找

49、到，则发生了伪命中，否则就只好访问下一级存储器。则就只好访问下一级存储器。4.快速命中与慢速命中 要保证绝大多数命中都是快速命中。7171/154/1545.3 降低Cache失效率的方法 例例5.65.6 假设当在按直接映象找到的位置处没有发现匹配，而假设当在按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要在另一个位置才找到数据（伪命中）需要2 2个额外的周期。仍用个额外的周期。仍用上个例子中的数据，问：当上个例子中的数据，问：当CacheCache容量分别为容量分别为2 2 KBKB和和128128 KBKB时，直时，直接映象、接映象、2 2路组相联和伪相联这三种

50、组织结构中，哪一种速度最路组相联和伪相联这三种组织结构中，哪一种速度最快？快？解解 首先考虑标准的平均访存时间公式：首先考虑标准的平均访存时间公式：平均访存时间平均访存时间伪相联伪相联 命中时间命中时间伪相联伪相联失效率失效率伪相联伪相联失效开销失效开销伪相联伪相联7272/154/1545.3 降低Cache失效率的方法 由于：由于：失效率失效率伪相联伪相联失效率失效率2 2路路 命中时间命中时间伪相联伪相联命中时间命中时间1 1路路伪命中率伪命中率伪相联伪相联2 2 伪相联查找的命中率等于伪相联查找的命中率等于2 2路组相联路组相联CacheCache的命中率和直接映象的命中率和直接映象C

51、acheCache命中率之差。命中率之差。伪命中率伪命中率伪相联伪相联 命中率命中率2 2路路命中率命中率1 1路路 （1 1失效率失效率2 2路路）（）（1 1失效率失效率1 1路路）失效率失效率1 1路路失效率失效率2 2路路 综合上述分析，有：综合上述分析，有：平均访存时间平均访存时间伪相联伪相联命中时间命中时间1 1路路（失效率（失效率1 1路路失效率失效率2 2路路）2 2 失效率失效率2 2路路失效开销失效开销1 1路路7373/154/1545.3 降低Cache失效率的方法将前面表中的数据代入上面的公式，得：将前面表中的数据代入上面的公式，得：平均访存时间平均访存时间伪相联，伪

52、相联，2 2 KBKB 1 1（0.0980.0980.0760.076）2 2（0.0760.0765050）4.8444.844 平均访存时间平均访存时间伪相联，伪相联，128128 KBKB 1 1（0.0100.0100.0070.007）2 2（0.0070.0075050）1.3561.356根据上一个例子中的表，对于根据上一个例子中的表，对于2 2 KBKB Cache Cache，可得：，可得：平均访存时间平均访存时间1 1路路 5.90 5.90 个时钟个时钟 平均访存时间平均访存时间2 2路路 4.90 4.90 个时钟个时钟7474/154/1545.3 降低Cache失

53、效率的方法 对于对于128KB128KB的的CacheCache有，可得：有，可得：平均访存时间平均访存时间1 1路路 1.50 1.50 个时钟个时钟 平均访存时间平均访存时间2 2路路 1.45 1.45 个时钟个时钟可见，对于这两种可见，对于这两种CacheCache容量，伪相联容量，伪相联CacheCache都是速度最快的。都是速度最快的。5.缺点：多种命中时间7575/154/1545.3 降低Cache失效率的方法1.指令和数据都可以预取2.预取内容既可放入Cache，也可放在外缓冲器中。例如：指令流缓冲器例如：指令流缓冲器3.指令预取通常由Cache之外的硬件完成4.预取效果Jo

54、ppi的研究结果q指令预取指令预取 (4(4 KBKB，直接映象，直接映象CacheCache，块大小，块大小1616 B B)n1 1个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获15152525的失效的失效n4 4个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获5050n1616个块的指令流缓冲器：捕获个块的指令流缓冲器：捕获72725.3.6 硬件预取 7676/154/1545.3 降低Cache失效率的方法q数据预取数据预取 (4(4 KB,KB,直接映象直接映象Cache)Cache)n1 1个数据流缓冲器：捕获个数据流缓冲器：捕获2525的失效的失效n还可以采用多个数据流缓冲器

55、还可以采用多个数据流缓冲器Palacharla和Kessler的研究结果q流缓冲器：既能预取指令又能预取数据流缓冲器：既能预取指令又能预取数据q对于两个对于两个6464 KBKB四路组相联四路组相联CacheCache来说：来说：n8 8个流缓冲器能捕获个流缓冲器能捕获50507070的失效的失效7777/154/1545.3 降低Cache失效率的方法 例例5.75.7 Alpha AXP 21064 Alpha AXP 21064采用指令预取技术，其实际失效率采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，是多少？若不采用指令预取技术，Alpha AXP 21064Alpha

56、AXP 21064的指令的指令CacheCache必须为多大才能保持平均访存时间不变？必须为多大才能保持平均访存时间不变？解解 假设当指令不在指令假设当指令不在指令CacheCache里，而在预取缓冲器中找到时，里，而在预取缓冲器中找到时，需要多花一个时钟周期。需要多花一个时钟周期。下面是修改后的公式：下面是修改后的公式：平均访存时间预取平均访存时间预取 命中时间失效率命中时间失效率预取命中率预取命中率1 1 失效率失效率（1 1预取命中率）预取命中率）失效开销失效开销7878/154/1545.3 降低Cache失效率的方法 假设预取命中率为假设预取命中率为25%25%，命中时间为，命中时间

57、为2 2个时钟周期，失效开销个时钟周期，失效开销为为5050个时钟周期。查表可知个时钟周期。查表可知8 8 KBKB指令指令CacheCache的失效率为的失效率为1.10%1.10%。则：。则：平均访存时间平均访存时间预取预取 2 2（1.10%1.10%25%25%1 1）1.10%1.10%（1 125%25%）5050 2 20.002750.002750.413 0.413 2.4152.415 为了得到相同性能下的实际失效率，由原始公式得：为了得到相同性能下的实际失效率，由原始公式得：平均访存时间平均访存时间 命中时间失效率命中时间失效率失效开销失效开销 失效率失效率 （平均访存时

58、间命中时间）（平均访存时间命中时间）/失效开销失效开销 （2.4152.4152 2）/50/500.83%0.83%7979/154/1545.3 降低Cache失效率的方法 在编译时加入预取指令，在数据被用到之前发出预取请求。1.预取有以下几种类型：寄存器预取：把数据取到寄存器中。Cache预取：只将数据取到Cache中。故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。5.3.7 编译器控制的预取 8080/154/1545.3 降低Cache失效率的方法本节假定本节假定CacheCach

59、e预取都是非故障性的，预取都是非故障性的，也称非绑定预取。也称非绑定预取。2.在预取数据的同时，处理器应能继续执行。只有这样，预取才有意义。非阻塞非阻塞Cache(Cache(非锁定非锁定Cache)Cache)3.编译器控制预取的目的 使执行指令和读取数据能重叠执行。使执行指令和读取数据能重叠执行。4.循环是预取优化的主要对象失效开销小时：循环体展开12次失效开销大时：循环体展开许多次8181/154/1545.3 降低Cache失效率的方法 例例5.85.8 对于下面的程序，首先判断哪些访问可能会导致数对于下面的程序，首先判断哪些访问可能会导致数据据CacheCache失效。然后，加入预取

60、指令以减少失效。最后，计算所失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：执行的预取指令的条数以及通过预取避免的失效次数。假定：(1)(1)我们用的是一个容量为我们用的是一个容量为8 8 KBKB、块大小为、块大小为1616 B B的直接映象的直接映象CacheCache，它采用写回法并且按写分配。，它采用写回法并且按写分配。(2)a(2)a、b b分别为分别为3 3100100（3 3行行100100列）和列）和1011013 3的双精度浮点的双精度浮点数组，每个元素都是数组，每个元素都是8 8 B B。当程序开始执行时，这些数据都不在

61、。当程序开始执行时，这些数据都不在CacheCache内。内。for（i=0;i 3;i=i+1）for（j=0;j 100;j=j+1）a i j =b j 0 *b j+1 0;8282/154/1545.3 降低Cache失效率的方法解解计算过程失效情况 总的失效次数251次 改进后的程序q假设失效开销很大，预取必须至少提前假设失效开销很大，预取必须至少提前7 7次循环进行。次循环进行。8383/154/1545.3 降低Cache失效率的方法for（j=0;j 100;j=j+1）prefetch（b j+7 0）;/*预取预取7 7次循环后所需的次循环后所需的b b（j,0 j,0）

62、*/prefetch（a 0 j+7）;/*预取预取7 7次循环后所需的次循环后所需的a a（0,j 0,j）*/for（i=1;i 3;i=i+1）for（j=0;j 100;j=j+1）prefetch（a i j+7）;/*预取预取7 7次循环后所需的次循环后所需的a a（i,j i,j）*/a i j =b j 0 *b j+1 0;8484/154/1545.3 降低Cache失效率的方法q失效情况失效情况 总的失效次数总的失效次数1919次次8585/154/1545.3 降低Cache失效率的方法 例例5.95.9 在以下条件下，计算例在以下条件下，计算例5.85.8中所节约的时

63、间：中所节约的时间：(1)(1)忽略指令忽略指令CacheCache失效，并假设数据失效，并假设数据CacheCache无冲突失效和无冲突失效和容量失效。容量失效。(2)(2)假设预取可以被重叠或与假设预取可以被重叠或与CacheCache失效重叠执行，从而能失效重叠执行，从而能以最大的存储带宽传送数据。以最大的存储带宽传送数据。(3)(3)不考虑不考虑CacheCache失效时，修改前的循环每失效时，修改前的循环每7 7个时钟周期循个时钟周期循环一次。修改后的程序中，第一个预取循环每环一次。修改后的程序中，第一个预取循环每9 9个时钟周期循环个时钟周期循环一次，而第二个预取循环每一次，而第二

64、个预取循环每8 8个时钟周期循环一次（包括外层个时钟周期循环一次（包括外层forfor循环的开销）。循环的开销）。(4)(4)一次失效需一次失效需5050个时钟周期。个时钟周期。8686/154/1545.3 降低Cache失效率的方法解解修改前：修改前：循环时间循环时间3003007 7 21002100失效开销失效开销251251505012550/14650 12550/14650 2100210012550125501465014650修改后：修改后：循环时间循环时间1001009 92002008 825002500失效时间失效时间19195050950950250025009509

65、5034503450 加速比加速比14650/345014650/34504.24.28787/154/1545.3 降低Cache失效率的方法基本思想 在编译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。McFaring 发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。q2KB Cache:2KB Cache:降低降低5050q8KB Cache8KB Cache：降低：降低75%75%数据对存储位置的限制比指令的少，因此更便于优化。5.3.8 编译器优化 8888/154/1545.3 降低Cache失效率的方法通过把数据重新组织，使得一块数据在被从Cac

66、he替换出去之前，能最大限度利用其中的数据(访问次数最多)。1.数组合并举例：/*修改前*/int val SIZE;int key SIZE;8989/154/1545.3 降低Cache失效率的方法/*修改后*/struct merge int val;int key;struct merge merged_array SIZE;9090/154/1545.3 降低Cache失效率的方法2.内外循环交换 举例：/*修改前*/for（j=0;j 100;j=j+1）for（i=0;i 5000;i=i+1）x i j =2*x i j;/*修改后*/for（i=0;i 5000;i=i+1）for（j=0;j 100;j=j+1）x i j =2*x i j;9191/154/1545.3 降低Cache失效率的方法3.循环融合 /*修改前*/for（i=0;i N;i=i+1）for（j=0;j N;j=j+1）a i j =1/b i j *c i j;for（i=0;i N;i=i+1）for（j=0;j N;j=j+1）d i j =a i j +c i j;/*修改后*/f