2、直接映象及其变换
( 映象规则：主存中一块只能映象到Cache的一个特定的块中。
计算公式：b＝B mod Cb
其中：b为Cache的块号，B是主存的块号，Cb是Cache的块数。
整个Cache地址与主存地址的低位部分完全相同。
块0
(
块1
(
( 区0
(
块Cb-1
(
块0
块Cb
(
块1
块Cb+1
(
( 区1
(
块Cb-1
块2Cb-1
(
Cache
块Mb-Cb
(
块Mb-Cb+1
(
( 区Me-1
(
块Mb-1
(
主存储器
直接相联映象方式
( 地址变换过程：
用主存地址中的块号B去访问区号存储器把读出来的区号与主存地址中的区号E进行比较
比较结果相等，且有效位为1，则Cache命中。
比较结果相等，有效位为0，表示Cache中的这一块已经作废。
比较结果不相等，有效位为0，表示Cache中的这一块是空的。
比较结果不相等，有效位为1，表示Cache中的这一块是有用的。
( 提高Cache速度的一种方法：
把区号存储器与Cache合并成一个存储器
( 直接映象方法的主要优点：
硬件实现很简单，不需要相联访问存储器访问速度也比较快，实际上不进行地址变换
( 直接映象方式的主要缺点：块的冲突率比较高。
主存地址
区号E
块号B
块内地址W
Cache地址
块号b
块内地址w
块失效
相等比较
相等
比较相等且有效为1
E
1
访问Cache
区号E（按地址访问）
有效位
区表存储器
直接相联地址变换
区号E
块号B
块内地址W
Cache地址
块号b
块内地址w
送CPU
访问主存
相等比较
相等
1/w
选择
…
…
…
1
E
D0
D1
…
Dw-1
…
有效位
区号E
数据D0
数据D1
数据Dw-1
按地址访问的Cache
图3.43 快速度的直接相联地址变换
3、组相联映象及其变换
( 映象规则：
主存和Cache按同样大小划分成块，还按同样大小划分成组。
从主存的组到Cache的组之间采用直接映象方式。
在两个对应的组内部采用全相联映象方式。
(
块0
(
(
……
(组0
(
Gb-1
(
(
Gb
(
(
……
(组1
(
2Gb-1
( 区0
……
(
块0
( (
GbCg-Gb
(
组0 (
……
( (
……
(组Cg-1
(
Gb-1
( (
Cb-1=GbCg-1
(
(
Gb
(
……
1 (
……
(
(
2Gb-1
( (
GbCg(Me-1)
(
……
(
……
(Cg(Me-1)
(
GbCg(Me-1)+Gb-1
(
(
Cb-Gb=CgGb-Gb
( (
GbCg(Me-1)+Gb
(
Cg-1(
……
( (
……
(CgMe-Cg+1
(
Cb-1=CgGb-1
( (
GbCg(Me-1)+2Gb-1块2（Cb-1）
( Me-1
Cache
……
(
Me-Gb=GbCgMe-Gb
(
(
……
(CgMe-1
(
Mb-1=GbCgMe-1
(
主存储器
组相联映象方式
( 地址变换过程：
用主存地址中的组号G按地址访问块表存储器。
把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较。
如果有相等的，表示Cache命中。
如果没有相等的，表示Cache没有命中。
( 提高Cache的访问速度的一种方法：
把Cache的地址变换与访问Cache并行进行，并采用流水线方式工作。
把块表存储器中一个相联比较的组按块方向展开存放。
用多个相等比较器来代替相联访问，加块查表的速度。
( 组相联映象方式的优点：
块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。
( 组相联映象方式的缺点：
实现难度和造价要比直接映象方式高。
区号E
组号G
组内块号B
块内地址W
主存地址
组号g
组内块号b
块内地址w
Cache地址
不等
相联比较
相等
相联比较(Gb个块)
E区号,组内块号B
组内块号b
块 表
组相联映象方式的地址变换
区号E
区内组号G
组内块号B
块内地址W
主存地址
块失效
组号g
组内块号b
块内地址w
与
Cache地址
或
≠
相等比较
＝
≠
相等比较
＝
≠
相等比较
＝
……
……
E,B
b
e
E,B
b
……
E,B
b
e
……
块表(按地址访问,读出的多个字段进行相联比较,e为有效位)
组相联地址变换的一种实现方法
采用组相联映象方式的典型机器的Cache分组情况机器型号
Cache的块数Cb
每组的块数Gb
Cache组数Cg
DEC VAX-11/780
1024
2
512
Amdahl 470/V6
512
2
256
Intel i860 D-Cache
256
2
128
Honeywell 66/60
512
4
128
Amdahl 470/V7
2048
4
512
IBM 370/168
1024
8
128
IBM3033
1024
16
64
Motolola 88110 I-Cache
256
2
128
4、位选择组相联映象及其变换
( 映象规则：
除了分块之外，Cache分组，主存按照Cache的组大小分区。
主存中的块与Cache中的组之间是直接映象关系，
主存中的块与Cache中组内部的各个块之间是全相联映象方式。
块0
(
1
(
……
( 区0
(
块0
(
(
组0 (
……
(
Cg-1
(
(
Gb-1
(
Cg
(
(
Gb
(
Cg+1
(
1 (
……
(
……
( 1
(
2Gb-1
(
(
……
2Cg-1
(
……
(
Cb-Gb=CgGb-Gb
(
Cg-1(
……
(
Cg(Mb-1)
(
(
Cb-1=CgGb-1
(
Cg(Mb-1)+1
(
Cache
……
( Me-1
(
Mb-1=CgMe-1
(
主存储器
图3.47 位选择组相联映象方式
( 与组相联映象方式比较：映象关系明显简单，实现起来容易。
在块表中存放和参与相联比较的只有区号E，不再有组内块号B。
区号E
区内块号B
块内地址W
主存地址
块失效
组号g
组内块号b
块内w
与
Cache地址
或
≠
相等比较
＝
≠
相等比较
＝
≠
相等比较
＝
……
……
E
b
E
b
……
E
b
……
区号E
块号b
e
区号E
块号b
e
区号E
块号b
e
块表(按地址访问,读出的多个区号进行相联比较,e是有效位)
位选择组相联地址变换的一种实现方式
(
块0
(
(
……
(段0
(
Sb-1
(
(
块0
( (
Sb
(
段0 (
……
( (
……
( 1
(
Sb-1
( (
2Sb-1
(
(
Sb
(
1 (
……
(
(
2Sb-1
(
……
……
(
Cb-Sb=Sb(Cs-1)
(
Cs-1(
……
(
(
Cb-1=SbCs-1
(
Cache
(
Mb-Sb=Sb(Ms-1)
(
(
……
( Ms-1
(
Mb-1=SbMs-1
(
主存储器
段相联映象方式
5、段相联映象及其变换
( 映象规则：
主存和Cache都按同样大小分块，并分段。
段之间采用全相联映象方式，段内部的块之间采用直接映象方式。
( 段相联方式的地址变换过程：
首先用主存地址中的段号S与段表中的主存段号字段进行相联比较。
如果有相等的，用主存地址中的段内块号B按地址访问Cache段号部分。
把读出的段号s与主存地址的段内块号及块内地址拼接得到Cache地址。
如果没有相等的，则发出Cache块失效请求。
主存地址
段号S
段内块号B
块内地址W
段号s
段内块号b
块内地址w
Cache地址
相联比较
(
(
(段0
……
(
(
S
(
(
按地址访问
……
(段1
s
1
(
(
……
………
……
主存段号S
Cache段号s
有效位
(
(
……
(Ms-1
(
(
段表（按地址和相联两种访问方式）
段相联地址变换方式
( 段相联方式的主要优点：
段表比较简单，实现的成本低。
例如：一个容量为256KB的Cache，分成8个段，每段2048块，每块16B。
在段表存储器中只需要存储8个主存地址的段号S。
而在块表中要存储8×2048＝16384个区号（相当于段号），
两者相差2000多倍。
( 段相联方式的主要缺点：
当发生段失效时，要把本段内已经建立起来的映象关系全部撤消。
3.3.3 Cache替换算法及其实现
( Cache替换算法使用时间：
发生段失效，且可以装入新调入块的几个Cache块都已经被装满时。
直接映象方式实际上不需要替换算法。
全相联映象方式的替换算法最复杂。
( Cache替换算法要解决的问题：
1、记录每次访问Cache的块号。
2、管理好所记录的Cache块号，为找出被替换的块号提供方便。
3、根据记录和管理的结果，找出被替换的块号。
( Cache替换算法的主要特点：全部用硬件实现
1、轮换法及其实现用于组相联映象方式中，有两种实现方法。
方法一：每块一个计数器
( 在块表内增加一个替换计数器字段，
计数器的长度与Cache地址中的组内块号字段的长度相同。
( 替换方法及计数器的管理规则：
新装入或替换的块，它的计数器清0；同组其它块的计数器都加“1”。
在同组中选择计数器的值最大的块作为被替换的块。
( 例子：Solar-16/65小型机的Cache采用位选择组相联映象方式。
Cache每组的块数为4，因此，每块用一个2位的计数器。
一种轮换法的装入及替换过程序列
初始值
装入块00
装入块01
装入块10
装入块11
替换块00
块00
00
00
01
10
11
00
块01
00
01
00
01
10
11
块10
00
01
10
00
01
10
块11
00
01
10
11
00
01
方法二：每组一个计数器
( 替换规则和计数器的管理：
本组有替换时，计数器加“1”，
计数器的值就是要被替换出去的块号。
( 例如：NOVA3机的Cache采用组相联映象方式。
Cache每组的块数为8，每组设置一个3位计数器。
在需要替换时，计数器的值加“1”，
用计数器的值直接作为被替换块的块号。
( 轮换法的优点：实现比较简单。
能够利用历史上的块地址流情况，
( 轮换法的缺点：没有利用程序的局部性特点。
2、LRU算法及其实现
( 在块表内为每一块设置一个计数器，
计数器的长度与Cache地址中的组内块号字段的长度相同。
( 计数器的使用及管理规则：
新装入或替换的块，其计数器清0，同组中其它块的计数器都加1。
命中的块，其计数器清0，同组的其它计数器中，凡是计数器的值小于命中块所属计数器原来值的，都加1，其余计数器不变。
需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块就是要被替换的块。
( 例子：IBM 370/165机的Cache采用组相联映象方式。每组有4块，为了实现LRU替换算法，在块表中为每一块设置一个2位的计数器。在访问Cache的过程中，块的装入、替换及命中时，计数器的工作情况如表
块地址流
主存块1
主存块2
主存块3
主存块4
主存块5
主存块4
块号
计数器
块号
计数器
块号
计数器
块号
计数器
块号
计数器
块号
计数器
Cache块0
1
00
1
01
1
10
1
11
5
00
5
01
Cache块1
01
2
00
2
01
2
10
2
11
2
11
Cache块2
01
10
3
00
3
01
3
10
3
10
Cache块3
01
10
11
4
00
4
01
4
00
装入
装入
装入
装入
替换
命中
( LRU算法的优点：命中率比较高能够比较正确地利用程序的局部性特点，
充分地利用历史上块地址流的分布情况。
是一种堆栈型算法，随着组内块数增加，命中率单调上升。
( LRU算法的缺点：
控制逻辑复杂，增加了判断和处理命中的情况。
3、比较对法以三个块为例，三个块分别称为块A、B、C
( 表示方法：
用表示B块比A块更久没有被访问过，
如果要表示块C最久没有被访问过：
从最近到最远分别是：A、B、C或B、A、C
即
( 每次访问之后要改变触发器的状态。
在访问块A之后：TAB＝1，TAC＝1
在访问块B之后：TAB＝0，TBC＝1
在访问块C之后：TAC＝0，TBC＝0
ALRU
BLRU
CLRU
与门
与门
与门
0 1
TAB
0 1
TAC
0 1
TBC
访问A
访问B
访问C
R
S
R
S
R
S
每组3个块的比较对法
( 硬件需求量计算：
需要的触发器个数为：
与门的个数为Gb个，每个与门的输入端个数为Gb-1个其中：Gb为每组的块数。
每组块数
3
4
6
8
16
64
256
触发器个数
3
6
15
28
120
2016
32640
与门个数
3
4
6
8
16
64
256
与门输入端个数
2
3
5
7
15
63
255
( 当每组的块数比较多时，采用分级的办法实现。
实质上是用降低速度来换取节省器件。
例如：IBM 3033机的Cache，每组的块数为16，分3级。
从第1级到第3级分别为4、2、2。
共需要触发器个数为：6＋4＋8＝18。
如果不分级则需要触发器120个。
例如：IBM 370/168机的Cache，每组的块数为8，分2级。
第1级为4，第2级为2。
总共需要触发器个数为：6＋1×4＝10个。
如果不分级，则需要28个触发器。
4、堆栈法
( 堆栈法的管理规则如下：
把本次访问的块号与堆栈中保存的所有块号进行相联比较。
如果有相等的，则Cache命中。把本次访问的块号从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。
如果没有相等的，则Cache块失效。本次访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底，栈底单元中的块号被移出堆栈，它就是要被替换的块号。
本次访问的块号
栈顶
最近访问过的块
……
压入过程到此为止
与本次访问的块号相等
……
栈底
最久没有被访问过的块
堆栈法的工作原理
例如：每组为4块，则堆栈有4个存储单元，每个单元2位。
I0
I1
CP
D C
A0
1
D C
A1
1
NA
与门
D C
B0
1
D C
B1
1
NB
与门
D C
C0
1
D C
C1
1
NC
与门
D C
D0
1
D C
D1
1
D0
D1
每组4块的堆栈法实现
( 堆栈法的主要优点：
块失效率比较低，因为它采用了LRU算法。
硬件实现相对比较简单。
( 堆栈法的主要缺点：
速度比较低，因为它需要进行相联比较。
堆栈法与比较对法所用触发器的比例是：
其中，Gb是Cache每一组的块数。
当Gb大于8时，堆栈法所用的器件明显少于比较对法。
