《湘潭大学第4章高速缓冲存储器和虚拟存储器》由会员分享，可在线阅读，更多相关《湘潭大学第4章高速缓冲存储器和虚拟存储器（52页珍藏版）》请在金锄头文库上搜索。
1、高速缓冲存储器Cache和虚拟存储 器TLB 5.5 高速缓冲存储器Cache CacheCache 二二 五五 三三 四四 一一 Cache的基 本原理 主存与Cache的地址映射方式 替换算法 写策略 Cache的多层次设计 一、Cache的基本原理 Cache的 工作原理 Cache的 特点 Cache的 命中率 123 1、Cache的特点 Cache是指位于CPU和主存之间的一个高速 小容量的存储器，一般由SRAM构成。 Cache功能：用于弥补CPU和主存之间的速 度差异，提高CPU访问主存的平均速度。 设置Cache的理论基础，是程序访问的局 部性原理。 Cache的内容是主存部
2、分内容的副本， Cache的功能均由硬件实现，对程序员是 透明的。 Cache存储器工作原理（局部性工作原理） 对大量典型程序的运行情况进行分析得到：在一 个较短的时间间隔内，由程序产生的地址往往集 中在地址空间的很小范围内。 原因：程序地址的分布一般是连续的，再加上循 环程序、子程序等要重复执行多次。因此对程序 地址的访问自然具有相对集中的倾向。 数据分布不如指令明显，但对数组的存储和访问 使存储器地址相对集中。 2、Cache的工作原理 程序的簇聚性(局部性)指在每一小段时间内 ，程序所要用到的指令或数据的地址往往集 中在一个局部区域内，因而对局部范围内的 存储器地址频繁访问，而对此范围外
3、的地址 则访问甚少的现象。 两种局部性： 时间局部性：最近被访问的信息很可能还要被访问。 将最近被访问的信息项装入到Cache中。 空间局部性：最近被访问的信息临近的信息也可能被访 问。 将最近被访问信息项附近的信息一起装入到Cache中 。 如果能把正在执行的指令地址附近的一部分 指令或数据从主存成批调入一个能高速访问 的小容量存储器(Cache) ，供CPU在一段时间 内随时使用，从而大大减少CPU访问主存的次 数，加快程序的运行速度。 Cache的速度比主存快510倍。 Cache、主存与CPU的关系 Cache的原理图 Cache的读写操作 CPU在读写存储器时，Cache控制逻辑首先
4、要 依据地址来判断这个字是否在Cache中，若 在Cache中，则称为“命中”；若不在，则 称为“不命中”。 针对命中/不命中、读/写操作，Cache的处 理是不同的： 读命中：立即从Cache读出送给CPU。 读不命中：通常有两种解决方法： (1)将主存中该字所在的数据块复制到Cache中，然后再 把这个字传送给CPU。 (2)把此字从主存读出送到CPU，同时，把包含这个字的 数据块从主存中读出送到Cache中。 Cache的读写操作 写不命中：直接将该字写入主存中，且不再调入 Cache； 写命中：通常也有两种方法进行处理： 写贯穿方法：同时对Cache和主存进行写操作； 写回：只写Cac
5、he，仅当此Cache块被替换时，才将该 块写入主存 3、Cache的命中率 命中率指CPU访问主存数据时，命中Cache的 次数，占全部访问次数的比率。 失效率就指不命中Cache的次数，占全部访 问次数的比率。 命中率h取决于程序的行为、Cache的容量、 组织方式、块大小。 在一个程序执行期间，设Nc表示Cache 完成存取的总次数，Nm表示主存完成存 取的总次数，则命中率： v若tc表示Cache的访问时间，tm表 示主存的访问时间，则Cache/主 存系统的平均访问时间ta为： vCache/主存系统的访问效率e: 二、主存与Cache的地址映射方式 讨论前提：Cache的数据块称为
6、行，主存的 数据块称为块，行与块是等长的；主存容量 为2m块，Cache容量为2c行，每个字块中含2b 字。 主存中只有一小部分块的内容可放在Cache中。 Cache存储单元的组成部分: 数据字段：保存从主存单元复制过来的数据。 标志字段：保存相应主存单元的地址信息。 有效位字段：标识数据字段和标志字段的是否 有效。 讨论的问题：如何根据主存地址，判断 Cache有无命中并变换为Cache的地址，以 便执行读写。有三种地址映射方式： 直接映射 全相联映射 组相联映射 1、直接映射 直接映射是一种多对一的映射关系：主存的 第i块一定映射到Cache的第j行，且： j=i mod 2c 直接映像
7、方式特点： 主存的字块只可以和固定的Cache字块对应，映 射方式直接、简单，易实现，利用率低。 标志位较短，比较电路的成本低。如果主存空 间有2m块，Cache中字块有2c块，则标志位只要 有m-c位，且仅需要比较一次。 机制不灵活，Cache命中率低。 标记K： 直接映像硬件实现举例 注意P358-359与这里讲的区别。 书上访问Cache是访问2个字(4字节/字)，这里 是用W进行选择，不需要在外面加一个2选择1多 路器来选择。 2、全相联映射 全相联映射是多对多的映射关系：对于主存 的任何一块均可以映射到Cache的任何一行 。 特点： 主存的字块可以和Cache的任何字块(行)对应，
8、 利用率高，方式灵活，命中率高。 标志位较长，比较电路的成本太，高难于设计 和实现。如果主存空间有2m块，则标志位要有m 位。如果Cache有n块，则需要有n个比较电路。 全相联硬件实现举例 3、组相联映射 组相联映像是将Cache的行分成c=2c-r组， 每组2r行。主存的字块存放到Cache中的哪个 组是固定的，至于映射到该组哪一行是灵活 的，即有如下函数关系： j(i mod 2c)*2r+k 其中 0k2r-1 组相联映像方式特点： 组间为直接映像，组内为全相联映像。 大大增加了映射的灵活性，主存中一块可映射 到Cache 的2r块，提高了命中率。 每次比较只是进行2r路比较，r 较小
9、时，硬件 开销不是很大。 集中了两个方式的优点。成本也不太高。 组相联映像通常采用2路、4路和8路比较， 即取r=1,r=2,r=3。 组相联硬件实现举例 三种映像方式比较 全相联映射 主存中的一块可以映射到Cache中任何一个位置 直接映像 主存中的一块只能映射到Cache中唯一的一个位置 定位时，不需要判断，只需替换 多路组相联映射 主存中的一块可以选择映射到Cache中多个位置 全相联映射和多路组相联映射的失效处理 从主存中取出新块 为了腾出Cache空间，需要替换出一个Cache块 不唯一，则需要判断应替出哪块 三、替换算法 1、随机替换算法 2、先进先出算法（FIFO） 3、最近最少
10、使用算法（LRU） 该算法统计哪一个Cache行是近段时间使用次数 最少的Cache行，需替换时就将它替换出去。 LRU替换算法可以通过为每个Cache行设置一个 计数器来实现LRU替换算法，Cache每命中一次， 命中行的计数器被清零，其他行的计数器加1， 需要替换的话，就将计数器值最大的行替换出去 。 LRU算法的平均命中率比FIFO要高，并且当分 组容量加大时，能提高LRU替换算法的命中率 。如下图。 图 LRU算法替换登记表（数字为块号） 例：假定cache是直接映射的，每块4字。 Cache的容量是16字，初始时cache为空。对 于下述访问主存地址序列(字地址)： 1,4,8,5,
11、20,17,19,56,9,11,4,43,5,6,9,17 。 标出每次访问的cache命中情况以及最后cache的 内容，并计算命中率。 如果Cache访问时间为0.1s，主存的访问时间为 1s，问CPU访问内存的平均时间是多少？ 解：cache的块数=16/4=4块。 根据 Cache块号=主存地址/4 (mod 4) 可得到下表： 块0 块1 块2 块3 Cache中最后的内容如下： 主存地址范围块号 030 471 8112 12-153 16190 20231 24-272 28313 32-350 36391 40-432 44473 48510 52551 56-592 序 号
12、 12345678910111213141516 地 址 14852017195691144356917 块 号 0121100222121120 命 中 0001001001001100 块0 块1 块2 块3 地址17 地址6 地址9 空 命中率=5/16=31.25% CPU访问内存的平均时间Ta=H*Tc+(1-H)*Tm =0.3125*0.1+0.6875*1 =0.71875 四、写策略 常用的写策略通常有写贯穿和写回两种 1. 写贯穿策略 当CPU写Cache命中时，所有写操作既对 Cache也对主存进行；当CPU写Cache不命中 时，直接写主存，有两种做法： 不将该数据所在
13、的块拷贝到Cache行，称为 WTNWA法； 将该数据所在块拷贝到Cache的某行，称为 WTWA法。 2.写回策略（Write Back） 当CPU写Cache命中时，写操作只是对Cache进 行，而不修改主存的相应内容，仅当此Cache 行被换出时，相应的主存内容才被修改；当 CPU写Cache不命中时，先将该数据所在块拷贝 到Cache的某行，余下操作与Cache写命中时相 同。 为了区别Cache行是否被改写过，应为每个 Cache行设置一个修改位，CPU修改Cache行时 ，标记其修改位，当此Cache行被换出时，判 别此Cache行的修改位，从而决定是否将Cache 行数据写回主存
14、相应单元。 3、两种写策略比较 写贯穿策略保证了主存数据总是有效，写 回策略可能导致Cache和主存数据不一致； 写回策略的效率高于写贯穿策略； 写回策略的控制比写贯穿策略的控制复杂 。 五、Cache的多层次设计 设计Cache主要考虑五个问题： 容量 Cache中行的大小 Cache的组织（地址映射方式） 指令和数据共用同一个Cache还是分享不同 Cache Cache的层次 1. 统一Cache和分离Cache 统一Cache：只有一个Cache，指令和数据混 放。 分离Cache：分为指令Cache和数据Cache。 它消除了流水线中指令处理器和执行单元间 的竞争，因此，特别适用于P
15、entium 和 Power PC这样的超标量流水线中；是Cache 结构发展的趋势。 2. 单级Cache与两级Cache 一级Cache（）和二级Cache 采用两级Cache结构可以提高性能 3. Cache一致性问题 MESI协议的状态图 RH读命中； RMS读不命中，共享 ； RME读不命中，专有 ； WH写命中； WM写不命中； SHR读监听命中； SHW写监听命中或读 是用于修改； +无效处理； Cache行填入； 无效行拷回； 读用于修改 CACHE使用中的几个问题 CACHE的重要技术指标：命中率 影响 CACHE 命中率的因素 CACHE 的容量，大一些好 CACHE 与主存储器每次交换信息的单位量 (Cache Line Size)适中 CACHE 不同的组织方式，多路组相联更好 CACHE 的多级组织可提高命中率 CACHE 装满后的替换算法 cache的容量与命中率的关系 Cache Size in KB Hit Rate cache line size与缺失率的关系 多级的cache结构与命中率的关系 为增加cache容量，可以在已有的cache(第 一级)存储器系统之外，再增加一个容量更 大的cache(第二级) 。 第二级cache的容量比第一级cache的容量要 大得多，在第一级cache中保存的信息也一 定保存在第二级cac
