第4章存储层次

第4章存储层次4.1存储器的层次结构4.2Cache基本知识4.3降低Cache失效率的方法4.4减少Cache失效开销4.5减少命中时间4.6主存4.7虚拟存储器4.8进程保护4.9IntelCorei7中的存储器层次结构计算机系统结构第4章存储层次4.1存储器的层次结构4.1.1从单级存储器到多级存储器1.从用户的角度来看，存储器的三个主要指标是：

容量，速度，价格(每位价格)2.人们对这三个指标的期望: 容量大，速度快，价格低3.这三个指标相互矛盾 如：速度越高，价格越高；容量越大，价格越低；容量越大，速度越慢。4.解决方法采用多种存储器技术，构成存储层次。4.1存储器的层次结构M1-Mn：用不同技术实现的存储器它们之间以块或页面为单位传送数据，M1离CPU最近，容量最小，每位价格最高。Mn离CPU最远，容量最大，每位价格最低。考虑相邻的两级，靠近CPU的一级总是容量小一些，速度快一些，价格高一些。4.1存储器的层次结构整个系统的目标：从CPU看去，这个存储器系统的速度接近于M1的，而容量和价格则接近于Mn。须做到：存储器越靠近CPU，CPU对它的访问频率越高。大多数访问都能在M1完成（根据局部性原理）。任何一级存储器中的内容一般都是其下一层存储器中内容的子集。当CPU访存时，首先是访问M1，若找到数据，则访问结束。若没有找到，就需要访问M2，将包含所需数据的块（或页面）调入M1。若M2中还没有找到，就需访问M3，以此类推。小容量存储器：速度高，价格也高。大容量存储器：速度低，价格也低。高性能要求存储器速度高，实际应用要求存储器容量大，互相矛盾。怎么办？现代计算机一般采用存储层次。4.1存储器的层次结构顶层包含最常用的信息。任何一层中包含的信息，都是其下一层中信息的一个副本。CPU访问存储器时，若在Cache中没找到所要的信息，就从下一层中调入。4.1存储器的层次结构4.1.2存储层次的性能参数每位价格C，命中率H，平均访问时间TA假设：S──容量TA──访问时间C──每位价格下面仅考虑由M1和M2构成的两级存储层次：

M1的参数：S1，TA1，C1 M2的参数：S2，TA2，C21.

每位价格C

C＝C1S1＋C2S2S1＋S2显然，当S1<<S2时，C≈C24.1存储器的层次结构2.命中率H和失效率F 命中率为CPU访问存储系统时，在M1中找到所需信息的概率。

命中率一般用模拟的方法来确定，也就是通过模拟一组有代表性的程序，分别记录下访问M1和M2的次数N1和N2，则

H＝N1/(N1＋N2)

N1──访问M1的次数 N2──访问M2的次数

失效率F＝1－H4.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＋FTM

4.1存储器的层次结构4.1.3“Cache－主存”和“主存－辅存”层次从主存的角度来看

“Cache－主存”层次：弥补主存速度的不足

“主存－辅存”层次：弥补主存容量的不足1.“Cache－主存”层次

主存与CPU的速度差距4.1存储器的层次结构4.1存储器的层次结构4.1存储器的层次结构3.“主存－辅存”层次4.1存储器的层次结构存储层次CPU对第二级的

访问方式比较项目目的存储管理实现

访问速度的比值

(第一级和第二级)典型的块(页)大小失效时CPU是否切换“Cache－主存”层次“主存－辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现主要由软件实现几比一几百比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其他进程“Cache－主存”与“主存－辅存”层次的区别4.1存储器的层次结构4.1.4存储层次的四个问题当把一个块调入高一层(靠近CPU)存储器时，

可以放在哪些位置上?

(映象规则)当所要访问的块在高一层存储器中时，如何

找到该块?

(查找算法)3.当发生失效时，应替换哪一块？

(替换算法)4.当进行写访问时，应进行哪些操作?

