Cache存储器——基本原理CACHE的功能

1、Cache存储器基本原理CACHE 的功能 Cache存储器基本原理 CACHECACHE的功能的功能 CACHECACHE是一种高速缓冲存储器，是为了解是一种高速缓冲存储器，是为了解 决决CPUCPU和主存之间速度不匹配而采用的一和主存之间速度不匹配而采用的一 项重要技术。项重要技术。 CACHECACHE能高速地向能高速地向CPUCPU提供指令和数据，提供指令和数据， 从而加快了程序的执行速度。从而加快了程序的执行速度。 为追求高速，包括管理在内的全部功能为追求高速，包括管理在内的全部功能 由硬件实现。由硬件实现。 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理 小容

2、量快速存储器小容量快速存储器 位于位于CPUCPU和内存之间和内存之间 可以在放在可以在放在CPUCPU内部，也可作为单独的模块。内部，也可作为单独的模块。 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理 LRU管理逻辑 相联 存储器 CPU 主 存 CPU与CACHE之间的数据是以字为 单位，而CACHE与主存之间的数据 交换是以块为单位的。当CPU读取 主存中一个字时，便发出此字的内 存地址到

3、CACHE和主存。 此时CACHE控制逻辑依据地址判断 此字当前是否在CACHE 中，若是， 此字立即传送给CPU；若非，则 用主存读周期把此字从内存读出送 到CPU，与此同时，把含由这个字 的整个数据块从主存读出送到 CACHE中。 Cache存储器基本原理CACHE 的功能 Cache存储器基本原理 CACHE的命中率：在一个程序执行期间，在一个程序执行期间， 设设NcNc表示表示cachecache完成存取的总次数，完成存取的总次数，NmNm表表 示主存完成存取的总次数，示主存完成存取的总次数，h h定义为命中定义为命中 率。则有：率。则有： mc c NN N h Cache存储器基本

