第07章 72 高速缓冲存储器

1、1/2917.2 7.2 高速缓冲存储器高速缓冲存储器cachecache 程序访问的局部性程序访问的局部性 对局部范围的存储器地址频繁访问，而对对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象。此范围以外的地址则访问甚少的现象。 程序地址的分布本来就是连续的，再加上循环程序地址的分布本来就是连续的，再加上循环 程序段和子程序段要重复执行多次，因此，对程序段和子程序段要重复执行多次，因此，对 程序地址的访问自然地具有相对集中的倾向。程序地址的访问自然地具有相对集中的倾向。 cache cache存储器工作原理存储器工作原理 2/292 根据局部性原理，可在主存和根据局部性原

2、理，可在主存和CPUCPU之间设置一个之间设置一个 高速的容量相对较小的存储器，如果当前正在高速的容量相对较小的存储器，如果当前正在 执行的程序和数据存放在这个存储器中，则当执行的程序和数据存放在这个存储器中，则当 程序运行时，不必从主存取指令和取数据，而程序运行时，不必从主存取指令和取数据，而 访问这个高速存储器即可，所以提高了程序的访问这个高速存储器即可，所以提高了程序的 运行速度，这个存储器称作运行速度，这个存储器称作高速缓冲存储器高速缓冲存储器。 cachecache介于介于CPUCPU和主存之间，它的工作速度数倍和主存之间，它的工作速度数倍 于主存，全部功能由硬件实现，并且对程序员于

3、主存，全部功能由硬件实现，并且对程序员 是是透明透明的。的。3/293 命中率：命中率：CPUCPU所要访问的信息所要访问的信息在在cachecache中的比率。中的比率。 通常用通常用“命中率命中率”来测量来测量cachecache的效率。的效率。 失效率：失效率：CPUCPU要访问的信息要访问的信息不在不在cachecache中的比率。中的比率。 影响影响cachecache效率的因素：效率的因素：cachecache的容量、块的大的容量、块的大 小、块替换算法、程序本身。小、块替换算法、程序本身。4/294 cache容量比主存的容量小得多，但不能太小，容量比主存的容量小得多，但不能太小

4、， 太小会使命中率太低；也没有必要过大，过大太小会使命中率太低；也没有必要过大，过大 不仅会增加成本，而且当容量超过一定值后，不仅会增加成本，而且当容量超过一定值后， 命中率随容量的增加将不会有明显地增长。命中率随容量的增加将不会有明显地增长。 随着芯片价格的下降，随着芯片价格的下降，cachecache的容量不断增大，的容量不断增大， 由几十由几十K K发展到几百发展到几百K K，甚至达到几，甚至达到几M M字节。字节。5/295 读操作读操作 命中：直接读即可。命中：直接读即可。 失效：需要从主存读取新字块调入失效：需要从主存读取新字块调入cache。调入时，若调入时，若cache已满，则

5、必须去掉一个旧字块，已满，则必须去掉一个旧字块，让位于一个新字块。这种替换应遵循一定的规则，让位于一个新字块。这种替换应遵循一定的规则，最好能使被替换的字块是下一段时间内估计最少最好能使被替换的字块是下一段时间内估计最少使用的。这些规则称为使用的。这些规则称为替换策略替换策略或或替换算法替换算法，由，由替换部件加以实现。替换部件加以实现。6/296 写操作（字块已在写操作（字块已在cache中时）中时）cache中保存的字块是主存相应字块的一个副本。中保存的字块是主存相应字块的一个副本。若程序执行过程中要对该字块的某个单元进行若程序执行过程中要对该字块的某个单元进行写操作，如何保持写操作，如何

