前言：之前的计算机组成原理总结，总是把题目放在前面，但是很明显这样后面的知识点总结很难看到，所以这一篇做一个修改，把知识点总结先放前面消化理解，再欣赏后面的经典例题。

一.高速缓冲存储器

1.1 出现原因

• 避免CPU的“空等”现象
• 解决CPU与主存之间的速度差异

1.2 构成

   - 由SRAM组成

1.3 程序的局部性原理

• 空间局部性：现在使用的信息在最近的未来还会用到(循环)。
• 时间局部性：最近的未来要使用的信息和现在使用的信息在空间上是临近的（顺序存放、顺序执行）。

1.4 基本工作原理

• 主存和缓存按块存储，块的大小相同
• 每块有若干字节组成，大小为块长
• Cache中块数远少于主存块数
• 按某种策略预测未来访存的数据，将其装入cache

1.5 工作过程

例如：CPU发起读请求，进行以下步骤：

• 访存地址在Cache中命中，读Cache
• 访存地址在Cache中未命中
  • ①读主存，并把此字所在的块调入Cache
  • ②若Cache已满， 则替换Cache某块信息

注意:某些计算机同时访问主存和Cache。

1.6 补充

CPU与Cache之间的数据交换以字为单位，而Cache与主存之间的数据交换以Cache块为单位。

1.7 计算

1.8 解决问题

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

1. 数据查找。如何快速判断数据是否在Cache中。
2. 地址映射。主存块如何存放在Cache中，如何将主存地址转换为Cache地址。
3. 替换策略。Cache满后，使用何种策略对Cache块进行替换或淘汰。
4. 写入策略。如何既保证主存块和Cache块的数据一 致性，又尽量提升效率。

二.Cache与主存的映射方式

2.1 直接映射

2.1.1地址结构

标记	Cache行号	块内地址

2.1.2 优点

• 实现简单

2.1.3 缺点

• 不够灵活
• 空间利用率低

2.1.4映射方式

每个缓存块i可以和若干个主存块对应，每个主存块j只能和一个缓存块对应。

2.2 全相联映射

2.2.1 地址结构

标记	块内地址

2.2.2 优点

• 比较灵活
• 冲突概率低
• 空间利用率高，命中率高

2.2.3 缺点

• 标记比较速度慢
• 实现成本高
• 电路复杂

2.2.4 映射方式

          主存中的任一块可以映射到缓存的任一块。

2.3组相联映射

2.3.1 地址结构

标记	组号	块内地址

2.3.2 映射方式

• 组间采用直接映射
• 组内采用全相联映射

2.4三种映射方式比较

三种映射方式中，直接映射的每个主存块只能映射到Cache中的某固定行; 全相联映射可以映射到所有Cache行: N路组相联映射可以映射到N行。当Cache大小、主存块大小定时，

• 直接映射的命中率最低，全相联映射的命中率最高。
• 直接映射的判断开销最小所需时间最短， 全相联映射的判断开销最大、所需时间最长。
• 直接映射标记所占的额外空间开销最少，全相联映射标记所占的额外空间开销最大。

三. Cache中主存块的替换算法

• 随机算法（RAND)
• 先进先出算法（FIFO）
• 近期最少使用算法（LRU）
• 最不经常使用算法（LFU）
  这里的算法比较复杂，我单独写了一篇博客，有助于大家理解:替换算法（详解）

四. Cache写策略

原因：Cache块是主存块副本，对Cache进行更新需保证Cache与主存数据一致。

4.1 Cache写命中时的写策略

①全写法(写直通法、write-through): 同时写Cache和主存，实现简单，访存次数增加效率低;写缓冲(write- buffer)解决速度不匹配问题
②写回法(write- back) :只写Cache块，当块失效时写主存，需标志脏位，可能不一致

4.2 Cache写不命中的写策略

①写分配法(write- allocate):加载主存块到Cache,更新Cache块; 与写回法合用;
②非写分配法(non-write- allocate):只写入主存，不进行调块;与全写法合用;

4.3 分离的Cache结构

