计算机系统结构电子教案

第7章存储层次（P188）

MemoryHirarchy长期存在的问题：在合理的总价格限制下，单一型主存器件的速度跟不上CPU的发展，容量不能满足软件尺寸扩大。本章学习提高主存系统性能/价格比的几种结构化方法，重点是“Cache-主存层次”，焦点问题是如何使流水线每拍完成一次访存。本章基本公式：(1)平均时间T=P1×T1+P2×T2其中P1+P2=100%，并且T1和T2都可以再用该式迭代展开，复杂时，可用概率树来表示（全概率公式）；(2)实际时间T=理想时间+P3

×每次额外开销时间其中P3是不利事件发生概率。2014.2.171计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第1页!7.1存储层次原理及性能指标（P188）7.1.1基本原理“存储层次”的定义：（参见P189第3段）由2种或多种存储部件构成的复合存储系统，通过内部管理机构的自动更换机制，能够不断将大容量低速存储部件中的活跃内容复制到小容量高速存储部件中（后者作为前者的局部副本）。它既能满足CPU的快速存取需要，又有很大的存储容量，平均单位价格也很低，等效于同时满足3方面要求的理想单一存储部件。依据：程序访问的局部化原理（时间局部化，空间局部化）。模型：如右图所示，存储层次由n层组成，满足3个不等式：TAi<TAi+1，ci>ci+1，Si<Si+1。2014.2.172计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第2页!存储层次的基本术语

逻辑地址（又称为相对地址、虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。

物理地址（又称为绝对地址、实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从M1到Mn各层都有自己的物理地址空间，而对当前执行的程序模块来说，逻辑地址空间只有一个。

地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。

地址变换（又叫虚实变换）指逻辑地址到物理地址的变换过程或者算法。

页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。

实页争用又叫实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。

页和块：前者用于主-辅层次，后者用于Cache-主存层次，意义相同。2014.2.173计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第3页!7.7.1存储层次的管理方式(续)(2)页式管理。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。我们把用户文件划分得到的一个长度单位称为“虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页”。页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。页式管理方法的虚实变换算法是查页表。两种层次都用此技术。(3)段页式管理。它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表。段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。它的实现最复杂，仅用于主存—辅存层次。段页式管理方法的最小调度单位仍是页，基本操作可归于页式管理。2014.2.174计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第4页!课堂练习7.1（续）虚地址经变址寻址和基址寻址(B)+(X)+D形成。现有一个程序，出现下列访问主存的操作：(1)列出产生主存页面失效的操作序号。(2)如果不发生主存页面失效的话，计算访问主存的物理地址。(3)列出非法操作的序号。(4)列出被修改过的主存页面号。2014.2.175计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第5页!7.1.4存储层次的基本问题(P192)①映象规则——一个虚块（页）被允许放到哪些实块（页）上；②查找算法——如何在实存中找到指定的虚块（页）（主要是虚实变换）；③替换算法——块（页）争用时，调出哪个虚块（页）；④写策略——写存储层次的具体操作。典型存储层次（PC计算机，以Intel芯片组为例）2014.2.176计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第6页!(3)速度

表现访问速度的参数较多。命中率H：被访问数据事先已在M1的概率不命中率F：不命中的概率，又称失效率，F=1-H平均访存时间：命中时的访存时间为TA1，不命中时的访存时间为TA2，平均访存时间则是它们的概率均值其中TM是失效开销，TM=TA2+TB22014.2.177计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第7页!假设：TAi表示第i级器件读/写时间；TBi表示第i级向上级传送时间。根据模型有：命中M1时：TA=TA1命中M2时：TA=TA1+TA2+TB2≈TA2……命中Mn时：TA=TA1+TA2+TB2+……+TAn+TBn≈Tan区别：单次访问总时间近似等于本次到达的最低一层的访问时间，因为每层都只访问一次；大量访问的平均时间则由各层访问时间共同构成，因为较高层的一次访问时间虽短，但它们被访问的百分比远远大于较低层。多级存储层次的单次访问时间2014.2.178计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第8页!多级存储层次的平均访问时间1

M1103BTA1=1us103B

