🏷️ 知识点：Cache映射方式

假定主存地址位数为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字， 每字32位，写操作时采用回写 (Write Back) 方式，则能存放4K 字数据的Cache 的总容量的位数至少是 ()。

A.146K

B.147K

C.148K

D.158K

[tag_link]

正确答案：C

直接映射的 地址结构 为： 主存字块标记 | 行号 | 块内地址 主存块大小为 4 个字，每字 32 位，因此块大小为： 4 × 32 bit = 128 bit = 16 B 。计算机按字节编址，故块内地址占 lo g 2 ( 16 ) = 4 位。Cache 可存放 4K 字数据，块大小为 4 字，因此 Cache 行数为： 4 K /4 = 1 K = 1024 ， 行号占 lo g 2 ( 1024 ) = 10 位。主存地址位数为 32 位，块内地址占 4 位，行号占 10 位， 因此主存字块标记占 32 − 4 − 10 = 18 位。写操作采用回写（Write Back）方式，每行标记字段包括： 18 位主存字块标记、1 位有效位、1 位脏位， 合计 18 + 1 + 1 = 20 位。每行数据部分大小为 4 字 × 32 位 = 128 位。Cache 总容量为： ( 20 + 128 ) × 1024 = 148 × 1024 位 = 148 Kb

有如下 C 语言程序段：

for (k = 0 ;k< a[k]=a[k]+

1000;k++) 32;

若数组 a 以及变量 k 均为 int 型 ，int 型数据占4B, 数据 Cache 采用直接映射方式，数据区大小是 1KB, 块大小是16B, 该程序段执行前 Cache 为空，则该程序段执行过程中，访问数组 a 的 Cache 的 缺失率是()。

A. 1.25% B. 2.5% C. 12.5% D. 25%

[tag_link]

正确答案：C

分析语旬 a[k] = a[k] + 32 : 首先读取 a[k] 需要访问一次 a[k] ，之后将结果赋值给 a[k] 需要访问一次，共访问两次。第一次访问 a[k] 未命中，并将该字所在的主存块调入 Cache 对应的块中，对于该主存块中的 4 个整数的两次访问中只在访问第一次的第一 个元素时发生缺失，其他 的 7 次访问中全部命中，故该程序段执行过程中访问数组 a 的 Cache 缺失率约为 1/8（即 12.5%）。

若计算机主存地址为32位，按字节编址，Cache 数据区大小为32KB, 主存块大小为32B, 采用直接 映射方式和回写( Write Back) 策略，则Cache行的位数至少是()。

A.275

B.274

C.258

D.257

[tag_link]

正确答案：A

由于是 直接映射 ，所以物理地址的结构分为以下几个部分： | Tag（17 bits） | Cache 块号（10 bits） | 块内偏移（5 bits） | Cache 行包含以下几个部分：标记（tag 17bits）、有效位（valid 1bit）、修改位（dirty 1bit）、数据区（32B） Cache 行的大小为 17 + 1 + 1 + 32 * 8 = 275

某计算机主存地址为32位，按字节编址，某Cache的数据区容量为32KB, 主存块大小为64B, 采用 8路组相联映射方式，该Cache 中比较器的个数和位数分别为()。

A.8,20

B.8,23

C.64,20

D.64,23

[tag_link]

正确答案：A

Cache 采用 组相联映射 ，主存地址结构应分为 Tag 标记、组号、块内地址三部分。主存块大小 = Cache 块大小 = 64B = 2 6 B，因此块内地址占 6 位。Cache 数据区容量为 32KB, 每个 Cache 块大小为 64B，则 Cache 总块数 = 32KB/64B = 2 9 ，由于采用 8 路组相联映射，即 每 8 个 Cache 块为一个分组，因此总共被分为 2 9 /8 = 2 6 组，因此，组号占 6 位。除了块内地 址和组号，剩余的位为 Tag 标记，占 32-6-6=20 位。地址结构如下所示。Tag 标记 组号 块内地址 20 位 6 位 6 位 Cache 采用 8 路组相联映射，因此在访问一个物理地址时，要先根据组号定位到某一分组，然 后用物理地址的高 20 位（Tag 标记）与分组中 8 个 Cache 行的 Tag 标记做并行比较（用 8 个 20 位“比较器”实现），若某个 Cache 行的 Tag 标记与物理地址的高 20 位完全一致，则选 中该 Cache 行。综上所述，在组相联映射的 Cache 中，“比较器”用于并行地比较分组中所 有 Cache 行的 Tag 标记位与欲访问物理地址的 Tag 标记位，因此比较器的个数就是分组中的 Cache 行数 8，比较器的位数就是 Tag 标记位数 20。

