3.5高速缓冲存储器

程序的转移概率通常较高，数据分布也较为离散，因此单纯依赖并行主存系统来提升主存效率是有限的。高速缓存(Cache)具有比主存更快的访问速度，因此在CPU与主存之间设置Cache可以显著提升存储系统的整体效率。Cache 由SRAM组成，通常集成在CPU内部。

3.5.1 程序访问的局部性原理#

Cache的设计基于程序访问的局部性原理，包括时间局部性和空间局部性。

时间局部性是指如果某条指令或数据项当前被访问，则在不久的将来很可能再次被访问。这源于程序中存在循环、重复调用的子程序，以及对同一数据的多次操作。空间局部性是指如果某存储单元被访问，则其邻近的存储单元在不久的将来很可能也被访问。这是因为指令通常顺序存放并顺序执行，而数据（如数组、向量）也往往以连续块的形式存储。

高速缓冲技术正是利用局部性原理，将程序当前活跃的部分数据暂存于容量小但速度极快的Cache中，使CPU的多数访存操作直接在Cache中完成，从而显著提升程序执行效率。

【例3.1】 假设数组元素按行优先方式存储，对于以下两个程序：

程序A:
1
int sumarrayrows(int a[M][N])
2
{
3
    int i, j, sum = 0；
4
    for (i = 0； i < M; i++)
5
        for(j = 0; j < N; j++)
6
            sum += a[i][j] ;
7
    return sum;
8
}
程序B:
1
int sumarraycols(int a[M][N])
2
{
3
    int i, j, sum = 0；
4
    for(j = 0; j < N; j++)
5
        for (i = 0; i < M; i++)
6
            sum += a[i][j];
7
    return sum;
8
}
对于数组a的访问，哪个程序的空间局部性更好？哪个时间局部性更好？

对于指令访问，for循环体的空间局部性和时间局部性如何？

解：假设M和N均为2048，按字节编址，每个数组元素占4字节。

对于数组a，程序A和程序B的空间局部性差异显著。

程序A按行访问：a[0][0],a[0][1],···,a[0][2047];a[1][0],a[1][1],···,a[1][2047];···。访问顺序与存放顺序是一致的，由于连续访问的元素位于相邻地址，空间局部性良好。

程序B按列访问：a[0][0],a[1][0],···,a[2047][0];a[0][1],a[1][1],···,a[2047][1];···。访问顺序与存放顺序不一致，每次访问均需跨越2048个元素，即8192字节，若主存与Cache的交换单位小于8KB，则每次访问几乎都落在不同的Cache行中，空间局部性极差。

两个程序中，数组a的时间局部性均较差，因为每个数组元素仅被访问一次。

对于for循环体的指令访问，程序A与程序B的局部性表现相同。因为循环体内的指令在内存中连续存放，顺序执行，空间局部性良好；整个循环共执行 $2048 \times 2048$ 次，时间局部性良好。

综上，尽管程序A与程序B功能完全相同，但由于内外循环顺序不同，导致对数组a访问的空间局部性存在巨大差异，进而造成实际执行效率的显著不同。

3.5.2 Cache的基本工作原理#

为便于 Cache 与主存交换信息，Cache和主存都被划分为大小相等的块，Cache块也称 Cache行，每块由若干字节组成，块的长度称为块长（也称行长）。因为Cache的容量远小于主存的容量，所以Cache中的块数要远少于主存中的块数，Cache中仅保存主存中最活跃的若干块的副本。因此，可按照某种策略预测CPU在未来一段时间内待访存的数据，将其装入Cache。

1. Cache 的访问过程#

典型的Cache访问流程。CPU执行程序时，每当需要从主存取指令或读/写数据，首先访问 Cache。若所需信息已在Cache 中(称为Cache命中)，则直接从Cache读取，无须访问主存；若未命中（也称缺失），则需从主存中将该地址所在的一个主存块整体调入Cache，并将该块写入一个 Cache行(若Cache已满，则按替换算法选择被替换块)。此后，CPU再从Cache中获取所需数据。整个访问过程（包括命中判断、块调入、替换等）必须在单条指令执行周期内完成，因此完全由硬件实现。Cache机制对程序员是透明的。

