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

计 算 机 体 系 结 构第五章 存 储 层 次本章要点:• 存储系统• 存储层次• 存储系统的性能参数• Cache存储器工作原理• Cache地址映象与变换算法• Cache替换算法及其实现• Cache写操作1计 算 机 体 系 结 构• Cache系统性能的改进方法• 主存系统• 低位交叉访问存储器• 高位交叉访问存储器• 虚拟存储器工作原理• 段式、页式、段页式存储管理• 虚拟存储器地址映象与变换算法• 页面替换算法及其实现• 缓冲对虚拟存储系统性能的影响• Cache、主存、虚拟存储器的比较2计 算 机 体 系 结 构本章的主要应用问题• Cache性能分析 • 层次存储器性能分析• Cache地址流分析• 虚拟存储器地址流分析• 存储器系统设计 3第五章 存 储 层 次5.1 存储器的层次结构存储器是计算机的核心部件之一，其性能直接关系到整个计算机系统性能的高低存储器的三个主 要指标是：速度、容量和价格(即每位价格)如何以合理的价格，设计容量和速度满足计算机系统需 求的存储器系统，始终是计算机体系结构设计中的 关键问题之一5.1.1 从单级存储器到多级存储器计算机软件设计者和计算机用户总是希望存储器 的容量越大越好，而且速度要快，价格也不能太昂 贵。

而实际情况却是：速度越快，每位价格越高； 容量越大，每位价格越低；容量越大，速度越慢 人们对存储器设计的三个指标要求是互相矛盾的4第五章 存 储 层 次解决问题的办法必须切合实际地综合考虑：从实 现“容量大、价格”的要去来看，应采用能提供大容 量技术的存储器技术；但从满足性能需求的角度来 看，又应采用昂贵且容量较小的快速存储器走出 这种困境的唯一方法，就是采用多种存储技术，构 成存储器的层次结构，如图5.1所示5第五章 存 储 层 次在多级存储层次中，最靠近CPU的M1速度最快、 容量最小、价格最高；而远离CPU的Mn则是速度最慢、容量最大、价格最低存储系统的设计目标是：M1的速度，Mn的容量和价格层次存储器设计的依据：程序局部性原理在层次存储中，靠近CPU的存储器中的数据一般都是其下一层存储器中数据的子集CPU访存时的基本原则：有近及远，首先是访问 M1 ， 若在M1中找不到所要的数据，就要访问M2 ， 将包含所需数据的块或页面调入M1 若在M2中还 找不到，就要访问M3 ，依此类推如果所有层次中都没有，就出现错误6第五章 存 储 层 次5.1.2 存储层次的性能参数研究方法：层次存储器基本问题通过两层存储器结构进行研究。

对于由M1和M2构成的两级存储层次结构，假设 M1、M2的容量、访问时间和每位价格分别为S1、 TA1、C1和S2、TA2、C21. 存储层次的平均每位价格 显然，当S1<

现代计算机都采用Cache来解决这个问题9第五章 存 储 层 次“Cache-主存”层次的工作几乎完全由硬件实现，因此它不但对应用程序员是透明的，而且对系统程 序员几乎也是透明的2. “主存-辅存”层次为了弥补主存容量，在主存外面增加一个容量更 大、每位价格更低、但速度更慢的存储器(称为辅存， 一般是硬盘)它们依靠辅助软硬件的作用，构成 一个整体，如图5.3所示主存-辅存”层次常被用来实现虚拟存储器，向编程人员提供大量的程序空间 3. “Cache-主存”层和“主存-辅存”层的简单比较表5.1对“Cache-主存”层和“主存-辅存”层做了一个简单的比较10第五章 存 储 层 次5.1.4 两级存储层次之间的四个基本问题对于具体存储层次而言，将研究一下四个问题： 1. 当把一个块调入高一层（靠近CPU）存储器时，可以放到哪些位置上？（映象规则） 2. 当要访问的块在高一层存储器时，如何找到该块？（查找算法） 3. 当发生失效时，应替换哪一块？（替换算法） 4. 当进行写访问时，应进行哪些操作？（写策略）5.2 Cache基本知识Cache用于解决上述四个基本问题，即映象规则、查找算法、替换算法以及写策略。

11第五章 存 储 层 次Cache是按块进行管理的，Cache和主存均被分割成 大小不同的块，信息以块为单位调入CacheCPU的访存地址被分割成块地址和块内地址两部分：主存地址： 块地址 块内位移主存块地址用于查找在Cache中的位置，块内位移用于确定所访问的数据在该块中的位置 5.2.1 映象规则三种映象规则如图5.4所示 1. 全相联：主存中的任一块可以被放置到Cache中的任何一个位置的方法 2. 直接映象：主存中的每一个块只能被放置到Cache中唯一的一个位置 3. 组相联映象：主存中的每一个块可以被放置到 Cache中唯一的一个组中的任一个位置12第五章 存 储 层 次全相联映象时，主存中的任一块可以放置到Cache 中的任一位置，如图5.4(a)所示，主存中的第9块可 以放入Cache中的任意一个位置(带阴影)图示中画 出了Cache大小为8块、主存大小为16块的情况 直接映象情况下，对于主存的第i块(块地址为i)， 设它映象到Cache中的第j块，则 j＝i mod (M) 其中，M为Cache的块数若M＝2m，则当地址表 示为二进制数时，Cache的块号j实际上就是主存地 址i的m位，如下图所示。

