第五章 存储层次 5.1 存储层次结构 5.2 Cache基本知识 5.3 降低Cache失效率的方法 5.4 减少Cache失效开销

Presentation on theme: "第五章 存储层次 5.1 存储层次结构 5.2 Cache基本知识 5.3 降低Cache失效率的方法 5.4 减少Cache失效开销"— Presentation transcript:

1 第五章 存储层次 5.1 存储层次结构 5.2 Cache基本知识 5.3 降低Cache失效率的方法 5.4 减少Cache失效开销
第五章 存储层次 5.1 存储层次结构 5.2 Cache基本知识 5.3 降低Cache失效率的方法 5.4 减少Cache失效开销 5.5 通过并行操作减少失效开销或失效率 5.6 减少命中时间 5.7 主存 5.8 虚拟存储器－基本原理

2 5.1 存储层次结构 存储系统设计是计算机体系结构设计的关键问题之一 价格，容量，速度的权衡
用户对存储器的“容量，价格和速度”要求是相互矛盾的 速度越快，每位价格就高 容量越大，每位价格就低 容量越大，速度就越慢 目前主存一般由DRAM构成 Microprocessor与Memory之间的性能差异越来越大 CPU性能提高大约60%/year DRAM 性能提高大约 9％/year

3 技术发展趋势 Capacity Speed (latency) Logic: 2x in 3 years 2x in 3 years
DRAM: 4x in 3 years 2x in 10 years Disk: 4x in 3 years 2x in 10 years DRAM Year Size Cycle Time Kb 250 ns Kb 220 ns Mb 190 ns Mb 165 ns Mb 145 ns Mb 120 ns 1000:1! 2:1! Here is a table showing you quantitatively what I mean by high density. In 1980, the biggest DRAM chip you can buy has around 64Kb on it and their cycle time is around 250ns. This year you can buy 64 Mb DRAMs chips, that is an order of magnitude bigger than those back in with a speed that is twice as fast. The general rule for DRAM has been quadruple in size every 3 years. We will talk about DRAM cycle time later today. For now, I want you to point out an important point: The logic speed of your processor is doubling every 3 years but the DRAM speed only gets 40% improvement every 10 years. This mean DRAM speed relative to your processor is getting slower every day. That is why we believe Memory System design will become more and more important in the future because getting to your DRAM will become one of the biggest bottlenecks. +2 = 28 min. (Y:08) (8 Gbi)

4 微处理器与DRAM 的性能差异 Processor-DRAM Memory Gap (latency) Processor-Memory
Performance Gap Growing

5 Microprocessor-DRAM性能差异
利用caches来缓解微处理器与存储器性能上的差异 Microprocessor-DRAM 性能差异 time of a full cache miss in instructions executed 1st Alpha : 340 ns/5.0 ns =  68 clks x 2 or 136 instructions 2nd Alpha : 266 ns/3.3 ns =  80 clks x 4 or 320 instructions 3rd Alpha : 180 ns/1.7 ns =108 clks x 6 or 648 instructions 1st generation Latency 1/2 but Clock rate 3X and IPC is 3X Now move to other 1/2 of industry

6 存储系统的设计目标 通过优化存储系统的组织来使得针对典型应用平均访存时间最短 Processor Workload or Benchmark
programs Processor reference stream <op,addr>, <op,addr>,<op,addr>,<op,addr>, . . . op: i-fetch, read, write Memory 通过优化存储系统的组织来使得针对典型应用平均访存时间最短 $ MEM

7 基本解决方法：多级层次结构 多级分层结构 M1 速度最快，容量最小，每位价格最高 Mn速度最慢，容量最大，每位价格最低 并行
……….. CPU M1 速度最快，容量最小，每位价格最高 Mn速度最慢，容量最大，每位价格最低 并行 存储系统接近M1的速度，容量和价格接近Mn

8 现代计算机系统的多级存储层次 应用程序局部性原理: 给用户 一个采用低成本技术达到的存储容量. （容量大，价格低）
一个采用高速存储技术达到的访问速度.（速度快） CPU Register C A H E MEMORY I/O device Speed (ns): 0.25ns 1ns 100ns 10ms Size (bytes): 500B 64KB 1GB 1TB

9 存储层次工作原理： Locality! Temporal Locality (时间局部性):
=>保持最近访问的数据项最接近微处理器 Spatial Locality (空间局部性): 以由地址连续的若干个字构成的块为单位，从低层复制到上一层 Lower Level Memory Upper Level To Processor From Processor Blk X Blk Y

10 存储层次结构涉及的基本概念 Block 镜像和一致性问题 寻址：不管如何组织，我们必须知道如何访问数据
Block : 不同层次的Block大小可能不同 命中和命中率 失效和失效率 镜像和一致性问题 高层存储器是较低层存储器的一个镜像 高层存储器内容的修改必须反映到低层存储器中 数据一致性问题 寻址：不管如何组织，我们必须知道如何访问数据 要求：我们希望不同层次上块大小是不同的 在L0 cache 可能以Double, Words, Halfwords, 或bytes 在L1cache仅以cache line 或 slot为单位访问 在更低层….. 因此总是存在地址映射问题 物理地址格式 Block Frame Address + Block Offset

11 存储层次的性能参数(1/2) 假设采用二级存储：M1和M2 M1和M2的容量、价格、访问时间分别为：
S1 、 C1、TA S2、C2、TA2 Lower Level Memory Upper Level To Processor From Processor Blk X Blk Y

12 存储层次的性能参数 (2/2) 存储层次的平均每位价格C 命中(Hit): 访问的块在存储系统的较高层次上
C=(C1*S1+C2*S2)/(S1+S2) 命中(Hit): 访问的块在存储系统的较高层次上 若一组程序对存储器的访问，其中N1次在M1中找到所需数据，N2次在M2中找到数据 则 Hit Rate（命中率）: 存储器访问在较高层命中的比例 H= N1/(N1+N2) Hit Time（命中时间）:访问较高层的时间，TA1 失效(Miss):访问的块不在存储系统的较高层次上 Miss Rate （失效）= 1 - (Hit Rate) = 1 – H ＝ N2/(N1+N2) 当在M1中没有命中时：一般必须从M2中将所访问的数据所在块搬到M1中，然后CPU才能在M1中访问。 设传送一个块的时间为TB,即不命中时的访问时间为：TA2+TB+TA1 = TA1+TM TM 通常称为失效开销 平均访存时间: 平均访存时间 TA = HTA1+(1-H)(TA1+TM) = TA1+(1-H)TM

