[计算机体系结构]第5章存储层次.ppt

《[计算机体系结构]第5章存储层次.ppt》由会员分享，可在线阅读，更多相关《[计算机体系结构]第5章存储层次.ppt（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计计 算算 机机 体体 系系 结结 构构第五章第五章 存存 储储 层层 次次本章要点本章要点:存储系统存储系统 存储层次存储层次 存储系统的性能参数存储系统的性能参数 CacheCache存储器工作原理存储器工作原理 CacheCache地址映象与变换算法地址映象与变换算法 CacheCache替换算法及其实现替换算法及其实现 CacheCache写操作写操作1计计 算算 机机 体体 系系 结结 构构 CacheCache系统性能的改进方法系统性能的改进方法 主存系统主存系统 低位交叉访问存储器低位交叉访问存储器 高位交叉访问存储器高位交叉访问存储器 虚拟存储器工作原理虚拟存储器工作原理 段式

2、、页式、段页式存储管理段式、页式、段页式存储管理 虚拟存储器地址映象与变换算法虚拟存储器地址映象与变换算法 页面替换算法及其实现页面替换算法及其实现 缓冲对虚拟存储系统性能的影响缓冲对虚拟存储系统性能的影响 CacheCache、主存、虚拟存储器的比较主存、虚拟存储器的比较2计计 算算 机机 体体 系系 结结 构构 本章的主要应用问题本章的主要应用问题 CacheCache性能分析性能分析 层次存储器性能分析层次存储器性能分析 Cache Cache地址流分析地址流分析 虚拟存储器地址流分析虚拟存储器地址流分析 存储器系统设计存储器系统设计 3第第五五章章 存存 储储 层层 次次5.1 存储器

3、的层次结构存储器的层次结构 存储器是计算机的核心部件之一，其性能直接关系到整个计算机系统性能的高低。存储器的三个主要指标是：速度、容量和价格(即每位价格)。如何以合理的价格，设计容量和速度满足计算机系统需求的存储器系统，始终是计算机体系结构设计中的关键问题之一。5.1.1 从单级存储器到多级存储器从单级存储器到多级存储器 计算机软件设计者和计算机用户总是希望存储器的容量越大越好，而且速度要快，价格也不能太昂贵。而实际情况却是：速度越快，每位价格越高；容量越大，每位价格越低；容量越大，速度越慢。人们对存储器设计的三个指标要求是互相矛盾的。4第第五五章章 存存 储储 层层 次次 解决问题的办法必须

4、切合实际地综合考虑：从实现“容量大、价格”的要去来看，应采用能提供大容量技术的存储器技术；但从满足性能需求的角度来看，又应采用昂贵且容量较小的快速存储器。走出这种困境的唯一方法，就是采用多种存储技术，构成存储器的层次结构，如图5.1所示。5第第五五章章 存存 储储 层层 次次 在多级存储层次中，最靠近CPU的M1速度最快、容量最小、价格最高；而远离CPU的Mn则是速度最慢、容量最大、价格最低。存储系统的设计目标是：M1的速度，Mn的容量和价格。层次存储器设计的依据：程序局部性原理程序局部性原理。在层次存储中，靠近CPU的存储器中的数据一般都是其下一层存储器中数据的子集。CPU访存时的基本原则：

5、有近及远，首先是访问M1，若在M1中找不到所要的数据，就要访问M2，将包含所需数据的块或页面调入M1。若在M2中还找不到，就要访问M3，依此类推。如果所有层次中都没有，就出现错误。6第第五五章章 存存 储储 层层 次次5.1.2 存储层次的性能参数存储层次的性能参数 研究方法：层次存储器基本问题通过两层存储器结构进行研究。对于由M1和M2构成的两级存储层次结构，假设M1、M2的容量、访问时间和每位价格分别为S1、TA1、C1和S2、TA2、C2。1.存储层次的平均每位价格显然，当S1S2时，C C2。2.命中率H 命中率为CPU访问存储系统时，在M1中找到所需信息的概率。访问M1和M2的次数为

6、N1和N2。7第第五五章章 存存 储储 层层 次次 不命中率或失效率F是指CPU访存时在M1找不到所需信息的概率。3.平均访问时间TA 分两种情况来考虑CPU的一次访存：（1）当命中时，访问时间即为TA1。TA1常称为命中时间（hit-time）。（2）大多数二级存储层次结构下，当不命中M1时，就必须从M2中访问这个字，并把包含所请求的字的信息块传送到M1，之后CPU才能访问这个字。假设传送一个信息块所需的时间为TB，则不命中时的访问时间为：TA2TBTA1TM其中TMTA2TB，它为从向M2发出访问请求到把整个数据块调入M1中所需的时间。TM常称为失效开销。8第第五五章章 存存 储储 层层