6、保持cache与主存的一致性？与主存的一致性？ 有两种写入方式有两种写入方式 标志交换方式（写回法）标志交换方式（写回法） 通过式写（写直达法）通过式写（写直达法）7/297 暂时只向暂时只向cachecache存储器写入，并用标志加以注明，存储器写入，并用标志加以注明， 直到经过修改的字块被从直到经过修改的字块被从cachecache中替换出来时才中替换出来时才 一次写入主存。一次写入主存。 只有写标志只有写标志“置位置位”的字块才有必要最后从的字块才有必要最后从cachecache 存储器一次写回主存。存储器一次写回主存。(1) (1) 标志交换方式（写回法）标志交换方式（写回法） 特点：

7、特点：写操作速度快，但在写回以前，主存中的写操作速度快，但在写回以前，主存中的 字块未经随时修改而可能失效。字块未经随时修改而可能失效。8/298 每次写入每次写入cachecache时也同时写入主存，使时也同时写入主存，使cachecache和和 主存保持一致。主存保持一致。(2) (2) 通过式写（写直达法）通过式写（写直达法） 特点：特点：实现简单且随时保持主存数据的正确性。实现简单且随时保持主存数据的正确性。 但有可能要增加多次不必要的向主存的写入。但有可能要增加多次不必要的向主存的写入。 写操作（字块不在写操作（字块不在cache中时）中时） 直接对主存进行写入，而不写入直接对主存进

8、行写入，而不写入cache存储器。存储器。9/299 具有具有cachecache的存储器的平均存取时间：的存储器的平均存取时间： 设设cachecache的存取时间为的存取时间为tctc，命中率为，命中率为h h， 主存的存取时间为主存的存取时间为tMtM，则：，则：平均存取时间平均存取时间htc+(1-h)(tc+tM)htc+(1-h)(tc+tM)10/2910(1) 地址映像地址映像 地址映像：地址映像：为了把信息放到为了把信息放到cachecache存储器中，存储器中， 必须应用某种函数把主存地址映像到必须应用某种函数把主存地址映像到cachecache。2. cache2. ca

9、che存储器组织存储器组织 地址变换：地址变换：信息按照映像关系装入信息按照映像关系装入cachecache后，后， 执行程序时将主存地址变换成执行程序时将主存地址变换成cachecache地址的地址的 变换过程。变换过程。 映像函数：映像函数：决定主存地址和决定主存地址和cachecache地址的对应地址的对应 关系。关系。11/2911 假设：假设：主存空间被分为主存空间被分为Mm(0)Mm(0)、Mm(1)Mm(1)、Mm(2Mm(2m m-1)-1)共共2 2m m个块，字块大小为个块，字块大小为2 2b b个字；个字；cachecache存储空间被分为存储空间被分为Mc(0)Mc(0

10、)、Mc(1)Mc(1)、Mc(2Mc(2c c-1)-1)共共2 2c c个同样大小的块。个同样大小的块。12/2912 直接映像直接映像 直接映像函数为：直接映像函数为： j=i mod 2j=i mod 2c c 其中：其中： j j cachecache的字块号；的字块号； i i 主存的字块号；主存的字块号； 2 2c c cachecache的块数。的块数。 主存的每一块都对应主存的每一块都对应cachecache的某一固定块；的某一固定块； cachecache的每一块都对应主存的若干块。的每一块都对应主存的若干块。13/2913 主存地址格式为：主存地址格式为： 标记位：标记位

11、：指明指明cachecache中的某块对应于主存的中的某块对应于主存的 哪一块（缓存也需加哪一块（缓存也需加t t位标记位）。位标记位）。 cachecache块号：块号：指明指明cachecache中的块地址。中的块地址。 块内字地址：块内字地址：确定块内的字地址。确定块内的字地址。标记位标记位cachecache块号块号块内字地址块内字地址t t位位c c位位b b位位m m位位14/2914图图 直接映像直接映像cachecache组织组织15/2915 直接映像的特点：直接映像的特点： 实现简单，只需利用主存地址按某些字段实现简单，只需利用主存地址按某些字段 直接判断，即可确定所需的字