13 常见的存储层次的组织 Registers <-> Memory cache <-> memory
由编译器完成调度 cache <-> memory 由硬件完成调度 memory <-> disks 由硬件和操作系统（虚拟管理） 由程序员完成调度

14 存储层次研究的四个问题 Q1: Where can a block be placed in the upper level? (Block placement) Q2: How is a block found if it is in the upper level? (Block identification) Q3: Which block should be replaced on a miss? (Block replacement) Q4: What happens on a write? (Write strategy)

15 需考虑的其他问题 CPU如何知道一次访问是否命中 失效开销问题 其他一些问题 即需要能较早的知道是否命中，以便发出相应的信号
可能需要更多的硬件开销和软件开销 硬件和软件引起的异常会增多

16 5.2 Cache基本知识 现代计算机，在CPU和主存之间一般都设置一个高速，小容量的存储器cache，它对于提高计算机系统的性能有着重要的意义

17 Q1：映象规则 当要把一个块从主存调入Cache时，如何放置问题 三种方式 全相联方式：即所调入的块可以放在cache中的任何位置
一般，主存块地址i 与cache中块地址j 的关系为： j ＝ i mod （M) ，M为cache中的块数 组相联映象：主存中每一块可以被放置在Cache中唯一的一个组中的任意一个位置，组由若干块构成，若一组由n块构成，我们称N路组相联 组间直接映象 组内全相联 若cache中有G组，则主存中的第i 块的组号K K = i mod (G),

18 Q1: Where can a block be placed in the upper level?
Block 12 placed in 8 block cache: Fully associative, direct mapped, 2-way set associative S.A. Mapping = Block Number Modulo Number Sets Fully associative: block 12 can go anywhere Block no. Direct mapped: block 12 can go only into block 4 (12 mod 8) Block no. Set associative: block 12 can go anywhere in set 0 (12 mod 4) Set 1 2 3 Block no. Block-frame address Block no.

19 Q1的讨论 N-Way组相联：如果每组由N个块构成，cache的块数为M，则cache的组数G为M/N 不同相联度下的路数和组数 路数 组数
路数 组数 全相联 M 直接相联 M 其他组相联 1 < N <M < G < M 相联度越高，cache空间利用率就越高，块冲突概率就越小，失效率就越低 N值越大，失效率就越低，但Cache的实现就越复杂，代价越大 现代大多数计算机都采用直接映象，两路或四路组相联。

20 Q2(1/2): 查找方法 在CACHE中每一block都带有tag域（标记域），标记分为两类 Set Select Data Select
Address Tags：标记所访问的单元在哪一块中，这样物理地址就分为三部分： Address Tags ## Block index## block Offset 全相联映象时，没有Block Index 显然 Address tag越短，查找所需代价就越小 Status Tags：标记该块的状态，如Valid, Dirty等 Block offset Block Address Tag Index Set Select Data Select

21 Q2（2/2)查找方法 原则：所有可能的标记并行查找，cache的速度至关重要 ，即并行查找 并行查找的方法
用相联存储器实现，按内容检索 用单体多字存储器和比较器实现 显然相联度 N越大，实现查找的机制就越复杂，代价就越 高 无论直接映象还是组相联，查找时，只需比较 tag，index 无需参加比较

22 Example: 1 KB Direct Mapped Cache with 32 B Blocks
对于容量为 2 N 字节的cache: 最高(32-N)位部分 为 Cache Tag 最低M位为字节选择位 (Block Size = 2 M) Block address 31 9 4 Cache Tag Example: 0x50 Cache Index Byte Select Ex: 0x01 Ex: 0x00 Stored as part of the cache “state” Let’s use a specific example with realistic numbers: assume we have a 1 KB direct mapped cache with block size equals to 32 bytes. In other words, each block associated with the cache tag will have 32 bytes in it (Row 1). With Block Size equals to 32 bytes, the 5 least significant bits of the address will be used as byte select within the cache block. Since the cache size is 1K byte, the upper 32 minus 10 bits, or 22 bits of the address will be stored as cache tag. The rest of the address bits in the middle, that is bit 5 through 9, will be used as Cache Index to select the proper cache entry. +2 = 30 min. (Y:10) Valid Bit Cache Tag Cache Data : Byte 31 Byte 1 Byte 0 : 0x50 Byte 63 Byte 33 Byte 32 1 2 3 : : : : Byte 1023 Byte 992 31

23 Example: Set Associative Cache
N-way set associative: 每一个cache索引对应N个cache entries 这N个cache项并行操作 Example: Two-way set associative cache Cache index 选择cache中的一组 这一组中的两块对应的Tags与输入的地址同时比较 根据比较结果选择数据 Cache Index Valid This is called a 2-way set associative cache because there are two cache entries for each cache index. Essentially, you have two direct mapped cache works in parallel. This is how it works: the cache index selects a set from the cache. The two tags in the set are compared in parallel with the upper bits of the memory address. If neither tag matches the incoming address tag, we have a cache miss. Otherwise, we have a cache hit and we will select the data on the side where the tag matches occur. This is simple enough. What is its disadvantages? +1 = 36 min. (Y:16) Cache Tag Cache Data Cache Data Cache Block 0 Cache Tag Valid : Cache Block 1 : : : Compare Adr Tag Compare 1 Sel1 Mux Sel0 OR Cache Block Hit

24 Q3：替换算法 主存中块数一般比cache中的块多，可能出现该块所对应的一组或一个Cache 块已全部被占用的情况，这时需强制腾出其中的某一块，以接纳新调入的块， 替换哪一块，这是替换算法要解决的问题： 直接映象，因为只有一块，别无选择 组相联和全相联由多种选择 替换方法 随机法（Random)，随机选择一块替换 优点：简单，易于实现 缺点：没有考虑Cache块的使用历史，反映程序的局部性较差，失效率较高 FIFO－选择最早调入的块 优点：简单 虽然利用了同一组中各块进入Cache的顺序，但还是反映程序局部性不够，因为最先进入的块，很可能是经常使用的块 最近最少使用法（LRU) (Least Recently Used) 优点：较好的利用了程序的局部性，失效率较低 缺点：比较复杂，硬件实现较困难

25 LRU和Random的比较（失效率） 观察结果（失效率）
Data Cache misses per 1000 instructions comparing LRU, Random, FIFO replacement for serveral sizes and associativities. These data were collected for a block size of 64 bytes for the Alpha architecture using 10 SPEC2000 benchmarks. Five are from SPECint2000(gap, gcc, gzip, mcf and perl) and five are from SPECfp2000(applu, art, equake, lucas and swim) 观察结果（失效率） 相联度高，失效率较低。 Cache容量较大，失效率较低。 LRU 在Cache容量较小时，失效率较低 随着Cache容量的加大，Random的失效率在降低

