计算机系统结构 西南林业大学计信学院 邢丽伟

计算机系统结构 第4章 存储层次 4.1 存储器的层次结构 4.2 Cache基本知识 4.3 降低Cache失效率的方法 第4章 存储层次 4.1 存储器的层次结构 4.2 Cache基本知识 4.3 降低Cache失效率的方法 4.4 减少Cache失效开销 4.5 减少命中时间 4.6 主存 4.7 虚拟存储器 4.8 进程保护 4.9 Intel Core i7中的存储器层次结构

第4章 存储层次 4.1 存储器的层次结构 4.1.1 从单级存储器到多级存储器 1. 从用户的角度来看，存储器的三个主要指标是： 第4章 存储层次 4.1 存储器的层次结构 4.1.1 从单级存储器到多级存储器 1. 从用户的角度来看，存储器的三个主要指标是： 容量，速度，价格(每位价格) 2. 人们对这三个指标的期望: 容量大，速度快，价格低 3. 这三个指标相互矛盾 如：速度越高，价格越高；容量越大，价格越低；容量越大，速度越慢。 4. 解决方法 采用多种存储器技术，构成存储层次。

4.1 存储器的层次结构 M1-Mn：用不同技术实现的存储器 它们之间以块或页面为单位传送数据， M1离CPU最近，容量最小，每位价格最高。 4.1 存储器的层次结构 M1-Mn：用不同技术实现的存储器 它们之间以块或页面为单位传送数据， M1离CPU最近，容量最小，每位价格最高。 Mn离CPU最远，容量最大，每位价格最低。 考虑相邻的两级，靠近CPU的一级总是容量小一些，速度快一些，价格高一些。

4.1 存储器的层次结构 整个系统的目标：从CPU看去，这个存储器系统的速度接近于M1的，而容量和价格则接近于Mn。 4.1 存储器的层次结构 整个系统的目标：从CPU看去，这个存储器系统的速度接近于M1的，而容量和价格则接近于Mn。 须做到：存储器越靠近CPU，CPU对它的访问频率越高。大多数访问都能在M1完成（根据局部性原理）。 任何一级存储器中的内容一般都是其下一层存储器中内容的子集。当CPU访存时，首先是访问M1，若找到数据，则访问结束。若没有找到，就需要访问M2，将包含所需数据的块（或页面）调入M1。若M2中还没有找到，就需访问M3，以此类推。 小容量存储器：速度高，价格也高。大容量存储器：速度低，价格也低。 高性能要求存储器速度高，实际应用要求存储器容量大，互相矛盾。怎么办？现代计算机一般采用存储层次。

4.1 存储器的层次结构 顶层包含最常用的信息。 任何一层中包含的信息，都是其下一层中信息的一个副本。 4.1 存储器的层次结构 顶层包含最常用的信息。 任何一层中包含的信息，都是其下一层中信息的一个副本。 CPU访问存储器时，若在Cache中没找到所要的信息，就从下一层中调入。

4.1 存储器的层次结构 4.1.2 存储层次的性能参数 每位价格C，命中率H，平均访问时间TA 假设：S ── 容量 TA ── 访问时间 4.1 存储器的层次结构 4.1.2 存储层次的性能参数 每位价格C，命中率H，平均访问时间TA 假设：S ── 容量 TA ── 访问时间 C ── 每位价格 下面仅考虑由M1和M2构成的两级存储层次： M1的参数：S1，TA1，C1 M2的参数：S2，TA2，C2 1. 每位价格C C＝ C1S1＋C2S2 S1＋S2 显然，当S1 << S2时，C ≈ C2

4.1 存储器的层次结构 2. 命中率 H 和失效率 F 命中率为CPU访问存储系统时，在M1中找到所需信息的概率。 命中率一般用模拟的方法来确定，也就是通过模拟一组有代表性的程序，分别记录下访问M1和M2的次数N1和N2，则 H＝N1/(N1＋N2) N1 ── 访问M1的次数 N2 ── 访问M2的次数 失效率 F＝1－H

4.1 存储器的层次结构 3. 平均访问时间 TA 分两种情况来考虑CPU的一次访存： 4.1 存储器的层次结构 3. 平均访问时间 TA 分两种情况来考虑CPU的一次访存： 当命中时，访问时间即为TA1，所以TA1常称为命中时间。 不命中时，情况比较复杂。在大多数两级存储层次中，若 访问的字不在M1中，就必须从M2把所请求的字的信息块传 送到M1，之后CPU才可在M1中访问到这个字。假设传递一 个信息块所需的时间为TB,则不命中的访问时间为 TA2+TB+TA1=TA1+TM 其中，TM=TA2+TB，它是从向M2发出访问请求到把整个数据块调 入M1中所需的时间。TM常称为失效开销。 根据以上分析可知 TA＝HTA1＋(1－H )(TA1+TM)＝TA1＋(1－H )TM 或 TA＝TA1＋F TM

4.1 存储器的层次结构 4.1.3 “Cache－主存”和“主存－辅存”层次 1. “Cache－主存”层次 主存与CPU的速度差距 4.1 存储器的层次结构 4.1.3 “Cache－主存”和“主存－辅存”层次 从主存的角度来看 “Cache－主存”层次：弥补主存速度的不足 “主存－辅存”层次： 弥补主存容量的不足 1. “Cache－主存”层次 主存与CPU的速度差距

4.1 存储器的层次结构

4.1 存储器的层次结构

4.1 存储器的层次结构 3. “主存－辅存”层次

4.1 存储器的层次结构 存储层次 CPU对第二级的 访问方式 比较项目 目 的 存储管理实现 访问速度的比值 (第一级和第二级) 4.1 存储器的层次结构 存储层次 CPU对第二级的 访问方式 比较项目 目　　的 存储管理实现 访问速度的比值 (第一级和第二级) 典型的块(页)大小 失效时CPU是否切换 “Cache －主存”层次 “主存－辅存”层次 为了弥补主存速度的不足 为了弥补主存容量的不足 主要由专用硬件实现 主要由软件实现 几比一 几百比一 几十个字节 几百到几千个字节 可直接访问 均通过第一级 不切换 切换到其他进程 “Cache－主存”与“主存－辅存”层次的区别

4.1 存储器的层次结构 4.1.4 存储层次的四个问题 1. 当把一个块调入高一层(靠近CPU)存储器时， 可以放在哪些位置上? 4.1 存储器的层次结构 4.1.4 存储层次的四个问题 1. 当把一个块调入高一层(靠近CPU)存储器时， 可以放在哪些位置上? (映象规则) 2. 当所要访问的块在高一层存储器中时，如何 找到该块? (查找算法) 3. 当发生失效时，应替换哪一块？ (替换算法) 4. 当进行写访问时，应进行哪些操作? (写策略)

第4章 存储层次 4.2 Cache基本知识 Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。 相应地，CPU的访存地址被分割成两部分：块地址和块内位移。 主存地址： 块地址 块内位移 主存块地址用于查找该块在Cache中的位置， 块内位移用于确定所访问的数据在该块中的位置。

4.2 Cache基本知识 5.2.1 映象规则 映象规则主要有全相联映象，直接映象和组相联映象三种。 1.全相联映象 5.2.1 映象规则 映象规则主要有全相联映象，直接映象和组相联映象三种。 1.全相联映象 全相联：主存中的任一块可以被放置到Cache中的任意一个位置。 特点：空间利用率最高，冲突概率最低，实现最复杂。

4.2 Cache基本知识

4.2 Cache基本知识 2.直接映象 直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。 (循环分配) ◆ 特点：空间利用率最低，冲突概率最高，实现最简单。 ◆ 对于主存的第i 块，若它映象到Cache的第j 块，则: j＝i mod (M ) （M为Cache的块数）

4.2 Cache基本知识

4.2 Cache基本知识 3. 组相联映象 ◆ 设M＝2m，则当表示为二进制数时，j 实际 上就是i 的低m 位： 主存块地址 i： j ◆ 组相联：主存中的每一块可以被放置到Cache 中唯一的一个组中的任何一个位置。 （Cache等分为若干组，每组由若干个块构成） ◆ 组相联是直接映象和全相联的一种折中。

4.2 Cache基本知识

4.2 Cache基本知识 ◆ 组的选择常采用位选择算法 若主存第i 块映象到第k 组，则: k＝i mod（G） （G为Cache的组数） 设G＝2g，则当表示为二进制数时，k 实 际上就是i 的低 g 位： g位 k 主存块地址 i： ◆ 上述的m和k 通常称为索引

4.2 Cache基本知识 ◆ n 路组相联：每组中有n 个块(n＝M /G ) n 称为相联度。 相联度越高，Cache空间的利用率就越高， 块冲突概率就越低，失效率也就越低。 n (路数) G (组数) 全相联 M 1 直接映象 1 M 　组相联 1＜n＜M 1＜G＜M ◆ 绝大多数计算机的Cache: n ≤4 想一想：相联度一定是越大越好？

4.2 Cache基本知识 块冲突是指一个主存块要进入已被占用的Cache块位置。 显然，全相联的失效率最低，直接映象的失效率最高。虽然从降低失效率的角度来看，n的值越大越好，但在后面我们将看到，增大n值并不一定能使整个计算机系统的性能提高，而且还会使Cache的实现复杂度和代价增大。 因此，绝大多数计算机都采用直接映象、两路组相联或4路组相联。特别是直接映象，采用得最多。

4.2 Cache基本知识 4.2.2 查找方法 1. 如何确定Cache中是否有所要访问的块？ 若有的话如何确定其位置？ 设置查找目录表。 目录表共有M项，每一项对应于Cache中的一个块，用于指出当前该块中存放的信息是哪一个主存块的（可能有多个主存块映象到该Cache块）。它实际上是记录了该主存块的块地址的高位部分，称为标识（tag）。每个主存块能唯一的由其标识来确定。

