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

1、1,第五章 存 储 层 次,本章要点: 存储系统 存储层次 存储系统的性能参数 Cache存储器工作原理 Cache地址映象与变换算法 Cache替换算法及其实现 Cache写操作,2, Cache系统性能的改进方法 主存系统 低位交叉访问存储器 高位交叉访问存储器 虚拟存储器工作原理 段式、页式、段页式存储管理 虚拟存储器地址映象与变换算法 页面替换算法及其实现 缓冲对虚拟存储系统性能的影响 Cache、主存、虚拟存储器的比较,3,本章的主要应用问题 Cache性能分析 层次存储器性能分析 Cache地址流分析 虚拟存储器地址流分析 存储器系统设计,4,5.1 存储器的层次结构 存储器是计算

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

3、器技术；但从满足性能需求的角度来 看，又应采用昂贵且容量较小的快速存储器。走出 这种困境的唯一方法，就是采用多种存储技术，构 成存储器的层次结构，如图5.1所示。,6,在多级存储层次中，最靠近CPU的M1速度最快、 容量最小、价格最高；而远离CPU的Mn则是速度最 慢、容量最大、价格最低。 存储系统的设计目标是：M1的速度，Mn的容量和 价格。 层次存储器设计的依据：程序局部性原理。 在层次存储中，靠近CPU的存储器中的数据一般 都是其下一层存储器中数据的子集。 CPU访存时的基本原则：有近及远，首先是访问 M1 ， 若在M1中找不到所要的数据，就要访问M2 ， 将包含所需数据的块或页面调入M

4、1 。若在M2中还 找不到，就要访问M3 ，依此类推。如果所有层次中 都没有，就出现错误。,7,5.1.2 存储层次的性能参数 研究方法：层次存储器基本问题通过两层存储器 结构进行研究。 对于由M1和M2构成的两级存储层次结构，假设 M1、M2的容量、访问时间和每位价格分别为S1、 TA1、C1和S2、TA2、C2。 1. 存储层次的平均每位价格 显然，当S1S2时，C C2。 2. 命中率H 命中率为CPU访问存储系统时， 在M1中找到所需信息的概率。 访问M1和M2的次数为N1和N2。,8,不命中率或失效率F是指CPU访存时在M1找不到所 需信息的概率。 3. 平均访问时间TA 分两种情况

5、来考虑CPU的一次访存： （1）当命中时，访问时间即为TA1。 TA1常称为命中 时间（hit-time）。 （2）大多数二级存储层次结构下，当不命中M1时， 就必须从M2中访问这个字，并把包含所请求的字的 信息块传送到M1 ，之后CPU才能访问这个字。假设 传送一个信息块所需的时间为TB，则不命中时的访 问时间为： TA2TBTA1TM 其中TMTA2TB，它为从向M2发出访问请求到把整 个数据块调入M1中所需的时间。TM常称为失效开销。,9,根据以上分析可知： TAHTA1(1H)(TA1TM ) TA1(1H)TM 或 TATA1FTM 5.1.3 “Cache-主存”和“主存-辅存”层

6、次 1. “Cache-主存”层次 CPU和主存之间在性能上的差距越来越大，如图 5.2所示。现代计算机都采用Cache来解决这个问题。,10,“Cache-主存”层次的工作几乎完全由硬件实现， 因此它不但对应用程序员是透明的，而且对系统程 序员几乎也是透明的。 2. “主存-辅存”层次 为了弥补主存容量，在主存外面增加一个容量更 大、每位价格更低、但速度更慢的存储器(称为辅存， 一般是硬盘)。“它们依靠辅助软硬件的作用，构成 一个整体，如图5.3所示。主存-辅存”层次常被用来 实现虚拟存储器，向编程人员提供大量的程序空间。 3. “Cache-主存”层和“主存-辅存”层的简单比较 表5.1对

7、“Cache-主存”层和“主存-辅存”层做了一个 简单的比较。,11,5.1.4 两级存储层次之间的四个基本问题 对于具体存储层次而言，将研究一下四个问题： 1. 当把一个块调入高一层（靠近CPU）存储器时，可以放到哪些位置上？（映象规则） 2. 当要访问的块在高一层存储器时，如何找到该块？（查找算法） 3. 当发生失效时，应替换哪一块？（替换算法） 4. 当进行写访问时，应进行哪些操作？（写策略） 5.2 Cache基本知识 Cache用于解决上述四个基本问题，即映象规则、 查找算法、替换算法以及写策略。,12,Cache是按块进行管理的，Cache和主存均被分割成 大小不同的块，信息以块为