(写策略)1.2.第4章存储层次4.2Cache基本知识Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。相应地，CPU的访存地址被分割成两部分：块地址和块内位移。主存地址：块地址块内位移主存块地址用于查找该块在Cache中的位置，块内位移用于确定所访问的数据在该块中的位置。4.2Cache基本知识5.2.1映象规则映象规则主要有全相联映象，直接映象和组相联映象三种。1.全相联映象全相联：主存中的任一块可以被放置到Cache中的任意一个位置。特点：空间利用率最高，冲突概率最低，实现最复杂。4.2Cache基本知识4.2Cache基本知识2.直接映象直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。(循环分配)◆特点：空间利用率最低，冲突概率最高，实现最简单。◆对于主存的第i块，若它映象到Cache的第j块，则:

j＝imod(M)（M为Cache的块数）

4.2Cache基本知识4.2Cache基本知识◆

组相联：主存中的每一块可以被放置到Cache

中唯一的一个组中的任何一个位置。（Cache等分为若干组，每组由若干个块构成）◆组相联是直接映象和全相联的一种折中。◆设M＝2m，则当表示为二进制数时，j实际

上就是i的低m位：3.组相联映象m位j主存块地址i：4.2Cache基本知识4.2Cache基本知识◆上述的m和k通常称为索引◆组的选择常采用位选择算法若主存第i块映象到第k组，则:

k＝imod（G）（G为Cache的组数）设G＝2g，则当表示为二进制数时，k实

际上就是i的低g位：g位k主存块地址i：4.2Cache基本知识◆绝大多数计算机的Cache:n≤4

想一想：相联度一定是越大越好？◆n路组相联：每组中有n个块(n＝M/G)

n称为相联度。

相联度越高，Cache空间的利用率就越高，

块冲突概率就越低，失效率也就越低。全相联直接映象组相联n(路数)G(组数)MM111＜n＜M1＜G＜M4.2Cache基本知识块冲突是指一个主存块要进入已被占用的Cache块位置。显然，全相联的失效率最低，直接映象的失效率最高。虽然从降低失效率的角度来看，n的值越大越好，但在后面我们将看到，增大n值并不一定能使整个计算机系统的性能提高，而且还会使Cache的实现复杂度和代价增大。因此，绝大多数计算机都采用直接映象、两路组相联或4路组相联。特别是直接映象，采用得最多。4.2Cache基本知识4.2.2查找方法1.如何确定Cache中是否有所要访问的块？若有的话如何确定其位置？

设置查找目录表。目录表共有M项，每一项对应于Cache中的一个块，用于指出当前该块中存放的信息是哪一个主存块的（可能有多个主存块映象到该Cache块）。它实际上是记录了该主存块的块地址的高位部分，称为标识（tag）。每个主存块能唯一的由其标识来确定。4.2Cache基本知识为了指出Cache中的块是否包含有效信息，一般是在目录表中给每一项设置一个有效位。例如，当该位为“1”时表示该目录表项有效，Cache中相应块所包含的信息有效。当一个主存块被调入Cache中某一个块位置时，它的标识就被填入到目录表中与该Cache块相对应的项中，并且该项的有效位被置“1”。4.2Cache基本知识根据映象规则不同，一个主存块可能映象到Cache中的一个或多个Cache块位置。为便于讨论，我们把它们称为候选位置。当CPU访问该主存块时，必须且只需查找它的候选位置所对应的目录表项（标识）。如果有与所访问的主存块相同的标识，且其有效位为“1”，则它所对应的Cache块即是所要找的块。4.2Cache基本知识直接映象Cache的候选位置最少，只有一个；全相联Cache的候选位置最多，为M个；而n路组相联则介于两者之间，为n个。4.2Cache基本知识◆并行查找与顺序查找4.2Cache基本知识◆顺序查找提高性能的方法：主候选位置(MRU块)

前瞻执行4.2Cache基本知识◆并行查找的实现方法：举例：４路组相联并行标识比较（比较器的个数及位数）

相联存储器单体多字存储器＋比较器4.2Cache基本知识主存块地址：目录表（标识存储器）4.2Cache基本知识4.2Cache基本知识4.2Cache基本知识4.2.3替换算法

所要解决的问题：当要从主存调入一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全被占用的情况。这时需强迫腾出其中的某一块，以接纳新调入的块。那么应该替换哪一块？1.随机法

为了均匀使用一组中的各块，随机地选择被替换的块。有些系统采用伪随机数法产生块号。

特点：实现简单，但反映不了程序的局部性。2.先进先出法（FIFO）

选择最早调入的块作为被替换的块。