假设某计算机按字编址，Cache 有4个行， Cache 和主存之间交换的块大小为1个字。若Cache 的内 容初始为空，采用2路组相联映射方式和LRU 替换策略。访问的主存地址依次为0,4,8,2,0,6,8,6,4,8时， 命中Cache 的次数是()。

A.1

B.2

C.3

D.4

[tag_link]

正确答案：C

地址映射采用 2 路 组相联 ，则主存地址为 01、45、89 可映射到第 0 组 Cache 中，主存地址为 23、6~7 可映射到第 1 组 Cache 中。Cache 置换过程如下表所示。

注："_" 表示当前访问块，"*" 表示本次访问命中。

注意：在不同的《组成原理》教材中，关于组相联映射的介绍并不相同。通常采用唐朔飞教材中的方式，但本题中采用的是蒋本珊教材中的方式。可以推断两次命题的老师应该不是同一位老师，这也给考生答题带来了困扰。

计算机 M 字长为 32 位，按字节编址，数据 cache 的数据区大小为 32KB，采 8 路组相联，主存块大小为 64B，cache 命中时间为 2 个时钟周期，缺失损失为 200 个时钟周期，采用页式虚拟存储，页大小为 4KB。数组 d 的起始地址为 0180 0020H（VA31~VA0）。

(1) 主存地址中的 Cache 组号，块内地址分别占几位？VA 中哪些位可以作为 Cache 索引。

(2) d[100] 的 VA 是多少？d[100] 所在主存块中对应的 Cache 组号是多少？

(3) 设代码已经在 cache 中，i,x 已装入内存，但不在 cache，则 d[0] 在其主存块内的偏移量是多少？执行 for 的过程中，访问 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少？（缺失率用百分比表示，保留两位小数）

(4) d 分布在几个页中？若代码已在主存，d 不在主存，则执行 for 的过程中，访问 d 所引起的缺页次数是？

int x, d[2048], i;
for (i = 0; i < 2048; i++)
    d[i] = d[i]/x;

虚拟页式管理 cache映射方式 缺页异常

[tag_link]

1）cache 块大小和主存块大小一致为 64B，所以块内偏移为 6 位（26=64）。cache 块的数量为 32KB / 64B = 512，由于采用 8 路组相连，所以总共有 512 / 8 = 64 个组，组号占 6 位（26=64）。所以第 6 位到第 11 位可以作为 Cache 索引（用来定位地址可能被哪一组所缓存）。

2）&d[100] = d + 100 * 4 = 0x0180 0020 + 400 = 0x0180 01B0，对应的二进制为 0000 0001 1000 0000 0000 0001 1011 0000，组号为 000110B 即 6。

3）物理地址的结构为：页内偏移 12 位，物理页号 20 位，所以 &d[0] 的页内偏移为 020H = 32。数组总共需要用 2048 * 4 / 64 = 128 个完整 cache 块存储，但由于数组第一个元素处于某个 cache 的中间（偏移为 32），所以总共需要 129 个 cache 块存储，在访问每个 cache 块中的第一个元素时会发生 Cache 缺失。另外需要注意一点，对于指令 d[i] = d[i] / x，实际上是访问了两次：一次读取，一次写入。所以在计算缺失率和平均访问时间的时候需要考虑这两次访问。缺失率 = 129 / (2048 * 2) ≈ 3.15%。数组的平均访问时间为 = (129 * 200 + (4096 - 129) * 2) / 4096 ≈ 8.24 个时钟周期。

4）数组 d 需要占用 8KB 的存储空间，占用两个页面。由于数组的起始地址处于页面内部（偏移 32B），所以数组 d 分布在三个页面中，触发的缺页次数为 3。

某计算机采用页式虚拟存储管理方式，按字节编址。CPU 进行存储访问的过程如题 44 图所示。

根据题 44 图回答下列问题。

(1) 主存物理地址占多少位？