8、单位调入Cache。 CPU的访存地址被分割成块地址和块内地址两部分： 主存地址： 块地址 块内位移 主存块地址用于查找在Cache中的位置，块内位移 用于确定所访问的数据在该块中的位置。 5.2.1 映象规则三种映象规则如图5.4所示。 1. 全相联：主存中的任一块可以被放置到Cache中的任何一个位置的方法。 2. 直接映象：主存中的每一个块只能被放置到Cache中唯一的一个位置。 3. 组相联映象：主存中的每一个块可以被放置到Cache中唯一的一个组中的任一个位置。,13,全相联映象时，主存中的任一块可以放置到Cache 中的任一位置，如图5.4(a)所示，主存中的第9块可 以放入Cac

9、he中的任意一个位置(带阴影)。图示中画 出了Cache大小为8块、主存大小为16块的情况。 直接映象情况下，对于主存的第i块(块地址为i)， 设它映象到Cache中的第j块，则 ji mod (M) 其中，M为Cache的块数。若M2m，则当地址表 示为二进制数时，Cache的块号j实际上就是主存地 址i的m位，如下图所示。 因此，可以直接用主存地址的低m位去选择直接映 象Cache中的相应块。,14, 组相联映象是直接映象和全相联映象的一种折衷： 首先是映象到唯一的一个组上(直接映象的特征)， 然后这个块可以被放入这个组中的任何一个位置(全 相联的特征)。 若主存第i块映象到Cache的第

10、k组，则 ki mod (G) 其中，G为Cache的组数。 设G2g，则当表示为二进制数时，k实际上就是i 的低g位，如图所示。 因此，可以直接用主存块地址的低g位去选择Cache 中的相应组。这里的低g位以及上述直接映象中的低 m位通常称为索引。,15,如果每组中有n个块(n=M/G)，则称该映象规则为 n路组相联。n的值为相联度。直接相联和全相联是 组相联的两种极端情况。表5.2给出了路数n和组数G 的取值。表中M为Cache的块数。下面是一般性分析 1. 相联度越高(即n的值越大)，Cache空间的利用率 越高，块冲突(一个主存块要进入已被占用的Cache 位置)概率越低，因而Cach

11、e的失效率就越低； 2. 全相联的失效率最低，直接相联的失效率最高； 3. 增大n值并不一定使整个计算机系统的性能提高， 而且还会使Cache的实现复杂度和代价增大。 因此，绝大多数计算机都采用直接相联、两路相 联或四路相联。特别是直接相联，采用最多。,16,5.2.2 查找方法 当CPU访问Cache时，有两个问题要解决： (1)当CPU访问Cache时，如何确定Cache中是否有 要访问的块？ (2)若有的话，如何确定其位置？ 这是通过查找目录表来实现的。 Cache中设有一个目录表，该表共有m项，每一项 对应于Cache中的一个块，称为标识(tag)。 在目录表中给每一项设置一个有效位，

12、记录Cache 中相应块所包含的信息有效。一个主存块被调入 Cache中某一个块位置时，它的标识就被填入目录表 中与该Cache块相对应的项中，并且该项的有效位被 置“1”，否则置“0”。,17,根据映象规则不同，一个主存块可能映象到Cache 中的一个或多个Cache块位置。我们称之为候选位置。 当CPU访问该主存块时，必须且只需查找它的候 选位所对应的目录表项(标识)。如果有与所访问的 主存块相同的标识，且其有效值为“1”，则它所对应 的Cache块就是所要找的块。 为了保证速度，对各候选位置的标识的检查比较 应并行进行。直接映象Cache的候选位置只有1个； 全相联Cache的候选位置为

13、m个；n路组相联则介于 两者之间，为n个。一般采用单体多字存储器和比较 器来实现并行查找。n越大，实现查找的机制就越复 杂，代价就越高。 无论是直接映象还是组相联映象，查找时，只需 比较tag。Index无需参加比较。,18,如果Cache的容量不变，提高相联度会增加每一组 中的块数，从而会减少index的位数和增加tag的位数。图5.5给出了4路组相联并行标识比较。 5.2.3 替换算法 当要从主存调入一块到Cache中时，会出现该块所 映象的一组（或一个）Cache块已被占用的情况。这 时，必须强迫腾出其中的某一块，已接纳新调入的 块。腾出哪一块？这就是替换算法所要解决的问题。 直接映象：

14、Cache中的替换很简单，因为只有一个 块可选择；组相联和全相联：Cache中有多个块选择， 替换算法有随机法、FIFO和LRU三种。 评价替换算法的标准：尽可能避免替换马上就要 用到的信息。,19,1. 随机法 随机地选择被替换的块。优点：简单、易于用硬 件实现，且对调试硬件很有帮助。不足：没有考虑 Cache块被使用的情况，反映不了程序的局部性。 2. 先进先出FIFO（First-First-Out） 最先装入相应组的块作为被替换的块。优点：容 易实现。不足：虽然利用了各块进入Cache的顺序这 段“历史”信息，但还是不能正确反映程序的局部性。 因为最先进入的块，很可能是经常要用到的块。