7、次次 根据以上分析可知：TAHTA1(1H)(TA1TM)TA1(1H)TM或 TATA1FTM5.1.3 “Cache-主存主存”和和“主存主存-辅存辅存”层次层次 1.“Cache-主存”层次 CPU和主存之间在性能上的差距越来越大，如图5.2所示。现代计算机都采用Cache来解决这个问题。9第第五五章章 存存 储储 层层 次次 “Cache-主存”层次的工作几乎完全由硬件实现，因此它不但对应用程序员是透明的，而且对系统程序员几乎也是透明的。2.“主存-辅存”层次 为了弥补主存容量，在主存外面增加一个容量更大、每位价格更低、但速度更慢的存储器(称为辅存，一般是硬盘)。“它们依靠辅助软硬件的

8、作用，构成一个整体，如图5.3所示。主存-辅存”层次常被用来实现虚拟存储器，向编程人员提供大量的程序空间。3.“Cache-主存”层和“主存-辅存”层的简单比较 表5.1对“Cache-主存”层和“主存-辅存”层做了一个简单的比较。10第第五五章章 存存 储储 层层 次次5.1.4 两级存储层次之间的四个基本问题两级存储层次之间的四个基本问题 对于具体存储层次而言，将研究一下四个问题：1.当把一个块调入高一层（靠近CPU）存储器时，可以放到哪些位置上？（映象规则）2.当要访问的块在高一层存储器时，如何找到该块？（查找算法）3.当发生失效时，应替换哪一块？（替换算法）4.当进行写访问时，应进行哪

9、些操作？（写策略）5.2 Cache基本知识基本知识 Cache用于解决上述四个基本问题，即映象规则、查找算法、替换算法以及写策略。11第第五五章章 存存 储储 层层 次次 Cache是按块进行管理的，Cache和主存均被分割成大小不同的块，信息以块为单位调入Cache。CPU的访存地址被分割成块地址和块内地址两部分：主存地址：主存地址：块地址块地址 块内位移块内位移 主存块地址用于查找在Cache中的位置，块内位移用于确定所访问的数据在该块中的位置。5.2.1 映象规则映象规则三种映象规则如图5.4所示。1.全相联：主存中的任一块可以被放置到Cache中的任何一个位置的方法。2.直接映象：主

10、存中的每一个块只能被放置到Cache中唯一的一个位置。3.组相联映象：主存中的每一个块可以被放置到Cache中唯一的一个组中的任一个位置。12第第五五章章 存存 储储 层层 次次 全相联映象时，主存中的任一块可以放置到Cache中的任一位置，如图5.4(a)所示，主存中的第9块可以放入Cache中的任意一个位置(带阴影)。图示中画出了Cache大小为8块、主存大小为16块的情况。直接映象情况下，对于主存的第i块(块地址为i)，设它映象到Cache中的第j块，则 ji mod(M)其中，M为Cache的块数。若M2m，则当地址表示为二进制数时，Cache的块号j实际上就是主存地址i的m位，如下图

11、所示。因此，可以直接用主存地址的低m位去选择直接映象Cache中的相应块。13第第五五章章 存存 储储 层层 次次 组相联映象是直接映象和全相联映象的一种折衷：首先是映象到唯一的一个组上(直接映象的特征)，然后这个块可以被放入这个组中的任何一个位置(全相联的特征)。若主存第i块映象到Cache的第k组，则 ki mod(G)其中，G为Cache的组数。设G2g，则当表示为二进制数时，k实际上就是i的低g位，如图所示。因此，可以直接用主存块地址的低g位去选择Cache中的相应组。这里的低g位以及上述直接映象中的低m位通常称为索引。14第第五五章章 存存 储储 层层 次次 如果每组中有n个块(n=

12、M/G)，则称该映象规则为n路组相联。n的值为相联度。直接相联和全相联是组相联的两种极端情况。表5.2给出了路数n和组数G的取值。表中M为Cache的块数。下面是一般性分析 1.相联度越高(即n的值越大)，Cache空间的利用率越高，块冲突(一个主存块要进入已被占用的Cache位置)概率越低，因而Cache的失效率就越低；2.全相联的失效率最低，直接相联的失效率最高；3.增大n值并不一定使整个计算机系统的性能提高，而且还会使Cache的实现复杂度和代价增大。因此，绝大多数计算机都采用直接相联、两路相联或四路相联。特别是直接相联，采用最多。15第第五五章章 存存 储储 层层 次次5.2.2 查找

