分类： LINUX
2008-06-08 10:02:11
在现代处理器设计中， Cache有效地解决了处理速度和存储速度之间的匹配问题，从而成为RISC技术成功的一项重要的支撑技术。现代计算机几乎没有不含Cache的。在很多 机器中，还采用了多级Cache结构。可以说，Cache和流水线共同构成了RISC成功的两大支柱。本文将详细讨论Cache设计中的一些重要问题。
Cache设计中的四大基本问题
映射方式
相对于主存来说，Cache是一个小存储器。因此主存的块到Cache的行的映射是一种多到一映射。通常有三种映射策略：
a)直接映射
主存的一个块只能对应Cache的某一特定行。该方案中Cache被分为若干行，主存块号i对应的Cache行号为i对Cache行数的模。
b)全相连映射
主存的一个块可以存放在Cache中的任何行。
c)组相连映射
Cache行被分为M组，每组包含N行。主存的一个块和一个特定的组相对应，可存放在该组的任何一行。主存块号I映射成Cache的组号为I对Cache组数M的模。其中每组的行数N常被称为Cache的路数。
不难看到，直接映射和全相联可以看作是组相联方案的特殊形式。全相联命中率最高，但实现最复杂；直接映射实现最简单，但命中率较低。采用组相联是一种折衷方式，在总容量一定后，考虑组数M，路数N，及行中字节数L之间的配合关系。
映射机构
这 是映射方式的实现问题。在Cache中为每个行设置了一个标志以指明该行对应的主存块地址。每个Cache行的标志中可包含一些特定信息，根据这些特定信 息可以检测它们是否和来自CPU的块地址相匹配。由于速度对Cache至关重要，所以应该对所有可能的标志行并行查找。
另 外，我们必需判断出Cache中的块中是否存放着有效信息。通用解决方法是在标志上增加一个有效位，以指明该标志是否包含有效地址。若有效位未设置，则不 能对其进行匹配。由于每个Cache行都需要一个标志，所以增大行的大小对减小标志存储器占Cache总成本的比例是有益的。
替换策略
对于直接映射方式，在失效时只能对一个块进行替换，是最为简单的。但是对全相联和组相联方式，出现失效时需要在多个块中进行选择。这是我们有如下三种基本替换策略：
a)随机替换策略
这种策略就是随机的在候选块中选择一个进行替换。由于纯粹的随机选择会给硬件调试带来很大的困难，所以在一些系统中实际采用一种具有可再现能力的伪随机策略。
b)最近最少使用策略（LRU）
为了减少替换出最近可能使用的信息的机会，可以对块的访问情况进行记录。在发生Cache失效时，利用访问的时间局部性现象，替换出候选块中最近最少被访问的存储块。
c)先进先出策略（FIFO）
这种策略在Cache失效时，替换掉存放在Cache中时间最长的候选存储块。
试 验数据证明随机替换策略一般比先进先出策略性能要好，而实现也更简单。所以我们只对随机替换策略和LRU策略进行比较分析。随机策略的一个重要性质就是易 于硬件实现。随着可记录块数的增多，LRU策略的实现成本迅速增加，而性能改进一般并不十分明显。表1显示了LRU策略和随机策略在实效率方面的一些情 况。可以看出，LRU在较小的Cache中比在较大的Cache中起着更重要的作用。
存储器的写策略
对Cache主要进行的是读操作，统计数据表明通常程序的读操作至少是写操作的两倍。但Amdahl定律提醒我们面向高性能的设计绝不能忽视写操作的速度。对于写命中情况，有两种基本的写策略：
a)写透策略
信息将被同时写到Cache行和低级存储器的相应存储块中。
b)写回策略
信息仅被写到Cache的相应行中，当被改变的行被替换出Cache时，其内容才被写回到主存相应的块。
这 两种写策略各有利弊。对于写回策略，写操作能以Cache的速度来进行，而且在一个块内进行多次写操作仅需要一次对低级存储器的写动作，有益于降低对存储 器的带宽要求，使其在多处理器系统中备受重视。对于写透策略，读失效不会导致必须对低级存储器进行写操作，而且写透操作更容易实现。写透策略的另一优点是 主存中总是保存着最新数据，这对于多处理器系统和I/O设计都是非常重要的。
对于写失效情况，也有两种选择：
a)装入写
将块装入Cache，接着进行和命中情况相同的操作。
b)绕写
对低级存储器的相应内容进行改写，但不装入Cache。
上述两种写失效策略对写透和写回策略都适用，但对于写回方式，一般采用装入写策略，便于该存储块能被Cache继续利用；对于写透方式，由于后续对该存储块的写操作仍需写到主存中，故以绕写策略为好。
Cache的性能分析
之前本文介绍的各种技术的目的是减少平均访存时间。但是，设计Cache的最终目的是减少CPU的执行时间。CPU时间可以分为CPU执行时间和访存等待时间，即：
CPU时间＝（CPU执行时钟数+访存等待时钟数）×时钟周期
由于Cache失效是访存等待的最重要原因，我们假设访存等待都是有Cache失
效产生的，以简化分析。
访存等待时钟数＝（存储器访问数/程序）×失效率×失效损失
将指令总数IC提取出来单独考虑，可得：
CPU时间＝IC×(CPI执行+（访存数/指令）×失效率×失效损失)×时钟周期长度
可见，对于越小CPI的处理器，设置Cache对CPI的影响程度越大。由于计算CPI时，Cache失效的损失以CPU时钟周期为单位进行衡量，所以较高的CPU时钟频率将导致较大的失效损失。
根据CPU时间公式，可得采用Cache会增大处理器的CPI，但它可以有效减少平均访存等待的周期数，所以它是有益于提高CPU性能的。对于CPI较小，特别是RISC处理器，Cache失效对CPI的影响很严重，在设计这种处理器的时候，必须降低Cache的失效率。
Cache失效原因的分析
导致Cache失效的主要原因有以下三种：
a)突发失效
对某存储块进行第一次访问时，由于该块不在Cache中，所以必须首先将存储块取到Cache中。这种情况又称为冷启失效。
b)容量失效
如果Cache不能容纳某一程序执行过程中的所有存储块，那么当程序又需使用某一曾在Cache中，但现在已替换出的存储块时，就会出现容量失效。
c)冲突失效
在采用组相联或直接映射替换策略的Cache中，许多块都必须映射到Cache中的某一块中，由于这种原因使得当程序又需要使用某一曾在Cache中，但现在已被替换出的存储块时，就会出现冲突失效。
全 相联Cache中没有冲突失效，但增加相联度在意味着增加成本，而且可能延长访问时间，这样就会降低处理器的整体性能。要减少容量失效，就要增加 Cache的容量。上层存储器容量太小，就会频繁产生抖动现象，这意味着机器将以接近低级存储器的速度运行。增加存储块的大小可以减小突发失效的数目，但 这又会增加冲突失效的可能。这就需要在Cache的设计工作中，综合考虑三种失效情况，确定折衷的设计方案。
结束语
在现代处理器设计中，Cache有效地解决了处理速度和存储速度之间的匹配问题，从而成为现代处理器不可缺少的核心技术之一。在设计中应充分考虑各种条件的制约，权衡各种因素，才能充分提高系统的性能。