M2106BTA2=10usM3109BTA3=100us109B(a)(b)例7.0有一个109字节的程序被装入右图所示的M3准备运行。假定指令字长=1字节，程序中无转移指令和内存读/写指令。忽略传送时间TB。(1)按图(a)求TA和e；(2)按图(b)推导三层体系的TA公式；(3)按图(b)求TA和e；(4)比较(1)(3)结果，有何结论？解：2014.2.179计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第9页!多级存储层次的平均访问时间3(4)结论：插入中间层后，层间速度差减少，访问效率提高。2014.2.1710计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第10页!刚才推导中使用的不命中率都是局部不命中率。为了避免混淆，有必要分清两种不命中率：全局不命中率是一个比局部不命中率更有意义的指标，它指出了在CPU发出的所有访存请求中，究竟有多大比例是穿过该级，到达下一级存储器的。7.4.1局部不命中率与全局不命中率（P214）2014.2.1711计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第11页!多级存储层次的平均访问时间公式重写将这些局部不命中率、全局不命中率的定义式代入到前面的多级存储层次平均访问时间公式中，我们可以得到更容易记忆的公式形式：2014.2.1712计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第12页!(2)TA＝TA1＋F1×(TA2＋F2×TM2)＝1＋4%×(10＋50%×100)＝1＋4%×60＝3.4个时钟周期式中后面部分4%×60为每次访存的平均停顿时间（即失效开销）：每次访存的平均停顿时间（即失效开销）＝4%×60＝2.4由于平均每条指令访存1.5次，所以：每条指令的平均停顿时间＝2.4×1.5＝3.6个时钟周期习题7.9例7.3（续）2014.2.1713计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第13页!地址映象问题的提出1.页表占用空间过大问题页表必须存放在实存M1里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在M2。页表占用空间=页表行数×每行宽度其中，页表行数=虚存容量/页面大小以Win2K为例，虚存页表=4×4G/4K=22

×232/212=222=4MB

Cache-主存层次的页表=4×4G/16=230=1GB，而Cache1只有32K减少页表空间的思路分减少行数和减少行宽两类。2.相联目录表方法（又称“实页表”）/减少行数仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。P196图7.10示意Cache中用多字并行比较方法实现的相联目录表。此法须严格限制字数。3.快慢表方法（TLB）/减少行数4.改变地址映象/减少行宽2014.2.1714计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第14页!全相联的地址映象方式与地址变换原理示意图(a)(b)2014.2.1715计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第15页!(2)直接相联(directmapped)直接相联是一种最强的约束关系，它规定每个虚页只对应唯一的实页。为了便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现起来非常简单，因为在二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位，如下页示意图(c)所示。例5.2已知虚页号=7，实页总数=4，用直接相联求实页号。解：可用十进制形式求：7mod4=3；也可用二进制形式求：由于n=4，所以log2n=2，取7的二进制形式111B的最低2位，得11B，即3。直接相联映象方式不需要借助页表来进行虚实变换，显然大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留），但是由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率下降。这种映象方式主要用于对实存价格、速度敏感的Cache-主存层次。直接相联的“候选位置”为1个实页，它又被简称为“1路Cache”。2014.2.1716计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第16页!(3)组相联(setassociative，P194)组相联映象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。具体做法是先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合，对应的虚实组之间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”。如图(c)所示。采用组相联映象方式时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低；另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。这种映象方式性价比较好，在Cache-主存层次中被普遍使用。实组内页数被称为“路数”，又称为“相联度”（associativity）,它表明一个虚页的选择范围。下页图示为2路组相联（2-waysetassociative）。2014.2.1717计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第17页!组相联的地址映象方式与地址变换原理(c)2014.2.1718计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第18页!位选择组相联的地址映象方式与地址变换原理(a)(b)2014.2.1719计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第19页!(1)页表法

每个虚页对应1项，虚页号就是项号，项内存储实页号，如课堂练习7.2。这种方法原理简单，但是占用空间非常大。当页表尺寸超过1页时，它本身还要按页面尺寸分割成许多分散存放的子表，再造一个“表上表”来找到当前需要的子表。进一步发展就会形成“多级页表”，导致虚实变换分多步进行，时间大大延长。7.2.3虚实变换基本方法（P195）2014.2.1720计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第20页!(3)快慢表方法（P231）这是页表法的一种加快方案。地址变换缓冲器TLB（TranslationLook-asideBuffer）是一个专用的高速缓冲器，用于存放近期经常使用的页表项副本，TLB利用程序的局部性原理，以小表代替大表，缩短查找时间。7.2.3虚实变换基本方法（续2）2014.2.1721计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第21页!(5)单体多字存储器＋多比较器查表方法（P196第2段）这是目录表法的一种廉价方案，对组相联非常适用。限制条件是组内页数不太多，下图为4的情况。7.2.3虚实变换基本方法（续4）2014.2.1722计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第22页!Cache─主存层次虚实变换实现（直接相联）快命中方案：直接相联，目录表法（P196，图7.9）举例：为了方便用10进制讨论。设虚块号=000～999，实块号=0～9，于是有索引=0～9，而标识=00～99。索引=0的实块里装的虚块标识可以是00，01，……，99，对应的虚块号就是000，010，020，030，……，990。2014.2.1723计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第23页!7.3.5伪相联（P209）优点缺点直接映象组相联命中时间小命中时间大不命中率高不命中率低“伪相联”又称“列相联”，按原理还可称为“伴生Cache”。(1)比较直接相联、组相联的优缺点从例7.4我们将看到，直接相联的命中时间较短，而多路组相联的失效率较低，所以它们的平均访问时间依两个因素的作用大小而互有输赢。有没有什么方法取二者之长呢？(2)伪相联的优点伪相联就是直接相联、组相联的一种组合方案。优点是命中时间短、不命中率还低，所以它的平均访问时间往往比直接相联、组相联都短。2014.2.1724计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第24页!(4)快速命中与慢速命中