26 Q4: 写策略 程序对存储器读操作占26％， 写操作占9％ 大概率事件优先原则－优化Cache的读操作
写所占的存储器访问比例 9/( ) 大约为7％ 占访问数据Cache的比例： 9/(26+9) 大约为25% 大概率事件优先原则－优化Cache的读操作 Amdahl定律：不可忽视“写”的速度 “写”的问题 读出标识，确认命中后，对Cache写 （串行操作） Cache与主存内容的一致性问题 写策略就是要解决: 何时更新主存问题

27 两种写策略 写直达法（Write through) 写回法 当发生写失效时的两种策略 优点：易于实现，容易保持不同层次间的一致性
缺点：速度较慢 写回法 优点：速度快，减少访存次数 缺点：一致性问题 当发生写失效时的两种策略 按写分配法(Write allocate)：写失效时，先把所写单元所在块调入Cache，然后再进行写入，也称写时取（Fetch on Write)方法 不按写分配法（no-write allocate): 写失效时，直接写入下一级存储器，而不将相应块调入Cache，也称绕写法（Write around) 原则上以上两种方法都可以应用于写直达法和写回法，一般情况下 Write Back 用Write allocate Write through 用no-write allocate

28 Review 存储系统的层次结构 Cache基本知识 Q1: Block placement
Q2: Block identification Q3: Block replacement Q4: Write strategy CPU Register C A H E MEMORY I/O device Speed (ns): 0.25ns 1ns 100ns 5ms Size (bytes): 500B 64KB 512MB 100GB

29 Alpha AX 21064 Cache结构（数据Cache)
基本技术特性 容量 8KB ，Block 32B, 共256个Block 直接映象 写直达法，写失效时，no-write allocate 方法 每个字为8个字节 21064物理地址34位 21位tag##8位index ##5位块内偏移 Cache命中的步骤 读命中 写命中 Cache失效 Cache向CPU发暂停信号 块传送，21064 Cache与下一级存储器之间数据通路16字节，传送全部32字节需要10个cycles

30 Alpha AX 21064 Cache结构（数据Cache)
基本技术特性 Block 32bytes per Block, 共256个Block 直接映象 写直达法，写失效时，no-write allocate 方法 21064物理地址34位 21位tag##8位index ##5位块内偏移 Cache命中的步骤 读命中 写命中 Cache失效 Cache向CPU发暂停信号 块传送，21064Cache与下一级存储器之间数据通路16字节，传送全部32字节需要10个cycles

31 Alpha 21264 Data Cache 基本技术特征
Cache size: 64Kbytes Block size: 64-bytes Two-way 组相联 Write back, 写失效时，write allocate bits 虚拟地址，虚实映射为44-bits的物理 地址，也支持43-bits虚拟地址，虚实映射为41-bits 的物理地址 29位tags##9位index##6位 Block offset

32 Alpha Data Cache <26>-><29>

33 Review 存储系统的层次结构 Cache基本知识 Cache性能分析 四个问题 AMAT = 命中时间+失效率＊失效开销 CPU
Register C A H E MEMORY I/O device Speed (ns): 0.25ns 1ns 100ns 5ms Size (bytes): 500B 64KB 1GB 100GB

34 Cache 性能分析 CPU time = (CPU execution clock cycles Memory stall clock cycles) x clock cycle time Memory stall clock cycles = (Reads x Read miss rate x Read miss penalty Writes x Write miss rate x Write miss penalty) Memory stall clock cycles = Memory accesses x Miss rate x Miss penalty Different measure: AMAT Average Memory Access time (AMAT) = Hit Time + (Miss Rate x Miss Penalty) Note: memory hit time is included in execution cycles.

35 性能分析举例 Suppose a processor executes at Miss Behavior:
Clock Rate = 200 MHz (5 ns per cycle), Ideal (no misses) CPI = 1.1 50% arith/logic, 30% ld/st, 20% control Miss Behavior: 10% of memory operations get 50 cycle miss penalty 1% of instructions get same miss penalty CPI = ideal CPI + average stalls per instruction 1.1(cycles/ins) + [ 0.30 (DataMops/ins) x 0.10 (miss/DataMop) x 50 (cycle/miss)] + [ 1 (InstMop/ins) x 0.01 (miss/InstMop) x 50 (cycle/miss)] = ( ) cycle/ins = 3.1 65% of the time the proc is stalled waiting for memory! AMAT=(1/1.3)x[1+0.01x50]+(0.3/1.3)x[1+0.1x50]=2.54 指令命中时间为1，失效率为1%,失效开销为50，取指令所占比例100/(100+30) Load和store操作失效率为10%,失效开销为50，取指令所占比例30/(100+30)

36 Example: Harvard Architecture
Unified vs Separate I&D (Harvard) Statistics (given in H&P): 16KB I&D: Inst miss rate=0.64%, Data miss rate=6.47% 32KB unified: Aggregate miss rate=1.99% Which is better (ignore L2 cache)? Assume 33% data ops  75% accesses from instructions (1.0/1.33) hit time=1, miss time=50 Note that data hit has 1 stall for unified cache (only one port) AMATHarvard=75%x(1+0.64%x50)+25%x(1+6.47%x50) = 2.05 AMATUnified=75%x(1+1.99%x50)+25%x( %x50)= 2.24 Proc I-Cache-1 Unified Cache-1 Cache-2 D-Cache-1

37

38 以顺序执行的计算机 UltraSPARC III为例.
举例3： 以顺序执行的计算机 UltraSPARC III为例. 假设Cache失效开销为 100 clock cycles，所有指令忽略存储器停顿需要1个cycle Cache失效可以用两种方式给出 （1）假设平均失效率为2%，平均每条指令访存1.5次 （2）假设每1000条指令cache失效次数为30次 分别基于上述两种条件计算处理器的性能 结论： (1) CPI越低，固定周期数的Cache失效开销的相对影响就越大 (2) 在计算CPI时，失效开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的失效开销会较大，其CPI中存储器停顿部分也就较大。 因此 Cache对于低CPI，高时钟频率的CPU来说更加重要

