Cache 速算 — Tianyi Chen

技巧 1：Index + Offset 就是单路容量#

如上图：

\left\{ \begin{aligned} \text{单路容量}&=\text{Cache 容量}\div\text{路数}=2^{\text{Index}+\text{Offset}}\text{ B}\\ \text{Tag 位数}&=\text{地址位数}-(\text{Index}+\text{Offset}) \end{aligned} \right.

例题

给出：32 位地址，Cache 32KB，4 路组相联，块 64B。

求：Tag、Index、Offset 各几位。

解：

单路容量： $32\text{KB}\div4=8\text{KB}=2^{13}\text{B}$ ，Index + Offset = 13 位。
Tag： $32-13=19$ 位。只问 Tag 的话到这里就做完了，块大小都用不上。
拆 Index 和 Offset：块 $64\text{B}=2^6\text{B}$ ，Offset = 6 位，Index = $13-6=7$ 位。

\underbrace{\qquad\text{Tag}\qquad}_{19\text{ 位}} \;\Big|\; \overbrace{\underbrace{\;\text{Index}\;}_{7\text{ 位}} \;\Big|\; \underbrace{\;\text{Offset}\;}_{6\text{ 位}}}^{13\text{ 位} = 8\text{KB 单路}}

题目不给地址位数、只给主存大小时，主存除以单路容量就行：

\text{Tag 位数}=\log_2\left(\text{主存}\div\text{单路容量}\right)

比如主存 4GB，一路容量 8KB，就是 $2^{32}\div2^{13}=2^{19}$ ，Tag 还是 19 位。

技巧 2：十六进制消消乐#

题目一般会给一个十六进制地址，问它在第几组。地址由 Tag + Index + Offset 拼成，求组号其实就是求 Index：把头上的 Tag 和尾巴的 Offset 砍掉，剩下的就是。

注意： 不用把整个地址展开成二进制。1 个十六进制位 = 4 个二进制位，只展开被 Tag、Offset 截断的那一两位就行，如下：

例题

给出：Tag 19 位，Index 7 位，Offset 6 位，地址 0x12347AC8。

求：它在第几组。

解：

左边砍 Tag： $19=4\times4+3$ 。前 4 个十六进制位 1234 占 16 位，全是 Tag，划掉。第 5 位是 7，展开是 0111，Tag 再拿走前 3 位 011，只留最后 1 位 1 给 Index。

其实只留最后 1 位的话，7 都不用展开：奇数末位就是 1，偶数就是 0。
右边砍 Offset： $6=1\times4+2$ 。最后 1 位 8 占 4 位，全是 Offset，划掉。倒数第 2 位是 C，展开是 1100，Offset 再拿走最后 2 位 00，留下前 2 位 11 给 Index。
中间照抄：夹在 7 和 C 中间的 A 是 1010，整个属于 Index。

\underbrace{\texttt{1234}}_{\text{16 位，全是 Tag}}\;\underbrace{\texttt{0111}}_{\texttt{7}}\;\underbrace{\texttt{1010}}_{\texttt{A}}\;\underbrace{\texttt{1100}}_{\texttt{C}}\;\underbrace{\texttt{1000}}_{\texttt{8}}

\underbrace{\cdots\,\texttt{011}}_{\text{Tag 19 位}} \;\Big|\; \underbrace{\texttt{1}\,\texttt{1010}\,\texttt{11}}_{\text{Index 7 位}} \;\Big|\; \underbrace{\texttt{00}\,\texttt{1000}}_{\text{Offset 6 位}}

Index 是 1101011，即 $64+32+8+2+1=107$ ，第 107 组。

技巧 3：数组地址跳跃#

数组名后面第一个方括号是第一维，第二个是第二维，依次类推：

\texttt{int a}\underbrace{\texttt{[64]}}_{\text{第一维}}\underbrace{\texttt{[64]}}_{\text{第二维}}

C 语言按行优先存放，最后一维的元素挨着放：a[0][0]、a[0][1]……a[0][63] 放完，才轮到 a[1][0]。第一维每加 1，地址就跳过一整个第二维，也就是 $64\times4\text{B}$ 。

例题

给出：单路容量 4KB，int a[64][64]（每个 int 4B），a[0][0] 在 0x00401000。

求：a[16][0] 的地址，以及它和 a[0][0] 是否同组。

解：

第二维 64 个元素，每个 4B。从 a[0][0] 到 a[16][0]，第一维跳了 16：

64\times4\text{B}\times16=2^6\times2^2\times2^4\text{B}=2^{12}\text{B}=4\text{KB}

12 位正好是 3 个 4 位二进制，也就是 3 个十六进制的 0，秒出 0x1000：

text

0x00401000 + 0x1000 = 0x00402000

判同组：一路 4KB，Offset + Index 也是 12 位。地址正好加了 $2^{12}$ ，只动了 12 位往上的 Tag，低 12 位的 Index 和 Offset 都没变，同组。

注意： 判断同组的标准做法是比 Index 是否相同。相减是单路容量的整数倍，只是一个快速判断：是整数倍，就一定同组；不是整数倍，还得回去比 Index。比如 Index + Offset 共 13 位，单路容量就是 0x2000。0x12347AC8 和 0x9876FAC0 尾巴一个 8 一个 0，相减不是 0x2000 的整数倍，但 Index 相同，照样同组。

技巧 4：Cache 硬件总容量#

注意区分 Cache 数据容量和 Cache 硬件总容量。硬件不光存数据，每一块还要额外存 Tag，以及题目给的各种状态位。比如：

有效位：1 位，标记这格有没有装数据。
脏位：题目说采用回写法，就加 1 位。
LRU 替换位： $K$ 路 LRU 就是 $\log_2K$ 位。

\text{总容量}=\text{总块数}\times(\text{Tag}+\text{状态位}+\text{块大小}\times8)

其中，总块数 = Cache 容量 ÷ 块大小，也等于路数 × $2^{\text{Index}}$ 。

注意： 数据位 = 块大小 × 8，64B 就是 512 位。Offset 是地址里的字段，Cache 里不存。

技巧 5：数组顺序遍历命中率#

一个 Cache 块能装下的元素个数：

N=\text{块大小}\div\text{单个元素大小}

变形一：除不尽，向上取整算 Miss#

int a[64][64]，第二维 64 个元素，但内层循环只跑前 50 个（j < 50）：

\underbrace{16\text{ 个}}_{\text{块 1}} \;\Big|\; \underbrace{16\text{ 个}}_{\text{块 2}} \;\Big|\; \underbrace{16\text{ 个}}_{\text{块 3}} \;\Big|\; \underbrace{2\text{ 个}}_{\text{块 4}}

50 个元素要搬几块？ $\lceil50\div16\rceil=4$ 块，前 3 块装 48 个，第 49、50 个逼着硬件去搬第 4 块。
搬 4 块就是 4 次 Miss。访问 50 次，Miss 4 次，命中率 $\frac{50-4}{50}=92\%$ 。

变形二：看清有没有赋值（一读一写，访问翻倍）#

对比这两行（假设 sum 在寄存器里）：

sum += a[i];：只对 a[i] 做一次读（Load）。
a[i] = a[i] + 10;：先把 a[i] 读（Load）出来加 10，再把结果写（Store）回 a[i]。

每个元素 1 次 Load + 1 次 Store，共 2 次访存。第一次 Load 就算 Miss，块也已经搬进 Cache 了，紧接着对同一个 a[i] 的 Store 一定命中。

块内 16 个元素一共 $16\times2=32$ 次访存，还是只有开头 1 次 Miss，命中率从 $\frac{15}{16}$ 变成 $\frac{31}{32}$ 。

看到 a[i] = a[i] + ...，访问次数乘 2，Miss 次数不变。

变形三：外层套循环重复遍历（Miss 率被稀释）#

外面套一层 for (int k = 0; k < 10; k++)，而且整个数组不超过 Cache 容量（能全部塞进 Cache）：

只有第 1 遍（k = 0）有 Miss。
第 2 到 10 遍，整个数组已经在 Cache 里了，全部命中。

总 Miss 数不变，总访问次数乘 10，未命中率从 $\frac{1}{16}$ 稀释成 $\frac{1}{16}\div10=\frac{1}{160}$ 。

技巧 6：按列遍历与颠簸（Thrashing）#

二维数组按列遍历（外层 j++，内层 i++ 跨行跳）时，访问完 a[0][0]（把 a[0][0..15] 搬进 Cache），下一步却跳去下一行的 a[1][0]，刚搬进来的 a[0][1..15] 一个都没用上。

等第 0 列扫完、外层来到 j = 1 去访问 a[0][1] 时，a[0][0..15] 还在不在 Cache 里？

这取决于扫第 0 列的过程中，映射到同一组的那些行有没有把它挤出去。地址每差一个单路容量，就落回同一组。一列从上扫到下，跨过几个单路容量，同一组就要挤进几块：

\text{同组竞争块数}=\text{一列跨过的字节数}\div\text{单路容量}

同组竞争块数 > 路数：同一组装不下，先进来的块等不到下一列就被踢走，这就是颠簸（Thrashing）。只读命中率 0%，一读一写 50%。过程见综合题第 3 问。
同组竞争块数 ≤ 路数：第 0 列扫完，搬进来的块全都还在，后面几列全部命中。命中率和按行遍历一样，是 $1-\frac{1}{N}$ 。

综合题#

例题

给出：32 位计算机，按字节编址。数据 Cache 容量 8KB，2 路组相联，块大小 64B，LRU 替换。

C 语言二维数组 int a[64][64]（每个元素 4B），按行优先存放，首地址 a[0][0] 为 0x00401000。Cache 初始为空，只考虑对数组 a 的访存。

代码甲：

for (int i = 0; i < 64; i++)
    for (int j = 0; j < 64; j++)
        a[i][j] = a[i][j] + 10;

代码乙：

for (int j = 0; j < 64; j++)
    for (int i = 0; i < 64; i++)
        sum += a[i][j];

求：

主存地址中 Offset、Index、Tag 各占几位？单路容量的十六进制是多少？a[16][0] 与 a[0][0] 是否映射到同一组？
代码甲的命中率是多少？内层循环改成 j < 50，命中率又是多少？
代码乙的命中率是多少？
代码乙的内层循环改成 i < 32，命中率变成多少？

解：

第 1 问#

求 Offset、Index、Tag 位数：
- 块大小 $64\text{B}=2^6\text{B}$ ，Offset = 6 位。
- 单路容量 $8\text{KB}\div2=4\text{KB}=2^{12}\text{B}$ ，Index + Offset = 12 位。
- Index = $12-6=6$ 位，一共 $2^6=64$ 组，组号 0 到 63。
- Tag = $32-12=20$ 位。
$\underbrace{\qquad\text{Tag}\qquad}_{20\text{ 位}} \;\Big|\; \underbrace{\;\text{Index}\;}_{6\text{ 位}} \;\Big|\; \underbrace{\;\text{Offset}\;}_{6\text{ 位}}$
单路容量和 a[16][0]：
- 单路容量 $2^{12}\text{B}$ ，12 位是 3 个十六进制的 0，即 0x1000。
- 第二维 64 个元素，每个 4B，第一维跳了 16： $64\times4\text{B}\times16=2^{12}\text{B}$ ，正好也是 0x1000。
- a[16][0] 的地址是 0x00401000 + 0x1000 = 0x00402000。
- 地址正好加了一个单路容量，低 12 位不变，同组（都是第 0 组）。

第 2 问#

代码甲内层是 j++，顺着行遍历。一个块装 16 个元素，a[i][j] = a[i][j] + 10; 一读一写，每个元素访存 2 次。

j < 64：每块 32 次访存，1 次 Miss，命中率 $\frac{31}{32}$ ，即 $96.875\%$ 。
j < 50：每行 $\lceil50\div16\rceil=4$ 块，4 次 Miss；访存 $50\times2=100$ 次，命中率 $\frac{100-4}{100}=96\%$ 。

第 3 问#

代码乙外层 j++、内层 i++，是按列遍历，而且 sum += a[i][j] 只有 1 次读。

先算一件事：数组一行 256B，一个 Cache 块 64B，每往下走一行（i++），主存里就跨过 $256\div64=4$ 个块，组号 +4。

\underbrace{\texttt{a[i][0..15]}}_{\text{组 }4i} \;\Big|\; \underbrace{\texttt{a[i][16..31]}}_{\text{组 }4i+1} \;\Big|\; \underbrace{\texttt{a[i][32..47]}}_{\text{组 }4i+2} \;\Big|\; \underbrace{\texttt{a[i][48..63]}}_{\text{组 }4i+3}

固定外层 j = 0（扫第 0 列），内层 i 从 0 走到 63，访问的块落在这些组（组号到 64 就绕回 0）：

\underbrace{0,4,\dots,60}_{i=0\sim15} \;\Big|\; \underbrace{0,4,\dots,60}_{i=16\sim31} \;\Big|\; \underbrace{0,4,\dots,60}_{i=32\sim47} \;\Big|\; \underbrace{0,4,\dots,60}_{i=48\sim63}

每次访问都是 Miss，一共 4 轮：

第 1 轮（i = 0..15）：把组 0、4……60 的 Way 0 填满。
第 2 轮（i = 16..31）：把这些组的 Way 1 填满。
第 3 轮（i = 32..47）：组已经满了，按 LRU，第 1 轮进来的第 0 到 15 行被踢出。
第 4 轮（i = 48..63）：第 2 轮进来的第 16 到 31 行也被踢出。

单看第 0 组，第 0、16、32、48 行都要进来（同理，第 1、17、33、49 行都要进第 4 组……）：

\text{组 0}:\;\underbrace{\text{第 0 行},\;\text{第 16 行}}_{\text{先进来，被踢出}},\;\underbrace{\text{第 32 行},\;\text{第 48 行}}_{\text{留在组 0}}

4 个块抢 2 个位置。j = 0 这一列扫完时，第 0 组里只剩第 32 行和第 48 行，第 0 行和第 16 行早就被踢出 Cache 了。算一下也一样：一列跨 $64\times256\text{B}=16\text{KB}$ ， $16\text{KB}\div4\text{KB}=4>2$ ，必然颠簸。

接着外层进入 j = 1（扫第 1 列）：

i = 0 读 a[0][1]：去第 0 组找第 0 行，早被踢走了，Miss。搬回第 0 行，又把第 32 行踢走。
i = 16 读 a[16][1]：去第 0 组找第 16 行，也早被踢走了，Miss。搬回第 16 行，又把第 48 行踢走。
i = 32 读 a[32][1]：第 32 行刚才被 i = 0 踢走了，Miss。
i = 48 读 a[48][1]：第 48 行刚才被 i = 16 踢走了，Miss。

这就是颠簸（Thrashing）。每次搬进来的块，里面明明装着后面 15 列要用的数据，却在用到之前就被同一组的其他行挤掉了。每次访存全部落空，命中率 0%。

第 4 问#

代码乙的内层循环改成 i < 32：

i 只从 0 走到 31，只有第 3 问里的第 1、2 轮。
再看第 0 组：只有第 0 行（i = 0）和第 16 行（i = 16）映射到第 0 组，没有第 32 行和第 48 行了。
2 行抢第 0 组，Cache 正好是 2 路组相联。Way 0 放第 0 行，Way 1 放第 16 行，谁也不用踢谁，全部装下。

算一下也一样：一列跨 $32\times256\text{B}=8\text{KB}$ ， $8\text{KB}\div4\text{KB}=2\le2$ ，不颠簸。

既然不会互相踢出：

j = 0（第 0 列）：i 从 0 走到 31，这 32 次访问全部 Miss，把每行开头的块 a[i][0..15] 全搬进 Cache。
j = 1 到 15（接下来 15 列）：访问 a[i][1] 到 a[i][15]，数据都在 Cache 里，15 列全部命中。
j = 16：进入下一块 a[i][16..31]，又是“1 列 Miss + 15 列 Hit”。

每 16 列里 1 列 Miss、15 列 Hit，命中率 $\frac{15}{16}$ ，即 $93.75\%$ 。

作业#

作业2010 年 408 第 44 题

某计算机的主存地址空间大小为 256MB，按字节编址。指令 Cache 和数据 Cache 分离，均有 8 个 Cache 行，每个 Cache 行大小为 64B，数据 Cache 采用直接映射方式。现有两个功能相同的程序 A、B，其伪代码如下所示：

程序 A：

int a[256][256];
...
int sum_array1()
{
    int i, j, sum = 0;
    for (i = 0; i < 256; i++)
        for (j = 0; j < 256; j++)
            sum += a[i][j];
    return sum;
}

程序 B：

int a[256][256];
...
int sum_array2()
{
    int i, j, sum = 0;
    for (j = 0; j < 256; j++)
        for (i = 0; i < 256; i++)
            sum += a[i][j];
    return sum;
}

假定 int 类型数据用 32 位补码表示，程序编译时 i、j、sum 均分配在寄存器中，数组 a 按行优先方式存放，其首地址为 320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

若不考虑用于 Cache 一致性维护和替换算法的控制位，则数据 Cache 的总容量为多少？
数组元素 a[0][31] 和 a[1][1] 各自所在的主存块对应的 Cache 行号分别是多少（Cache 行号从 0 开始）？
程序 A 和 B 的数据访问命中率各是多少？哪个程序的执行时间更短？

看答案

答：

第 1 问：主存 $256\text{MB}=2^{28}\text{B}$ ，地址 28 位。直接映射就是 1 路，单路容量就是整个 Cache： $8\times64\text{B}=512\text{B}=2^9\text{B}$ ，Index + Offset = 9 位，Tag = $28-9=19$ 位。

每个 Cache 行： $1\text{（有效位）}+19\text{（Tag）}+64\times8\text{（数据）}=532$ 位，总容量 $8\times532=4256$ 位，即 532B。

第 2 问：块 $64\text{B}=2^6\text{B}$ ，Offset 6 位，Index $9-6=3$ 位。首地址 320 就是 0x140。

a[0][31]： $320+31\times4=444$ ，即 0x1BC。
a[1][1]： $320+(256+1)\times4=1348$ ，即 0x544。

看低 9 位，前 3 位是 Index：

\texttt{0x1BC}:\;\underbrace{\texttt{110}}_{\text{Index}}\;\underbrace{\texttt{111100}}_{\text{Offset}} \qquad \texttt{0x544}:\;\underbrace{\texttt{101}}_{\text{Index}}\;\underbrace{\texttt{000100}}_{\text{Offset}}

a[0][31] 在 Cache 第 6 行，a[1][1] 在 Cache 第 5 行。

第 3 问：

程序 A 内层循环走第二维，地址连续，顺序读。一块装 $64\div4=16$ 个 int，首地址 $320=5\times64$ 正好是块的开头，命中率 $\frac{15}{16}=93.75\%$ 。
程序 B 内层循环走第一维。第二维 256 个元素，第一维每加 1，地址加 $256\times4\text{B}=1\text{KB}$ ，正好是 2 个单路容量（512B），内层循环读到的元素全落在同一个 Cache 行。内层循环跨 $256\times1\text{KB}=256\text{KB}$ ， $256\text{KB}\div512\text{B}=512$ 块抢 1 个位置，每次都 Miss，命中率 0。

程序 A 命中率高，执行时间更短。