第五章 存储器层次结构

第五章 存储器层次结构 第五章 存储器层次结构 存储器是计算机系统的核心组成部分。本章介绍存储器层次结构(memory hierarchy)的基本概念和原理，讨论和 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 如何利用局部性原理提高Cache/主存存储器层次结构、虚拟存储器(主存/辅存存储层次)的性能。最后以Alpha机的存储系统为实例综合介绍存储体系的工作过程。 5.1存储器层次结构的基本概念 5.1.1存储器的基本性能参数 评价存储器性能的参数主要有三个方面:容量、速度与价格。 存储器容量用S=W×l×m 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示，W为存储器字长，l为存储器字数，m则为存储器体数。评价存储器的速度一般有以下几个参数: 访问时间(access time)Ta:从存储器接到读请求到所读的字传送到数据总线上的时间间隔。 存储周期Tm:连续两次访问存储器之间所必需的最小时间间隔。一般Tm > Ta。 存储带宽Bm:存储器被连续访问时所提供的数据传输速流，单位是位(或字节)/秒。 存储器的价格通常用单位字节价格来表示。若总容量为S的存储器的总价格为C，则单位字节价格c,C/S。 5.1.2存储器层次结构的基本原理 程序设计人员总是希望存储器的速度尽可能的高，以与处理器的速度相匹配;存储器的容量尽可能的大，以装下可能极大的程序;因此，高速度、大容量、低价格始终是存储体系的设计目标。 一方面，经过几十年的发展，存储器的工艺实现技术有了突飞猛进的发展，高速、大容量、低价的存储器件以惊人的速度生产出来。尽管如此，存储技术的发展证明单一工艺的单一存储器很难同时满足容量、价格、速度三方面的性能要求(见图5.1存储器的速度与价格的关系曲线)。事实上，对容量与速度、速度与价格、容量与价格的性能要求是相互有矛盾的。而且，存储器速度的改进始终跟不上CPU速度的提高 。 图5.1 存储器的速度与价格的关系曲线 另一方面，第一章中我们已介绍了局部性原理，即所有程序都具有这样的行为特性:程序倾向于再次使用最近刚用过的数据和指令。这样的局部性反映在空间和时间两个方面。 空间局部性(spatial locality)((如果某个数据或指令被引用，那么地址邻近的数据或指令不久很可能也将被引用。 时间局部性(temporal locality)((如果某个数据或指令被引用，那么不久它可能还将再次被引用。 为了满足对存储器的性能要求，随着存储技术的不断发展，根据程序本身这种局部性的行为特性以及小硬件速度更快的设计原则，基于不同容量和速度的多种存储器所构成的存储器层 5-1 第五章 存储器层次结构 次结构很自然地就产生了，如图5.2。一个存储器层次结构由多级不同类型的存储器构成;越靠近CPU的存储器容量越小、速度越快、价格越高，离CPU越远的存储器容量越大、速度越慢、价格越低;第,级存储器存储的信息是第,,,级存储信息的子集(根据时间局部性)，相邻两级存储器之间以块为单位进行信息交换(根据空间局部性);各级存储器借助辅助软硬件构成一个整体，使得该存储体系具有接近于第,级存储器速度、接近于第,级存储器容量和单位字节价格的性能。 图5.2 存储器层次结构 存储器层次结构是由多级存储器构成的，但管理是以两级存储器为单位来进行的，而且一般只有在相邻两级存储器之间可以进行信息交换。下面以两级存储器层次结构(简称存储层次，如图5.3为例介绍存储器层次结构的一些基本概念。 块(block):相邻两级存储器之间信息交换的最小单位。块大小一般是固定的，也可以是可变的。若块大小固定，则两级存储器的容量为块大小的整数倍。 图5.3 两级存储器层次结构 命中率(hit rate)H:CPU产生的有效地址可以直接在高层存储器中访问到的概率。 失效率(miss rate)M:CPU产生的有效地址直接在高层存储器中访问不到的概率。M,,,H。 命中时间(hit time):访问高层存储器所需的时间，其中包括本次访问是命中还是失效的判定时间。 失效损失(miss penalty):用低层存储器中相应的块替换高层存储器中的块，并将该块传送到请求访问的设备(通常是CPU)的时间。它又可细分为访问时间和传送时间(transfer time)两部分。其中前者指访问高层存储器失效时，在低层存储器中访问到块中第一个字的时间，又称访问延迟(access latency)。后者则是传送块内其它字的附加时间。访问时间与低层存储器的延迟有关，而传送时间则依赖于两级存储器之间的传输带宽和块大小。 5.1.3存储器层次结构的性能 由于存储器层次结构的设计目标之一是使其速度接近于高层存储器的速度，因此容易根据命中率的高低来评价存储器层次结构性能的好坏。由于命中率或失效率与硬件速度无关，因而这样的评价是很片面的。更好的评价存储器层次结构的性能参数是平均存储访问时间(average memory-access time)，其定义如下: 平均存储访问时间,命中时间 ， 失效率 × 失效损失 应该注意的是尽管用平均存储访问时间评价存储器层次结构的速度性能比简单的用命中率来评价要好，平均存储访问时间仍然是性能的一种间接测度，它无法完全替代执行时间这个最准确的性能参数。 图5.4给出了块大小与失效率、失效损失之间的关系曲线(假设高层存储器的容量保持不变)。 图5.4 块大小与失效率、失效损失之间的关系 5-2 第五章 存储器层次结构 由图5.4(,)可见失效率与块大小之间的关系呈现三种不同性质:(,)当块大小过小时，失效率很高。随着块大小的增加，由于有效地利用了程序的空间局部性，失效率呈现下降趋势;(,)当高层存储器容量保持不变时，失效率有一最低限值，此时块大小的变化对失效率没有影响;(,)当块大小超过某定值后，(这一定值又称为污染点)，失效率呈现随块大小增加而上升的趋势，这是由于在高层存储器容量不变的情况下，增加块大小使高层存储器中的块数减少，对利用程序的时间局部性不利:有用的信息(不久将再次被使用的信息)被大块中的无用信息替换出去，造成失效率上升。 由于失效损失中的访问延迟部分与块大小无关，传送时间随块大小的增加而线性增长，因此失效损失也将随块大小的增加而线性增长，如图书5.4(,)。当访问延迟很大时，增加块大小对失效损失的影响不大。综合考虑块大小对失效率及失效损失的影响后，块大小与平均存储访问时间的关系见图5.5。 图5.5 块大小与平均存储访问时间的关系 设计存储器层次结构的根本目标是为了减少执行时间，因此在确定块大小时，不能以失效率为标准，而应选择使平均访问时间最小的块大小。 5.1.4存储器层次结构对CPU设计的影响 处理器的性能是计算机设计的最终依据，所以在选择降低平均存储访问时间的策略时应考虑对CPU性能的影响，保证设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 不仅能降低平均存储访问时间，还能有益于改进CPU的性能，如同时提高CPI。下面讨论一下存储器层次结构设计对CPU设计的影响。 在不支持存储器层次结构的系统中，由于所有的存储访问都需要相同的时间，所以处理器的设计相对简单。而在存储器层次结构中对高层存储器的访问存在失效问题，这意味着CPU必须能够处理可变的存储访问时间。当失效损失较小，只有几十个时钟周期时，CPU通常采用等待块传输结束的策略。而当失效损失很大，达到CPU时钟的几千倍时，仍让CPU空闲着等待传输结束就太浪费了。一般采用中断使CPU切换到其它进程去执行的办法。但用这种方法来避免失效损失带来的额外开销意味着任何存储访问都可能导致CPU中断。这样CPU还必须能够恢复引起这种中断的存储地址，使系统在失效处理时知道要传送哪一块。当存储传送结束时，恢复原来被中断的进程，重新执行引起访问失效的那条指令。 处理器还必须设有一些机制以确定所需信息是否在存储器层次结构的最高层存储器中。在每次存储访问时都要作这种判定检查，因而会影响命中时间。为了保证达到可接受的性能，这种检测机制通常用硬件实现。要实现存储器层次结构，处理机还必须有在相邻两级存储器之间传送信息块的机制。如果块传送只需几十个时钟周期，那么这种传送机制一般用硬件来控制;如果需要几千个时钟周期，则可以用软件方法实现。 5.1.5存储器层次结构设计的基本问题 由于所有的存储器层次结构几乎都有相同的设计目标，遵循相同的设计原则，所以在考虑设计某二级存储器构成的存储器层次结构时所需考虑的基本问题是一致的。下面是存储器层次结构设计中的四大基本问题: (,)映象方式:在低层存储器中的块以什么方式与高层存储器中的块相对应，即每个低层存储器的块按什么规则装入高层存储器。 5-3 第五章 存储器层次结构 (,)映象机构:是映象方式的实现。如果某信息块在高层存储器中，如何识别与查找它。 (,)替换策略:发生访问失效而高层存储器所有可能对应块中不存在无效的块，此时根据什么规则选择有效信息块将之淘汰出高层存储器，而换之以从低层存储器中传送来的新块。 (,)写策略:写操作时采用何种策略以保持相邻两级存储器中数据的一致性，发生写操作失效时是否将被写的块从低层存储器取入高层存储器。 我们将从这四个方面来介绍Cache,主存存储器层次结构和虚拟存储器，以及由它们在存储体系中所处的层次所决定的一些特性和性能优化方法。 5.2 Cache,主存存储器层次结构 在现代计算机设计中几乎全部采用了Cache技术，这是因为在CPU与主存之间引入Cache，有效地解决了CPU与主存之间的速度匹配问题。由Cache与主存构成的存储器层次结构具有两级存储器层次结构的一般特点，在,(,(,中介绍的基本概念在此也同样适用，只是在Cache,主存存储器层次结构中块的概念常用行(line)来表示。有关Cache,主存存储器层次结构的一些基本结构参数的典型范围见表,(,。 表,(, Cache基本结构参数 5.2.1 Cache,主存的映象方式 最基本的Cache,主存映象方式有三种: (,)直接映象(direct mapped):这是最简单的一种映象方式。主存中的一信息块只能对应 CbCache的一个特定行，如图5.6。设Cache中共有m,2行，主存共分为,,块，通常按下列规则将主存中的第,块映象到Cache中的第,行: Cb ,,, ,,, 2 图5.6 直接映象 (,)全相关映象(fully associative):主存中的一信息块可对应Cache中的任意一行，如图5.7所示。 图5.7 全相关映象 q (,)组相关映象(set associative):将Cache的行分成若干组，不妨设为,组，,,2， C()Cq,ebb2则每组中有,,22,,,,行。主存中的第,块可以对应Cache中的某一特定组(一般是第(, ,,, ,)组)中的任意一行。若组中有,行，则称之为,路组相关映象。组相关映象方式示意图见图5.8。 5-4 第五章 存储器层次结构 图5.8 组相关映象 容易看出，直接映象与全相关映象都是组相关映象方式的特例:直接映象即,路组相联， Cb而全相关映象为,路组相联(,,)。 2 5.2.2 Cache,主存的映象机构 映象机构的功能是根据CPU送来的有效主存地址确定要访问的信息是否在Cache中，并找到该信息块，也即它是映象方式的具体实现。 由于无论采用哪种映象方式，Cache中的某一行总是对应于主存的多个块，即Cache中的某信息行其来源可以是主存中的多个块。因此，Cache中的每行都带有一个标志(tag)以确定该行所对应的主存块。Cache中存放标志的那部分存储器称为标志存储器。每个Cache的标志中可以包含一些特定信息，根据这些特定信息可以检测他们是否和来自CPU的块帧地址相匹配。存放标志的那部分存储器称为标志存储器。由于主存中的某一块可映象到Cache中的多个块(除直接映象外)，而且对Cache,主存存储器层次结构来说，速度性能是至关重要的，因而来自CPU的主存地址是和Cache中所有可能对应行的标志同时作相联比较，以快速找出相匹配的块，如图5.9 所示。 图5.9 映象机构示意图 为确定Cache行中所含信息是否有效，通常还在行标志中添加一个有效位(valid bit)，指明行中信息是否有效。如果未置有效位，则该行的标志不能与主存地址匹配。 在估算Cache成本时，标志存储器的成本容易被忽略。因为每个Cache行都带有一个标志，所以增加块大小有益于减少标志成本在Cache总成本中所占的比例。 下面，我们考虑如何由CPU地址在Cache中判定其要访问的信息块。如图5.10，来自CPU的主存物理地址由两部分组成:居地址高端的块帧地址(block-frame address)和低端部分的块内 w偏移地址(block-offset address)。其中块内偏移地址用于从块内选取所需字节(设块大小为2字节);块帧地址(,,位)在组相联方式下又分成二部分:索引(index)用于选取组，标志(tag)用 q2于和Cache中的行标志进行比较。当CPU给出一地址后，首先由索引确定组之一，然后地 e2址标志和该组中的所有行标志(共个，每个,,,？位)进行相联比较。若有相同的且有效位被置位，则表示相应信息块在Cache中，命中Cache后由块内偏移地址确定要访问的具体字节。否则Cache失效。 图5.10 CPU地址组成 如果Cache的容量、块大小保持不变，增加相联度意味着增加组内行数，此时组数减少，引起索引位数减少而标志位数增加，在图5.10中表现为标志,索引界限向右移动。极端情况下 Cb2即为全相联方式的映象机构:此时参与相联比较的共有个行标志，标志宽度为,,位。相 5-5 第五章 存储器层次结构 反，减小相联度则引起索引位数增加而标志位数减少，极端情况下就是直接映象方式的映象机构:此时参与相联比较的只有一个行标志，宽度为(,,,,,)位。易知，在Cache容量、块大小一定的情况下，相联度越高，Cache块冲突率、失效率越低，而映象机构的实现越复杂、成本越高。从性能折衷权衡考虑，组相关映象方式是一种较好的选择方案。当然更精确的办法是用典型工作负载作软件模拟，进行量化性能分析，这部分内容将在第5.2.6节中讨论。 5.2.3 Cache,主存的替换策略 当访问Cache失效时，如果相应的组中存在无效数据行(该行的有效位未置)，此时不存在替换问题。否则必须采取某种策略选择一有效数据行将其淘汰出Cache，而换之以从主存送来的数据块。Cache替换策略非常重要，它将直接影响Cache的命中率。 对于直接映象方式而言，实现替换策略的硬件机制相对较简单。事实上，此时不存在选择问题，因为参与地址匹配的只有一个行标志，所以发生失效时只能对这一特定行进行替换。但是，对于全相联和组相关映象，发生Cache失效时，如果组中不存在无效的数据行，就需要在多个有效数据行中进行选择。基本的替换策略有以下三种: (1)随机替换策略(RAND)——随机地在候选行中选择一行进行替换。由于完全随机的选择将给硬件调试带来很大的困难，因此，为使替换行为可再现以利调试，一些系统实际上采用的是伪随机替换策略。这种策略没有利用数据行的“历史”使用信息，不反映程序行为的局部性。 (2)先进先出策略(FIFO)——在候选块中选择最早送入Cache的那一行进行替换。它利用了数据行的“历史”使用信息，但不能正确反映程序局部性，因为最早进入Cache的块很可能是经常被引用的块。 (3)最近最少使用策略(LRU)——在候选块中选择最近最少被访问到的那一行进行替换。这种策略是利用程序局部性原理的必然结果:因为最近使用过的块很可能不久再次被引用。为减少可能再次被引用的块替换出去的机会，最佳候选块只能是最近最少使用的块。要实现LRU策略，就必须记录行被访问的情况。图5.11给出了在全相关映象的存储器层次结构中，对于某一块帧地址序列，使用LRU策略选择的替换块号。假设Cache分为4个块，而且开始时最近最少使用的块是块0。 图5.11 LRU替换策略示意图 尽管FIFO策略利用了数据块使用的“历史”信息，但实验数据表明RAND策略的性能一般要比FIFO策略要好。而且RAND最重要的特点是简单，易于用硬件实现。一般说来，LRU策略的性能要好于RAND，但随着要记录访问情况的块数增多，实现LRU策略的成本迅速增加，此时性能改进却不明显。表5.2列出了不同Cache容量、不同相联度情况下，使用LRU策略和RAND策略时Cache失效率的对比实验数据。由图中最后一行数据可知:当Cache容量达256KB时，采用何种替换策略对失效率几乎没有影响。因此可见:与大容量Cache相比，替换策略对小容量Cache的性能影响更大。 表5.2 替换策略对Cache失效率的影响 5.2.4 Cache/主存的写策略 所有的取指访问是读操作，而大部分指令不对存储器进行写操作, 所以，对于Cache的访问主要是读操作。根据第三章指令使用频度分析数据可知，一般程序的数据传送指令中，取数 5-6 第五章 存储器层次结构 操作(Load)大约是存数操作(Store)的2倍(,Fig4.34中，Load 指令占18%，Store指令占9%)，而且在存储器数据传送(memory transfer )中，写操作所占比例不到10%。根据高频事件高速处理的设计原则，在Cache中应尽量优化读操作的能力，同时由Amdahl定律可知，面向高性能的设计不能忽视写操作的速度。 通常，Cache的读操作较易快速实现。一般，在读取并比较标志的同时就可以读取相应数据行，即一得到来自CPU的块帧地址就可以开始读操作。如果读命中，则读出的数据行立即送往CPU，而如果读失效，读出的数据作废，这样作既没好处，也没损失。 写操作的情况就不同了。处理器指定写操作的数据宽度一般在1,8字节之间，即一个写操作仅改变一个数据块某一部分的内容。通常写操作又细分为三个步骤:(1)读取源数据块;(2)修改其中的一部分;(3) 写回修改后的数据。因为修改步骤不能与标志检查并行进行，所以一定要等标志检查确定命中后才能进行修改步骤。这样，写操作所需的时间通常比读操作长。 在Cache设计中有多种不同的写策略，基本的写策略有如下两种: (1)直写技术(write through)——信息被写入Cache行的同时，利用CPU和主存之间的直接数据通路写入主存的对应块中。 (2)回写技术(write back)——信息只写入Cache的相应行。仅当被修改过的行被替换出Cache时，才将它写入主存的相应存储块中。 根据Cache行的信息与对应主存块中的信息相同与否，采用回写技术的Cache行被分为“干净的”或“脏的”两种。“干净的”行即该数据行在Cache中未被修改过，数据与其主存中的对应块相同。而“脏的”行即该数据块在Cache中已被修改过。因此当“干净的”行被替换出Cache时，不必将该行写回主存。相反，当“脏的”行被替换时，必须将其写回主存。为区分行是“干净的”还是“脏的”，通常为每个Cache行设置一个称为“脏位”(也称“修改位”)的标志位，指示该Cache行是否曾被修改过。 回写技术和直写技术各有利弊。回写技术的优点是:Cache命中时，写操作是以写Cache的速度进行，而且在一个数据块内的多次写操作只需要对低层存储器写一次。由于每个写操作都不必写主存，因而回写技术有利于降低Cache/主存存储器层次结构对主存带宽的要求。这一性质使回写技术在多处理器(机)系统设计中颇具吸引力。对于直写技术，读操作引起的Cache失效不会导致对低层存储器的写操作，而且直写技术的硬件实现更为简单。直写技术的另一个优点是主存中总是保存着数据的最新拷贝，这一性质对I/O和处理器(机)系统都非常重要，我们将在5.2.7以及第,章再加以讨论。这样，在多处理器(机)系统的设计中，既希望利用回写技术减少每个处理器(机)与主存之间的数据传输量，又希望用直写技术保证Cache和主存的一致性。 如果采用直写技术，那么在对低层存储器的写操作期间，CPU必须停下来等待，CPU的这段等待时间被称为写停顿延迟。通常所用的减少写停顿延迟的办法是设置写缓冲，使CPU在存储器更新期间能继续工作。但设置写缓冲也不能完全避免写停顿，这一点我们将在5.2.7中再讨论。 当出现写失效时，无论直写技术还是回写技术都存在是否要将修改的数据块装入Cache的问题，一般有两种选择方案: (1)写分配(write allocate)——将要写的数据装入Cache，然后进行和写命中时相同的操作。这种方法与读失效时的处理方法类似。 (2)无写分配(no write allocate)——也称为绕写(write around)。直接对低级存储器中的数据块做改写操作，不再将此数据块装入Cache。 虽然这两种方案对直写技术或回写技术都适用，但通常的做法是在采用回写技术时选择写分配，这样对该数据块的后续写操作可以在Cache中进行(时间局部性原理的自然应用);采用直写技术时一般选择无写分配，因为按直写技术，即使该数据块有后续写操作仍需对主存作改写操作。 5-7 第五章 存储器层次结构 5.2.5 Cache/主存存储器层次结构实例 本节将以VAX-11/780的Cache为例具体介绍Cache/主存存储器层次结构的结构，并介绍其工作流程。 VAX-11/780的Cache的容量为8KB(8192字节)，块大小为8字节，映象方式是2路组相联，采用随机替换策略及直写技术，配有1个字(4字节)的写缓冲，写失效时采用无写分配方法。VAX-11/780的Cache结构如图5.12所示。 图5.12 VAX-11/780的Cache结构 如图5.12，当Cache读命中时，Cache的工作流程可分为五大步骤，这五个步骤是在一个CPU时钟周期内完成的。 (1)来自CPU的地址被分为29位块帧地址和3位块内偏移地址，块帧地址又分成20位标志和9位索引。 (2)根据索引选择Cache中的一个组，读取组内各行标志以判定要访问的数据块是否在Cache中。图中512组中的0号数据块组成模块0(bank0)，而1号数据块组成模块1(bank1)。索引被同时送往两个模块，读取该组中两个数据行的行标志。索引的位数是由Cache容量、块大小及相联度决定的，表达式如下: Cache容量 8192 组数 = ————————— = ———— = 512 = 29 行大小 * 相联度 8 * 2 (3)块帧地址的标志域与步骤(2)中读取的两个行标志作相等比较。为保证相应行的数据有效，对应的有效位必须是被置位的，否则比较结果无效(被忽略)。 (4)假设有一行标志与块帧地址的标志相匹配，则由2选1多路转换器选取相应的数据行。二个行标志同时匹配的情况是不可能发生的，因为替换算法保证了一个数据块只有一个行标志。为减少 命中时间，数据读取是与读取行标志同时进行的，所以当多路转换器就绪时，数据也已准备好了。这一步骤在组相联的Cache中是不可少的，但在直接映象Cache中，因为不必选择数据行，所以本步骤可以省去。由于多路转换器可能处在关键的定时路径(timing path)上，因而可能影响(危及)CPU的时钟周期。在下面的例3中我们将对这种影响作定量分析。 (5)读出的字送往CPU。 读Cache失效时，Cache向CPU发出一个停顿(stall)信号通知CPU等待，并从主存中读入2个字(8字节)。在VAX-11/780上这需要6个时钟周期(忽略总线干扰(bus interference))。从主存读取的数据块送达时，Cache要选择一个数据行替换出去，VAX-11/780的Cache采用随机替换策略，即当组中二个数据行均为有效行时随机选取一行替换出去。替换数据块意味着更新该行的数据、地址标志和有效位。完成这些工作后Cache再经过一个常规的读命中周期，将读取的数据送往CPU。 与其他任何Cache一样，VAX-11/780的写操作比读操作更为复杂。如果写命中，那么前四步操作与读命中时完全一样，第五步则是修改数据块，并将数据更新部分写入Cache相应行。由于VAX-11/780在写失效时采用无写分配方法，因而一旦发生写失效，CPU将绕过Cache直接将数据写入低层存储器。 由于VAX-11/780采用直写技术，并配有一个字长的写缓冲，因而在把数据送往低层存储器时实际是将数据字送往写缓冲。若写缓冲是空的，则数据与地址被写入缓冲，整个写操作就完成了。在写缓冲将数据送往主存的同时，CPU可继续其工作。但如果写缓冲是满的，此时Cache和CPU必须等待，直到缓冲为空才能将数据写入，完成写操作。 5-8 第五章 存储器层次结构 5.2.6 Cache/主存的性能分析 一、Cache对处理器性能影响的定量分析 CPU时间可以细分为CPU执行程序所需的时间和等待存储系统的时间，即可表示为: CPU时间 = (CPU执行时钟周期数 + 访存停顿时钟周期数)× 时钟周期 为了简化Cache/主存的性能评估，有时往往假设:所有的访存停顿延迟都是因Cache失效引起的(由5.2.4节可知，写命中时采用直写技术对主存的写操作会引起写停顿)。这样假设的根据是:(1)对很多计算机来说情况确实和假设的一致;(2)尽管访存停顿不完全是由Cache失效引起的，但绝大部分是由Cache产生的，因为Cache是引起访存停顿的最重要的原因。在本节的讨论中，我们将采用这一假设，但需说明的是要计算CPU的最终性能必须考虑所有访存停顿情况。 上述CPU时间的计算公式要求我们必须明确CPU访问Cache所需的时间应算入哪一部分:CPU执行时钟周期还是访存停顿时钟周期。尽管将访问Cache的时间归入哪一部分都各有理由，普遍为设计者所接受的是将Cache命中所需的时钟周期包括在CPU执行时钟周期内，而将Cache失效所需的时间算入访存停顿延迟。这样访存停顿时钟周期就可以根据每个程序的访存次数、失效损失(以时钟周期为单位)以及读写Cache的失效率来计算，公式如下: 访存停顿时钟周期数 = 读操作次数 × 读失效率 × 读失效损失 + 写操作次数 × 写失效率 × 写失效损失 将读写操作合并在一起考虑，上述公式可简化为: 访存停顿时钟周期数 = 访存次数/程序 × 失效率 × 失效损失 如果把指令总数(IC)从执行时间和访存延迟时间里提出来，则原CPU时间计算公式就化成了用指令的平均访存次数、失效率、失效损失描述的新公式: CPU时间 = IC × (执行CPI + 访存次数/程序 × 失效率 × 失效损失)× 时钟周期 有些设计人员也常用一条指令产生失效的概率来测量Cache的失效率，而不是一次访存产生失效的概率，即: 失效率/指令 = 访存次数/指令 × 失效率 这种失效率测量公式的优点是它和硬件的具体实现无关。例如，在VAX-11/750中设置了8字节的指令预取缓冲器(IB)，只要IB一有空闲字节(可能只是一个字节)，它就会发出读请求，而一次读操作是从存储器中读取一个边界对齐的32位字。因此一个32位的指令字有可能一次或分四次才能从存储器取到IB中，即指令部件可能重复访问单一字节。这样，如果以一次访问产生失效的概率来测量失效率，就可以人为地降低失效率。但这种表示也有缺点:它依赖于机器的体系结构。所以这种测量公式适用于衡量某一系列机的Cache失效率。以此公式为基础，我们又可以导出CPU时间的另一公式: CPU时间 = IC × (执行CPI + 失效率/指令 × 失效损失)× 时钟周期 根据上述计算公式，下面我们以几个实例来说明如何对Cache/主存存储器层次结构作定量性能分析。 例5-1 在VAX-11/780机上，Cache的失效损失为6个时钟周期，不考虑访存停顿延迟时所有 5-9 第五章 存储器层次结构 指令的平均执行时间为8.5个时钟周期。假设Cache失效率为11%，并且每条指令平均有3.0次访存。定量计算这种Cache/主存存储器层次结构对CPU性能的影响程度。 [解答] 不考虑访存停顿的CPU时间 = IC × 执行CPI × 时钟周期 = IC × 8.5 × 时钟周期 考虑访存停顿的CPU时间 = IC × (执行CPI + 访存停顿时钟周期/指令)× 时钟周期 = IC ×(8.5 + 3.0 × 11% × 6 ) × 时钟周期 = IC × 10.5 × 时钟周期 考虑访存阻塞的时间CPU ,124.不考虑访存阻塞的时间CPU 所以Cache/主存存储层次对性能的影响是使CPI由8.5增加到了10.5，CPU时间增大了24%。 例5-2 本例考虑Cache/主存对于CPI较小的处理器所产生的性能影响。假设Cache的失效损失为10个时钟周期，每条指令平均需要1.5个时钟周期的执行时间;Cache失效率仍为11%，并且每条指令平均访存1.4次。 [解答] 考虑访存停顿的CPU时间 = IC × (执行CPI + 访存停顿时钟周期/指令)× 时钟周期 = IC ×(1.5 + 1.4 × 11% × 10 ) × 时钟周期 = IC × 3.0 × 时钟周期 考虑访存阻塞的时间CPU ,200.不考虑访存阻塞的时间CPU 所以Cache失效使CPI从1.5变成了3.0，CPU时间增大了一倍。 由上述两例可知，Cache/主存存储器层次结构对处理器性能有着重要甚至是巨大的影响。我们可以得出以下三个结论: (1)CPI越小，Cache/主存对CPU性能的影响越大; (2)因为主存一般是用相同的存储器芯片实现的，并且独立于CPU，所以不同计算机的主存通常有着相近的访存时间。但在计算CPI时，Cache的失效损失是以CPU时钟周期为单位来计算的， 因而尽管主存有着相同的访存速度，较高的CPU时钟频率将导致较大的失效损失; (3)对于CPU时钟频率较高、CPI较小的处理器，如RISC处理器，Cache失效时对性能的影响是极严重的。所以在设计此类处理器时必须尽量降低Cache的失效率，同时在评估此类处理器的性能时绝对不可忽略Cache失效所造成的影响。 因为降低存储器层次结构的平均访问时间是我们的设计目标，本章的大部分将用平均存储访问时间来评价存储器层次结构的性能。但是必须明确:最终的设计目标是减小CPU时间。 例5-3 不同的Cache结构对CPU的性能会产生怎样的影响呢,假设CPI为1.5个时钟周期，时钟周期为20ns;每条指令平均需要访存1.3次;两种Cache的块大小均为64KB;近似假定两种Cache的失效损失相同，都需200ns(实际上失效损失一定要取为时钟周期的整数倍)。一种Cache采用直接映象方式，而另一种则用组相关映象方式。因为CPU速度直接受Cache速度的影响，所以假定组相联Cache中应多路选择器(见5.2.5节中图5.12步骤4)的需要，CPU时钟周期必须延长8.5%。计算平均存储访问时间和CPU时间。 5-10 第五章 存储器层次结构 [解答] 由表5.3可知:64KB直接映象的Cache的失效率为3.9%，而64KB二路组相关映象的Cache的失效率为3.0%。根据平均存储访问时间的计算公式: 平均存储访问时间 = 命中率 + 失效率 × 失效损失 得二种Cache/主存存储器层次结构的平均存储访问时间: (直接映象) 平均存储访问时间 = 20 + 3.9% × 200 = 27.8 (ns) (二路组相联)平均存储访问时间 = 20 ×(1 + 8.5% )+ 3.0 × 200 = 27.7(ns) 所以从平均存储访问时间看，题中二路组相联的Cache结构的性能要稍好些。 由CPU性能的计算公式: CPU时间 = IC ×(执行CPI + 失效率/指令 × 失效损失)× 时钟周期 = IC ×(执行CPI × 时钟周期 + 访存次数/指令 × 失效率 × 失效损失 × 时钟周期) 且已知失效损失 × 时钟周期 = 200ns，所以可得: (直接映象) CPU时间 = IC ×(1.5 ×20 + 1.3 ×3.9% ×200 )= 40.1×IC (二路组相联)CPU时间 = IC ×(1.5 ×20 ×(1 + 8.5%)+ 1.3 ×3.0% ×200)=40.4×IC 与平均存储访问时间所得性能评价的结果相反，从CPU时间角度看，题中直接映象的Cache结构性能更好些。由于CPU时间是我们的最终性能评价标准，而且直接映象的硬件实现更简单，所以在本例的两个设计方案中，直接映象的Cache结构的设计方案更好。 二、Cache失效原因分析 按导致Cache失效的原因划分，Cache失效可分成以下三类: (1)被迫失效(compulsory miss)——第一次访问存储块时，由于该块不在Cache中，所以必须首先将此存储块从主存取入Cache中。这样引起的失效也称为冷启动失效(cold start miss) 或首次访问失效(first reference miss)。 (2)容量失效(capacity)——如果Cache不能容纳程序执行过程中所需的所有存储块，那么当程序再次访问到曾装入Cache又已被替换出去的某存储块时，就会出现容量失效。 (3)冲突失效(conflict)——在采用组相联和直接映象方式的Cache中，主存的很多块都将映象到Cache的某一行。如果因为这个原因，当程序再次访问到曾装入Cache又被替换出去的某存储块时，就会出现冲突失效，也称为碰撞失效(collision miss)。 表5.3列出了这三种原因导致LRU Cache失效的分布比例。为了说明相联度对失效率的影响效果，对每一Cache容量下失效率的测量数据都按相联度分为四类。图中所示的“n路”是指从上一相联度下降到下一级相联度所引起的失效。图中的四类分别是: 8路:由全相联(没有冲突失效)到8路组相联 4路:由8路组相联到4路组相联 2路:由4路组相联到2路组相联 1路:由2路组相联到1路组相联(直接映象) 表5.3 不同Cache容量和相联度情况下三种失效的分布比例 由表5.3中的统计数据我们可以导出图5.13和图5.14。由图5.13我们可清楚地看到增大Cache容量能有效地减小容量失效和冲突失效的失效率，从而降低总的Cache失效率;提高相联度则能减少冲突引起的失效。从图5.14可以发现，随着Cache容量的增大，因容量限制导致的失效在总失效中所占的比例逐渐减小，而冲突和冷启成为失效的主要原因。 5-11 第五章 存储器层次结构 图5.13 三种失效的实际失效率与Cache容量的定量关系 图5.14 直接映象Cache的三种失效分布及不同相联度冲突分布 在对导致失效的原因作了上述分析后，我们再来看看这种失效分类对设计Cache时考虑减少失效措施有何指导意义。从原理上讲，减少冲突失效最简单，只要采用全相关映象方式就可以完全避免冲突失效。但是全相关映象机构的硬件实现复杂，成本最高，而且可能延长存储器层次结构的平均访问时间，因而可能导致综合性能的降低。对于容量失效，除了购买容量更大的存储器芯片外没有什么更好的办法。如果存储器层次结构中的高层存储器的容量与程序需求相比过小，那么程序处理的大部分时间将用于在两级存储器之间频繁地来回传送数据，存储器层次结构这种现象被称为“抖动”现象。频繁失效将导致过多的存储块替换行为，因而出现“抖动”现象意味着系统将以接近于低层存储器的速度运行，而且由于失效造成的额外开销，系统运行速度甚至可能低于低层存储器。根据空间局部性原理，增大块大小可以减少被迫失效，但这意味着减少Cache中的行数，因而可能会增加冲突引起的失效。 上述失效原因分析模型确实有助于我们认识Cache的失效行为，但也应看到这样的失效分类方法也有一定的局限性。比如，增加Cache容量可以扩大Cache的访问范围，因而既可以有效地减少容量失效，也可以减少冲突失效，这样当Cache的结构参数改变时，一种失效就可能转变成另外一种失效。此外，上述失效原因分析并未考虑替换策略对失效可能产生的影响。虽然一般情况下，替换策略对失效的影响并不明显，但在一些特殊情况下，替换策略可能会导致Cache的意外行为。例如使得高相联度的Cache却有着很高的失效率，这类行为与我们用三种失效原因分析所得的结果正好相反。 三、块大小对Cache性能的影响 在5.1.3节中，我们定性地讨论了块大小和存储器层次结构性能之间的关系，见图5.4和图5.5。这一部分将给出一组实验测试数据定量分析在Cache/主存存储器层次结构中块大小对Cache性能的影响。 图5.15显示了不同Cache容量下的失效率与块大小之间的定量关系，这些数据是通过跟踪一些程序在VAX机上的执行情况，在直接映象的Cache模拟系统上测试得到的。由图易知，通常增加块大小能有效地降低失效率。但注意到图上容量为1KB的Cache，块大小取256字节时的失效率比取16字节、64字节时的失效率都要高得多，因而可知:当Cache容量较小时，不能使块大小取得过大，因为超过某一上限值继续增加块大小时，反而会使失效率上升。 图5.15 失效率与块大小之间的定量关系 图5.16是根据图5.15中的失效率计算得到的。这里假设失效损失为8个时钟周期，主存和总线可在一个时钟周期内传送4个字节的数据。而且假定Cache失效时需先将对应存储块装入Cache，然后将所需数据字送到CPU。从图中可以看出，一般在块大小取16字节或64字节时，Cache/主存的平均存储访问时间最小;只有在Cache容量很大时，取256字节的块大小才比取4字节的块大小要好。 5-12 第五章 存储器层次结构 图5.16 平均存储访问时间与块大小之间的定量关系 四、独立指令/数据Cache和一致Cache 与其它级别的存储器层次结构不同，Cache有时被分为独立的指令Cache和数据Cache。若Cache中既可以存放指令，又可以存放数据，此时称之为一致Cache(unified cache)或混合Cache (mixed cache)。CPU知道送出的访问地址是指令地址还是数据地址，因而可以为指令Cache和数据Cache分别设置地址、数据端口，这样Cache和CPU之间的传输带宽就增加了一倍, 这将有利于指令流水线的实现。(,在4.2.2节已分析了为流水线执行增加存储端口的好处。)指令、数据分开存放的Cache结构的优点是我们可以根据程序读取指令和访问数据所具有的不同行为特征(我们知道指令访问的局部性比数据局部性更为明显)分别优化指令Cache和数据Cache，有针对性地选择容量、块大小、相联度等结构参数，使得整个Cache/主存存储器层次结构有较好的综合性能。在这里我们将仅对指令失效率与数据失效率的不同之处加以讨论。 在表5(4中列出了结构相同的独立指令/数据Cache和一致Cache的失效率。数据表明:指令Cache的失效率要低于数据Cache，这与指令、数据的行为特性是相符的。指令、数据分开存放于独立的Cache中能消除因指令块和数据块冲突引起的失效，但也限制了分配给指令和数据的Cache空间。所以两类Cache的性能比较应在Cache总容量相等的条件下进行，比如分开的1KB指令Cache/1KB数据Cache应与2KB一致Cache作比较。要计算独立指令/数据Cache的平均失效率，必须知道存储访问中指令、数据的访问比例，见例5-4。 表5.4 不同容量的指令Cache、数据Cache、一致Cache的失效率 例5-4 假设53%的存储访问是读指令。问16KB指令Cache/16KB数据Cache与32KB的一致Cache相比，哪一个失效率更低, [解答] 根据表5.4的实验数据可得: 独立指令/数据Cache的平均失效率 = 54% × 3.6% ，47% × 5.3% = 4.4% 而32KB一致Cache的失效率为4.3%，所以一致Cache 的失效率稍低些。 表5.4 不同容量的指令Cache、数据Cache、一致Cache的失效率 若指令Cache与数据Cache分别采用不同的结构参数，那么上述例子的结果可能会有所不同。 5.2.7 主存的组织方式 由于主存在计算机系统中地位独特——在存储器层次结构中处于Cache的下一级，同时作为输入的目的和输出的源又担任着I/O接口的任务，所以主存的设计必须同时满足Cache、向量部件和I/O三方面的需求。与Cache不同的是，主存的性能测量要同时强调访问延迟和存储带宽。一般说来，Cache主要关心主存的访问延迟，这直接影响Cache的失效损失;而向量部件和I/O更为关心传输带宽。但当Cache的块大小由4,8字节增大到64,256字节时，主存的传输带宽对Cache来说也非常重要。主存与I/O的关系将在第六章中讨论。 现代的计算机中几乎所有的主存都采用DRAM芯片实现，(几乎所有的Cache都用SRAM芯片)。DRAM(动态随机访问存储器)与SRAM(静态随机访问存储器)的主要差别有三个方面:(1)对DRAM芯片来说，在读出数据之后还需重新写回数据，因而它的访问延迟和存储周期不同。SRAM的访问时间与存储周期则没有差别;(2)为防止信息丢失，DRAM需要定期刷 5-13 第五章 存储器层次结构 新每个存储单元，SRAM却不需要;(3)DRAM设计强调容量，而对SRAM设计来说，容量和速度同样重要。就可以比较的存储器设计技术而言，DRAM的容量大概为SRAM的16倍，而SRAM的存储周期比DRAM的约快8,16倍。 Amdahl提出的一条设计原则是:为保证系统性能平衡，存储容量应与CPU速度的提高保持线性增长的关系，根据这个原则，计算机设计者是在DRAM容量每隔三年提高4倍的前提下来设计CPU的。然而不幸的是DRAM的速度性能的提高极其缓慢，见图5.17。图中低速CPU的性能在1985年以前每年递增19%，85年后每年递增50%，高速CPU在80,85年间的发展速度是每年递增26%，85年后递增速度高达100%;而DRAM的速度每年只递增7%。 图5.17 DRAM、CPU的速度性能增长曲线 根据Amdahl定律，CPU与DRAM之间的这种速度性能差距将极大地限制处理器综合性能的提高。当然改进Cache的组织结构，比如扩大Cache容量可以减小这种差距，但这仍然是不够的。本节将就如何改进主存的组织方式以提高主存性能展开讨论。 一般说来，改进主存的带宽性能要比减少主存的访问延迟更为容易，而且提高带宽可以相应增加Cache的块大小，而不会引起失效损失的增加。如图5.18, 主存的组织方式一般有三种:单体单字主存结构、单体多字主存结构和多体交叉主存结构。 图5.18 主存的三种组织方式 (1)单体单字主存结构 因为绝大多数CPU访问都以32位字为单位，所以Cache往往是以一字宽为单位组织的，为与Cache宽度相匹配，主存的宽度也是一个字。这就是最简单也最基本的主存结构，如图5.17(a)。为便于与其它两种主存结构作性能比较，我们假设这种结构的基本参数为:发送地址需1个时钟周期，每个字的访问时间为6个时钟周期，传送1个字长的数据要1个时钟周期。已知Cache的块大小为4个字(16字节)，所以可知基本主存结构下，Cache的失效损失为4×(1，6，1)=32个时钟周期，而存储带宽为1/2 字节/时钟周期。 (2)单体多字主存结构 要提高主存的带宽性能，最简单的方法是增加主存的宽度。只要把主存的宽度增加一倍或三倍，就可以使主存存储带宽相应地增加到原来的二倍或四倍。如果把单体单字主存的宽度增加到四倍，那么Cache的失效损失就能从原来的32个时钟周期降到1×8=8个时钟周期，主存的存储带宽从1/2字节/时钟周期增大到2字节/时钟周期。 采用单体多字主存结构的代价首先是必须增加总线宽度。因为CPU访问Cache仍是以字为单位进行的，这样又必须在Cache和CPU之间加进一个多路选择器，如图5.18 (b) 。(如果Cache比总线速度更快，那么多路选择器应放在Cache和总线之间。)因为多路选择器可能正好处在关键的定时路径上，因而可能影响CPU的时钟周期。一般主存设计应允许用户扩展主存容量，而这种结构对此有限制，它要求至少以原容量的2倍或4倍方式扩展。另外，要实现带纠错的存储块部分写操作(比如字节写)是比较困难的:为了计算新的纠错码并在写操作完成后保存起来，必须把整个字中除更新字节外的其余部分也读出来。如果纠错是对存储单元的整个宽度进行的，那么采用单体多字结构就会增加这类“读—修改—写”序列的频度，因为这种结构使更多的写操作变成了部分写操作。由于大部分写操作是对32位字进行的，很多单体多字主存结构实际上都是以32位字为单位进行纠错。 (3)多体交叉主存结构 5-14 第五章 存储器层次结构 这种结构的主存由m个一字宽的存储分体组成，一次访问最多可以读写m个字。由于每个分体都为一字宽，因而不必改变总线和Cache的宽度，只要送到各分体的m个地址不发生冲突(没有两个地址属于同一存储分体)，m个存储分体就可以同时读出m个字。与单体多字主存结构相比，这m个地址不必是顺序的，而单体多字则要求可并行读出的多个字必须是顺序地址且处于同一存储单元。根据设定的基本主存结构参数，理想情况下，采用多体交叉主存结构，Cache的失效率可以减小到1，6，4×1=11个时钟周期，而存储带宽增大到1.5字节/时钟周期。这种模块结构对于写操作也非常有利。若出现两个相继的写访问，对基本主存结构，第二个写访问必须等第一个写操作完成以后才能开始;而在多体结构下，只要二个写地址不属于同一分体，二个存储分体就可以在时间上重叠进行写操作(不完全同时，是因为二个要写入的数据要通过同一数据总线相继送入二个存储分体)。 存储单元的编址模式会影响多体交叉主存结构的性能。一般采用以字为单位模m交叉编址的方式:如图5.18(c) ，体0中包含所有那些字地址模4等于0的字，体1中则为字地址模4等于1的字，体2、体3以此类推。这种编址模式可以优化顺序的存储访问，因为顺序的二个字地址必不在同一分体中。当Cache发生读失效，从主存中读入要访问的存储块时，块内的字是顺序读出的，因此特别适合于字交叉编址的多体交叉主存结构。对于回写技术的Cache,将Cache写回主存对应块时的情况与读失效情况相同,采用多体交叉结构也很有益处。 例5-5 采用单体交叉和多体交叉主存结构对处理器性能到底有多大的影响? 已知Cache块大小=1字,存储总线宽度=1字,Cache失效率=15%,访问次数/指令=1.2,Cache失效损失=8时钟周期(同前设定),平均执行时间/指令(不考虑Cache失效时)=2时钟周期,如果块大小增加到2字,则失效率降低到10%,若块大小增加到4字,则失效率降低到5%,计算并比较块大小取2个字和4个字时采用3种主存结构时的处理器性能。 [解答] 在例中时钟周期和指令数保持不变,所以只要计算CPI就可以得出各种方案下的处理器的性能比较结果。 当Cache块大小取1字时,基本主存结构的CPI为: 2+(1.2×15%×8)=3.44 当Cache块大小取2字时,基本主存结构的CPI为: 单体单字主存结构 2+(1.2×10%×8×2)=3.92 2体交叉主存结构 2+(1.2×10%×(1+6+2×1))=3.08 , 3.92/3.08=1.12 单体2字主存结构 2+(1.2×10%×8)=2.96 , 3.44/2.96=1.16 所以当Cache块大小增加一倍时,对于字宽主存结构,处理器性能直线下降。而当采用多体交叉主存结构和单体多字主存结构的处理器性能分别提高了12%和16%。 当Cache块大小增大到4个字时,3种主存结构的CPI为: 单体单字主存结构 2+(1.2×10%×8×2)=3.92 4体交叉主存结构 2+(1.2×5%(1+6+4×1))=2.66 , 3.44/2.66=1.29 单体2字主存结构 2+(1.2×10%×8)=2.96 , 3.44/2.96=1.16 所以再次说明采用大的存储块对基本主存结构来说肯定有损于处理器性能,而采用多体交叉主存结构和单体多字主存结构能提高处理器性能。在例中,块大小为4字时,处理器性能分别提高29%和16% 。 采用多体交叉存储技术的最初动机是为了优化顺序访问,后来则是为了能同时进行多个独立的存储访问。例如,输入设备可能使用存储控制器及其存储模块,而CACHE 和向量部件也需要通过存储控制器访问各自的存储模块,为了减少冲突,就需要设置多个存储控制器控制各存储分体(或多字交叉的分体组)独立执行读写操作。比如象NEC SX/3 就使用了高达128个存储分体。 随着存储芯片容量的提高,相同容量的主存系统所需的芯片数会不断减少,这使得多体交叉 5-15 第五章 存储器层次结构 主存的成本比基本主存结构昂贵得多。比如,一个16MB的主存要组织成16个存储分体的多体交叉结构,需要16×32=512块256K×1bit的存储芯片,如果采用单体单字主存结构,只需要32块4M×1位存储芯片。这是多体交叉主存的主要缺点。这种结构的另一个缺点也是用户难于按需扩充主存容量，因为存储控制器一般要求多存储分体的容量相等,所以如果用户想扩充容量,至少要扩充到原来的2倍。 5.3 虚拟存储器(Virtual Memory) 虚拟存储器是整个存储器体系结构中用于管理主存,辅存存储层次的存储管理技术。自60年代提出发展至今，目前已广泛应用于各种机型，成为计算机一种必不可少的存储管理技术。 虚拟存储器最初主要是为了满足应用程序对高速大容量主存的需求。大家知道，CPU只能执行装入主存的程序。在采用虚拟存储器之前， 如果程序太大不能全部装入主存，程序员就必须将程序划分成彼此互斥调用的程序模块。程序运行期间这些可相互覆盖的模块，在用户程序控制下不断地在主存和辅存之间调进调出，由程序员保证程序不会超过用户可用的物理地址空间。这大大增加了程序员编程的负担和难度。虚拟存储器技术则使应用程序员可在机器指令地址码决定的比主存容量大得多的逻辑地址空间上编程，程序不必修改就可以以接近于主存的速度在虚拟存储器上运行。 当程序从辅存调入主存时，必须进行程序在主存中的定位，即将程度的逻辑地址映象转换成主存的实际地址。由虚拟存储器实现的重定位是由一个地址映象表机构完成的，它允许同一程序在物理存储空间的任一位置上运行。而且虚拟存储器还能减少程序启动时间。因为程序开始执行时不必将所有的数据和代码都装入物理存储空间，仅在用到时才将它们从辅存中调入主存。 虚拟存储器还提供存储共享和保护机制。为了充分利用计算机资源，通常在计算机上任何时刻总是同时运行着多个进程,每个进程都有各自的地址空间。 为每个进程都提供全地址空间(full-address-space)极其昂贵，而且实际上很多进程使用的只是整个地址空间的一小部分。因此，必须有一种机制使得多个进程共享有限的物理地址空间。而虚拟存储器本身就具有共享存储的性质。它将物理存储空间划分为存储块，并将它们分配给各个进程。其中各进程的共享代码和数据段放在相同的存储块内。另外它还提供存储保护机制，保证各进程都只能访问那些分配给它们的存储块。 在5.1.2节中介绍的存储层次的概念大多也适用于虚拟存储器。 但一般用页面或段(segment)来表达块这个概念，称失效为页面失效。 对虚拟存储器来说， 由CPU产生虚地址，由软硬件共同将其转换成物理地址以访问主存， 这个过程称之为存储映象(memory mapping)或地址翻译(address translation)。表5.5给出了虚拟存储器(主存/辅存存储层次)的典型结构参数。根据采用的相关技术， 虚拟存储器可分为两大类:块大小固定不变的页式虚拟存储器和块大小可变的 162段式虚拟存储器。一般一个页面为固定的512?8192字节，而段大小可变，机器支持的范围为 32字节?2字节。 表5.5 虚拟存储器的结构参数 采用何种虚拟存储器将影响CPU的设计。若为页式寻址方式，那么CPU产生的地址是单一的长度固定的虚地址，它由页号和页内位移两部分组成。对于段式寻址，由于段大小可变，因而存放段号需要一个字，段内位移又需要一个字，所以虚地址长度为2个字。对于编译程序来说页式寻址方式更易实现。 这两类虚拟存储器各有优缺点，对比列于表5.6中。 由于替换问题(表中第三行)，纯粹的段式虚拟存储器已很少见。为取长补短，一些机器采用的是将段式和页式相结合的段页式虚 5-16 第五章 存储器层次结构 拟存储器。在这种虚拟存储器中，段由整数倍页面组成。存放一个段的物理存储空间不必是连续的，因而简化了替换问题，段也不必整个都调入主存。实际上段可以看作是一个逻辑单位。 表5.6 页式和段式虚拟存储器优缺点比较 5.3.1 虚拟存储器与Cache/主存存储层次的差别 尽管虚拟存储器是由主存(DRAM)和辅存(磁存储器)构成的存储层次，也具有二存储层次的一般特点，但其在整个存储体系中所处的位置决定了它有着自己的特点，在设计有其特有的指导原则。为便于对比学习，在介绍虚拟存储器的设计前先来分析一下它与Cache/主存存储层次的差别。 对比表5.1和表5.6，我们可以看到虚拟存储器与Cache/主存的一些基本差别。此外，它们之间还有以下区别: (1)Cache设计的主要出发点是弥补主存速度不足，而虚拟存储器的引进主要是为了扩大程序可用的存储空间。 (2)Cache/主存的替换策略主要是由硬件控制实现的， 而虚拟存储器替换算法则基本由操作系统实现。因为页面失效损失与页面命中时间相比大得多，所以操作系统用于决定替换页面的时间也可相对长些。 (3)处理器地址长度决定了虚拟存储器的存储空间大小，而一般Cache容量与处理器地址长度无关。 (4)辅存除了作为虚拟存储器二级存储层次中的低层存储器外， 还用作文件系统，这一部分不属于地址空间。事实上，辅存的绝大部分均用作文件系统。 因此，存储空间、页面、地址在虚拟存储系统中实际上均对应三个不同的概念:对应主存，分别被称为物理存储空间、实页面、主存实地址;对应由处理器地址决定的虚拟存储器，则称之为逻辑存储空间、虚页面、虚地址;而在辅存中则为辅存空间、辅存实地址。 5.3.2 虚拟存储器设计的基本问题 一、映象方式 从原理上讲，主存与辅存中存储块的对应关系仍可以有三种:直接映象、组相关映象和全相关映象。但是在虚拟存储器中，失效意味着访问磁存储器(磁盘)，与页面命中时间和Cache失效损失相比，页面失效损失极大， 因而减少失效代价成为虚拟存储器设计的重要原则。所以，在选择映象方式时，如果要在低失效率和易于实现这两者之间做选择，操作系统设计人员总会选择低失效率。这就要求OS允许让辅存中的一存储块能映象到主存中的任意块。即虚拟存储器一般总是采用全相关映象方式。 二、地址翻译 虚存空间到主存物理空间的映象关系是通过称为页表的数据结构来实现的。页表由页表项组成，每个虚页面都对应一个页表项。页表项的主要内容是与一虚页面对应的实页号。来自CPU的虚地址通过虚页号查找页表，得到相应的实页号， 与虚地址中的页内位移组成实地址访问主存。如图5.19。 图5.19 虚拟存储器的基本地址翻译 5-17 第五章 存储器层次结构 为了支持多用户(或多进程)共享存储空间，每个用户(或进程)都有自己的页表，这样虚地址虚页号又被分成用户标识号UID(或进程标志PID)和虚页号。通过进程标志查找页表基址寄存器(PTBR)得到该用户(或进程)的页表后，再进行虚实页号的地址翻译。对于段页式虚拟存储器，地址翻译更为复杂，如图5.20。 通常虚地址由用户标识号UID、段号、页面号和页内位移组成。首先由UID查找段表基址寄存器得到该用户的段表，再据段号查找相应段表项得到该段对应的页表，然后做虚实页号的地址翻译。一般页表项除了实页号外，还包括有关其它控制信息，如指示该实页是否在主存的有效位，指示该实页在主存中是否被修改过的修改位(也称“脏位”)，指示该页面是否为多个进程所共享的专用位，以及为支持存储保护而设置的保护密级和访问权限字段。 图5.20 段页式虚拟存储器的地址翻译 有时系统还必须用多级页表才能实现虚实地址转换。例如当虚地址为28位时，即用户程可 16用的逻辑存储空间为256MB时， 若取页面大小为4KB，则页表共有2个页表项。设每个页 18表项占4字节，则整个页表要占用=256KB存储空间，必须分开存放在几个页面内。为此要2 建立多级页表，由上一级页表的页表项指出下一级页表的基址。使用反向页表(inverted page table)，可减小页表所需的存储空间。即一个实页面对应一个页表项，这样页表长度远小于虚页面数。若物理地址空间为8MB，则页表大小为8KB。对于反向页表，一般通过对虚页号作哈希(Hash)函数变换来查找。 三、替换策略 设计操作系统最重要的指导原则是:尽可能减少页面失效。目前几乎所有的虚拟存储器都采用LRU替换策略，原因在于LRU块是近期内再次被访问可能性最小的块。为便于系统选择LRU块，每个页面都有一个“使用位”(use bit)或“引用位” (reference bit)，一旦页面被访问就置位。操作系统定期记录并清除这些使用位就可以知道在一定时间间隔内哪些页面近期被访问过，从而选择出最近最少被访问的页面。 四、写策略 由于写磁盘的访问时间高达几十万个时种周期，现在还没有虚拟存储器能够让CPU的每一次存储操作在写入主存的同时也写入辅存。 即虚拟存储器不可能采用直写技术而总是用回写技术。由于访问辅存的代价太高，虚拟存储器给每个页面设置一个“脏位”，页面被调出主存时，仅当该页面在主存中被修改过时，即对应的脏位被置位时才写回辅存。 五、选择页面大小 页面大小是虚拟存储器的一个基本结构参数。选用大页面或小页面各有利弊。就大页面来说，它有如下优点: (1)因页表大小与页面大小成反比， 采用大页面可以节省存放页表的主存空间(或其它存储介质，如TLB)。 (2)在主存与辅存之间传送大页面比小页面的传送效率高。 采用小页面主要是为了节省物理存储空间。程序所需的存储空间可能不是页面的整数倍，此时，在最后一个页面内可能出现不用的存储空间，它被称为内部碎片(internal fragmentation)。假设每个进程都由三个部分组成:程序正文、堆、栈，那么每个进程平均要浪费1.5个页面。这对页面大小取2KB?8KB的MB 级的存储器来说，浪费的存储空间很有限。但当页面较大，如?32KB时，那么存储空间(主存和辅存)及I/O带宽的损失就非常大。 采用小页面的另一 5-18 第五章 存储器层次结构 优点是可以减小进程的启动时间。通常很多进程都较小，若采用大的页面就会延长调用进程的时间。 六、加快地址翻译 在虚拟存储器中，存储访问都有一个查页表进行地址翻译的过程，这意味着每一次存储访问都至少要访存两次:第一次访存为查页表得到实地址，第二次才能存取所需的数据。若需要查多级页表，那么存储访问的代价更高。 为减小访存代价，一种方法是，记住最后一次地址翻译的结果，若当前虚地址与上一次访问的虚页号相同，则可以省去本次地址翻译。更为常用的办法是用一个特殊的Cache来实现地址翻译。根据程序的局部性原理， 既然指令和数据的引用具有局部性特征，那么为引用而做的地址翻译必然也会表现出局部性。即在一段时间内，地址翻译只会用到页表中相对集中的一些页表项，因而可以用专用快速硬件来实现只含有部分页表项的地址翻译。这个专用于地址翻译的Cache 也称为翻译准备缓冲器(translation-lookaside buffer)TLB。TLB的结构和原理与Cache相同,只不过在TLB中与Cache的标志相对应的是虚页号,与数据或指令对应的是实页号,此外还有一些控制信息,如使用位、脏位等。 但这里的脏位是指对应页面是否被修改过，而不是指TLB中的地址被修改过，也不是指数据Cache中对应数据块被修改过。 TLB 的常用结构参数见表5.7。 表5.7 TLB的典型结构参数 由于整个存储体系是由Cache、主存、辅存共同构成的，因而将Cache与虚拟存储器连接起来就会有下述问题:首先必须通过TLB把虚地址翻译成物理实地址， 然后才能以实地址访问Cache， 这意味着 Cache 的命中时间将因此而延长。 为减少Cache命中时间，一般是把虚地址的页内位移送往Cache，在读取Cache 标志的同时将虚地址的虚页号送往TLB做地址翻译，然后再将Cache的标志与TLB 变换而得的实地址作标志匹配比较。由于TLB通常比Cache的标志存储器容量更小，速度更快，因而这样的地址翻译不会影响Cache的命中时间。 但这种方法有一个缺点:对于直接映象Cache来说，它的容量不能超过一个页面。另一种方法是采用虚拟寻址Cache，见5.5.1节。 5.3.3 存储共享和保护 在支持多道程序设计的计算机系统中，主存中同时存在多个用户进程和系统进程。由于多道程序(进程)分时共享CPU和存储资源， 系统必须提供存储保护和共享机制。这种存储保护和共享机制是软硬件共同配合实现的。存储共享意味着多个进程可以共享相同的代码或数据段，这样既便于进程间通信，又可以减少相同信息的拷贝数以节省存储空间。存储共享功能的实现相对简单，只要将不同的虚页面映象到同一物理页面上即可。为保证多道程序系统正常工作，必须设置存储保护机制，以防止一个进程出错而破坏主存中其它进程的正确运行。它包括两个方面:(1) 防止一进程形成错误地址，访问其它不属于它的存储区域;(2) 防止一进程以非法方式侵权访问存储区域。 最简单的存储区域保护机制是通过设置寄存器方式实现的。系统设置一对地址寄存器，一般称为基地址寄存器和界地址寄存器。地址寄存器的值由操作系统在开始执行一道程序前分配，用户程序无法修改。当一程序由地址翻译所得的物理地址访问主存时，首先要比较物理地址与两个地址寄存器的值以检查地址是否越界。当满足基地址?物理地址?界地址时，该物理地址为有效访存地址，否则产生越界中断。一般系统把物理地址看作是无符号整数，因此地址越界检查也可按下式进行:基地址+物理地址?界地址。当一个用户程序占用主存的几个连续存储区 5-19 第五章 存储器层次结构 域时，就必须设置多对基、界地址寄存器。 要实现正确的进程切换，保证操作系统可以修改地址寄存器而用户进程不能修改，系统必须提供以下机制: (1)至少提供两种工作状态:用户状态和管理状态， 指明当前运行进程是用户进程还是操作系统进程。操作系统进程有时也称为核心进程(kernel process)或管理进程(supervisor process)。 (2)在CPU状态中增设基/界地址寄存器、用户/管理状态位和中断使能/ 屏蔽位(enable/disable)。用户可读取这些CPU状态，但不能改写， 否则操作系统就无法控制用户进程。当发生进程切换时，与该进程相关的CPU状态要保存起来， 以便切换回原进程时再恢复。 (3)提供CPU在两种工作状态之间相互转换的机制。在用户状态下一般通过系统调用转入管理状态。即执行一条特殊指令将控制转向管理代码空间的一个特定位置，系统调用指令处的PC值被保存起来，CPU进入管理状态。 从管理状态返回用户状态类似于程序返回，即恢复用户/管理状态位原先的值。 支持多道程序设计是虚拟存储系统的设计目标之一。 在虚拟存储器中， 由于CPU地址要通过地址映象将虚地址转换成物理地址， 因而在地址翻译过程中可以加入这种以基界地址为基础的存储区域保护机制??页表保护，这是虚拟存储系统固有的性质。因为每个程序都有一个由操作系统建立的程序页表，程序只能访问到自己的页表所规定的实页，不论虚地址如何出错，都只能影响这有限的几个实页，而不会访问到其它存储页面。对于段页式虚拟存储器，在段表中不仅设置页表始址，还给出段表长度(页面数)，因而可以判断虚页号是否越界。 存储区域保护的另一种方式是设置存储保护密级;给每一个页面或段设置访问允许标志(access permission)，即保护密级。比如将存储区域分为用户/核心区或(系统区)(user/kernel)，只要CPU给出一个用户/核心信号， 就可以避免用户程序侵入系统存储区域。但这种两级保护密级无法避免同一程序内由于部分出错而影响整个程序以至系统正常运行的情况。因而可以将保护密级扩展为若干级，按程序的重要性以及对系统影响程度大小分层，这也被称为环保护。如图5.24，保护密级由内向外逐级降低，允许访问第n级密级存储区域的程序能访问除第n-1级以外的其它任何区域。 图5.21 存储区域的环保护 此外，还有一种存储区域保护法称为键保护，它的机制类似于锁和钥匙:主存的每个页面都由系统分配一个存储键，相当于“锁”，一个用户所占用的实页的键均相同;而用户则由系统给定一个访问键，相当于“钥匙”。程序每次访问主存前，都要检查主存地址所在页面的键与程序的访问键是否相符，只有相符才准访问。但是若采用这种存储保护方法，要实现存储共享，而又不能允许用户程序复制访问键，这样就必须有相应的硬件设施和操作系统机制完成在程序间传递访问键的功能。因而键保护这种存储保护机制所需的硬件支持较多。 存储保护的另一个方面是存储区域的访问方式保护。上述的存储区域保护是指对允许访问的区域可以进行任何形式的访问，而对不允许访问的区域则任何形式的访问都不允许，这不能满足实际应用的需要。访问方式是指对存储区域中的信息作执行、读、写操作，不同存储区域对不同密级的用户来说允许的访问方式不同。存储访问方式保护是指给每个页面规定访问方式，即在页面对应的页表项中设置访问方式域段。当有用户访问该页面时，在地址翻译的同时检查它是否为侵权访问。一般访问方式保护和存储区域保护是结合起来使用的。 5-20 第五章 存储器层次结构 5.3.4虚拟存储器实例 本节我们以VAX11-780为例具体介绍虚拟存储器的结构和工作原理。VAX采用的是段页式虚拟存储器,它既利用分段存储管理方式将地址空间分成系统区和用户区,节省页表空间,又能利用分页存储管理性质提供虚拟存储管理,便于程序重定位和存储共享保护。 VAX的虚拟存储系统首先将地址空间分成两个大段:用户进程区和系统区， 由地址的第31位指示，第31位为O指用户区，为1则为系统区。每个进程都有独自占用的私有空间(private space)，即均有各自的用户进程区， 并和其它进程一起共享系统空间。每个用户进程区又进一步分为二个段:P0和P1,由地址的第30位区分。P0区(第30位,0)存放用户程序正文和堆(heap);P1区(地址30位,1)则用作程序的控制栈区。见图5.22。 图5.22 P0和P1组织 30当P0或P1段超过1024MB(B)时, 说明虚拟空间被用完。系统区、P0区、P1区均有各自的2 页表, 各有一对基界地址寄存器分别指出各区页表的起始地址和界值。其中系统区页表存放在物理存储器中，P0、P1区的页表放在虚拟存储器的系统区中，即P0、P1区采用的是二级页表。这对于VAX 这种采用小页面(512B)大页表的虚拟存储器系统非常重要。一方面能有效地节省物理存储空间，另一方面可以保证页表随P0、P1区扩大而增大。后者对那些在执行期间所需存储空间动态变化的程序特别重要。但在最坏情况下，一次访存将引起两次页面失效。第一次失效为页表所在的页面不在主存，此时需从辅存调入该页面以完成地址翻译。第二次失效则为要访问的页面不在主存。 图5.23 VAX虚拟地址的映象机构 图5.23给出了VAX虚拟地址的映象机构。由址址的最高两位选择相应的基界地址寄存器对得到相应页表,检查地址是否越界。若地址越界， 则中断作越界处理。否则查找页表进行地址翻译，得到的物理实页号与页内位移一起形成完整的物理地址。VAX的页表项除了实页号以外，有以下域段: ,??修改位。指示该页面在主存中是否已被修改过。 ,??有效位。指示该页表项所含有的实页号是否为有效地址。 ,??存在位。指示该页面是否在主存中。 PROT??四位存储保护码。 VAX的页表项中未设使用位，因而它根据修改位和其它一些软件措施来实现LRU替换算法。VAX 的存储共享是通过将不同虚页面映象到同一物理实页面上完成的。存储保护则采用四级环保护与访问方式保护结合编码的办法。四级环保护为核心级、执行级、管理程序和用户程序级。访问方式分为禁止访问、只读、读写三种。例如PROT域段为1001时指核心、执行级进程允许读写访问，管理程序级允许读访问，而用户程序级禁止访问。为了进一步隔四个保护密级，每一级都分别有各自的堆栈和堆栈指针的备份。 图5. 24 VAX-11/780的TLB 5-21 第五章 存储器层次结构 VAX-11/780为了缩短地址翻译的时间还设计了一个TLB，其组织结构如图5. 24。它采用的是二路级相联的映象方式。64组共128个页表项分成两大模块:由各组中,号页表项组成的模块,，以及由各组中的1 号页表项组成的模块1。VAX-11/780的TLB有一个与众不同的特点，即将两个模块又再分成两部分，每个模块的前32个页表项留给系统进程专用，后32个页表项留给用户进程用。由虚地址的最高位指示当前进程是系统进程还是用户进程，以此选择模块的前后两个部分。这样做有两个目的:(一)缩短进程切换时间。由于地址空间的系统区是所有进程的公用区间，因而当进程切换时只须将TLB中两个模块的后半部分的32 个页表项置为无效，而不必将整个TLB的页表项均置为无效。(二)提高性能。 当进程切换频繁发生时， 可以防止系统进程和用户进程互相把对方有用的页表项挤出TLB，避免因频繁切换造成TLB失效率上升。 TLB的地址翻译过程如下:虚地址的5位索引送往TLB(?)的同时,地址最高位也被送往TLB(?)以读取相应标志作匹配检查。 当然只有那些有效位被置位的页表项才允许参与匹配检查。在第?步中还要根据TLB 中的存储保护信息检查对本页面的访问是否为侵权访问。虚地址的标志部分同时与一组中的两个标志作比较(?)。将相应页表项中的物理页帧地址送往2选1多路选择开关(?)，然后标志匹配的页表项对应的物理页帧地址(21位)与9 位页内位移一起组成完整的物理地址被送往主存(?)，TLB访问结束。若找不到匹配的页表项或页面不在主存中， 则需作异常处理。 5.4基于程序行为特性的优化技术 5.4.1指令预取缓冲器 指令在绝大多数情况下都是顺序执行的，因而后续要用的指令在大多数情况下都是当前执行指令之后的顺序指令子序列。如果后续指令在用到之前就预先从存储器中取出来，那么CPU就能更快地得到要执行的指令，系统的性能就能进一步提高。根据高频事件高速处理的设计原则，同时为了充分利用程序顺序执行的这个特点，很多计算机都设置了指令预取缓冲器(IB)，即在CPU执行一条指令的同时， 将后续指令子序列取到指令预取缓冲器中。如果我们把CPU看作是指令的消费者， 把存储器看作是指令的提供者，那么只有在存储器提供指令的速度大于CPU 消费指令的速度时，指令预取才有意义，否则，预取缓冲器不可能在CPU 之前得到后续指令。要使存储器提供指令的速度赶上CPU消费指令的速度，有两个办法。 一是增加数据通路的带宽，一次取几条指令。二是使存储体系的速度大于CPU的速度。 采用指令预取缓冲器也有一个缺点，当取入预取缓冲器中的指令是CPU 不会用到的指令时，比如发生分支转移时，指令预取将增加CPU与存储器之间的数据传输量。另外，设置指令预取缓冲器将有助于变长指令的对齐操作。 一般指令预取缓冲器可以容纳2至8条指令序列，比如VAX-11/780的指令预取缓冲器为8B，可容纳两条32位的指令，如图5.25所示。下面我们以VAX-11/780的指令预取缓冲器为例，介绍指令预取的工作原理。 图5. 25 VAX-11/780的指令预取缓冲器 5-22 第五章 存储器层次结构 当前指令的操作码在IB的高位字节里，且高位字节可对应任意字节地址，而IB的其余字节必须顺序存放。当IB的一条指令被消费掉(指令译码器可以在一个时钟周期内读取IB高端的4个字节)以后，整个IB就左移，使IB 高位字节包含下一条指令的操作码。IB中的每个字节还设有一个有效位V， 以便指示对应字节中是否为顺序存放的有效指令。 IB总是试图超前PC取入指令。只要IB中一出现空闲字节，它就申请读取包含该字节的边界对齐的指令字，而且从存储器只预取32位指令字。当32位预取的字送达时，它就尽可能多地按IB当前空闲字节数装入该字。因而，一个32位的指令字可能只需从存储器取一次就装入IB中，也可能需要从存储器取四次才整个装入IB中。 当程序发生分支转移或中断时，PC值被修改，此时对应新的PC值的指令不在IB中，IB中却可能已经预取了一条或两条不用的指令。因而当PC被修改时，IB的所有有效位均被置为无效，IB按PC值重新预取。 5.4.2寄存器和寄存器窗口 由第3章的统计数据可知， 因过程调用时保存和恢复寄存器值引起的存储访问在总的数据存储访问中占到5%-40%。如果能减少这一类存储访问，系统的性能将得到改善。一方面，随着VLST工艺迅速发展，已完全可能在处理机内设置大量寄存器;另一方面，经实验研究，典型过程的局部变量、传递参数以及过程调用的深度大多数情况下均在相对较小的范围里波动。据此人们提出了一种被称为寄存器窗口的技术，它能优化寄存器使用，有效地减少过程调用时的存储访问次数。 寄存器窗口技术的基本思想是把大量寄存器分成大小相同的寄存器组，每组为一个窗口。如图5.26所示。每个窗口分为三个区域:(,)和上级调用过程的窗口重叠的参数寄存器，如图中R26-R31， 它存放从上级调用过程传递到本过程的参数以及本过程要传送回去的结果。(,)局部寄存器，图中为R16-R25， 存放本过程的局部变量。(,)和被调用过程的窗口重叠的临时寄存器，用于存放传递给下一级被调用过程的参数并接收从被调用过程返回的结果，图中为R10-R15。 不同过程占用不同的寄存器窗口，任意时刻，只有一个窗口是活动的。只有活动窗口中的寄存器是可见和可访问的。所有过程共享的全局变量存放在全局寄存器R0-R9 中，它在过程调用时保持不变。每个过程可以看到本过程占用窗口中的寄存器，加上全局寄存器，一次只能看到32个寄存器。 图5. 26 寄存器窗口 为了使过程调用的深度不受限制，一般窗口是以环形方式组织分配的。当发生过程调用时，调用过程的R10,R15就成了被调用过程的R26-R31， 过程之间的参数传递通过窗口重叠完成，避免了数据的实际移动。当所有窗口被分配完而又发生过程调用时，我们称寄存器窗口上溢(Window overflow)， 若寄存器窗口全部未被占用却又发生过程返回，此时寄存器窗口下溢(Window underflow)。图5.27说明了程序运行过程中寄存器窗口的使用情况。图中x轴为时间，y轴为过程调用或嵌套的深度，过程调用时深度加深，过程返回时深度变浅。一个矩形框为一次窗口上溢或下溢。图中的程序执行过程中有8次窗口上溢、2次窗口下溢。而当整个程序执行结束时，上溢和下溢的次数应相等。 5-23 第五章 存储器层次结构 图5.27 程序运行中寄存器窗口使用情况 采用重叠寄存器窗口技术以后，有过程调用或过程返回时，仅当窗口上溢或下溢时才需要访问存储器以保存或恢复存放过程局部变量和参数的寄存器。寄存器窗口中仅需转储或恢复参数寄存器和局部寄存器(R16-R31)。 当然要评价寄存器窗口对系统性能的影响必须考虑窗口上溢或下溢的代价，除了转储或恢复寄存器外，还需加上中断带来的损失。尽管如此，实验数据表明，寄存器窗口技术能有效地减少因过程调用而引起的存储访问次数。表5. 列出了在DLX和SPARC上运行基准测试程序GCC和TEX的对比数据。其中SPARC采用了寄存器窗口技术，表中SPARC的数据包含了窗口上溢和下溢时的LOAD和STORE。由表中数据可知，对GCC程序，在DLX 上运行比在SPARC上要多执行约20%的LOAD指令，多执行约60%的STORE指令，而对TEX 程序，相应地要多执行3%的LOAD指令，多执行41%的STORE指令。表中未列SPICE 程序的情况，是因为寄存器窗口技术对于浮点运算密集的程序基本没有什么影响。 表5. 寄存器窗口技术对访存次数的影响。 5.5 改进Cache/主存性能的技术 由于CPU与DRAM之间器件速度差距不断增大， 如何缩小这种差距以提高处理器的综合性能成为很多体系结构设计师的热门研究课题。前面我们已经介绍了一些技术措施，如改进主存结构和Cache的结构，但要进一步减小Cache/ 主存的平均访问时间却非常困难,原因在于: (1)增加块大小能降低失效率,但低失效率并不能抵销高失效损失, 因而不一定能降低平均访问时间; (2)增大Cache容量在降低失效率的同时会降低Cache速度,从而危及CPU 的时钟频率; (3)提高Cache关联度在减少冲突失效的同时会降低Cache的速度,也会影响 CPU的时钟频率。 此外，失效率是根据用户程序访存情况计算的，这与实际情况相比还较粗糙。比如，当考虑用户程序要调用操作系统代码时，真正的Cache 失效率要比预期的高得多，如图5.28。 图5.28 考虑系统调用时的Cache失效率 本节将介绍一些进一步改进Cache/主存性能的技术措施。由于平均存储访问时间是由命中时间、失效损失和失效率决定的，所以我们将从缩短命中时间、减少失效损失这二个方面来介绍相关技术。最后讨论有关Cache一致性问题， 其中将涉及减少Cache刷新次数以降低失效率的方法。 5.5.1 缩短命中时间 一、加快写命中操作 如前所述,Cache 写操作中的修改步骤必须在地址标志比较结束后才能进行，这样Cache的写命中过程不能象读命中一样在一个时钟周期内完成。 要加快写命中操作，一般采用下面两种 5-24 第五章 存储器层次结构 方法: 一种方法是，对于写直达Cache ， 将 Cache 的写操作设计成流水工作方式。VAX8800采用的就是这种方法。它将行标志和数据行分开,使两者独立寻址，从而读取行标志与数据行访问可同时进行。这样，Cache仍要比较行标志和当前写地址,但在本次标志比较阶段可同时执行前次写访问的更新步骤。当前次访问为写命中时，CPU不必空等就可执行写入Cache的步骤，因而每一个时钟周期可执行一个写命中操作。 另一种方法是采用“子块映象方式”，使写命中操作在一个时钟周期内完成，但它只适用于直接映象Cache。在这种方式下，每个Cache行被分为更小的子块，每个子块都带有一个“有效位”。当行标志与存储地址匹配时，要访问的字不一定在Cache中，只有当相应子块的有效位被置位时，才说明访问命中Cache。如图5. 29，地址标志为201、203的访问将命中Cache，而202、204的访问会导致Cache失效。当发生Cache读失效时，只装入对应存储块中要访问的子块。这样，子块映象Cache的存储块(行)不再是Cache和主存之间数据交换的最小单位， 而仅仅是与地址标志相联系的一个信息单位。 图5.29 子块映象方式 最初采用子块映象方式主要是为了减小大存储块引起的失效损失，因为在失效时需要读入的只是大存储块的一部分，即子块。此外还能减少小容量Cache 的标志存储器在Cache总容量中所占的比例。如果图5.29中的Cache不采用子块方式，取存储块大小为子块大小,那么地址标志就需要16个。 采用这种方法也有利于缩短写命中时间。具体方法是不管地址标志是否匹配，都将数据写入Cache，置有效位,然后将更新的字写入主存的相应块。这种处理方法在各种标志比较情况下都适用。 (1)标志匹配且有效位已置位:将数据写入Cache行是常规操作，而重置有效位不会产生任何有害结果。 (2)标志匹配但有效位未置:要访问的数据块正好在Cache中，只是访问的字尚未装入Cache，此时将数据写入相应行并置有效位是合理操作。 (3)标志不匹配:即写失效。在此情况下， 若是写直达 Cache ， 由于写入Cache的对应子块的有效位被置位了，所以要修改该Cache行的地址标志，取消该行其余子块的有效位(Cache 行的其余子块并未装入 Cache )。 这种操作对写直达Cache是合理的，因为主存仍能保存数据的最新拷贝。 对于回写技术的Cache，数据的最新拷贝是保存在Cache中的，因而在标志匹配检查前进行写入操作会覆盖有效数据信息，所以这种方法不适用于写回Cache。 二、虚拟寻址Cache 因为命中时间既影响Cache/主存的平均访问时间，又直接关系到CPU 的时钟周期， 所以， 缩短命中时间能直接提高处理器的综合性能。 前面的方法主要是从Cache/主存存储层次内部来考虑缩短Cache的命中时间， 下面讨论就整个存储体系来看(考虑虚拟存储器)，如何加快Cache的命中操作。 一种方法是，在虚拟地址送往TLB作地址翻译的同时， 利用地址的页内位移部分访问Cache，读取Cache的地址标志，然后与来自TLB的物理地址标志部分做比较。因为TLB往往比Cache的标志存储器小而且快，所以在Cache 读取标志的同时做虚地址转换不会降低Cache的命中时间。但这种方法有一个缺点:若Cache采用直接映象方式，那么 Cache 的容量不能超过一个页面的大小。 不过可以通过提高相联度使Cache容量不受限制，比如IBM3033的Cache就采用了16路组相联的映象方式。 5-25 第五章 存储器层次结构 要加快Cache命中操作，要避免上述容量限制， 可以将整个存储访问过程设计成深度(heaving)流水工作方式，其中TLB地址翻译仅作为流水线的一个工作段。因为TLB是容量小于Cache的独立部件，所以较易用流水方式实现。这种依赖于 CPU流水线高效性而获取高存储带宽的方法不会增加存储访问时间。 此外，采用虚拟寻址Cache(Virtual cache)也能改进Cache命中时间， 方法是将虚地址直接映象到Cache，对Cache命中来说可省去TLB表的地址翻译时间。 不过，实际上这种技术并未被广泛采用，原因有两个:第一，每当进程切换时，虚地址指向不同的物理地址，这就要求对Cache进行冲洗(flush)，即让Cache 中的所有数据作废。从图5.19可知，进程切换引起的Cache冲洗会使虚拟Cache的失效率大大提高。一种解决办法是在Cache地址标志中加入进程标志(PID)，这些标志由操作系统分配给各进程，仅当某一PID被重新分配时才需冲洗Cache。由图5.30可见，采用PID措施后，Cache失效率明显降低。第二，对于同一物理地址，操作系统和用户程序所用的是两个不同的虚地址。这样的双重地址被称为“别名地址”(alias)，它会导致同一数据在虚拟Cache 中有两个拷贝。如果其中之一被修改了，那么另一个就会过时(stale)。而在物理Cache中不会出现这种情况，因为数据访问首先被映象到同一物理存储块上。要解决别名造成的数据不一致问题，一般有两种方法。一是用称为“抗别名”(anti-alias) 硬件机制保证每个Cache行只对应唯一的物理地址标志。 二是通过软件强制别名共享一些相同的地 18址位。比如，SUN UNIX操作系统要求别名地址的最后18位必须相同，这样容量小于等于2(256K)B的直接映象Cache 中任何两行的物理地址标志都不会相同。这种软件要求也有助于简化大容量Cache或组相联Cache的抗别名硬件实现。(当然，从硬件设计者角度来看，最好的软件解决方法是不用别名地址。) 图5.30 虚拟Cache的失效率 5.5.2 减小失效损失 一、加快写失效操作 对于直达Cache， 减少失效损失最重要的技术措施是设置大小适中的写缓冲。这样只数据一写入缓冲，CPU就可继续执行。 但当读失效要访问的数据恰好还在写缓冲里尚未送入主存时，就可能出错。见例5?6。 例5?6 有以下指令代码序列: SW 512(R0)， R3; 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将映象到同一Cache行, 并设有一个4字长的写缓冲。问执行代码序列后R2和R3的值是否总相等, [解答] 代码执行的可能结果之一如下:执行第一条指令后，R3的值被写入了写缓冲。第2条取操作的地址索引正好映象到Cache的同一块，发生读失效，从主存1024地址处读出新数据块取入Cache。当执行第三条指令，试图从主存地址512处读入数据时，Cache再次发生读失效，但此时应写入主存512地址的R3值尚在写缓冲中，这时从主存512处取入Cache和R2的值将是更新前的旧值。此时，R2与R3不等。 要避免这种情况，在发生读失效时必须等写缓冲清空后再访问主存。但对于写直达Cache的几个字长的写缓冲来说，发生失效时，通常缓冲都不为空， 这样就会加大失效损失。据估计，等待4字长的写缓冲清空，平均失效损失增加50%。变通的办法是在发生读失效时，检查写缓冲中的地址与读请求地址是否冲突。若没有冲突且主存就绪，就让读失效操作继续下去，否则 5-26 第五章 存储器层次结构 暂停读失效操作，直到写缓冲里的存储块被送往主存。 设置写缓冲也能减小写回Cache的写失效损失。 只要增设一个和存储块同样大小的写缓冲存放脏块，读取新存储块的操作就可以先执行。在新的存储块取入相应Cache行后，CPU可以继续其工作，而写缓冲就可以和CPU并行操作将脏块写回主存。当发生读失效时，与前述情况类似，可以暂停CPU 执行读失效操作而等待写缓冲清空。 二、加快读失效操作 加快写操作有助于改进Cache/主存性能，但Cache 访问中绝大多数是读操作，因此，优化读失效显得十分重要。基本思想是，在整个存储块取入Cache 行之前就将要访问的字送给CPU。一般有两种策略: (1)尽早重启动策略(early restart)??一旦存储块中被访问的字从主存送达Cache，不管其余字是否已送至Cache，都立即将它送给CPU使其继续执行。 (2)乱序取策略(out-of-order fetch )??先向主存请求读取访问失效的字，一旦送达就送给CPU使其继续执行，同时将块中其余字取入Cache。这种方法有时也称之为绕取(wrapped fetch)。 应该注意的是，这些技术可能对处理器的性能有负面影响。读取存储块的重要依据是空间局部性原则，它表明下一次访问的字很可能就在本次所访问的存储块内。这样，在块中其余的字取入Cache之前，CPU有可能因紧接着的Cache 访问再次失效而出现暂停。此外在将其余字取入Cache的同时处理其它访问请求， 会使处理器的控制机制变得更为复杂。而乱序取策略也不象预期的那样有效，一个原因是存储块中的各个字被首先访问的概率是不等的。据实验测得，对于指令Cache中16字的块，其平均入口点在距高端字节2.8字的地方。实际上， 由于取指一般是顺序访问指令字，而在数据Cache中对数组的访问也是顺序进行的， 所以居块中高端的字被首先访问的概率最大。 三、两级Cache CPU的速度越来越快，主存的容量越来越大，而主存和CPU之间的速度差距也越来越大。因而体系结构的设计就面临这样相互矛盾的要求:一方面要将Cache 设计得更快(意味着容量小)以匹配CPU的速度增长，另一方面则要将Cache设计得更大(意味着速度慢)以缩小主存和CPU之间日益增大的速度差距。两级Cache就可以同时满足速度和容量这两方面的设计要求。即在原来的Cache 和主存之间再增加一个Cache。靠近CPU的那个Cache称为一级Cache，一般做在处理器芯片上，也称为片内Cache。它容量较小，速度与CPU的时钟周期相匹配。 新增设的 Cache 称为二级Cache，一般做在处理器芯片外，也称为片外Cache。二级Cache容量较大， 以便尽可能多的访问在二级Cache中完成而不必再去访问主存。二级Cache的典型结构参数见表5.5。 表5.5 二级Cache的典型结构参数 若用下标L1和L2分别表示一级和二级Cache，那么两级Cache的平均存储访问时间可定义如下: 平均存储访时间=命中时间L1+失效率L1×失效损失L1 其中 失效损失L1=命中时间L2+失效率L2×失效损失L2 所以 平均存储访问时间=命中时间L1+失效率L1×(命中时间L2+失效率L2×失效损失 L2) 5-27 第五章 存储器层次结构 式中二级Cache的失效率是指那些未命中一级Cache转而访问二级Cache 发生失效的概率，而不是所有CPU存储访问中未命中二级Cache的概率。为避免混淆，引进下面两个概念: 局部失效率(local miss rate )??本级 Cache 的失效访问次数除以该级Cache的总访问次数。式中的失效率L2即指二级Cache的局部失效率。 全局失效率(global miss rate)??本级Cache的失效访问次数除以CPU产生的所有存储访问次数。据此则有，全局失效率L2=失效率L1×失效率L2。 例5?7 假定在1000次存储访问中一级Cache失效40次，二级Cache失效20次，计算各失效率。 [解答] 失效率L1=40/1000=4% 局部失效率L2=20/40=50% 全局失效率L2=20/1000=2% 图5.31 显示了二级Cache 容量和二级 Cache 失效率之间的关系。 其中一级Cache容量为32KB。由图可见，当二级Cache的容量小于32KB(一级Cache 的容量)时，Cache失效率较高;当二级Cache的容量增大到256KB以后，单级 Cache 与多级Cache的全局失效率相近。 图5.31 二级Cache容量与失效率之间的关系 图5.31则显示了二级Cache容量与相对执行时间之间的关系，其中设4096KB的二级Cache的命中时间为一个时钟周期，它的相对执行时间定为1.00，而一级Cache为32KB的写回Cache。 图5.32 二级Cache容量与相对执行时间的关系 设计二级Cache结构参数时需要明确两级Cache的差别:一级Cache 的速度将直接影响CPU的时钟周期，而二级Cache的速度仅影响一级Cache的失效损失。 这样二级Cache可选用的结构参数就更多一些。 它的设计目标是:降低平均存储访问时间以减小CPI。 首先考虑选择二级Cache的容量。由于一级 Cache 中的所有信息可能都在二级Cache中，二级Cache的容量必须比一级Cache大。由图5.31可知，当二级Cache的容量仅比一级Cache大一点时，局部失效率很高。因而目前的计算机将二级Cache的容量设计得相当大，甚至和主存的容量一样大。若二级Cache的容量比一级Cache的大得多，那么全局失效率将和单级Cache的失效率相等，这意味着二级Cache实际上不会发生容量失效，而只需考虑冷启动失效和少量冲突失效。 接下来考虑映象方式，讨论二级Cache是否采用组相关映象方式更为有利。 先看下面的例子。 例5?7 已知:采用二路组相关映象方式将使二级Cache 的命中时间延长一个时钟周期的10%，直接映象二级Cache的命中时间L2=4个时钟周期，局部失效率 L2=25%，失效损失L2=30个时钟周期。二路组相关映象的局部失效率L2=20% ， 问二级Cache的相联度对失效损失有多大影响, 〔解答〕 二级Cache若采用直接映象方式，则 失效损失L1=4+30%*30=11.5个时钟周期 若采用二路组相关映象方式，将影响二级Cache的命中时间，由已知可得 : 失效损失L1=4.1+20%*30=10.1个时钟周期 实际上二级Cache总是与CPU和一级Cache同步操作，相应地二级Cache的命中时间必为 5-28 第五章 存储器层次结构 时钟周期的整数倍，所以二级Cache的命中时间要么压缩到4个时钟周期，要么延长至5个时钟周期。这两种情况下的一级Cache失效损失分别为: 失效损失L1=4+20%*30=10.0个时钟周期 失效损失L1=5+20%*30=11.0个时钟周期 由此可知二级Cache采用二路组相关映象方式总是比直接映象方式要好。 采用高相联度映象方式对于二级Cache是有利的，这是因为(1)提高相联度对二级Cache的命中时间影响很小，(2)提高相联度可减少冲突失效，而失效损失在平均存储访问时间中所占比例相当大。但是对大容量的二级Cache来说， 提高相联度并没有多大的好处，因为大容量已避免了很多因冲突引起的失效。 根据空间局部性原则，选用大的存储块对二级Cache是有利的。 尽管大的块对小容量Cache来说会增加冲突失效而导致失效率上升，但对大容量的二级Cache来说，没有这个问题。而且二级Cache的访问时间与主存访问时间相比相对较小， 大存储块不会使一级Cache的失效损失过大，因而两级Cache一般倾向于采用大存储块。图5.33示意了二级Cache选用不同块大小时的相对执行时间。 图5.33 二级Cache的块大小与相对执行时间的关系 最后还须考虑是否让一级Cache中的所有数据总是都在二级Cache中。如果一级Cache中的信息总是二级Cache的子集， 那么称此两级 Cache 具有多级蕴含性质(multilevel inclusion property)。这种多级蕴含性质有助于I/O和Cache 间的一致性检查，但会降低平均存储访问时间，因而两级Cache 有时需要采用不同大小的存储块:小容量的一级Cache采用小存储块，而大容量的二级Cache采用大块。在这种情况下，当二级Cache发生失效要将一存储块替换出去时，所有的在一级Cache中的对应此替换块的小块都要被作废，这将使一级Cache的失效率上升。 5.5.3Cache的一致性问题 Cache设计不仅要考虑提高CPU的执行时间，还应考虑对系统性能的影响，尤其是对I/O的影响。由于设置了Cache，数据信息既可以在主存中，也可在Cache 中。如果CPU是读取和修改数据的核心部件，那么CPU几乎不可能读到过时(stale )数据。但由于I/O的存在，CPU及I/O就有可能读到过时数据。如图5.34，如果 CPU 往Cache中写入，而主存中对应块的内容未更新，此时若CPU、I/O 设备要通过主存交换信息，那么I/O设备就有可能读到过时数据。同样，如果某一I/O设备已将新的内容送入主存的某一区域，而Cache中对应此区域的数据块却保持不变，这时CPU或其它设备访问这些数据块也会读到过时数据。这种因Cache 和主存的数据信息不一致而造成的错误通常被称为Cache的一致性问题。 图5.34 Cache的一致性问题 如果输入是将数据直接送入Cache，而输出则将数据从Cache中读出送往I/O 设备，那么I/O设备和CPU看到的将是相同的数据，Cache 的一致性问题也就解决了。但这种方法的困难之处在于它会干扰CPU的正常工作，I/O设备和CPU竞争访问Cache将导致CPU暂停而等待低速的I/O操作。并且输入操作也会影响到Cache:送入Cache的新数据在近期内可能不会被CPU访问。例如，当发生页面失效时，CPU可能只需访问该页面的某些字，按此方法要将该页 5-29 第五章 存储器层次结构 面全部调入Cache， 而实际上程序不可能访问到该页面中的所有字。 在包含Cache的计算机系统中，I/O的设计目标是既能避免过时数据问题，又尽可能不干扰CPU的正常工作。因此很多系统都是在主存中开辟I/O缓冲区，直接在 I/O设备与主存之间进行I/O操作。如果是写直达Cache，那么主存中总是保存着数据的最新拷贝，对输出来说不存在过时数据问题(这也是很多计算机采用直写技术的重要原因)。但对输入可能引起不一致的问题。软件的解决方法之一是:保证在输入缓冲区中的数据块不在Cache中。 方法之二是将缓冲区页面标记为“禁止高速缓冲”(noncacheable)，由操作系统控制将数据输入这样的禁止高速缓冲页面。这些方法能减少Cache的冲洗次数,从而降低因冲洗而造成的Cache失效率。 还有一种方法是在发生输入操作时,由操作系统将输入缓冲内的地址从Cache中“冲洗”出去。硬件的解决办法是检查输入操作地址，判定其是否在Cache中。若在Cache中，那么把Cache中相应行的有效位清除以避免过时数据。 上述所有方法也同样适用于写回Cache时因输出而引起的一致性问题。 在多处理机系统中也存在着Cache一致性问题，我们将在第九章加以详细讨论。 5.6 Alpha机的存储器层次结构 前面我们分别介绍了Cache/主存存储层次和虚拟存储器的结构和工作原理，本节将以采用Alpha芯片的DEC3000的存储体系为例， 综合介绍整个存储器的结构和工作过程。 图5.35 Alpha机的存储器层次结构 Alpha机的存储器体系结构如图5.35 。它由CPU寄存器、一级Cache、二级Cache 、主存、盘五级存储器构成。Alpha机的地址码长43位，指令、数据为64位。为解决流水线资源冲突问题，一级Cache采用独立指令/数据Cache的设计方案。指令Cache和数据Cache均为8KB的直接映象Cache。其中数据Cache的写命中以流水方式处理，采用直写技术，当写失效时用写不分配，并设有一个4×32B 的写缓冲。 片外二级Cache设计成直接映象的写回Cache，写失效时用写分配，容量为128KB至8MB(图中为DEC3000的配置，65536块×32B/块=2MB);为减少其失效损失，设置了一个大小为一个存储块32B的替换块缓冲器，即二级Cache的写缓冲。它的失效损失为3? 16个时钟周期。DEC3000的主存由4块存储母板组成，每块母板上设2?8个单面或双面的单列直插式存储模块(SIMM?Single inline memory modules)，每个单面存储模块有10片DRAM，其中8片用于存储信息，2片用于纠错。DRAM可选用1Mb、 4Mb或16Mb的。因此主存容量的可选范围为8MB(4*2*8*1*1Mb/8)至1024MB(4*8* 8* 2*16Mb/8)。主存与二级Cache之间的数据通路宽度为16B，平均传输时间为36个时钟周期/信息块(32B)。为加快虚实地址翻译，分别设置了全相联的指令TLB(iTLB)和数据TLB(dTLB)。iTLB可容纳12个页表项，其中8个用于8KB的页面， 4 个用于4MB的大页面(4MB的大页面是为操作系统或数据库一类的大程序而设置的)。DTLB包含32个页表项，页面大小为8KB?4MB。此外，为支持指令执行流水线，采用了指令预取技术， 设置了一个指令预取流缓冲器 ( instruction pre-fetch stream buffer)，容量大小为一个块(32B)。 当Alpha机加电后，首先由硬件将指令自片外PROM加载到指令Cache中。此时Cache中的指令均为有效指令，所以可忽略指令 Cache 的有效位。 同时由硬件清除数据Cache的有效位。PC被置为核心代码段(kseg segment)的始址，因而可避免TLB的地址翻译。然后由核心代码为用户进程更新iTLB相应页表项。若TLB访问失效， 则系统将调用特权结构库代码(PAL ,Privileged Architecture Library)更新TLB。PAL是专门扩充的能访问低层硬件的机器语 5-30 第五章 存储器层次结构 言代码。当执行PAL代码时异常事件被禁止，存储管理系统也不检查指令访问是否为侵权行为，使PAL能填充TLB。一旦操作系统准备开始执行一个用户进程，就将PC置为段0的合适地址。 存储体系的工作流程如下: 指令虚地址的页帧地址送往iTLB(?)。iTLB同时查找12个页表项，寻找匹配的有效页表项作地址翻译，除地址翻译外，TLB 还检查本次访问是否引起异常处理(?)。异常事件指对页面作侵权访问或页面不在主存中，此时需作异常处理。在步骤?的同时，虚地址页内位移的8位索引被送往指令Cache(? )， 访问指令Cache得到地址标志。然后地址标志与iTLB变换所得的21 位物理地址比较(?)，检查是否匹配。若地址匹配，则由块内偏移地址得到8B要访问的指令字送往CPU(?)，指令流访问至此结束。若访问指令Cache不命中，则在开始访问二级Cache(?)的同时检查指令预取流缓冲器(?)。如果在指令预取流缓冲器里找到要访问的指令字(?)，则8B指令字被送往CPU，指令所在的整个存储块被写入指令Cache(?)，并且取消对二级Cache的访问请求。注意，步骤?至步骤?仅需1个时钟周期。如果要访问的指令不在指令预取流缓冲器里，那么就要到二级Cache 中去读取指令所在的存储块。由于DEC3000的二级Cache容量是2MB=65536块*32B/块，所以29位存储块地址被分成13位地址标志和16位索引。其中16位索引送到二级Cache读取二级Cache的标志(?)。如果该标志与地址相匹配(11)，那么指令所在的存储块被送往指令Cache。因为两级Cache间的数据通路宽度为16B，所以32B存储块是分两次分别以 5 个时钟周期传送的。在此同时，发出预取下一个顺序存储块的请求，这个存储块将在随后的10个时钟周期内送往指令预取流缓冲器(13)。其中预取存储块的地址不必经iTLB变换，只需在引起指令cache失效的指令地址上加32B即可。如果新地址与失效指令地址在同一页面内，则预取，否则不作预取。 如果访问二级Cache又不命中，那么变换所得的物理地址被送往主存(14) 以读取新的存储块。由于二级Cache是写回Cache，因而在失效时可能要将替换块送回主存。首先需检查替换块是否为脏块，若为脏块，则被送入替换块缓冲器( Victim buffer)，为新的存储块腾出空间(15)。一旦新的存储块从主存送达， 立即被装入二级Cache(16)。然后，替换块缓冲器中的旧块被送回主存(17)。 由于替换块缓冲器只能容纳一个存储块,所以二级Cache再次失效时,就会被停顿,直至替换块缓冲器清空。 假定最初读取的这条指令是一条取数指令。那么随后的操作是将数据虚地址的页帧地址送往dTLB(18) 。 与此同时， 虚地址页内位移中的 8 位索引被送往数据Cache(19)。如果在dTLB中找不到有效的页表项，那么就会自陷调用PAL代码读取该数据虚地址的页表项。最坏情况下，数据所在页面不在主存，此时操作系统将从磁盘上读取该页面(20)。由于在页面故障处理期间可以执行上百万条指令，所以如果有进程等待运行，操作系统就将切换到其它进程上去。 假设在dTLB中找到了有效页表项作地址翻译(21)，那么数据Cache 的标志和数据物理地址做比较(22)。若地址匹配，则将块中要访问的8B数据送往CPU(23);否则，访问数据Cache失效，此时将访问二级Cache读取数据。访问二级Cache 的步骤与前述指令失效时的情况相似。 假定最初读取的这条指令不是取指令,而是一条存数指令,那么数据虚地址的页帧地址和页内位移将分别被送往dTLB和数据Cache(18、19)。 在地址翻译时也要检查对页面的访问是否为侵权访问。然后变换所得的物理地址被送往数据Cache， 并作地址标志匹配检查(21、22)。由于数据Cache用的是写直达写不分配策略， 要存储的数据被同时送往写缓冲(24)和数据Cache(25)。如前介绍，数据Cache的写命中是以流水方式处理的，因而在检查本次访问的地址与标志是否匹配的同时，前一次写命中的数据被写入数据Cache(26)。若本次写访问又命中数据Cache，则存储的数据被送入写流水缓冲器，否则，由于是写不分配Cache，数据仅被送入写缓冲。 写缓冲有4个数据入口，每个可存放一个数据块。如果写缓冲满，那么CPU就必须暂停直到其中的一块被送往二级Cache。若缓冲器不满，CPU就继续执行，而要存储的数据字的地址被送至写缓冲(27)。若该数据字所在的存储块已经在写缓冲里，那么后续的要写入的数据将不断填入这个存储块。 5-31 第五章 存储器层次结构 所有存数指令的数据最终都将被送至二级Cache。如果写操作命中二级Cache，那么数据就被写入Cache(28)，并被标记为是脏块。由于二级Cache是写回Cache ，不能用流水方式处理写操作，因而一次32B的整块数据写操作要花15 个时钟周期，其中5个时钟周期用于地址检查，10个时钟周期用于传送数据。而一次小于等于16B的写操作要花10个时钟周期:5个时钟周期仍用于地址检查，5个时钟周期用于数据传送。所以在数据字被送入写缓冲时作地址检查就很有必要，它能更好地利用两级Cache之间的数据带宽。 如果访问二级Cache失效，就要检查替换块是否为脏块。若替换块是脏的， 它就被移动到替换块缓冲器(15)里，为新存储块腾出位置。若写入的是整个数据块，那么将数据送入Cache并标记为脏块，整个存数操作就完成了。 如果是一个存储块的部分写操作，那么由于二级Cache在失效时用写分配策略 ，所以还需访问主存将存储块的其余字读入二级Cache。 习题 5.1 在这个练习中，我们将运行一个程序来评估一个内存系统的行为。其中的关键是要能准确地计时和让程序进入内存系统以申请不同层次的结构。下面列出UNIX系统中的C代码。第一部分是一个过程，它利用UNIX系统中的功能获得准确的用户CPU时间;这个过程如果要在其他系统上运行，就需要做一些改动。第二部分是一组循环语句，用来进行不同跨度和Cache大小的读写内存操作。为了得到准确的Cache计时，这组代码要重复多次。第三部分仅仅计算循环的开销，这样我们可以从总时间中把这部分时间减去，以得到准确的内存访问时间。最后打印每次不同大小和跨度时的访问时间。你可以根据要回答的问题和所要测量的系统内存大小来修改CACHE_MAX 的值。下面这段代码是从伯克利大学的Andrea Dusseau写的一个程序中取来的，基于Saavedra-Barrera[1992]的详细描述。 #include #include #include #include #define CHCHE_MIN (1024) /* smallest cache */ #define CACHE_MAX (1024*1024) /* largest cache */ #define SAMPLE 10 /* to get a larger time sample */ #define CLK_TCK 60 /* number clock ticks per second */ int x[CACHE_MAX]; /* array going to stride through */ double get_seconds(){ /* routine to read time */ struct tms rusage; times(&rusage); /* UNIX utility; time in clock ticks */ return(double)(rusage.tms_utime)/CLK_TCK; } void main(){ int register i, index, stride, limit, temp; int steps, tsteps, csize; double sec0, sec; /* timing variables */ for (csize = CACHE_MIN; csize<=CACHE_MAX, csize = csize*2) for (stride =1; stride<= csize/2; stride = stride*2){ sec = 0; /* initialize timer */ limit = csize - stride +1 ; /* cache size this loop */ 5-32 第五章 存储器层次结构 steps = 0; do { /* repeat until collect 1 second */ sec0 = get_seconds(); /* start timer */ for (i=SAMPLE*stride; i!=0;i=i-1) /* larger sample */ for (index=0; index i (a sub j) = 0; N这是因为7是具有形式2-1的基数。由于上面表达式中的乘法表示成2的幂次，它们可以通过二进制移位来替换(一种非常快速的操作)。 4. 现在地址已经足够小通过在ROM中查找模数来得到组号(bank number)。 最后我们回答下列问题: Na. 给定2-1个内存bank, 作为上面第三步中间结果的一个结果，M位长的一个地址大小大约减少多少,给出通用公式，并说明当N=3和M=32时的情况。 b. 画出能通过给定的32位地址从7组内存中挑选出正确结果的硬件块结构图。假设每组(bank)8位宽。在这个组织中地址和ROM有多大, 5.10 减少击不中的一种方法是预取下一数据块。Alpha 21064使用了一个简单而有效的策略，当第i块被访问时检查第i+1块是否在高速缓存中，如果不在就进行预取。你是否认为随着块长度的增加这种自动预取技术多少有些有效,为什么,那么随着高速缓存的增加是否也相同呢,为什么, 5.11 Smith和Goodman[1983]发现，对一个小型指令高速缓存，使用直接映射的高速缓存比使用LRU替换算法全联系的高速缓存表现出更好的性能。 a. 试解释为什么会是这样。(提示:你不可能用三C模型来解释，因为它忽略了替换策略。) b. 利用Cache模拟器观察结果是否一致。 5.12 现在二级Cache包含了几兆数据。虽然新的TLB提供不同长度的页来映射更多内存，大多数操作系统并没有从中获得什么好处。是否在高速缓存中能找到的数据在TLB中却可能找不到,这样使TLB被识别以避免这种击不中, 5.13 如果你根据给定的书中的联系观察冲突击不中，随着容量的增加冲突击不中数目上上下 5-35 第五章 存储器层次结构 下。例如，对于二组联系映射，一个2KB的高速缓存的击不中率是0.010，4KB高速缓存是0.013，8KB高速缓存则是0.008。为什么会是这样呢, 5.14 如果一个完美内存系统的基本CPI为1.5，对于下列这些高速缓存CPI值分别是多少,利用书中的图表。 a. 直接映射，16KB统一写回高速缓存。 b. 二组联系，16KB统一写回高速缓存。 c. 直接映射，32KB统一写回高速缓存。 假设内存延迟为6个时钟，传输率为每时钟周期4个字节且其中50%的传输是脏(dirty)的。每个数据块有16个字节，20%的指令是数据传输指令。高速缓存按地址顺序取块中的字，CPU拖延到块中所有的字都被读取为止。没有写缓冲区。一次TLB击不中要花20个时钟。一个TLB并不降低一个高速缓存的速度。对于TLB来说有0.1%的击不中率，这其中既包括直接从CPU来的地址访问，也包括从Cache击不中来的地址。当上述Cache是虚拟寻址或者物理寻址时分别对一个TLB的性能有什么影响, 5.15 数据通用(Data General)描述了为88000系统结构的ECL实现设计的一个三级高速缓存。那么计算三级高速缓存的平均访问时间的公式是什么, 5-36