39 考虑不同组织结构的Cache对性能的影响:
直接映像Cache 和两路组相联Cache，试问他们对CPU性能的影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设： （1）理想Cache(命中率为100%）情况下CPI 为2.0，时钟周期为2ns，平均每条指令访存1.3次 （2）两种Cache容量均为64KB，块大小都是32B （3）采用组相联时，由于多路选择器的存在，时钟周期增加到原来的1.1倍 （4）两种结构的失效开销都是70ns (在实际应用中，应取整为整数个时钟周期） （5）命中时间为1个cycle，64KB直接映像Cache的失效率为1.4%, 相同容量的两路组相联Cache 的失效率为1.0

40 失效开销与Out-of-Order执行的处理器
需要确定两个参数： Length of memory latency Length of latency overlap 例如：在 前面的例子中，若假设允许处理器乱序执行，则对于直接映射方式，假设30%的失效开销可以覆盖（overlap)，那么原来的70ns失效开销就变为49ns.

41 Summary of performance equations in this chapter

42 改进Cache 性能的方法 平均访存时间＝命中时间＋失效率×失效开销 从上式可知，基本途径 降低失效率 减少失效开销 降低命中时间

43 5.3 降低Cache失效率的方法 Cache失效的原因 可分为三类 3C 强制性失效 (Compulsory)
第一次访问某一块，只能从下一级Load，也称为冷启动或首次访问失效 容量失效（Capacity) 如果程序执行时，所需块由于容量不足，不能全部调入Cache， 则当某些块被替换后，若又重新被访问，就会发生失效。 可能会发生“抖动”现象 冲突失效（Conflict (collision)) 组相联和直接相联的副作用 若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置)，然后又被重新访问的情况，这就属于冲突失效

44 各种类型的失效率（1/2)

45 各种类型的失效率（2/2)

46 从统计规律中得到的一些结果 相联度越高，冲突失效就越小 强制性失效和容量失效不受相联度的影响 强制性失效不受Cache容量的影响
容量失效随着容量的增加而减少 符合2:1Cache经验规则 即大小为N的直接映象Cache的失效率约等于大小为N/2的两路组相联的Cache失效率。

47 减少3C的方法 从统计规律可知 增大Cache容量 通过预取可帮助减少强制性失效 增大块 对冲突和容量失效的减少有利
必须小心不要把你需要的东西换出去 需要预测比较准确（对数据较困难，对指令相对容易） 增大块 减缓强制性失效 可能会增加冲突失效（因为在容量不变的情况下，块的数目减少了）

48 增加Cache块大小 （1/2) 降低失效率最简单的方法是增加块大小,统计结果如下图5-6：

49 假定存储系统在延迟40个时钟周期后，每2个时钟周期能 送出16个字节，即：经过42个时钟周期，它可提供16个字 节；经过44个四周周期，可提供32个字节；依此类推。试 根据图5-6列出的各种容量的Cache，在块大小分别为多少 时，平均访存时间最小？

50 增加Cache块大小 （2/2) 从统计数据可得到如下结论 分析 设计块大小的原则，不能仅看失效率
块大小增加，可使强制性失效减少（空间局部性原理） 块大小增加，可使冲突失效增加（因为Cache中块数量减少） 失效开销增大（上下层间移动，数据传输时间变大） 设计块大小的原则，不能仅看失效率 原因：平均访存时间 ＝ 命中时间＋失效率×失效开销

51 提高相联度 8路组相联在降低失效率方面的作用已经和全相联一样有效 2:1Cache经验规则 提高相联度，会增加命中时间
容量为N的直接映象Cache失效率与容量为N/2的两路组相联Cache的失效率差不多相同 提高相联度，会增加命中时间

52 Victim Cache 在Cache和Memory之间增加一个小的全相联Cache

53 基本思想 通常Cache为直接映象，因而冲突失效率较大 Victim cache采用全相联－失效率较低 Victim cache存放由于失效而被丢弃的那些块 失效时，首先检查Victim cache是否有该块，如果有就将该块与Cache中相应块比较。 Jouppi (DEC SRC)发现，含1到5项的Victim cache对减 少失效很有效，尤其是对于那些小型的直接映象数据 Cache 。测试结果，项为4的Victim Cache能使4KB直接 映象数据Cache冲突失效减少20%-90%

54 Pseudo Associative Caches
也称为Column Associate(列相联）。该方法能获得多路 组相联Cache的低失效率，又能保持直接映象的Cache命 中速度。 基本思想 先以直接映象方式查找块 如果失效，查找另一块 另一块入口地址，即将索引字段最高位取反 如果还是失效，只好再访问下一级存储器 问题 具有一快一慢的命中时间，对应于正常命中和伪命中 如果直接映象Cache里的许多快速命中在伪相联中变成慢速命中，那么这种优化措施反而会降低整体性能 解决问题的简单方法：交换两块的内容

55 Pseudo Associative Caches 一快一慢的命中时间

56 Review- Cache 性能分析 CPU time = (CPU execution clock cycles Memory stall clock cycles) x clock cycle time Memory stall clock cycles = (Reads x Read miss rate x Read miss penalty Writes x Write miss rate x Write miss penalty) Memory stall clock cycles = Memory accesses x Miss rate x Miss penalty Different measure: AMAT Average Memory Access time (AMAT) = Hit Time + (Miss Rate x Miss Penalty) Note: memory hit time is included in execution cycles.

57 Review- 降低失效率的基本方法 引起失效的原因 降低失效率的基本方法 增大块大小 增大Cache容量 提高相联度 伪相联技术
强制性失效 (Compulsory) 容量失效（Capacity) 冲突失效（Conflict (collision)) 降低失效率的基本方法 增大块大小 增大Cache容量 提高相联度 伪相联技术 编译优化技术

58 编译器优化 无需对硬件做任何改动，通过软件优化降低失效率 研究从两方面展开： 减少指令失效，重新组织程序（指令调度）而不影响程序的正确性
减少数据失效 减少指令失效，重新组织程序（指令调度）而不影响程序的正确性 Mc-Farling 的研究结果：通过使用profiling信息来判断指令组间可能发生的冲突，并将指令重新排序以减少失效。 研究表明：容量为2KB, 块大小为 4Bytes的直接映象Icache，通过使用指令调度可以使失效率降低50％。容量增大到 8KB, 失效率可降低75％ 在有些情况下，当能够使某些指令不进入ICache时，可以得到最佳性能。即使不这样做，优化后的程序在直接映象Cache中的失效率也低于未优化程序在同样大小的8路组相联Cache中的失效率。 减少数据失效，主要通过优化来改善数据的空间局部性和时间局部性，基本方法为： 数据合并 内外循环交换，循环融合 分块