特点：容易实现。还是不能正确地反映程序的局部性。4.2Cache基本知识3.最近最少使用法（LRU）

选择近期最少被访问的块作为被替换的块。实际应用中通常是选择最久没有被访问过的块作为被替换的块。

特点：失效率低。能较好地反映程序的局部性原理。但LRU比较复杂，硬件实现比较困难，特别是当组的大小增加时，LRU的实现代价会越来越高，而且经常只能是近似的实现。4.2Cache基本知识表中的数据是对于一个VAX地址流（既包括用户程序也包括操作系统程序）在块大小为16B的情况下统计的。在这个例子中，对于大容量Cache，LRU和随机法的失效率几乎没什么差别。4.2Cache基本知识4.2.4写策略处理器对Cache的访问主要是读访问，因此设计Cache要针对最经常发生的“读”进行优化。幸运的是，最经常发生的“读”也是最容易提高速度的。访问Cache时，在读出标识进行比较的同时，可以把相应的Cache块也读出。如果命中，则把该块中请求的数据立即送给CPU；若为失效，则所读出的块没什么用处，但也没什么坏处，置之不理就是了。4.2Cache基本知识“写”在所有访存操作中所占的比例统计结果表明，对于一组给定的程序：load指令：26％store指令：9％“写”在所有访存操作中所占的比例：

9％/(100％＋26％＋9％)≈7％“写”在访问数据Cache操作中所占的比例：

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

◆写直达法执行“写”操作时，不仅写入Cache，而且

也写入下一级存储器。

◆写回法执行“写”操作时，只写入Cache。仅当

Cache中相应的块被替换时，才写回主存。

(设置“污染位”)4.2Cache基本知识两种写策略的比较

◆写直达法的优点：易于实现，一致性好。

◆写回法的优点：速度快，而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache不到达主存，因而所使用的存储器频带较低；4.2Cache基本知识写缓冲器：采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写等待。减少写等待的一种常用优化技术是采用写缓冲器，从而使下一级存储器的更新和CPU的执行重叠起来。4.2Cache基本知识写策略与调块

写直达法──不按写分配

写回法──按写分配“写”操作时的调块：由于“写”访问并不需要用到所访问单元中原有的数据。所以，当发生写失效时，是否调入相应的块，有两种选择：◆按写分配(写时取)

写失效时，先把所写单元所在的块调入

Cache，再行写入。◆不按写分配(绕写法)

写失效时，直接写入下一级存储器而不调块。4.2Cache基本知识4.2.5Cache的结构例子：DEC的AlphaAXP21064中的内部数据Cache1.简介

容量：8KB

块大小：32B

块数：256

映象方法：直接映象

“写”策略：写直达采用不按写分配写缓冲器大小：4个块4.2Cache基本知识2.结构图4.2Cache基本知识3.工作过程

◆

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

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

混合Cache：指令和数据混合Cache。 若流水线中同时请求一个数据字和一个指令字，会出现冲突，导致CPU等待。

分离Cache：分为指令Cache和数据Cache两个Cache。 AlphaAXP21064有一个8KB的指令Cache，其结构与8KB的数据Cache几乎一样。 CPU知道它发出的地址是指令地址还是数据地址，因此可以为它们设置不同的端口，这样就会加倍对存储系统和CPU之间数据通道带宽的要求。由于系统对指令和数据的操作特性不同，独立的指令Cache和数据Cache使我们能分别对它们进行优化，它们各自采用不同的容量、块大小和相联度时的性能可能会更好。4.2Cache基本知识16KB容量1KB2KB4KB8KB32KB指令Cache3.06%失效率的比较64KB128KB数据Cache混合Cache2.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.2Cache基本知识分离Cache平均失效率的计算：访问指令Cache的百分比×指令Cache的失效率＋访问数据Cache的百分比×数据Cache的失效率4.2.6Cache性能分析失效率与硬件速度无关，用它来评价存储系统的性能非常方便,所以经常会用到它。容易产生一些误导：一种更好的评测存储系统性能的指标是平均访存时间。平均访存时间平均访存时间＝命中时间＋失效率×失效开销4.2Cache基本知识例5.1

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

