张晨曦全套配套课件计算机系统结构第2版第5章存储系统

《张晨曦全套配套课件计算机系统结构第2版第5章存储系统》由会员分享，可在线阅读，更多相关《张晨曦全套配套课件计算机系统结构第2版第5章存储系统（165页珍藏版）》请在金锄头文库上搜索。

1、第5章 存储系统 张晨曦 刘依 www.A 微信公众号：arch365,5.1 存储系统的基本知识 5.2 Cache基本知识 5.3 降低Cache不命中率 5.4 减少Cache不命中开销 5.5 减少命中时间 5.6 并行主存系统 5.7 虚拟存储器 5.8 实例：AMD Opteron的存储器层次结构,计算机系统结构设计中关键的问题之一 ： 如何以合理的价格，设计容量和速度都满足计 算机系统要求的存储器系统？ 人们对这三个指标的要求 容量大、速度快、价格低 三个要求是相互矛盾的 速度越快，每位价格就越高； 容量越大，每位价格就越低； 容量越大，速度越慢。,5.1 存储系统的基本知识,5

2、.1.1 存储系统的层次结构,5.1 存储系统的基本知识,解决方法：采用多种存储器技术，构成多级存储层次结构。 程序访问的局部性原理：对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。 (局部性原理) 程序访问的局部性包含两个方面 时间局部性：程序马上将要用到的信息很可能就是现在正在使用的信息。 空间局部性：程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的。,5.1 存储系统的基本知识,存储系统的多级层次结构 演示,多级存储层次,5.1 存储系统的基本知识,假设第i个存储器Mi的访问时间为Ti，容量为Si，平均每位价格为Ci，则 访问时间：

3、 T1 C2 Cn 整个存储系统要达到的目标：从CPU来看，该存储系统的速度接近于M1的，而容量和每位价格都接近于Mn的。 存储器越靠近CPU，则CPU对它的访问频度越高，而且最好大多数的访问都能在M1完成。,5.1 存储系统的基本知识,下面仅考虑由M1和M2构成的两级存储层次： M1的参数：S1，T1，C1 M2的参数：S2，T2，C2,5.1.2 存储层次的性能参数,5.1 存储系统的基本知识,存储容量S 一般来说，整个存储系统的容量即是第二级存储器M2的容量，即S=S2。 每位价格C 当S1S2时，CC2。,5.1 存储系统的基本知识,命中率H 和不命中率F 命中率：CPU访问存储系统时

4、，在M1中找到所需信息的概率。 N1 访问M1的次数 N2 访问M2的次数 不命中率 ：F1H,5.1 存储系统的基本知识,平均访问时间TA TA HT1（1H）（T1TM） T1（1H）TM 或 TA T1FTM 分两种情况来考虑CPU的一次访存： 当命中时，访问时间即为T1（命中时间） 当不命中时，情况比较复杂。 不命中时的访问时间为：T2TBT1T1TM TM T2TB 不命中开销TM：从向M2发出访问请求到把整个数据块调入M1中所需的时间。 传送一个信息块所需的时间为TB。,5.1 存储系统的基本知识,三级存储系统 Cache（高速缓冲存储器） 主存储器 磁盘存储器（辅存） 可以看成是

5、由“Cache主存”层次和“主存辅存”层次构成的系统。,5.1.3 三级存储系统,5.1 存储系统的基本知识,从主存的角度来看 “Cache主存”层次：弥补主存速度的不足 “主存辅存”层次： 弥补主存容量的不足 “Cache主存”层次 主存与CPU的速度差距 “Cache - 主存”层次 “主存辅存”层次,5.1 存储系统的基本知识,1980年以来存储器和CPU性能随时间而提高的情况 （以1980年时的性能作为基准）,5.1 存储系统的基本知识,两种存储层次,5.1 存储系统的基本知识,存储层次,CPU对第二级的 访问方式,比较项目,目 的,存储管理实现,访问速度的比值 (第一级和第二级),典