59 编译器优化方法举例之一：数组合并 Page 212 /* 修改前*/ int val[SIZE]; int key[SIZE]; /* 修改后*/ struct merge { int val; int key; }; struct merge merged_array[SIZE];

60 编译器优化方法举例之二：内外循环交换 /* Before */ for (j = 0; j < 100; j = j+1) for (i = 0; i < 5000; i = i+1) x[i][j] = 2 * x[i][j]; /* After */

61 编译器优化方法举例之三：分块 (1/2) /* Before */ for (i = 0; i < N; i = i+1)
编译器优化方法举例之三：分块 (1/2) /* Before */ 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; }; 最坏情况下，N3次操作，产生的存储器访问次数为: 2N3+N2

62 编译器优化方法举例之三：分块 (2/2) /* After */ for (jj = 0; jj < N; jj = jj+B)
编译器优化方法举例之三：分块 (2/2) /* After */ 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,N); j = j+1) {r = 0; for (k = kk; k < min(kk+B,N); k = k + 1) r = r + y[i][k]*z[k][j]; x[i][j] = x[i][j] + r; };

63 降低失效率的基本方法小结 增大块大小 增大Cache容量 提高相联度 伪相联技术 编译优化技术

64 5.4 减少Cache失效开销 减少CPU与存储器间性能差异的重要手段 基本手段： 平均访存时间＝命中时间＋失效率×失效开销
多级Cache技术(Multilevel Caches) 子块放置技术(Sub-block Placement) 请求字处理技术(Critical Word First and Early Restart) 让读优先于写(Giving Priority to Read Misses over Writes) 合并写(Merging Write Buffer)

65 采用两级Cache 与CPU无关，重点是Cache与Memory之间的接口
问题：为了使Memory-CPU性能匹配，到底应该把Cache做的更快，还是应该把Cache做的更大 答案：两者兼顾。二级Cache –降低失效开销（减少访问存储器的次数。 带来的复杂性：性能分析问题 性能参数 平均访存时间＝命中时间L1+失效率L1×失效开销L1 失效开销L1 = 命中时间L2 + 失效率L2×失效开销L2 AMAT = Hit TimeL1+Miss rateL1×(Hit TimeL2+Miss rateL2×Miss penaltyL2) 对第二级Cache，系统所采用的术语 局部失效率：该级Cache的失效次数 / 到达该级Cache的访存次数 全局失效率：该级Cache的失效次数/ CPU发出的访存总次数

66 Miss rates versus cache size for multilevel caches

67 两级Cache的一些研究结论 在L2比L1大得多得情况下，两级Cache的全局失效率和容量与第二级Cache相同的单级Cache的失效率接近
容量：一般很大，可能没有容量失效，只有强制性失效和冲突失效 相联度对第二级Cache的作用 Cache可以较大，以减少失效次数 多级包容性问题：第一级Cache中的数据是否总是同时存在于第二级Cache中。 如果L1和L2的块大小不同，增加了多级包容性实现的复杂性

68 多级Cache举例 Given the data below, what is the impact of second-level cache associativity on its miss penalty? Hit timeL2 for direct mapped = 10 clock cycles Two-way set associativity increases hit time by 0.1 clock cycles to 10.1clock cycles Local miss rateL2 for direct mapped = 25% Local miss rateL2 for two-way set associative = 20% Miss penaltyL2 = 100 clock cycles 结论：提高相联度，可减少第一级Cache的失效开销 第二级Cache特点：容量大，高相联度，块较大，重点减少失效次数。

69 子块放置技术 在减少Tag数量的同时，减少Cache与Memory之间的数据传送量
解决方法：将大块分成若干小块，其中每一小块共享Tag域，并增加Valid表示该子块是否有效。 Cache和Memory之间的最小数据传送单位为子块，从而降低了Cache和Memory之间的数据传送量，以减少失效开销 P218 图5.15

70 100 1 300 200 400

71 请求字处理技术 尽早重启动：只要所请求的字到达，立即发送给 CPU，让等待的CPU尽早重启动继续执行，让其余 字的传送与CPU的执行并行。

72 让读失效优先于写 Write Buffer (写缓冲)，特别对写直达法更有效
CPU不必等待写操作完成，即将要写的数据和地址送到Write Buffer后，CPU继续作其他操作。 写缓冲导致对存储器访问的复杂化 原因：在读失效时，写缓冲中可能保存有所读单元的最新值，还没有写回。 解决问题的简单方法1：推迟对读失效的处理，直到写缓冲器清空，导致新的问题——读失效开销增大。 另一办法2：在读失效时，检查写缓冲的内容，如果没有冲突，而且存储器可访问，就可以继续处理读失效 由于读操作为大概率事件，需要读失效优先，以提高性能 写回法时，也可以利用写缓冲器来提高性能 把脏块放入缓冲区，然后读存储器，最后写存储器

73 让读优先于写图示

74 合并写（write merging) 例如：21064 写缓冲器含有4个块，每块大些为4个字（32个字节），每个字8个字节。
使用写直达法，如果此时写缓冲未满，那么就把数据和完整的地址写入缓冲器，对CPU而言，本次“写”访问完成，由缓冲器负责写入主存 在向写缓冲器写入地址和数据时，如果缓冲器重存在被修改过的块，就检查其地址，看看本次写入数据的地址是否与缓冲器内的某个有效块地址匹配，如果匹配，就把新数据与该块合并，称为“合并写”

75 减少失效开销小结 多级Cache技术(Multilevel Caches) 子块放置技术(Sub-block Placement)
请求字处理技术(Critical Word First and Early Restart) 让读优先于写(Giving Priority to Read Misses over Writes) 合并写(Merging Write Buffer) Victim Caches

76 Review- 降低失效率的基本方法 引起失效的原因 降低失效率的基本方法 增大块大小 增大Cache容量 提高相联度 伪相联技术
强制性失效 (Compulsory) 容量失效（Capacity) 冲突失效（Conflict (collision)) 降低失效率的基本方法 增大块大小 增大Cache容量 提高相联度 伪相联技术 编译优化技术

77 Review-减少失效开销 多级Cache技术(Multilevel Caches) 子块放置技术(Sub-block Placement)
请求字处理技术(Critical Word First and Early Restart) 让读优先于写(Giving Priority to Read Misses over Writes) 合并写(Merging Write Buffer) Victim Caches

78 5.5 通过并行操作减少失效开销或失效率 非阻塞Cache技术 (Nonblocking Caches to Reduce stalls on Cache Misses) 针对乱序执行的处理器 硬件预取技术(Hardware Prefetching of Instructions and Data) 编译器控制的预取技术 (Compiler-Controlled Prefetching)