因此，可以直接用主存地址的低m位去选择直接映 象Cache中的相应块13第五章 存 储 层 次 组相联映象是直接映象和全相联映象的一种折衷 ： 首先是映象到唯一的一个组上(直接映象的特征)， 然后这个块可以被放入这个组中的任何一个位置(全 相联的特征)若主存第i块映象到Cache的第k组，则k＝i mod (G) 其中，G为Cache的组数设G＝2g，则当表示为二进制数时，k实际上就是i 的低g位，如图所示因此，可以直接用主存块地址的低g位去选择Cache 中的相应组这里的低g位以及上述直接映象中的低 m位通常称为索引 14第五章 存 储 层 次如果每组中有n个块(n=M/G)，则称该映象规则为 n路组相联n的值为相联度直接相联和全相联是 组相联的两种极端情况表5.2给出了路数n和组数G 的取值表中M为Cache的块数下面是一般性分析1. 相联度越高(即n的值越大)，Cache空间的利用率 越高，块冲突(一个主存块要进入已被占用的Cache 位置)概率越低，因而Cache的失效率就越低；2. 全相联的失效率最低，直接相联的失效率最高；3. 增大n值并不一定使整个计算机系统的性能提高， 而且还会使Cache的实现复杂度和代价增大。

因此，绝大多数计算机都采用直接相联、两路相联或四路相联特别是直接相联，采用最多15第五章 存 储 层 次5.2.2 查找方法当CPU访问Cache时，有两个问题要解决：(1)当CPU访问Cache时，如何确定Cache中是否有 要访问的块？(2)若有的话，如何确定其位置？ 这是通过查找目录表来实现的Cache中设有一个目录表，该表共有m项，每一项 对应于Cache中的一个块，称为标识(tag)在目录表中给每一项设置一个有效位，记录Cache 中相应块所包含的信息有效一个主存块被调入 Cache中某一个块位置时，它的标识就被填入目录表 中与该Cache块相对应的项中，并且该项的有效位被 置“1”，否则置“0”16第五章 存 储 层 次根据映象规则不同，一个主存块可能映象到Cache 中的一个或多个Cache块位置我们称之为候选位置 当CPU访问该主存块时，必须且只需查找它的候 选位所对应的目录表项(标识)如果有与所访问的 主存块相同的标识，且其有效值为“1”，则它所对应 的Cache块就是所要找的块为了保证速度，对各候选位置的标识的检查比较 应并行进行直接映象Cache的候选位置只有1个； 全相联Cache的候选位置为m个；n路组相联则介于 两者之间，为n个。

一般采用单体多字存储器和比较 器来实现并行查找n越大，实现查找的机制就越复 杂，代价就越高无论是直接映象还是组相联映象，查找时，只需 比较tagIndex无需参加比较17第五章 存 储 层 次如果Cache的容量不变，提高相联度会增加每一组 中的块数，从而会减少index的位数和增加tag的位数 图5.5给出了4路组相联并行标识比较 5.2.3 替换算法当要从主存调入一块到Cache中时，会出现该块所 映象的一组（或一个）Cache块已被占用的情况这时，必须强迫腾出其中的某一块，已接纳新调入的 块腾出哪一块？这就是替换算法所要解决的问题 直接映象：Cache中的替换很简单，因为只有一个 块可选择；组相联和全相联：Cache中有多个块选择， 替换算法有随机法、FIFO和LRU三种评价替换算法的标准：尽可能避免替换马上就要用到的信息18第五章 存 储 层 次1. 随机法随机地选择被替换的块优点：简单、易于用硬 件实现，且对调试硬件很有帮助不足：没有考虑 Cache块被使用的情况，反映不了程序的局部性 2. 先进先出FIFO（First-First-Out）最先装入相应组的块作为被替换的块。

优点：容 易实现不足：虽然利用了各块进入Cache的顺序这 段“历史”信息，但还是不能正确反映程序的局部性 因为最先进入的块，很可能是经常要用到的块 3. 最近最少使用法LRU（Least Recently Used）选择近期最少被访问的块作为被替换的块优点 ： 反映程序的局部性原理，因而其失效在上述三种方 法中是最低的不足：LRU比较复杂，硬件实现比 较困难，特别是当组的大小增加时，LRU的实现19第五章 存 储 层 次代价会越来越高，而且经常只是近似地实现（选择 最久没有被访问过块作为被替换的块）LRU实际上是依据程序局部性原理的一个推论：如果最近刚用过的块很可能就是马上要再用到的块 ， 而最久没用过的块就是最佳的被替换者表5.3给出了LRU与随机法在失效率方面的比较 20第五章 存 储 层 次表中的数据是对于一个VAX地址流(包括用户程序和 操作系统程序)，块大小为16B的情况下统计的在 这个例子中，对于大容量Cache，LRU和随机法的失 效率几乎没有什么差别显然，n越大，Cache容量 越大，时效率越低此外，表中虽然没有列出，但 是FIFO法的失效率比随机法和LRU都高。

5.2.4 写策略写需要对存储器和Cache两部分进行操作写与读的比较： （1）检查标识并不能与写入Cache块并行进行，“写 ” 一般比“读”化肥更多的时间 （2）处理器要写入的数据的宽度不是定长的通 常为1~8字节)，写入时，只。