15、 3. 最近最少使用法LRU（Least Recently Used） 选择近期最少被访问的块作为被替换的块。优点： 反映程序的局部性原理，因而其失效在上述三种方 法中是最低的。不足：LRU比较复杂，硬件实现比 较困难，特别是当组的大小增加时，LRU的实现,20,代价会越来越高，而且经常只是近似地实现（选择 最久没有被访问过块作为被替换的块）。 LRU实际上是依据程序局部性原理的一个推论： 如果最近刚用过的块很可能就是马上要再用到的块， 而最久没用过的块就是最佳的被替换者。 表5.3给出了LRU与随机法在失效率方面的比较。,21,表中的数据是对于一个VAX地址流(包括用户程序和 操作系统程序)

16、，块大小为16B的情况下统计的。在 这个例子中，对于大容量Cache，LRU和随机法的失 效率几乎没有什么差别。显然，n越大，Cache容量 越大，时效率越低。此外，表中虽然没有列出，但 是FIFO法的失效率比随机法和LRU都高。 5.2.4 写策略 写需要对存储器和Cache两部分进行操作。 写与读的比较： （1）检查标识并不能与写入Cache块并行进行，“写” 一般比“读”化肥更多的时间。 （2）处理器要写入的数据的宽度不是定长的。(通 常为18字节)，写入时，只能修改Cache块中相应的,22,部分，不能够多修改。而“读”则可以多读出几个字 节也没关系。 Cache与主存内容一致性问题：

17、Cache内容是主存 部分内容的一个副本。“写”访问却可能导致它们内 容的不一致。显然，为了保证正确性，主存的内容 也必须更新。 何时更新主存，是写策略所要解决的问题。写策 略是区分不同Cache设计方案的一个重要标志。写策 略主要有写直达法和写回法两种。 1. 写直达法 该法也称为存直达法。在执行“写”操作中，不仅 把信息写入Cache中相应的块，而且也写入下一级存 储器中相应的块。,23,优点：易于实现。下一级存储器中的数据总是最 新的。这一个优点对于I/O和多处理机是重要的。 问题：写直达法在进行“写”操作的过程中CPU必 须等待，直到“写”操作结束，称为CPU写停顿(write sta

18、ll)。 常用的优化技术：写缓冲器(write buffer)。CPU一 旦把数据写入该缓冲器，就可以继续执行，使下一 级存储器的更新和CPU的执行重叠起来。 2. 写回法(write back) 该法也称为拷回法(copy back)。只把信息写入 Cache中相应的块。该块只有在被替换时，才被写回 主存。为了减少在替换时块的写回，在Cache中的每 一块设置一个“污染位”，用于指出该块是“脏的”，,24,即没被修改过（被修改过）还是干净的（没被修改 过）。替换时，若被替换的块石干净的，则不必写 回下一级存储器。只有被修改过的块写回。 写回法的优点：速度快，“写”操作能以Cache存储 器的

19、速度进行。对于同一单元的多个写只需最后一 次写回下一级存储器。有些“写”只到达Cache，不到 达主存，所使用的存储器频带较低。这使得写回法 对于多处理机很有吸引力。 写访问失效时的内存分配。当发生写失效时，是 否调入相应的块，有两种选择： （1）按写分配法（Write allocate） 写失效时，先把所写单元所在的块调入Cache，然 后再进行写入。与读失效类似，此法也称为写时取。,25,（2）不按写分配法（no-write allocate） 写失效时，直接写入下一级存储器而不将相应的 块调入Cache。这种方法也称为绕写法(write around)。 写回法Cache一般采用按写分配

20、法（这样以后对那 个块的“写”就能被Cache捕获）。 写直达法一般采用不按写分配法（因为以后对那 个块的“写”仍然还要到达下一级存储器）。 5.2.5 Cache的结构 下面以DEC的Alpha AXP 21064为例进一步说明。 该Cache的结构如图5.6所示。容量为8KB，块大 小为32字节，共有256个块；直接相联映象；采用写 直达法，写缓冲的大小为4个块，并且在写失效时不 按写分配。,26,四选一的多路选择器：数据RAM为8各字节宽； 索引加上块内偏移量的高两位作为RAM的地址，就 选取了相应的8个字节，多路选择器仅仅是块内偏移 量高两位的译码示意。 （1）21064读数据Cach

