7.5.3 cache行和主存块之间的映射方式

第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

##### 7.5.3 cache行和主存块之间的映射方式
在将主存块复制到 cache行时，主存块和 cache行之间必须遵循一定的映射规则。这
样，CPU要访问某个主存单元时，可依据映射规则到 cache 对应的行中查找信息，而不用在
整个 cache 中查找。
根据不同的映射规则，主存块和 cache行之间有以下3种映射方式。
(1)直接(direct):每个主存块映射到cache的固定行中。
(2)全相联(full associate):每个主存块映射到 cache的任意行中。
(3)组相联(set associate):每个主存块映射到 cache 固定组的任意行中。
1.直接映射
直接映射的基本思想是把主存的每一块映射到固定的一个 cache行中，也称模映射，其
映射关系如下：
cache行号=主存块号 mod cache 行数
例如，假定cache共有16行，根据100 mod16=4可知，主存第100块应映射到 cache的第4
行中。
通常 cache的行数是2的n次幂，假定cache有2“行，主存有2”块，即以m位主存块
号中低c位作为对应的 cache行号来进行 cache映射，即主存块号的低c位正好是它要装入
① 注：国内教材对“不命中”的说法有多种，如“失效”“失靶”“缺失”等，其含义一样，本书使用“缺失”一词。
第7章
237


<!-- page: 255 -->