13、方法查找方法 当CPU访问Cache时，有两个问题要解决：(1)当CPU访问Cache时，如何确定Cache中是否有要访问的块？(2)若有的话，如何确定其位置？这是通过查找目录表来实现的。Cache中设有一个目录表，该表共有m项，每一项对应于Cache中的一个块，称为标识(tag)。在目录表中给每一项设置一个有效位，记录Cache中相应块所包含的信息有效。一个主存块被调入Cache中某一个块位置时，它的标识就被填入目录表中与该Cache块相对应的项中，并且该项的有效位被置“1”，否则置“0”。16第第五五章章 存存 储储 层层 次次 根据映象规则不同，一个主存块可能映象到Cache中的一个或多

14、个Cache块位置。我们称之为候选位置。候选位置。当CPU访问该主存块时，必须且只需查找它的候选位所对应的目录表项(标识)。如果有与所访问的主存块相同的标识，且其有效值为“1”，则它所对应的Cache块就是所要找的块。为了保证速度，对各候选位置的标识的检查比较应并行进行。直接映象Cache的候选位置只有1个；全相联Cache的候选位置为m个；n路组相联则介于两者之间，为n个。一般采用单体多字存储器和比较器来实现并行查找。n越大，实现查找的机制就越复杂，代价就越高。无论是直接映象还是组相联映象，查找时，只需比较tag。Index无需参加比较。17第第五五章章 存存 储储 层层 次次 如果Cach

15、e的容量不变，提高相联度会增加每一组中的块数，从而会减少index的位数和增加tag的位数。图5.5给出了4路组相联并行标识比较。5.2.3 替换算法替换算法 当要从主存调入一块到Cache中时，会出现该块所映象的一组（或一个）Cache块已被占用的情况。这时，必须强迫腾出其中的某一块，已接纳新调入的块。腾出哪一块？这就是替换算法所要解决的问题。直接映象直接映象：Cache中的替换很简单，因为只有一个块可选择；组相联和全相联组相联和全相联：Cache中有多个块选择，替换算法有随机法、FIFO和LRU三种。评价替换算法的标准：尽可能避免替换马上就要用到的信息。18第第五五章章 存存 储储 层层

16、次次1.随机法 随机地选择被替换的块。优点优点：简单、易于用硬件实现，且对调试硬件很有帮助。不足不足：没有考虑Cache块被使用的情况，反映不了程序的局部性。2.先进先出FIFO（First-First-Out）最先装入相应组的块作为被替换的块。优点优点：容易实现。不足不足：虽然利用了各块进入Cache的顺序这段“历史”信息，但还是不能正确反映程序的局部性。因为最先进入的块，很可能是经常要用到的块。3.最近最少使用法LRU（Least Recently Used）选择近期最少被访问的块作为被替换的块。优点优点：反映程序的局部性原理，因而其失效在上述三种方法中是最低的。不足不足：LRU比较复杂，

17、硬件实现比较困难，特别是当组的大小增加时，LRU的实现19第第五五章章 存存 储储 层层 次次代价会越来越高，而且经常只是近似地实现（选择最久没有被访问过块作为被替换的块）。LRU实际上是依据程序局部性原理的一个推论：如果最近刚用过的块很可能就是马上要再用到的块，而最久没用过的块就是最佳的被替换者。表5.3给出了LRU与随机法在失效率方面的比较。20第第五五章章 存存 储储 层层 次次表中的数据是对于一个VAX地址流(包括用户程序和操作系统程序)，块大小为16B的情况下统计的。在这个例子中，对于大容量Cache，LRU和随机法的失效率几乎没有什么差别。显然，n越大，Cache容量越大，时效率越

18、低。此外，表中虽然没有列出，但是FIFO法的失效率比随机法和LRU都高。5.2.4 写策略写策略 写需要对存储器和Cache两部分进行操作。写与读的比较：（1）检查标识并不能与写入Cache块并行进行，“写”一般比“读”化肥更多的时间。（2）处理器要写入的数据的宽度不是定长的。(通常为18字节)，写入时，只能修改Cache块中相应的21第第五五章章 存存 储储 层层 次次部分，不能够多修改。而“读”则可以多读出几个字节也没关系。Cache与主存内容一致性问题：Cache内容是主存部分内容的一个副本。“写”访问却可能导致它们内容的不一致。显然，为了保证正确性，主存的内容也必须更新。何时更新主存，