6、型的块(页)大小,不命中时CPU是否切换,“Cache 主存”层次,“主存辅存”层次,为了弥补主存速度的不足,为了弥补主存容量的不足,主要由专用硬件实现,主要由软件实现,几比一,几万比一,几十个字节,几百到几千个字节,可直接访问,均通过第一级,不切换,切换到其他进程,“Cache主存”与“主存辅存”层次的区别,5.1 存储系统的基本知识,当把一个块调入高一层(靠近CPU)存储器时， 可以放在哪些位置上? （映像规则） 当所要访问的块在高一层存储器中时，如何 找到该块? （查找算法） 当发生不命中时，应替换哪一块？ （替换算法） 当进行写访问时，应进行哪些操作? （写策略）,5.1.4 存储层次

7、的四个问题,存储空间分割与地址计算 Cache和主存分块 Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。 主存块地址（块号）用于查找该块在Cache中的位置。 块内位移用于确定所访问的数据在该块中的位置。,5.2 Cache基本知识,5.2.1 基本结构和原理,Cache的基本工作原理示意图,5.2.2 映像规则,全相联映像 全相联：主存中的任一块可以被放置到Cache中的任意一个位置。 举例 对比：阅览室位置 随便坐 特点：空间利用率最高，冲突概率最低，实现最复杂。,5.2 Cache基本知识,5.2 Cache基本知识,5.2 Cache

8、基本知识,直接映像 直接映像：主存中的每一块只能被放置到Cache中唯一的一个位置。 举例 （循环分配） 对比：阅览室位置 只有一个位置可以坐 特点：空间利用率最低，冲突概率最高， 实现最简单。 对于主存的第i 块，若它映像到Cache的第j 块，则: ji mod (M ) （M为Cache的块数）,设M=2m，则当表示为二进制数时，j实际上就是i的低m位:,j,i：,m位,5.2 Cache基本知识,5.2 Cache基本知识,组相联映像 组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。 举例 组相联是直接映像和全相联的一种折中,5.2 Cache基本知识,组的

9、选择常采用位选择算法 若主存第i 块映像到第k 组，则: ki mod（G） （G为Cache的组数） 设G2g，则当表示为二进制数时，k 实际上就是i 的低 g 位: 低g位以及直接映像中的低m位通常称为索引。,k,i：,g位,5.2 Cache基本知识,n 路组相联：每组中有n个块(nM/G )。 n 称为相联度。 相联度越高，Cache空间的利用率就越高，块冲突 概率就越低，不命中率也就越低。 绝大多数计算机的Cache: n 4 想一想：相联度一定是越大越好？,全相联,直接映像,组相联,n (路数),G (组数),M,M,1,1,1nM,1GM,5.2 Cache基本知识,当CPU访问

10、Cache时，如何确定Cache中是否有所要访问的块？ 若有的话，如何确定其位置？ 通过查找目录表来实现 目录表的结构 主存块的块地址的高位部分，称为标识 。 每个主存块能唯一地由其标识来确定,5.2.3 查找算法,5.2 Cache基本知识,只需查找候选位置所对应的目录表项 并行查找与顺序查找 提高性能的重要思想：主候选位置(MRU块) （前瞻执行） 并行查找的实现方法 相联存储器 目录由2g个相联存储区构成，每个相联存储区的大小为n（h+log2n）位。 根据所查找到的组内块地址，从Cache存储体中读出的多个信息字中选一个，发送给CPU。,5.2 Cache基本知识,5.2 Cache基

11、本知识,单体多字存储器比较器 举例： 路组相联并行标识比较 （比较器的个数及位数） 路组相联Cache的查找过程 直接映像Cache的查找过程 优缺点 不必采用相联存储器，而是用按地址访问的存储器来实现。 所需要的硬件为：大小为2g nh位的存储器和n个h位的比较器。 当相联度n增加时，不仅比较器的个数会增加，而且比较器的位数也会增加。,5.2 Cache基本知识,5.2 Cache基本知识,例子：DEC的Alpha AXP21064中的内部数据Cache 简介 容量：8KB 块大小：32B 块数：256 映像方法：直接映像 写缓冲器大小：4个块,5.2.4 Cache的工作过程,结构图,5.

