cache合并#优质参考

1、Cache 学习5.1 Cache的必要性问题：在多层次存储器结构中，距离CPU越远，访问容量越大，访问速度越慢。解决采用存储器层次结构，实现大容量、快速存储器。每一层比下一层有更小的存储空间、更快的读写速率，价格与最便宜的一层一致，层与层之间是子集关系。桌面处理器：一次为单个用户运行一个程序，需要考虑存储器层次结构带来的延迟问题，阻止程序间数据混淆。服务器：同时为成千上百个用户执行大量应用程序，导致更多的环境切换，因此服务器还需要存储带宽问题，兼顾防止一个用户访问其他用户的数据。嵌入式：首先，用于实时处理，要考虑最坏情况时的性能，Cache能提高平均性能，但是会降低最坏情况的性能。其次，嵌入

2、式关注功耗和平均寿命，需要减少硬件，与扩展硬件提高存储性能方法相悖。第三，嵌入式操作系统一般非常简单，可不考虑存储层次保护机制。最后，嵌入式处理器内存小，常常不需要磁盘存储。5.2 Cache知识回顾名词：Cache命中，Cache缺失，块，页、页缺失。层次名称：寄存器，Cache，（块）内存，（页）磁盘5.2.1 Cache性能回顾CPU暂停工作、等待一次存储器访问的周期数成为存储器停顿周期数，其性能可以表示为:CPU执行时间=（CPU时钟周期数+存储器停顿周期数）缺失代价假设CPU时钟周期包含了处理Cache命中和Cache缺失时CPU停止的时间，存储器停顿周期数可以表示为：存储器停顿周期

3、数=缺失次数缺失代价 =执行指令数缺失次数/指令数缺失代价=执行指令数存储器访问次数/指令数缺失率缺失代价一般缺失率可用硬件Cache仿真器来测量。通常情况下，一般采用每千条指令的缺失次数来计算。5.2.2 Cache层次存储4个问题Q1：一个块，会放在哪里？直接映射：每个块在Cache中只能出现在唯一位置上，映射方法：(块地址) mod (Cache中的块数)全相联映射：一个块可以放到cache中任何一个地方。组相联映射：一个块放到一个受限的组里。一个块首先映射到到一个组中，可以放到组中任何一个块中。组通常用为选择方式确定：(块地址) mod ( cache中的组数)如果一个组里有n块，这种

4、映射方法称之为n路组向联。直接映射是一个简单的1路组相联。全相联是只有1组的m路组向联映射。Q2：怎样找到cache中的块？Cache地址分为块地址与偏移地址；块地址又分为标志字段与索引字段。偏移地址用来选择块中所需要的数据；索引字段用来选择组，通过标志字段来判断是否发生命中，无需判断块内偏移与索引字段。增加相联度会增加组内的块数，组数减少导致索引段减少，标识字段增加，最后变成全相联，不存在索引字段。Q3：没有命中，块怎样替换？直接映射法：直接替换没用命中的检查的块。全相联或组相联，需要多个块做出选择。大容量时3中方法区别不大，小容量时LRU最优：随机替换(Random)：利用伪随机数块号，尤

5、其适用于硬件调试。最近最少使用(LRU):记录块的访问次数，利用历史信息替换掉最长时间没有使用的cache块。先进先出（FIFO）。Q4:写操作时cache会发生什么？一般来说，CPU需要等待读操作完成，不需要等待写操作完成，且块标志与数据同时读出，舍弃没有命中的信息可提高速率，嵌入式系统不允许无用工作。对写操作不能进行如此优化，因为只有标识为有效时，块才能被修改。2中基本的写策略：写直达（write through）：信息同时写入cache和更低一层的存储器的块中。易实现，写直达方法中读操作缺失发生时cache始终是干净的，因此不需要对低层存储器进行写操作，常与不按写分配（no-write

6、allocate）配合。写回法（write back）：信息只写入cache。只有cache中块被替换，信息才会写回到主存中。写操作与cache速度一致，且一个块一次写入仅仅需要对下层存储器的一次写操作，因此需要较小的带宽，可用于多处理器的服务器系统。常与写分配（write allocate）配合。写操作缺失时，通常策略如下：写分配（write allocate）内存读到cache，执行命中前面写命中时的操作。与读缺失类似。不按写分配（no-write allocate），仅修改低层存储器中的该块，不将该块写入cache中，直到程序要读一个块时，该块才被取到cache中。Cache可以提供指令