4.2 Cache基本知识 为了指出Cache中的块是否包含有效信息，一般是在目录表中给每一项设置一个有效位。例如，当该位为“1”时表示该目录表项有效，Cache中相应块所包含的信息有效。当一个主存块被调入Cache中某一个块位置时，它的标识就被填入到目录表中与该Cache块相对应的项中，并且该项的有效位被置“1”。

4.2 Cache基本知识 根据映象规则不同，一个主存块可能映象到Cache中的一个或多个Cache块位置。为便于讨论，我们把它们称为候选位置。 当CPU访问该主存块时，必须且只需查找它的候选位置所对应的目录表项（标识）。如果有与所访问的主存块相同的标识，且其有效位为“1”，则它所对应的Cache块即是所要找的块。

4.2 Cache基本知识 直接映象Cache的候选位置最少，只有一个； 全相联Cache的候选位置最多，为M个； 而n路组相联则介于两者之间，为n个。

4.2 Cache基本知识 ◆ 并行查找与顺序查找

4.2 Cache基本知识 ◆ 顺序查找提高性能的方法：主候选位置(MRU块) 前瞻执行

4.2 Cache基本知识 ◆ 并行查找的实现方法： 相联存储器 单体多字存储器＋比较器 举例： ４路组相联并行标识比较 （比较器的个数及位数）

4.2 Cache基本知识 主存块地址： 目录表 （标识存储器）

4.2 Cache基本知识

4.2 Cache基本知识

4.2 Cache基本知识 4.2.3 替换算法 所要解决的问题：当要从主存调入一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全被占用的情况。这时需强迫腾出其中的某一块，以接纳新调入的块。那么应该替换哪一块？ 1. 随机法 为了均匀使用一组中的各块，随机地选择被替换的块。有些系统采用伪随机数法产生块号。 特点：实现简单，但反映不了程序的局部性。 2. 先进先出法（FIFO） 选择最早调入的块作为被替换的块。 特点：容易实现。还是不能正确地反映程序的局部性。

4.2 Cache基本知识 3. 最近最少使用法（LRU） 选择近期最少被访问的块作为被替换的块。实际应用中通常是选择最久没有被访问过的块作为被替换的块。 特点：失效率低。能较好地反映程序的局部性原理。但LRU比较复杂，硬件实现比较困难，特别是当组的大小增加时，LRU的实现代价会越来越高，而且经常只能是近似的实现。

4.2 Cache基本知识 表中的数据是对于一个VAX地址流（既包括用户程序也包括操作系统程序）在块大小为16B的情况下统计的。在这个例子中，对于大容量Cache，LRU和随机法的失效率几乎没什么差别。

4.2 Cache基本知识 4.2.4 写策略 处理器对Cache的访问主要是读访问，因此设计Cache要针对最经常发生的“读”进行优化。 4.2.4 写策略 处理器对Cache的访问主要是读访问，因此设计Cache要针对最经常发生的“读”进行优化。 幸运的是，最经常发生的“读”也是最容易提高速度的。访问Cache时，在读出标识进行比较的同时，可以把相应的Cache块也读出。如果命中，则把该块中请求的数据立即送给CPU；若为失效，则所读出的块没什么用处，但也没什么坏处，置之不理就是了。

4.2 Cache基本知识 “写”在所有访存操作中所占的比例 统计结果表明，对于一组给定的程序： “写”在所有访存操作中所占的比例： load指令：26％ store指令：9％ “写”在所有访存操作中所占的比例： 　9％/(100％＋26％＋9％)≈7％ “写”在访问数据Cache操作中所占的比例： 　 9％/(26％＋9％)≈25％ 取指令 读数据 写数据

4.2 Cache基本知识 然而，对于“写”却不是如此。只有在读出标识并进行比较，确认是命中后，才可对Cache块进行写入。由于检查标识不能与写入Cache并行进行，“写”一般比“读”花费更多的时间。 另一个比较麻烦的地方是，处理器要写入的数据的宽度不是定长的（通常为1~8B）。写入时，只能修改Cache块中相应的部分，而“读”则可以多读出几个字节也没关系。 “写”访问有可能导致Cache和主存内容的不一致。显然，为了保证正确性，主存的内容也必须更新。至于何时更新，这正是写策略要解决的问题。

4.2 Cache基本知识 两种写策略 写策略是区分不同Cache设计方案的一个重要标志。 ◆ 写直达法 　◆ 写直达法 执行“写”操作时，不仅写入Cache，而且 也写入下一级存储器。 　◆ 写回法 执行“写”操作时，只写入Cache。仅当 Cache中相应的块被替换时，才写回主存。 (设置“污染位”)

4.2 Cache基本知识 两种写策略的比较 ◆ 写直达法的优点：易于实现，一致性好。 　 ◆ 写直达法的优点：易于实现，一致性好。 　 ◆ 写回法的优点：速度快，而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache不到达主存，因而所使用的存储器频带较低；

4.2 Cache基本知识 写缓冲器： 采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写等待。减少写等待的一种常用优化技术是采用写缓冲器，从而使下一级存储器的更新和CPU的执行重叠起来。

4.2 Cache基本知识 “写”操作时的调块： 由于“写”访问并不需要用到所访问单元中原有的数据。所以，当发生写失效时，是否调入相应的块，有两种选择： 　 ◆ 按写分配(写时取) 写失效时，先把所写单元所在的块调入 Cache，再行写入。 　 ◆ 不按写分配(绕写法) 写失效时，直接写入下一级存储器而不调块。 写策略与调块 写直达法 ── 不按写分配 写回法 ── 按写分配

4.2 Cache基本知识 4.2.5 Cache的结构 例子：DEC的Alpha AXP21064中的内部数据Cache 1. 简介 容量：8KB 块大小：32B 块数：256 映象方法：直接映象 “写”策略：写直达 采用不按写分配 写缓冲器大小：4个块

2. 结构图 4.2 Cache基本知识

3. 工作过程 ◆ “读”访问命中 4.2 Cache基本知识

◆ “写”访问命中 4.2 Cache基本知识

4.2 Cache基本知识 ◆ 失效情况下的操作 发生读失效时，Cache向CPU发出一个暂停信号，通知它等待，并从下一级存储器中读入32B数据。21064的Cache和它的下一级存储器之间的数据通路为16B，每次数据传送需5个时钟周期，传送全部32B数据要花10个时钟周期。因为21064的数据Cache是直接映象的，所以被替换的块只有一个，别无选择。替换一个块意味着更新该块的数据、标识和有效位。 发生写失效时，21064采用不按写分配规则。也就是说Cache使数据“绕过”Cache，直接写入主存。

4.2 Cache基本知识 4. 混合Cache与分离Cache 混合Cache：指令和数据混合Cache。 若流水线中同时请求一个数据字和一个指令字， 会出现冲突，导致CPU等待。 分离Cache：分为指令Cache和数据Cache两个Cache。 Alpha AXP21064有一个8KB的指令Cache，其结构与8KB 的数据Cache几乎一样。 CPU知道它发出的地址是指令地址还是数据地址，因此 可以为它们设置不同的端口，这样就会加倍对存储系 统和CPU之间数据通道带宽的要求。由于系统对指令和 数据的操作特性不同，独立的指令Cache和数据Cache 使我们能分别对它们进行优化，它们各自采用不同的 容量、块大小和相联度时的性能可能会更好。

4.2 Cache基本知识 失 效 率 的 比 较 16 KB 容 量 1 KB 2 KB 4 KB 8 KB 32 KB 指令 Cache 容　量 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% 以上数据是在块大小为32B、映象方法为直接映象的条件下，针对SPEC92典型程序，在DECstation5000上测出的平均值。对指令的访问约占所有访问的75%.

4.2 Cache基本知识 4.2.6 Cache性能分析 分离Cache平均失效率的计算： 与硬件速度无关，用它来评价存储系统的性能非常方便,所以经常会用到它。 容易产生一些误导：一种更好的评测存储系统性能的指标是平均访存时间。 平均访存时间 　　 平均访存时间 ＝ 命中时间＋失效率×失效开销

4.2 Cache基本知识 例5.1 假设Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期(因为混合Cache只有一个端口，无法同时满足两个请求。流水线中，混合Cache会导致结构冲突)，根据上表所列的失效率，试问指令Cache和数据Cache容量均为16KB的分离Cache和容量为32KB的混合Cache相比，哪种Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？

4.2 Cache基本知识 100%/（100%+26%+9%）=75% Load Store 解： 如前所述，约75%的访存为取指令。因此，分离Cache的总体失效率为： (75%×0.64%)＋(25%×6.47%)＝2.10% 根据前表，容量为32KB的混合Cache的失效率略低一些，只有1.99%.