上述访问流程是先查Cache，未命中再访主存，这是统考真题遵循的方式。部分系统采用“并行访问”策略（同时查Cache和主存），若命中，则提前终止主存访问，但考试中通常不涉及。

2. Cache的命中率分析#

CPU所需访问的信息已在Cache 中的概率称为Cache命中率。设某程序执行期间，Cache命中次数为 $N_c$ ，访问主存的次数为 $N_m$ (未命中次数)，则命中率 $H$ 定义为

H = N_c / (N_c+N_m)

命中时：CPU直接从Cache读取数据，耗时为命中时间 $T_c$ (访问Cache的时间)。

未命中时：需先从主存读取包含目标数据的一个主存块送入Cache，再将所需数据送至CPU，总耗时为 $T_m+T_c$ 。其中 $T_m$ 称为缺失损失，即从主存调入一个块所需的时间。

因此，Cache-主存系统的平均访问时间 $T_a$ 为

T_a = H T_c + (1-H)(T_m + T_c) = T_c + (1-H) T_m

【例3.2】 假设Cache的速度是主存的5倍，且Cache的命中率为95%，则采用Cache后，存储器性能提升多少（假设系统先访问Cache，未命中时才访问主存）？

解：设 Cache的存取时间为 $t$ ，则主存的存取时间为 $5t$ 。系统的平均访问时间 $T$ 为

$T = \text{命中时的访问时间} \times \text{命中率} + \text{缺失时的访问时间} \times \text{缺失率} = 0.95 \times t + 0.05 \times (t + 5t) = 1.25t$

或等价地

$T = \text{命中时的访问时间} + \text{缺失时的访存开销} \times \text{缺失率} = t + 0.05 \times 5t = 1.25t$

可见，采用Cache后，存储器性能提升至原来的 $5t / 1.25t = 4$ 倍。

根据 Cache的读、写流程可知，实现 Cache时需解决以下关键问题：

数据查找。如何快速判断所需数据是否在 Cache 中。
地址映射。主存块如何存放在Cache中，以及如何将主存地址转换为Cache地址。
替换策略。当Cache已满时，采用何种策略选择被替换的Cache行。
写入策略。如何在保证主存与Cache数据一致性的前提下，尽可能提升写操作效率。

3.5.3 Cache和主存的映射方式#

由于 Cache 行数远少于主存块数，Cache 只能存放主存中部分块的副本。为识别每个 Cache行对应哪个主存块，需要为每行设置一个标记位，记录其主存块编号。同时设置一位有效位，用于指示该行数据是否有效。系统启动或复位时，所有Cache行均无效；仅当主存块被装入某Cache行后，其有效位才置为1。

地址映射是指将主存地址空间按一定规则映射到 Cache 地址空间，即决定主存块如何装入Cache。常见的映射方式有三种，包括直接映射、组相联映射和全相联映射。

1. 直接映射#

主存中的每一块只能装入Cache中的唯一指定位置。若该位置已有内容，则发生块冲突，原块将被无条件替换（无须替换算法）。直接映射实现简单，但灵活性差，即使Cache中其他行空闲，也不能用于存放该主存块，因此块冲突概率最高，空间利用率最低。

直接映射关系可表示为

\text{Cache行号} = \text{主存块号} \bmod \text{Cache总行数}

设Cache共有 $2^c$ 行，主存共有 $2^m$ 块。则主存的第0块、第 $2^c$ 块、第 $2^{c+1}$ 块……均映射到Cache的第0行；主存的第1块、第 $2^c+1$ 块、第 $2^{c+1}+1$ 块……均映射到Cache的第1行，以此类推。

由此可见，主存块号的低 $c$ 位即为其对应的 Cache行号。

为标识来源，每个Cache行设置一个长度为 $t = m - c$ 的标记。当某主存块调入Cache后，将其块号的高 $t$ 位存入对应Cache行的标记字段中。