随着新技术的发展，需要将指令Cache与数据Cache分开设计。统一的cache的优点是设计和实现相对简单，但由于执行部件存取数据时，指令预取部件要从同一cache读指令，会引发冲突。采用分离的cache结构可以解决这个问题。

五.经典题目

1. 在高速缓存系统中，主存容量为12MB，Cache 容量为400KB，则该存储系统的容量为（ ）
   A.12MB + 400KB
   B.12MB
   C.12MB - 12MB + 400KB
   D.12MB - 400KR
   解析：B。由于Cache中存放的是主存中某一部分信息的副本，所以不能认为总容量为两个层次容量的简单相加。

2. 某32位计算机的Cache容量为16KB, Cache 行的大小为 16B，若主存与Cache地址映像采用直接映像方式，则主存地址为0x1234E8F8的单元装入Cache的地址是( )。
   A.00010001001101
   B.01000100011010
   C.10100011111000
   D.11010011101000
   理解：分析直接映射地址结构。主存地址=Cache地址 + 主存标记项。
   解析：C。因为Cache容量为16KB = 2¹⁴B，所以Cache地址长14位(选项都为14位，即隐含了按字节编址)。主存与Cache地址映像采用直接映像方式，将32位的主存地址0x1234E8F8写成二进制，根据直接映射的地址结构可知，取低14位就是Cache地址。

3. 某存储系统中，主存容量是Cache容量的4096倍，Cache被分为64个块， 当主存地址和Cache地址采用直接映像方式时，地址映射表的大小应为( )。（假设不考虑一致维护和替换算法位。)
   A.64097bit
   B.6412bit
   C.64096bit
   D.6413bit
   解释：地址映射表：主存标记阵列。
   解析：D。由于Cache被分为64个块，则Cache有64行，采用直接映射，一行相当于一组。因此标记阵列每行存储1个标记项，其中主存标记项为12位(2¹²= 4096，是Cache容量的4096倍，即地址长度比Cache长12位)，加上1位有效位，因此每行标记项为13位。该标记阵列有64行，所以总的大小有 64*13 位。

4. 有效容量为128KB的Cache,每块16B，采用8路组相联。字节地址为1234567H的单元调入该Cache,则其Tag应为( )。
   A.1234H
   B.2468H
   C.048DH
   D.12345H

• 有效容量=存储容量。
• 8路组相联：每一组有8个块。
• Tag===主存标记。
• 字节地址=主存地址。
  解析：C。块大小为16B，所以块内地址字段为4位; Cache 容量为128KB，采用8路组相联，共有128KB/(16B*8)= 1024组，组号字段为10位;剩下的为标记字段1234567H转换为二进制数0001 0010 0011 0100 0101 0110 0111，标记字段对应高14位即048DH。

5. 有一主存-Cache层次的存储器，其主存容量为1MB, Cache 容量为16KB，每块有8个字(每字32位)，采用直接地址映像方式，Cache起始字块为第0块，若主存地址为35301H且CPU访问Cache命中，则在Cache的第( )( 十进制表示)字块中。
   A.152
   B.153
   C.154
   D.151
   解析：A。先写出主存地址的二进制形式，然后分析Cache块内地址、Cache字块地址和主存字块标记主存地址的二进制数0011 0101 0011 0000 0001，根据直接映射的地址结构，字块内地址为低5位(每字块含32B，2⁵=32， 因此为5位)，主存字块标记为高6位(IMB/16KB=64，2⁶=64， 因此为6位)，其余01 0011 00即为Cache字块地址，转换为十进制数152。

6. 假设主存地址位数为32位，按字节编址，主存和Cache之间采用全相联映射方式，主存块大小为1个字，每字32位，采用回写(write back)方式和随机替换策略，则能存放32K字数据的Cache的总容量至少应有( ) 位。
   A. 1536K
   B. 1568K
   C. 2016K
   D. 2048K
   理解：Cache行的总位数=数据位+标记位+修改位+有效位+替换控制位。 这里的位是空间大小的位，不是位数的位。
   解析：D。主存块大小为1个字，即32位，按字节编址，故块内地址52位在全相联映射方式下，主存地址只有两个字段，故标志占32-2= 30位。因采用回写法，故需1位修改位:因为采用随机替换策略，故无须替换控制位。每个Cache行的总位数为32bit (数据位)+ 30bit (tag位)+ 1bit(修改位) + 1bit (有效位) = 64bit。综上，Cache总容量至少应有32Kx64bit 2048K bit。