如前所述，约75%的访存为取指令。因此，分离Cache的总体失效率为：(75%×0.64%)＋(25%×6.47%)＝2.10%根据前表，容量为32KB的混合Cache的失效率略低一些，只有1.99%.100%/（100%+26%+9%）=75%LoadStore4.2Cache基本知识平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间＝指令所占的百分比×(指令命中时间＋指令失效率×失效开销＋数据所占的百分比×(数据命中时间＋数据失效率×失效开销)所以，两种结构的平均访存时间分别为：平均访存时间分离

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

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

×时钟周期时间存储器停顿周期数指令数4.2Cache基本知识考虑Cache的失效后，性能为：

CPU时间有cache＝IC×（2.0＋1.33×2%×50）×时钟周期时间＝IC×3.33×时钟周期时间实际CPI：3.33

3.33/2.0=1.67(倍)

CPU时间也增加为原来的1.67倍。但若不采用Cache,则：

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

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

解

平均访存时间为：平均访存时间＝命中时间＋失效率×失效开销因此，两种结构的平均访存时间分别是：

平均访存时间1路＝2＋（0.014×70）＝2.98ns平均访存时间2路＝2×1.10＋（0.010×70）＝2.90ns2路组相联Cache的平均访存时间比较低。

CPU时间＝IC×(CPIexe＋每条指令的平均存储器

停顿周期数)×时钟周期时间

＝IC×(CPIexe×时钟周期时间＋

每条指令的平均存储器停顿时间)4.2Cache基本知识因此：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×IC5.31×ICCPU时间1路─────＝─────＝1.015.27×ICCPU时间2路和平均访存时间的比较结果相反，直接映象Cache的平均性能好一些，这是因为在两路组相联的情况下，虽然失效次数减少了，但所有指令的时钟周期时间都增加了10%。由于CPU时间是我们进行评价的基准，而且直接映象Cache实现更简单，所以本例中直接映象Cache是较好的选择。4.2Cache基本知识4.2.7改进Cache的性能平均访存时间＝命中时间＋失效率×失效开销可以从三个方面改进Cache的性能：降低失效率减少失效开销减少Cache命中时间下面介绍17种Cache优化技术8种用于降低失效率5种用于减少失效开销4种用于减少命中时间4.2Cache基本知识写缓冲合并第4章存储层次4.3降低Cache失效率的方法三种失效(3C)强制性失效(Compulsorymiss)当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。

(冷启动失效，首次访问失效)容量失效(Capacitymiss)如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。4.3降低Cache失效率的方法冲突失效(Conflictmiss)在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。(碰撞失效，干扰失效)三种失效所占的比例图示I(绝对值)图示Ⅱ(相对值)4.3降低Cache失效率的方法4.3降低Cache失效率的方法4.3降低Cache失效率的方法可以看出：相联度越高，冲突失效就越少；强制性失效和容量失效不受相联度的影响；强制性失效不受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中块的数目，所以有可能会增加冲突失效。

Cache容量越大，使失效率达到最低的块大小就越大。4.3降低Cache失效率的方法4.3降低Cache失效率的方法各种块大小情况下Cache的失效率

4.3降低Cache失效率的方法增加块大小会增加失效开销

例5.4假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节。即，经过42个时钟周期，它可提供16个字节；经过44个时钟周期，可提供32个字节；依此类推。请问对于上表中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？解：平均访存时间=命中时间+失效率×失效开销

假设命中时间与块大小无关，为1个时钟周期，那么对于一个块大小为16B、容量为1KB的cache来说，平均访存时间=1+（15.05%×42)=7.321

对于一个块大小为256B、容量为256KB的cache来说，平均访存时间=1+（0.49%×72)=1.3534.3降低Cache失效率的方法各种块大小情况下Cache的平均访存时间

4.3降低Cache失效率的方法Cache设计者一直在努力同时减少失效率和失效开销。从失效开销的角度来讲，块大小的选择取决于下一级存储器的延迟和带宽两个方面。高延迟和高带宽时，宜采用较大的Cache块，因为这时每次失效时，稍微增加一点失效开销，就可以获得许多数据。与之相反，低延迟和低带宽时，宜采用较小的Cache块，因为采用大Cache块所能节省的时间不多。4.3降低Cache失效率的方法4.3.3提高相联度采用相联度超过8的方案的实际意义不大。2:1Cache经验规则容量为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把相应的失效率代入上式，即可得平均访存时间。例如，1KB的直接映象Cache的平均访存时间为：平均访存时间1路=1.00＋0.133×50＝7.65