要保证绝大多数命中都是快速命中，就是命中率要高。一种简单的办法是在出现伪命中时，交换上下两个区的内容，因为当前在下区的块很可能是“常用块”。伪命中情况下需要增加2个额外的时钟周期（其中1个周期是多找1次花去的，1个周期是交换操作所需）。(5)伪相联的缺点：

它的多种命中时间使得CPU流水线上各指令之间的时间对齐变得困难，所以往往应用在离CPU比较远的Cache上，比如L2-Cache。7.3.5伪相联（续2）2014.2.1725计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第25页!例7.3.5（补充，2版P198例5.6）

一个伪相联Cache，当在按直接映象找到的位置处没有发现匹配、而在另一个位置才找到数据（伪命中）时需要增加2个额外的周期。其它已知条件如下表所示。(1)推导伪相联平均访存时间公式；(2)当Cache容量分别为2KB和128KB时，直接映象、两路组相联和伪相联这三种组织结构中，哪一种的平均访存时间最短？7.3.5伪相联（续4）2014.2.1726计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第26页!将后3式依次向前代入，得到所需公式：

平均访存时间伪相联＝命中时间1路＋(不命中率1路－不命中率2路)×2周期＋不命中率2路×不命中开销1路(2)当Cache容量为2KB时：平均访存时间1路＝1.0＋0.098×50＝5.90平均访存时间2路＝1.1＋0.076×50＝4.90平均访存时间伪相联，2KB＝1.0＋(0.098－0.076)×2＋(0.076×50)＝4.844当Cache容量为128KB时：平均访存时间1路＝1.0＋0.010×50＝1.50平均访存时间2路＝1.1＋0.007×50＝1.45平均访存时间伪相联，128KB＝1.0＋(0.010－0.007)×2＋(0.007×50)＝1.356可见，对于这两种Cache容量，伪相联Cache都是速度最快的。7.3.5伪相联（续6）2014.2.1727计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第27页!各次作业应交的内容作业9（第10次课）7.112014.2.1728计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第28页!所以在计算平均CPI时，应该加上存储器平均“不命中开销”。本章仅考虑存储器等待在平均CPI计算中的作用，暂时不考虑流水线因相关、冲突导致的延迟，所以上式简化写为又被称为以下是计算二者关系的几组常用公式。7.2.7访存时间对CPU性能的影响22014.2.1729计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第29页!(4)程序执行时间（即“CPU时间”）：a.b.c.d. (7.3)e. (7.1)f. (7.2)g.7.2.7访存时间对CPU性能的影响42014.2.1730计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第30页!例7.2（P204）

考虑两种不同组织结构的Cache：直接映象Cache和两路组相联Cache，

(1)理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次；

(2)两种Cache容量均为64KB，块大小都是32B；

(3)在组相联Cache中，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。这是因为对Cache的访问总是处于关键路径上，对CPU的时钟周期有直接的影响；

(4)这两种结构Cache的不命中开销都是70ns（在实际应用中，应取整为整数个时钟周期）；

(5)命中时间为1个时钟周期，64KB直接映象Cache的不命中率为1.4%，相同容量的两路组相联Cache的不命中率为1.0%。

分别比较它们的平均访存时间、CPU时间。2014.2.1731计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第31页!例7.2（续2）(2)

CPU时间＝IC×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间＝IC×（CPIexecution×时钟周期时间＋每条指令的平均访存次数×不命中率×不命中开销×时钟周期时间）代入参数得：CPU时间1路＝IC×(2.0×2＋(1.3×0.014×70))

＝5.27×ICCPU时间2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))

＝5.31×IC直接映象Cache的CPU时间短一些。5.31×ICCPU时间1路─────＝─────＝1.015.27×ICCPU时间2路2014.2.1732计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第32页!(1)L2-Cache采用直接相联

平均访问时间

＝10.0＋25%×50＝22.5

个时钟周期(2)L2-Cache采用两路组相联

平均访问时间

＝10.1＋20%×50＝20.1

个时钟周期(3)两路组相联的命中时间之所以比直接相联增加0.1个时钟周期，是因为虚实变换按组查表后要进行多路选择（P199图7.12和P198第8段），需要额外增加时间。具体实现方案可以把时钟周期调慢为1.01倍（这将使所有动作都减慢1%，甚至主存访问），或者仅在命中时增加1个时钟周期。按增加1个时钟周期的方案，L2-Cache的命中时间为11，有：

平均访问时间＝11＋20%×50＝21.0