12、2 Cache基本知识,工作过程 “读”访问命中 （完成4步需要2个时钟周期 ） Cache的容量与索引index、相联度、块大小之间的关系 Cache的容量=2index相联度块大小 把容量为8192、相联度为1、块大小为32（字节）代入： 索引index：8位 标识：29821位 “写”访问命中,5.2 Cache基本知识,设置了一个写缓冲器 （提高“写”访问的速度） 按字寻址的，它含有4个块，每块大小为4个字。 当要进行写入操作时，如果写缓冲器不满，那么就把数据和完整的地址写入缓冲器。对CPU而言，本次“写”访问已完成，CPU可以继续往下执行。由写缓冲器负责把该数据写入主存。 在写入缓冲

13、器时，要进行写合并检查。即检查本次写入数据的地址是否与缓冲器内某个有效块的地址匹配。如果匹配，就把新数据与该块合并 。,5.2 Cache基本知识,发生读不命中与写不命中时的操作 读不命中：向CPU发出一个暂停信号，通知它等待，并从下一级存储器中新调入一个数据块（32字节）。 写不命中：将使数据“绕过”Cache，直接写入主存。 对比：Alpha AXP 21264的数据Cache结构 容量：64KB 块大小：64字节 LRU替换策略 主要区别 采用2路组相联 采用写回法 没有写缓冲器,5.2 Cache基本知识,替换算法 所要解决的问题：当新调入一块，而Cache又已被占满时，替换哪一块？

14、直接映像Cache中的替换很简单 因为只有一个块，别无选择。 在组相联和全相联Cache中，则有多个块供选择。 主要的替换算法有三种 随机法 优点：实现简单 先进先出法FIFO,5.2.5 替换算法,5.2 Cache基本知识,最近最少使用法LRU 选择近期最少被访问的块作为被替换的块。 （实现比较困难） 实际上：选择最久没有被访问过的块作为被替换的块。 优点：命中率较高 LRU和随机法分别因其不命中率低和实现简单而被广泛采用。 模拟数据表明，对于容量很大的Cache，LRU和随机法的命中率差别不大。,5.2 Cache基本知识,LRU算法的硬件实现 堆栈法 用一个堆栈来记录组相联Cache的

15、同一组中各块被访问的先后次序。 用堆栈元素的物理位置来反映先后次序 栈底记录的是该组中最早被访问过的块，次栈底记录的是该组中第二个被访问过的块，栈顶记录的是刚访问过的块。 当需要替换时，从栈底得到应该被替换的块（块地址）。,5.2 Cache基本知识,5.2 Cache基本知识,堆栈中的内容必须动态更新 当Cache访问命中时，通过用块地址进行相联查找，在堆栈中找到相应的元素，然后把该元素的上面的所有元素下压一个位置，同时把本次访问的块地址抽出来，从最上面压入栈顶。而该元素下面的所有元素则保持不动。 如果Cache访问不命中，则把本次访问的块地址从最上面压入栈顶，堆栈中所有原来的元素都下移一个

16、位置。如果Cache中该组已经没有空闲块，就要替换一个块。这时从栈底被挤出去的块地址就是需要被替换的块的块地址。,5.2 Cache基本知识,堆栈法所需要的硬件 需要为每一组都设置一个项数与相联度相同的小堆栈，每一项的位数为log2n位。 硬件堆栈所需的功能 相联比较 能全部下移、部分下移和从中间取出一项的功能 速度较低，成本较高（只适用于相联度较小的LRU算法） 比较对法 基本思路 让各块两两组合，构成比较对。每一个比较对用一个触发器的状态来表示它所相关的两个块最近一次被访问的远近次序，再经过门电路就可找到LRU块。,5.2 Cache基本知识,例如：假设有A、B、C三个块，可以组成3对：AB、AC、 BC。每一对中块的访问次序分别用“对触发器”TAB、TAC、TBC表示。 TAB为“1”，表示A比B更近被访问过； TAB为“