21、e 第一步：地址的分割。 21064微处理器传送给Cache的物理地址为34位。 这个地址被分为两部分：块地址（29位）和块内偏 移地址（5位）。块地址进一步被分为地址标识（21 位）和Cache索引（8位）；索引从256个Cache块中 选择一块，读出数据和标识；标识用于判断要访问 的块是否在Cache中（是否命中）；索引的位数由 Cache容量、块大小、相联度决定。,27,21064的Cache是直接映象的，所以相联度为1，索引 所需的位数满足： 索引的为8位，标识为29-8=21位。 第二步：按索引选择标识 在直接映象的Cache中，读出数据并送往CPU与读 出标识并进行匹配这两个过程可

22、以并行进行。 第三步：标识比较。 标识从Cache中读出来以后，就去和CPU送来的物 理地址中的标识部分进行比较。为了保证标识信息 有效，其相应的有效位必须为“1”，否则比较的结果 就是无效的。,28, 第四步：CPU从Cache中取数据。 如果标识比较的结果匹配，且有效位为“1”，那么 最后一步就是发信号通知CPU从Cache中取走数据。 其它说明：21064完成这4步需要2个时钟周期；如 果这两个周期中均按，指令需要用到本次“读”的结 果，这条指令就只好等待。 （2）21064写数据Cache 写命中：前三步跟上面是一样的。在确定标识比 较为匹配之后，才把数据写入。因为21064使用写直

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

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

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

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

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

28、新访问的情况下。这种失效也 称为碰撞失效(collision)或干扰失效(interference)。,35,表5.5针对三种SPEC92典型程序给出了上述三种 失效所占的比例。可以看出： （1）相联度越高，冲突失效就越少； （2）强制性失效和容量失效不受相联度的影响； （3）强制性失效不受Cache容量的影响，但容量失 效随着容量的增加而减少； （4）表中的数据符合2:1的Cache经验规则，即大小 为N的直接映象Cache的失效率约等于大小为N/2的 两路组相联Cache的失效率。 相联度越高，冲突失效就越少；全相联不会发生 冲突失效。用硬件实现全相联根昂贵，而且可能降 低处理器的时钟频率

29、，导致整体性能的下降。,36,相联失效随着容量的增加而减少，除了增大Cache 以外，没有别的办法。但是它不受相联度的影响。 图5.9是表5.5中数据的图示。表5.6为各块大小情 况下Cache的失效率。降低Cache失效率的7种方法： 增加Cache块大小 提高相联度 设置Cache替换缓冲 伪相联映象 预取技术 由编译器控制的预取 编译器优化 许多降低失效率的方法会增加命中时间(hit time) 或失效开销(miss penalty)。,37,5.3.1 增加Cache块的大小 “U”形曲线：降低失效率最简单的方法是增加块 大小。Cache容量越大，使失效率达到最低的块大小 就越大。如图

30、5.10所示。,38,增加块大小有双重作用： （1）利用了时间局部性，减少了强制性失效； （2）减少Cache中块的数目，所以有可能会增加冲 突失效。在Cache容量较小时，甚至还会增加容量失 效。刚开始增加块大小时，由于块还不是很大，上 述第一种作用超过第二种作用，从而使失效下降。 但到块较大时，第二种作用超过第一种作用，故使 失效率上升。,39,5.3.2 提高相联度 提高相联度会使失效率下降。由此我们得出两条 经验规则： （1）8路组相联在降低失效率方面的作用与全相联 一样有效。也就是说，采用相联度超过8的实际意义 不大。 （2）2:1Cache经验规则：容量为N的直接映象Cache 的

31、失效率和容量为N/2的两路组相联Cache差不多相 同。 改进平均访存时间某一方面是以损失另一方面为 代价的：增加块大小在降低失效率的同时增加失 效开销（原因：块的调入时间加大） 为减少失效 开销，有要求提高相联度提高相联度则是以增加 命中时间为代价的。,40,5.3.3 Victim Cache 一种能减少冲突失效而又不影响时钟频率的方法 是：在Cache中存放因失效而被丢弃（替换）的那些 块(即牺牲Victim)，每当发生失效时，在访问下一级 存储器之前，先检查Victim Cache中是否含有所需的 块，如果有，就将该块与Cache中某个块做交换。 效果：Jouppi发现，含1到5项的V

32、ictim Cache对减 少冲突失效很有效，尤其是对于那些小型的、直接 映象 数据Cache更是如此。对于不同的程序，一个 项数为4的Victim Cache能使一个4KB直接映象数据 Cache的冲突失效减少20%90%。 从Cache的层次来看，Victim Cache可以看成位于 Cache和存储器之间的又一级Cache，采用命中率较 高的全相联映象，容量小，且仅仅在替换时起作用。,41,图5.11描述了Victim Cache在存储层次中的位置。,42,5.3.4 伪相连Cache 伪相联(pseudo-associate)或列相联(column associate)： 既能获得多路