个时钟周期(2)(3)情况下L2-Cache的平均访问时间都比直接相联小，所以L2-Cache采用两路组相联性能更好。注：教材中该例中说“幸运的话，取整为10个周期”，就是说多路选择动作时间有可能“挤”进原有的10周期中，习题中通常不这样给条件。习题7.10例7.4（续）2014.2.1733计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第33页!Windows2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存，需要使用物理地址。物理内存以字节（8位）为单位编址。物理内存分页，一个物理页的大小为4K字节，第0个物理页从物理地址0x00000000处开始。由于页的大小为4KB，就是0x1000字节，所以第1页从物理地址0x00001000处开始。第2页从物理地址0x00002000处开始。可以看到由于页的大小是4KB，所以只需要32bit的地址中高20bit来寻址物理页。使用了分页机制之后，4G的地址空间被分成了固定大小的页，每一页或者被映射到物理内存，或者被映射到硬盘上的交换文件中，或者没有映射任何东西。对于一般程序来说，4G的地址空间，只有一小部分映射了物理内存，大片大片的部分是没有映射任何东西。物理内存也被分页，来映射地址空间。对于32bit的Win2k，页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。Windows2000虚拟存储器12014.2.1734计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第34页!物理地址的转换，使用物理地址取出值，完成指令。对于IntelCPU来说，分页标志位是寄存器CR0的第31位，为1表示使用分页，为0表示不使用分页。对于初始化之后的Win2k我们观察CR0，发现第31位为1。表明Win2k是使用分页的。

CPU把虚拟地址转换成物理地址：一个虚拟地址，大小4个字节(32bit)，包含着找到物理地址的信息，分为3个部分：第22位到第31位这10位（最高10位）是页目录中的索引，第12位到第21位这10位是页表中的索引，第0位到第11位这12位（低12位）是页内偏移。对于一个要转换成物理地址的虚拟地址，CPU首先根据CR3中的值，找到页目录所在的物理页。然后根据虚拟地址的第22位到第31位这10位（最高的10bit)的值作为索引，找到相应的页目录项(PDE,pagedirectoryentry),页目录项中有这个虚拟地址所对应页表的物理地址。有了页表的物理地址，根据虚拟地址的第12位到第21位这10位的值作为索引，找到该页表中相应的页表项(PTE,pagetableentry),页表项中就有这个虚拟地址所对应物理页的物理地址。最后用虚拟地址的最低12位，也就是页内Windows2000虚拟存储器32014.2.1735计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第35页!32bit的一个指针，可以寻址范围0x00000000-0xFFFFFFFF，4GB大小。也就是说一个32bit的指针可以寻址整个4GB地址空间的每一个字节。一个页表项负责4K的地址空间和物理内存的映射，一个页表1024项，也就是负责1024*4k=4M的地址空间的映射。一个页目录项，对应一个页表。一个页目录有1024项，也就对应着1024个页表，每个页表负责4M地址空间的映射。1024个页表负责1024*4M=4G的地址空间映射。一个进程有一个页目录。所以以页为单位，页目录和页表可以保证4G的地址空间中的每页和物理内存的映射。每个进程都有自己的4G地址空间，从0x00000000-0xFFFFFFFF。通过每个进程自己的一套页目录和页表来实现。由于每个进程有自己的页目录和页表，所以每个进程的地址空间映射的物理内存是不一样的。两个进程的同一个虚拟地址处（如果都有物理内存映射）的值一般是不同的，因为他们往往对应不同的物理页。4G地址空间中低2G，0x00000000-0x7FFFFFFF是用户地址空间，4G地址空间中高2G，0x80000000-0xFFFFFFFF是系统地址空间。访问系统地址空间需要程序有ring0的权限。Windows2000虚拟存储器52014.2.1736计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第36页!7.2.5替换算法(P198)上面所讲的地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。不命中时需要增加的操作就是首先调出一页，调出之后再调入称为“替换”。替换算法要解决的是选择调出对象的问题。替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。2014.2.1737计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第37页!从LFU到LRU的近似逻辑推理：近期最少使用LFU→最近一个单位时间内使用次数最少→相邻两次使用的平均间隔时间最大→上次使用时间离现在最久→最久没有使用LRU偶然偏差：使用稀疏的页面有可能恰巧刚刚用过，离现在更近。统计性能：“现在”离“上次”使用时间的平均距离，应为相邻两次使用时间距离的1/2，所以大多数情况下LRU与LFU的判断结论应该是一致的。2014.2.1738计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第38页!课堂练习7.3（郑纬民题3-19中3、4、6、8小问，稍改）假设在一个采用位选择组相联映象方式的Cache中，主存由B0～B7共8块组成，Cache有2组，每组2块，每块的大小为16个字节，采用LRU块替换算法。程序执行过程中依次访问这个Caehe的块地址流如下：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3(3)画出主存与Cache之间各个块的映象对应关系。(4)Cache块号记为C0、C1、C2和C3，列出程序执行过程中Cache地址流。(6)计算Cache的块命中率。(8)如果上述地址流中的每个块号实际代表对该块的连续16次访问，计算在这种情况下的Cache命中率（也称为存储单元命中率）。2014.2.1739计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第39页!7.2.4Cache的工作过程（P197）概况：块大小32B，块数256，直接映象，写直达，采用不按写分配2014.2.1740计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第40页!Cache“写”访问2014.2.1741计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第41页!(2)混合式（统一式）Cache在命中情况下，每次有效MEM操作都会迫使后面一条指令的IF停顿（结构冲突）。分离式Cache与混合式Cache（续1）混合式Cache结构示意图IFIDWBMEMEX混合Cache下一级存储器2014.2.1742计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第42页!例7.5（2版P186例5.1）假设Cache的命中时间为1个时钟周期，失效开销为50个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，根据上表所列的失效率，试问指令Cache和数据Cache容量均为16KB的分离Cache与容量为32KB的混合Cache相比，哪种Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？解：(1)平均失效率测试表明，（经验值）。平均失效率分离16KB+16KB＝(75%×0.64%)＋(25%×6.47%)＝2.10%