直接映射的地址结构如下

| 标记 | Cache行号 | 块内地址 |

CPU访存过程：根据访存地址中间的 $c$ 位确定Cache行，将该 Cache行中的标记与主存地址的高 $t$ 位进行比较，若标记相等且有效位为1，则Cache命中，根据地址低位的块内地址从该Cache行中读取数据；若标记不等或有效位为0，则Cache未命中，CPU需从主存读取该地址所在块，将其装入对应Cache行，置有效位为1，更新标记为地址高 $t$ 位，并将所需数据送至CPU。

2. 全相联映射#

主存中的每一块可以装入Cache中的任何位置。每行的标记用于指出该行来自主存的哪一块，因此CPU访存时需要与所有 Cache行的标记进行比较。优点：

Cache 块的冲突概率低，只要有空闲Cache行，就不会发生冲突；
空间利用率高；
命中率高。

缺点：

标记的比较速度较慢；
实现成本较高，通常需采用按内容寻址的相联存储器。

全相联映射的地址结构如下

| 标记 | 块内地址 |

CPU访存过程：首先将主存地址的高位标记（位数 $= \log_2$ 主存块数）与Cache各行的标记进行比较。若有一个相等且对应有效位为1，则Cache命中，此时根据块内地址从该Cache行中取出信息；若都不相等或有效位为0，则Cache未命中，此时CPU从主存中读出该地址所在的一块信息装入Cache的任意一个空闲行，置有效位为1，并设置标记，同时将所需数据送至CPU。

通常为每个Cache行都设置一个比较器，比较器的位数等于标记字段长度。访存时根据标记字段的内容访问Cache行中的主存块，因此其查找过程是一种按内容访问的存取方式，属于相联存储器。这种方式的时间开销和硬件开销都较大，不适合大容量Cache。

3. 组相联映射#

将Cache划分为 $Q$ 个大小相等的组，每个主存块只能映射到固定组中的任意一行，即组间采用直接映射，组内采用全相联映射。它是直接映射与全相联映射的一种折中方案：当 $Q=1$ (整个Cache为一个组)时，退化为全相联映射；当 $Q=$ Cache总行数（每组仅1行）时，退化为直接映射。设每组包含 $r$ 个Cache行，则称为 $r$ 路组相联映射。

路数 $r$ 越大，组内可选位置越多，块冲突概率越低，但所需的比较器数量和控制逻辑也越复杂。合理选择 $r$ ，可在硬件成本接近直接映射的同时，获得接近全相联映射的性能。

组相联映射关系可表示为

\text{Cache组号} = \text{主存块号} \bmod \text{Cache组数}(Q)

组相联映射的地址结构如下

| 标记 | 组号 | 块内地址 |

CPU访存过程：首先根据访存地址中的组号字段确定目标 Cache组；将该组内所有Cache行的标记与主存地址的高位标记并行比较；若某行标记匹配且其有效位为1，则Cache命中，根据块内地址从该行读取数据；若所有行均不匹配或匹配行的有效位为0，则Cache未命中，CPU从主存读取该地址所在块，将其装入该组中任意一个空闲行(若无空闲行，则按替换算法选择一行)，置有效位为1，写入标记，并将所需数据送至CPU。

直接映射中每块仅对应一个唯一的Cache行，因此只需设置1个比较器。而 $r$ 路组相联映射需在同一组的 $r$ 个 Cache行中并行比较，因此需设置 $r$ 个比较器。

在Cache容量和主存块大小固定的条件下，三种映射方式的特性对比如下：

命中率：直接映射最低，全相联映射最高。
判断开销与所需时间：直接映射最小、最快，全相联映射最大、最慢。
标记存储开销：直接映射最少，全相联映射最多。

3.5.4 Cache中主存块的替换算法#

在采用全相联映射或组相联映射方式时，当向Cache传送一个新主存块而Cache(或Cache组)已满，就需要使用替换算法选择被替换的Cache行。而在直接映射中，每个主存块只能映射到唯一的Cache行，因此当该行已被占用时，新块直接覆盖旧块，无须替换算法。