19、是写策略所要解决的问题。写策略是区分不同Cache设计方案的一个重要标志。写策略主要有写直达法和写回法两种。1.写直达法 该法也称为存直达法。在执行“写”操作中，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。22第第五五章章 存存 储储 层层 次次 优点：易于实现。下一级存储器中的数据总是最新的。这一个优点对于I/O和多处理机是重要的。问题：写直达法在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，称为CPU写停顿(write stall)。常用的优化技术：写缓冲器(write buffer)。CPU一旦把数据写入该缓冲器，就可以继续执行，使下一级存储器的更新

20、和CPU的执行重叠起来。2.写回法(write back)该法也称为拷回法(copy back)。只把信息写入Cache中相应的块。该块只有在被替换时，才被写回主存。为了减少在替换时块的写回，在Cache中的每一块设置一个“污染位”，用于指出该块是“脏的”，23第第五五章章 存存 储储 层层 次次即没被修改过（被修改过）还是干净的（没被修改过）。替换时，若被替换的块石干净的，则不必写回下一级存储器。只有被修改过的块写回。写回法的优点：速度快，“写”操作能以Cache存储器的速度进行。对于同一单元的多个写只需最后一次写回下一级存储器。有些“写”只到达Cache，不到达主存，所使用的存储器频带较低

21、。这使得写回法对于多处理机很有吸引力。写访问失效时的内存分配。当发生写失效时，是否调入相应的块，有两种选择：（1）按写分配法（Write allocate）写失效时，先把所写单元所在的块调入Cache，然后再进行写入。与读失效类似，此法也称为写时取。24第第五五章章 存存 储储 层层 次次（2）不按写分配法（no-write allocate）写失效时，直接写入下一级存储器而不将相应的块调入Cache。这种方法也称为绕写法(write around)。写回法Cache一般采用按写分配法（这样以后对那个块的“写”就能被Cache捕获）。写直达法一般采用不按写分配法（因为以后对那个块的“写”仍然还

22、要到达下一级存储器）。5.2.5 Cache的结构的结构 下面以DEC的Alpha AXP 21064为例进一步说明。该Cache的结构如图5.6所示。容量为8KB，块大小为32字节，共有256个块；直接相联映象；采用写直达法，写缓冲的大小为4个块，并且在写失效时不按写分配。25第第五五章章 存存 储储 层层 次次 四选一的多路选择器：数据RAM为8各字节宽；索引加上块内偏移量的高两位作为RAM的地址，就选取了相应的8个字节，多路选择器仅仅是块内偏移量高两位的译码示意。（1）21064读数据Cache 第一步：地址的分割。21064微处理器传送给Cache的物理地址为34位。这个地址被分为两部

23、分：块地址（29位）和块内偏移地址（5位）。块地址进一步被分为地址标识（21位）和Cache索引（8位）；索引从256个Cache块中选择一块，读出数据和标识；标识用于判断要访问的块是否在Cache中（是否命中）；索引的位数由Cache容量、块大小、相联度决定。26第第五五章章 存存 储储 层层 次次21064的Cache是直接映象的，所以相联度为1，索引所需的位数满足：索引的为8位，标识为29-8=21位。第二步：按索引选择标识 在直接映象的Cache中，读出数据并送往CPU与读出标识并进行匹配这两个过程可以并行进行。第三步：标识比较。标识从Cache中读出来以后，就去和CPU送来的物理地址

24、中的标识部分进行比较。为了保证标识信息有效，其相应的有效位必须为“1”，否则比较的结果就是无效的。27第第五五章章 存存 储储 层层 次次 第四步：CPU从Cache中取数据。如果标识比较的结果匹配，且有效位为“1”，那么最后一步就是发信号通知CPU从Cache中取走数据。其它说明：21064完成这4步需要2个时钟周期；如果这两个周期中均按，指令需要用到本次“读”的结果，这条指令就只好等待。（2）21064写数据Cache 写命中：前三步跟上面是一样的。在确定标识比较为匹配之后，才把数据写入。因为21064使用写直达Cache，所以到此写过程还未结束，还应将数据送往缓冲器。21064的写缓冲器

25、含有四个块，每块大小为4个字，缓冲器是按字寻址（21064中每个字为8字节）。28第第五五章章 存存 储储 层层 次次 写缓冲为空，就把数据和完整的地址写入缓冲器。对CPU而言，本次“写”访问已完成，可以继续工作，而写缓冲器将负责把该数据写入主存。（3）21064数据Cache的写合并 缓冲器内还有其他被修改过的块，就与缓冲器内有效块的地址进行匹配；如果匹配，就把新数据与该块合并。这叫写合并（write merging）。没有这种优化措施，按顺序地址连续“写”四次，就可能会填满整个缓冲器。采用写合并，就可以很容易地将这四个字放入缓冲器的同一块中。每个缓冲器有4项，每项能放4个字（32字节），各