平均失效率混合32KB＝1.99%（查表）

混合Cache较低。分离式Cache与混合式Cache（续3）2014.2.1743计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第43页!平均访存时间＝命中时间＋不命中率×不命中开销可以从三个方面改进Cache的性能：降低不命中率减少不命中开销减少Cache命中时间本书介绍了17种Cache优化技术（P223表7.5）8种用于降低不命中率5种用于减少不命中开销4种用于减少命中时间本课堂内只了解一下其中两个概念，细节内容不作深入了。7.2.8改进Cache性能（P205）2014.2.1744计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第44页!减少三种不命中的方法强制性不命中：增加块大小，预取（本身很少）容量不命中：增加容量

（抖动现象）冲突不命中：提高相联度（理想情况：全相联）许多降低不命中率的方法会增加命中时间或不命中开销7.3.1三种类型的不命中（续）2014.2.1745计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第45页!7.6并行主存系统（非层次技术，P223）本小节不在课堂讲授，供需要的同学自学。并行存储器技术可以提高主存系统的整体等效速度，实际应用中，常将它与存储层次技术组合使用，可以互为补充，获得很高的性能。并行存储器技术的基本思想是用多个独立的存储部件组成主存系统，让它们并行工作，在一个存储周期内可以访问到多个数据，从而实现较高的存取流量。教材P224～P224介绍了3种提高主存速度的技术：1.多字宽存储器；2.多体交叉存储器；3.避免体冲突的软硬件方法。下面介绍提高访问常用的低位多体交叉访问存储器。2014.2.1746计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第46页!主存地址与结构参数的换算（P225）：其中：n──存储体个数，A──主存地址，

j──体内地址，k──体序号（k=0，1，2，…，n-1）例5.1已知n=4，问主存地址13是在几号体的几号单元？解：由于n=4，体选译码信号使用主存地址的最低log2n=2位，所以地址13（其二进制为1101B）对应的体号k=1（即01B）、体内地址j=3（即11B），也就是说，地址13位于1号体的3号单元（参看前一页插图）。 根据上式，所有k值（即体号）相同的地址之间均相差n的整倍数，称之为“模n同余”。2014.2.1747计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第47页!

Kg=010.0g=0.24.463.682.00g=0.51.00g=10110n并行存储器平均加速倍数（西安电子科技大学李学干教材2版）1.只考虑取指地址序列（假设地址顺序递增，直至出现一条转移指令）：其中g是指令序列中出现转移指令的概率。此公式在右图中用绿线表示。2.只考虑取数地址序列（假设地址完全随机）此公式在右图中用红线表示。2014.2.1748计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第48页!7.7.1存储层次的管理方式(P230)根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在3种存储层次管理方式。目前在主存—辅存层次实现中，具体机器可能采用3种方式中的某1种，而Cache-主存层次普遍只采用第2种，因为它简单，便于硬件实现。(1)段式管理。段是程序中的一个逻辑单位，可以是一个程序模块，或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。每段使用独立的逻辑地址空间，即都从0开始计算地址。段式管理方法的主要缺点是各段长短不一，调进调出之后容易形成大量不规则的零碎空间。段式管理方法的虚实变换算法是查段表。因其实现较复杂，仅用于主存—辅存层次。2014.2.1749计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第49页!课堂练习7.1一个页式虚拟存储器按字节编址，页面大小为1K字节，每个数据的字长为4个字节。现有一个程序的页表如下：表中的装入标志为“1”表示该虚页已经装入主存，为“0”则表示还未装入主存。修改标志为“0”表示该页还没有被修改过，为“1”则表示该页已经被修改过。访问方式“RW”表示该页可以读可以写，但不能作为指令来执行；“R”表示该页只能读，不能写和执行；“X”表示该页只能作为指令来执行，不能读和写。2014.2.1750计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第50页!7.1.3“主─辅”层次与“Cache─主存”层次的对比（P192表7.1，P231表7.7）“主存-辅存”层次目的：提高等效容量。基本调度单位：页，几百Byte到几千Byte。速度比：几万倍。虚实转换：页表（以虚页号为索引）“Cache-主存”层次目的：提高等效速度。基本调度单位：块，几十Byte。速度比：几倍。虚实转换：目录表（以实页号为索引）2014.2.1751计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第51页!7.1.2存储层次的性能指标（P189）先以2级存储层次为例进行公式推导，并且只考虑各级存储器件自身的操作，忽略控制机构的附加开销。多级层次以及附加开销留到以后讨论。(1)容量：S=S2（理论上）(2)单价：（美分/bit）2014.2.1752计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第52页!访问效率e（补充）访问效率e受H和r的影响（参见右图）：

