第三章 存贮系统,3.5 Cache存储器,3.5.1 cache基本原理 1.cache的功能 cache是介于CPU和主存之间的小容量存储器，存取速度比主存快。它能高速地向CPU提供指令和数据，加快程序的执行速度。它是为了解决CPU和主存之间速度不匹配而采用的一项重要技术 .组成原理-白中英网络版Chap03images3.36.swf,3.5 Cache存储器,2. Cache的基本原理 CPU与cache之间的数据交换是以字为单位，而cache与主存之间的数据交换是以块为单位。一个块由若干定长字组成的。当CPU读取主存中一个字时，便发出此字的内存地址到cache和主存。此时cache控制逻辑依据地址判断此字当前是否在 cache中：若是，此字立即传送给CPU；若非，则用主存读周期把此字从主存读出送到CPU，与此同时，把含有这个字的整个数据块从主存读出送到cache中。由始终管理cache使用情况的硬件逻辑电路来实现LRU替换算法,3.5 Cache存储器,3.cache的命中率 增加cache的目的，就是在性能上使主存的平均出 时间尽可能接近cache的读出时间。因此,cache的命中 率应接近于1。由于程序访问的局部性 ，这是可能的。在一个程序执行期间，设Nc表示cache完成存取的 总次数，Nm表示主存完成存取的总次数，h定义为命中 率，则有 若tc表示命中时的cache访问时间，tm表示未命中时的 主存访问时间，1-h表示未命中率，则cache/主 存系统的平均访问时间ta为：,3.5 Cache存储器,【例5】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=60ns,3.5 Cache存储器,3.5.2.主存与cache的地址映射 cache的容量很小，它保存的内容只是主存内容的一个子集，且cache与主存的数据交换是以块为单位。 地址映射即是应用某种方法把主存地址定位到cache中。 址映射方式有全相联方式、直接方式和组相联方式三种,3.5 Cache存储器,1.全相联映射方式 主存中一个块的地址与块的内容一起存于cache的行中，其中块地址存于cache行的标记部分中。 这种方法可使主存的一个块直接拷贝到cache中的任意一行上，非常灵活。 它的主要缺点是比较器电路难于设计和实现,因此只适合于小容量cache采用。 全相联映射的示意图演示(P108图3.37a) .组成原理-白中英网络版Chap03images3.38.swf,3.5 Cache存储器,2.直接映射方式 这也是一种多对一的映射关系，但一个主存块只能拷贝到cache的一个特定行位置上去。 cache的行号i和主存的块号j有如下函数关系：i=j mod m（m为cache中的总行数） 直接映射方式的示意图演示(P109图3.38a) .组成原理-白中英网络版Chap03images3.39.swf 直接映射方式的优点是硬件简单，成本低。 缺点是每个主存块只有一个固定的行位置可存放,容易产生冲突。因此适合大容量cache采用。,3.5 Cache存储器,3.组相联映射方式 这种方式是前两种方式的折衷方案。它将cache分成u组，每组v行，主存块存放到哪个组是固定的，至于存到该组哪 一行是灵活的，即有如下函数关系： muv 组号qj mod u 组相联映射的示意图演示 .组成原理-白中英网络版Chap03images3.40.swf 组相联映射方式中的每组行数v一般取值较小，这种规模的v路比较器容易设计和实现。而块在组中的排放又有一定的灵活性,冲突减少。,例5,例：设主存的容量为1KB，Cache的容量为128B，每块的大小为8B。 1.直接映射、全相联映射、组相联映射（2组并联）的主存地址格式可分成哪几个部分、各占多少位？ 2.如果一个主存的地址为0010010011，试说明在上述三种映射方式下，该地址页在Cache中应处的位置，并说明CPU访问该地址的过程。,例5,解： 3 4 3 1. 直接映射 主存组号 Cache行号 块内地址 7 3 2.全相联映射 主存块号 块内地址 4 3 3 3.组相联映射 主存组号 Cache组号 块内地址 因为主存共分为1KB/8B=128个块， Cache共分为128B/8B=16个行 主存共分为128/16=8个组,2.直接映射 主存 Cache 0#块 0#行 0#组 1#块 1#行 15#块 15#行 16#块 3位的标记位 1#组 31#块 001 0010 011 1#组 2#行 3#块内 112#块 地址 7#组 127#块,组相联映射 主存 Cache 0#块 0#行 0#组 0#组 1#块 1#行 2#行 1#组 7#块 3#行 8#块 1#组 7#组 15#块 15#行 4位的标记位 120#块 15#组 0010 010 011 127#块 2#主存组 2#cache组 3#块内,例5,全相联映射 此时该地址块可存放在Cache中的任何一行。,3.5 Cache存储器,3.5.3.替换策略 cache工作原理要求它尽量保存最新数据，必然要产生替换。 对直接映射的cache来说，只要把此特定位置上的原主存块换出cache即可。 对全相联和组相联cache来说， 就要从允许存放新主存块的若干特定行中选取一行换出。,3.5 Cache存储器,3.5 Cache存储器,最不经常使用(LFU)算法 LFU算法将一段时间内被访问次数最少的那行数据换出。每行设置一个计数器。从0开始计数，每访问一次， 被访行的计数器增1。当需要替换时，将计数值最小的行换出，同时将这些行的计数器都清零。 这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，不能严格反映近期访问情况。,3.5 Cache存储器,近期最少使用(LRU)算法 LRU算法将近期内长久未被访问过的行换出。每行也设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1。当需要替换时，将计数值最大的行换出。 这种算法保护了刚拷贝到cache中的新数据行，有较高的命中率。,3.5 Cache存储器,随机替换 随机替换策略从特定的行位置中随机地选取一行换出。在硬件上容易实现，且速度也比前两种策略快。 缺点是降低了命中率和cache工作效率。,3.5 Cache存储器,3.5.4 cache的写操作策略 CPU对cache的写入更改了cache的内容。可选用写操作策略使cache内容和主存内容保持一致。,3.5 Cache存储器,写回法 当CPU写cache命中时，只修改cache的内容，而不立即写入主存；只有当此行被换出时才写回主存。 实现这种方法时，每个cache行必须配置一个修改位，以反映此行是否被CPU修改过。,3.5 Cache存储器,写回法 当CPU写cache不未命中时，为了包含欲写字的主存块在cache 分配一行，将此块整个拷贝到cache后对其进行修改。主存的写修改操作统一地留到换出时再进行。 这种方法减少了访问主存的次数,因为对Cache的多次修改，只需要一次回写到主存。但是存在不一致性的隐患。,3.5 Cache存储器,全写法 当写cache命中时，cache与主存同时发生写修改，因而较好地维护了cache与主存的内容的一致性。 当写cache未命中时，只能直接向主存进行写入。 优点是cache中每行无需设置一个修改位以及相应的判断逻辑。 缺点是cache对cpu向主存的写操作无高速缓冲功能，降低了cache的功效。,3.5 Cache存储器,写一次法 基于写回法并结合全写法的写策略,写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。这便于维护系统全部cache的一致性。 该策略主要用于处理器的片内cache,3.5 Cache存储器,MESI协议 一致性要求:如cache中某个字被修改，那么在主存中，该字的副本立即或最后加以修改,并确保其它引用主存上该字的正确性. (1)目录协议:它由位于主存的目录来保存有关各个局部cache的全局性状态信息,并由一个集中式的主存/cache控制器来维护cache一致性.,3.5 Cache存储器,(2)监听协议:将维护一致性的责任分散到各个cache控制器。它必须识别出它的cache中哪些块是与其它cache共享的.当修改一个共享块时，必须在系统中广播有关信息。监听协议又分为写修改协议和写无效协议。 MESI协议是采用写无效监听协议.,3.5 Cache存储器,每个cache行有两个状态位,用于描述该行当前处于M、E、S、I中的哪种状态,从而决定它的读/写操作行为。这四种状态的定义是: 修改态(M):此cache行以被修改过，内容不同于主存并且为此cache专有； 专有态(E):此cache行内容同于主存，但不出现在其它cache中； 共享态(S):此cache行内容同于主存，但也出现在其它cache中； 无效态(I):此cache行内容无效(空行)。,3.5 Cache存储器,3.5.5 奔腾PC机的cache 奔腾PC机采用两级cache结构。安装在主板上的2级cache(L2)采用2路组相联映射方式，集成在CPU内的 1级cache(L1)也采用2路组相联映射方式，L1又是L2的子集，从而使L1未命中处理时间大大缩短。CPU中的L1分设成各8KB的指令cache和数据cache,有利于CPU高速执行程序。 数据cache采用2路组相联结构，采用LRU替换算法，一组两行共用一个LRU二进制位。数据cache的工作方式受CPU控制寄存器CR0中CD和NW位组合状态控制，如下表3.8所示。,3.5 Cache存储器,表3.10奔腾CPU片内数据cache工作方式 其中CD=1,NW=1时复位后状态，而CD=0,NW=0时最佳使用状态,3.5 Cache存储器,两级cache和主存之间的工作环境方框图演示 .组成原理-白中英网络版Chap03images3.42.swf CPU与外部数据交换时，存储器读写总线周期主要有两类: 一类是256位猝发式传送，用于L1的行填入和行写出,一次完成整行的填入或写出。 另一类是不经L1的64位传送 ，此时CHACE仅为高电平，称为非超高速缓存式传送。,3.5 Cache存储器,L2级cache采用的是写回法，L1级数据cache采用的是写一次法。为了维护cache的一致性，L1和L2均采用MESI协议,即要求每个cache行有两个状态位，用以描述该行当前是处于修改态、专有态、共享态或者无效态中的哪种状态，从而决定对它的读/写操作行为。 总之，L2级cache的内容是主存的子集，而L1级cache又是L2级cache的子集。L2负责整个系统的cache/主存一致性，L1负责响应L2，与L2一起维护L1