26、项的地址标在左边，有效位V用于指出其后的4各字节是否已被占用。29第第五五章章 存存 储储 层层 次次 缓冲器满：缓冲器一旦满，并且没有地址相匹配的块，Cache和CPU就需要等待到缓冲器有空闲项。没有时，的值为100、104、108和112的四次写，占据了缓冲器的全部四个项；有写合并时，这四个字被合并为一项，如图5.7所示。（4）21064的Cache失效 读失效：Cache向CPU发出一个暂停信号，通知它等待；从下一级存储器中读入32字节数据；21064的Cache和它的下一级存储器之间的数据通路(21064微处理器总线的数据通道)为16字节（128位）。21064的数据Cache是直接映

27、象的，所以被替换块只有一个；替换一个块意味着更新该块的数据、标识和有效位。30第第五五章章 存存 储储 层层 次次 写失效：21064采用不按写分配原则，也就是说，CPU将数据“绕过”Cache，直接写入主存。（5）指令Cache和数据Cache的设置 使用指令数据混合Cache（称为统一Cache或混合Cache)来同时提供数据和指令，但它有可能会成为瓶颈。例如，当流水方式工作的处理器执行load或store指令时，可能会同时请求一个数据字和一个指令字，导致CPU等待。分离的Cache：将单一的Cache分为两个Cache，一个专门放指令，另一个专门存放数据。21064有一个8KB的指令Ca

28、che，其结构和8KB数据Cache几乎一样。提高了系统对存储系统和CPU之间数据通道带宽的要求；能分别对它们进行优化。31第第五五章章 存存 储储 层层 次次结果：指令Cache的失效率比数据Cache的低；消除了Cache中的指令块和数据块互相冲突而引起的失效。32第第五五章章 存存 储储 层层 次次5.2.6 Cache性能分析性能分析5.2.7 改进改进Cache性能性能根据平均访存时间公式：平均访存时间命中时间失效率失效开销可知，可以从以下三个方面改进Cache的性能：（1）降低失效率；（2）减少失效时间；（3）减少Cache命中时间。下面将介绍15种Cache优化技术，其中，7种用

29、于降低失效率；5种用于减少失效开销；3种用于减少命中时间。33第第五五章章 存存 储储 层层 次次5.3 降低降低Cache失效率的方法失效率的方法 三类失效（简称为“3C”）（1）强制性失效（Compulsory miss）：当第一次访问一个块时，该块需从下一级存储器中调入Cache。也称为冷启动失效或首次访问失效。（2）容量失效（Capacity miss）：如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。（3）冲突失效(Conflict miss)：在组相联或直接映射中，若太多的块映射到同一组(块)中，则会出现该组中某个块被别的块替换（即

30、使别的组或块有空闲位置），然后又被重新访问的情况下。这种失效也称为碰撞失效(collision)或干扰失效(interference)。34第第五五章章 存存 储储 层层 次次 表5.5针对三种SPEC92典型程序给出了上述三种失效所占的比例。可以看出：（1）相联度越高，冲突失效就越少；（2）强制性失效和容量失效不受相联度的影响；（3）强制性失效不受Cache容量的影响，但容量失效随着容量的增加而减少；（4）表中的数据符合2:1的Cache经验规则，即大小为N的直接映象Cache的失效率约等于大小为N/2的两路组相联Cache的失效率。相联度越高，冲突失效就越少；全相联不会发生冲突失效。用硬件

31、实现全相联根昂贵，而且可能降低处理器的时钟频率，导致整体性能的下降。35第第五五章章 存存 储储 层层 次次 相联失效随着容量的增加而减少，除了增大Cache以外，没有别的办法。但是它不受相联度的影响。图5.9是表5.5中数据的图示。表5.6为各块大小情况下Cache的失效率。降低Cache失效率的7种方法：增加Cache块大小 提高相联度 设置Cache替换缓冲 伪相联映象 预取技术 由编译器控制的预取 编译器优化 许多降低失效率的方法会增加命中时间(hit time)或失效开销(miss penalty)。36第第五五章章 存存 储储 层层 次次5.3.1 增加增加Cache块的大小块的大