e是一个相对值，便于不同系统之间的比较。2014.2.1753计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第53页!课堂练习7.2设计“Cache-主存”层次，Cache的容量有三种选择，如上表所示。忽略平均访存时间TA公式中的TB。(1)分别计算三种方案的等效访问时间；(2)分别计算三种方案每KB的平均价格；(3)分别根据等效访问时间、每KB的平均价格排序；(4)根据等效访问时间和平均价格的乘积排序。2014.2.1754计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第54页!多级存储层次的平均访问时间2由这2式合并得此公式参见教材P214倒数第12行。2014.2.1755计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第55页!(1)问中，为什么？答：每当CPU访问M1不命中时，存储系统会从M3装入1000字节到M1，再从M1取1个字节送给CPU，所以本次访问结果为“失效”，但是紧接着的999次访问将“命中”，以后又是如此重复，……。同学们不要把访问“失效”理解为访问“失败”，认为CPU在M1找不到数据就会放弃本次访问。“失效”的定义是经过等待后完成的访问，而“命中”是不需要等待即完成的访问，仅此不同。(3)问中，为什么？答：M2接受M1的数据请求，每次是1000字节。M2的初始状态为“空”，对于M1的首次请求不能立即满足，需要先从M3索取1000000字节数据填满自己，再向M1提供所要的1000字节数据。这次访问称为“失效”。此后M1向M2发出的999次请求都能立即响应，而再下一次请求又需要等待…。如此重复，所以H2=999/1000。例题说明：2014.2.1756计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第56页!因为：所以：依此类推，……7.4.1局部不命中率与全局不命中率（续）2014.2.1757计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第57页!例7.3考虑某一两级Cache：级Cache为L1，第二级Cache为L2。(1)假设在1000次访存中，Cache1的不命中是40次，Cache2的不命中是20次。求各种局部不命中率和全局不命中率；(2)假设Cache1的命中时间是1个时钟周期，Cache2的命中时间是10个时钟周期，不命中开销是100时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问：平均访存时间是多少？每条指令的平均停顿时间（即失效开销）是多少个时钟周期？解：(1)级Cache的不命中率（全局和局部）是40/1000，即4%；第二级Cache的局部不命中率是20/40，即50%；第二级Cache的全局不命中率是20/1000，即2%。例7.32014.2.1758计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第58页!各次作业应交的内容作业8（第9次课）7.92014.2.1759计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第59页!7.2.2四种常见的地址映象方式（P193）(1)全相联(fullyassociative)全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。这种关系可用下页示意图(a)、(b)表示。全相联的虚实变换信息完全来自于变换表，查表过程如图(c)所示。全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入/调出的操作开销也最少，有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。由于页表必须常驻在实存中，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）容量大得多，所以全相联映象方式一般用于主存-辅存层次。一个虚页被允许进入的实页集合称为“候选位置”（P195），全相联的“候选位置”为整个实存。2014.2.1760计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第60页!全相联的地址映象方式与地址变换原理示意图(c)2014.2.1761计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第61页!直接相联的地址映象方式与地址变换原理2014.2.1762计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第62页!组相联的地址映象方式与地址变换原理(a)(b)组相联的“候选位置”为组内页数，即“路数”。2014.2.1763计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第63页!(4)位选择组相联(P194图7.7c)位选择组相联映象方式映象关系中，实存分组，虚存按实组数分区，区内不分组。虚块号与实组号之间是直接映象关系，而虚块与该实组内的各个实块之间是全相联映象方式。例如，虚块0可以映象到实组0的任意一块中。在一般组相联映象方式中，一个虚组与一个实组之间是多个块到多个块的映象。而在位选择组相联映象方式中，改成了一个虚块到实组中多个块的映象。映象关系明显简单，实现起来可以容易些。另外，从数据的分布情况看。对于一般组相联映象方式，虚存中的几个连续块映象到实存中可能也是连续的，而对于位选择组相联映象方式，虚存中的连续块映象到实存中肯定是不连续的，它们被分散到实存的各个组中。由于在虚存与实存之间是以块为单位进行调度的，而实存是以字为单位访问的，只要实存中的一个字不跨越两个块，在实存内部的块与块之间的分布是否连续对实存的正常工作是没有关系的。由于虚存每个区中的块数与实组数相等，而且它们之间采用直接映象方式，因此，虚存地址中的区内块号可以直接作为实组号。位选择组相联的地址变换过程比一般组相联映象方式简单，而与全相联映象方式基本相同。2014.2.1764计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第64页!位选择组相联的地址映象方式与地址变换原理(c)2014.2.1765计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第65页!(2)部分虚实表法（P195图7.8）

这是一种统称，指表项数少于虚页数的情形，下面要介绍的3种方法都属于这一类。（与Hash查表有点相似）