33、组相联Cache的低失效率，又能保持直 接映象Cache的命中速度。 工作过程：采用这种方法时，在命中情况下，访 问Cache的过程和直接映象Cache中的情况相同；而 发生失效时，在访问下一级存储器之前，会先检查 Cache另一个位置，看是否匹配。如果这一块的标识 匹配，则称发生了“伪命中”。否则，就只好访问下 一级存储器。 第二个位置的选择：一种简单的确定另一块位置 的方法是将索引字段的高位取反，然后按照新索引 去寻找“伪相联”中的对应块。,43,如果直接映象Cache里的许多快速命中在伪相联 Cache中变成慢速命中，那么这种优化措施反而会降 低整体性能。解决方案之一：交换两个块的内容：

34、 问题：多种命中时间会使CPU流水线的设计复杂化。 图5.12给出了正常命中时间、伪命中时间和失效 开销之间的关系。,44,采用直接映象和两路组相联时，命中时间相差 2%10%。 一般情况：很高的处理器时钟频率，需要结构简 单的Cache；单时钟频率越高，失效开销越大（时钟 周期数越多）。,45,5.3.5 硬件预取技术 预取技术：预取内容可以直接放入Cache，也可以 放在一个访问速度比主存快的外部缓冲器中。指令 和数据都可以在处理器提出访问请求之前进行预取。 指令预取通常由Cache之外的硬件完成。 工作方式：被请求指令块返回时放入Cache，而预 取指令块则放在缓冲器中；如果某次被请求的

35、指令 块正好在缓冲器里，则取消对该块的访存请求，直 接从缓冲器中读出这一块，同时发出对下一指令块 的预取访存请求。 优点：预取技术、Victim Cache和伪相联都能在不 影响处理器时钟频率的前提下降低时效率。,46,Jouppi的研究结果表明：对于块大小为16B，容 量为4KB的直接映象指令Cache，一个块的指令缓 冲器就可以捕获15%25%的失效，4个块的指令缓 冲器可以捕获大约50%的失效，而16个块的缓冲器 则可以捕获72%的失效。一个数据缓冲器大约可以 捕获4KB直接映象Cache25%的失效。对数据Cache， 可以采用多个数据缓冲器，分别从不同的地址预取 数据。用4个数据缓冲

36、器可以将命中率提高到43%。,47,5.3.6 由编译器控制的预取 基本思想：由编译时加入预取指令，在数据被用 到之前发出预取请求。 预取有以下几种类型： 寄存器预取：把数据取道寄存器中。 Cache预取：只将数据取到Cache中，而不放入寄存器。 故障性预取是指在预取时，若出现虚地址故障或 违反保护权限，则会发生异常。而非故障性预取， 也叫做非绑定预取，在遇到相应情况时则不会发生 异常。 预取指令需要花费一条指令的开销，要注意保证 这种开销不超过预取所带来的收益。,48,5.3.7 编译器优化 通过对软件的优化来降低失效率。 特点：无需对硬件做任何改动就可以降低失效率。 前提：重新组织程序而

37、不影响程序的正确性。 目的：改善数据的空间局部性和时间局部性。 优化的四个例子（四种技术，如图所示）：数组合并、互换循环、循环融合、分块。,49,5.4 减少Cache失效开销 以往对Cache的研究一直把重点放在减少失效次数 上，但是Cache性能公式却告诉我们，家少Cache失 效开销可以跟降低Cache失效率一样带来性能上的提 高。由图5.2可以看出，随着技术的发展，处理器速 度的提高要快于DRAM速度的提高，这使得Cache失 效开销的相对代价随时间不断增加。下面将给出解 决这一问题的5种优化措施。其中最后一种是通过增 加另一级Cache来减少失效开销，这也许是最令人感 兴趣的方法。

38、5.4.1 读失效优先于写 提高写直达Cache性能最重要的方法是使用一个大 小适中的写缓冲器。但是写缓冲器却导致对存储器 的访问复杂化。下面通过例子进一步说明。,50,问题分析：在执行SW指令之后，R3中的数据被放入写缓冲器。接下来的第一条LW指令使用相同的Cache索引，因而产生一次失效。第二条LW指令欲把的值为512的存储单元的值读入寄存器R2中，这也会造成一次失效。如果此时写缓冲器还微将数据写入存储单元512中，那么第二条LW指令将把错误的旧值读入Cache和寄存器R2。如果不采取适当的预防措施，R2的值就不会等于R3的值。,51,解决方法（写直达）：推迟对读失效的处理，直 至写缓冲器