128KB的8路组相联Cache的平均访存时间为：

平均访存时间8路＝1.14＋0.006×50＝1.444.3降低Cache失效率的方法在各种容量和相联度情况下Cache的平均访存时间4.3降低Cache失效率的方法当Cache容量不超过16KB时，上述三个不等式成立。从32KB开始，对于平均访存时间有：4路组相联的平均访存时间小于2路组相联的;2路组相联的小于直接映象的;但8路组相联的却比4路组相联的大。4.3降低Cache失效率的方法4.3.4VictimCache一种能减少冲突失效次数而又不影响时钟频率的方法。基本思想在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。4.3降低Cache失效率的方法每当发生失效时，在访问下一级存储器之前，先检查VictimCache中是否含有所需的块。如果有，就将该块与Cache中某个块做交换。VictimCache在存储层次中的位置

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

KB

Cache的冲突失效减少20%～90%874.3降低Cache失效率的方法4.3.5伪相联Cache多路组相联的低失效率和直接映象的命中速度优点缺点直接映象组相联命中时间小命中时间大失效率高失效率低伪相联Cache的优点命中时间小失效率低4.3降低Cache失效率的方法基本思想及工作原理在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。快速命中与慢速命中要保证绝大多数命中都是快速命中。4.3降低Cache失效率的方法4.3降低Cache失效率的方法例5.6假设当在按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。仍用上个例子中的数据，问：当Cache容量分别为2KB和128KB时，直接映象、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失效率的方法将前面表中的数据代入上面的公式，得：

平均访存时间伪相联，2KB

＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844平均访存时间伪相联，128KB

＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356根据上一个例子中的表，对于2KBCache，可得：

平均访存时间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硬件预取指令和数据都可以预取预取内容既可放入Cache，也可放在速度比主存快的外缓冲器中。例如：指令流缓冲器指令预取通常由Cache之外的硬件完成4.3降低Cache失效率的方法以AlphaAXP21064为例，在发生指令失效时取两个块：被请求指令块和顺序的下一指令块。被请求指令块返回时放入Cache，而预取指令块则放在缓冲器中；如果某次被请求的指令块正好在缓冲器里，则取消对该块的访存请求，直接从缓冲器中读出这一块，同时发出对下一指令块的预取方寸请求。Joppi的研究结果指令预取(4KB，直接映象Cache，块大小＝16B)1个块的指令流缓冲器：捕获15％～25％的失效4个块的指令流缓冲器：捕获50％16个块的指令流缓冲器：捕获72％4.3降低Cache失效率的方法数据预取(4KB,直接映象Cache)1个数据流缓冲器：捕获25％的失效还可以采用多个数据流缓冲器，分别从不同的地址预取数据。Jouppi发现，用4个数据流缓冲器可以将命中率提高到43%Palacharla和Kessler的研究结果流缓冲器：既能预取指令又能预取数据对于两个64KB四路组相联Cache来说：8个流缓冲器能捕获50％～70％的失效4.3降低Cache失效率的方法例5.7AlphaAXP21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，AlphaAXP21064的指令Cache必须为多大才能保持平均访存时间不变？

解

假设当指令不在指令Cache里，而在预取缓冲器中找到时，需要多花一个时钟周期。下面是修改后的公式：平均访存时间预取＝命中时间＋失效率×预取命中率×1＋失效率×（1－预取命中率）×失效开销4.3降低Cache失效率的方法假设预取命中率为25%，命中时间为2个时钟周期，失效开销为50个时钟周期。查表可知8KB指令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编译器控制的预取在编译时加入预取指令，在数据被用到之前发出预取请求。预取有以下几种类型：寄存器预取：把数据取到寄存器中。Cache预取：只将数据取到Cache中。这两种预取可以是故障性的,也可是非故障性的。故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。4.3降低Cache失效率的方法本节假定Cache预取都是非故障性的，也称非绑定预取。在预取数据的同时，处理器应能继续执行。只有这样，预取才有意义。非阻塞Cache(非锁定Cache)：要求cache在等待预取数据返回的同时,还能继续提供指令和数据。