表项数少于虚页数意味着查表时会有多个虚页查到表中同一项的情况发生，另外也意味着区分表中项号的地址位数少于虚页号的位数，虚页号中未用的位数正是造成重复的原因。

表项数少于虚页数的做法既是节省成本的需要，也符合任何时刻只有少部分虚页占用实存的实际，问题是每个表项必须说明它当前记录的是一组共享虚页中的哪一个的信息，这就要用到“标识”字段。虚页号里用于计算表内地址的部分称为“索引”index，用来与查表内容相比较的部分称为“标识”tag。下图以组相联为例说明“标识”的意义，它有16个虚页，只用4个表项。7.2.3虚实变换基本方法（续1）2014.2.1766计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第66页!(4)目录表法（P196第1段）

只对已经装入实存的虚页造表，其项数比页表少得多。为避免逐行比对，须使用相联存储器来存放，通过并行比较实现一次查遍，器件价格远高于普通存储器。7.2.3虚实变换基本方法（续3）2014.2.1767计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第67页!主─辅层次虚实变换实现主流方案：全相联，页表法（P232）2014.2.1768计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第68页!Cache─主存层次虚实变换实现（组相联）低失效方案：位选择组相联（2路），目录表法（P196，图7.9）2014.2.1769计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第69页!(3)基本思想及工作原理

在逻辑上把直接相联Cache的空间分为上、下两个区。对于任何一次访问，伪相联Cache先按直接相联Cache的方式去处理。若命中，则其访问过程与直接相联Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中。再找不到就只好访问下一级存储器。

显然伪相联的“候选位置”=2，与2路组相联相同。

每次访问时间有3种可能：正常命中（快速命中）伪命中（慢速命中）不命中7.3.5伪相联（续1）2014.2.1770计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第70页!7.3.5伪相联（续3）折中方案：伪相联（2路），目录表法（P209）2014.2.1771计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第71页!解：(1)首先按通用形式写出伪相联的平均访存时间公式：平均访存时间伪相联＝平均命中时间伪相联＋不命中率伪相联×不命中开销伪相联

然后根据伪相联原理，可以写出其中的：

平均命中时间伪相联＝命中时间1路＋伪命中率伪相联×2周期

由于伪相联不命中时，就是2个候选位置都不命中，所以：

不命中率伪相联＝不命中率2路

又由于伪相联的2个候选位置命中率之和等于2路组相联，所以：

伪命中率伪相联＝命中率2路－命中率1路

＝(1－不命中率2路)－(1－不命中率1路)

＝不命中率1路－不命中率2路7.3.5伪相联（续5）2014.2.1772计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第72页!结论：从不命中率看，F2路=F伪相联<F1路，伪相联因不命中带来的平均延时与2路一样短（1路较长）；从命中时间看，伪相联在正常命中时与1路一样短（2路较长），伪命中时要增加2拍，后者概率=H2路–H1路。这种情况下1路要增加50拍。代入2KB、128KB容量的数据，算出平均访存时间TA都是伪相联最短。缺点：多种命中时间习题：7.117.3.5伪相联（续7）2014.2.1773计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第73页!衡量访存时间是否合适的主要标准是处理机速度，具体说是处理机分配来读/写存储器的时间长短。处理机速度越高要求访存时间越短。衡量处理机速度的常用标准是CPI，因为它与程序执行时间成正比。

对顺序执行的处理机，CPI定义为每条指令执行所需的平均周期数。对流水执行的处理机，CPI定义为相邻两条指令启动时间相差的平均周期数。我们现在只关心流水处理机。

下图说明访存等待（不命中）会延长瞬时CPI。7.2.7访存时间对CPU性能的影响1（P203）IFIDEXMemWBstallIFIDEXMemWBIFIDEXMemWBIFIDEXMemWBIFIDEXMemWBCPI=1CPI=22014.2.1774计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第74页!(1)第i级的不命中率：特殊地，F1又可以记为F，因为M1被访问次数就是CPU的总访存次数。(2)存储系统的平均访问时间（从CPU看）：其中H1～Hn是来自互斥事件的完备群，它们满足关系式：注意该公式忽略了各级之间的传送时间。(3)第i级的平均访问时间：其中Ti是第i级的命中时间，TMi是第i级的失效开销时间。7.2.7访存时间对CPU性能的影响32014.2.1775计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第75页!例7.1（P204）

假设Cache不命中开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache不命中率为2%，平均每条指令访存1.33次。比较有Cache与无Cache情况下的CPU时间。解：已知TA1=2.0，即理想CPI=2.0，TA2=50，F=2%，平均每条指令访存1.33次CPU时间有cache＝IC×（CPIexecution＋每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间＝IC×（2.0＋1.33×2%×50）×时钟周期时间＝IC×3.33×时钟周期时间从此式知，实际CPI＝2.0＋1.33×2%×50＝3.33，是理想情况下的3.33/2.0＝1.67(倍)，换言之，CPU时间是理想情况下的1.67倍。

