《计算机系统结构-5-存储层次》由会员分享，可在线阅读，更多相关《计算机系统结构-5-存储层次（173页珍藏版）》请在文档大全上搜索。
1、117321735.2Cache基本知识5.3 降低Cache失效率的方法5.4减少Cache失效开销5.1存储器的层次结构5.5减少命中时间5.6主存5.7虚拟存储器5.8进程保护和虚存实例5.9Alpha AXP 21064存储层次第五章 存储层次31735.1.1 从单级存储器到多级存储器1. 从用户的角度来看，存储器的三个主要指标是： 容量，速度，价格容量，速度，价格( (每位价格每位价格) )2. 人们对这三个指标的期望3. 这三个指标相互矛盾4. 解决方法 采用多种存储器技术，构成存储层次。采用多种存储器技术，构成存储层次。 演示演示 演示演示 ( (局部性原理局部性原理) )5.
2、1 5.1 存储器的层次结构存储器的层次结构第五章 存储层次4173517361735.1.2 存储层次的性能参数 C C，H H，T TA A假设：假设：S S 容量容量 T TA A 访问时间访问时间 C C 每位价格每位价格下面仅考虑由下面仅考虑由M M1 1和和M M2 2构成的两级存储层次：构成的两级存储层次： M M1 1的参数：的参数：S S1 1，T TA1A1，C C1 1 M M2 2的参数：的参数：S S2 2，T TA2A2，C C2 21. 每位价格C C C C C1 1S S1 1C C2 2S S2 2S S1 1S S2 25.1 存储器的层次结构71732.
3、 命中率 H 和失效率 F H HN N1 1/(/(N N1 1N N2 2) ) N N1 1 访问访问M M1 1的次数的次数 N N2 2 访问访问M M2 2的次数的次数 失效率失效率 F F1 1H H5.1 存储器的层次结构91733. 平均访问时间 TA T TA AT TA1A1( (1 1H H ) )T TM M 或或 T TA AT TA1A1F F T TM M T TA1A1 命中时间命中时间 T TM M 失效开销失效开销10173111735.1.3 “Cache主存”和“主存辅存”层次1. 从主存的角度来看 “CacheCache主存主存”层次层次：弥补主存速
4、度的不：弥补主存速度的不足足 “主存辅存主存辅存”层次层次： 弥补主存容量的不弥补主存容量的不足足2. “Cache主存”层次 主存与主存与CPUCPU的速度差距的速度差距5.1 存储器的层次结构 “Cache - Cache - 主存主存”层次层次3. “主存辅存”层次15173存储层次存储层次CPU对第二级的对第二级的访问方式访问方式比较项目比较项目目的目的存储管理实现存储管理实现 访问速度的比值访问速度的比值(第一级和第二级第一级和第二级)典型的块典型的块(页页)大小大小失效时失效时CPU是否切换是否切换“Cache 主存主存”层次层次“主存辅存主存辅存”层次层次为了弥补主存速度的不足为
5、了弥补主存速度的不足 为了弥补主存容量的不足为了弥补主存容量的不足主要由专用硬件实现主要由专用硬件实现主要由软件实现主要由软件实现几比一几比一几百比一几百比一几十个字节几十个字节几百到几千个字节几百到几千个字节可直接访问可直接访问均通过第一级均通过第一级不切换不切换切换到其他进程切换到其他进程“Cache“Cache主存主存”与与“主存辅存主存辅存”层次的区别层次的区别5.1 存储器的层次结构161735.1.4 存储层次的四个问题当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上? ( (映象规则映象规则) )当所要访问的块在高一层存储器中时，如何找到该块? ( (查找算法查找算
6、法) )3. 当发生失效时，应替换哪一块？ ( (替换算法替换算法) )4. 当进行写访问时，应进行哪些操作? ( (写策略写策略) )1. 2.5.1 存储器的层次结构5.2 Cache基本知识1存储空间分割与地址计算 181735.2.1 映象规则1. 全相联映象 全相联：全相联：主存中的任一块可以被放置到主存中的任一块可以被放置到 CacheCache中的任意一个位置。中的任意一个位置。 举例举例 对比：对比： 阅览室位置阅览室位置 随便坐随便坐 特点：特点： 空间利用率最高，冲突概率最低，空间利用率最高，冲突概率最低， 实现最复杂。实现最复杂。2Cache和主存分块5.2 Cache
7、基本知识201732. 直接映象 直接映象：直接映象：主存中的每一块只能被放置到主存中的每一块只能被放置到 CacheCache中唯一的一个位置。中唯一的一个位置。 举例举例 ( (循环分配循环分配) ) 对比：对比：阅览室位置阅览室位置 只有一个位置可只有一个位置可 以坐以坐 特点：特点：空间利用率最低，冲突概率最高，空间利用率最低，冲突概率最高， 实现最简单。实现最简单。 对于主存的第对于主存的第i i 块，若它映象到块，若它映象到CacheCache的第的第 j j 块，则块，则: : j ji i mod ( mod (M M ) ) （M M为为CacheCache的块数）的块数）5
8、.2 Cache 基本知识22173 组相联：组相联：主存中的每一块可以被放置到主存中的每一块可以被放置到CacheCache 中唯一的一个组中的任何一个位置。中唯一的一个组中的任何一个位置。 举例举例 组相联是直接映象和全相联的一种折衷组相联是直接映象和全相联的一种折衷 设设M M2 2m m，则当表示为二进制数时，则当表示为二进制数时，j j 实际实际 上就是上就是i i 的低的低m m 位：位：3. 组相联映象m位位ji：5.2 Cache 基本知识24173 上述的上述的j j 和和k k 通常称为通常称为索引索引 组的选择常采用位选择算法组的选择常采用位选择算法 若主存第若主存第i
9、i 块映象到第块映象到第k k 组，则组，则: : k ki i modmod（G G） （G G为为CacheCache的组数）的组数） 设设G G2 2g g，则当表示为二进制数时，则当表示为二进制数时，k k 实实 际上就是际上就是i i 的低的低 g g 位：位：g 位位ki：5.2 Cache 基本知识25173 绝大多数计算机的绝大多数计算机的Cache: Cache: n n 44 想一想：相联度一定是越大越好？想一想：相联度一定是越大越好？ n n 路组相联：路组相联：每组中有每组中有n n 个块个块( (n nM M/ /G G ) ) n n 称为称为相联度。相联度。 相联
10、度越高，相联度越高，CacheCache空间的利用率就越高，空间的利用率就越高， 块冲突概率就越低，失效率也就越低。块冲突概率就越低，失效率也就越低。 全相联全相联直接映象直接映象组相联组相联n n ( (路数路数) )G G ( (组数组数) )M MM M1 11 11 1n nM M1 1G GM M5.2 Cache 基本知识261735.2.2 查找方法1. 如何确定Cache中是否有所要访问的块？ 若有的话如何确定其位置？若有的话如何确定其位置？ 答案答案5.2 Cache 基本知识 目录表的结构目录表的结构 只需查找只需查找候选位置候选位置所对应的目录表项所对应的目录表项 并行查
11、找与顺序查找并行查找与顺序查找30173 提高性能的提高性能的重要思想：重要思想：主候选位置主候选位置(MRU(MRU块块) ) 前瞻执行前瞻执行31173 并行查找的实现方法：并行查找的实现方法：5.2 Cache 基本知识举例：举例： 路组相联并行标识比较路组相联并行标识比较 （比较器的个数及位数）（比较器的个数及位数）l 相联存储器相联存储器l 单体多字存储器比较器单体多字存储器比较器 路路组组相联相联CacheCache的查找过程的查找过程 直接映象直接映象CacheCache的查找过程的查找过程351735.2.3 替换算法 所要解决的问题：当新调入一块，而所要解决的问题：当新调入一
12、块，而CacheCache又已被占满时，替换哪一块？又已被占满时，替换哪一块？2. FIFO3. LRU 优点：优点：失效率低失效率低 LRULRU和随机法的失效率的比较和随机法的失效率的比较1. 随机法 优点：优点：实现简单实现简单5.2 Cache 基本知识36173371735.2.4 写策略1. “写”操作所占的比例 LoadLoad指令：指令：2626 StoreStore指令：指令：9 9 “写写”在所有访存操作中所占的比例：在所有访存操作中所占的比例： 9 9/(100/(10026269 9)7)7 “写写”在访问在访问CacheCache操作中所占的比例：操作中所占的比例：
13、9 9/(26/(269 9)25)253“写”访问有可能导致Cache和主存内容的不一致2. “写”操作必须在确认是命中后才可进行5.2 Cache 基本知识381734两种写策略 写直达法写直达法 执行执行“写写”操作时，不仅写入操作时，不仅写入CacheCache，而且，而且 也写入下一级存储器。也写入下一级存储器。 写回法写回法 执行执行“写写”操作时，只写入操作时，只写入CacheCache。仅当。仅当 CacheCache中相应的块被替换时，才写回主存。中相应的块被替换时，才写回主存。 ( (设置设置“污染位污染位”) )5.2 Cache 基本知识391735 5两种写策略的比较
14、两种写策略的比较 写回法的写回法的优点：优点：速度快，所使用的存储器频速度快，所使用的存储器频 带较低；带较低； 写直达法的写直达法的优点：优点：易于实现，一致性好。易于实现，一致性好。401736. 写缓冲器8. 写策略与调块 写回法写回法 按写分配按写分配 写直达法写直达法 不按写分配不按写分配7. “写”操作时的调块 按写分配按写分配( (写时取写时取) ) 写失效时，先把所写单元所在的块调入写失效时，先把所写单元所在的块调入 CacheCache，再行写入。，再行写入。 不按写分配不按写分配( (绕写法绕写法) ) 写失效时，直接写入下一级存储器而不调块。写失效时，直接写入下一级存储器
15、而不调块。5.2 Cache 基本知识411735.2.5 Cache的结构例子：例子：DECDEC的的Alpha AXP21064Alpha AXP21064中的内部数据中的内部数据 CacheCache。1. 简介 容量：容量：8KB8KB 块大小：块大小：32B32B 块数：块数：256256 采用采用不按写分配不按写分配 映象方法：映象方法：直接映象直接映象 “写写”策略：策略：写直达写直达 写缓冲器大小：写缓冲器大小：4 4个块个块5.2 Cache 基本知识2. 结构图3. 工作过程 “读读”访问访问命中命中 “写写”访问访问命中命中451735. 混合Cache与分离Cache
16、(1) (1) 优缺点优缺点 (2) (2) 失效率的比较失效率的比较 5.2 Cache 基本知识 失效情况下的操作失效情况下的操作4617316 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.5
17、7%2.87%1.99%1.36%0.95%47173(3) (3) 分离分离CacheCache平均失效率的计算：平均失效率的计算：访问指令访问指令CacheCache的百分比的百分比指令指令CacheCache的失效率的失效率访问数据访问数据CacheCache的百分比的百分比数据数据CacheCache的失效率的失效率5.2.6 Cache性能分析2. 平均访问时间 平均访问时间命中时间失效率平均访问时间命中时间失效率失效开销失效开销1. 失效率48173例例5.15.1 假设假设CacheCache的命中时间为的命中时间为1 1个时钟周期，失效个时钟周期，失效开销为开销为50 50 个
18、时钟周期，在混合个时钟周期，在混合CacheCache中一次中一次loadload或或storestore操作访问操作访问CacheCache的命中时间都要增加一个的命中时间都要增加一个时钟周期时钟周期( (因为混合因为混合CacheCache只有一个端口，无法同只有一个端口，无法同时满足两个请求。按照前一章中有关流水线的术时满足两个请求。按照前一章中有关流水线的术语，混合语，混合CacheCache会导致结构冲突会导致结构冲突) )，根据表，根据表5 54 4所所列的失效率，试问指令列的失效率，试问指令CacheCache和数据和数据CacheCache容量均容量均为为16KB16KB的分离
19、的分离CacheCache和容量为和容量为32KB32KB的混合的混合CacheCache相相5.2 Cache 基本知识49173解：解： 如前所述，约如前所述，约75%75%的访存为取指令。因此，的访存为取指令。因此，分离分离CacheCache的总体失效率为：的总体失效率为： (75%(75%0.64%)0.64%)(25%(25%6.47%)6.47%)2.10%2.10% 根据表根据表5 54 4，容量为，容量为32KB32KB的混合的混合CacheCache的失的失效率略低一些，只有效率略低一些，只有1.99%.1.99%.比，哪种比，哪种CacheCache的失效率更低？又假设采
20、用写直达的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各起的等待。请问上述两种情况下平均访存时间各是多少？是多少？5.2 Cache 基本知识50173平均访存时间公式可以分为指令访问和数据平均访存时间公式可以分为指令访问和数据访问两部分：访问两部分：平均访存时间平均访存时间指令所占的百分比指令所占的百分比 ( (指令命中时间指令失效率指令命中时间指令失效率失效开销失效开销) ) 数据所占的百分比数据所占的百分比 ( (数据命中时间数据失效率数据命中时间数据失效率失效开销失效开销) )所
21、以，两种结构的平均访存时间分别为：所以，两种结构的平均访存时间分别为：平均访存时间平均访存时间分离分离75%75%(1(10.64%0.64%50)50) 25%25%(1(16.47%6.47%50)50) (75%(75%1.32)1.32)(25%(25%4.325)4.325) 0.9900.9901.0591.0592.052.055.2 Cache 基本知识51173平均访存时间平均访存时间混合混合75%75%(1(11.99%1.99%50)50) 25%25%(1(11 11.99%1.99%50)50) (75%(75%1.995)1.995)(25%(25%2.995)2.
22、995) 1.4961.4960.7490.7492.242.243. 程序执行时间 CPUCPU时间时间(CPU(CPU执行周期数存储器停顿周期数执行周期数存储器停顿周期数) ) 时钟周期时间时钟周期时间 其中，其中， 存储器停顿周期数存储器停顿周期数访存次数访存次数失效率失效率 失效开销失效开销5.2 Cache 基本知识52173CPUCPU时间时间ICICCPIexeCPIexe每条指令的平均存储每条指令的平均存储 器停顿周期数器停顿周期数时钟周期时间时钟周期时间CPUCPU时间时间ICICCPIexeCPIexe访存次数访存次数/ /指令数指令数 失效率失效率失效开销失效开销时钟周期
23、时间时钟周期时间5.2 Cache 基本知识53173例例5.25.2 我们用一个和我们用一个和Alpha AXPAlpha AXP类似的机器作为类似的机器作为第一个例子。假设第一个例子。假设CacheCache失效开销为失效开销为5050个时钟个时钟周期，当不考虑存储器停顿时，所有指令的周期，当不考虑存储器停顿时，所有指令的执行时间都是执行时间都是2.02.0个时钟周期，个时钟周期， CacheCache的失效的失效率为率为2%2%，平均每条指令访存，平均每条指令访存1.331.33次。试分析次。试分析CacheCache对性能的影响。对性能的影响。54173考虑考虑CacheCache的失
24、效后，性能为：的失效后，性能为：CPU CPU 时间时间有有cachecacheICIC(2.0(2.0(1.33(1.332%2%50)50) 时钟周期时间时钟周期时间 ICIC3.333.33时钟周期时间时钟周期时间CPU CPU 时间时间ICIC( (CPICPIexeexe ) ) 时钟周期时间时钟周期时间存储器停顿周期数存储器停顿周期数指令数指令数解：解：5.2 Cache 基本知识实际实际CPI CPI ：3.333.333.33/2.0 = 1.67(3.33/2.0 = 1.67(倍倍) )55173 CPU CPU时间也增加为原来的时间也增加为原来的1.671.67倍。但若不
25、倍。但若不采用采用Cache,Cache,则：则： CPICPI2.0+502.0+501.331.3368.568.55.2 Cache 基本知识56173 考虑两种不同组织结构的考虑两种不同组织结构的CacheCache：直接映象：直接映象CacheCache和两路组相联和两路组相联CacheCache，试问它们对，试问它们对CPUCPU的性的性能有何影响？先求平均访存时间，然后再计算能有何影响？先求平均访存时间，然后再计算CPUCPU性能。分析时请用以下假设：性能。分析时请用以下假设： 理想理想Cache(Cache(命中率为命中率为100100) )情况下的情况下的CPICPI 为为2
26、.02.0，时钟周期为，时钟周期为2ns2ns，平均每条指令，平均每条指令 访存访存1.31.3次。次。 两种两种CacheCache容量均为容量均为64KB64KB，块大小都是，块大小都是3232 字节。字节。例例5.35.35.2 Cache 基本知识57173 图图5.105.10说明，在组相联说明，在组相联CacheCache中，我们必须增中，我们必须增 加一个多路选择器，用于根据标识匹配结果加一个多路选择器，用于根据标识匹配结果 从相应组的块中选择所需的数据。因为从相应组的块中选择所需的数据。因为CPU CPU 的速度直接与的速度直接与CacheCache命中的速度紧密相关命中的速度
27、紧密相关, ,所所 以对于组相联以对于组相联CacheCache，由于多路选择器的存，由于多路选择器的存 在而使在而使CPUCPU的时钟周期增加到原来的的时钟周期增加到原来的1.101.10倍。倍。 这两种结构这两种结构CacheCache的失效开销都是的失效开销都是70ns70ns。在。在 实际应用中，应取整为整数个时钟周期。实际应用中，应取整为整数个时钟周期。 命中时间为命中时间为1 1个时钟周期，个时钟周期，64KB64KB直接映象直接映象 CacheCache的失效率为的失效率为1.4%1.4%，相同容量的两路组，相同容量的两路组 相联相联CacheCache的失效率为的失效率为1.0
28、%1.0%。5.2 Cache 基本知识5817359173由由: :平均访存时间命中时间失效率平均访存时间命中时间失效率失效开销失效开销得得: :平均访存时间平均访存时间1 1路路2.02.0(0.014(0.01470)70)2.98ns2.98ns平均访存时间平均访存时间2 2路路2.02.01.101.10(0.010(0.01070)70)2.90ns2.90ns由由: :CPU CPU 时间时间ICIC( (CPICPIexeexe每条指令的平均存储器每条指令的平均存储器 停顿周期数停顿周期数) )时钟周期时间时钟周期时间 IC IC ( (CPICPIexeexe时钟周期时间时钟
29、周期时间 每条指令的平均存储器停顿时间每条指令的平均存储器停顿时间) )解：解：5.2 Cache 基本知识60173CPUCPU时间时间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.31ICIC得：得：5.315.31ICICCPUCPU时间时间1 1路路 1.011.015.275.27ICICCPUCPU时间时间2 2路路5.2 Cache 基本知识61173平均访存时间命中时间失效
30、率平均访存时间命中时间失效率失效开销失效开销可以从三个方面改进可以从三个方面改进CacheCache的性能：的性能：(1) (1) 降低失效率降低失效率(2) (2) 减少失效开销减少失效开销(3) (3) 减少减少CacheCache命中时间命中时间下面介绍下面介绍1515种种CacheCache优化技术优化技术5.2.7 改进Cache性能5.2 Cache 基本知识63173(1) (1) 强制性失效强制性失效(Compulsory miss)(Compulsory miss) 当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在 CacheCache中，需从下一级存储器中调入中
31、，需从下一级存储器中调入CacheCache， 这就是这就是强制性失效。强制性失效。 ( (冷启动失效，首次访问失效。冷启动失效，首次访问失效。) )(2) (2) 容量失效容量失效(Capacity miss ) (Capacity miss ) 如果程序执行时所需的块不能全部调如果程序执行时所需的块不能全部调 入入CacheCache中，则当某些块被替换后，若又中，则当某些块被替换后，若又5.3 降低Cache失效率的方法1. 三种失效(3C)第五章 存储层次64173 重新被访问，就会发生失效。这种失效称重新被访问，就会发生失效。这种失效称 为为容量失效。容量失效。(3) (3) 冲突失
32、效冲突失效(Conflict miss)(Conflict miss) 在组相联或直接映象在组相联或直接映象CacheCache中，若太多中，若太多 的块映象到同一组的块映象到同一组( (块块) )中，则会出现该组中，则会出现该组 中某个块被别的块替换中某个块被别的块替换( (即使别的组或块有即使别的组或块有 空闲位置空闲位置) )，然后又被重新访问的情况。这，然后又被重新访问的情况。这 就是发生了就是发生了冲突失效。冲突失效。 ( (碰撞失效，干扰失效碰撞失效，干扰失效) )5.3 降低Cache 失效率的方法651732. 三种失效所占的比例(SPEC92)(SPEC92)表表5.55.5
33、 5.3 降低Cache 失效率的方法图示图示I(I(绝对值绝对值) )图示图示(相对值相对值) )68173可以看出：可以看出：(1) (1) 相联度越高，冲突失效就越少；相联度越高，冲突失效就越少；(2) (2) 强制性失效和容量失效不受相联度的影响；强制性失效和容量失效不受相联度的影响；(3) (3) 强制性失效不受强制性失效不受CacheCache容量的影响，但容容量的影响，但容 量失效却随着容量的增加而减少；量失效却随着容量的增加而减少；(4) (4) 表中的数据符合表中的数据符合2:12:1的的CacheCache经验规则经验规则，即，即 大小为大小为N N 的直接映象的直接映象C
34、acheCache的失效率约等于的失效率约等于 大小为大小为N N/2/2 的两路组相联的两路组相联CacheCache的失效率。的失效率。69173强制性失效：强制性失效：增加块大小，预取增加块大小，预取 ( (本身很少本身很少) )容量失效：容量失效：增加容量增加容量 ( (抖动现象抖动现象) )冲突失效：冲突失效：提高相联度提高相联度 ( (理想情况：全相联理想情况：全相联) )3. 减少三种失效的方法4. 许多降低失效率的方法会增加命中时间或 失效开销5.3 降低Cache 失效率的方法701735.3.1 增加Cache块大小1. 失效率与块大小的关系 (1) (1) 对于给定的对于
35、给定的CacheCache容量，当块大小增加容量，当块大小增加 失效率开始是下降，后来反而上升了；失效率开始是下降，后来反而上升了； (2) Cache(2) Cache容量越大，使失效率达到最低的容量越大，使失效率达到最低的 块大小就越大。块大小就越大。5.3 降低Cache 失效率的方法71173721732. 2. 增加块大小会增加失效开销增加块大小会增加失效开销3. 3. 例题例题73173例例 5.45.4 假定存储系统在延迟假定存储系统在延迟4040个时钟周期后，每个时钟周期后，每2 2个个时钟周期能送出时钟周期能送出1616个字节。即个字节。即: :经过经过4242个时钟周期，个
36、时钟周期，它可提供它可提供1616个字节；经过个字节；经过4444个时钟周期，可提供个时钟周期，可提供3232个字节；依此类推。试问对于表个字节；依此类推。试问对于表5-65-6中列出的各种中列出的各种容量的容量的CacheCache，在块大小分别为多少时，平均访存，在块大小分别为多少时，平均访存时间最小？时间最小？解解： 解题过程解题过程 1KB1KB、4KB4KB、16KB Cache: 16KB Cache: 块大小块大小3232字节字节 64KB64KB、256KB Cache: 256KB Cache: 块大小块大小6464字节字节5.3 降低Cache 失效率的方法块大小块大小（字
37、节）（字节）失效开销失效开销（时钟周期）（时钟周期）Cache容量（字节）容量（字节）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.8704.1862.2631.5941.30864487.6054.3602.2671.5091.2451285610.3185.3572.5511.5711.2742567216.8477.8473.3691.8281.353751735.3.2 提高相联度1. 采用相联度超过8的方法实际意义不大2. 2:1 Cache经验规则 容量为容量为N N 的直接映象的直接映象CacheCache 容量为容量为N N/
38、2/2的两路组相联的两路组相联CacheCache3. 提高相联度是以增加命中时间为代价 例如：例如： TTLTTL或或ECLECL板级板级CacheCache，两路组相联：，两路组相联： 增加增加1010 定制的定制的CMOS Cache, CMOS Cache, 两路组相联：两路组相联： 增加增加2 25.3 降低Cache 失效率的方法761734. 例题 假定提高相联度会按下列比例增大处理器假定提高相联度会按下列比例增大处理器时钟周期：时钟周期： 时钟周期时钟周期2 2路路 1.101.10时钟周期时钟周期1 1路路 时钟周期时钟周期4 4路路 1.121.12时钟周期时钟周期1 1路
39、路 时钟周期时钟周期8 8路路 1.141.14时钟周期时钟周期1 1路路 假定命中时间为假定命中时间为1 1个时钟，直接映象情况个时钟，直接映象情况下失效开销为下失效开销为5050个时钟周期，而且假设不必将个时钟周期，而且假设不必将失效开销取整。使用表失效开销取整。使用表5 55 5中的失效率，试问中的失效率，试问当当CacheCache为多大时，以下不等式成立？为多大时，以下不等式成立？例例 5.55.55.3 降低Cache 失效率的方法77173平均访存时间平均访存时间8 8路路 平均访存时间平均访存时间4 4路路平均访存时间平均访存时间4 4路路 平均访存时间平均访存时间2 2路路平
40、均访存时间平均访存时间2 2路路 平均访存时间平均访存时间1 1路路解解： 在各种相联度的情况下，平均访存时间分在各种相联度的情况下，平均访存时间分别为：别为： 平均访存时间平均访存时间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
41、.00 失效率失效率1 1路路50505.3 降低Cache 失效率的方法78173 在每种情况下的失效开销相同，都是在每种情况下的失效开销相同，都是5050个时钟周期。把相应的失效率代入上式，个时钟周期。把相应的失效率代入上式， 即可得平均访存时间。即可得平均访存时间。 例如，例如，1KB1KB的直接映象的直接映象CacheCache的平均的平均访存时间为：访存时间为：平均访存时间平均访存时间1 1路路 1.001.00(0.133(0.13350)50) 7.657.65 容量为容量为128KB128KB的的8 8路组相联路组相联CacheCache的平均的平均访存时间为：访存时间为：平均
42、访存时间平均访存时间8 8路路 1.141.14(0.006(0.00650)50) 1.441.44表表5-85-85.3 降低Cache 失效率的方法Cache容量容量（K字节）字节）相联度（路）相联度（路）124817.656.606.225.4425.904.904.624.0944.603.953.573.1983.303.002.872.59162.452.202.122.04322.001.801.771.79641.701.601.571.591281.501.451.421.44801731 1. 基本思想 在在CacheCache和它从下一级存储器调数据和它从下一级存储器调
43、数据 的通路之间设置一个全相联的小的通路之间设置一个全相联的小CacheCache， 用于存放被替换出去的块用于存放被替换出去的块( (称为称为VictimVictim) )， 以备重用。以备重用。 工作过程工作过程5.3.3 Victim Cache5.3 降低Cache 失效率的方法8117382173 对于减小冲突失效很有效，特别是对对于减小冲突失效很有效，特别是对于小容量的直接映象数据于小容量的直接映象数据CacheCache，作用尤其，作用尤其明显。明显。 例如，项数为例如，项数为4 4的的Victim Cache:Victim Cache: 使使4KB Cache4KB Cache
44、的冲突失效减少的冲突失效减少20%20%90%90%2. 作用5.3 降低Cache 失效率的方法831731. 直接映象 vs组相联5.3.4 伪相联Cache2 2. 伪相联Cache优点优点缺点缺点直接映象直接映象组相联组相联命中时间小命中时间小命中时间大命中时间大失效率高失效率高失效率低失效率低取直接映象及组相联两者的优点：取直接映象及组相联两者的优点： 命中时间小，失效率低命中时间小，失效率低5.3 降低Cache 失效率的方法84173(1) (1) 基本思想及工作原理基本思想及工作原理 ( (动画演示动画演示) ) 在逻辑上把直接映象在逻辑上把直接映象CacheCache的空间上
45、下的空间上下 平分为两个区。对于任何一次访问，伪相联平分为两个区。对于任何一次访问，伪相联 CacheCache先按直接映象先按直接映象CacheCache的方式去处理。若的方式去处理。若 命中，则其访问过程与直接映象命中，则其访问过程与直接映象CacheCache的情的情 况一样。若不命中，则再到另一区相应的位况一样。若不命中，则再到另一区相应的位 置去查找。若找到，则发生了伪命中，否则置去查找。若找到，则发生了伪命中，否则 就只好访问下一级存储器。就只好访问下一级存储器。(2) (2) 快速命中与慢速命中快速命中与慢速命中 要保证绝大多数命中都是快速命中。要保证绝大多数命中都是快速命中。5
46、.3 降低Cache 失效率的方法85173861733. 例题例例5.65.6 假设当在按直接映象找到的位置处没有发假设当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据现匹配、而在另一个位置才找到数据( (伪命中伪命中) )需要需要2 2个额外的周期。仍用上个例子中的数据，个额外的周期。仍用上个例子中的数据，问：当问：当CacheCache容量分别为容量分别为2KB2KB和和128KB128KB时，直接时，直接映象、两路组相联和伪相联这三种组织结构中，映象、两路组相联和伪相联这三种组织结构中，哪一种速度最快？哪一种速度最快？5.3 降低Cache 失效率的方法87173首先考
47、虑标准的平均访存时间公式：首先考虑标准的平均访存时间公式： 平均访存时间平均访存时间伪相联伪相联 命中时间命中时间伪相联伪相联失效率失效率伪相联伪相联失效开销失效开销伪相联伪相联由于：由于： 失效率失效率伪相联伪相联失效率失效率2 2路路 命中时间命中时间伪相联伪相联命中时间命中时间1 1路路伪命中率伪命中率伪相联伪相联2 2； 伪命中率伪命中率伪相联伪相联命中率命中率2 2路路命中率命中率1 1路路 (1(1失效率失效率2 2路路) )(1(1失效率失效率1 1路路) ) 失效率失效率1 1路路失效率失效率2 2路路解：解：5.3 降低Cache 失效率的方法88173故：故： 平均访存时间
48、平均访存时间伪相联伪相联 命中时间命中时间1 1路路( (失效率失效率1 1路路失效率失效率2 2路路) )2 2 失效率失效率2 2路路失效开销失效开销1 1路路将表将表5 55 5中的数据代入上面的公式，得：中的数据代入上面的公式，得： 平均访存时间平均访存时间伪相联，伪相联，2KB2KB 1 1(0.098(0.0980.076)0.076)2 2(0.076(0.07650)50) 4.8444.844 平均访存时间平均访存时间伪相联，伪相联，128KB128KB 1 1(0.010(0.0100.007)0.007)2 2(0.007(0.00750)50) 1.3561.3565.
49、3 降低Cache 失效率的方法89173根据上一个例子中的表根据上一个例子中的表5 58 8，对于，对于2KB Cache2KB Cache，可得：可得： 平均访存时间平均访存时间1 1路路 5.90 5.90 个时钟个时钟 平均访存时间平均访存时间2 2路路 4.90 4.90 个时钟个时钟对于对于128KB128KB的的CacheCache有，可得：有，可得： 平均访存时间平均访存时间1 1路路 1.50 1.50 个时钟个时钟 平均访存时间平均访存时间2 2路路 1.45 1.45 个时钟个时钟可见，对于这两种可见，对于这两种CacheCache容量，伪相联容量，伪相联CacheCac
50、he都是速度最快的。都是速度最快的。缺点：缺点：多种命中时间多种命中时间5.3 降低Cache 失效率的方法901735.3.5 硬件预取技术1. 指令和数据都可以预取2. 预取内容既可放入Cache，也可放在 外缓冲器中 例如：指令流缓冲器例如：指令流缓冲器3. 预取效果 (1) (1) JoppiJoppi的研究结果的研究结果 指令预取：指令预取：(4KB(4KB，直接映象，直接映象Cache,Cache, 块大小块大小1616字节字节) )5.3 降低Cache 失效率的方法911731 1个块的指令流缓冲器：个块的指令流缓冲器： 捕获捕获15152525 的失效的失效4 4个块的指令流
51、缓冲器：个块的指令流缓冲器： 捕获捕获50501616个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获7272 数据预取：数据预取：(4KB,(4KB,直接映象直接映象Cache)Cache) 1 1个数据流缓冲器：个数据流缓冲器：捕获捕获2525的失效的失效 还可以采用多个数据流缓冲器还可以采用多个数据流缓冲器(2) Palacharla(2) Palacharla和和KesslerKessler的研究结果的研究结果 流缓冲器：流缓冲器：既能预取指令又能预取数据既能预取指令又能预取数据 对于两个对于两个64KB64KB四路组相联四路组相联CacheCache来说：来说： 8 8个流缓冲器能个
52、流缓冲器能捕获捕获50507070的失效。的失效。5.3 降低Cache 失效率的方法921734. 例题例例5.75.7 Alpha AXP 21064Alpha AXP 21064采用指令预取技术，其实际采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，失效率是多少？若不采用指令预取技术，AlphaAlphaAPX 21064APX 21064的指令的指令CacheCache必须为多大才能保持平均访必须为多大才能保持平均访存时间不变？存时间不变？解：解： 假设从预取缓冲器中找到所需指令需多花假设从预取缓冲器中找到所需指令需多花1 1个个时钟周期。时钟周期。 平均访存时间平均访存时
53、间预取预取 命中时间失效率命中时间失效率预取命中率预取命中率1 1 失效率失效率(1(1预取命中率预取命中率) )失效开销失效开销5.3 降低Cache 失效率的方法93173假设：假设： 预取命中率预取命中率2525 命中时间命中时间1 1个时钟周期个时钟周期 失效开销失效开销5050个时钟周期个时钟周期 由表由表5.45.4可知，可知，8KB8KB指令指令CacheCache的失效率的失效率1.101.10 故平均访存时间故平均访存时间预取预取 1 1(1.10 %(1.10 %25 %25 %1)1) (1.10 %(1.10 %(1(125 %)25 %)50)50) 1 10.002
54、750.002750.4125 0.4125 1.4151.415 由公式：由公式： 平均访问时间命中时间失效率平均访问时间命中时间失效率失效开销失效开销5.3 降低Cache 失效率的方法94173可得相应的失效率为：可得相应的失效率为：失效率失效率( (平均访问时间命中时间平均访问时间命中时间)/)/失效开销失效开销 (1.451(1.4511)/501)/500.830.838KB Cache8KB Cache 带预取的带预取的8kB Cache8kB Cache失效率1.101.100.830.8316KB Cache16KB Cache0.640.645.3 降低Cache 失效率的
55、方法951735.3.6 由编译器控制的预取1. 预取的类型 寄存器预取：寄存器预取：把数据取到寄存器中把数据取到寄存器中 CacheCache预取：预取： 只将数据取到只将数据取到CacheCache中中 故障性预取：故障性预取：预取时，若出现虚地址故障预取时，若出现虚地址故障 或违反访问权限，就会发生异常。或违反访问权限，就会发生异常。 非故障性预取：非故障性预取：预取时，若出现虚地址故预取时，若出现虚地址故 障或违反访问权限，并不会导致异常，只障或违反访问权限，并不会导致异常，只 是转变为是转变为“不预取不预取”。由编译器加入预取指令，在数据被用到之前由编译器加入预取指令，在数据被用到之
56、前发出预取请求。发出预取请求。5.3 降低Cache 失效率的方法961734. 例题2. 在预取数据的同时，处理器应能继续执行 只有这样，预取才有意义。只有这样，预取才有意义。 非阻塞非阻塞Cache (Cache (非锁定非锁定Cache)Cache)3. 循环是预取优化的主要对象 失效开销小时：失效开销小时：循环体展开循环体展开1 12 2次次 失效开销大时：失效开销大时：循环体展开许多次循环体展开许多次5.3 降低Cache 失效率的方法97173例例 5.85.8 对于下面的程序，判断哪些访问可能会导致对于下面的程序，判断哪些访问可能会导致数据数据CacheCache失效。然后，加入
57、预取指令以减少失失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：过预取避免的失效次数。假定： (1) (1) 我们用的是一个容量为我们用的是一个容量为8KB8KB、块大小为、块大小为 16B16B的直接映象的直接映象CacheCache，它采用写回法并，它采用写回法并 且按写分配。且按写分配。 (2) a(2) a、b b分别为分别为3 3100(3100(3行行100100列列) )和和1011013 3 的双精度浮点数组，每个元素都是的双精度浮点数组，每个元素都是8 8个个 字节。当程序开始执行
58、时，这些数据都字节。当程序开始执行时，这些数据都 不在不在CacheCache内。内。5.3 降低Cache 失效率的方法98173for (ifor (i0 ; i 3 ; i0 ; i 3 ; ii i1 )1 ) for (j for (j0 ; j 100 ; j0 ; j 100 ; jj j1 )1 ) aij aijbj0bj0bjbj10;10;解：解：( (1) 1) 计算过程计算过程(2) (2) 失效情况失效情况 总的失效次数总的失效次数251251次次 (3) (3) 改进后的程序改进后的程序5.3 降低Cache 失效率的方法99173100173101173for
59、(jfor (j0 0，j j100100；j jj j1) 1) prefetch (bj prefetch (bj70); 70); / /* * 预取预取7 7次循环后所需的次循环后所需的b(j ,0 ) b(j ,0 ) * */ / prefetch (a0j prefetch (a0j7); 7); / /* * 预取预取7 7次循环后所需的次循环后所需的a(0,j ) a(0,j ) * */ / a0j a0jbj 0 bj 0 * * b jb j1010 for (i for (i1; i 3; i1; i 3; ii i1) 1) for (j for (j0; j 10
60、0; j0; j 100; jj j1)1) prefetch(aij prefetch(aij7);7); / /* * 预取预取7 7次循环后所需的次循环后所需的a(i , j a(i , j ) ) * */ / aij aijbj0 bj0 * * bj bj10;10; 5.3 降低Cache 失效率的方法102173例例 5 59 9 在以下条件下，计算例在以下条件下，计算例5.85.8中所节约的时间：中所节约的时间： (1) (1) 忽略指令忽略指令CacheCache失效，并假设数据失效，并假设数据CacheCache 无冲突失效和容量失效。无冲突失效和容量失效。 (2) (2
61、) 假设预取可以被重叠或与假设预取可以被重叠或与CacheCache失效重失效重 叠执行，从而能以最大的存储带宽传送叠执行，从而能以最大的存储带宽传送 数据。数据。 (3) (3) 不考虑不考虑CacheCache失效时，修改前的循环每失效时，修改前的循环每7 7 个时钟周期循环一次。修改后的程序中，个时钟周期循环一次。修改后的程序中，失效情况失效情况 总的失效次数总的失效次数1919次次5.3 降低Cache 失效率的方法103173解：解： 修改前：修改前： 循环时间循环时间3003007 7 21002100 失效开销失效开销251251505012550/1465012550/1465
62、0 2100 210012550125501465014650 第一个预取循环每第一个预取循环每9 9个时钟周期循环一次，个时钟周期循环一次， 而第二个预取循环每而第二个预取循环每8 8个时钟周期循环一个时钟周期循环一 次次( (包括外层包括外层forfor循环的开销循环的开销) )。(4) (4) 一次失效需一次失效需5050个时钟周期。个时钟周期。5.3 降低Cache 失效率的方法104173 修改后：修改后： 循环时间循环时间1001009 92002008 825002500 失效时间失效时间19195050950950 2500 250095095034503450 加速比加速比1
63、4650/345014650/34504.24.25.3 降低Cache 失效率的方法1051735.3.7 编译器优化2KB Cache:2KB Cache: 降低降低50508KB Cache8KB Cache：降低降低75%75%1. 基本思想 在编译时，对程序中的指令和数据进行在编译时，对程序中的指令和数据进行重新组织，以降低重新组织，以降低CacheCache失效率。失效率。2. McFaring 发现：通过对指令进行重新排序， 可有效地降低指令Cache的失效率。5.3 降低Cache 失效率的方法1061733. 数据对存储位置的限制比指令的少，因此 更便于优化。 通过把数据重新
64、组织，使得在一块数通过把数据重新组织，使得在一块数 据被从据被从CacheCache替换出去之前，能最大限度替换出去之前，能最大限度 利用其中的数据利用其中的数据( (访问次数最多访问次数最多) ) (1) (1) 数组合并数组合并 举例：举例： / /* * 修改前修改前 * */ / int val SIZE;int val SIZE; int key SIZE; int key SIZE;5.3 降低Cache 失效率的方法107173(2) (2) 内外循环交换内外循环交换 举例：举例： / /* * 修改前修改前 * */ / for (jfor (j0 ;j100 ;j0 ;j10
65、0 ;jj j1)1) for (i for (i0 ;i5000 ;i0 ;i5000 ;ii i1)1) xij xij2 2* *xij;xij; / /* * 修改后修改后 * */ / struct merge struct merge int val ; int val ; int key ; int key ; ; ; struct merge merged_arraysize; struct merge merged_arraysize;5.3 降低Cache 失效率的方法108173(3) (3) 循环融合循环融合 举例：举例： / /* * 修改前修改前 * */ / fo
66、r (i for (i0 ; iN ;i0 ; iN ;ii i1)1) for (j for (j0 ; jN ; j0 ; jN ; jj j1)1) aij aij1/bij1/bij* *cij;cij; / /* * 修改后修改后 * */ / for (ifor (i0 ;i100 ;i0 ;i100 ;ii i1)1) for (j for (j0 ;j 000 ;j0 ;j 000 ;jj j1)1) xij xij2 2* *xij;xij;5.3 降低Cache 失效率的方法109173 / /* * 修改后修改后 * */ / for (i for (i0 ;i N ;i0 ;i N ;ii i1)1) for (j for (j0 ;j N ;j0 ;j N ;jj j1) 1) aij aij1/bij1/bij* *cij;cij; dij dijaijaijcij;cij; for (i for (i0 ;iN ;i0 ;iN ;ii i1)1) for (j for (j0 ; jN ;j0 ; jN ;jj j1)1) dij dijaijaijcij