7. 假定采用多模块交叉存储器组织方式，存储器芯片和总线支持突发传送，CPU通过存储器总线读取数据的过程为：发送首地址和读命令需1个时钟周期，存储器准备第一个数据需8个时钟周期，随后每个时钟周期总线上传送1个数据，可连续传送8个数据(即突发长度为8)。若主存和Cache之间交换的主存块大小为64B，存取宽度和总线宽度都为8B，则Cache的一次缺失损失至少为( )个时钟周期。
   A.17
   B.20
   C.33
   D.80
   突发传送：同一行相邻的存储单元连续进行数据传输。
   总线宽度：总线在单位时间内可以传输的数据总数（平时常说的32位、64位）。
   存取宽度：一次访存操作可存取的数据位数。
   突发长度：在一次突发传输中进行的数据传输次数。
   解析：A。一次缺失损失就需要从主存读出一个主存块(64B)，每个突发传送总线事务可读取8B*8 = 64B，因此，只需要一个突发传送总线事务。每个突发传送总线事务所用的时间为1+8+8=17个时钟周期，因此共需要17个时钟周期。

8. 某计算机的Cache共有16 块，采用二路组相联映射方式(即每组2块)。每个主存块大小为32B，按字节编址主存129号单元所在主存块应装入的Cache组号是（ ）
   A.0
   B.2
   C.4
   D.6
   理解：主存块大小=Cache块大小
   解析：C。由于Cache共有16块，采用二路组相联，共分为8组，组号为0，1，2……7组号占3位。主存块大小为32B，按字节编址，块内地址占5位。主存单元地址129 = 0……100 00001（十进制转二进制），后5位是块内地址，块内地址的前3位是组号，因此将映射到组号4的任意个 Cache 块中。

9. 有如下C语言程序段:

for(k=0;k<1000;k++)
	a[k]=a[k]+32;

若数组a和变量k均为int型，int型数据占4B，数据Cache采用直接映射方式，数据区大小为1KB，块大小为16B，该程序段执行前Cache为空，则该程序段执行过程平访问数组a的Cache缺失率约为( )。
A.1.25%
B.2.5%
C.12.5%
D.25%
理解：一次访存读取一行，一行有4个int整型数据，每访问一个int型数据执行一次循环即两次访问。
解析：C。分析语句a[k)=a[k]+3：首先读取a[k]需要访问一次a[k]，之后将结果赋值给a[k]需要访问一次，共访问两次。第一次访问a未命中，并将该字所在的主存块调入Cache对应的块中，对该主存块中的4个整数的两次访问中，只在访问第一次的第一个元素时发生缺失，其他的7次访间中全部会中，因此该程序段执行过程中访问数组a的Cache缺失率的为1/8。

10. 若计算机主存地址为32位关子节锅址，莱Cache的数据区容量为32KB，主存块大小为64B，采用8路组相联映射方式，该Cache中比较器的个数和位数分别为( ).
    A.8.20
    B.8,23
    C.64,20
    D.64,23
    解释：比较器用于并行地比较分组中所有cache行的Tag标记位与欲访问物理地址的Tag标记位，因此比较器的个数就是分组中的cache的行数，比较器的位数就是Tag标记位数。
    解析：A。

六.常见问题与易混淆知识点

1. Cache行的大小和命中率之间有什么关系?
   行的长度较大，可以充分利用程序访问的空间局部性，使一个较大的局部空间被起调到Cache中，因而可以增加命中机会。但是，行长也不能太大，主要原因有两个:

• 1)行长大使失效损失变大。也就是说，若未命中，则需花更多时间从主存读块。
• 2)行长太大，Cache项数变少，因而命中的可能性变小。

2. 发生取指令Cache缺失的处理过程是什么?

• 1)程序计数器恢复当前指令的值。
• 2)对主存进行读的操作。
• 3)将读入的指令写入Cache中，更改有效位和标记位。
• 4)重新执行当前指令。