32、小 “U”形曲线：降低失效率最简单的方法是增加块大小。Cache容量越大，使失效率达到最低的块大小就越大。如图5.10所示。37第第五五章章 存存 储储 层层 次次增加块大小有双重作用：（1）利用了时间局部性，减少了强制性失效；（2）减少Cache中块的数目，所以有可能会增加冲突失效。在Cache容量较小时，甚至还会增加容量失效。刚开始增加块大小时，由于块还不是很大，上述第一种作用超过第二种作用，从而使失效下降。但到块较大时，第二种作用超过第一种作用，故使失效率上升。38第第五五章章 存存 储储 层层 次次5.3.2 提高相联度提高相联度 提高相联度会使失效率下降。由此我们得出两条经验规则：（

33、1）8路组相联在降低失效率方面的作用与全相联一样有效。也就是说，采用相联度超过8的实际意义不大。（2）2:1Cache经验规则：容量为N的直接映象Cache的失效率和容量为N/2的两路组相联Cache差不多相同。改进平均访存时间某一方面是以损失另一方面为代价的：增加块大小在降低失效率的同时增加失效开销（原因：块的调入时间加大）为减少失效开销，有要求提高相联度提高相联度则是以增加命中时间为代价的。39第第五五章章 存存 储储 层层 次次5.3.3 Victim Cache 一种能减少冲突失效而又不影响时钟频率的方法是：在Cache中存放因失效而被丢弃（替换）的那些块(即牺牲Victim)，每当发

34、生失效时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需的块，如果有，就将该块与Cache中某个块做交换。效果：Jouppi发现，含1到5项的Victim Cache对减少冲突失效很有效，尤其是对于那些小型的、直接映象 数据Cache更是如此。对于不同的程序，一个项数为4的Victim Cache能使一个4KB直接映象数据Cache的冲突失效减少20%90%。从Cache的层次来看，Victim Cache可以看成位于Cache和存储器之间的又一级Cache，采用命中率较高的全相联映象，容量小，且仅仅在替换时起作用。40第第五五章章 存存 储储 层层 次次图5.11描述了

35、Victim Cache在存储层次中的位置。41第第五五章章 存存 储储 层层 次次5.3.4 伪相连伪相连Cache 伪相联(pseudo-associate)或列相联(column associate)：既能获得多路组相联Cache的低失效率，又能保持直接映象Cache的命中速度。工作过程：采用这种方法时，在命中情况下，访问Cache的过程和直接映象Cache中的情况相同；而发生失效时，在访问下一级存储器之前，会先检查Cache另一个位置，看是否匹配。如果这一块的标识匹配，则称发生了“伪命中”。否则，就只好访问下一级存储器。第二个位置的选择：一种简单的确定另一块位置的方法是将索引字段的高位

36、取反，然后按照新索引去寻找“伪相联”中的对应块。42第第五五章章 存存 储储 层层 次次 如果直接映象Cache里的许多快速命中在伪相联Cache中变成慢速命中，那么这种优化措施反而会降低整体性能。解决方案之一：交换两个块的内容：问题：多种命中时间会使CPU流水线的设计复杂化。图5.12给出了正常命中时间、伪命中时间和失效开销之间的关系。43第第五五章章 存存 储储 层层 次次 采用直接映象和两路组相联时，命中时间相差2%10%。一般情况：很高的处理器时钟频率，需要结构简单的Cache；单时钟频率越高，失效开销越大（时钟周期数越多）。44第第五五章章 存存 储储 层层 次次5.3.5 硬件预取

37、技术硬件预取技术 预取技术：预取内容可以直接放入Cache，也可以放在一个访问速度比主存快的外部缓冲器中。指令和数据都可以在处理器提出访问请求之前进行预取。指令预取通常由Cache之外的硬件完成。工作方式：被请求指令块返回时放入Cache，而预取指令块则放在缓冲器中；如果某次被请求的指令块正好在缓冲器里，则取消对该块的访存请求，直接从缓冲器中读出这一块，同时发出对下一指令块的预取访存请求。优点：预取技术、Victim Cache和伪相联都能在不影响处理器时钟频率的前提下降低时效率。45第第五五章章 存存 储储 层层 次次 Jouppi的研究结果表明：对于块大小为16B，容量为4KB的直接映象指

38、令Cache，一个块的指令缓冲器就可以捕获15%25%的失效，4个块的指令缓冲器可以捕获大约50%的失效，而16个块的缓冲器则可以捕获72%的失效。一个数据缓冲器大约可以捕获4KB直接映象Cache25%的失效。对数据Cache，可以采用多个数据缓冲器，分别从不同的地址预取数据。用4个数据缓冲器可以将命中率提高到43%。46第第五五章章 存存 储储 层层 次次5.3.6 由编译器控制的预取由编译器控制的预取 基本思想：由编译时加入预取指令，在数据被用到之前发出预取请求。预取有以下几种类型：寄存器预取：把数据取道寄存器中。Cache预取：只将数据取到Cache中，而不放入寄存器。故障性预取是指在