4、原理CACHE 的功能 Cache存储器基本原理 若若tc表示命中时的表示命中时的Cache访问时间，访问时间，tm表表 示未命中时的主存访问时间，示未命中时的主存访问时间，1-h表示未表示未 命中率，则命中率，则Cache/主存系统的平均访问主存系统的平均访问 时间时间ta为：为： ta=htc+(1-h)tm Cache存储器基本原理CACHE 的功能 Cache存储器基本原理 设设r=tm/tc表示主存慢于表示主存慢于Cache的倍率，的倍率，e 表示访问效率，则有：表示访问效率，则有： hrrrhhthht t t t e mc c a c )1 ( 1 )1 ( 1 )1 ( Cac

5、he存储器基本原理CACHE 的功能 CPU执行一段程序时，执行一段程序时，cache完成存取的完成存取的 次数为次数为1900次，主存完成存取的次次，主存完成存取的次 数为数为100 次，已知次，已知cache存取周期为存取周期为50ns，主存存取周，主存存取周 期为期为250ns，求，求cache/主存系统的效率和平均主存系统的效率和平均 访问时间。访问时间。 【解】 h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=250ns/50ns=5 e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3% ta=tc/e=50ns/0.833=6

6、0ns Cache存储器基本原理CACHE 的功能 Cache存储器基本原理CACHE 的功能 Cache存储器地址映射 主存与主存与CACHE的地址映射的地址映射 全相联映射方式全相联映射方式 直接映射方式直接映射方式 组相联映射方式组相联映射方式 Cache存储器基本原理CACHE 的功能 Cache存储器地址映射 全相联映射方式：全相联映射方式： 在全相联映射中，将主存中一个块在全相联映射中，将主存中一个块 的地址与块的内容一起存于的地址与块的内容一起存于CACHECACHE的行中，的行中， 其中块地址存于其中块地址存于CACHE CACHE 行的标记部分中。行的标记部分中。 CACHE

7、CACHE的数据块大小称为的数据块大小称为行行。主存的。主存的 数据块大小称为数据块大小称为块块。行与块是等长的。行与块是等长的。 Cache存储器基本原理CACHE 的功能 全相联映射方式 主存中一个块的地址与块的内容一起主存中一个块的地址与块的内容一起 存于存于cachecache的行中，其中块地址存于的行中，其中块地址存于cachecache 行的标记部分中。行的标记部分中。 这种方法可使主存的一个块直接拷贝这种方法可使主存的一个块直接拷贝 到到cachecache中的任意一行上，非常灵活。中的任意一行上，非常灵活。 它的主要缺点是比较器电路难于设计它的主要缺点是比较器电路难于设计 和实

8、现和实现, ,因此只适合于小容量因此只适合于小容量cachecache采用。采用。 Cache存储器基本原理CACHE 的功能 Cache存储器地 址映射 （a） 全相联映象 0 2 4 6 3 1 5 7 0 2 4 6 3 1 5 7 8 10 12 14 11 9 13 15 块号 块号 Cache 主存 Cache存储器基本原理CACHE 的功能 直接映射方式 这也是一种多对一的映射关系，但一个主这也是一种多对一的映射关系，但一个主 存块只能拷贝到存块只能拷贝到cachecache的一个特定行位置上去。的一个特定行位置上去。 cachecache的行号的行号i i和主存的块号和主存的块

9、号j j有如下函数关有如下函数关 系：系：i=j mod mi=j mod m（m m为为cachecache中的总行数）中的总行数） 直接映射方式的优点是硬件简单，成本低。直接映射方式的优点是硬件简单，成本低。 缺点是每个主存块只有一个固定的行位置缺点是每个主存块只有一个固定的行位置 可存放，容易产生冲突。因此适合大容量可存放，容易产生冲突。因此适合大容量cachecache 采用采用。 Cache存储器基本原理CACHE 的功能 Cache存储器地址映射 直接映射方式：直接映射方式： i = j mod m （b） 直接映象 0 2 4 6 3 1 5 7 0 2 4 6 3 1 5 7

10、8 10 12 14 11 9 13 15 块号块号 块号块号 Cache 主存主存 Cache存储器基本原理CACHE 的功能 组相联映射方式 这种方式是前两种方式的折衷方案。这种方式是前两种方式的折衷方案。 它将它将cachecache分成分成u u组，每组组，每组v v行，主存块存放行，主存块存放 到哪个组是固定的，至于存到该组哪一行到哪个组是固定的，至于存到该组哪一行 是灵活的，即有如下函数关系：是灵活的，即有如下函数关系： m mu uv v 组号组号q qj mod u j mod u 组相联映射方式中的每组行数组相联映射方式中的每组行数v v一般取一般取 值较小，这种规模的值较小

11、，这种规模的v v路比较器容易设计和路比较器容易设计和 实现。而块在组中的排放又有一定的灵活实现。而块在组中的排放又有一定的灵活 性，冲突减少。性，冲突减少。 Cache存储器基本原理CACHE 的功能 Cache存储器地址映射 组相联映射方式组相联映射方式 （c） 组相联映象 块号 块号Cache 主存 0 2 4 6 3 1 5 7 第0组 第1组 第2组 第3组 0 2 4 6 3 1 5 7 8 10 12 14 11 9 13 15 Cache存储器基本原理CACHE 的功能 Cache存储器替换策略 cache工作原理要求它尽量保存最新数据，工作原理要求它尽量保存最新数据， 必然要

12、产生替换。必然要产生替换。 替换策略替换策略 随机法随机法 FIFO LRU 最不经常使用最不经常使用(LFU)算法算法 LFULFU算法将一段时间内被访问次数最少的那行数据换出。算法将一段时间内被访问次数最少的那行数据换出。 每行设置一个计数器。从每行设置一个计数器。从0 0开始计数，每访问一次，被访行的开始计数，每访问一次，被访行的 计数器增计数器增1 1。当需要替换时，将计数值最小的行换出，同时将。当需要替换时，将计数值最小的行换出，同时将 这些行的计数器都清零。这些行的计数器都清零。 这种算法将计数周期限定在对这些特定行两次替换之间的这种算法将计数周期限定在对这些特定行两次替换之间的

13、间隔时间内，不能严格反映近期访问情况。间隔时间内，不能严格反映近期访问情况。 近期最少使用近期最少使用(LRU)算法算法 LRULRU算法将近期内长久未被访问过的行换出。每行也设置算法将近期内长久未被访问过的行换出。每行也设置 一个计数器，一个计数器，cachecache每命中一次，命中行计数器清零，其它各每命中一次，命中行计数器清零，其它各 行计数器增行计数器增1 1。当需要替换时，将计数值最大的行换出。当需要替换时，将计数值最大的行换出。 这种算法保护了刚拷贝到这种算法保护了刚拷贝到cachecache中的新数据行，有较高的中的新数据行，有较高的 命中率命中率。 随机替换随机替换 随机替换

14、策略从特定的行位置中随机地选取一行换出。在随机替换策略从特定的行位置中随机地选取一行换出。在 硬件上容易实现，且速度也比前两种策略快。硬件上容易实现，且速度也比前两种策略快。 缺点是降低了命中率和缺点是降低了命中率和cachecache工作效率工作效率。 Cache存储器基本原理CACHE 的功能 Cache存储器写操作策略 写策略写策略 写回法写回法 全写法全写法 写一次法写一次法 Cache存储器基本原理CACHE 的功能 写回法： 当当CPUCPU写写CACHECACHE命中时，只修改命中时，只修改CACHECACHE的内容，的内容， 而不立即写入主存。只有当此行被换出时才写回主而不立即

15、写入主存。只有当此行被换出时才写回主 存。存。 如果如果CPUCPU写写CACHECACHE未命中，未包含欲写字的主存未命中，未包含欲写字的主存 块在块在CACHECACHE分配一行，将此块整个拷贝到分配一行，将此块整个拷贝到CACHECACHE后对后对 其进行修改。其进行修改。 实现这种方法时，每个实现这种方法时，每个cachecache行必须配置一个行必须配置一个 修改位，以反映此行是否被修改位，以反映此行是否被CPUCPU修改过。修改过。 这种方法减少了访问主存的次数，但是存在不这种方法减少了访问主存的次数，但是存在不 一致性的隐患。一致性的隐患。 Cache存储器基本原理CACHE 的

16、功能 全写法： 当写当写CACHECACHE命中时，命中时，CACHECACHE与主存同时与主存同时 发生写修改，因而较好地维护了发生写修改，因而较好地维护了CACHECACHE和和 主存内容的一致性。主存内容的一致性。 当写当写CACHECACHE未命中时，只能直接向主未命中时，只能直接向主 存进行写入。存进行写入。 缺点是降低了缺点是降低了cachecache的功效。的功效。 Cache存储器基本原理CACHE 的功能 写一次法： 基于写回法并结合全写法的写策略基于写回法并结合全写法的写策略, 写命中与写未命中的处理方法与写回写命中与写未命中的处理方法与写回 法基本相同，只是第一次写命中时

17、同时要法基本相同，只是第一次写命中时同时要 写入主存。写入主存。 Cache存储器基本原理CACHE 的功能 奔腾奔腾PCPC机的机的cache cache 奔腾奔腾PCPC机采用两级机采用两级cachecache结构。安装结构。安装 在主板上的在主板上的2 2级级cache(L2)cache(L2)采用采用2 2路组相联路组相联 映射方式，集成在映射方式，集成在CPUCPU内的内的1 1级级cache(L1)cache(L1) 也采用也采用2 2路组相联映射方式，路组相联映射方式，L1L1又是又是L2L2的的 子集，从而使子集，从而使L1L1未命中处理时间大大缩未命中处理时间大大缩 短。短。

18、CPUCPU中的中的L1L1分设成各分设成各8KB8KB的指令的指令cachecache 和数据和数据cache,cache,有利于有利于CPUCPU高速执行程序。高速执行程序。 L2L2级级cachecache采用的是写回法，采用的是写回法，L1L1级数级数 据据cachecache采用的是写一次法。采用的是写一次法。 Cache存储器基本原理CACHE 的功能 数据数据cachecache采用采用2 2路组相联结构，采路组相联结构，采 用最近最少使用算法用最近最少使用算法LRULRU替换算法。替换算法。 L2L2级级cachecache的内容是主存的子集，而的内容是主存的子集，而 L1L1级级cachecache又是又是L2L2级级cachecache的子集。的子集。L2L2负负 责整个系统的责整个系统的cache/cache/主存一致性，主存一致性，L1L1负负 责响应责响应L2L2，与，与L2L2一起维护一起维护L1/L2L1/L2两个两个 cachecache的一致性，保证三级存储系统的一的一致性，保证三级存储系统的一 致性。致性。 Cache存储器基本原理CACHE 的功能 练