79 非阻塞Cache技术 对有些允许乱序执行的机器（采用动态调度方法）,CPU无需在Cache失效时等待。即在等待数据Cache失效时，可以继续取指令。 采用非阻塞Cache或非锁定Cache技术，在某一Cache失效时，仍然允许CPU进行其他的命中访问，可以有效地提高CPU性能。 Hit under n-miss HP PA n = 8 失效下命中，Cache控制器复杂度上升，因为这时可能有多个访存同时进行。

80 Blocking cache vs. Nonblocking Cache

81 硬件预取 Victim Cache, Pseudo Associative Cache 可以在不影响处理器时钟的频率下，降低失效率，预取技术也能实现这一点 CPU在执行这块代码时，硬件预取下一块代码，因为CPU可能马上就要执行这块代码，这样可以降低或消除Cache的访问失效 当块中有控制指令时，预取失效 预取的指令可以放在Icache中，也可以放在其他地方（存取速度比Memory块的地方 AXP21064失效时，取2块指令块 目标块放在Icache，下一块放在ISB(指令流缓冲）中 如果访问的块在ISB中，取消访存请求，直接从ISB中读，并发出对下一指令块的预取访存请求 Jouppi研究结果：块大小为16字节，容量为4KB的直接映象Cache，1个块的指令流缓冲器，可以捕获15％－25％的失效，4个块 ISB可捕获50％的失效，16块ISB可捕获72％的失效

82 硬件预取 预取数据 出发点：CPU访问一块数据，可能马上要访问下一块数据 Jouppi研究结果：块大小16字节，4KB直接映象Cache， 1Block DSB－25％ 4Block DSB － 43％ Palacharla和Kessler 1994年研究 一个具有两个64KB四路组相联(Icache, Dcache)的处理器来说，8Blocks流缓冲器能够捕获其50％－70％的失效 举例：Alpha AXP21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，Alpha AXP 21064的指令Cache必须为多大才能保持平均访存时间不变？ 假设当指令不在指令Cache中，在预取缓冲区中找到时，需要多花1个时钟周期。 假设预取命中率为25%，命中时间为1个时钟周期，失效开销为50个时钟周期 8KB指令Cache的失效率为1.10%，16KB指令cache的失效率为0.64% 注意：预取是利用存储器的空闲带宽，而不是与正常的存储器操作竞争。

83 由编译器控制预取 （1/2) 在ISA中增加预取指令，让编译器控制预取 预取的种类 故障问题
寄存器预取 : 把数据取到R中 Cache预取：只将数据取到Cache中，不放入寄存器 故障问题 两种类型的预取可以是故障性预取，也可以是非故障性预取 所谓故障性预取指在预取时若出现虚地址故障，或违反保护权限，就会有异常发生 非故障性预取，如导致异常就转化为空操作 只有在预取时，CPU可以继续执行的情况下，预取才有意义 Cache在等待预取数据返回的同时，可以正常提供指令和数据，称为非阻塞Cache或非锁定Cache

84 由编译器控制预取 （2/2) 循环是预取优化的主要目标 失效开销较小时，Compiler简单的展开一两次，调度好预取与执行的重叠
失效开销较大时，编译器将循环体展开多次，以便为较远的循环预取数据 由于发出预取指令需要花费一条指令的开销，因此要避免不必要的预取 重点放在那些可能导致失效的访问 举例：P307 （Hennessy & Patterson) 举例：P308 （Hennessy & Patterson)

85 Review 降低失效率的基本方法 减少失效开销的基本方法 增大Cache容量 增大块大小 提高相联度 Victim Cache 伪相联技术
预取技术（硬件预取、编译控制的预取） 编译优化技术 减少失效开销的基本方法 多级Cache 请求字处理技术 子块放置技术 读优先于写 非阻塞Cache技术 预取技术

86 5.6 减少命中时间(1/2) 容量小，结构简单的Cache 虚拟Cache 容量小，一般命中时间短，有可能做在片内
另一方案，保持Tag在片内，块数据在片外，如DEC Alpha 第一级Cache应选择容量小且结构简单的设计方案 虚拟Cache 物理地址Cache。VA通过TLB产生物理地址，然后存取Cache 缺点：需要中间的转换过程，导致命中时间拉长 基本思路：对于支持VM的CPU，采用虚拟Cache 即直接能以VA来判定是否命中 为什么没有普遍采用这种方式： 问题之一：页级保护问题 复制TLB中的保护信息，增加一个域来保存它，每次检查该域 问题之二：Same VA -> different PA, 任务切换时，刷新Cache 或 用PID作为Tag的一部分，使一个Cache可由多个任务共享 问题之三：different VA -> same PA

87 PID方式的绝对失效率增加了0.3%-0.6%，比Purge相比，减少0.6%-4.3%

88 以虚地址中的页内偏移作为访问Cache的索引，标识用物 理地址，这样地址转换过程可以与取Cache中的标识并行
减少命中时间(2/2) 问题之三：different VA -> same PA 解决办法 用硬件方法保证Cache中每一Cache块对应于唯一一个物理地址。例如alpha 21264, 64KB Cache, 2路组相联，8KB页 软件限制VA-PA的映射。例如别名地址的最后18位相同。如Sun 的Unix 以虚地址中的页内偏移作为访问Cache的索引，标识用物 理地址，这样地址转换过程可以与取Cache中的标识并行 第三种减少命中时间的方法：流水线化Cache访问 将地址转换和访问Cache分开，分别安排在流水线的不同段中

89 提高Cache性能小结

90

91 5.7 主存 存储器的访问源 存储器性能指标 种类：DRAM和SRAM Amdahl经验规则
5.7 主存 存储器的访问源 取指令、取操作数、写操作数和I/O 存储器性能指标 容量、速度和每位价格 访问时间（Access Time) 存储周期（Cycle Time) 种类：DRAM和SRAM Amdahl经验规则 容量随CPU速度的提高而线性增加，实际情况 容量60% per year，而性能7% per year，差距是显然的 根据A-定律，如果忽略计算的一个部分，而去努力提高其余部分的速度，其收效甚微。 解决存储器频带问题的三种途径：多个存储器并行工作，设置各种缓 冲器，Cache存储系统 Cycle Time Time Access Time

92 三种存储器组织方式 Wide: Interleaved: Simple:
CPU/Mux 1 word; Mux/Cache, Bus, Memory N words (Alpha: 64 bits & 256 bits) Interleaved: CPU, Cache, Bus 1 word: Memory N Modules (4 Modules); example is word interleaved Simple: CPU, Cache, Bus, Memory same width (32 bits)