39、预取时，若出现虚地址故障或违反保护权限，则会发生异常。而非故障性预取，也叫做非绑定预取，在遇到相应情况时则不会发生异常。预取指令需要花费一条指令的开销，要注意保证这种开销不超过预取所带来的收益。47第第五五章章 存存 储储 层层 次次5.3.7 编译器优化编译器优化 通过对软件的优化来降低失效率。特点：无需对硬件做任何改动就可以降低失效率。前提：重新组织程序而不影响程序的正确性。目的：改善数据的空间局部性和时间局部性。优化的四个例子（四种技术，如图所示）：数组合并、互换循环、循环融合、分块。48第第五五章章 存存 储储 层层 次次5.4 减少减少Cache失效开销失效开销 以往对Cache的研

40、究一直把重点放在减少失效次数上，但是Cache性能公式却告诉我们，家少Cache失效开销可以跟降低Cache失效率一样带来性能上的提高。由图5.2可以看出，随着技术的发展，处理器速度的提高要快于DRAM速度的提高，这使得Cache失效开销的相对代价随时间不断增加。下面将给出解决这一问题的5种优化措施。其中最后一种是通过增加另一级Cache来减少失效开销，这也许是最令人感兴趣的方法。5.4.1 读失效优先于写 提高写直达Cache性能最重要的方法是使用一个大小适中的写缓冲器。但是写缓冲器却导致对存储器的访问复杂化。下面通过例子进一步说明。49第第五五章章 存存 储储 层层 次次 问题分析：在执行

41、SW指令之后，R3中的数据被放入写缓冲器。接下来的第一条LW指令使用相同的Cache索引，因而产生一次失效。第二条LW指令欲把的值为512的存储单元的值读入寄存器R2中，这也会造成一次失效。如果此时写缓冲器还微将数据写入存储单元512中，那么第二条LW指令将把错误的旧值读入Cache和寄存器R2。如果不采取适当的预防措施，R2的值就不会等于R3的值。50第第五五章章 存存 储储 层层 次次 解决方法（写直达）：推迟对读失效的处理，直至写缓冲器清空。新问题：Cache中有一个大小只有几个字的写缓冲器在发生读失效时几乎总有数据，这就增加了读失效的开销。改进方法：读失效时检查写缓冲器的内容，如果没有

42、冲突而且存储器可访问，就可以继续处理读失效。在写回法：假定读失效将替换一个“脏”的存储块。我们可以不像往常那样先把“脏”块写回存储器，然后再读存储器，而是先把被替换的“脏”块拷入一个缓冲器，然后读存储器，最后再写存储器。这样CPU的“读”访问就能更快地完成。发生读失效时，处理器既可以采用等待缓冲区清空的方法，也可以采用检查缓冲区中各字的地址是否有冲突的方法。51第第五五章章 存存 储储 层层 次次5.4.2 子块放置技术子块放置技术 子块放置技术把一个Cache块划分成若干个小块，称之为子块。为每一个子块赋予一位有效位，用于说明该子块中的数据是否有效。因此，标识匹配并不意味着这个字一定在Cac

43、he中，只有当与该字对应的有效位也为“1”时才是。失效时只需从下一级存储器调入一个子块。这样，一个Cache中就有可能有的子块有效，有的子块无效。显然子块的失效开销小于完整Cache块的失效开销。子块可以被看成是地址标识之外的又一级寻址。图5.15给出了一个例子。显然，使用子块可以减少标识所占的存储空间。如果图中的有效位都用完整的标识来替代，标识所占用的空间将大得多。这正是采用子块放置法的原因。52第第五五章章 存存 储储 层层 次次5.4.3 请求字处理技术请求字处理技术 当从存储器向CPU调入一块时，块中往往只有一个字是CPU立即需要的，这个字称为请求字。请求字处理技术指当CPU所请求的字