计算机组成与系统结构(第3版)
238
的 cache行号。在cache中，给每一个行设置一个t位长的标记(tag),此处t=m-c,主存
某块调入cache后，就将其块号的高t位设置在对应cache行的标记中。根据以上分析可
知，主存地址被分成以下3个字段：
标记
cache 行号
块内地址
其中，高t位为标记，中间c位为cache行号(也称行索引),剩下的低位地址为块内地址。
如图7.27(a)所示，直接映射方式下，每2个主存块一对一映射到 cache的2个行中，
CPU访存过程如图7.27(b)所示。
位
第0行[标记
第1行
数据
第25-1行[
:
cache
⋯
主存
(a) cache 和主存间的映射关系
第0块
第1块
第2°-1块
第 26块
第2+1块
第2*-1块
m位
1位
c位
b位
标记
行号
块内地址
相等，
不等
比较
缺失
标记
标记
:
标记
命中，
cache 读出
数据总线
主存
主存
读出
(b)CPU访存过程
图7.27 cache和主存之间的直接映射方式
访存过程如下：首先根据主存地址中间的c位，直接找到对应的 cache行，将对应 cache
行中的标记和主存地址的高t位标记进行比较，若相等并有效位为1,则访问cache命中，此
时，根据主存地址中低位的块内地址，在对应的cache行中存取信息；若不相等或有效位为
0,则不命中(缺失),此时，CPU从主存中读出该地址所在的一块信息送到对应的 cache行
中，将有效位置1,并将标记设置为地址中的高t位，同时将该地址中的内容送CPU。
例7.4 假定主存和 cache之间采用直接映射的方式，块大小为1B。cache数据区容量
为4B,主存地址为32位，按字节编址。问：主存地址如何划分?根据程序访问的局部性原
理说明块大小设置为1B时的缺陷。
解：块大小为1B,故块内无须寻址，即块内地址位数为0。cache的数据区容量为4B,
共4行。因此，32位主存地址被划分为两个字段：标记位数t=30,行号位数c=2。
块大小设置为1B会产生以下两方面的问题。
(1)邻近单元很可能被访问，但由于没有跟着该字节调入cache,因此邻近单元的访问
会发生缺失。也就是说，块大小为1B时，程序访问的空间局部性没有被利用。
(2)在 cache行数不变的情况下，块太小使得映射到同一个 cache行的主存块数增加，
发生冲突的概率增大，引起频繁信息交换。
例7.5 假定主存和 cache 之间采用直接映射方式，块大小为512B。cache 数据区容量
为8KB,主存空间大小为1MB。问：主存地址如何划分?要求用图表示主存块和 cache 行


<!-- page: 256 -->

存储器层次结构
之间的映射关系，假定 cache当前为空，说明CPU对主存单元0240CH的访问过程。
解：cache数据区容量为8KB=21B=16行×512B/行。因为主存的每16块和 cache
的16行一一对应，所以可将主存的每16块看成一个块群，因而，得到主存空间地址划分为
1MB=22°B=128块群×16块/块群×512B/块。因此，主存地址位数n=20,标记位数t=
7,行号位数c=4,块内地址位数为9。
主存地址划分以及主存块和 cache行的对应关系如图7.28 所示。
cache
第0行
标记
数据
第1行
第2行
第15行
:
7位
7位
4位
9位
主存地址
标记cache行号块内地址
主存块号
主存储器
第0块
第1块
第0块群
第15块
第16块
第17块
第1块群
第31块
第2032块
第2033块
第127 块群
第2047块
图7.28 直接映射方式下主存块和 cache 行对应关系
主存地址 0240CH 展开为二进制数为0000 0010 0100 0000 1100,划分为以下3部分：
0000001
0010
### 0 0000 1100
该地址所在块号是0000 001 0010(第18块),所属块群号为0000 001(第1块群),映射到的
cache行号为0010(第2行)。
访问0240CH单元的过程如下，首先根据地址中间4位0010,找到 cache第2行，因为
cache为空，所以每个 cache行的有效位都为0,因此，不管第2行的标志是否等于0000 001,
都不命中。此时，将0240CH单元所在的第18块复制到cache第2行，并置有效位为1,置
标记为0000 001(表示信息取自主存第1块群中对应的主存块)。
例7.6 假定主存和 cache之间采用直接映射方式，块大小为16B。cache的数据区容
量为64KB,主存地址为32位，按字节编址。问：主存地址如何划分?说明访存过程，并计
算 cache 总容量为多少。
解：cache 数据区容量为64KB=2'*B=212行×2'B/行。
因为主存的每2'“块和 cache的22行一一对应，所以可将主存的每个2“块看成一个块群。
主存地址位数n=32,主存地址空间划分为22B=2“块×2'B/块=21块群×2'2块/块群×
2'B/块。因此，标记位数t=16,行号位数c=12,块内地址位数为4。
第7章
239


<!-- page: 257 -->

计算机组成与系统结构(第3版)
240
主存地址的划分以及访存过程实现如图7.29 所示。图中 tag表示标记字段；index 表
示 cache行索引，即行号；块内地址分为两部分：高两位(word字段)为字偏移量、低两位
(byte字段)为字节偏移量。hit 表示命中。
整个访存过程由硬件实现，分为以下5个步骤：①根据12位cache行索引找到对应行；
②将16位标志与对应行中的标志进行比较；③比较相等并有效位为1时，输出hit为1;
④由两位字偏移量从4个32位字中选择一个字输出；⑤由两位字节偏移量从1个32 位字
中选择一字节输出。CPU 在hit为1的情况下，根据要访问的是字还是字节选择从第④步
还是第⑤步得到结果。若hit不为1,则CPU要启动一次“cache行读”总线事务操作，通过
总线到主存读一块连续的信息到 cache 行中。
31
主存地址
0
byte
hit
tag
16
②’
index
16
①
.12
128
⑤
byte
word
V
tag
data
MUX
word
>4K行
16
32
32
32
32
③
MUX
④
32
data
图 7.29 直接映射方式的实现
从图7.29中可看出，每个cache行由一位有效位V、16位标记(tag)和4个32 位的数据
(data)组成，共有2l2=4K行，因此，cache的总容量为212×(4×32+16+1)=4K×145=
580Kbits=72.5KB。其中，数据占总容量的64KB/72.5KB=88.3??
直接映射的优点是容易实现，命中时间短，但由于是多对一的映射，会引起频繁的调进
调出。例如，在例7.5中，若需将主存第0块与第16块同时调入cache,由于它们都只对应
cache 第0行，即使其他行空闲，也总有一个主存块不能调入cache。很显然，直接映射方式
不够灵活，使得cache 存储空间得不到充分利用，命中率较低。
2.全相联映射
全相联映射的基本思想是一个主存块可装入cache任意一行中。在全相联映射 cache
中，每行的标记用于指出该行取自主存的哪个块。因为一个主存块可能在任意一个 cache
行中，所以，需要比较所有cache行的标记，因此，主存地址中无须cache行索引，只有标记和
块内地址两个字段。全相联映射方式下，只要有空闲 cache行，就不会发生冲突，因而块冲
突概率低。
例7.7 假定主存和 cache之间采用全相联映射，块大小为512B,按字节编址。cache
数据区容量为8KB,主存地址空间为1MB。问：主存地址如何划分?要求用图表示主存块


<!-- page: 258 -->

存储器层次结构
和 cache 行之间的映射关系，并说明 CPU对主存单元0240CH 的访问过程。
解：cache数据区容量为8KB=21B=2*行×512B/行；主存地址空间为1MB=22°B=
21块×512B/块。
20位的主存地址划分为两个字段：标记字段，位数t=11;块内地址字段，位数为9。
主存地址划分以及主存块和 cache行之间的对应关系如图7.30 所示。
cache
第0行
标记
数据
第1行
第2行
:
第15行
11位
1位
9位
主存地址
标记
块内地址
主存储器
第0块
第1块
第15块
第2047块
主存块号
图7.30 全相联映射方式下主存块和 cache 行对应关系
主存地址 0240CH展开成二进制数为0000 0010 0100 0000 1100,所以主存地址划分为
### 0000 0010 010
### 0 0000 1100
访问0240CH单元的过程如下，首先将高11位标记00000010 010与 cache 中每个行的标记进
行比较，若有一个相等并且对应有效位为1,则命中，此时，CPU根据块内地址00000 1100
从该行中取出信息；若都不相等，则不命中，此时，需要将 0240CH单元所在的主存第
### 0000 0010 010块(即第18块)复制到 cache的任何一个空闲行中，并置有效位为1,置标记
为0000 0010 010(表示信息取自主存第18块)。
为了加快比较的速度，通常每个 cache行都设置一个比较器，比较器位数等于标记字段
的位数。全相联 cache访存时根据标记字段的内容来查找cache行中的主存块，因而它查找
主存块的过程是一种“按内容访问”的存取方式，因此，它是一种“相联存储器”。全相联映射
方式的时间开销和所用元件开销都较大，实现起来比较困难，不适合容量较大的 cache。
3.组相联映射
直接映射和全相联映射的优缺点正好相反，二者结合可以取长补短。因此将两种方式
结合起来产生了组相联映射方式。
组相联映射的主要思想是，将 cache所有行分成29个大小相等的组，每组有2°行。每
个主存块被映射到 cache 固定组中的任意一行，即采用组间模映射、组内全映射的方式，映
射关系如下：
cache组号=主存块号 mod cache 组数
例如，假定8KB的 cache划分为23组×21行/组×512B/行，则主存第100块应映射到
第7章
241


<!-- page: 259 -->

计算机组成与系统结构(第3版)
242
cache 第4组的任意一行中，因为100 mod 23=4。
如此设置的2°组×2'行/组的 cache映射方式称为2’路组相联映射，即s=1为2 路组
相联，s=2为4路组相联，以此类推。通过对主存块号取模，使得每2个主存块与24个
cache组一一对应，主存地址空间实际上被分成了若干组群，每个组群中有2°个主存块对应
于cache的2°个组。假设主存地址有n位，块内地址占k位，有2”个组群，则n=m+q+
k,主存地址被划分为以下3个字段：
标记
cache 组号
块内地址
其中，高m位为标记，中间q位为组号(也称组索引),剩下的k位低位地址部分为块内地
址。标记字段的含义表示当前地址所在的主存块位于主存中的哪个组群。
例如，假定cache 数据区容量为8KB,每个主存块大小为32B,按字节编址，则块内地址
的位数k=5;采用2路组相联，即每组有2行，则 cache有8KB/(32B×2)=128组，即q=
7,s=1。假定主存地址为32位，则m=32-7-5=20,即主存共有22°个组群，每个组群有
2?=128块，每块有2?=32字节，因而主存地址划分为标记20位、组号7位、块内地址5位。
s的选取决定了块冲突的概率和相联比较的复杂性。s越大，则 cache发生块冲突的概
率越低，相联比较电路越复杂。选取适当的s,可使组相联映射的成本比全相联的成本低得
多，而性能上仍可接近全相联方式。在较早的时候，由于 cache 容量不大，所以通常s=1或
2,即2路或4路组相联较常用，但随着技术的发展，cache 容量不断增加，s的值有增大的趋
势，目前有许多处理器的 cache采用8路或 16 路组相联方式。
对于组相联 cache,CPU访存过程如下：首先根据访存地址中间的q位cache组号，直
接找到对应的cache组，将对应cache组中每个行的标记与主存地址的高m 位标记进行比
较，若有一个相等并且有效位为1,则访问cache命中，此时，根据主存地址中的块内地址，在
对应 cache行中存取信息；若都不相等或虽相等但有效位为0,则不命中，此时，CPU从主存
中读出该地址所在的一块信息送到cache对应组的任意一个空闲行中，将有效位置1,并设
置标记，同时将该地址中的内容送CPU。
实现组相联映射的硬件线路如图7.31所示，图中采用的是2路组相联映射的 cache,整
个访存过程如下：①根据主存地址中的 cache组号找到对应组；②将地址中的标记与对应
组中每个行的标记 tag进行比较；③将比较结果和有效位V相“与”;④若有一路比较相等
并且有效位为1,则输出hit为1,并选中这一路 cache行中的主存块；⑤在 hit为1的情况
下，根据主存地址中的块内地址从选中的一块内取出对应单元的信息，若 hit 不为1,则
CPU要到主存中读一块信息到 cache行中。
例7.8 假定主存和cache之间采用2路组相联映射，块大小为512B,采用字节编址。
cache 数据区容量为8KB,主存地址空间为1MB。问：主存地址如何划分?要求用图表示
主存块和 cache行之间的映射关系，并说明CPU对主存单元0240CH的访问过程。
解：cache数据容量为8KB=21B=2°组×2'行/组×512B/行；主存地址空间为
1MB=22°B=2“块×512B/块=2°组群×2块/组群×2°B/块。因此，主存地址位数n=
20,标记位数m=8,组号位数q=3,块内地址位数k为9。
主存地址划分以及主存块和 cache行的对应关系如图7.32所示。


<!-- page: 260 -->

存储器层次结构
主存地址
标记
组号
块内地址
V
tag
②
比较
data
block x
:
④
①
data
block y
④
tag
②
比较
V
主存数据-
⑤
hit
③
③
图7.31 组相联映射方式的硬件实现
cache
标记
数据
第0组
第1组<
第7组
8位
8位
3位
9位
主存地址
标记
cache组号块内地址
主存块号
主存储器
第0块
第1块
第0组群
第7块
第8块
第9块
第1组群
第15块
第2040块
第2041块第 255组群
第2047块
图7.32 组相联映射方式下主存块和 cache行对应关系
主存地址 0240CH展开为二进制数为0000 0010 0100 0000 1100,所以主存地址划分为
### 0000 0010
010
### 0 0000 1100
访问0240CH单元的过程如下，首先根据地址中间3位010,找到 cache 第2组，将标记0000 0010
与第2组中两个 cache行的标记同时进行比较，若有一个相等且有效位为1,则命中。此时，
根据低9位块内地址从对应行中取出单元内容送CPU;若都不相等或有一个相等但有效位
为0,则不命中。此时，将0240CH单元所在的主存第00000010 010 块(即第18块)复制到
cache第010组(即第2组)的任意一个空行中，并置有效位为1,置标记为0000 0010(表示
第7章
243
信息取自主存第2组群)。


<!-- page: 261 -->

计算机组成与系统结构(第3版)
244
组相联映射方式结合了直接映射和全相联映射的优点。当cache的组数为1时，变为
全相联映射；当每组只有一个 cache行时，则变为直接映射。组相联映射的冲突概率比直接
映射低，由于只有组内各行采用全相联映射，所以比较器的位数和个数都比全相联映射少，
易于实现，查找速度也快得多。
4.3种映射方式比较
对于一个主存块来说，3种映射方式下对应 cache 行的个数不同。直接映射是唯一映
射，每个主存块只有一个固定行与之对应；全相联映射是任意映射，每个行都可对应；N路
组相联映射有N行对应。这种特性可用“关联度”来度量，即关联度指一个主存块映射到
cache中时可能存放的位置个数。因此，直接映射的关联度最低，为1;全相联映射的关联度
最高，为 cache的总行数；N 路组相联映射的关联度居中，为N。
当 cache大小、主存块大小一定时，关联度和命中率、命中时间、标记所占额外开销等有
如下关系。
(1)关联度越低，命中率越低。因此直接映射命中率最低，全相联映射命中率最高。
(2)关联度越低，判断是否命中的开销越小，命中时间越短。因此，直接映射的命中时
间最短，全相联映射的命中时间最长。
(3)关联度越低，标记所占额外空间开销越少。因此.直接映射额外空间开销最少，全
相联映射额外空间开销最大。
例7.9 假定主存地址为32位，按字节编址，主存块大小为16B,cache共有4K行，则
在关联度分别为1、2、4和全相联方式下标记所占总位数是多少?
解：关联度为1(即直接映射)时，每组1行，共4K组，标记占32-4-12=16位，总位
数占4K×16=64K位；关联度为2(即2路组相联)时，每组2行，共2K组，标记占32-4-
11=17位，总位数占4K×17=68K位；关联度为4(即4路组相联)时，每组4行，共1K组，
标记占32-4-10=18位，总位数占4K×18=72K位；全相联时，整个为1组，每组4K行，
标记占32—4=28位，总位数占4K×28=112K位。
7.5.4cache中主存块的替换算法
cache 行数比主存块数少得多，因此，往往多个主存块会映射到同一个 cache行中。当
新的一个主存块复制到 cache时，cache中的对应行可能已经全部被占满，此时，必须选择淘
汰掉一个 cache行中的主存块。例如，对于例7.8中的2路组相联映射cache,假定第0组的
两个行分别被主存第0块和第8块占满，此时若需调人主存第16块，根据映射关系，它只能
存放到 cache第0组，因此，已经在第0组的主存第0块和第8块这两块中，必须选择调出
其中一块，到底调出哪一块呢?这就是淘汰策略问题，也称为替换算法或替换策略。
常用的替换算法有先进先出(first in first out,FIFO)、最近最少用(least recently used,
LRU)、最不经常用(least frequently used,LFU)和随机替换算法(random)等。可以根据实
现的难易程度以及是否能获得较高的命中率两方面来决定采用哪种算法。
1.先进先出算法
FIFO算法的基本思想是：总是选择淘汰最早装入 cache 的主存块。这种算法实现起
来较方便，但不能正确反映程序的访问局部性，因为最先进入cache的主存块也可能是目前
经常要用的，因此，这种算法有可能产生较大的缺失率。


<!-- page: 262 -->

存储器层次结构
2.最近最少用算法
LRU算法的基本思想是：总是选择淘汰近期最少使用的主存块。这种算法能比较正
确地反映程序的访问局部性，因为当前最少使用的块一般来说也是将来最少被访问的。但
它的实现比 FIFO算法要复杂一些。
下面用一个例子来说明LRU算法的具体实现。为简化说明，以下假设组相联方式下
不一定满足组大小是2的n次幂，虽然这样假设与实际不符，但并不影响对实现原理的解释
说明。
假定主存中的5块{1,2,3,4,5}映射到 cache的同一组，对于主存块访问地址流《1,2,
3,4,1,2,5,1,2,3,4,5},在3路、4路和5路组相联的情况下，采用LRU算法的替换过程如
图7.33 所示。
1
1
2
2
3
3
2
4
4
3
2
1
1
4
3
2
2
2
1
4
3
5
5
4
3
1
5
2
4
3
2
2
5
4
3
3
3
2
5
4
4
4
3
2
5
5
5
4
3
2
3行/组
4行/组
5行/组
√√
√√
√
√
√
√
√
√
√
√ √
图7.33 LRU替换算法示例
从图7.33可以看出，在LRU算法中，同一时刻小组中的块集合必然是大组中块集合的
子集。因此，在小组中命中时在大组中肯定命中，通常把满足这种特性的算法称为栈算法。
因此，LRU算法是栈算法。
当程序中的局部化范围(即某段时间集中访问的存储区)超过 cache组大小时，命中率
可能变得很低。例如，假设上述例子中的访存地址流是1,2,3,4,1,2,3,4,1,2,3,4,⋯,而
cache每组只有3行，那么命中率为0。这种现象称为颠簸(pingpong)或抖动(thrashing)。
LRU算法并不是像图7.33所示通过移动块来实现的。实际上，每个 cache 行有一个计
数器，用计数值来记录主存块的使用情况，通过硬件修改计数值，并根据计数值选择淘汰某
个 cache行中的主存块。淘汰时，只要将被淘汰行的有效位清零即可。这个计数值称为
LRU位，其位数与 cache组大小有关。理论上，n路时 LRU位为log?n,例如，2 路时 LRU
位为1,4路时LRU位为2。
为简化上述 LRU 位计数的硬件实现，通常采用一种近似的LRU 位计数方式来实现
LRU算法。近似LRU计数方法仅区分哪些是新调入的主存块，哪些是较长时间未用的主
存块，然后，在较长时间未用的块中选择一个被替换出去。
3.最不经常用算法
LFU算法的基本思想是：替换掉 cache中引用次数最少的块。LFU也用与每个行相
关的计数器来实现。这种算法与LRU 有点类似，但不完全相同。
4. 随机替换算法
从候选行的主存块中随机选取一个淘汰掉，与使用情况无关。模拟试验表明，随机替换
第7章
245


<!-- page: 263 -->

计算机组成与系统结构(第3版)
246
算法在性能上只稍逊于基于使用情况的算法，而且代价低。
例7.10 假定主存空间大小为32K×16位，按字编址，每字16位。cache采用4路组
相联映射方式，数据区大小为4K字，主存块大小为64字。假定 cache 开始为空，处理器按
顺序访问主存单元0,1,⋯,4351,一共重复访问10次。假设 cache 比主存快10 倍，采用
LRU 替换算法。试分析采用 cache 后速度提高了多少?
解：主存空间大小为32K字=512块×64字/块，cache数据区容量为4K字=16组×4
行/组×64字/行，所以，cache共有64行，分成16组，每组4行。
因为每块为64字，4352/64=68,所以主存单元0～4351对应前68块(第0～67块),即
处理器的访问过程是对主存前68块连续访问10次。
图7.34给出了前两次循环的主存块替换情况，图中列方向是 cache的16个组，行方向
是每组的4个 cache行。根据组相联映射的特点，cache行和主存块之间的映射关系如下：
主存第0～15块分别对应 cache 第0～15组，可以放在对应组的任一行中，在此，假定按顺
序存放在第0行；主存第16～31块也分别对应 cache的第0～15组，假定放到第1行；同
理，主存第32～47块分别放到 cache第0～15组的第2行；第48～63块分别放到 cache 第
0～15组的第3行。这样，第0～63块都没有冲突，每块都是第一个字在cache中没有找到，
调到 cache对应组的某一行后，其余每个字都能在cache中找到。因此每一块只有第一字未
命中，其余的63个字都命中。
第0组
第1组
第2组
第3组
第4组
第15组
第0行
0/64/48
1/65/49
2/66/50
3/67151
4
:
15
第1行
16/0/64
17/1/65
18/2/66
19/3/97
20
31
第2行
32/16
33/17
34/18
35/19
36
:
47
第3行
48/32
49(33
50/34
51/35
52
63
图7.34 例7.10中主存块的替换情况
主存的第64～67块分别对应 cache的第0～3组，此时，这4组的4行都不空闲，所以
要选择一个块被淘汰。因为采用LRU算法，所以，分别将最近最少用的第0～3块从第0～
3组的第0行中替换出来。再把第64～67块分别放到对应 cache 行中，每块也都是第一个
字在 cache中没有找到，调入后其余63个字都能在 cache 中找到。
综上所述，第一次循环时，对于所有68块都只有第一字未命中，其余63个字都命中。
以后9次循环中，因为cache第4～15组中的4×12=48个 cache行内的主存块一直没
有被替换，所以只有68-48=20 个主存块的第一字未命中，其余都命中。
访问总次数为4352×10=43520,未命中次数为68+9×20=248,命中率p=(43520-
248)/43520=99.43??
假定 cache和主存的访问时间分别为T。和T.,根据题意可知T。=10T。采用 cache
后，cache-主存层次的平均访问时间为
T.=T.+(1-p)Tm=T.+(1-p)×10T。


<!-- page: 264 -->

存储器层次结构
因此，采用 cache后速度提高的倍数为
Tm/T?=10T./(T.+(1-p)×10T.)=10/(1+(1-p)×10)≈9.5