4.2 Cache基本知识 平均访存时间公式可以分为指令访问和数据访问两部分： 平均访存时间＝ 指令所占的百分比× (指令命中时间＋指令失效率×失效开销＋ 数据所占的百分比× (数据命中时间＋数据失效率×失效开销) 所以，两种结构的平均访存时间分别为： 平均访存时间分离 ＝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 因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构冲突。执行一个程序所需要的CPU时间与Cache的性能密切相关。

4.2 Cache基本知识 程序执行时间 CPU时间＝（CPU执行周期数+存储器停顿周期数）× 时钟周期时间 其中： 存储器停顿时钟周期数＝“读”的次数×读失效率×读失效开销＋“写”的次数×写失效率×写失效开销 将读/写合并，并求出“读”和“写”的平均失效率和平均失效开销，上式可化简： 存储器停顿时钟周期数＝访存次数×失效率×失效开销

4.2 Cache基本知识 　　 例5.2 我们用一个和Alpha AXP类似的机器作为第一个例子。假设Cache失效开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache失效率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。 　 解 存储器停顿周期数 CPU 时间＝IC×(CPIexe＋──────── ) ×时钟周期时间 指令数

4.2 Cache基本知识 考虑Cache的失效后，性能为： CPU时间有cache＝IC×（2.0＋1.33×2 %×50）×时钟周期时间 　　实际CPI ：3.33 　　　　　3.33/2.0 = 1.67(倍) 　　CPU时间也增加为原来的1.67倍。 　　 但若不采用Cache,则： 　　　　　CPI＝2.0＋50×1.33＝68.5

4.2 Cache基本知识 Cache失效对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的： CPIexecution越低，固定周期数的Cache失效开销的相对影响就越大。 在计算CPI时，失效开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的失效开销较大，其CPI中存储器停顿这部分也就较大。 　 因此Cache对于低CPI、高时钟频率的CPU来说更加重要。

4.2 Cache基本知识 例5.3 考虑两种不同组织结构的Cache：直接映象Cache和2路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设： (1)理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。 (2)两种Cache容量均为64KB，块大小都是32字节。 (3)下图说明，在组相联Cache中，必须增加一个多路选择器，用于根据标识匹配结果从相应组的块中选择所需的数据。因为CPU的速度直接与Cache命中的速度紧密相关，所以对于组相联Cache，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。

4.2 Cache基本知识 (4) 这两种结构Cache的失效开销都是70 ns。（在实际应用中，应取整为整数个时钟周期） (5) 命中时间为1个时钟周期，64 KB直接映象Cache的失效率为1.4%，相同容量的2路组相联Cache的失效率为1.0%。

4.2 Cache基本知识

4.2 Cache基本知识 解 平均访存时间为： 平均访存时间＝命中时间＋失效率×失效开销 因此，两种结构的平均访存时间分别是： 平均访存时间1路＝2＋（0.014×70）＝2.98 ns 平均访存时间2路＝2×1.10＋（0.010×70）＝2.90 ns 2路组相联Cache的平均访存时间比较低。 CPU 时间＝IC×(CPIexe＋每条指令的平均存储器 停顿周期数)×时钟周期时间 ＝IC ×(CPIexe×时钟周期时间＋ 每条指令的平均存储器停顿时间)

4.2 Cache基本知识 因此： CPU时间1路 ＝ IC×(2.0×2＋(1.3×0.014×70)) ＝ 5.27×IC ───── ＝ ───── ＝1.01 CPU时间1路 5.27×IC 和平均访存时间的比较结果相反，直接映象Cache的平均性能好一些，这是因为在两路组相联的情况下，虽然失效次数减少了，但所有指令的时钟周期时间都增加了10%。由于CPU时间是我们进行评价的基准，而且直接映象Cache实现更简单，所以本例中直接映象Cache是较好的选择。

4.2 Cache基本知识 4.2.7 改进Cache的性能 平均访存时间＝命中时间＋失效率×失效开销 可以从三个方面改进Cache的性能： 降低失效率 减少失效开销 减少Cache命中时间 下面介绍17种Cache优化技术 8种用于降低失效率 5种用于减少失效开销 4种用于减少命中时间

4.2 Cache基本知识 写缓冲合并

第4章 存储层次 4.3 降低Cache失效率的方法 三种失效(3C) 强制性失效(Compulsory miss) 第4章 存储层次 4.3 降低Cache失效率的方法 三种失效(3C) 强制性失效(Compulsory miss) 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。 　　　 (冷启动失效，首次访问失效) 容量失效(Capacity miss ) 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。

4.3 降低Cache失效率的方法 三种失效所占的比例 冲突失效(Conflict miss) 图示I(绝对值) 图示Ⅱ(相对值) (碰撞失效，干扰失效) 三种失效所占的比例 图示I(绝对值) 图示Ⅱ(相对值)

4.3 降低Cache失效率的方法

4.3 降低Cache失效率的方法

4.3 降低Cache失效率的方法 可以看出： 相联度越高，冲突失效就越少； 强制性失效和容量失效不受相联度的影响； 表中的数据符合2:1的Cache经验规则，即大小为N的直接映象Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。

4.3 降低Cache失效率的方法 减少三种失效的方法 强制性失效：增加块大小，预取 （本身很少） 容量失效：增加容量 （抖动现象） 　　　　　（本身很少） 容量失效：增加容量 　　　　　（抖动现象） 冲突失效：提高相联度 　　　　　（理想情况：全相联） 许多降低失效率的方法会增加命中时间或失效开销

4.3 降低Cache失效率的方法 4.3.1 增加Cache的容量 降低cache失效率最直接的方法是增加Cache的容量 缺点: 增加成本 可能增加命中时间 这种方法在片外Cache中用得比较多

4.3 降低Cache失效率的方法 4.3.2 增加Cache块大小 失效率与块大小的关系 原因： 一方面它减少了强制性失效； 另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突失效。 Cache容量越大，使失效率达到最低的块大小就越大。

4.3 降低Cache失效率的方法

4.3 降低Cache失效率的方法 各种块大小情况下Cache的失效率 块大小 （字节） Cache容量（字节） 1K 4K 16K 64K 15.05% 8.57% 3.94% 2.04% 1.09% 32 13.34% 7.24% 2.87% 1.35% 0.70% 64 13.76% 7.00% 2.64% 1.06% 0.51% 128 16.64% 7.78% 2.77% 1.02% 0.49% 256 22.01% 9.51% 3.29% 1.15%

4.3 降低Cache失效率的方法 增加块大小会增加失效开销 　 解：平均访存时间=命中时间+失效率×失效开销 假设命中时间与块大小无关，为1 个时钟周期，那么对于一个块大小为16B、容量为1KB的cache来说， 平均访存时间=1+（15.05% ×42)=7.321 对于一个块大小为256B、容量为256KB的cache来说， 平均访存时间=1+（0.49% ×72)=1.353

4.3 降低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.308 64 48 7.605 4.360 2.267 1.594 1.245 128 56 10.318 5.357 2.551 1.509 1.274 256 72 16.847 7.847 3.369 1.571 1.353

4.3 降低Cache失效率的方法 Cache设计者一直在努力同时减少失效率和失效开销。从失效开销的角度来讲，块大小的选择取决于下一级存储器的延迟和带宽两个方面。高延迟和高带宽时，宜采用较大的Cache块，因为这时每次失效时，稍微增加一点失效开销，就可以获得许多数据。与之相反，低延迟和低带宽时，宜采用较小的Cache块，因为采用大Cache块所能节省的时间不多。

4.3 降低Cache失效率的方法 4.3.3 提高相联度 采用相联度超过8的方案的实际意义不大。 2:1 Cache经验规则 4.3.3 提高相联度 采用相联度超过8的方案的实际意义不大。 2:1 Cache经验规则 容量为N的直接映象Cache的失效率和容量为N/2的2路组相联Cache的失效率差不多相同。 提高相联度是以增加命中时间为代价。 例如： 2路组相联比直接映像，采用TTL（晶体管-晶体管逻辑电路）或ECL（射极耦合逻辑电路）板级Cache命中时间增加10％，若采用定制的CMOS（互补型金属氧化物半导体电路） Cache, 增加2％

4.3 降低Cache失效率的方法 例5.5 假定提高相联度会按下列比例增大处理器时钟周期： 时钟周期2路 ＝1.10×时钟周期1路 时钟周期4路 ＝1.12×时钟周期1路 时钟周期8路 ＝1.14×时钟周期1路 假定命中时间为一个时钟周期，失效开销为50个时钟周期，使用表5.5中的失效率，试问当Cache为多大时，以下不等式成立？ 平均访存时间8路 < 平均访存时间4路 平均访存时间4路 < 平均访存时间2路 平均访存时间2路 < 平均访存时间1路

4.3 降低Cache失效率的方法 解 在各种相联度的情况下，平均访存时间分别为： 平均访存时间8路 = 命中时间8路 + 失效率8路×失效开销8路 = 1.14＋失效率8路×50 平均访存时间4路 = 1.12 ＋失效率4路×50 平均访存时间2路 = 1.10 ＋失效率2路×50 平均访存时间1路 = 1.00 ＋失效率1路×50 把相应的失效率代入上式，即可得平均访存时间。 例如，1 KB的直接映象Cache的平均访存时间为： 平均访存时间1路 = 1.00＋0.133×50＝7.65 128 KB的8路组相联Cache的平均访存时间为： 平均访存时间8路＝1.14＋0.006×50＝1.44

4.3 降低Cache失效率的方法 在各种容量和相联度情况下Cache的平均访存时间 Cache容量 相联度（路） 1 2 4 8 7.65 6.60 6.22 5.44 5.90 4.90 4.62 4.09 4.60 3.95 3.57 3.19 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

4.3 降低Cache失效率的方法 当Cache容量不超过16 KB时，上述三个不等式成立。 从32 KB开始，对于平均访存时间有： 4路组相联的平均访存时间小于2路组相联的; 2路组相联的小于直接映象的; 但8路组相联的却比4路组相联的大。

4.3 降低Cache失效率的方法 4.3.4 Victim Cache 一种能减少冲突失效次数而又不影响时钟频率的方法。 基本思想 在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。

4.3 降低Cache失效率的方法 每当发生失效时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需的块。如果有，就将该块与Cache中某个块做交换。 Victim Cache在存储层次中的位置

4.3 降低Cache失效率的方法 作用 对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。 例如 项数为4的Victim Cache: 能使4 KB Cache的冲突失效减少20%～90%

4.3 降低Cache失效率的方法 4.3.5 伪相联Cache 多路组相联的低失效率和直接映象的命中速度 伪相联Cache的优点 优　点 缺　点 直接映象 组相联 命中时间小 命中时间大 失效率高 失效率低 伪相联Cache的优点 命中时间小 失效率低