93 提高主存性能的方法 增大存储器的宽度（并行访问存储器） 最简单直接的方法 优点：简单、直接，可有效增加带宽 缺点
增加了CPU与存储器之间的连接通路的宽度，实现代价提高 主存容量扩充时，增量应该是存储器的宽度 写操作问题（部分写操作） 冲突问题 取指令冲突，遇到程序转移时，一个存储周期中读出的n条指令中，后面的指令将无用 读操作数冲突。一次同时读出的几个操作数，不一定都有用 写操作冲突。这种并行访问，必须凑齐n个字之后一起写入。如果只写一个字，必须先把属于同一个存储字的数据读到数据寄存器中，然后在地址码的控制下修改其中一个字，最后一起写。 读写冲突。当要读写的字在同一个存储字内时，无法并行操作。 冲突的原因

94 冲突的原因 从存储器本身看，主要是地址寄存器和控制逻辑只有一套。如果有n个独立的地址寄存器和n套读写控制逻辑，那么第3，4种冲突自然解决，第1、2种冲突也会有所缓解。

95 采用简单的多体交叉存储器 一套地址寄存器和控制逻辑 存储器芯片组织为多个体（Bank） 存储体的宽度，通常为一个字，不需要改变总线的宽度
目的：在总线宽度不变的情况下，完成多个字的并行读写 存储器中所包含的体数，为避免访问冲突，基本原则为： 体的数目 >= 访问体中一个字所需的时钟周期数 例如：某一向量机的存储系统，CPU发出访存请求10个时钟周期后，CPU将从存储体0得到一个字，随后体0开始读该存储体的下一个字，而CPU依次从其余7个存储体中得到后继的7个字。在第18个周期，CPU 将需要存储体0提供下一个字，但该字要到第20个时钟周期才被读出，CPU只好等待。 缺陷：不能对单个体单独访问，对解决冲突没有帮助，逻辑上是一种宽存储器，对各个存储体的访问被安排在不同的时间段

96 Increasing Bandwidth - Interleaving
Access Pattern without Interleaving: CPU Memory D1 available Start Access for D1 Start Access for D2 Memory Bank 0 Access Pattern with 4-way Interleaving: Without interleaving, the frequency of our access will be limited by the DRAM cycle time. With interleaving, that is having multiple banks of memory, we can access the memory much more frequently by accessing another bank while the last bank is finishing up its cycle. For example, first we will access memory bank 0. Once we get the data from Bank 0, we will access Bank 1 while Bank 0 is still finishing up the rest of its DRAM cycle. Ideally, with interleaving, how quickly we can perform memory access will be limited by the memory access time only. Memory interleaving is one common techniques to improve memory performance. + 1 = 68 min. (Y:48) Memory Bank 1 CPU Memory Bank 2 Memory Bank 3 Access Bank 1 Access Bank 0 Access Bank 2 Access Bank 3 We can Access Bank 0 again

97 地址映射方法 ( m个存储体，每个存储体容量为n)
高位交叉编址：相当于对存储单元矩阵按列优先的方式进行编址 考虑处于第 i 行第 j 列的单元，其线性地址为： A = j X n + i 其中： j =0~m-1 ；i = 0~n-1 已知：一个单元的线性地址为A， 则： j = A / n 取下限 i = A mod n 取线性地址高位 log2m位就是体号，其余低位部分就是体内地址 低位交叉编址：相当于对存储单元矩阵按行优先的方式进行编址 A = i X m + j 其中： i = 0~n-1 ；j = 0~m-1 i = A / m 取下限 j = A mod m 取线性地址低位 log2m位就是体号，其余高位部分就是体内地址

98 避免存储体冲突 存储体冲突：两个访问请求访问同一个体 关键问题：地址映射方法 （1） 体号 ＝ 地址 MOD 体数
体内地址 ＝ 地址 / 体数 （2）体号 ＝ 地址 MOD 体数 当存储体数为素数且为2**n －1时， 体内地址 ＝ 地址 MOD 存储体中的字数 要求：体号和体内地址计算尽量简单。

99 独立存储体 目的：可对单个存储体独立操作 思路：有多个存储控制器，每个体有独立的地址线，可能有独立的数据线
多处理机系统 I/O CPU （hit under n misses, 非阻塞Cache) 思路：有多个存储控制器，每个体有独立的地址线，可能有独立的数据线 多体交叉方式中访存操作和数据传送重叠；独立存储体完全重叠 独立存储体方式与多体交叉方式的结合 主存系统由若干独立存储体构成 独立存储体内，按多体交叉方式组织

100 Row and Column Address together:
典型的DRAM组织 bit (data) lines r o w d e c Each intersection represents a 1-T DRAM Cell RAM Cell Array Similar to SRAM, DRAM is organized into rows and columns. But unlike SRAM, which allows you to read an entire row out at a time at a word, classical DRAM only allows you read out one-bit at time time. The reason for this is to save power as well as area. Remember now the DRAM cell is very small we have a lot of them across horizontally. So it will be very difficult to build a Sense Amplifier for each column due to the area constraint not to mention having a sense amplifier per column will consume a lot of power. You select the bit you want to read or write by supplying a Row and then a Column address. Similar to SRAM, each row control line is referred to as the word line and each vertical data line is referred to as the bit line. +2 = 57 min. (Y:37) word (row) select Column Selector & I/O Circuits row address Column Address Row and Column Address together: Select 1 bit a time data

101 Synchronous DRAM SDRAM
Fast Page Mode Synchronous DRAM SDRAM DRAM与Memory控制器之间的接口从异步接口到同步接口 DRAM接口上增加同步时钟 减少了握手开销 2001年 总线速度为 MHZ, SDRAM DIMM 的速度PC100, PC133, PC150, 8Bytes宽度的DIMM （存储器模块）的峰值速度可达到 MB/sec Double Data rate(DDR) DRAM时钟信号的上升沿和下降沿都传送数据，以增加存储器模块的带宽