39、清空。 新问题：Cache中有一个大小只有几个字的写缓冲 器在发生读失效时几乎总有数据，这就增加了读失 效的开销。改进方法：读失效时检查写缓冲器的内 容，如果没有冲突而且存储器可访问，就可以继续 处理读失效。 在写回法：假定读失效将替换一个“脏”的存储块。 我们可以不像往常那样先把“脏”块写回存储器，然 后再读存储器，而是先把被替换的“脏”块拷入一个 缓冲器，然后读存储器，最后再写存储器。这样 CPU的“读”访问就能更快地完成。发生读失效时， 处理器既可以采用等待缓冲区清空的方法，也可以 采用检查缓冲区中各字的地址是否有冲突的方法。,52,5.4.2 子块放置技术 子块放置技术把一个Cache

40、块划分成若干个小块， 称之为子块。为每一个子块赋予一位有效位，用于 说明该子块中的数据是否有效。因此，标识匹配并 不意味着这个字一定在Cache中，只有当与该字对应 的有效位也为“1”时才是。失效时只需从下一级存储 器调入一个子块。这样，一个Cache中就有可能有的 子块有效，有的子块无效。显然子块的失效开销小 于完整Cache块的失效开销。子块可以被看成是地址 标识之外的又一级寻址。 图5.15给出了一个例子。显然，使用子块可以减 少标识所占的存储空间。如果图中的有效位都用完 整的标识来替代，标识所占用的空间将大得多。这 正是采用子块放置法的原因。,53,5.4.3 请求字处理技术 当从存储

41、器向CPU调入一块时，块中往往只有一 个字是CPU立即需要的，这个字称为请求字。 请求字处理技术指当CPU所请求的字到达后，不 等整个块都调入Cache，就可把改字发送给CPU病重 新启动CPU。有两种具体的方案： （1）尽早重启动(early restart) 在请求字没有到达时，CPU处于等待状态。一旦 请求字到达，就立即发送给CPU，并启动。 （2）请求字优先(request word first) 调块时，首先向存储器请求CPU所要的请求字， 再从存储器调入该块的其余部分。请求字优先也称 为回绕读取(wrapped fetch)或关键字优先(critical)。,54,5.4.4 非阻

42、塞Cache技术 基本出发点：一个Cache请求失效时可以发出后续 请求。这种“失效下命中”(hit under miss)的优化措施 在Cache失效时，不是完全拒绝CPU的访问，而是能 处理部分访问，从而减少了实际失效开销。这就是 非阻塞(non blocking)Cache或非锁定Cache技术。 如果Cache允许多个失效重叠，即支持“多重失效 下的命中”(hit under multiple miss)和“失效下失效” (miss under miss)，则可进一步减少实际失效开销。 “失效下命中”措施大大增加了Cache控制器的复杂 度，因为这时可能有多个访存同时进行。 理论上可以

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

44、提高影响不大，简单的“一 次失效命中”就可以了，几乎得到了所有的好处。 另外，“失效下命中”方法有一个潜在优点：它不 会影响命中时间，而组相联却会。,56,5.4.5 采用两级Cache 二级Cache技术的着眼点：Cache和主存的接口。 为了克服CPU和主存之间越来越大的性能差距， 使存储器和CPU的性能匹配，我们是应该把Cache做 得更快，还是应该把Cache做得更大？一种答案是： 二者兼顾。通过在原有Cache和存储器之间增加另一 级Cache，构成两级Cache，我们可以把第一级Cache 做得足够小，使其速度和快速CPU的时钟周期相匹 配，而把第二级Cache做得足够大，使它能捕

45、获更多 本来需要到主存去的访问，从而降低实际失效开销。 性能公式用下标L1和L2分别表示第一级和第二级 Cache，则：,57,平均访存时间命中时间L1失效率L1失效开销L1 失效开销L1命中时间L2失效率L2 失效开销L2 所以，平均访存时间命中时间L1失效率L1 （命中时间L2失效率L2 失效开销L2） 二级Cache系统采用以下术语 （1）局部失效率 对于某一级Cache来说，局部失效率 该级Cache的失效次数/到达该级Cache的访存次数 对于第二级Cache来说，就是上面的失效率。 （2）全局失效率 对于某一级Cache来说，全局失效率 该级Cache的失效次数/CPU发出的访存总

46、次数 使用上面公式中的变量，第二级Cache的全局失效率 全局失效率L2失效率L1失效率L2,58,对于第二级Cache，有以下两点结论： （1）在第二级Cache比第一级Cache大得多的情况下， 两级Cache的全局失效率和容量与第二级Cache相同 的单级Cache的失效率非常接近。这时可以利用前面 关于单级Cache的分析和知识。 （2）局部失效率不是衡量第二级Cache的一个好指 标，因为它是第一级Cache失效率的函数，可以通过 改变第一级Cache而使之变化，而且不能全面反映两 级Cache体系的性能。因此，在评价第二级Cache时， 应用全局失效率这个指标。 第二级Cache的

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