7、与数据，但存在瓶颈，例如同时执行一条载入指令与存储指令，单独的cache会产生资源冲突，产生停顿。最简单的方法是将cache划分为指令cache与数据cache。指令cache比数据cache有更低的缺失率，但分立的指令cache与数据cache缺失率之和比相同容量的cache更大。5.3 Cache性能5.3.1 平均存储器访问时间指令数可以用来评价CPU的性能，缺失率可以评价存储器层次结构的性能，但也会产生误导，可用平均存储器访问时间来评定：虽然降低最小平均存储器访问时间是一个合理的目标，但是最终目标时降低CPU执行时间，两者时有区别的。例如在2路组相联情况下，虽然缺失率与平局存储器访问时

8、间较低，但进行组内多路选择时CPU时钟周期也会增加，导致CPU执行时间变长。一般观点，把命中时钟周期数包含到CPU执行时钟周期数种。Cache的行为会对较低CPI与较快时钟频率的CPU产生双重影响：1 CPI较低时，cache缺失时钟数会对CPU时间产生较大影响。2 计算CPI（cache缺失情况）时，cache缺失代价用缺失时花费的CPU时钟周期数来度量。因此，对于存储器层次结构相同的计算机，CPU频率越高，每次缺失就需要更多的时钟周期数，因此CPI花费在存储器部分的周期就较多。5.3.2 缺失代价与乱序执行处理器乱序执行（out-of-order execution）：CPU允许将多条指令

9、不按程序规定的顺序分开发送给各相应电路单元处理的技术。这样将根据各电路单元的状态和各指令能否提前执行的具体情况分析后，将能提前执行的指令立即发送给相应电路。重新定义存储器停顿周期：一般确定延迟时间的方式有3种：从存储器指令进入指令窗口的时刻算起；或是从地址产生的时刻算起；或是从指令实际被送到存储器的时刻算起。只要使用一致，任何一种方式都行。1. 索引长度确定：2. 平均存储器访问时间：3. 存储器停顿周期：4. CPU执行时间：为平均每条指令的访存次数5. 对于乱序执行处理器的平均每条指令的停顿周期数：5.4 降低Cache缺失代价5.4.1 多级cache此为降低缺失代价中最重要的方法。在原

10、cache存储器之间加一级cache，第一级cache可以小到足以与快速CPU运行时钟相匹配，第二级cache可以大到足以捕捉到对主存的大多数访问，从而减少缺失代价。缺失代价重新定义为：其中，第一级cache缺失代价为：局部缺失率：这一级cache的缺失数与这一级cache的访存总数；第一级cache中，等于；第二级中，等于。全局缺失率：这一级cache的缺失数与CPU产生的访存总数；第一级中，等于；第二级中，等于。第二级局部缺失率比较大，因为第一级cache存储数据是最易命中的，所以全局缺失率是一个更有用的度量方法。此时每条指令的缺失次数重新提出：首先，可以选择价高相联度来降低第二级缺失率，

11、可降低缺失代价。其次，多级包含的存储器结构便于检查I/O口与cache之间的一致性，但缺点是，当二级cache发生缺失时，要保证与之对应的一级cache块无效，从而会导致一级cache缺失率略微升高。当二级cache只比一级cache大一点时，可以采用多级互斥（multilevel exclusion）。一级cache缺失时只会导致两者之间进行对应的块互换，而不是用第二级cache中的块去替换一级cache中的块，防止二级cache空间浪费。5.4.2 关键字优先和提前启动给予CPU在某一个时刻只需要块中的一个字，不必要等全部块装入便可启动CPU，具体如下：关键字优先：首先向存储器请求缺失的字

12、，然后它一旦到达便把它发给CPU，使得CPU在装入其他字的同时能够继续执行其他指令。提前重启动：以正常顺序获取字，块中所需字一旦到达，立即发给CPU，使得CPU继续执行。通常这些技术适用于大cache块设计，否则收益甚微。5.4.3 确定读缺失对写的优先级例如写缓存区中可能包含读缺失时所需要的更新数据，此时最简单的方法是读缺失等待、直到写缓存为空为止。另一种方案时读缺失时查看缓存的内容，如果没有冲突且存储器系统可以访问，就让读缺失继续。一般后者多用。写回法的cache中，处理器的写开销也可以降低。当读缺失发生时，脏块将被代替。我们可以把脏块复制到一个缓存区后就读下一层的存储器，而不是先把脏块写