若不采用Cache，则每次访存增加50个时钟周期，每条指令的周期数为：CPI无cache＝2.0＋1.33×50＝68.5，是理想情况下的68.5/2.0＝34.25倍！2014.2.1776计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第76页!例7.2（续1）解：摘要：理想CPI=2，不命中开销=70ns，每条指令访存1.3次，F直接=1.4%，F组=1.0%，Cycle直接=2ns，Cycle组=2.2ns。比较直接映象Cache（即1路）与2路组相联Cache的平均访存时间、CPU时间。(1)平均访存时间为：平均访存时间＝命中时间＋不命中率×不命中开销因此，两种结构的平均访存时间分别是：

平均访存时间1路＝2.0＋（0.014×70）＝2.98ns

平均访存时间2路＝2.0×1.10＋（0.010×70）＝2.90ns

两路组相联Cache的平均访存时间短一些。2014.2.1777计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第77页!

欲设计一个L2-Cache，已知它的不命中开销L2＝50个时钟周期，问下列两种映像方式对不命中开销有何影响。

(1)L2-Cache采用直接相联，局部不命中率L2＝25%，命中时间L2＝10个时钟周期；

(2)L2-Cache采用两路组相联，局部不命中率L2＝20%，命中时间L2＝10.1个时钟周期。解：（此例与P204的例7.2参数相似，注意区别）

题目已经给出了L2-Cache恒定的“不命中开销L2”，那么它的不同映像方式影响的只能是L1-Cache的不命中开销，根据多级存储层次原理，TM1＝M2的平均访问时间。所以本题实质上是问哪种映像方式下L2-Cache的平均访问时间较小。

另外，在不使用L3-Cache情况下，“不命中开销L2＝50个时钟周期”意思是“主存平均访问时间＝50个时钟周期”。例7.4（P216）2014.2.1778计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第78页!各次作业应交的内容作业10（第11次课）7.102014.2.1779计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第79页!页表———一个页表的大小为4K字节，放在一个物理页中。由1024个4字节的页表项组成。页表项的大小为4个字节(32bit)，所以一个页表中有1024个页表项。页表中的每一项的内容（每项4个字节,32bit）高20bit用来放一个物理页的物理地址，低12bit放着一些标志。页目录———一个页目录大小为4K字节，放在一个物理页中。由1024个4字节的页目录项组成。页目录项的大小为4个字节(32bit)，所以一个页目录中有1024个页目录项。页目录中的每一项的内容（每项4个字节）高20bit用来放一个页表（页表放在一个物理页中）的物理地址，低12bit放着一些标志。对于x86系统，页目录的物理地址放在CPU的CR3寄存器中。如果CPU寄存器中的分页标志位被设置，那么执行内存操作的机器指令时，CPU会自动根据页目录和页表中的信息，把虚拟地址转换成物理地址，完成该指令。比如moveax,004227b8h，这是把地址004227b8h处的值赋给寄存器的汇编代码，004227b8这个地址就是虚拟址。CPU在执行这行代码时，发现寄存器中的分页标志位已经被设定，就自动完成虚拟地址到Windows2000虚拟存储器22014.2.1780计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第80页!偏移，加上这个物理页的物理地址，就得到了该虚拟地址所对应的物理地址。一个页目录有1024项，虚拟地址最高的10bit刚好可以索引1024项（2的10次方等于1024）。一个页表也有1024项，虚拟地址中间部分的10bit，刚好索引1024项。虚拟地址最低的12bit（2的12次方等于4096），作为页内偏移，刚好可以索引4KB，也就是一个物理页中的每个字节。一个虚拟地址转换成物理地址的计算过程就是，处理器通过CR3找到当前页目录所在物理页，取虚拟地址的高10bit,然后把这10bit右移2bit（因为每个页目录项4个字节长，右移2bit相当于乘4）得到在该页中的地址，取出该地址处PDE（4个字节），就找到了该虚拟地址对应页表所在物理页，取虚拟地址第12位到第21位这10位，然后把这10bit右移2bit（因为每个页表项4个字节长，右移2bit相当于乘4）得到在该页中的地址，取出该地址处的PTE（4个字节），就找到了该虚拟地址对应物理页的地址，最后加上12bit的页内偏移得到了物理地址。Windows2000虚拟存储器42014.2.1781计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第81页!Windows2000虚实变换示意图2014.2.1782计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第82页!几种常用的替换算法(1)随机算法RAND──在比较范围内任取一页作为淘汰页；(2)先进先出算法FIFO──在比较范围内选取调入最早的一页作为淘汰页；(3)最不经常使用算法LFU──在比较范围内选取最近一个单位时间内使用次数最少的一页作为淘汰页；(4)最不接近使用算法LRU──在比较范围内选取最后一次使用离现在最久的一页作为淘汰页。2014.2.1783计算机系统结构计算机系统结构》电子教案共94页，您现在浏览的是第83页!算法模拟：实存状况图(清华教材图3.32)以下是FIFO、L