4.3 降低Cache失效率的方法 基本思想及工作原理 在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。 快速命中与慢速命中 要保证绝大多数命中都是快速命中。

4.3 降低Cache失效率的方法

4.3 降低Cache失效率的方法 例5.6 假设当在按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。仍用上个例子中的数据，问：当Cache容量分别为2 KB和128 KB时，直接映象、2路组相联和伪相联这三种组织结构中，哪一种速度最快？ 解 首先考虑标准的平均访存时间公式： 平均访存时间伪相联 ＝ 命中时间伪相联＋失效率伪相联×失效开销伪相联

4.3 降低Cache失效率的方法 由于： 失效率伪相联＝失效率2路 命中时间伪相联＝命中时间1路＋伪命中率伪相联×2 伪相联查找的命中率等于2路组相联Cache的命中率和直接映象Cache命中率之差。 伪命中率伪相联 ＝命中率2路－命中率1路 ＝（1－失效率2路）－（1－失效率1路） ＝失效率1路－失效率2路 综合上述分析，有： 平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×2 ＋失效率2路×失效开销1路

4.3 降低Cache失效率的方法 将前面表中的数据代入上面的公式，得： 平均访存时间伪相联，2 KB ＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844 平均访存时间伪相联，128 KB ＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356 根据上一个例子中的表，对于2 KB Cache，可得： 平均访存时间1路 ＝5.90 个时钟 平均访存时间2路 ＝4.90 个时钟

4.3 降低Cache失效率的方法 对于128KB的Cache有，可得： 平均访存时间1路 ＝1.50 个时钟 平均访存时间2路 ＝1.45 个时钟 可见，对于这两种Cache容量，伪相联Cache都是速度最快的。 缺点： 多种命中时间使流水线设计更复杂化。

4.3 降低Cache失效率的方法 4.3.6 硬件预取 指令和数据都可以预取 4.3.6 硬件预取 指令和数据都可以预取 预取内容既可放入Cache，也可放在速度比主存快的外缓冲器中。 例如：指令流缓冲器 指令预取通常由Cache之外的硬件完成

4.3 降低Cache失效率的方法 以AlphaAXP21064为例，在发生指令失效时取两个块：被请求指令块和顺序的下一指令块。被请求指令块返回时放入Cache，而预取指令块则放在缓冲器中；如果某次被请求的指令块正好在缓冲器里，则取消对该块的访存请求，直接从缓冲器中读出这一块，同时发出对下一指令块的预取方寸请求。 Joppi的研究结果 指令预取 (4 KB，直接映象Cache，块大小＝16 B) 1个块的指令流缓冲器： 捕获15％～25％的失效 4个块的指令流缓冲器： 捕获50％ 16个块的指令流缓冲器：捕获72％

4.3 降低Cache失效率的方法 数据预取 (4 KB,直接映象Cache) 1个数据流缓冲器：捕获25％的失效 还可以采用多个数据流缓冲器，分别从不同的地址预取数据。Jouppi发现，用4个数据流缓冲器可以将命中率提高到43% Palacharla和Kessler的研究结果 流缓冲器：既能预取指令又能预取数据 对于两个64 KB四路组相联Cache来说： 8个流缓冲器能捕获50％～70％的失效

4.3 降低Cache失效率的方法 例5.7 Alpha AXP 21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，Alpha AXP 21064的指令Cache必须为多大才能保持平均访存时间不变？ 解 假设当指令不在指令Cache里，而在预取缓冲器中找到时，需要多花一个时钟周期。 下面是修改后的公式： 平均访存时间预取 ＝命中时间＋失效率×预取命中率×1＋ 失效率×（1－预取命中率）×失效开销

4.3 降低Cache失效率的方法 假设预取命中率为25%，命中时间为2个时钟周期，失效开销为50个时钟周期。查表可知8 KB指令Cache的失效率为1.10%。则： 平均访存时间预取 ＝2＋（1.10 %×25 %×1）＋1.10 %×（1－25 %）×50 ＝2＋0.00275＋0.413 ＝2.415 为了得到相同性能下的实际失效率，由原始公式得： 平均访存时间 ＝命中时间＋失效率×失效开销 失效率 ＝（平均访存时间－命中时间）/失效开销 ＝（2.415－2）/50＝0.83 % 介于普通8KBcache的失效率1.10%和16KBcache的失效率0.63%之间。

4.3 降低Cache失效率的方法 4.3.7 编译器控制的预取 在编译时加入预取指令，在数据被用到之前发出预取请求。 预取有以下几种类型： 4.3.7 编译器控制的预取 在编译时加入预取指令，在数据被用到之前发出预取请求。 预取有以下几种类型： 寄存器预取：把数据取到寄存器中。 Cache预取：只将数据取到Cache中。 这两种预取可以是故障性的,也可是非故障性的。 故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。 非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。

4.3 降低Cache失效率的方法 本节假定Cache预取都是非故障性的，也称非绑定预取。 在预取数据的同时，处理器应能继续执行。 只有这样，预取才有意义。非阻塞Cache (非锁定Cache)：要求cache在等待预取数据返回的同时,还能继续提供指令和数据。 编译器控制预取的目的 使执行指令和读取数据能重叠执行。 循环是预取优化的主要对象，因为它易于进行预取优化。 失效开销小时：循环体展开1～2次，并调度好预取和执行的重叠 失效开销大时：循环体展开许多次

4.3 降低Cache失效率的方法 例5.8 对于下面的程序，首先判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定： (1) 我们用的是一个容量为8 KB、块大小为16 B的直接映象Cache，它采用写回法并且按写分配。 (2) a、b分别为3×100（3行100列）和101×3的双精度浮点数组，每个元素都是8 B。当程序开始执行时，这些数据都不在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 ];

4.3 降低Cache失效率的方法

4.3 降低Cache失效率的方法 当没有预取功能时，对数组a中元素的写操作是按照他们在主存中的存放顺序进行的。由于每一块含两个元素，当j为偶数是第一次访问一个块，为奇数时是第二次，因此j为偶数失效， j为奇数命中。

4.3 降低Cache失效率的方法

4.3 降低Cache失效率的方法 因此，在没有预取功能时，这个循环一共将引起 150+101=251次数据Cache失效。 优化措施： 将循环分解，使得在第一次循环中不仅预取a，而且预取b，而在第二次循环中只预取a，因为此时b早已经被预取了。假设失效开销很大，预取必须至少提前7次循环进行。

4.3 降低Cache失效率的方法 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 ];

4.3 降低Cache失效率的方法 优化后的程序预取了数据：a[i][7]~a[i][99], [7][0]~b[100][0] 。 失效情况为： 第一次循环中访问a[0][0]~a[0][6]时失效[7/2]=4，访问 b[0][0]~b[6][0]时失效7次； 第二、三次循环中访问a[i][0]~a[i][6]时失效[7/2] × 2=8次 。 故，总的失效次数减少为： 4+7+8=19次 由此结果可知，避免232次失效，其代价是执行了400条预取 指令，这可能是一个很好的折中。

4.3 降低Cache失效率的方法 例5.9 在以下条件下，计算例5.8中所节约的时间： (1) 忽略指令Cache失效，并假设数据Cache无冲突失效和容量失效。 (2) 假设预取可以被重叠或与Cache失效重叠执行，从而能以最大的存储带宽传送数据。 (3) 不考虑Cache失效时，修改前的循环每7个时钟周期循环一次。修改后的程序中，第一个预取循环每9个时钟周期循环一次，而第二个预取循环每8个时钟周期循环一次（包括外层for循环的开销）。 (4) 一次失效需50个时钟周期。

4.3 降低Cache失效率的方法 加速比＝14650/3450＝4.2 循环时间＝300×7 ＝2100 解 修改前： 双重循环一共执行了3×100次循环，每次用7个时钟周期， 循环时间＝300×7 ＝2100 失效开销＝251×50＝12550 2100＋12550＝14650 修改后： 循环时间＝100×9＋200×8＝2500 失效时间＝19×50＝950 2500＋950＝3450 加速比＝14650/3450＝4.2

4.3 降低Cache失效率的方法 4.3.8 编译器变化 基本思想 在编译时，对程序中的指令和数据进行重新 组织，以降低Cache失效率。 4.3.8 编译器变化 基本思想 在编译时，对程序中的指令和数据进行重新 组织，以降低Cache失效率。 McFaring 发现： 通过对指令进行重新排序，可有效地降低指令 Cache的失效率。 2KB Cache: 降低50％ 8KB Cache：降低75% 数据对存储位置的限制比指令的少，因此更便于优化。 通过把数据重新组织，使得一块数据在被从Cache替换出去之前，能最大限度利用其中的数据(访问次数最多)。

4.3 降低Cache失效率的方法 数组合并 /* 修改后 */ 举例： /* 修改前 */ int val [ SIZE ]; int key [ SIZE ]; /* 修改后 */ struct merge { int val ; int key ; } ; struct merge merged_array [ SIZE ];

4.3 降低Cache失效率的方法 内外循环交换 举例： /* 修改前 */ 只要简单地交换循环的嵌套关系就能使程序按数据在存储器中存储的顺序进行访问。也是通过提高空间局部性来减少失效次数。 举例： /* 修改前 */ for （ j = 0 ; j < 100 ; j = j+1 ） for （ i = 0 ; i < 5000 ; i = i+1 ） x [ i ][ j ] = 2 * x [ i ][ j ]; /* 修改后 */

4.3 降低Cache失效率的方法 循环融合 /* 修改前 */ 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 （ j = 0 ; j < N ; j = j+1 ） { d [ i ][ j ] = a [ i ][ j ] + c [ i ][ j ]; }

4.3 降低Cache失效率的方法 分块 /* 矩阵乘法运算，修改前 */ for （ i = 0; i<N; i = i+1 ） 把对数组的整行或整列访问改为按块进行。 /* 矩阵乘法运算，修改前 */ 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）