44、到达后，不等整个块都调入Cache，就可把改字发送给CPU病重新启动CPU。有两种具体的方案：（1）尽早重启动(early restart)在请求字没有到达时，CPU处于等待状态。一旦请求字到达，就立即发送给CPU，并启动。（2）请求字优先(request word first)调块时，首先向存储器请求CPU所要的请求字，再从存储器调入该块的其余部分。请求字优先也称为回绕读取(wrapped fetch)或关键字优先(critical)。53第第五五章章 存存 储储 层层 次次5.4.4 非阻塞非阻塞Cache技术技术 基本出发点：一个Cache请求失效时可以发出后续请求。这种“失效下命中”(

45、hit under miss)的优化措施在Cache失效时，不是完全拒绝CPU的访问，而是能处理部分访问，从而减少了实际失效开销。这就是非阻塞(non blocking)Cache或非锁定Cache技术。如果Cache允许多个失效重叠，即支持“多重失效下的命中”(hit under multiple miss)和“失效下失效”(miss under miss)，则可进一步减少实际失效开销。“失效下命中”措施大大增加了Cache控制器的复杂度，因为这时可能有多个访存同时进行。理论上可以同时处理的失效个数越多，所能带来的性能上的提高就越大。54第第五五章章 存存 储储 层层 次次 对于SPEC92

46、典型程序，图5.16给出了对于不同的重叠失效数，数据Cache的平均失效开销（以周期为单位）与阻塞Cache平均失效开销的比值。所考虑的Cache采用直接映象，容量为8KB，块大小为32字节。测试程序为18个SPEC92程序。前14个测试程序为浮点程序，后4个为整数程序。在重叠失效个数为1、2和64的情况下，浮点程序的平均比值分别为：76、51和39，而整数程序的平均比值分别为：81、78和78。从图中可以看出，对于浮点程序来说，重叠失效次数越多，性能提高越多；但对于整数程序来说，重叠次数对性能提高影响不大，简单的“一次失效命中”就可以了，几乎得到了所有的好处。另外，“失效下命中”方法有一个潜

47、在优点：它不会影响命中时间，而组相联却会。55第第五五章章 存存 储储 层层 次次5.4.5 采用两级采用两级Cache 二级Cache技术的着眼点：Cache和主存的接口。为了克服CPU和主存之间越来越大的性能差距，使存储器和CPU的性能匹配，我们是应该把Cache做得更快，还是应该把Cache做得更大？一种答案是：二者兼顾。通过在原有Cache和存储器之间增加另一级Cache，构成两级Cache，我们可以把第一级Cache做得足够小，使其速度和快速CPU的时钟周期相匹配，而把第二级Cache做得足够大，使它能捕获更多本来需要到主存去的访问，从而降低实际失效开销。性能公式用下标L1和L2分别

48、表示第一级和第二级Cache，则：56第第五五章章 存存 储储 层层 次次平均访存时间命中时间L1失效率L1失效开销L1失效开销L1命中时间L2失效率L2 失效开销L2 所以，平均访存时间命中时间L1失效率L1 （命中时间L2失效率L2 失效开销L2）二级Cache系统采用以下术语（1）局部失效率 对于某一级Cache来说，局部失效率 该级Cache的失效次数/到达该级Cache的访存次数 对于第二级Cache来说，就是上面的失效率。（2）全局失效率 对于某一级Cache来说，全局失效率 该级Cache的失效次数/CPU发出的访存总次数使用上面公式中的变量，第二级Cache的全局失效率 全局失

49、效率L2失效率L1失效率L257第第五五章章 存存 储储 层层 次次 对于第二级Cache，有以下两点结论：（1）在第二级Cache比第一级Cache大得多的情况下，两级Cache的全局失效率和容量与第二级Cache相同的单级Cache的失效率非常接近。这时可以利用前面关于单级Cache的分析和知识。（2）局部失效率不是衡量第二级Cache的一个好指标，因为它是第一级Cache失效率的函数，可以通过改变第一级Cache而使之变化，而且不能全面反映两级Cache体系的性能。因此，在评价第二级Cache时，应用全局失效率这个指标。第二级Cache的设计只有两个问题需要权衡：它能否降低CPU中的平均

50、访存时间部分？它的成本是多少？58第第五五章章 存存 储储 层层 次次 第二级Cache的容量一般很大，和过去计算机的主存一样大！大容量意味着第二级Cache可能实际上没有容量失效，只剩下一些强制性失效和冲突失效。我们可以利用前面几节介绍的技术来减少第二级Cache的失效率，从而达到减少失效开销的目的 综合上述考虑，Cache设计的本质是在快速命中和失效次数少这两方面进行权衡。大部分优化措施都是在提高一方的同时降低另一方。对于第二级Cache而言，它的命中次数比第一级Cache少得多，所以重点就转移到了减少失效次数上。这就导致了大容量、更高相联度和更大块大小的Cache的出现。图5.17给出了