常用的替换算法包括随机、先进先出、最近最少使用和最不经常使用算法。

随机(RAND)算法：随机选择一个Cache行进行替换。实现简单，但未利用程序访问的局部性原理，命中率通常较低。
先进先出(FIFO)算法：替换最早装入的Cache行。实现较容易，但未考虑局部性原理，最早进入的块可能仍是当前热点数据，因此命中率不高。
最近最少使用(LRU)算法：基于程序访问的局部性原理，优先替换最近最久未被访问的Cache 行。其平均命中率通常高于 FIFO。LRU算法是考查重点。

TIP
手算提示：画出表后从需要替换的那位向前数，数到剩下最后一个，那个就是要替换的

在硬件实现中，LRU算法为每组Cache维护一组计数器（常称LRU替换位），用来记录各Cache行的相对访问顺序。LRU位的位数取决于组的路数：2路组相联需1位LRU位，4路组相联需2位LRU位。

计数器的更新规则：
1. 命中时，所命中行的计数器清零，比其低的计数器加1，其余不变；
2. 未命中且有空闲行时，新装入的行的计数器置0，其他非空闲行全加1；
3. 未命中且无空闲行时，替换计数值最大（本例中为3）的行，新装入的行的计数器置0，其余全加1。
当被频繁访问的主存块数量超过Cache每组的行数时，可能导致持续缺失。例如，若访问序列变为1,2,3,4,5,1,2,3,4,5，···，而Cache每组仅有4行，则每次访问第5个块都会驱逐下一个将被访问的块，导致命中率为0，这种现象称为抖动。
最不经常使用(LFU)算法：替换一段时间内累计访问次数最少的Cache行。每行设置一个计数器，新行装入时计数器初始化为0，每次访问该行则计数器加1；替换时选择计数值最小的行。LFU与LRU的思想不同：LRU关注最近是否用过，LFU关注总共用了多少次。

3.5.5 Cache的一致性问题#

由于Cache 中的内容是主存块的副本，当对 Cache进行写操作时，必须采用适当的写策略以维持 Cache 与主存数据的一致性。根据写操作是否命中 Cache，可分为两类情况。所谓写命中是指CPU要写入的主存地址所在的块当前已在Cache中；反之则为写不命中。

1. Cache写命中的处理方法#

(1) 全写法（直写法，Write Through）#

当CPU对 Cache 写命中时，数据同时写入Cache和主存。由于主存始终与Cache 保持同步，因此在替换Cache 块时，可直接覆盖，无须写回。该方法实现简单，能保证主存数据的实时正确性，但缺点是每次写操作都需访问主存，降低了系统性能。

为缓解直写法的性能开销，可在Cache与主存之间增设写缓冲(Write Buffer)。CPU将数据同时写入Cache和写缓冲，由写缓冲异步地将数据写入主存。写缓冲可缓解CPU与主存之间的速度差异。但在高频率写操作下，写缓冲可能饱和甚至溢出。

(2) 回写法(Write Back)#

当CPU对 Cache写命中时，仅将数据写入 Cache，不立即写入主存，仅在该块被替换出 Cache时才写回主存。这种方法减少了主存访问次数，提高了Cache效率，但存在数据不一致的风险。为避免不必要的写回操作，每个Cache行设置一个修改位（又称脏位）：若修改位为1，表示该行数据已被修改，替换时必须写回主存；若修改位为0，表示该行数据与主存一致，替换时可直接覆盖。需要注意的是，直写法无须脏位，因为主存始终同步；回写法则必须设置脏位。

2. Cache写不命中的处理方法#

(1) 写分配法(Write Allocate)#

当发生写不命中时，先将数据写入主存的对应单元，然后将该主存块调入Cache的一个空闲行中。该方法利用了程序的空间局部性，但每次写不命中都要将主存块加载到Cache中。

(2) 非写分配法(Not-Write-Allocate)#

当发生写不命中时，直接将数据写入主存，不将主存块调入Cache。

3.5.6 Cache容量的计算例#