4.3 降低Cache失效率的方法 两个内部循环读取了数组z的全部N × N个元素，并反复读取数组y的某一行的N个元素，所产生的N个结果被写入数组x的某一行。

4.3 降低Cache失效率的方法 /* 修改后 */ 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; } (失效次数：2N3 /B ＋N2) 为了保证正在访问的元素能在Cache中命中，把原程序改为只对大小为B×B的子数组进行计算，B称为分块因子。

4.3 降低Cache失效率的方法

第4章 存储层次 4.4 减少Cache失效开销 让读失效优先于写 写缓冲合并 请求字处理技术 非阻塞Cache技术 采用两级Cache 第4章 存储层次 4.4 减少Cache失效开销 随着技术的发展，处理器速度的提高要快于DRAM速度的提高，这使得Cache失效开销的相对代价随时间不断增加。 让读失效优先于写 写缓冲合并 请求字处理技术 非阻塞Cache技术 采用两级Cache

4.4 减少Cache失效开销 4.4.1 让读失效优先于写 提高写直达Cache性能最重要的方法是使用一个大小适中的写缓冲器。然而，写缓冲器却导致对存储器的访问复杂化了，因为在读失效时，写缓冲器中可能保存所读单元的最新值。 例5.10 考虑以下指令序列： SW R3, 512（R0） ；M[512]←R3 （Cache索引为0） LW R1, 1024（R0） ；R1←M[1024] （Cache索引为0） LW R2, 512（R0） ；R2←M[512] （Cache索引为0） 假设cache采用写直达法和直接映象，并且地址512和1024映射到同一块，写缓冲器为4个字，试问寄存器R2的值总是等于R3的值吗？

4.4 减少Cache失效开销 在执行Store指令之后，R3的值被写入缓冲器，接下来的第一条Load 指令使用相同的Cache索引，因而产生一次失效。第二条Load指令欲把地址为512的存储单元的值读入寄存器R2中，这也会造成失效。如果此时写缓冲器还未将数据写入存储单元512中，第二条Load指令读入错误值。如果不采取适当的预防措施，R2的值不会等于R3的值。

4.4 减少Cache失效开销 解决问题的方法(读失效的处理) 在写回法Cache中，也可采用写缓冲器。 推迟对读失效的处理，直到写缓冲器清空。 （缺点：读失效的开销增加，如50％） 在读失效时检查写缓冲器中的内容，如果没有冲突而且存储器可访问就可继续处理读失效。 在写回法Cache中，也可采用写缓冲器。 假定读失效将替换一个“脏”的存储块，我们可以不像往常那样先把“脏”块写回存储器，然后在读存储器，而是先把被替换的“脏”块拷入一个缓冲器，然后读存储器，最后再写存储器。这样CPU的读访问就能更快地完成。 和上面的情况类似，发生读失效时，处理器既可以采用等待缓冲区清空的方法，也可以采用检查缓冲区中各字的地址是否有冲突的方法。

4.4 减少Cache失效开销 4.4.2 写缓冲合并 该项技术是提高写缓冲器的效率 4.4.2 写缓冲合并 该项技术是提高写缓冲器的效率 写直达Cache是依靠写缓冲来提高完成对下一级存储器的写操作的时间。 如果写缓冲器为空，就把数据和相应地址写入该缓冲器。 从CPU的角度来看，该写操作就算完成了。

4.4 减少Cache失效开销 如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。 如果写缓冲器满且又没有能进行写合并的项，就必须等待。 提高了写缓冲器的空间利用率，而且还能减少因写缓冲器满而要进行的等待时间。

4.4 减少Cache失效开销

4.4 减少Cache失效开销 4.4.3 请求字处理技术 请求字 4.4.3 请求字处理技术 请求字 从下一级存储器调入Cache的块中，往往只有一个字是立即需要的。这个字称为请求字。 应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。 请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。

4.4 减少Cache失效开销 一般说来，这些技术仅当Cache块很大时才有效。因为， Cache块较小时，用不用这些技术，失效开销差别不大。 此外，在采用请求字优先时，若下一条指令正好访问Cache块的另一部分（以请求字为界，Cache被分为上下两部分。请求字属于其中一部分），则只能节省一个时钟周期，因为只有得到请求字的指令在流水线中可以前进，下一条指令必须停下来等待所需的数据。

4.4 减少Cache失效开销 4.4.4 非阻塞Cache技术 采用尽早重启动技术时，CPU在继续执行之前，仍需等待请求字到达。有些流水方式的机器允许指令乱序执行（后面的指令可以跨越前面的指令先执行），CPU无须在Cache失效时停顿。 非阻塞Cache：Cache失效时仍允许CPU进行其他的命中访问。即允许“失效下命中”。 这种“失效下命中”的优化措施在Cache失效时，不是完全拒绝CPU的访问，而是能处理部分访问，从而减少了实际失效开销。

4.4 减少Cache失效开销 如果更进一步，让Cache允许多个失效重叠，即支持“多重失效下的命中”和“失效下的失效”，则可进一步减少实际失效开销。（此种方法的前提是：存储器必须能够处理多个失效） 可以同时处理的失效个数越多，所能带来的性能上的提高就越大。 下图给出了对于不同的重叠失效个数，数据Cache的平均存储器等待时间（以周期为单位）与阻塞Cache平均存储器等待时间的比值。 所考虑的Cache采用直接映像，容量为8kB，块大小为32B。测试程序为18个SPEC92程序。前14个测试程序为浮点程序，后4个为整数程序。

4.4 减少Cache失效开销

4.4 减少Cache失效开销 例5.11 对于上图描述的Cache，在2路组相联和“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？ 假设8KB数据Cache的平均失效率为：对于浮点程序，直接映象Cache为11.4%，而2路组相联Cache为10.7%；对于整数程序，直接映象Cache为7.4%，2路组相联Cache为6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期。

4.4 减少Cache失效开销 解 对于浮点程序，平均存储器等待时间为： 失效率直接映象 × 失效开销 ＝ 11.4 % × 16 ＝ 1.84 失效率2路组相联 × 失效开销 ＝ 10.7 % × 16 ＝ 1.71 1.71/1.84≈0.93 即2路组相联映像cache的平均存储器等待时间是直接映像Cache的93%，而支持“一次失效下命中”技术的直接映像Cache的平均存储器等待时间是直接映像Cache 的76%。

4.4 减少Cache失效开销 对于整数程序： 失效率直接映象 × 失效开销 ＝ 7.4 % × 16 ＝ 1.18 失效率2路组相联 × 失效开销 ＝ 6.0 % × 16 ＝ 0.96 0.96/1.18≈0.81 “一次失效下的命中”也是81%，二者一样。 失效下命中”方法有一个潜在优点： 它不会影响命中时间，而组相联却会。

4.4 减少Cache失效开销 4.4.5 采用两级Cache 应把Cache做得更快？还是更大？ 答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大 性能分析 平均访存时间 ＝ 命中时间L1＋失效率L1×失效开销L1 失效开销L1 ＝ 命中时间L2＋失效率L2×失效开销L2 平均访存时间 ＝ 命中时间L1＋失效率L1× （命中时间L2＋失效率L2×失效开销L2） 在这个公式里，第二级Cache的失效率是以在第一级Cache中不命中而到达第二级Cache的访存次数为分母来计算的。为避免二义性，对于二级Cache系统的失效率分两种：

4.4 减少Cache失效开销 局部失效率与全局失效率 局部失效率＝该级Cache的失效次数/到达该级 Cache的访问次数 例如：上述式子中的失效率L2 全局失效率＝该级Cache的失效次数/CPU发出的 访存的总次数 全局失效率L2＝失效率L1×失效率L2 评价第二级Cache时，应使用全局失效率这个指标。它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。

4.4 减少Cache失效开销 例5.12 假设在1000次访存中，第一级Cache失效40次， 第二级Cache失效20次。试问：在这种情况下，该Cache系统的局部失效率和全局失效率各是多少？ 解 第一级Cache的失效率（全局和局部）是40/1000，即4%； 第二级Cache的局部失效率是20/40，即50%； 第二级Cache的全局失效率是20/1000，即2%。

4.4 减少Cache失效开销 对于第二级Cache，我们有以下结论： 在第二级Cache比第一级 Cache大得多的情况下，两级Cache的全局失效率和容量与第二级Cache相同的单级Cache的失效率非常接近。 局部失效率不是衡量第二级Cache的一个好指标，因此，在评价第二级Cache时，应用全局失效率这个指标。

4.4 减少Cache失效开销 第一级Cache和第二级Cache之间的首要区别是第一级Cache的速度会影响CPU的时钟频率，而第二级Cache的速度只影响第一级Cache的失效开销。第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间。 第二级Cache设计时有两个问题： 它能否降低CPI中的平均访存时间部分？ 它的成本是多少？

4.4 减少Cache失效开销 第二级Cache的参数 容量 因为第一级Cache中的所有信息都会出现在第二级Cache中，第二级Cache的容量一般比第一级的大许多。如果第二级Cache只是稍大一点，局部失效率将很高。 如512 KB，1024 KB 相联度 第二级Cache可采用较高的相联度或伪相联方法。

4.4 减少Cache失效开销 例5.13 给出有关第二级Cache的以下数据： （1） 2路组相联使命中时间增加10%×CPU时钟周期 （2） 对于直接映象，命中时间L2 ＝ 10个时钟周期 （3） 对于直接映象，局部失效率L2 ＝ 25% （4） 对于2路组相联，局部失效率L2 ＝ 20% （5） 失效开销L2 ＝ 50个时钟周期 试问第二级Cache的相联度对失效开销的影响如何？