48、小的Cache的出现。 图5.17给出了相对执行时间和第二级Cache块大小 的关系。,60,5.5 减少命中时间 命中时间是平均访存时间的三个组成部分之一。 命中时间的重要性在于它影响到处理器的时钟频 率。本节先讨论减少命中时间的通用技术，然后论 述一个适用写命中的优化措施。 5.5.1 容量小、结构简单的Cache 采用容量小而且结构简单的Cache，可以有效地提 高Cache的访存速度。如果Cache容量小得合理，就 可以与处理器做在同一芯片上，避免因芯片外访问 而增加时间开销。一种折衷方案：把Cache的标识放 在片内，而把 Cache的数据存储在片外。保持Cache 结构简单：例如采

49、用直接映象Cache。直接映象Cache的主要优点，是设计者可以让标识检测和数 据传送重叠进行，这样可以有效地减少命中时间。,61,5.5.2 虚拟Cache 问题：在采用虚拟存储器的机器中，每次访存都 必须进行虚地址到实地址变换，即将CPU发出的虚 地址转换为物理地址。 解决方法：在Cache中直接使用虚拟地址。这样的 Cache称为虚拟Cache，而物理Cache则是指那些使用 物理地址的传统Cache。 直接使用虚拟地址访问Cache，在命中时消除了用 于地址转换的时间。 虚拟Cache问题之一：进程切换时，由于新进程的 虚拟地址所指向的空间与原进程的不同，故需要清 空Cache。,62

50、,解决这个问题的一种办法：地址标识中增加一个 进程表示符字段(PID)，这样多个进程的数据是属于 哪个 程序的。进程切换时，仅当某个PID被重用(即 该PID以前已被分配了某个进程，现又把它分配给 另一个进程)时，才需清空Cache。 虚拟Cache没有流行起来的一个原因是操作系统和 用户程序对于同一个物理地址可能采用两种以上不 同形式的虚拟地址来访问，它们可能会导致同一个 数据在虚拟Cache中存在两个副本。另外，I/O通常 使用物理地址，为了与虚拟Cache打交道，需要把物 理地址映象为 虚拟地址。,63,5.5.3 写操作流水化 写命中通常比读命中花费更多的时间，因为在写 入数据之前必须

51、先检测标识，否则就有可能将数据 写到错误的单元中。我们可以通过把写操作流水化 来提高写命中的速度。Alpha APX 21064和其他一些 机器采用了这种技术。 图5.18为对于三种方式，虚地址Cache在不同容量 下的失效率。图5.19为流水化写的硬件组织结构。,64,5.5.4 Cache优化技术小结 上述5.3到5.5节中叙述的减少失效率，失效开销和 命中时间的技术通常会影响平均访存时间公式的其 他组成部分，而且会影响存储层次的复杂性。表5.9 对这些技术作了小结，并估计了它们对复杂性的影 响。表中“+”号表示这一技术改进了相应指标，“-” 号表示它使该指标变差，而空格栏则表示它对该指

52、标无影响。从表中可以看出，没有什么技术能同时 改进两项或三项指标。表中关于复杂性的衡量是主 观化的，0表示最容易，3表示最复杂。,65,5.6 主存 主存是存储层次中紧接着Cache下面的一个层次。 主存是数据输入的目的地，也是数据输出的发源地， 它既被用作满足Cache的请求，也被用作I/O接口。 主存的性能主要用延迟和带宽来衡量。以往，Cache 主要关心的是主存的延迟（它影响Cache的失效开 销），而I/O则主要关心主存的带宽。随着第二级 Cache的广泛使用，主存带宽对于Cache来说也变得 重要了，这是因为第二级Cache的块大小较大的缘故。 实际上，Cache设计者可以通过增加C

53、ache块的大小 来利用高存储带宽。,66,5.6.1 存储器技术 访存时间：从发出读请求到所需的数据到达为止 所须的时间。 存储周期：两次相邻访存请求之间的最小时间间 隔。 DRAM地址复用：这样可将芯片的地址引脚数减 少一半。每次访存时，先发送一半的地址，称为行 选通(row access strobe或RAS)；接着发送另一半地 址，称为列选通(column access store或CAS)。存储 单元被组织成一个按行或按列寻址的矩形阵列。 DRAM的特别要求：刷新。DRAM只用一个晶体 管(其中的电容)来存储一位信息，但读取这一位时， 会破坏其中的信息；电容中的电荷也会随时间流失。,