102 Fast Page Mode Operation
Regular DRAM Organization: N rows x N column x M-bit Read & Write M-bit at a time Each M-bit access requires a RAS / CAS cycle Fast Page Mode DRAM N x M “SRAM” to save a row After a row is read into the register Only CAS is needed to access other M-bit blocks on that row RAS_L remains asserted while CAS_L is toggled Column Address N cols DRAM Row Address N rows So with this register in place, all we need to do is assert the RAS to latch in the row address, then entire row is read out and save into this register. After that, you only need to provide the column address and assert the CAS needs to access other M-bit within this same row. I like to point out that even I use the word “SRAM” here but this is no ordinary sram. It has to be very small but the good thing is that it is internal to the DRAM and does not have to drive any external load. Anyway, this type of operation where RAS remains asserted while CAS is toggled to bring in a new column address is called Page Mode operation. Strore orw so don’t have to repeat: SRAM It will become clearer why this is called Page Mode operation when we look into the operation of the SPARCstation 20 memory system. + 2 = 71 min. (Y:51) N x M “SRAM” M bits M-bit Output A Row Address CAS_L RAS_L Col Address 1st M-bit Access 2nd M-bit 3rd M-bit 4th M-bit

103 由标准的DRAM核+新的接口，存储器模块更像存储系统， 而不是一个存储器组件
新的DRAM界面：RAMBUS 由标准的DRAM核+新的接口，存储器模块更像存储系统， 而不是一个存储器组件 第一代RAMBUS的接口 (RDRAM)取消了RAS/CAS，而用 包交换总线或称分离总线替代，称为RDRAM。8位数据总 线、行列信息复用，时钟 300MHZ 第二代RAMBUS的接口 （direct RDRAM) DRDRAM 分离的行、列命令总线和18位数据总线 内部bank从RDRAM的4扩展到8，时钟到400MHZ RAMBUS与DDR SDRAM的比较 带宽：DIMM宽度>=64位 带宽接近RAMBUS 在基于Cache的系统中，得到第一个字节之前的延迟+数据传输的延迟，RAMBUS改进了后一项 价格

104 举例：假设某台机器的特性及其Cache的性能为：
例题： 举例：假设某台机器的特性及其Cache的性能为： 块大小为1个字 存储器总线宽度为1个字 Cache失效率为3% 平均每条指令访存1.2次 Cache失效开销为32个时钟周期 平均CPI（忽略Cache失效）为2 试问多体交叉和增加存储器宽度对提高性能各有何作用？ 如果把Cache块大小变为2个字时，失效率降为25;块大小 变为4个字时，失效率降为1%。求在采用2路、4路多体交 叉存取以及将存储器和总线宽度增加一倍时，性能分别提 高多少？

105 允许应用程序的大小，超过主存容量。目的是提高存储系 统的容量 帮助OS进行多进程管理
5.8 虚拟存储器－基本原理 允许应用程序的大小，超过主存容量。目的是提高存储系 统的容量 帮助OS进行多进程管理 每个进程可以有自己的地址空间 提供多个进程空间的保护 可以将多个逻辑块映射到共享的物理存储器上 静态重定位和动态重定位 应用程序运行在虚地址空间 虚实地址转换对用户是透明的 虚拟存储管理的是主存－辅助存储器这个层面上 失效：页失效或地址失效 块：页或段

106

107 Cache与VM的区别 目的不同 替换的控制者不同 地址空间 下一级存储器 Cache是为了提高访存速度 VM是为了提高存储容量
VM的页失效通常由OS处理 一般页失效开销很大，因此替换算法非常重要 地址空间 VM空间由CPU的地址尺寸确定 Cache的大小与CPU地址尺寸无关 下一级存储器 Cache下一级是主存 VM下一级是磁盘，大多数磁盘含有文件系统，文件系统寻址与主存不同，它通常在I/O空间中，VM的下一级通常称为SWAP空间

108 虚拟存储器页式管理的典型参数与Cache的比较

109 页式管理和段式管理 VM可分为两类：页式和段式 页式：每页大小固定 段式：每段大小不等
两者区别：P241 表 GC－Garbage Collector

110

111 VM的四个问题 (1/2) 映象规则 查找算法－用附加数据结构 选择策略：低失效率和复杂的映象算法，还是简单的映射方法，高失效率
由于失效开销很大，一般选择低失效率方法，即全相联映射 查找算法－用附加数据结构 固定页大小－用页表 VPN －> PPN Tag标识该页是否在主存 可变长段 －段表 段表中存放所有可能的段信息 段号 －>段基址 再加段内偏移量 可能由许多小尺寸段 页表 页表中所含项数：一般为虚页的数量 功能: VPN－>PPN，方便页重新分配，有一位标识该页是否在内存

112 按虚页的数量设置页表大小，可能页表非常大
页表项问题 按虚页的数量设置页表大小，可能页表非常大 例如32位虚地址，4KB / 页，页表项需要 4GB/4KB项 需要页大小与页表项数目的平衡问题 另一方案：反向页表 基本思路：页表反映物理页的数目，而不是虚拟页的数目 用Hash表 完成虚拟页号到物理页号的转换 通过比较Tag确定是否是所需的PN 如果是，再检测其是否在内存 如果不是：则从硬盘上查找全部页表

113 VM的四个问题（2/2) 替换规则 写策略 LRU是最好的 但真正的LRU方法，硬件代价较大 用硬件简化，通过OS来完成
为了帮助OS寻找LRU页，每个页面设置一个 use bit 当访问主存中一个页面时，其use bit置位 OS定期复位所有使用位，这样每次复位之前，使用位的值就反映了从上次复位到现在的这段时间中，哪些页曾被访问过。 当有失效冲突时，由OS来决定哪些页将被换出去。 写策略 总是用写回法，因为访问硬盘速度很慢。

114

115 页面大小的选择 页面选择较大的优点 页面选择较大的缺点 减少了页表的大小 如果局部性较好，可以提高命中率 内存中的碎片较多，内存利用率低
进程启动时间长 失效开销加大

116 Alpha VPN－>PPN

117 TLB （Translation look-aside Buffer)
页表一般很大，存放在主存中。 导致每次访存可能要两次访问主存，一次读取页表项，一次读写数据 解决办法：采用 TLB TLB 存放近期经常使用的页表项，是整个页表的部分内容的副本。 基本信息： VPN##PPN##Protection Field##use bit ## dirty bit OS修改页表项时，需要刷新TLB，或保证TLB中没有该页表项的副本 TLB必须在片内 速度至关重要 TLB过小，意义不大 TLB过大，代价较高 相联度较高（容量小）

118 TLB的典型参数 block size - same as a page table entry - 1 or 2 words hit time - 1 cycle miss penalty - 10 to 30 cycles miss rate - .1% to 2% TLB size - 32 B to 8 KB

119 举例：Alpha 21064的TLB

120 Summary of Virtual Memory and Caches

121 16-KB 直接映像unified cache, 采用写回法，失效率为0.049