12、块是否已在直接判断，即可确定所需的字块是否已在 cachecache存储器中。成本较低。存储器中。成本较低。 不灵活，没有好的块替换算法（为什么）。不灵活，没有好的块替换算法（为什么）。16/2916 全相联映像全相联映像 主存的任一块可映像到主存的任一块可映像到cachecache的任一块。的任一块。标记位标记位块内字地址块内字地址t tc c位位b b位位m m位位 主存地址格式为：主存地址格式为： 缓存也需加缓存也需加t+ct+c位标记位。位标记位。17/2917图图 全相联映像全相联映像cachecache组织组织18/2918 全相联映像的特点：全相联映像的特点： 最灵活（为什么？）

13、。最灵活（为什么？）。 但成本最高。但成本最高。19/2919 组相联映像组相联映像 把把cachecache中的块分成若干组，每组包含若干中的块分成若干组，每组包含若干 块。主存块与块。主存块与cachecache组之间是组之间是直接映像直接映像，而，而 与组内各块之间是与组内各块之间是全相联映像全相联映像。 即：主存块可映像到即：主存块可映像到cachecache中某固定组中的中某固定组中的 任意块。任意块。 组相联映像方式是直接映像和全相联映像组相联映像方式是直接映像和全相联映像 方式的一种折衷方案。方式的一种折衷方案。20/2920 主存地址格式为：主存地址格式为： cachecach

14、e共共2 2C C块，被分成块，被分成2 2CC组，每组组，每组2 2r r个块。个块。 则：则：c cc+rc+r标记位标记位组地址组地址块内字地址块内字地址t+rt+r位位CC位位b b位位m m位位 当当r=0r=0时，为直接映像方式；时，为直接映像方式； 当当r=cr=c时，为全相联映像方式。时，为全相联映像方式。21/2921图图 组相联映像组相联映像cachecache组织组织22/2922 组相联映像的特点：组相联映像的特点： 性能与复杂性介于直接映像与全相联映像性能与复杂性介于直接映像与全相联映像 两种方式之间。两种方式之间。 较灵活且不难实现，最常用。较灵活且不难实现，最常用

15、。23/2923(1) 先进先出先进先出(FIFO)(FIFO)算法算法 当新的主存字块需要调入当新的主存字块需要调入cachecache，而它的可用，而它的可用 位置又已被占满时，就产生替换算法问题。位置又已被占满时，就产生替换算法问题。3. 3. 替换算法替换算法 总是把一组中最先调入总是把一组中最先调入cachecache的字块替换出去。的字块替换出去。 容易实现，开销小。容易实现，开销小。24/2924 FIFO举例举例 设：设：CPU对字块的访问顺序为对字块的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。 若若cache的大小为的大小为3个字块，求失效

16、率。个字块，求失效率。7 01203042303212017 77222244400000000000333222221111111100033333222 共有共有12次不命中，失效率为次不命中，失效率为12/17=70.5%。25/2925(2) 近期最少使用近期最少使用(LRU)(LRU)算法（最常用）算法（最常用） 把一组中近期最少使用的字块替换出去。把一组中近期最少使用的字块替换出去。 平均命中率比平均命中率比FIFOFIFO要高，并且当分组容量要高，并且当分组容量 加大时，能提高加大时，能提高LRULRU替换算法的命中率。替换算法的命中率。 需随时记录需随时记录cachecache中各个字块的使用情况，中各个字块的使用情况， 以便确定哪个字块是近期最少使用的字块。以便确定哪个字块是近期最少使用的字块。26/2926图图 LRULRU算法替换登记表算法替换登记表27/2927(3) 随机替换法随机替换法(RAND)(RAND) 在组内随机选择一块替换。在组内随机选择一块替换。 不考虑使用情况，性能比根据使用情况的不考虑使用情况，性能比根据使用情况的 替换算法要差些。替换算法要差些。28/2928图图 具有具有cachecache