4.4 减少Cache失效开销 解 对一个直接映象的第二级Cache来说，第一级Cache的失效开销为： 失效开销直接映象，L1 ＝ 10＋25%×50 ＝ 22.5 个时钟周期 对于2路组相联第二级Cache来说，命中时间增加了10%（0.1）个时钟周期，故第一级Cache的失效开销为： 失效开销2路组相联，L1 ＝ 10.1＋20%×50 ＝ 20.1 个时钟周期 把第二级Cache的命中时间取整，得10或11，则： 失效开销2路组相联，L1 ＝ 10＋20%×50 ＝ 20.0 个时钟周期 失效开销2路组相联，L1 ＝ 11＋20%×50 ＝ 21.0 个时钟周期 故对于第二级Cache来说，2路组相联优于直接映象。

4.4 减少Cache失效开销 块大小 需要考虑的另一个问题： 可以采用增加第二级Cache块大小的方法来减少失效。前面已经得出这样的结论：增加Cache块的大小也增加了小容量Cache的冲突失效次数，导致失效率上升。但对于大容量的第二级Cache来说，这一点并不成为问题。而且由于访存时间相对来说较长，所以64B、128B和256B的块大小都是第二级Cache经常使用的。 需要考虑的另一个问题： 第一级Cache中的数据是否总是同时存在于第二级Cache中。如果是的话，就说第二级Cache具有多级包容性。多级包容性是我们期望的，因为它便于实现I/O和Cache之间内容一致性的检测。

4.4 减少Cache失效开销 为了减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。在这种情况下，仍可实现包容性，但在处理第二级Cache失效时要做更多的工作： 替换第二级Cache中的块时，必须作废所有对应于该块的第一级Cache中的块。这样不但会使第一级Cache失效率有所增加，而且会造成不必要的作废。如果结合使用其他一些性能优化技术（如非阻塞的第二级Cache），包容性会进一步增加复杂度。 综合上述考虑，Cache设计的本质是在快速命中和减少失效次数这两个方面进行权衡。大部分优化措施都是在提高一方的同时损害另一方。 对于第二级Cache而言，由于它的命中次数比第一级Cache少得多，所以重点就转移到了减少失效次数上。这就导致了更大容量、更高相联度和块大小更大的Cache的出现。

第4章 存储层次 4.5 减少命中时间 容量小、结构简单的Cache 虚拟Cache Cache访问流水化 第4章 存储层次 4.5 减少命中时间 命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率。 容量小、结构简单的Cache 虚拟Cache Cache访问流水化

4.5 减少命中时间 4.5.1 容量小、结构简单的Cache 采用容量小而且结构简单的Cache，可以有效提高Cache的访问速度。 4.5 减少命中时间 4.5.1 容量小、结构简单的Cache 采用容量小而且结构简单的Cache，可以有效提高Cache的访问速度。 用地址的索引部分访问标识存储器，读出标识并与地址进行比较，是Cache命中过程中最耗时的部分。 硬件越简单，速度就越快。 例如采用直接映象Cache。可以让标识检测和数据传送重叠进行，这样可以有效地减少命中时间。 应使Cache足够小，以便可以与CPU一起放在同一块芯片上。 某些设计采用了一种折中方案：把Cache的标识放在片内，而把Cache的数据存储器放在片外。 所以，为了得到高速的时钟频率，第一级Cache应选用容量小且结构简单的设计方案。

4.5 减少命中时间 4.5.2 虚拟Cache 虚拟Cache：使用虚拟地址的Cache。 4.5 减少命中时间 4.5.2 虚拟Cache 虚拟Cache：使用虚拟地址的Cache。 直接用虚拟地址访问Cache，在命中时消除了用于地址转换的时间。 实际设计中并非都采用虚拟Cache，原因： 当进程切换时，由于新进程的虚拟地址(有可能与原进程相同)所指向的物理空间与原进程不同，故需要清空Cache。 解决方法：在地址标识中增加PID (进程标识符)字段，这样，多个进程的数据可以混合存在同一Cache中，由PID指出Cache中各块的数据是属于哪个程序的。 为减少PID的位数，PID经常是由操作系统指定。对于一个进程，操作系统从循环使用的几个数字中指定一个作为其PID。进程切换时，仅当某个PID被重用（即该PID以前被分配给了某个进程，现又把它分配给另一个进程）时，才需清空Cache。

4.5 减少命中时间 图：采用PID所带来的失效率上的改进。 4.5 减少命中时间 图：采用PID所带来的失效率上的改进。 （图中数据在VAX机上针对Ultrix操作系统收集的，并假设Cache采用直接映象，块大小为16B） 单进程：没有进程切换； PIDs：允许进程切换并使用进程标识符（PIDs） Purges：允许进程切换但不使用进程标识符。 结论： 和单进程相比，PIDs的绝对失效率增加0.3%~0.6% 与Purges相比，PIDs的绝对失效率减少0.6%~4.3%

4.5 减少命中时间 对于同一物理地址,操作系统和用户程序可能使用两个不同的虚拟地址,这些双重地址称为同义(synonym)或别名(alias)地址。它们可能导致同一个数据在虚拟cache中存在两个副本。 解决办法： 反别名法：用硬件方法保证每个cache块有一个唯一的物理地址。 页着色：强行要求别名地址的某些地址位相同，用软件解决。

4.5 减少命中时间 另一种实现快速命中的技术是把地址转换和访问Cache这两个过程分别安排到流水的不同级中，从而使时钟周期加快，但这同时也增加了命中所需的时间。这种方法增加了访存的流水级数，增加了分支预测错误时的开销。 还有一种方法，既能得到虚拟Cache的好处，又能得到物理Cache的优点。它直接用虚地址中的页内位移（页内位移在虚实地址的变换中保持不变）作为访问Cache的索引，但标识却是物理地址。CPU发出访存请求后，在进行虚/实地址变换的同时，可并行进行标识的读取。在完成地址变换之后，再把得到的物理地址与标识进行比较。 其局限性在于直接映象的Cache的容量不能超过页的大小。

2index=Cache容量/（块大小×相联度） 4.5 减少命中时间 为了实现大容量的Cache，又能使索引位数比较少，以便能直接从虚拟地址的页内位移部分得到，可以采用提高相联度的办法。根据如下公式得出。如：IBM3033采用了16路组相联。 2index=Cache容量/（块大小×相联度） 也可以不提高相联度，由操作系统来实现页着色。 另一种方法：硬件散列变换：用一块硬件来猜测虚页地址的后几位映像到什么样的物理地址。

4.5 减少命中时间 4.5.3 Cache访问流水化 使第一级Cache命中的实际延可以分散到多个时钟周期 4.5 减少命中时间 4.5.3 Cache访问流水化 使第一级Cache命中的实际延可以分散到多个时钟周期 访问Cache需要多个时钟周期才可以完成 例如 Pentium访问指令Cache需要一个时钟周期 Pentium Pro到Pentium Ⅲ需要两个时钟周期 Pentium 4 则需要4个时钟周期 此方法可缩短时钟周期时间，但会减缓命中速度。增加了流水线的段数，增加了预测错误分支的代价，但更便于采用高相联度的缓存。

4.5 减少命中时间 4.5.4 Cache优化技术总结 “＋”号：表示改进了相应指标。 “－”号：表示它使该指标变差。 4.5 减少命中时间 4.5.4 Cache优化技术总结 “＋”号：表示改进了相应指标。 “－”号：表示它使该指标变差。 空格栏：表示它对该指标无影响。 复杂性：0表示最容易，3表示最复杂。

第4章 存储层次 优化技术 失效 率 开销 命中 时间 硬件 复杂度 说 明 增加块大小 +  第4章 存储层次 优化技术 失效 率 开销 命中 时间 硬件 复杂度 说 明 增加块大小 +  实现容易；Pentium 4 的第二级Cache采用了128 B的块 增加Cache容量 被广泛采用，特别是第二级Cache 提高相联度 1 被广泛采用 Victim Cache 2 AMD Athlon采用了8个项的Victim Cache 伪相联Cache MIPS R10000的第二级Cache采用 硬件预取指令 和数据 2～3 许多机器预取指令，UltraSPARC Ⅲ预取数据

第4章 存储层次 优化技术 失效 率 开销 命中 时间 硬件 复杂度 说 明 编译器控制 的预取 + 3 第4章 存储层次 优化技术 失效 率 开销 命中 时间 硬件 复杂度 说 明 编译器控制 的预取 + 3 需同时采用非阻塞Cache；有几种微处理器提供了对这种预取的支持 用编译技术减少Cache失效次数 向软件提出了新要求；有些机器提供了编译器选项 使读失效 优先于写  1 在单处理机上实现容易，被广泛采用 写缓冲归并 与写直达合用，广泛应用，例如21164，UltraSPARC Ⅲ 尽早重启动 和关键字优先 2 被广泛采用 非阻塞Cache 在支持乱序执行的CPU中使用

第4章 存储层次 优化技术 失效 率 开销 命中 时间 硬件 复杂度 说 明 两级Cache + 2 第4章 存储层次 优化技术 失效 率 开销 命中 时间 硬件 复杂度 说 明 两级Cache + 2 硬件代价大；两级Cache的块大小不同时实现困难；被广泛采用 容量小且结构简单的Cache  实现容易，被广泛采用 对Cache进行索引时不必进行地址变换 对于小容量Cache来说实现容易，已被Alpha 21164和UltraSPARC Ⅲ采用 流水化Cache 访问 1 被广泛采用

第4章 存储层次 4.6 主存 主存的主要性能指标：延迟和带宽 第4章 存储层次 4.6 主存 主存的主要性能指标：延迟和带宽 以往：Cache主要关心延迟（它影响cache的失效开销），I/O主要关心带宽。 现在：Cache关心两者（随着二级Cache 的广泛使用，主存带宽对于Cache来说也变得重要了，这是因为第二级Cache的块大小比较大的缘故。） 下面讨论几种能提高主存性能的存储器组织技术 我们以处理Cache失效为例来说明各种存储器组织结构的好处。