54、67,为防止信息丢失，存储系统中每个DRAM在一定 的时间窗口(例如8微秒)内，都必须把它的每一行都 访问一遍，这个过程称为刷新。存储控制器中包含 定期刷新DRAM的硬件。刷新时，存储系统是不可 以访问的。DRAM设计者们努力把用于刷新的时间 控制在总时间的5以内。 与DRAM相反，SRAM不需要刷新。SRAM中每 位使用4到6个晶体管构成触发器。SRAM访问时和 存储器没有差别。 DRAM设计的重点是大容量。SRAM设计既关心 速度也关心容量。这是因为这样，SRAM的地址线 不能被复用。当采用同一制造技术工艺时，DRAM 的容量大约是SRAM容量的4到8倍，SRAM的存储 周期比DRAM的快

55、8到16倍，但价格也贵8到16倍。,68,几乎所有自1975年以来售出的计算机的主存都采 用DRAM做成的，而几乎所有的Cache都是SRAM。 不过Cary系列巨型机是个例外，如C-90采用SRAM 作主存。 Amdahl经验规则：为了操持系统平衡，存储容量 应随CPU速度的提高而线性增加。 表5.10给出DRAM的典型时间参数。,69,5.6.2 提高主存性能的存储器组织结构 和减少延迟相比，采用新型的组织结构来提高存 储带宽更容易。Cache可以通过增加Cache块的大小 来利用主存带宽的增加，因为在高带宽的情况下， 块大小增大并不会使失效开销增加多少。 下面以处理Cache失效为例来说

56、明各种存储器组织 结构。假设基本存储器为： 送地址需4个时钟周期； 每个字的访问时间为24个时钟周期； 传送一个字的数据需4个时钟周期。 如果Cache块大小为4个字，则失效开销为： 4(4+24+4)=128个时钟周期 存储器的带宽为每个时钟周期1/8(16/128)字节。,70,图5.21画出了几种提高存储带宽的方案。方案a中 所有部件的宽度都是一个字；方案b采用了宽度较大 的存储器总线和Cache；方案c是多体交叉存储器。,71,采用新型的组织结构提高存储带宽的技术有： 1. 增加存储器的宽度。这是提高存储器带宽的最 简单的方法。 不足之处： （1）它会增加CPU和存储器之间的连接通路（

57、通常 称为存储器总线）的宽度，使其实现代价提高； （2）当主存宽度增加后，用户扩充主存时的最小增 量也增加了相应的倍数； （3）在具有纠错功能的存储器中，实现对一行（一 次可并行读出的数据）中部分数据的写入比较复杂。,72,2. 采用简单的多体交叉存储器 存储系统采用DRAM，把存储芯片组织为多个体 (bank)，并让它们并行工作，从而能一次读或写多 个字(而不是一个字)。 图5.22为4路多体交叉存储器。,存储系统的设计目标：对于顺序访问，每个时钟周期都能从一个存储体中送出一个数据。,73,3. 独立存储体 交叉访问的进一步推广，就能同时进行多个独立 的访存。这时应有多个存储控制器，以允许多

58、个体 (或多组按字交叉的存储体)能独立操作。在这个存 储器中，每个体需要有独立的地址线，而且也许还 需要有独立的数据总线。 图5.23是一个含有独立存储体的示意图。,74,在多体存储器中，非阻塞Cache允许CPU在Cache 失效时继续运行，这就潜在地允许多个Cache失效被 同时处理。这种设计仅在采用多体结构时有意义， 否则多个读操作只能通过一个存储端口进行，所能 得到的好处不大：只能将访存操作和数据传送重叠 进行。采用多体结构的另一个原因，是共享公共存 储器多处理机系统的需求。 独立存储体可以和上述按字交叉的多体结合起来 使用，即将存储器分为若干个独立的存储体，而每 个独立存储体内部又划

59、分为若干个按字交叉方式工 作的体，有时称独立存储体为超体，而称超体内按 字交叉的部分为体。,75,4. 避免存储体冲突 体冲突指的是两个请求要访问同一个体。在传统 的多体交叉结构中，顺序访问被处理得很好，不会 发生体冲突。地址相差奇数值的访问也是如此。问 题是当地址相差为偶数值时，冲突的频度就增加了。 解决该问题的一种方法，是采用许多体去减少体 冲突的次数。这种方法只有在较大规模的机器中才 采用，例如NEC SX/3最多使用了128个体。 体冲突问题既可以用软件方法，也可以用硬件方 法解决。编译器可以通过循环交换优化来避免对同 一个体的访问。更简单的一种方法是让程序员或编 译器来扩展数组的大小，使之不是2的幂，从而强制 使上述地址落在不同的体内。,76,减少体冲突的一种硬件解决方案是使体数为素数！ 采用素数看起来似乎会需要更多的硬件来完成复杂 的计算：上述取模和除法运算。而且这些复杂的计 算会延长每次访存的时