13、入下一层存储器，然后再对下一层存储器进行读操作。这样可以很快的完成读操作。5.4.4合并缓冲区所有的存储都必须放到较低一级的存储层次上，因此写直达的cache也依靠写缓冲。写缓冲为空时，从CPU角度来说，将被替换掉的数据和地址都放到写缓冲中，写操作就结束；写缓冲区将数据写回内存时，CPU可继续工作。如果写缓冲里还有其他数据被修改过，检查地址，看新数据地址是否与缓冲区的某一项地址相匹配。如果匹配，新数据合并到该项中，此过程曾为“写合并”。写缓冲满、且地址不能匹配，cache与CPU必须等待，直到缓冲区空出一个项。因为一次写多个字比一次写一个字速度更快。5.4.5 牺牲cache保存被替换掉的块，

14、以便下一次使用。该循环方案是在cache与它的替换路径之间增加小容量的全相联cache。这个牺牲cache（victim cache）之包含cache中因为缺失而被替换出的块，然后发生缺失时，在访问下层存储器之前，先检查牺牲块，看其中是否包含所需数据。5.5 降低Cache缺失率3种缺失模型：a.强制缺失：对一个块的第一次访问一定不在cache中，所以该块必须调入到cache中。可以增加块大小来减少该缺失，但是又会导致其他种类的缺失。b.容量缺失：如果cache容纳不了一个程序执行所需的所有块，将会发生容量缺失（还会有强制缺失），某些块被抛弃随后再被调入。只能增大cache容量减少该缺失，但如

15、果上层存储器空间很小，很多时间会花费在层次结构两层之间搬运数据上，称之为存储器层次结构的抖动现象。因此，机器速度接近于较低层。c.冲突缺失：如果块替换策略时组相联或直接映射的，并且有太多的块被映射到同一组中，则某一个块被抛弃，之后重新调入，这时就发生了冲突缺失（还会有强制缺失与容量缺失）。全相联可以避免所有的冲突缺失，但是硬件昂贵，同时可能会使处理器处理时钟变慢。但是三种模型存在矛盾、局限的。改变cache容量，则缺失可能会由容量缺失变为冲突缺失。增加组相联度会使降低缺失率，与增加块容量降低缺失率的强制缺失也是矛盾的。所以，要寻求平衡点。5.4.1 增加块容量此为最简单的方法。但是它减少了块数

16、，更大的块可能导致冲突缺失，如果cache容量较小，可能会导致容量缺失。块容量的选择取决于较低层存储器的延迟和带宽：高延迟和高带宽存储器尽量使得块容量大一些，因为此时每次缺失时cache可以获得更多的字节，而缺失代价只有少量的增加。相反，低延迟、低带宽希望块容量小一些，因为较大的块并不能节省很多时间。例如，小容量块缺失的代价的两倍可能接近于两倍容量块一次缺失的代价，块容量小，块数量多，可能会减少冲突缺失。5.4.2 增加cache容量能减少容量缺失，但是会时cache命中时间增加，开销增大。5.4.3 增加相联度根据缺失率随相联度改善的的情况，得到2个一般结论：a.8路组相联和相同容量的全相联

17、cache在降低cache缺失率方面同样有效，因为容量缺失时用全相联cache来计算的。b.容量为N的直接映射同容量为N/2的2路组相联cache几乎有相同的缺失率。所以cache容量一般少于128KB。但是，增加相联度会导致命中时间增加；增加块容量会降低缺失率，但也增加了缺失代价。5.4.4 路预测与伪相联cache路预测:在cache中设置预测位，来预测下一次cache访问中可能会在组中用到的路或块。该方式需要提前利用多路选择器来选择即将被访问的块，只需要在一个时钟周期内比较一个简单的标志位。如果缺失，在检查其他块是否匹配。该方案可以在降低冲突缺失的同时，保证cache的命中速度。伪相联：

18、命中时，该过程同直接映射的cache访问过程一致。缺失时，在访问下一层存储器之前，通过检查另一个cache项确当是否在那里命中。最简单的方法是对索引字段中的最高位进行反转来发现“伪组”中的另一块。第一个缺点，如果cache快的命中时间变为伪相联cache中长命中时间，性能会下降，因此需要指出每个组中哪一个时快时间命中，哪一个时慢时间命中。最简单的方法时令高位的块为快的块，通过交换块中内容进行切换。第二个缺点是：检查另一个cache项有时间开销。5.4.5 编译优化不需要硬件改动，保证程序代码正确性的前提下，对软件进行优化。可分为指令缺失性能改善与数据缺失性能改善。例如，对指令重新编排，对块进行排序，利用分块算法，改进数据的空间和时间局部性来减少缺失率。5.6 通过并行减低缺失率或缺失代价5.6.1 用非阻塞cache减少缺失停顿对于乱序执行的流水线机器，C