4.6 主存 在下面的讨论中，假设基本存储器结构的性能为： 送地址需要4个时钟周期 每个字的访问时间为24个时钟周期 4.6 主存 在下面的讨论中，假设基本存储器结构的性能为： 送地址需要4个时钟周期 每个字的访问时间为24个时钟周期 传送一个字（32位）的数据需4个时钟周期 如果Cache块大小为4个字，则 失效开销为4×（4＋24＋4）＝128个时钟周期 存储器的带宽为每个时钟周期1/8（16/128）字节

4.6 主存 增加存储器的宽度 性能举例 (参照前面的假设) 当宽度为4个字时： 失效开销＝1×32(周期) 带宽＝0.5(字节/周期) 4.6 主存 增加存储器的宽度 性能举例　(参照前面的假设) 当宽度为4个字时： 失效开销＝1×32(周期) 带宽＝0.5(字节/周期) 缺点： 增加CPU和存储器之间的连接通路的宽度，实现代价变高 CPU和Cache之间有一个多路选择器，因为CUP每次只访问一个字。 扩充主存的最小增量增加了相应的倍数 写入有可能变得复杂 举例： DEC的Alpha Axp21064：256位宽

4.6 主存 多字宽存储器结构，采用宽度较大的存储器总线和Cache。 单字宽的存储器结构：这是一种最简单的方案，所有部件的宽度都是一个字。

4.6 主存 采用简单的多体交叉存储器 在存储系统中采用多个DRAM，并利用它们潜在的并行性。 4.6 主存 采用简单的多体交叉存储器 在存储系统中采用多个DRAM，并利用它们潜在的并行性。 多体较长存储器结构：总线和Cache的宽度都较窄，但存储器按交叉方式工作。 把存储芯片组织为多个体，并让它们并行工作，从而能一次读或写多个字。 存储体的宽度通常是一个字，这样就无需改变总线的宽度和Cache。但同时向几个体发送地址能使它们同时进行读访问。

4.6 主存 性能举例：(参照前面的假设) 存储器的各个体一般是按字交叉的 失效开销＝4＋24＋4×4＝44(周期) 4.6 主存 性能举例：(参照前面的假设) 失效开销＝4＋24＋4×4＝44(周期) 带宽＝0.4(字节/周期) 存储器的各个体一般是按字交叉的 交叉存储器（interleaved memory） 通常是指存储器的各个体是按字交叉的 字交叉存储器非常适合于处理： Cache读失效（因为调块时块中的各个字是顺序读出的），写回法Cache中的写回（不仅读出是顺序的，写也是顺序的）

4.6 主存 地址到存储体的映象方法： 假设四个存储体的地址是在字一级交叉的，即存储 体0中每个字的地址对4取模都是0，体1中每个字的地址 4.6 主存 地址到存储体的映象方法： 假设四个存储体的地址是在字一级交叉的，即存储 体0中每个字的地址对4取模都是0，体1中每个字的地址 对4取模都是1，依此类推。 4 8 12 地址 体0 1 5 9 13 地址 体1 2 6 10 14 地址 体2 3 7 11 15 地址 体3

4.6 主存 例5.14 假设某台计算机的特性及其Cache的性能为： (1) 块大小为1个字； (2) 存储器总线宽度为1个字； (3) Cache失效率为3%； (4) 平均每条指令访存1.2次； (5) Cache失效开销为32个时钟周期； (6)平均CPI（忽略Cache失效）为2。 试问多体交叉和增加存储器宽度对提高性能各有何作用？

4.6 主存 如果当把Cache块大小变为2个字时，失效率降为2%；块大小变为4个字时，失效率降为1%。根据前面给出的访问时间，求在采用2路、4路多体交叉存取以及将存储器和总线宽度增加一倍时，性能分别提高多少？ 解 在改变前的计算机中，Cache块大小为一个字， 其CPI为： 2＋（1.2×3%×32） = 3.15 当将块大小增加为2个字时，在下面三种情况下的CPI分别为 32位总线和存储器，不采用多体交叉： 2＋（1.2×2%×2×32） ＝ 3.54

4.6 主存 32位总线和存储器，采用多体交叉： 2＋1.2×2%×（4＋24＋8）＝ 2.86 性能提高了10% 4.6 主存 32位总线和存储器，采用多体交叉： 2＋1.2×2%×（4＋24＋8）＝ 2.86 性能提高了10% 64位总线和存储器，不采用多体交叉： 2＋（1.2×2%×1×32） = 2.77 性能提高了14% 将块大小增加到4个字时，可以得到以下数据： 32位总线和存储器，不采用多体交叉： 2＋（1.2×1%×4×32） ＝ 3.54 2＋1.2×1%×（4＋24＋16）＝ 2.53 性能提高了25% 2＋（1.2×1%×2×32） = 2.77

4.6 主存 存储器中应该含有多少个体呢？ 向量计算机采用以下衡量标准： 体的数目 ≥ 访问体中一个字所需的时钟周期数 存储系统的设计目标 4.6 主存 存储器中应该含有多少个体呢？ 向量计算机采用以下衡量标准： 体的数目 ≥ 访问体中一个字所需的时钟周期数 存储系统的设计目标 对于顺序访问，每个时钟周期都能从一个存储体中送出一个数据。

4.6 主存 独立存储体 设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存。 例如 4.6 主存 独立存储体 设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存。 例如 一台输入设备可能会使用某个存控，访问某个存储体； Cache读操作可能在使用另一个存控，访问另一个存储体； Cache写操作则可能在使用第三个存控，访问第三个存储体。 每个体需要有独立的地址线和独立的数据总线。

4.6 主存 非阻塞Cache与多体结构 采用多体结构的另一个原因 共享公共存储器多处理机系统的需求 独立存储体和按字交叉的多体结合起来使用 4.6 主存 非阻塞Cache与多体结构 非阻塞cache允许CPU在cache失效时继续运行，这就潜在地允许多个cache失效被同时处理。这在多体才有意义。 采用多体结构的另一个原因 共享公共存储器多处理机系统的需求 独立存储体和按字交叉的多体结合起来使用 将存储器分为若干个独立的存储体； 而每个独立存储体内部又划分为若干个按字交叉方式工作的体。

4.6 主存 避免存储体冲突 体冲突：两个请求要访问同一个体。 减少体冲突次数的一种方法：采用许多体 4.6 主存 避免存储体冲突 体冲突：两个请求要访问同一个体。 减少体冲突次数的一种方法：采用许多体 例如，NEC SX/3最多可使用128个体 这种方法存在问题： 假如有128个存储体，按字交叉方式工作，并执行以下程序： int x [ 256 ][ 512 ]； for （ j = 0； j < 512； j = j+1 ） for （ i = 0； i < 256； i = i+1 ） x [ i ][ j ] = 2 * x [ i ][ j ]； 因为512是128的整数倍，同一列中的所有元素都在同一个体内，无论CPU或存储系统多么高级，该程序都会在数据Cache失效时暂停。因为对存储器中的数据访问不是随机的。

4.6 主存 解决体冲突的方法 软件方法(编译器) 循环交换优化 扩展数组的大小，使之不是2的幂,从而强制使上述地址落在不同的体内。 4.6 主存 解决体冲突的方法 软件方法(编译器) 循环交换优化 扩展数组的大小，使之不是2的幂,从而强制使上述地址落在不同的体内。 硬件方法 传统为计算简单，存储系统的体数和每个体的容量都取为2的幂。 使体数为素数 采用素数看起来似乎会需要更多的硬件来完成复杂的计算，但幸运的是，有几种硬件方法能快速第完成运算。

第4章 存储层次 4.7 虚拟存储器 4.7.1 虚拟存储器基本原理 虚拟存储器是“主存－辅存”层次进一步发展的结果。 第4章 存储层次 4.7 虚拟存储器 4.7.1 虚拟存储器基本原理 虚拟存储器是“主存－辅存”层次进一步发展的结果。 它由价格较贵、速度较快、容量较小的主存储器和一个价格低廉、速度较慢、容量很大的辅助存储器（通常是磁盘）组成。 应用程序员可以用机器指令的地址码对整个程序统一编址，就如同应用程序员具有对应于这个地址码宽度的存储空间一样，而不必考虑实际存储空间的大小。

4.7 虚拟存储器 虚拟存储器可以分为两类：页式和段式 4.7 虚拟存储器 虚拟存储器可以分为两类：页式和段式 页式虚拟存储器把空间划分 大小相同的块，称为页面。而段式虚拟存储器则把空间划分 为可变长的块，称为段。页面是对空间的机械划分，而段则往往是按程序的逻辑意义进行划分。 页式存储器中，地址都是单一、固定长度的地址字，由页号和页内位移两部分组成。而在段式虚拟存储器中，地址需要用两个字来表示，一个是段号另一个为段内位移。 页式和段式虚拟存储器各有优缺点，有些机器采用段式和页式的组合——段页式。段页式兼有两者的优点。 在段页式中，每段被划分为若干个页面。这样既保持了段作为逻辑单位的优点，又简化了替换的实现，而且段不必作为整体全部一次调入主存，而是可以以页面为单位部分调入。

4.7 虚拟存储器 有关虚拟存储器的四个问题 映象规则 4.7 虚拟存储器 有关虚拟存储器的四个问题 映象规则 在处理虚存失效时，需要访问磁盘存储设备，因此虚存失效开销非常大。如果要在低失效率和简单的替换算法之间进行选择的话，操作系统设计者总是选择低失效率，因为失效开销实在是太大。因此操作系统允许将块放在主存的任意位置，即采用全相联映象。