(2) TLB 采用什么映射方式？TLB 用 SRAM 还是 DRAM 实现？

(3) Cache 采用什么映射方式？若 Cache 采用 LRU 替换算法和回写（Write Back）策略，则 Cache 每行中除数据（Data）、Tag 和有效位外，还应有哪些附加位？Cache 总容量是多少？Cache 中有效位的作用是什么？

(4) 若 CPU 给出的虚拟地址为 0008C040H，则对应的物理地址是多少？是否在 Cache 中命中？说明理由。若 CPU 给出的虚拟地址为 0007C260H，则该地址所在主存块映射到的 Cache 组号是多少？

虚拟页式管理 TLB cache映射方式

[tag_link]

1）物理地址 由实页号和页内地址拼接，因此其位数为 16+12=28 或直接可得 20+3+5=28。

2）TLB 采用全相联映射，可以把页表内容调入任一块空 TLB 项中，TLB 中每项都有一个比较器，没有映射规则，只要空闲就行。TLB 采用静态存储器 SRAM，读写速度快，但成本高，多用于容量较小的高速缓冲存储器。

3）从图中可以看到，Cache 中每组有两行，故采用 2 路组相联映射。因为是 2 路组相联并采用 LRU 替换算法，所以每行（或每组）需要 1 位 LRU 位；因为采用回写策略，所以每行有 1 位修改位（脏位），根据脏位判断数据是否被更新，若脏位为 1 则需要写回内存。28 位物理地址中 Tag 字段占 20 位，组索引字段占 3 位，块内偏移地址占 5 位，故 Cache共有23=8组，每组 2 行，每行有25=32 B，故 Cache 总容量为8×2×(20+1+1+1+32×8)=4464位= 558 字节。Cache 中有效位用来指出所在 Cache 行中的信息是否有效。

4）虚拟地址分为两部分：虚页号、页内地址；物理地址分为两部分：实页号、页内地址。利用虚拟地址的虚页号部分去查找 TLB 表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。虚页号 008CH 恰好在 TLB 表中对应实页号 0040H（有效位为 1，说明存在），虚拟地址的后 3 位为页内地址 040H，则对应的物理地址是 0040040H。物理地址为 0040040H，其中高 20 位 00400H 为标志字段，低 5 位 00000B 为块内偏移量，中间 3 位 010B 为组号 2，因此将 00400H 与 Cache 中的第 2 组两行中的标志字段同时比较，可以看出，虽然有一个 Cache 行中的标志字段与 00400H 相等，但对应的有效位为 0，而另一 Cache 行的标志字段与 00400H 不相等，故访问 Cache 不命中。因为物理地址的低 12 位与虚拟地址低 12 位相同，即为 001001100000B。根据物理地址的结构，物理地址的后八位 01100000B 的前三位 011B 是组号，因此该地址所在的主存映射到 Cache 的组号为 3。

对于上题，若计算机 M 的主存地址为 32 位，釆用分页存储管理方式，页大小为 4KB，则第 1 行的 push 指令和第 30 行的 ret 指令是否在同一页中（说明理由）？若指令 Cache 有 64 行，采用 4 路组相联映射方式，主存块大小为 64B，则 32 位主存地址中，哪几位表示块内地址？哪几位表示 Cache 组号？哪几位表示标记（tag）信息？读取第 16 行的 call 指令时，只可能在指令 Cache 的哪一组中命中（说明理由）？

虚拟页式存储 cache映射方式 地址翻译

[tag_link]

因为页大小为 4KB，所以虚拟地址的高 20 位为虚拟页号。第 1 行的 push 指令和第 30 行的 ret 指令的虚拟地址的高 20 位都是 00401H，因此两条指令在同一页中。指令 Cache 有 64 块，采用 4 路组相联映射方式，故指令 Cache 共有 64/4 = 16 组，Cache 组号共 4 位。主存块大小为 64B，故块内地址为低 6 位。综上所述，在 32 位主存地址中，低 6 位为块内地址，中间 4 位为组号，高 22 位为标记。因为页大小为 4KB，所以虚拟地址和物理地址的最低 12 位完全相同，因而 call 指令虚拟地址 0040 1025H 中的 025H = 0000 0010 0101B 为物理地址的低 12 位，对应的 7～10 位为组号，故对应的 Cache 组号为 0。