在计算Cache总容量时，需考虑Cache行的数据部分和每行的标记信息，即

\text{Cache总容量} = (\text{每行标记位数} + \text{每行数据位数}) \times \text{Cache总行数}

每行的标记信息通常包括：有效位、标记位、脏位和LRU替换位。其中，有效位和标记位是所有Cache必须包含的；脏位仅在采用回写策略时存在；LRU替换位仅在使用LRU算法时存在，其位数取决于组内行数。

【例3.3】 假设某计算机的主存地址空间大小为256MB，按字节编址，其数据Cache有8个Cache行，行长为64B。请回答：

若不考虑脏位和替换算法控制位，并采用直接映射方式，求该数据Cache的总容量？

若采用直接映射方式，主存地址为3200（十进制）的主存块对应的Cache行号是多少？若采用2路组相联映射，对应的Cache组号及可能的行号是多少？

以直接映射方式为例，简述访存过程（设访存地址为0123456H）。

解：

Cache 总容量=数据信息容量+标记信息容量（包括有效位和标记位）。本题不考虑脏位和替换算法控制位。主存地址位数为28位（主存地址空间为 $256\text{MB}=2^{28}\text{B}$ )；块内地址位数为6位（行长 $64\text{B}=2^6\text{B}$ )；Cache行号为3位(Cache行数 $8=2^3$ )。标记信息位数 $=28-6-3=19$ 位。每行含1位有效位+19位标记位=20位标记信息。每行数据部分为 $64\text{B}=512$ 位。因此，Cache总容量为 $8 \times (512+1+19) = 4256$ 位。

主存地址3200对应的块号为 $3200\text{B} / 64\text{B} = 50$ 。在直接映射方式中，Cache有8行，行号 $= 50 \bmod 8 = 2$ ，故对应的Cache行号为2。

在组相联映射方式中，组内采用全相联映射，组外采用直接映射，组号 $= 50 \bmod 4 = 2$ ，即该块可映射到第2组中的任意一行，对应的Cache行号为4或5。

在直接映射方式中，28位主存地址可分为19位的标记位，3位的块号，6位的块内地址，即0000000100100011010为标记位，001为块号，010110为块内地址。访存过程：根据行号010访问Cache第2行，比较其标记与地址高19位，并检查有效位：若匹配且有效位为1，则命中，按块内地址010110读取数据并送至CPU；否则未命中，从主存读取该块，写入Cache第2行，更新标记为地址高19位，并置有效位为1。

思考： 若(1)问中采用2路组相联映射方式，则Cache总容量是多少？结合主存与Cache的划分关系，推导2路组相联映射下的主存地址结构，并简述其访存过程。

3.5.7 Cache的应用#

(1) 分离 Cache#

随着指令流水技术的发展，现代处理器通常将指令Cache和数据Cache分开设计，形成分离的Cache结构。统一Cache的优点在于其设计和实现相对简单，但在流水线执行中，取指部件和执行部件同时访问同一Cache时容易产生冲突。通过采用分离Cache结构，不仅可以消除这类冲突，还能针对指令和数据的不同局部性特征进行优化，从而提升整体性能。

(2) 多级Cache#

现代计算机普遍采用多级Cache结构。以两级为例，按距离CPU的远近分别称为L1 Cache和L2 Cache：L1离CPU最近，速度最快、容量较小；L2则较远，速度较慢、容量较大。通常情况下，L1 级会采用分离的指令Cache和数据 Cache设计，其中L1数据Cache在写操作中采用写分配法（写不命中时加载块）与回写法（写命中时不立即写主存）相结合的策略。图3.25展示了一个典型的两级Cache系统。通常，L1和L2 Cache均采用回写法，当L1发生写命中时，仅更新L1；当L1块被替换时，若为脏块，则写回L2；L2同理，在替换时写回主存。由于L2 Cache的访问速度远高于主存，L1无须在写命中时访问主存，仅更新本地 Cache即可快速完成写操作；后续的脏块写回由L2高效承接，从而有效避免因频繁写操作导致的写缓冲饱和或溢出问题。