编译器控制预取的目的使执行指令和读取数据能重叠执行。循环是预取优化的主要对象，因为它易于进行预取优化。失效开销小时：循环体展开1～2次，并调度好预取和执行的重叠失效开销大时：循环体展开许多次4.3降低Cache失效率的方法

例5.8对于下面的程序，首先判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：(1)我们用的是一个容量为8KB、块大小为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失效率的方法解修改前：双重循环一共执行了3×100次循环，每次用7个时钟周期，循环时间＝300×7＝2100失效开销＝251×50＝125502100＋12550＝14650修改后：循环时间＝100×9＋200×8＝2500失效时间＝19×50＝9502500＋950＝3450

加速比＝14650/3450＝4.24.3降低Cache失效率的方法4.3.8编译器变化基本思想在编译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。McFaring发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。2KBCache:降低50％8KBCache：降低75%数据对存储位置的限制比指令的少，因此更便于优化。通过把数据重新组织，使得一块数据在被从Cache替换出去之前，能最大限度利用其中的数据(访问次数最多)。4.3降低Cache失效率的方法数组合并这种技术通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干数组的同一维。这些访问可能会相互干扰，导致冲突失效。可以通过组成复合数组，使得一个Cache块中能包含全部所需的元素。举例：

/*修改前*/

int

val[SIZE];

intkey[SIZE];/*修改后*/structmerge{intval;intkey;};structmergemerged_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];/*修改后*/for（i=0;i<5000;i=i+1）

for（j=0;j<100;j=j+1）

x[i][j]=2*x[i][j];4.3降低Cache失效率的方法循环融合

将多个独立的循环融合为单一的循环，能使读入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];for（i=0;i<N;i=i+1）

for（j=0;j<N;j=j+1）

d[i][j]=a[i][j]+c[i][j];/*修改后*/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];}4.3降低Cache失效率的方法分块这种优化可能是cache优化技术中最著名的一种,它也是通过改进时间局部性来减少失效。分块算法不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。把对数组的整行或整列访问改为按块进行。

/*矩阵乘法运算，修改前*/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失效开销随着技术的发展，处理器速度的提高要快于DRAM速度的提高，这使得Cache失效开销的相对代价随时间不断增加。让读失效优先于写写缓冲合并请求字处理技术非阻塞Cache技术采用两级Cache4.4减少Cache失效开销4.4.1让读失效优先于写提高写直达Cache性能最重要的方法是使用一个大小适中的写缓冲器。然而，写缓冲器却导致对存储器的访问复杂化了，因为在读失效时，写缓冲器中可能保存所读单元的最新值。例5.10

考虑以下指令序列：

SWR3,512（R0）；M[512]←R3（Cache索引为0）

LWR1,1024（R0）；R1←M[1024]（Cache索引为0）

LWR2,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失效开销解决问题的方法(读失效的处理)推迟对读失效的处理，直到写缓冲器清空。（缺点：读失效的开销增加，如50％）在读失效时检查写缓冲器中的内容，如果没有冲突而且存储器可访问就可继续处理读失效。在写回法Cache中，也可采用写缓冲器。假定读失效将替换一个“脏”的存储块，我们可以不像往常那样先把“脏”块写回存储器，然后在读存储器，而是先把被替换的“脏”块拷入一个缓冲器，然后读存储器，最后再写存储器。这样CPU的读访问就能更快地完成。和上面的情况类似，发生读失效时，处理器既可以采用等待缓冲区清空的方法，也可以采用检查缓冲区中各字的地址是否有冲突的方法。4.4减少Cache失效开销4.4.2写缓冲合并该项技术是提高写缓冲器的效率写直达Cache是依靠写缓冲来提高完成对下一级存储器的写操作的时间。如果写缓冲器为空，就把数据和相应地址写入该缓冲器。从CPU的角度来看，该写操作就算完成了。4.4减少Cache失效开销如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。如果写缓冲器满且又没有能进行写合并的项，就必须等待。

提高了写缓冲器的空间利用率，而且还能减少因写缓冲器满而要进行的等待时间。4.4减少Cache失效开销4.4减少Cache失效开销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只是稍大一点，局部失效率将很高。如512KB，1024KB相联度第二级Cache可采用较高的相联度或伪相联方法。4.4减少Cache失效开销例5.13给出有关第二级Cache的以下数据：（1）2路组相联使命中时间增加10%×CPU时钟周期