5.1.1 从单级存储器到多级存储器
1,从用户的角度来看，存储器的三个主要指标是：
容量，速度，价格 (每位价格 )
5.1 存储器的层次结构第五章 存储层次
2,人们对这三个指标的期望,
3,这三个指标相互矛盾,
4,解决方法采用多种存储器技术，构成存储层次,
5.1.2 存储层次的性能参数
C,S,TA
设,S ── 容量
TA ── 访问时间
C ── 每位价格下面仅考虑由 M1和 M2构成的两级存储层次：
M1的参数,S1,TA1,C1
M2的参数,S2,TA2,C2
1,每位价格 C C＝ ─────
如果 S1<< S2,C? C2
C1S1＋ C2S2
S1＋ S2
2,命中率 H 和失效率 F
命中率 H,CPU访问存储系统时，在 M1中找到所需信息的概率。
H＝ N1/(N1＋ N2)
N1 ── 访问 M1的次数
N2 ── 访问 M2的次数失效率 F,CPU访问存储系统时，在 M1中找不到所需信息的概率。
F＝ 1－ H
3,平均访问时间 TA
对大部分系统,TM＝ TA2＋ TB
由于
TA＝ H?TA1＋ (1－ H )(TA1+TM )
于是
TA＝ TA1＋ (1－ H )TM
或
TA＝ TA1＋ FTM
TA1 ── 命中时间
TM ── 失效开销
5.1.3,Cache－主存,和,主存－辅存,层次一般来说：
,Cache－主存,层次：弥补主存速度的不足
,主存－辅存,层次：弥补主存容量的不足
1.,Cache－主存,层次主存与 CPU的速度差距
“Cache - 主存,层次的实现：主要借助于辅助硬件。
2.,主存－辅存,层次
,主存－辅存,层次的实现：主要借助于辅助软硬件。
存储层次
CPU对第二级的访问方式比较项目目 的存储管理实现访问速度的比值
(第一级和第二级 )
典型的块 (页 )大小失效时 CPU是否切换
“Cache －主存”层次,主存－辅存”层次为了弥补主存速度的不足 为了弥补主存容量的不足主要由专用硬件实现 主要由软件实现几比一 几百比一几十个字节 几百到几千个字节可直接访问 均通过第一级不切换 切换到其他进程两者的比较 -----“Cache －主存”与“主存－辅存”
层次的区别
5.1.4 存储层次的四个问题当把一个块调入高一层 (靠近 CPU)存储器时，
可以放在哪些位臵上?
(映象规则 )
当所要访问的块在高一层存储器中时，如何找到该块?
(查找算法 )
3,当发生失效时，应替换哪一块？
(替换算法 )
4,当进行写访问时，应进行哪些操作?
(写策略 )
1.
2.
5.2 Cache基本知识
5.2.1 映象规则
1,全相联映象全相联,主存中的任一块可以被放臵到
Cache中的任意一个位臵。
特点,空间利用率最高，冲突概率最低，
实现最复杂。
实际,Cache常包含几百个块，主存常包含几百万个块。
2,直接映象：
◆ 直接映象,主存中的每一块只能被放臵到
Cache中唯一的一个位臵。
◆ 特点,空间利用率最低，冲突概率最高，实现最简单。
例如,对于主存的第 i 块，若它映象到 Cache的第 j 块，则,
j＝ i mod (M ) （ M 为 Cache的块数）
(循环分配 )
◆ 组相联,主存中的每一块可以被放臵到 Cache
中唯一的一个组中的任何一个位臵。
◆ 设 M＝ 2m，则当表示为二进制数时,j 实际上就是 i 的低 m 位：
3,组相联映象：
m位
ji：
组相联是直接映象和全相联的一种折衷
◆ 上述的 j 和 k 通常称为索引
◆ 组的选择常采用位选择算法若主存第 i 块映象到第 k 组，则,
k＝ i mod（ G） （ G为 Cache的组数）
设 G＝ 2g，则当表示为二进制数时,k 实际上就是 i 的低 g 位：
g 位
k主存块地址 i：
相联度一定是越大越好？
◆ 绝大多数计算机的 Cache,n ≤4
◆ n 路组相联,每组中有 n 个块 ( n＝ M /G )
n 称为相联度。
相联度越高,Cache空间的利用率就越高，
块冲突概率就越低，失效率也就越低。
全相联直接映象组相联
n (路数 ) G (组数 )
M
M1
1
1＜ n＜ M 1＜ G＜ M
5.2.2 查找方法
1,如何确定 Cache中是否有所要访问的块？
若有的话如何确定其位臵？
◆ 目录表的结构
◆ 查找范围：候选位臵所对应的目录表项
◆ 并行查找与顺序查找提高性能的 重要思想,主候选位臵 (MRU块 )
◆ 并行查找的实现方法：
▲ 相联存储器
▲ 单体多字存储器＋比较器举例,４路组相联并行标识比较
◆ 直接映象 Cache的查找过程
◆ ４路相联 Cache的查找过程
5.2.3 替换算法所要解决的问题：当新调入一块，而 Cache
又已被占满时，替换哪一块？
2,FIFO
3,LRU
优点,失效率低
1,随机法优点,实现简单
LRU和随机法的失效率的比较
5.2.4 写策略
1.,写,操作所占的比例
Load指令,26％
Store指令,9％
,写,在所有访存操作中所占的比例：
9％ /(100％＋ 26％＋ 9％ )≈ 7％
,写,在访问数据 Cache操作中所占的比例：
9％ /(26％＋ 9％ )≈ 25％
3．,写,访问有可能导致 Cache和主存内容的不一致
2.,写,操作必须在确认是命中后才可进行
4．两种写策略
◆ 写直达法执行,写,操作时，不仅写入 Cache，而且也写入下一级存储器。
◆ 写回法执行,写,操作时，只写入 Cache。仅当
Cache中相应的块被替换时，才写回主存。
(设臵,污染位,)
5．两种写策略的比较
◆ 写回法的优点,速度快，所使用的存储器频带较低；
◆ 写直达法的优点,易于实现，一致性好。
6,写缓冲器
8,写策略与调块写回法 ── 按写分配写直达法 ── 不按写分配
7.,写,操作时的调块
◆ 按写分配 (写时取 )
写失效时，先把所写单元所在的块调入
Cache，再行写入。
◆ 不按写分配 (绕写法 )
写失效时，直接写入下一级存储器而不调块。
5.2.5 Cache举例例子,DEC的 Alpha AXP21064中的内部数据
Cache。
1,简介容量,8KB
块大小,32B
块数,256
调块,不按写分配映象方法,直接映象
,写,策略,写直达写缓冲器大小,4个块
2,结构图
3,失效情况下的操作读失效,Cache向 CPU发出一个暂停信号,通知它等待，并从下一级存储器中读如 32个字节，
填入对应的 Cache块。
写失效,CPU不对 Cache进行操作。
4,写缓冲的结构写合并,当把数据写入写缓冲器时，判断本次所写入单元的块地址是否与写缓冲器中某个有效块的地址相同，若是，则把新数据与该块合并。
5,混合 Cache与分离 Cache
访存操作,指令访问 (读指令 )
数据访问 (读写数据 )
分离 Cache,指令 Cache + 数据 Cache
混合 Cache,单一的 Cache
优缺点,(1)实现成本
(2)结构冲突
16 KB
容 量
1 KB
2 KB
4 KB
8 KB
32 KB
指令 Cache
3.06%
失 效 率 的 比 较
64 KB
128 KB
数据 Cache 混合 Cache
2.26%
1.78%
1.10%
0.64%
0.39%
0.15%
0.02%
24.61%
20.57%
15.94%
10.19%
6.47%
4.82%
3.77%
2.88%
13.34%
9.78%
7.24%
4.57%
2.87%
1.99%
1.36%
0.95%
分离 Cache平均失效率的计算：
访问指令 Cache的百分比 × 指令 Cache的失效率
＋访问数据 Cache的百分比 × 数据 Cache的失效率访问指令 Cache的百分比：
100％ /(100％＋ 26％＋ 9％ )≈75 ％
访问数据 Cache的百分比：
(26％＋ 9％ )/(100％＋ 26％＋ 9％ )≈25 ％
6.分离 Cache与混合 Cache平均失效率的比较前提,指令 Cache容量 +数据 Cache容量
= 混合 Cache容量
5.2.6 性能分析
2,平均访问时间平均访问时间＝命中时间＋失效率 × 失效开销例 5.1
假设 Cache的命中时间为 1个时钟周期，失效开销为 50 个时钟周期，在混合 Cache中一次 load
或 store操作访问 Cache的命中时间都要增加一个时钟周期 (因为混合 Cache只有一个端口，无法同时满足两个请求。按照前一章中有关流水线的术语，混合 Cache会导致结构冲突 )，根据 表 5－ 4所列的失效率，试问指令 Cache和数据 Cache容量均
1,失效率解：
如前所述，约 75%的访存为取指令。因此，
分离 Cache的总体失效率为：
(75%× 0.64%)＋ (25%× 6.47%)＝ 2.10%
根据 表 5－ 4，容量为 32KB的混合 Cache的失效率略低一些，只有 1.99%.
为 16KB的分离 Cache和容量为 32KB的混合 Cache相比，哪种 Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？
平均访存时间公式可以分为指令访问和数据访问两部分：
平均访存时间＝ 指令所占的百分比 ×
(指令命中时间＋指令失效率 × 失效开销 )＋
数据所占的百分比 ×
(数据命中时间＋数据失效率 × 失效开销 )
所以根据 表 5－ 4，两种结构的平均访存时间分别为：
平均访存时间 分离 ＝ 75%× (1＋ 0.64%× 50)＋
25%× (1＋ 6.47%× 50)
＝ (75%× 1.32)＋ (25%× 4.325)
＝ 0.990＋ 1.059＝ 2.05
平均访存时间 混合 ＝ 75%× (1＋ 1.99%× 50)＋
25%× (1＋ 1＋ 1.99%× 50)
＝ (75%× 1.995)＋ (25%× 2.995)
＝ 1.496＋ 0.749＝ 2.24
3,程序执行时间在考虑存储器对系统性能影响时，可以将系统性能描述为：
CPU时间＝ (CPU执行周期数＋存储器停顿周期数 )
× 时钟周期时间其中，
存储器停顿周期数＝
,读,的次数 × 读失效率 × 读失效开销
+“写,的次数 × 写失效率 × 写失效开销如果读、写失效率以及读、写失效开销相差不大，
存储器停顿周期数＝ 访存次数 × 失效率 ×
失效开销于是
CPU时间＝ IC× [CPIexe＋访存次数 /指令数 ×
失效率 × 失效开销 ]× 时钟周期时间例 5.2
我们用一个和 Alpha AXP类似的机器作为第一个例子。假设 Cache失效开销为 50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是 2.0个时钟周期,Cache的失效率为 2%，平均每条指令访存 1.33次。试分析
Cache对性能的影响。
考虑 Cache的失效后，性能为：
CPU 时间 有 cache＝ IC× (2.0＋ (1.33× 2%× 50))
× 时钟周期时间
＝ IC× 3.33× 时钟周期时间解：
实际 CPI,3.33
3.33/2.0 = 1.67(倍 )
CPU时间增加为原来的 1.67倍。但若不采用
Cache,则：
CPI＝ 2.0+50× 1.33＝ 68.5
例 5.3
考虑两种不同组织结构的 Cache:直接映象 Cache和两路组相联 Cache，试问它们对 CPU的性能有何影响？分析时用以下假设：
(1)理想 Cache(命中率为 100%)情况下 CPI为 2.0，时钟周期为 2ns，平均每条指令访存 1.3次。
(2)两种 Cache的容量均为 64KB,块大小 32字节
(3)对于组相联 Cache,CPU的时钟周期增加到原来的
1.1倍
(4)失效开销都是 70ns
(5)命中时间为 1个时钟周期,64KB直接映象 Cache的失效率为 1.4%,64KB两路组相联 Cache的失效率为 1.0%
解：
平均访存时间 =命中时间 +失效率 × 失效开销平均访存时间 直接 =2.0+(0.014× 70)=2.98ns
平均访存时间 组相联 =2.0× 1.10 +(0.010× 70)
=2.90ns
CPU时间＝ IC× [CPIexe＋访存次数 /指令数 ×
失效率 × 失效开销 ]× 时钟周期时间
＝ IC× [CPIexe× 时钟周期时间
＋访存次数 /指令数 × 失效率 × 失效开销
× 时钟周期时间 ]
CPU时间 直接 =IC× (2.0× 2+(1.3× 0.014× 70))
=5.27× IC
CPU时间 组相联 =IC× (2.0× 2× 1.10 +(1.3× 0.010× 70))
=5.31× IC
平均访存时间＝命中时间＋失效率 × 失效开销可以从三个方面改进 Cache的性能：
(1) 降低失效率
(2) 减少失效开销
(3) 减少 Cache命中时间下面介绍 15种 Cache优化技术
5.2.7 改进 Cache性能
(1) 强制性失效 (Compulsory miss)
当第一次访问一个块时，该块不在
Cache中，需从下一级存储器中调入 Cache，
这就是 强制性失效。
(冷启动失效，首次访问失效。 )
(2) 容量失效 (Capacity miss )
如果程序执行时所需的块不能全部调入 Cache中，则当某些块被替换后，若又
5.3 降低 Cache失效率的方法
1,三种失效 (3C)
重新被访问，就会发生失效。这种失效称为 容量失效。
(3) 冲突失效 (Conflict miss)
在组相联或直接映象 Cache中，若太多的块映象到同一组 (块 )中，则会出现该组中某个块被别的块替换 (即使别的组或块有空闲位臵 )，然后又被重新访问的情况。这就是发生了 冲突失效。
(碰撞失效，干扰失效 )
2,三种失效所占的比例
(SPEC92)
可以看出：
(1) 相联度越高，冲突失效就越少；
(2) 强制性失效和容量失效不受相联度的影响；
(3) 强制性失效不受 Cache容量的影响，但容量失效却随着容量的增加而减少；
(4) 表中的数据符合 2:1的 Cache经验规则，即大小为 N 的直接映象 Cache的失效率约等于大小为 N/2 的两路组相联 Cache的失效率。
强制性失效,增加块大小，预取
(本身很少 )
容量失效,增加容量
(抖动现象 )
冲突失效,提高相联度
(理想情况：全相联 )
3,减少三种失效的方法
4,许多降低失效率的方法会增加命中时间或失效开销
5.3.1 增加 Cache块大小
2,增加块大小会增加失效开销
1,失效率与块大小的关系
(1) 对于给定的 Cache容量，当块大小增加失效率开始是下降，后来反而上升了；
(2) Cache容量越大，使失效率达到最低的块大小就越大。
3,例题例 5.4
假定存储系统在延迟 40个时钟周期后，每 2个时钟周期能送出 16个字节。即,经过 42个时钟周期，
它可提供 16个字节；经过 44个时钟周期，可提供 32
个字节；依此类推。试问对于 表 5-6中列出的各种容量的 Cache，在块大小分别为多少时，平均访存时间最小？
解,
平均访存时间为：
平均访存时间 ＝ 命中时间＋失效率 × 失效开销假设命中时间与块大小无关，为 1个时钟，那么对于一个块大小为 16字节，容量为 1KB的 Cache来说：
平均访存时间 ＝ 1＋（ 15.05 %× 42）
＝ 7.321 个时钟周期而对于块大小为 256B的大小为 256KB的 Cache来说，
平均访存时间为：
平均访存时间 ＝ 1＋（ 0.49 %× 72）
＝ 1.353 个时钟周期表 5.7列出了在这两种极端情况之间的各种块大小和各种 Cache容量的平均访存时间。
块大小
（字节
）
失效开销
（时钟周期）
Cache容量（字节）
1K 4K 16K 64K 256K
16 42 7.321 4.599 2.655 1.857 1.458
32 44 6.870 4.186 2.263 1.594 1.308
64 48 7.605 4.360 2.267 1.509 1.245
128 56 10.318 5.357 2.551 1.571 1.274
256 72 16.847 7.847 3.369 1.828 1.353
5.3.2 提高相联度
1,采用相联度超过 8的方法实际意义不大
2,2:1 Cache经验规则容量为 N 的直接映象
Cache≈ 容量为 N/2的两路组相联 Cache
3,提高相联度是以增加命中时间为代价例如：
TTL或 ECL板级 Cache，两路组相联：
增加 10％
定制的 CMOS Cache,两路组相联：
增加 2％
4,例题假定提高相联度会按下列比例增大处理器时钟周期：
时钟周期 2路 ＝ 1.10× 时钟周期 1路时钟周期 4路 ＝ 1.12× 时钟周期 1路时钟周期 8路 ＝ 1.14× 时钟周期 1路假定命中时间为 1个时钟，失效开销为 50个时钟周期，而且假设不必将失效开销取整。使用表 5－ 5中的失效率，试问当 Cache为多大时，以下不等式成立？
例 5.5
平均访存时间 8路 < 平均访存时间 4路平均访存时间 4路 < 平均访存时间 2路平均访存时间 2路 < 平均访存时间 1路解,
在各种相联度的情况下，平均访存时间分别为：
平均访存时间 8路 = 命中时间 8路 + 失效率 8路
× 失效开销 8路
= 1.14＋失效率 8路 × 50
平均访存时间 4路 = 1.12 ＋失效率 4路 × 50
平均访存时间 2路 = 1.10 ＋失效率 2路 × 50
平均访存时间 1路 = 1.00 ＋失效率 1路 × 50
在每种情况下的失效开销相同，都是
50个时钟周期。把相应的失效率代入上式，
即可得平均访存时间。
例如,1KB的直接映象 Cache的平均访存时间为：
平均访存时间 1路 ＝ 1.00＋ (0.133× 50)
＝ 7.65
容量为 128KB的 8路组相联 Cache的平均访存时间为：
平均访存时间 8路 ＝ 1.14＋ (0.006× 50)
＝ 1.44
表 5-8
Cache容量
（ K字节）
相联度（路）
1 2 4 8
1 7.65 6.60 6.22 5.44
2 5.90 4.90 4.62 4.09
4 4.60 3.95 3.57 3.19
8 3.30 3.00 2.87 2.59
16 2.45 2.20 2.12 2.04
32 2.00 1.80 1.77 1.79
64 1.70 1.60 1.57 1.59
128 1.50 1.45 1.42 1.44
1,基本思想在 Cache和它从下一级存储器调数据的通路之间设臵一个全相联的小 Cache，
用于存放被替换出去的块 (称为 Victim)，
以备重用。
工作过程
5.3.3 Victim Cache
对于减小冲突失效很有效，特别是对于小容量的直接映象数据 Cache，作用尤其明显。
例如，项数为 4的 Victim Cache:
使 4KB Cache的冲突失效减少 20%～ 90%
2,作用
1,直接映象 vs．组相联
5.3.4 伪相联 Cache(列相联 )
2,伪相联 Cache
优 点 缺 点直接映象组相联命中时间小命中时间大失效率高失效率低取直接映象及组相联两者的优点：
命中时间小，失效率低
(1) 基本思想及工作原理在逻辑上把直接映象 Cache的空间上下平分为两个区。对于任何一次访问，伪相联
Cache先按直接映象 Cache的方式去处理。若命中，则其访问过程与直接映象 Cache的情况一样。若不命中，则再到另一区相应的位臵去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。
(2) 快速命中与慢速命中要保证绝大多数命中都是快速命中。
3,例题例 5.6
假设当在按直接映象找到的位臵处没有发现匹配、而在另一个位臵才找到数据 (伪命中 )
需要 2个额外的周期。仍用上个例子中的数据，
问,当 Cache容量分别为 2KB和 128KB时，直接映象、两路组相联和伪相联这三种组织结构中，
哪一种速度最快？
首先考虑标准的平均访存时间公式：
平均访存时间 伪相联
＝命中时间 伪相联 ＋失效率 伪相联 × 失效开销 伪相联由于：
失效率 伪相联 ＝失效率 2路命中时间 伪相联 ＝命中时间 1路 ＋伪命中率 伪相联 × 2；
伪命中率 伪相联 ＝命中率 2路 －命中率 1路
＝ (1－失效率 2路 )－ (1－失效率 1路 )
＝失效率 1路 －失效率 2路解：
故：
平均访存时间 伪相联
＝命中时间 1路 ＋ (失效率 1路 －失效率 2路 )× 2
＋失效率 2路 × 失效开销 1路将表 5－ 5中的数据代入上面的公式，得：
平均访存时间 伪相联,2KB
＝ 1＋ (0.098－ 0.076)× 2＋ (0.076× 50)
＝ 4.844
平均访存时间 伪相联,128KB
＝ 1＋ (0.010－ 0.007)× 2＋ (0.007× 50)
＝ 1.356
根据上一个例子中的表 5－ 8，对于 2KB Cache，
可得：
平均访存时间 1路 ＝ 5.90 个时钟平均访存时间 2路 ＝ 4.90 个时钟对于 128KB的 Cache有，可得：
平均访存时间 1路 ＝ 1.50 个时钟平均访存时间 2路 ＝ 1.45 个时钟可见，对于这两种 Cache容量，伪相联 Cache
都是速度最快的。
缺点,多种命中时间
5.3.5 硬件预取技术依据,空间局部性思想,在 Cache访问失效时，不但从内存中取入对应的块，而且将它的邻近块 (通常为后继块 )取入一个速度快于主存的缓冲器中，这样当对后继块的访问发生时，可通过访问该缓冲器进行块替换。
1,指令和数据都可以预取
2,预取内容既可放入 Cache，也可放在外缓冲器 (速度快于主存 )中例如：指令流缓冲器
3,预取效果
(1) Jouppi的研究结果
◆ 指令预取,(4KB，直接映象 Cache,
块大小＝ 16字节 )
1个块的指令流缓冲器,捕获 15％～ 25％
的失效
4个块的指令流缓冲器,捕获 50％
16个块的指令流缓冲器,捕获 72％
◆ 数据预取,(4KB,直接映象 Cache)
1个数据流缓冲器,捕获 25％的失效还可以采用多个数据流缓冲器
(2) Palacharla和 Kessler的研究结果流缓冲器,既能预取指令又能预取数据对于两个 64KB四路组相联 Cache来说：
8个流缓冲器能 捕获 50％～ 70％的失效。
4,例题例 5.7
Alpha AXP 21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术,Alpha
APX 21064的指令 Cache必须为多大才能保持平均访存时间不变？
解：
假设从预取缓冲器中找到所需指令 (并进行替换 )需多花 1个时钟周期。
平均访存时间 预取
＝命中时间＋失效率 × 预取命中率 × 1
＋失效率 × (1－预取命中率 )× 失效开销假设：
预取命中率＝ 25％
命中时间＝ 1 个时钟周期失效开销＝ 50个时钟周期由 表 5－ 4可知,8KB指令 Cache的失效率＝ 1.10％
故平均访存时间 预取 ＝ 1＋ (1.10 %× 25 %× 1)＋
(1.10 %× (1－ 25 %)× 50)
＝ 1＋ 0.00275＋ 0.4125
＝ 1.415
由公式：
平均访问时间＝命中时间＋失效率 × 失效开销可得相应的失效率为：
失效率＝ (平均访问时间－命中时间 )/失效开销
＝ (1.451－ 1)/50＝ 0.83％
8KB Cache 带预取的8kB Cache
失效率 1.10％ 0.83％
16KB Cache
0.64％
关键：预取应建立在存储器的空闲频带
5.3.6 由编译器控制的预取
1,预取的类型
◆ 寄存器预取,把数据取到寄存器中
◆ Cache预取,只将数据取到 Cache中
◆ 故障性预取,预取时，若出现虚地址故障或违反访问权限，就会发生异常。
◆ 非故障性预取,预取时，若出现虚地址故障或违反访问权限，并不会导致异常，只是转变为,不预取,。
由编译器加入预取指令，在数据被用到之前发出预取请求。
4,例题
2,在预取数据的同时，处理器应能继续执行只有这样，预取才有意义。
非阻塞 Cache (非锁定 Cache)
3,循环是预取优化的主要对象失效开销小时,循环体展开 1～ 2次失效开销大时,循环体展开许多次例 5.8
对于下面的程序，判断哪些访问可能会导致数据 Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：
(1) 我们用的是一个容量为 8KB、块大小为
16B的直接映象 Cache，它采用写回法并且按写分配。
(2) a,b分别为 3× 100(3行 100列 )和 101× 3
的双精度浮点数组，每个元素都是 8个字节。当程序开始执行时，这些数据都不在 Cache内。
for (i＝ 0 ; i < 3 ; i＝ i＋ 1 )
for (j＝ 0 ; j < 100 ; j＝ j＋ 1 )
a[i][j]＝ b[j][0]× b[j＋ 1][0];
解：
(1) 计算过程
(2) 失效情况 数组 a 数组 b
总的失效次数＝ 251次
(3) 改进后的程序 (设预取的开销比较大，需提前 7 次循环进行 )
for (j＝ 0,j＜ 100； j＝ j＋ 1) {
prefetch (b[j＋ 7][0]);
/* 预取 7次循环后所需的 b(j,0 ) */
prefetch (a[0][j＋ 7]);
/* 预取 7次循环后所需的 a(0,j ) */
a[0][j]＝ b[j ][0] * b [j＋ 1][0]
}
for (i＝ 1; i < 3; i＝ i＋ 1) {
for (j＝ 0; j < 100; j＝ j＋ 1)
prefetch(a[i][j＋ 7]);
/* 预取 7次循环后所需的 a(i,j ) */
a[i][j]＝ b[j][0] * b[j＋ 1][0];
}
例 5,9
在以下条件下，计算例 5.8中所节约的时间：
(1) 忽略指令 Cache失效，并假设数据 Cache
无冲突失效和容量失效。
(2) 假设预取可以被重叠或与 Cache失效重叠执行，从而能以最大的存储带宽传送数据。
(3) 不考虑 Cache失效时，修改前的循环每 7
个时钟周期循环一次。修改后的程序中，
失效情况总的失效次数＝ (7+4)+4+4=19次解：
修改前：
循环时间 ＝ 300× 7 ＝ 2100
总失效开销＝ 251× 50＝ 12550
总运行时间＝ 2100＋ 12550＝ 14650
第一个预取循环每 9个时钟周期循环一次，
而第二个预取循环每 8个时钟周期循环一次 (包括外层 for循环的开销 )。
(4) 一次失效需 50个时钟周期。
修改后：
循环时间＝ 100× 9＋ 200× 8＝ 2500
总失效时间＝ 19× 50＝ 950
总运行时间＝ 2500＋ 950＝ 3450
加速比＝ 14650/3450＝ 4.2
5.3.7 编译器优化
2KB Cache,降低 50％
8KB Cache,降低 75%
1,基本思想在编译时，对程序中的指令和数据进行重新组织，以降低 Cache失效率。
2,McFaring 发现：通过对指令进行重新排序，
可有效地降低指令 Cache的失效率。
3,数据对存储位臵的限制比指令的少，因此更便于优化。
通过把数据重新组织，使得在一块数据被从 Cache替换出去之前，能最大限度利用其中的数据 (访问次数最多 )
(1) 数据合并举例：
/* 修改前 */
int val [SIZE];
int key [SIZE];
(2) 内外循环交换举例：
/* 修改前 */
for (j＝ 0 ;j<100 ;j＝ j＋ 1)
for (i＝ 0 ;i<5000 ;i＝ i＋ 1)
x[i][j]＝ 2*x[i][j];
/* 修改后 */
struct merge {
int val ;
int key ;
} ;
struct merge merged_array[size];
(3) 循环融合举例：
/* 修改前 */
for (i＝ 0 ; i<N ;i＝ i＋ 1)
for (j＝ 0 ; j<N ; j＝ j＋ 1)
a[i][j]＝ 1/b[i][j]*c[i][j];
/* 修改后 */
for (i＝ 0 ;i<100 ;i＝ i＋ 1)
for (j＝ 0 ;j< 000 ;j＝ j＋ 1)
x[i][j]＝ 2*x[i][j];
/* 修改后 */
for (i＝ 0 ;i < N ;i＝ i＋ 1)
for (j＝ 0 ;j < N ;j＝ j＋ 1) {
a[i][j]＝ 1/b[i][j]*c[i][j];
d[i][j]＝ a[i][j]＋ c[i][j];
}
for (i＝ 0 ;i<N ;i＝ i＋ 1)
for (j＝ 0 ; j<N ;j＝ j＋ 1)
d[i][j]＝ a[i][j]＋ c[i][j];
(4)分块把对数组的整行或整列访问改为按块进行。
举例：
/* 修改前 */
for (i＝ 0; i < N; i＝ i＋ 1)
for (j＝ 0; j < N; j＝ j＋ 1) {
r＝ 0;
for (k＝ 0; k < N; k＝ k＋ 1) {
r＝ r＋ y[i][k]*z[k][j];
}
x[i][j]＝ r;
}
计算过程最坏情况下失效次数,2N3＋ N2
/* 修改后 */
for (jj＝ 0; jj < N; jj＝ jj＋ B)
for (kk＝ 0; kk < N; kk＝ kk＋ B)
for (i＝ 0; i < N; i＝ i＋ 1)
for (j＝ jj; j < min(jj＋ B－ 1,N); j＝ j＋ 1) {
r＝ 0;
for (k＝ kk; k < min(kk＋ B－ 1,N); k＝ k＋ 1) {
r＝ r＋ y[i][k]*z[k][j];
}
x[i][j]＝ x[i][j]＋ r;
}
失效次数,2N3/B + N2
5.4.1 让读失效优先于写
5.4 减少 Cache失效开销
1,Cache中的写缓冲器导致对存储器访问的复杂化
2,解决问题的方法 (读失效的处理 )
◆ 推迟对读失效的处理
(缺点,读失效的开销增加，如 50％ )
◆ 检查写缓冲器中的内容
3,在写回法 Cache中，也可采用写缓冲器
5.4.2 子块放臵技术
1,为减少标识的位数，可采用增加块大小的方法，但这会增加失效开销,故应采用子块放臵技术。
2,子块放臵技术,把 Cache块进一步划分为更小的块 (子块 )，并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效。
Cache与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位。
3,举例 (图示 )
5.4.3 请求字处理技术
1,请求字从下一级存储器调入 Cache的块中，只有一个字是立即需要的。这个字称为 请求字。
2,应尽早把请求字发送给 CPU
◆ 尽早重启动,调块时，从块的起始位臵开始读起。一旦请求字到达，就立即发送给
CPU，让 CPU继续执行。
◆ 请求字优先,调块时，从请求字所在的位臵读起。这样，第一个读出的字便是请求字。将之立即发送给 CPU。
3,这种技术在以下情况下效果不大：
◆ Cache块较小
◆ 下一条指令正好访问同一 Cache块的另一部分。
5.4.4 非阻塞 Cache技术
1,非阻塞 Cache,Cache失效时仍允许 CPU进行其它的命中访问。即允许,失效下命中,
2,进一步提高性能：,多重失效下命中,,
,失效下失效,
(存储器必须能够处理多个失效 )
3,重叠失效个数对平均访问时间的影响非阻塞 Cache平均存储器等待时间与阻塞 Cache的比值
1 2
浮点程序 76％ 51％
64
39％
整数程序 81％ 78％ 78％
重叠失效个数对于图 5.17所描述的 Cache，在两路组相联和
“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？
假设 8KB数据 Cache的平均失效率为：
对于浮点程序，直接映象 Cache为 11.4%，两路组相联 Cache为 10.7%；
对于整数程序，直接映象 Cache为 7.4%，两路组相联 Cache为 6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为 16个时钟周期。
例 5.10
对于浮点程序，平均存储器等待时间为：
失效率 直接映象 × 失效开销＝ 11.4%× 16＝ 1.82
失效率 两路组相联 × 失效开销＝ 10.7%× 16＝ 1.71
1.71/1.82＝ 0.94
对于整数程序：
失效率 直接映象 × 失效开销＝ 7.4 %× 16＝ 1.18
失效率 两路组相联 × 失效开销＝ 6.0 %× 16 ＝ 0.96
0.96/1.18=0.81
结论,对浮点运算采用,一次失效下命中”措施比采用
,两路组相联,技术更有效,
解：
5.4.5 两级 Cache
1,应把 Cache做得更快？还是更大？
答案：二者兼顾，再增加一级 Cache
◆ 第一级 Cache(L1)小而快
◆ 第二级 Cache(L2)容量大
2,性能分析平均访问时间
＝命中时间 L1＋失效率 L1× 失效开销 L1
＝命中时间 L1＋失效率 L1×
(命中时间 L2＋失效率 L2× 失效开销 L2)
3,局部失效率与全局失效率局部失效率 ＝该级 Cache的失效次数 /到达该级 Cache的访问次数例如：上述式子中的失效率 L2
全局失效率 ＝该级 Cache的失效次数 /CPU
发出的访存的总次数全局失效率 L2＝失效率 L1× 失效率 L2
局部失效率一般不能反映对提高系统实际运行性能所发挥的作用,因此评价第二级 Cache时，一般使用全局失效率这个指标。
4,当第二级 Cache比第一级 Cache大得多时，两级 Cache的全局失效率和第二级 Cache相同的单级 Cache的失效率非常接近。
5,第二级 Cache的参数第二级 Cache不会影响 CPU的时钟频率，
因此其设计有更大的考虑空间。
两个问题：
◆ 能否降低 CPI中的平均访存时间部分？
◆ 成本是多少？
(1) 容量第二级 Cache的容量一般比第一级的大许多，如 512KB
(2) 相联度第二级 Cache可采用较高的相联度或伪相联方法例 5.12
给出有关第二级 Cache的以下数据：
⑴ 两路组相联使命中时间增加 10%× CPU时钟周期
⑵ 对于直接映象，命中时间 L2＝ 10个时钟周期
⑶ 对于直接映象，局部失效率 L2＝ 25%
⑷ 对于两路组相联，局部失效率 L2＝ 20%
⑸ 失效开销 L2＝ 50个时钟周期试问第二级 Cache的相联度对失效开销的影响如何？
解：
对于一个直接映象的第二级 Cache来说，
第一级 Cache的失效开销为：
失效开销 直接映象,L1
＝ 10＋ 25%× 50＝ 22.5个时钟周期对于两路组相联第二级 Cache来说，命中时间增加了 10%(0.1)个时钟周期，故第一级
Cache的失效开销为：
失效开销 两路组相联,L1
＝ 10.1＋ 20%× 50＝ 20.1个时钟周期故对于第二级 Cache来说，两路组相联优于直接映象。
(3) 块大小第二级 Cache可采用较大的块，
如 64,128,256字节。
为减少平均访存时间，可以让容量较小一的第一级 Cache采用较小的块，而让容量较大的第二级 Cache采用较大的块。
5.5 减少命中时间
2,应使 Cache足够小，以便可以与 CPU一起放在同一块芯片上。
命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是 Cache的访问时间限制了处理器的时钟频率。
1,硬件越简单，速度就越快；
5.5.1 容量小、结构简单的 Cache
1,虚拟 Cache
访问 Cache的索引以及 Cache中的标识都是虚拟地址 (一部分 )。
2,并非人人都采用虚拟 Cache
原因一：不同进程虚地址空间的相同。
3,解决方法：
(1)进程切换时清空虚拟 Cache。
(2)在地址标识中增加 PID字段 (进程标识符 )。
三种情况下失效率的比较：
单进程,PIDs，清空
PIDs与单进程相比,＋ 0.3％～＋ 0.6％
PIDs与清空相比,－ 0.6％～－ 4.3%
5.5.2 虚拟 Cache
4.原因二,同义和别名 (不同虚地址对应相同实地址情况 )
解决方法：
(1)反别名法 ——用硬件来保证每一个 Cache块对应唯一实地址。
(2)页着色 ——Sun公司的 UNIX系统要求所有有别名的地址最后 18位相同，而直接映象 Cache
的索引来自于这最后 18位 (Cache容量不超过 218
字节 )，这使得所有别名映象到同一 Cache块位臵。
5,根据页内位移 (这部分虚实地址相同 )进行
Cache索引 (同时进行虚实地址转换 )，用实地址判断是否命中。
优点,兼得虚拟 Cache和物理 Cache的好处
( Cache索引和虚实地址转换同时进行 )
局限性,Cache容量受到限制直接映象,Cache容量 ≤ 页大小组相联映象,Cache容量 ≤ 页大小 × 相联度
5.5.3 将写操作流水化以加快写命中读写命中一般包含两步：
(1)判断是否命中。
(2)(如果命中 )对 Cache进行读写。
对读操作：两步可并行进行。
对写操作：两步必须串行进行。
解决方法,将写操作的两步操作流水化,
优化技术 失效率失效开销命中时间硬件复杂度评价增加块大小 + - 0 实现容易； RS/6000 550采用了
128字节提高相联度 + - 1 MIPS R10000为 4路组相联
Victim Cache + 2 HP7200中采用了类似的技术伪相联 Cache + 2 已应用于 MIPS R10000的第二级 Cache
硬件预取指令和数据
+ 2 数据预取比较困难；仅被几台机器采用,如,Alpha 21064
编译器控制的预取 + 3 需采用非阻塞 cache；有几种机器支持它用 编 译 技 术 减 少
Cache失效次数
0 向软件提出了新要求；有些机器提供了编译器选项
+
使读失效优先级高于写
+ 1 在单处理机上实现容易,被广泛使用子块调入 + 1 主要用于减少标识的数目尽早重启动和关键字优先
+ 2 已 应 用 于 MIPS R10000 和
IBM 620
非阻塞 Cache + 3 已应用于 Alpha 21064 和
R10000中第二级 Cache + 2 硬件代价大；两级 Cache的块大小不同时实现困难；被广泛采用容量小且结构简单的 Cache
- + 0 实现容易,被广泛使用避免在对 Cache进行索引时进行地址转换
+ 2 对于小容量 Cache来说实现容易,已应用于 Alpha 21064
流水化写 + 1 已应用于 Alpha 21064
5.6.1 存储器技术
1,主存的主要性能指标,延迟和带宽
2,以往：
Cache主要关心延迟,I/O主要关心带宽
3,现在,Cache关心两者 (由于二级 Cache使用较大的块 )
5.6 主 存
1,存储器延迟：访问时间，存储周期
2,地址线复用：行选通和列选通
3,DRAM与 SRAM
容量,4～ 8,1
存储周期,8～ 16:1
价格,1,8～ 16
一般来说：
主存,DRAM Cache,SRAM
4,Amdahl经验规则为了保持系统平衡，存储容量和性能应随 CPU速度的提高而线性增加。
5,各代 DRAM的典型时间参数,
年 份 芯片容量行选通 (RAS)
最慢的 DRAM 最快的 DRAM
列 选 通
(CAS) 周期时间
1980
1983
1986
1989
1992
1995
64K 位
256K 位
1M 位
4M 位
16M 位
64M 位
180ns
150ns
120ns
100ns
80ns
65ns
150ns
120ns
100ns
80ns
60ns
50ns
75ns
50ns
25ns
20ns
15ns
10ns
250ns
220ns
190ns
165ns
120ns
90ns
表 5-10 各代 DRAM 的典型时间参数
5.6.2 提高主存性能的存储器组织结构
1,增加存储器的宽度
2,采用简单的多体交叉存储器
3,独立存储体
◆ 设臵多个存储控制器，使多个体能独立操作，
以便能同时进行 多个独立的访存 。
◆ 每个体有独立的地址线
◆ 非阻塞 Cache与多体结构
◆ 超体,多体交叉存储器 + 独立存储体独立存储体 独立存储体 独立存储体 独立存储体存 储 器 系 统
4,避免存储体冲突
◆ 体冲突,两个请求要访问同一个体
◆ 减少冲突,采用许多体例如,NEC SX/3最多 128个体问题仍旧存在：
例：
int x[256][512];
for (j=0;j<512;j++)
for (i=0;i<256;i++)
x[i][j]=2*x[i][j]
◆ 解决体冲突的方法：
▲ 软件方法 (编译器 )
1.循环交换优化例：
int x[256][512];
for (i=0;i<256;i++)
for (j=0;j<512;j++)
x[i][j]=2*x[i][j]
2.扩展数组的大小，使之不是 2的幂。
▲ 硬件方法使体数为 素数 以减少体冲突机会 。
一般取：
体号 =地址 mod 体数体内地址 =地址 / 体数当存储体数为素数，且为 2的幂减 1时，取体号 =地址 mod 体数体内地址＝地址 mod 存储体中的字数 (可以直接载取 )
根据中国剩余定理，可有以下一一对应：
地址 (体号，体内地址 )
◆ 举例体 内 地 址存 储 体顺 序 交 叉 取 模 交 叉
0
1
2
3
4
5
表 5-11 顺序交叉和取模交叉的地址映象举例
6
7
0 1 2 0 1 2
0 1 2 0 16 8
3 4 5
6 7 8
9 10 11
12 13 14
21 22 23
15 16 17
18 19 20
9 1 17
18 10 2
3 19 11
12 4 20
21 13 5
6 22 14
15 7 23
5,DRAM专用交叉结构
◆ 三种方式
▲ Nibble方式每次访问时，除给出所需位外，还能给出其后 3位。
▲ Page方式行选通 (RAS)后，整个一行内容并行输出到缓冲器，随后可以 SRAM速度随几访问其中的任意一位。
▲ Static column方式与 Page方式类似，只是在列地址改变时，数据线内容跟随变化而无需触发列访问选通线。
◆ RAMBUS
用总线方式取代 RAS/CAS
能自己完成刷新
能在一次访存期间 (发送地址到返回数据 )通过总线接受另一次访存请求
数据宽度一个字节
最高 2ns传送一个字节。
5.7 虚拟存储器
提出于 1961年
解决应用程序对主存容量的越来越高要求以及主存难以满足这一问题,
从程序覆盖技术发展而来
1,基本想法
外存作为基本存储器,存放执行中的程序和数据
为每个进程分配一个独立的逻辑空间 (虚拟空间 ),在这个空间中每条指令和数据都分配一个逻辑地址 (虚拟地址 )
5.7.1 虚拟存储器基本原理
指令与指令、指令与数据的访问关系用逻辑地址来表达
指令和数据在被访问到时被调入内存,相应的从逻辑地址到物理地址 (主存地址 )的映射被建立，然后按照这种映射关系在指令运行时把逻辑地址转化成物理地址，实现实际的访问。
2,虚拟存储器的特点
◆ 多个进程可以共享主存空间
◆ 程序员不必做存储管理工作
◆ 采用动态再定位，简化了程序的装入
3,虚拟存储器的分类按照空间管理单位
◆ 页式把空间分成大小相同的块 (4KB? 64KB)，称为页面
◆ 段式把空间分成可变长的块，称为段，段的大小可根据程序的逻辑意义来确定，一般是程序模块。
页 式 段 式地址大小 ( 字 ) 1 2 ( 段号和段内位移 )
对程序员是否透明 透明 可能透明替换一个块 容易 ( 所有块大小相同 ) 困难 ( 必须找到能容纳该段的空闲主存块 )
存储空间浪费 内部碎片 ( 页内未使用部分 ) 外部碎片 ( 主存中的无用块 )
磁盘传送效率 高 ( 可根据磁盘传送效率选择合适的页面大小 )
不一定 ( 比较小的段可能只有几个字节 )
4,有关虚拟存储器的四个问题
◆ 映象规则全相联 (失效开销太大 )
◆ 查找算法页表，段表虚页号 页内位移页表物理页号 页内位移虚拟地址物理地址页表每一项对应一个虚页号每一项一般有这样一些域
(1)该页是否已在主存中
(2)该页在主存中的起始地址 (物理页号 )
(3)其他信息 (如保护信息等 )
页表通常非常大
◆ 替换算法
LRU
主存的每个页面设臵一个使用位
◆ 写策略写回法 (磁盘不支持单个字的写 )
为了减少写操作通常使用,脏,位方法来保证只有被修改的页才被写回。
5.7.2 快表 TLB
页表一般比较大，存放在主存中。为了加快页表访问，通常设臵一个类似于 Cache的高速缓冲器，称为快表 (TLB)
◆ TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项 ;
◆ TLB中的内容是页表部分内容的一个副本，为了保持一致性，当修改页表某一项时，操作系统须清除
TLB中对应项 ;
◆ TLB也利用了局部性原理 ;
◆ TLB一般比 Cache的标识存储器更小、更快
5.7.3 页面大小的选择
1,大页面和小页面各有优点如何进行权衡?
2,大页面的好处：
◆ 页表的大小与页面大小成反比。较大的页面可以节省实现地址映象所需的存储空间及其它资源；
◆ 较大的页面可以使快速 Cache命中的实现更简单 (5.5节 )；
◆ 在主存和辅存之间 (也许还通过网络 )传送较大的页面比传送较小的页面更有效；
◆ TLB的项数有限，对于给定数目的项数，
较大的页面意味着可以高效地实现更多存储空间的地址变换，从而减小 TLB失效的次数。
3,采用较小的页面可以减少空间的浪费假设每个进程有三个主要的段：
代码，堆，堆栈,
则 平均浪费 1.5个页面。
当今计算机大部分都支持多道程序运行：
多个进程 (运行中的程序 )既能同时在独立的环境中运行又能共享系统资源。
典型例子：多用户分时系统 -----每个用户的进程既能共享资源 (如 CPU、内存、系统软件等 )又能彼此相互不影响的独立运行。
进程的保护问题,进程的正确运行不受其他进程运行状况的影响。
保护的手段,主要是对存储区域的保护，使一个进程的信息不被另一个进程错误地修改。
5.8 进程保护和虚存实例保护的形式,有一定的多样性，有时需要允许进程间有共享数据区域以进行数据通信。
5.8.1 进程保护
1,界地址寄存器方法 (最简单的方法 )
一对寄存器,基地址，上界地址检测条件,(基地址＋地址 )≤ 上界地址不适合虚拟存储器系统 ---进程的访问空间不是一个连续空间。
2,映象表方法 (适用于虚存系统 )
a) 形式 1,每个进程有一个独立页表，进程不能访问页表上找不到的主存页面。
存在问题,不能实现共享数据区域
b) 形式 2,将进程的地址空间分成系统区域和用户区域，系统区域为各进程共享，只用一个页表，
而用户区域各进程使用各自的页表。
存在问题,不能实现复杂的权限控制
c) 形式 3,在页表中给每个页面设臵许可信息，如只读、只可运行、只可由系统程序访问等。
许可信息的形式,
(1)键保护方式：操作系统给每个页面分配一个存储键 (锁 )，每个进程分配一个访问键 (钥匙 )，以控制其访问关系。
(2)环式保护方式：将系统程序和用户程序按访问权限分层，如核心层、系统层、操作系统扩展层、
应用层等，每个内存页面也有一个层号，对某一个进程，它只能访问同层或外层的页面硬件方面的支持至少包括：
(1)提供两种以上的状态，分别表示当前运行的进程是用户进程还是系统进程。
(2)提供一些 CPU状态，用户进程可读不可修改。
(3)提供一种在用户状态和系统状态转换的机制。
5.8.2 页式虚存举例,Alpha Axp
Alpha Axp体系结构采用 段页相结合 的方式。
1,Alpha的地址空间分为 3段：
kseg(地址最高两位,10) (内核 )
sego(最高位,0) (用户 )
seg1(最高两位,11) (用户 )
sego和 seg1的布局
2,Alpha采用三级页表地址变换过程
3,Alpha的页表项 (PTE)
4,Alpha Axp21064TLB的参数参 数 描 述块 大 小命 中 时 间平均失效开销
TBL 容 量块替换策略写 策 略块映象策略
1 PTE (8字节 )
1 个时钟周期
20 PTE (8字节 )
随 机不适用全相联指令 TLB,8 个 PTE 用于大小为 8K 字节的页，
4个 PTE 用于大小为 4MB 的页 (共 96 个字节 )
数据 TLB,32 个 PTE 用于大小为 8KB,64KB、
512KB 何 4MB 的页 (共 256 个字节 )
表 5-14 Alpha AXP 21064 TLB 的存储层次参数
5.9 Alpha Axp21064存储层次
1,简介
2,工作过程
5.10 小 结
1,本章存储层次实例总结表 5-15
块大小
(字节 )
虚拟存储器TLB 第一级 Cache 第二级 Cache
命中时间
(时钟周期 )
失效开销
(时钟周期 )
失效率 (局部 )
容量 (字节 )
映象算法写策略
4－ 8
(1 个 PTE)
1
10－ 30
第一级 Cache
全相联 /组相联标识 /块
4－ 32
1－ 2
8－ 66
第二级 Cavhe
直接映象标识 /块
32－ 256
6－ 15
30－ 200
页模式 DRAM
直接映象 /组相联标识 /块表 5-15 本章存储层次实例总结
4096－ 16384
10－ 100
700,000－ 6,000,000
磁盘全相联表替换算法查找算法下一级存储器
0.1－ 2% 0.5－ 20% 15－ 30% 0.00001－ 0.001%
32－ 8192
(8－ 1024 个 PTE) 1－ 128K 256K－ 16M 16－ 8192M
随机 无 (直接映象 ) 随机 近似 LRU
写页表时时清空 写直达 /写回法 写回法 写回法
1,从用户的角度来看，存储器的三个主要指标是：
容量，速度，价格 (每位价格 )
5.1 存储器的层次结构第五章 存储层次
2,人们对这三个指标的期望,
3,这三个指标相互矛盾,
4,解决方法采用多种存储器技术，构成存储层次,
5.1.2 存储层次的性能参数
C,S,TA
设,S ── 容量
TA ── 访问时间
C ── 每位价格下面仅考虑由 M1和 M2构成的两级存储层次：
M1的参数,S1,TA1,C1
M2的参数,S2,TA2,C2
1,每位价格 C C＝ ─────
如果 S1<< S2,C? C2
C1S1＋ C2S2
S1＋ S2
2,命中率 H 和失效率 F
命中率 H,CPU访问存储系统时，在 M1中找到所需信息的概率。
H＝ N1/(N1＋ N2)
N1 ── 访问 M1的次数
N2 ── 访问 M2的次数失效率 F,CPU访问存储系统时，在 M1中找不到所需信息的概率。
F＝ 1－ H
3,平均访问时间 TA
对大部分系统,TM＝ TA2＋ TB
由于
TA＝ H?TA1＋ (1－ H )(TA1+TM )
于是
TA＝ TA1＋ (1－ H )TM
或
TA＝ TA1＋ FTM
TA1 ── 命中时间
TM ── 失效开销
5.1.3,Cache－主存,和,主存－辅存,层次一般来说：
,Cache－主存,层次：弥补主存速度的不足
,主存－辅存,层次：弥补主存容量的不足
1.,Cache－主存,层次主存与 CPU的速度差距
“Cache - 主存,层次的实现：主要借助于辅助硬件。
2.,主存－辅存,层次
,主存－辅存,层次的实现：主要借助于辅助软硬件。
存储层次
CPU对第二级的访问方式比较项目目 的存储管理实现访问速度的比值
(第一级和第二级 )
典型的块 (页 )大小失效时 CPU是否切换
“Cache －主存”层次,主存－辅存”层次为了弥补主存速度的不足 为了弥补主存容量的不足主要由专用硬件实现 主要由软件实现几比一 几百比一几十个字节 几百到几千个字节可直接访问 均通过第一级不切换 切换到其他进程两者的比较 -----“Cache －主存”与“主存－辅存”
层次的区别
5.1.4 存储层次的四个问题当把一个块调入高一层 (靠近 CPU)存储器时，
可以放在哪些位臵上?
(映象规则 )
当所要访问的块在高一层存储器中时，如何找到该块?
(查找算法 )
3,当发生失效时，应替换哪一块？
(替换算法 )
4,当进行写访问时，应进行哪些操作?
(写策略 )
1.
2.
5.2 Cache基本知识
5.2.1 映象规则
1,全相联映象全相联,主存中的任一块可以被放臵到
Cache中的任意一个位臵。
特点,空间利用率最高，冲突概率最低，
实现最复杂。
实际,Cache常包含几百个块，主存常包含几百万个块。
2,直接映象：
◆ 直接映象,主存中的每一块只能被放臵到
Cache中唯一的一个位臵。
◆ 特点,空间利用率最低，冲突概率最高，实现最简单。
例如,对于主存的第 i 块，若它映象到 Cache的第 j 块，则,
j＝ i mod (M ) （ M 为 Cache的块数）
(循环分配 )
◆ 组相联,主存中的每一块可以被放臵到 Cache
中唯一的一个组中的任何一个位臵。
◆ 设 M＝ 2m，则当表示为二进制数时,j 实际上就是 i 的低 m 位：
3,组相联映象：
m位
ji：
组相联是直接映象和全相联的一种折衷
◆ 上述的 j 和 k 通常称为索引
◆ 组的选择常采用位选择算法若主存第 i 块映象到第 k 组，则,
k＝ i mod（ G） （ G为 Cache的组数）
设 G＝ 2g，则当表示为二进制数时,k 实际上就是 i 的低 g 位：
g 位
k主存块地址 i：
相联度一定是越大越好？
◆ 绝大多数计算机的 Cache,n ≤4
◆ n 路组相联,每组中有 n 个块 ( n＝ M /G )
n 称为相联度。
相联度越高,Cache空间的利用率就越高，
块冲突概率就越低，失效率也就越低。
全相联直接映象组相联
n (路数 ) G (组数 )
M
M1
1
1＜ n＜ M 1＜ G＜ M
5.2.2 查找方法
1,如何确定 Cache中是否有所要访问的块？
若有的话如何确定其位臵？
◆ 目录表的结构
◆ 查找范围：候选位臵所对应的目录表项
◆ 并行查找与顺序查找提高性能的 重要思想,主候选位臵 (MRU块 )
◆ 并行查找的实现方法：
▲ 相联存储器
▲ 单体多字存储器＋比较器举例,４路组相联并行标识比较
◆ 直接映象 Cache的查找过程
◆ ４路相联 Cache的查找过程
5.2.3 替换算法所要解决的问题：当新调入一块，而 Cache
又已被占满时，替换哪一块？
2,FIFO
3,LRU
优点,失效率低
1,随机法优点,实现简单
LRU和随机法的失效率的比较
5.2.4 写策略
1.,写,操作所占的比例
Load指令,26％
Store指令,9％
,写,在所有访存操作中所占的比例：
9％ /(100％＋ 26％＋ 9％ )≈ 7％
,写,在访问数据 Cache操作中所占的比例：
9％ /(26％＋ 9％ )≈ 25％
3．,写,访问有可能导致 Cache和主存内容的不一致
2.,写,操作必须在确认是命中后才可进行
4．两种写策略
◆ 写直达法执行,写,操作时，不仅写入 Cache，而且也写入下一级存储器。
◆ 写回法执行,写,操作时，只写入 Cache。仅当
Cache中相应的块被替换时，才写回主存。
(设臵,污染位,)
5．两种写策略的比较
◆ 写回法的优点,速度快，所使用的存储器频带较低；
◆ 写直达法的优点,易于实现，一致性好。
6,写缓冲器
8,写策略与调块写回法 ── 按写分配写直达法 ── 不按写分配
7.,写,操作时的调块
◆ 按写分配 (写时取 )
写失效时，先把所写单元所在的块调入
Cache，再行写入。
◆ 不按写分配 (绕写法 )
写失效时，直接写入下一级存储器而不调块。
5.2.5 Cache举例例子,DEC的 Alpha AXP21064中的内部数据
Cache。
1,简介容量,8KB
块大小,32B
块数,256
调块,不按写分配映象方法,直接映象
,写,策略,写直达写缓冲器大小,4个块
2,结构图
3,失效情况下的操作读失效,Cache向 CPU发出一个暂停信号,通知它等待，并从下一级存储器中读如 32个字节，
填入对应的 Cache块。
写失效,CPU不对 Cache进行操作。
4,写缓冲的结构写合并,当把数据写入写缓冲器时，判断本次所写入单元的块地址是否与写缓冲器中某个有效块的地址相同，若是，则把新数据与该块合并。
5,混合 Cache与分离 Cache
访存操作,指令访问 (读指令 )
数据访问 (读写数据 )
分离 Cache,指令 Cache + 数据 Cache
混合 Cache,单一的 Cache
优缺点,(1)实现成本
(2)结构冲突
16 KB
容 量
1 KB
2 KB
4 KB
8 KB
32 KB
指令 Cache
3.06%
失 效 率 的 比 较
64 KB
128 KB
数据 Cache 混合 Cache
2.26%
1.78%
1.10%
0.64%
0.39%
0.15%
0.02%
24.61%
20.57%
15.94%
10.19%
6.47%
4.82%
3.77%
2.88%
13.34%
9.78%
7.24%
4.57%
2.87%
1.99%
1.36%
0.95%
分离 Cache平均失效率的计算：
访问指令 Cache的百分比 × 指令 Cache的失效率
＋访问数据 Cache的百分比 × 数据 Cache的失效率访问指令 Cache的百分比：
100％ /(100％＋ 26％＋ 9％ )≈75 ％
访问数据 Cache的百分比：
(26％＋ 9％ )/(100％＋ 26％＋ 9％ )≈25 ％
6.分离 Cache与混合 Cache平均失效率的比较前提,指令 Cache容量 +数据 Cache容量
= 混合 Cache容量
5.2.6 性能分析
2,平均访问时间平均访问时间＝命中时间＋失效率 × 失效开销例 5.1
假设 Cache的命中时间为 1个时钟周期，失效开销为 50 个时钟周期，在混合 Cache中一次 load
或 store操作访问 Cache的命中时间都要增加一个时钟周期 (因为混合 Cache只有一个端口，无法同时满足两个请求。按照前一章中有关流水线的术语，混合 Cache会导致结构冲突 )，根据 表 5－ 4所列的失效率，试问指令 Cache和数据 Cache容量均
1,失效率解：
如前所述，约 75%的访存为取指令。因此，
分离 Cache的总体失效率为：
(75%× 0.64%)＋ (25%× 6.47%)＝ 2.10%
根据 表 5－ 4，容量为 32KB的混合 Cache的失效率略低一些，只有 1.99%.
为 16KB的分离 Cache和容量为 32KB的混合 Cache相比，哪种 Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？
平均访存时间公式可以分为指令访问和数据访问两部分：
平均访存时间＝ 指令所占的百分比 ×
(指令命中时间＋指令失效率 × 失效开销 )＋
数据所占的百分比 ×
(数据命中时间＋数据失效率 × 失效开销 )
所以根据 表 5－ 4，两种结构的平均访存时间分别为：
平均访存时间 分离 ＝ 75%× (1＋ 0.64%× 50)＋
25%× (1＋ 6.47%× 50)
＝ (75%× 1.32)＋ (25%× 4.325)
＝ 0.990＋ 1.059＝ 2.05
平均访存时间 混合 ＝ 75%× (1＋ 1.99%× 50)＋
25%× (1＋ 1＋ 1.99%× 50)
＝ (75%× 1.995)＋ (25%× 2.995)
＝ 1.496＋ 0.749＝ 2.24
3,程序执行时间在考虑存储器对系统性能影响时，可以将系统性能描述为：
CPU时间＝ (CPU执行周期数＋存储器停顿周期数 )
× 时钟周期时间其中，
存储器停顿周期数＝
,读,的次数 × 读失效率 × 读失效开销
+“写,的次数 × 写失效率 × 写失效开销如果读、写失效率以及读、写失效开销相差不大，
存储器停顿周期数＝ 访存次数 × 失效率 ×
失效开销于是
CPU时间＝ IC× [CPIexe＋访存次数 /指令数 ×
失效率 × 失效开销 ]× 时钟周期时间例 5.2
我们用一个和 Alpha AXP类似的机器作为第一个例子。假设 Cache失效开销为 50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是 2.0个时钟周期,Cache的失效率为 2%，平均每条指令访存 1.33次。试分析
Cache对性能的影响。
考虑 Cache的失效后，性能为：
CPU 时间 有 cache＝ IC× (2.0＋ (1.33× 2%× 50))
× 时钟周期时间
＝ IC× 3.33× 时钟周期时间解：
实际 CPI,3.33
3.33/2.0 = 1.67(倍 )
CPU时间增加为原来的 1.67倍。但若不采用
Cache,则：
CPI＝ 2.0+50× 1.33＝ 68.5
例 5.3
考虑两种不同组织结构的 Cache:直接映象 Cache和两路组相联 Cache，试问它们对 CPU的性能有何影响？分析时用以下假设：
(1)理想 Cache(命中率为 100%)情况下 CPI为 2.0，时钟周期为 2ns，平均每条指令访存 1.3次。
(2)两种 Cache的容量均为 64KB,块大小 32字节
(3)对于组相联 Cache,CPU的时钟周期增加到原来的
1.1倍
(4)失效开销都是 70ns
(5)命中时间为 1个时钟周期,64KB直接映象 Cache的失效率为 1.4%,64KB两路组相联 Cache的失效率为 1.0%
解：
平均访存时间 =命中时间 +失效率 × 失效开销平均访存时间 直接 =2.0+(0.014× 70)=2.98ns
平均访存时间 组相联 =2.0× 1.10 +(0.010× 70)
=2.90ns
CPU时间＝ IC× [CPIexe＋访存次数 /指令数 ×
失效率 × 失效开销 ]× 时钟周期时间
＝ IC× [CPIexe× 时钟周期时间
＋访存次数 /指令数 × 失效率 × 失效开销
× 时钟周期时间 ]
CPU时间 直接 =IC× (2.0× 2+(1.3× 0.014× 70))
=5.27× IC
CPU时间 组相联 =IC× (2.0× 2× 1.10 +(1.3× 0.010× 70))
=5.31× IC
平均访存时间＝命中时间＋失效率 × 失效开销可以从三个方面改进 Cache的性能：
(1) 降低失效率
(2) 减少失效开销
(3) 减少 Cache命中时间下面介绍 15种 Cache优化技术
5.2.7 改进 Cache性能
(1) 强制性失效 (Compulsory miss)
当第一次访问一个块时，该块不在
Cache中，需从下一级存储器中调入 Cache，
这就是 强制性失效。
(冷启动失效，首次访问失效。 )
(2) 容量失效 (Capacity miss )
如果程序执行时所需的块不能全部调入 Cache中，则当某些块被替换后，若又
5.3 降低 Cache失效率的方法
1,三种失效 (3C)
重新被访问，就会发生失效。这种失效称为 容量失效。
(3) 冲突失效 (Conflict miss)
在组相联或直接映象 Cache中，若太多的块映象到同一组 (块 )中，则会出现该组中某个块被别的块替换 (即使别的组或块有空闲位臵 )，然后又被重新访问的情况。这就是发生了 冲突失效。
(碰撞失效，干扰失效 )
2,三种失效所占的比例
(SPEC92)
可以看出：
(1) 相联度越高，冲突失效就越少；
(2) 强制性失效和容量失效不受相联度的影响；
(3) 强制性失效不受 Cache容量的影响，但容量失效却随着容量的增加而减少；
(4) 表中的数据符合 2:1的 Cache经验规则，即大小为 N 的直接映象 Cache的失效率约等于大小为 N/2 的两路组相联 Cache的失效率。
强制性失效,增加块大小，预取
(本身很少 )
容量失效,增加容量
(抖动现象 )
冲突失效,提高相联度
(理想情况：全相联 )
3,减少三种失效的方法
4,许多降低失效率的方法会增加命中时间或失效开销
5.3.1 增加 Cache块大小
2,增加块大小会增加失效开销
1,失效率与块大小的关系
(1) 对于给定的 Cache容量，当块大小增加失效率开始是下降，后来反而上升了；
(2) Cache容量越大，使失效率达到最低的块大小就越大。
3,例题例 5.4
假定存储系统在延迟 40个时钟周期后，每 2个时钟周期能送出 16个字节。即,经过 42个时钟周期，
它可提供 16个字节；经过 44个时钟周期，可提供 32
个字节；依此类推。试问对于 表 5-6中列出的各种容量的 Cache，在块大小分别为多少时，平均访存时间最小？
解,
平均访存时间为：
平均访存时间 ＝ 命中时间＋失效率 × 失效开销假设命中时间与块大小无关，为 1个时钟，那么对于一个块大小为 16字节，容量为 1KB的 Cache来说：
平均访存时间 ＝ 1＋（ 15.05 %× 42）
＝ 7.321 个时钟周期而对于块大小为 256B的大小为 256KB的 Cache来说，
平均访存时间为：
平均访存时间 ＝ 1＋（ 0.49 %× 72）
＝ 1.353 个时钟周期表 5.7列出了在这两种极端情况之间的各种块大小和各种 Cache容量的平均访存时间。
块大小
（字节
）
失效开销
（时钟周期）
Cache容量（字节）
1K 4K 16K 64K 256K
16 42 7.321 4.599 2.655 1.857 1.458
32 44 6.870 4.186 2.263 1.594 1.308
64 48 7.605 4.360 2.267 1.509 1.245
128 56 10.318 5.357 2.551 1.571 1.274
256 72 16.847 7.847 3.369 1.828 1.353
5.3.2 提高相联度
1,采用相联度超过 8的方法实际意义不大
2,2:1 Cache经验规则容量为 N 的直接映象
Cache≈ 容量为 N/2的两路组相联 Cache
3,提高相联度是以增加命中时间为代价例如：
TTL或 ECL板级 Cache，两路组相联：
增加 10％
定制的 CMOS Cache,两路组相联：
增加 2％
4,例题假定提高相联度会按下列比例增大处理器时钟周期：
时钟周期 2路 ＝ 1.10× 时钟周期 1路时钟周期 4路 ＝ 1.12× 时钟周期 1路时钟周期 8路 ＝ 1.14× 时钟周期 1路假定命中时间为 1个时钟，失效开销为 50个时钟周期，而且假设不必将失效开销取整。使用表 5－ 5中的失效率，试问当 Cache为多大时，以下不等式成立？
例 5.5
平均访存时间 8路 < 平均访存时间 4路平均访存时间 4路 < 平均访存时间 2路平均访存时间 2路 < 平均访存时间 1路解,
在各种相联度的情况下，平均访存时间分别为：
平均访存时间 8路 = 命中时间 8路 + 失效率 8路
× 失效开销 8路
= 1.14＋失效率 8路 × 50
平均访存时间 4路 = 1.12 ＋失效率 4路 × 50
平均访存时间 2路 = 1.10 ＋失效率 2路 × 50
平均访存时间 1路 = 1.00 ＋失效率 1路 × 50
在每种情况下的失效开销相同，都是
50个时钟周期。把相应的失效率代入上式，
即可得平均访存时间。
例如,1KB的直接映象 Cache的平均访存时间为：
平均访存时间 1路 ＝ 1.00＋ (0.133× 50)
＝ 7.65
容量为 128KB的 8路组相联 Cache的平均访存时间为：
平均访存时间 8路 ＝ 1.14＋ (0.006× 50)
＝ 1.44
表 5-8
Cache容量
（ K字节）
相联度（路）
1 2 4 8
1 7.65 6.60 6.22 5.44
2 5.90 4.90 4.62 4.09
4 4.60 3.95 3.57 3.19
8 3.30 3.00 2.87 2.59
16 2.45 2.20 2.12 2.04
32 2.00 1.80 1.77 1.79
64 1.70 1.60 1.57 1.59
128 1.50 1.45 1.42 1.44
1,基本思想在 Cache和它从下一级存储器调数据的通路之间设臵一个全相联的小 Cache，
用于存放被替换出去的块 (称为 Victim)，
以备重用。
工作过程
5.3.3 Victim Cache
对于减小冲突失效很有效，特别是对于小容量的直接映象数据 Cache，作用尤其明显。
例如，项数为 4的 Victim Cache:
使 4KB Cache的冲突失效减少 20%～ 90%
2,作用
1,直接映象 vs．组相联
5.3.4 伪相联 Cache(列相联 )
2,伪相联 Cache
优 点 缺 点直接映象组相联命中时间小命中时间大失效率高失效率低取直接映象及组相联两者的优点：
命中时间小，失效率低
(1) 基本思想及工作原理在逻辑上把直接映象 Cache的空间上下平分为两个区。对于任何一次访问，伪相联
Cache先按直接映象 Cache的方式去处理。若命中，则其访问过程与直接映象 Cache的情况一样。若不命中，则再到另一区相应的位臵去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。
(2) 快速命中与慢速命中要保证绝大多数命中都是快速命中。
3,例题例 5.6
假设当在按直接映象找到的位臵处没有发现匹配、而在另一个位臵才找到数据 (伪命中 )
需要 2个额外的周期。仍用上个例子中的数据，
问,当 Cache容量分别为 2KB和 128KB时，直接映象、两路组相联和伪相联这三种组织结构中，
哪一种速度最快？
首先考虑标准的平均访存时间公式：
平均访存时间 伪相联
＝命中时间 伪相联 ＋失效率 伪相联 × 失效开销 伪相联由于：
失效率 伪相联 ＝失效率 2路命中时间 伪相联 ＝命中时间 1路 ＋伪命中率 伪相联 × 2；
伪命中率 伪相联 ＝命中率 2路 －命中率 1路
＝ (1－失效率 2路 )－ (1－失效率 1路 )
＝失效率 1路 －失效率 2路解：
故：
平均访存时间 伪相联
＝命中时间 1路 ＋ (失效率 1路 －失效率 2路 )× 2
＋失效率 2路 × 失效开销 1路将表 5－ 5中的数据代入上面的公式，得：
平均访存时间 伪相联,2KB
＝ 1＋ (0.098－ 0.076)× 2＋ (0.076× 50)
＝ 4.844
平均访存时间 伪相联,128KB
＝ 1＋ (0.010－ 0.007)× 2＋ (0.007× 50)
＝ 1.356
根据上一个例子中的表 5－ 8，对于 2KB Cache，
可得：
平均访存时间 1路 ＝ 5.90 个时钟平均访存时间 2路 ＝ 4.90 个时钟对于 128KB的 Cache有，可得：
平均访存时间 1路 ＝ 1.50 个时钟平均访存时间 2路 ＝ 1.45 个时钟可见，对于这两种 Cache容量，伪相联 Cache
都是速度最快的。
缺点,多种命中时间
5.3.5 硬件预取技术依据,空间局部性思想,在 Cache访问失效时，不但从内存中取入对应的块，而且将它的邻近块 (通常为后继块 )取入一个速度快于主存的缓冲器中，这样当对后继块的访问发生时，可通过访问该缓冲器进行块替换。
1,指令和数据都可以预取
2,预取内容既可放入 Cache，也可放在外缓冲器 (速度快于主存 )中例如：指令流缓冲器
3,预取效果
(1) Jouppi的研究结果
◆ 指令预取,(4KB，直接映象 Cache,
块大小＝ 16字节 )
1个块的指令流缓冲器,捕获 15％～ 25％
的失效
4个块的指令流缓冲器,捕获 50％
16个块的指令流缓冲器,捕获 72％
◆ 数据预取,(4KB,直接映象 Cache)
1个数据流缓冲器,捕获 25％的失效还可以采用多个数据流缓冲器
(2) Palacharla和 Kessler的研究结果流缓冲器,既能预取指令又能预取数据对于两个 64KB四路组相联 Cache来说：
8个流缓冲器能 捕获 50％～ 70％的失效。
4,例题例 5.7
Alpha AXP 21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术,Alpha
APX 21064的指令 Cache必须为多大才能保持平均访存时间不变？
解：
假设从预取缓冲器中找到所需指令 (并进行替换 )需多花 1个时钟周期。
平均访存时间 预取
＝命中时间＋失效率 × 预取命中率 × 1
＋失效率 × (1－预取命中率 )× 失效开销假设：
预取命中率＝ 25％
命中时间＝ 1 个时钟周期失效开销＝ 50个时钟周期由 表 5－ 4可知,8KB指令 Cache的失效率＝ 1.10％
故平均访存时间 预取 ＝ 1＋ (1.10 %× 25 %× 1)＋
(1.10 %× (1－ 25 %)× 50)
＝ 1＋ 0.00275＋ 0.4125
＝ 1.415
由公式：
平均访问时间＝命中时间＋失效率 × 失效开销可得相应的失效率为：
失效率＝ (平均访问时间－命中时间 )/失效开销
＝ (1.451－ 1)/50＝ 0.83％
8KB Cache 带预取的8kB Cache
失效率 1.10％ 0.83％
16KB Cache
0.64％
关键：预取应建立在存储器的空闲频带
5.3.6 由编译器控制的预取
1,预取的类型
◆ 寄存器预取,把数据取到寄存器中
◆ Cache预取,只将数据取到 Cache中
◆ 故障性预取,预取时，若出现虚地址故障或违反访问权限，就会发生异常。
◆ 非故障性预取,预取时，若出现虚地址故障或违反访问权限，并不会导致异常，只是转变为,不预取,。
由编译器加入预取指令，在数据被用到之前发出预取请求。
4,例题
2,在预取数据的同时，处理器应能继续执行只有这样，预取才有意义。
非阻塞 Cache (非锁定 Cache)
3,循环是预取优化的主要对象失效开销小时,循环体展开 1～ 2次失效开销大时,循环体展开许多次例 5.8
对于下面的程序，判断哪些访问可能会导致数据 Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：
(1) 我们用的是一个容量为 8KB、块大小为
16B的直接映象 Cache，它采用写回法并且按写分配。
(2) a,b分别为 3× 100(3行 100列 )和 101× 3
的双精度浮点数组，每个元素都是 8个字节。当程序开始执行时，这些数据都不在 Cache内。
for (i＝ 0 ; i < 3 ; i＝ i＋ 1 )
for (j＝ 0 ; j < 100 ; j＝ j＋ 1 )
a[i][j]＝ b[j][0]× b[j＋ 1][0];
解：
(1) 计算过程
(2) 失效情况 数组 a 数组 b
总的失效次数＝ 251次
(3) 改进后的程序 (设预取的开销比较大，需提前 7 次循环进行 )
for (j＝ 0,j＜ 100； j＝ j＋ 1) {
prefetch (b[j＋ 7][0]);
/* 预取 7次循环后所需的 b(j,0 ) */
prefetch (a[0][j＋ 7]);
/* 预取 7次循环后所需的 a(0,j ) */
a[0][j]＝ b[j ][0] * b [j＋ 1][0]
}
for (i＝ 1; i < 3; i＝ i＋ 1) {
for (j＝ 0; j < 100; j＝ j＋ 1)
prefetch(a[i][j＋ 7]);
/* 预取 7次循环后所需的 a(i,j ) */
a[i][j]＝ b[j][0] * b[j＋ 1][0];
}
例 5,9
在以下条件下，计算例 5.8中所节约的时间：
(1) 忽略指令 Cache失效，并假设数据 Cache
无冲突失效和容量失效。
(2) 假设预取可以被重叠或与 Cache失效重叠执行，从而能以最大的存储带宽传送数据。
(3) 不考虑 Cache失效时，修改前的循环每 7
个时钟周期循环一次。修改后的程序中，
失效情况总的失效次数＝ (7+4)+4+4=19次解：
修改前：
循环时间 ＝ 300× 7 ＝ 2100
总失效开销＝ 251× 50＝ 12550
总运行时间＝ 2100＋ 12550＝ 14650
第一个预取循环每 9个时钟周期循环一次，
而第二个预取循环每 8个时钟周期循环一次 (包括外层 for循环的开销 )。
(4) 一次失效需 50个时钟周期。
修改后：
循环时间＝ 100× 9＋ 200× 8＝ 2500
总失效时间＝ 19× 50＝ 950
总运行时间＝ 2500＋ 950＝ 3450
加速比＝ 14650/3450＝ 4.2
5.3.7 编译器优化
2KB Cache,降低 50％
8KB Cache,降低 75%
1,基本思想在编译时，对程序中的指令和数据进行重新组织，以降低 Cache失效率。
2,McFaring 发现：通过对指令进行重新排序，
可有效地降低指令 Cache的失效率。
3,数据对存储位臵的限制比指令的少，因此更便于优化。
通过把数据重新组织，使得在一块数据被从 Cache替换出去之前，能最大限度利用其中的数据 (访问次数最多 )
(1) 数据合并举例：
/* 修改前 */
int val [SIZE];
int key [SIZE];
(2) 内外循环交换举例：
/* 修改前 */
for (j＝ 0 ;j<100 ;j＝ j＋ 1)
for (i＝ 0 ;i<5000 ;i＝ i＋ 1)
x[i][j]＝ 2*x[i][j];
/* 修改后 */
struct merge {
int val ;
int key ;
} ;
struct merge merged_array[size];
(3) 循环融合举例：
/* 修改前 */
for (i＝ 0 ; i<N ;i＝ i＋ 1)
for (j＝ 0 ; j<N ; j＝ j＋ 1)
a[i][j]＝ 1/b[i][j]*c[i][j];
/* 修改后 */
for (i＝ 0 ;i<100 ;i＝ i＋ 1)
for (j＝ 0 ;j< 000 ;j＝ j＋ 1)
x[i][j]＝ 2*x[i][j];
/* 修改后 */
for (i＝ 0 ;i < N ;i＝ i＋ 1)
for (j＝ 0 ;j < N ;j＝ j＋ 1) {
a[i][j]＝ 1/b[i][j]*c[i][j];
d[i][j]＝ a[i][j]＋ c[i][j];
}
for (i＝ 0 ;i<N ;i＝ i＋ 1)
for (j＝ 0 ; j<N ;j＝ j＋ 1)
d[i][j]＝ a[i][j]＋ c[i][j];
(4)分块把对数组的整行或整列访问改为按块进行。
举例：
/* 修改前 */
for (i＝ 0; i < N; i＝ i＋ 1)
for (j＝ 0; j < N; j＝ j＋ 1) {
r＝ 0;
for (k＝ 0; k < N; k＝ k＋ 1) {
r＝ r＋ y[i][k]*z[k][j];
}
x[i][j]＝ r;
}
计算过程最坏情况下失效次数,2N3＋ N2
/* 修改后 */
for (jj＝ 0; jj < N; jj＝ jj＋ B)
for (kk＝ 0; kk < N; kk＝ kk＋ B)
for (i＝ 0; i < N; i＝ i＋ 1)
for (j＝ jj; j < min(jj＋ B－ 1,N); j＝ j＋ 1) {
r＝ 0;
for (k＝ kk; k < min(kk＋ B－ 1,N); k＝ k＋ 1) {
r＝ r＋ y[i][k]*z[k][j];
}
x[i][j]＝ x[i][j]＋ r;
}
失效次数,2N3/B + N2
5.4.1 让读失效优先于写
5.4 减少 Cache失效开销
1,Cache中的写缓冲器导致对存储器访问的复杂化
2,解决问题的方法 (读失效的处理 )
◆ 推迟对读失效的处理
(缺点,读失效的开销增加，如 50％ )
◆ 检查写缓冲器中的内容
3,在写回法 Cache中，也可采用写缓冲器
5.4.2 子块放臵技术
1,为减少标识的位数，可采用增加块大小的方法，但这会增加失效开销,故应采用子块放臵技术。
2,子块放臵技术,把 Cache块进一步划分为更小的块 (子块 )，并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效。
Cache与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位。
3,举例 (图示 )
5.4.3 请求字处理技术
1,请求字从下一级存储器调入 Cache的块中，只有一个字是立即需要的。这个字称为 请求字。
2,应尽早把请求字发送给 CPU
◆ 尽早重启动,调块时，从块的起始位臵开始读起。一旦请求字到达，就立即发送给
CPU，让 CPU继续执行。
◆ 请求字优先,调块时，从请求字所在的位臵读起。这样，第一个读出的字便是请求字。将之立即发送给 CPU。
3,这种技术在以下情况下效果不大：
◆ Cache块较小
◆ 下一条指令正好访问同一 Cache块的另一部分。
5.4.4 非阻塞 Cache技术
1,非阻塞 Cache,Cache失效时仍允许 CPU进行其它的命中访问。即允许,失效下命中,
2,进一步提高性能：,多重失效下命中,,
,失效下失效,
(存储器必须能够处理多个失效 )
3,重叠失效个数对平均访问时间的影响非阻塞 Cache平均存储器等待时间与阻塞 Cache的比值
1 2
浮点程序 76％ 51％
64
39％
整数程序 81％ 78％ 78％
重叠失效个数对于图 5.17所描述的 Cache，在两路组相联和
“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？
假设 8KB数据 Cache的平均失效率为：
对于浮点程序，直接映象 Cache为 11.4%，两路组相联 Cache为 10.7%；
对于整数程序，直接映象 Cache为 7.4%，两路组相联 Cache为 6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为 16个时钟周期。
例 5.10
对于浮点程序，平均存储器等待时间为：
失效率 直接映象 × 失效开销＝ 11.4%× 16＝ 1.82
失效率 两路组相联 × 失效开销＝ 10.7%× 16＝ 1.71
1.71/1.82＝ 0.94
对于整数程序：
失效率 直接映象 × 失效开销＝ 7.4 %× 16＝ 1.18
失效率 两路组相联 × 失效开销＝ 6.0 %× 16 ＝ 0.96
0.96/1.18=0.81
结论,对浮点运算采用,一次失效下命中”措施比采用
,两路组相联,技术更有效,
解：
5.4.5 两级 Cache
1,应把 Cache做得更快？还是更大？
答案：二者兼顾，再增加一级 Cache
◆ 第一级 Cache(L1)小而快
◆ 第二级 Cache(L2)容量大
2,性能分析平均访问时间
＝命中时间 L1＋失效率 L1× 失效开销 L1
＝命中时间 L1＋失效率 L1×
(命中时间 L2＋失效率 L2× 失效开销 L2)
3,局部失效率与全局失效率局部失效率 ＝该级 Cache的失效次数 /到达该级 Cache的访问次数例如：上述式子中的失效率 L2
全局失效率 ＝该级 Cache的失效次数 /CPU
发出的访存的总次数全局失效率 L2＝失效率 L1× 失效率 L2
局部失效率一般不能反映对提高系统实际运行性能所发挥的作用,因此评价第二级 Cache时，一般使用全局失效率这个指标。
4,当第二级 Cache比第一级 Cache大得多时，两级 Cache的全局失效率和第二级 Cache相同的单级 Cache的失效率非常接近。
5,第二级 Cache的参数第二级 Cache不会影响 CPU的时钟频率，
因此其设计有更大的考虑空间。
两个问题：
◆ 能否降低 CPI中的平均访存时间部分？
◆ 成本是多少？
(1) 容量第二级 Cache的容量一般比第一级的大许多，如 512KB
(2) 相联度第二级 Cache可采用较高的相联度或伪相联方法例 5.12
给出有关第二级 Cache的以下数据：
⑴ 两路组相联使命中时间增加 10%× CPU时钟周期
⑵ 对于直接映象，命中时间 L2＝ 10个时钟周期
⑶ 对于直接映象，局部失效率 L2＝ 25%
⑷ 对于两路组相联，局部失效率 L2＝ 20%
⑸ 失效开销 L2＝ 50个时钟周期试问第二级 Cache的相联度对失效开销的影响如何？
解：
对于一个直接映象的第二级 Cache来说，
第一级 Cache的失效开销为：
失效开销 直接映象,L1
＝ 10＋ 25%× 50＝ 22.5个时钟周期对于两路组相联第二级 Cache来说，命中时间增加了 10%(0.1)个时钟周期，故第一级
Cache的失效开销为：
失效开销 两路组相联,L1
＝ 10.1＋ 20%× 50＝ 20.1个时钟周期故对于第二级 Cache来说，两路组相联优于直接映象。
(3) 块大小第二级 Cache可采用较大的块，
如 64,128,256字节。
为减少平均访存时间，可以让容量较小一的第一级 Cache采用较小的块，而让容量较大的第二级 Cache采用较大的块。
5.5 减少命中时间
2,应使 Cache足够小，以便可以与 CPU一起放在同一块芯片上。
命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是 Cache的访问时间限制了处理器的时钟频率。
1,硬件越简单，速度就越快；
5.5.1 容量小、结构简单的 Cache
1,虚拟 Cache
访问 Cache的索引以及 Cache中的标识都是虚拟地址 (一部分 )。
2,并非人人都采用虚拟 Cache
原因一：不同进程虚地址空间的相同。
3,解决方法：
(1)进程切换时清空虚拟 Cache。
(2)在地址标识中增加 PID字段 (进程标识符 )。
三种情况下失效率的比较：
单进程,PIDs，清空
PIDs与单进程相比,＋ 0.3％～＋ 0.6％
PIDs与清空相比,－ 0.6％～－ 4.3%
5.5.2 虚拟 Cache
4.原因二,同义和别名 (不同虚地址对应相同实地址情况 )
解决方法：
(1)反别名法 ——用硬件来保证每一个 Cache块对应唯一实地址。
(2)页着色 ——Sun公司的 UNIX系统要求所有有别名的地址最后 18位相同，而直接映象 Cache
的索引来自于这最后 18位 (Cache容量不超过 218
字节 )，这使得所有别名映象到同一 Cache块位臵。
5,根据页内位移 (这部分虚实地址相同 )进行
Cache索引 (同时进行虚实地址转换 )，用实地址判断是否命中。
优点,兼得虚拟 Cache和物理 Cache的好处
( Cache索引和虚实地址转换同时进行 )
局限性,Cache容量受到限制直接映象,Cache容量 ≤ 页大小组相联映象,Cache容量 ≤ 页大小 × 相联度
5.5.3 将写操作流水化以加快写命中读写命中一般包含两步：
(1)判断是否命中。
(2)(如果命中 )对 Cache进行读写。
对读操作：两步可并行进行。
对写操作：两步必须串行进行。
解决方法,将写操作的两步操作流水化,
优化技术 失效率失效开销命中时间硬件复杂度评价增加块大小 + - 0 实现容易； RS/6000 550采用了
128字节提高相联度 + - 1 MIPS R10000为 4路组相联
Victim Cache + 2 HP7200中采用了类似的技术伪相联 Cache + 2 已应用于 MIPS R10000的第二级 Cache
硬件预取指令和数据
+ 2 数据预取比较困难；仅被几台机器采用,如,Alpha 21064
编译器控制的预取 + 3 需采用非阻塞 cache；有几种机器支持它用 编 译 技 术 减 少
Cache失效次数
0 向软件提出了新要求；有些机器提供了编译器选项
+
使读失效优先级高于写
+ 1 在单处理机上实现容易,被广泛使用子块调入 + 1 主要用于减少标识的数目尽早重启动和关键字优先
+ 2 已 应 用 于 MIPS R10000 和
IBM 620
非阻塞 Cache + 3 已应用于 Alpha 21064 和
R10000中第二级 Cache + 2 硬件代价大；两级 Cache的块大小不同时实现困难；被广泛采用容量小且结构简单的 Cache
- + 0 实现容易,被广泛使用避免在对 Cache进行索引时进行地址转换
+ 2 对于小容量 Cache来说实现容易,已应用于 Alpha 21064
流水化写 + 1 已应用于 Alpha 21064
5.6.1 存储器技术
1,主存的主要性能指标,延迟和带宽
2,以往：
Cache主要关心延迟,I/O主要关心带宽
3,现在,Cache关心两者 (由于二级 Cache使用较大的块 )
5.6 主 存
1,存储器延迟：访问时间，存储周期
2,地址线复用：行选通和列选通
3,DRAM与 SRAM
容量,4～ 8,1
存储周期,8～ 16:1
价格,1,8～ 16
一般来说：
主存,DRAM Cache,SRAM
4,Amdahl经验规则为了保持系统平衡，存储容量和性能应随 CPU速度的提高而线性增加。
5,各代 DRAM的典型时间参数,
年 份 芯片容量行选通 (RAS)
最慢的 DRAM 最快的 DRAM
列 选 通
(CAS) 周期时间
1980
1983
1986
1989
1992
1995
64K 位
256K 位
1M 位
4M 位
16M 位
64M 位
180ns
150ns
120ns
100ns
80ns
65ns
150ns
120ns
100ns
80ns
60ns
50ns
75ns
50ns
25ns
20ns
15ns
10ns
250ns
220ns
190ns
165ns
120ns
90ns
表 5-10 各代 DRAM 的典型时间参数
5.6.2 提高主存性能的存储器组织结构
1,增加存储器的宽度
2,采用简单的多体交叉存储器
3,独立存储体
◆ 设臵多个存储控制器，使多个体能独立操作，
以便能同时进行 多个独立的访存 。
◆ 每个体有独立的地址线
◆ 非阻塞 Cache与多体结构
◆ 超体,多体交叉存储器 + 独立存储体独立存储体 独立存储体 独立存储体 独立存储体存 储 器 系 统
4,避免存储体冲突
◆ 体冲突,两个请求要访问同一个体
◆ 减少冲突,采用许多体例如,NEC SX/3最多 128个体问题仍旧存在：
例：
int x[256][512];
for (j=0;j<512;j++)
for (i=0;i<256;i++)
x[i][j]=2*x[i][j]
◆ 解决体冲突的方法：
▲ 软件方法 (编译器 )
1.循环交换优化例：
int x[256][512];
for (i=0;i<256;i++)
for (j=0;j<512;j++)
x[i][j]=2*x[i][j]
2.扩展数组的大小，使之不是 2的幂。
▲ 硬件方法使体数为 素数 以减少体冲突机会 。
一般取：
体号 =地址 mod 体数体内地址 =地址 / 体数当存储体数为素数，且为 2的幂减 1时，取体号 =地址 mod 体数体内地址＝地址 mod 存储体中的字数 (可以直接载取 )
根据中国剩余定理，可有以下一一对应：
地址 (体号，体内地址 )
◆ 举例体 内 地 址存 储 体顺 序 交 叉 取 模 交 叉
0
1
2
3
4
5
表 5-11 顺序交叉和取模交叉的地址映象举例
6
7
0 1 2 0 1 2
0 1 2 0 16 8
3 4 5
6 7 8
9 10 11
12 13 14
21 22 23
15 16 17
18 19 20
9 1 17
18 10 2
3 19 11
12 4 20
21 13 5
6 22 14
15 7 23
5,DRAM专用交叉结构
◆ 三种方式
▲ Nibble方式每次访问时，除给出所需位外，还能给出其后 3位。
▲ Page方式行选通 (RAS)后，整个一行内容并行输出到缓冲器，随后可以 SRAM速度随几访问其中的任意一位。
▲ Static column方式与 Page方式类似，只是在列地址改变时，数据线内容跟随变化而无需触发列访问选通线。
◆ RAMBUS
用总线方式取代 RAS/CAS
能自己完成刷新
能在一次访存期间 (发送地址到返回数据 )通过总线接受另一次访存请求
数据宽度一个字节
最高 2ns传送一个字节。
5.7 虚拟存储器
提出于 1961年
解决应用程序对主存容量的越来越高要求以及主存难以满足这一问题,
从程序覆盖技术发展而来
1,基本想法
外存作为基本存储器,存放执行中的程序和数据
为每个进程分配一个独立的逻辑空间 (虚拟空间 ),在这个空间中每条指令和数据都分配一个逻辑地址 (虚拟地址 )
5.7.1 虚拟存储器基本原理
指令与指令、指令与数据的访问关系用逻辑地址来表达
指令和数据在被访问到时被调入内存,相应的从逻辑地址到物理地址 (主存地址 )的映射被建立，然后按照这种映射关系在指令运行时把逻辑地址转化成物理地址，实现实际的访问。
2,虚拟存储器的特点
◆ 多个进程可以共享主存空间
◆ 程序员不必做存储管理工作
◆ 采用动态再定位，简化了程序的装入
3,虚拟存储器的分类按照空间管理单位
◆ 页式把空间分成大小相同的块 (4KB? 64KB)，称为页面
◆ 段式把空间分成可变长的块，称为段，段的大小可根据程序的逻辑意义来确定，一般是程序模块。
页 式 段 式地址大小 ( 字 ) 1 2 ( 段号和段内位移 )
对程序员是否透明 透明 可能透明替换一个块 容易 ( 所有块大小相同 ) 困难 ( 必须找到能容纳该段的空闲主存块 )
存储空间浪费 内部碎片 ( 页内未使用部分 ) 外部碎片 ( 主存中的无用块 )
磁盘传送效率 高 ( 可根据磁盘传送效率选择合适的页面大小 )
不一定 ( 比较小的段可能只有几个字节 )
4,有关虚拟存储器的四个问题
◆ 映象规则全相联 (失效开销太大 )
◆ 查找算法页表，段表虚页号 页内位移页表物理页号 页内位移虚拟地址物理地址页表每一项对应一个虚页号每一项一般有这样一些域
(1)该页是否已在主存中
(2)该页在主存中的起始地址 (物理页号 )
(3)其他信息 (如保护信息等 )
页表通常非常大
◆ 替换算法
LRU
主存的每个页面设臵一个使用位
◆ 写策略写回法 (磁盘不支持单个字的写 )
为了减少写操作通常使用,脏,位方法来保证只有被修改的页才被写回。
5.7.2 快表 TLB
页表一般比较大，存放在主存中。为了加快页表访问，通常设臵一个类似于 Cache的高速缓冲器，称为快表 (TLB)
◆ TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项 ;
◆ TLB中的内容是页表部分内容的一个副本，为了保持一致性，当修改页表某一项时，操作系统须清除
TLB中对应项 ;
◆ TLB也利用了局部性原理 ;
◆ TLB一般比 Cache的标识存储器更小、更快
5.7.3 页面大小的选择
1,大页面和小页面各有优点如何进行权衡?
2,大页面的好处：
◆ 页表的大小与页面大小成反比。较大的页面可以节省实现地址映象所需的存储空间及其它资源；
◆ 较大的页面可以使快速 Cache命中的实现更简单 (5.5节 )；
◆ 在主存和辅存之间 (也许还通过网络 )传送较大的页面比传送较小的页面更有效；
◆ TLB的项数有限，对于给定数目的项数，
较大的页面意味着可以高效地实现更多存储空间的地址变换，从而减小 TLB失效的次数。
3,采用较小的页面可以减少空间的浪费假设每个进程有三个主要的段：
代码，堆，堆栈,
则 平均浪费 1.5个页面。
当今计算机大部分都支持多道程序运行：
多个进程 (运行中的程序 )既能同时在独立的环境中运行又能共享系统资源。
典型例子：多用户分时系统 -----每个用户的进程既能共享资源 (如 CPU、内存、系统软件等 )又能彼此相互不影响的独立运行。
进程的保护问题,进程的正确运行不受其他进程运行状况的影响。
保护的手段,主要是对存储区域的保护，使一个进程的信息不被另一个进程错误地修改。
5.8 进程保护和虚存实例保护的形式,有一定的多样性，有时需要允许进程间有共享数据区域以进行数据通信。
5.8.1 进程保护
1,界地址寄存器方法 (最简单的方法 )
一对寄存器,基地址，上界地址检测条件,(基地址＋地址 )≤ 上界地址不适合虚拟存储器系统 ---进程的访问空间不是一个连续空间。
2,映象表方法 (适用于虚存系统 )
a) 形式 1,每个进程有一个独立页表，进程不能访问页表上找不到的主存页面。
存在问题,不能实现共享数据区域
b) 形式 2,将进程的地址空间分成系统区域和用户区域，系统区域为各进程共享，只用一个页表，
而用户区域各进程使用各自的页表。
存在问题,不能实现复杂的权限控制
c) 形式 3,在页表中给每个页面设臵许可信息，如只读、只可运行、只可由系统程序访问等。
许可信息的形式,
(1)键保护方式：操作系统给每个页面分配一个存储键 (锁 )，每个进程分配一个访问键 (钥匙 )，以控制其访问关系。
(2)环式保护方式：将系统程序和用户程序按访问权限分层，如核心层、系统层、操作系统扩展层、
应用层等，每个内存页面也有一个层号，对某一个进程，它只能访问同层或外层的页面硬件方面的支持至少包括：
(1)提供两种以上的状态，分别表示当前运行的进程是用户进程还是系统进程。
(2)提供一些 CPU状态，用户进程可读不可修改。
(3)提供一种在用户状态和系统状态转换的机制。
5.8.2 页式虚存举例,Alpha Axp
Alpha Axp体系结构采用 段页相结合 的方式。
1,Alpha的地址空间分为 3段：
kseg(地址最高两位,10) (内核 )
sego(最高位,0) (用户 )
seg1(最高两位,11) (用户 )
sego和 seg1的布局
2,Alpha采用三级页表地址变换过程
3,Alpha的页表项 (PTE)
4,Alpha Axp21064TLB的参数参 数 描 述块 大 小命 中 时 间平均失效开销
TBL 容 量块替换策略写 策 略块映象策略
1 PTE (8字节 )
1 个时钟周期
20 PTE (8字节 )
随 机不适用全相联指令 TLB,8 个 PTE 用于大小为 8K 字节的页，
4个 PTE 用于大小为 4MB 的页 (共 96 个字节 )
数据 TLB,32 个 PTE 用于大小为 8KB,64KB、
512KB 何 4MB 的页 (共 256 个字节 )
表 5-14 Alpha AXP 21064 TLB 的存储层次参数
5.9 Alpha Axp21064存储层次
1,简介
2,工作过程
5.10 小 结
1,本章存储层次实例总结表 5-15
块大小
(字节 )
虚拟存储器TLB 第一级 Cache 第二级 Cache
命中时间
(时钟周期 )
失效开销
(时钟周期 )
失效率 (局部 )
容量 (字节 )
映象算法写策略
4－ 8
(1 个 PTE)
1
10－ 30
第一级 Cache
全相联 /组相联标识 /块
4－ 32
1－ 2
8－ 66
第二级 Cavhe
直接映象标识 /块
32－ 256
6－ 15
30－ 200
页模式 DRAM
直接映象 /组相联标识 /块表 5-15 本章存储层次实例总结
4096－ 16384
10－ 100
700,000－ 6,000,000
磁盘全相联表替换算法查找算法下一级存储器
0.1－ 2% 0.5－ 20% 15－ 30% 0.00001－ 0.001%
32－ 8192
(8－ 1024 个 PTE) 1－ 128K 256K－ 16M 16－ 8192M
随机 无 (直接映象 ) 随机 近似 LRU
写页表时时清空 写直达 /写回法 写回法 写回法