4.7 虚拟存储器 查找算法 页式和段式管理都要使用一个页号或段号作为索引的数据结构,这个数据结构分别称为页表和段表.这个数据结构中含有所要查找的块物理地址,对于段式系统,段内位移加上段的物理地址就是最终的物理地址。而对于页式系统，只需简单地将页内位移拼接在相应页面的物理地址之后即可。 用页表实现虚拟地址到物理地址的映射

4.7 虚拟存储器 页表用虚拟页号作为索引，它所包含的项数与虚地址空间的总页面数相同。 4.7 虚拟存储器 页表用虚拟页号作为索引，它所包含的项数与虚地址空间的总页面数相同。 如果虚地址为28b，页大小为4KB，每个页表项为4B，那么页表的大小就是256KB。 为减少地址转换时间，计算机常设置一个专门用于地址转换的高速缓存。这种高速缓存称为变换旁查缓冲器（Translation Lookaside Buffer，TLB）或地址变换缓冲器。

4.7 虚拟存储器 替换算法 操作系统一般替换最近最少使用（LRU）的页，因为这个页可能是最没有用的。 4.7 虚拟存储器 替换算法 操作系统一般替换最近最少使用（LRU）的页，因为这个页可能是最没有用的。 为了帮助操作系统寻找LRU页，许多机器为主存中的每个页面设置了一个使用位，也称为访问位。每当主存中的页面被访问时，其相应的使用位就被置“1”。操作系统定期地使所有使用位复位。这样，在每次复位之前，使用位的值就反映了从上次复位到现在这段时间中哪些页曾被访问过。通过这种方法跟踪各个页被访问的情况，操作系统就能选择一个最近最少使用的页。

4.7 虚拟存储器 写策略 主存的下一级是磁盘，磁盘的访问时间非常长，需上百万个时钟周期。正是由于这两级存储器之间访问时间的巨大差距，目前还没有一个虚拟操作系统 能在CPU执行store操作时将数据穿过主存直接写入磁盘，而且也不应该这么处理。因此，虚拟存储器总是采用写回策略。 由于访问下一级存储器的开销非常大，虚拟存储器通常使用“脏”位来保证只有被修改过了的块才被写回磁盘，这样就可避免对下一级存储器的不必要的访问。

4.7 虚拟存储器 4.7.2 快表（TLB） 页表一般都很大，它一般存放在主存中。因此每次访存都要引起对主存的两次访问：第一次是读取页表项，以获得索要访问数据的物理地址；第二次才是访问数据本身。显然，这在实际应用中时无法忍受的，性能受影响太大。 一般采用快表（TLB）来解决这个问题。 TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项；其内容是页表部分内容的一个副本。

4.7 虚拟存储器 这样，进行地址变换时，一般直接查TLB就可以了。只有偶尔在TLB不命中时，才需要去访问内存中的页表。TLB也利用了局部性原理：如果访存具有局部性，则这些访存中的地址变换也具有局部性，即所使用的页表项是相对簇聚的，TLB也常称为快表或地址变换缓冲器。 TLB中的项与Cache中的项类似，也是两部分构成：标识和数据。标识中存放的是虚地址的一部分，而数据部分则存放物理页帧号、有效位、存储保护信息以及其他一些辅助信息。为了使TLB中的内容与页表保持一致，当修改页表中的某一项时，操作系统必须保证TLB中没有该页表项的副本。

4.7 虚拟存储器 TLB采用全相联映象，当进行地址变换时，把虚拟地址送往各个标识，进行比较。 4.7 虚拟存储器 TLB采用全相联映象，当进行地址变换时，把虚拟地址送往各个标识，进行比较。 只有有效位为“1”的标识才有可能匹配。同时根据TLB中的存储保护信息对本次访存的类型进行检查，看是否越权。 若存在匹配的标识，则多路选择器把相应的TLB项中的物理地址选出。 该地址与页内位移拼接成完整的34位物理地址。 （包含32个项）

4.7 虚拟存储器 一般TLB比Cache的标识存储器更小，而且更快，这样才能保证TLB中的读出操作不会使Cache的命中时间延长。 4.7 虚拟存储器 一般TLB比Cache的标识存储器更小，而且更快，这样才能保证TLB中的读出操作不会使Cache的命中时间延长。 由于TLB的速度至关重要，所以有时TLB的访问按流水方式实现。

第4章 存储层次 4.8 进程保护 多道程序引出了进程的概念。一个正在运行的程序加上它继续执行所需的任何状态就是进程。 第4章 存储层次 4.8 进程保护 多道程序引出了进程的概念。一个正在运行的程序加上它继续执行所需的任何状态就是进程。 不管进程是不间断地从开始一直执行到结束，还是在执行过程中不断地被中断并与其他进程切换，它都必须被正确执行。计算机设计者必须保证进程状态中有关CPU的部分能够被保存和恢复，操作系统设计者必须保证进程之间的计算互不干扰。 进程切换一般由操作系统解决：将主存空间分为几个区域，同时存放多个不同进程的状态。 计算机设计者需提供一定的保护机制，使进程之间不能互相修改。

4.8 进程保护 检测条件： 最简单的保护机制是用一对寄存器来检查每一个地址，以确保地址在两个界限（基地址，上界地址）之间。 4.8 进程保护 最简单的保护机制是用一对寄存器来检查每一个地址，以确保地址在两个界限（基地址，上界地址）之间。 检测条件： 　　基地址≤地址≤上界地址 用户进程应不能改变基地址寄存器和上界地址寄存器，以保证用户进程不被其他进程所破坏；而操作系统必须能改变这两个寄存器，这样它才能够进行进程切换。因此，计算机设计者还要完成另外3项工作，以帮助操作系统设计者保护进程不被其他进程破坏：

4.8 进程保护 提供至少两种模式，用于区分正在运行的进程是用户进程还是操作系统进程 称后者为内核进程、超级用户进程或管理进程 4.8 进程保护 提供至少两种模式，用于区分正在运行的进程是用户进程还是操作系统进程 称后者为内核进程、超级用户进程或管理进程 使CPU状态的一部分成为用户进程可读但不可写。 这包括：基地址/上界地址寄存器 　　　用户/管理模式位 　　　异常许可/禁止位 提供一种机制，使得CPU能从用户模式进入管理模式和从管理模式进入用户模式

4.8 进程保护 虚拟存储器 给每个页或段增加许可标志 这种页面级保护可以通过增加用户/内核保护进一步扩展，以防止用户程序访问属于内核的页。 4.8 进程保护 虚拟存储器 给每个页或段增加许可标志 这种页面级保护可以通过增加用户/内核保护进一步扩展，以防止用户程序访问属于内核的页。 只要CPU提供读/写信号和用户/内核信号，地址变换硬件就能很容易地在非法的访存操作造成破坏之前检测到它们。

4.8 进程保护 环形保护 将保护进一步升级。如，在CPU保护结构中加入环，可将访存保护由原来的两级（用户级和核心级）扩展到更多级。 4.8 进程保护 环形保护 将保护进一步升级。如，在CPU保护结构中加入环，可将访存保护由原来的两级（用户级和核心级）扩展到更多级。 在同心圆环结构的级别中，最可靠的程序可以访问所有信息，第二可靠的程序可以访问除最高级以外的任何信息，以此类推。最后是“平民”级程序，它最不可靠，可访问的信息的范围也就最小。 此外，对哪些存储区能存放程序（即执行保护），甚至对各级别之间的入口点，也有一定的限制。

4.8 进程保护 加锁和解锁 仅有上述这种简单的环结构还不够，例如，当要对给定密级中的一个程序进行限制时，就要采用一种新的分级系统，这种系统类似于现实生活中的加锁和解锁。 一个程序只有在得到钥匙后，才能解锁并访问数据。 为了是这些钥匙起作用，硬件和操作系统必须能显式地将它们从一个程序传到另一个程序，以防止程序进行伪造。为了能实现钥匙的快速检测，需要很多的硬件支持。

第4章 存储层次 4.9 Intel Core i7中的存储器层次结构 第4章 存储层次 4.9 Intel Core i7中的存储器层次结构 i7支持x86-64指令集体系结构，它是80x86体系结构的64位扩展。 i7是包含四个核心的乱序执行处理器。每个核心采用一种多次发送、动态调度、16级流水线，每个时钟周期可以执行多达4个80x86指令。 i7还使用一种名为“同时多线程”的技术，每个处理器可以支持两个同时线程。 2010年，最快速的i7的时钟频率为3.3GHz，指令的峰值执行速度为每秒132亿条指令，四核芯片超过每秒500亿条指令。

4.9 Intel Core i7中的存储器层次结构 I7使用48位虚拟地址和36位物理地址，物理存储器容量最大为36GB。存储器管理用一个两级TLB处理。 特性 指令TLB 数据DLB 第二级TLB 大小 128 64 512 相联度 四路 替换 伪LRU 访问延迟 1个周期 6个周期 失效 7个周期 访问页表需要数百个周期

4.9 Intel Core i7中的存储器层次结构 I7中三级缓存层次结构的特性 特性 L1 L2 L3 大小 32KB I/32KB D 256KB 每个核心2MB 相联度 四路I/八路D 八路 十六路 访问延迟 4个周期、流水化 10个周期 35个周期 替换策略 伪LRU 伪LRU，但采用一种有序选择算法 所有这三级缓存都采用写回法，块大小都为64个字节。每个核心的L1和L2缓存分离，而L3缓存在一个芯片的所有核心之间共享，每个核心总共2MB。 所有这三级缓存都是非阻塞的，允许存在多个未完成写入。 为L1缓存使用一个合并写缓冲区，在要写入数据但L1中没有该块时，用这个缓冲区保存数据。（即一次L1写失效不会调块。）

4.9 Intel Core i7中的存储器层次结构

4.9 Intel Core i7中的存储器层次结构