《计算机系统结构第3章》由会员分享，可在线阅读，更多相关《计算机系统结构第3章（72页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 存储系统,2,第一节 存储系统设计基本原理,一、存储系统设计目标,1、存储器性能指标,容量：SM=Wlm，其中W为字长、l和m为存储体字数和体数,速度：用访问时间TA、存储周期TM和带宽Bm表示。TA为PE启动访存请求后的等待时间；TM为MEM连续启动访存的间隔时间，TMTA；Bm=Wm/TM。,价格：c=C/SM,性能指标间的矛盾：大容量与高速度矛盾；高速度与低价格矛盾。,3,2、对存储系统的需求高速度、大容量、低价格。,需求带来的问题：只用一种存储器无法解决上述需求；采用几种存储器组合来满足需求，如何组织？,3、访存局部性原理,时间局部性：已被访问的存储项，可能很快被再次访问。
2、,空间局部性：被访问存储项的相邻存储项，可能很快被访问。,访存局部性原理是存储体系设计的基础。,4,4、层次化存储系统,层次结构：用多种类型的存储器组合实现存储器的大容量、高速度和低价格要求。,实现：cici+1，TAiTAi+1，SMiSMi+1。,设计目标：ccn；TTA1。达到目标后，存储系统的容量要求已不是问题。,5,二、存储系统设计原理,1、主要的存储层次,（1）Cache-主存存储层次 -高速缓冲存储器,目标：解决主存的速度不够问题。效果：CPU的速度，主存的容量。,（2）主存-辅存存储层次 -虚拟存储器,目标：解决主存的容量不够问题。效果：主存的速度，辅存的容量。,6,2、性能参
3、数,（1）每位平均价格c,影响因素：c1、c2 、SM1、SM2、各层间辅助开销,（2）命中率HCPU产生的逻辑地址能在M1中访问到的概率。,影响因素：地址流、预判算法、M1的存储粒度和容量等。,（3）平均访问时间TA,TA=HTA1+(1-H)TA2,影响因素：命中率H、各层的访问时间TA1和TA2。,回下页,7,3、层次存储系统总体设计,（1）根据ccn目标设计设计结果：相邻级的容量差SM较大；价格差c(等同于速度差TA)较大；相邻层访问时间比r=TA2/TA1,即r较大层间辅助成本开销较小。,（2）根据TATA1目标设计,访问效率：,设计结果：命中率H很高(e1、r较大)；层间辅助时间开
4、销较小。,转上页,8,4、层次存储系统详细设计需重点解决的问题：如何实现层次结构；如何提高命中率H；如何减少层间辅助开销。,（1）层次结构实现原理层次结构模型：,回下页,9,地址空间CPU使用的是虚拟地址空间，各存储层次有自己的物理空间，均需要进行虚拟地址-物理地址的转换；传统模型节省了转换成本，增加了转换延迟,传输粒度为减少平均访问时间、充分利用访存空间局部性原理，离CPU越远的存储器间传输粒度越大；可分摊每字节传输代价，和提高命中率H,层次存储器结构：组成-存储阵列、控制器、层次辅助机构；,存储粒度一般与传输粒度相同，如Cache为块，MEM为页，按上层粒度与上层通信，按本层粒度与下层通信
5、；,内部地址为存储粒度号+存储粒度内偏移。,转上页,回下页,10,层次存储器处理访问请求的过程：,转上页,回下页,回13页,11,实现的相关问题：,地址映象规则-存储粒度大小数据块从下层调入本层时可放在哪些位置(候选位置)；,转上页,查找方法如何在候选位置查找数据块的内部位置；,地址变换机构如何将外部地址转换成内部地址；,替换算法-发生失效(不命中)且无剩余空间时，替换哪个存储粒度大小的数据块；,更新策略-处理写请求时，何时将数据传递到下层。,（2）提高命中率H的方法在高速缓冲存储器中分析。,（3）减少层间辅助开销的方法可在访问请求处理过程的各个步骤进行优化处理。,12,第二节 高速缓冲存储器
6、,一、基本工作原理 1、组成Cache主要由快速存储阵列、目录表、控制器及层次管理辅助部件等组成。,回下页,13,2、基本工作原理,存储粒度：由一定数量的字构成的数据块，称为块；内部地址：块号+块内地址。,主存Cache层次管理：按Cache块大小将Cache和主存分成若干大小相同的块;传输粒度为Cache的存储粒度(块)；主存块只能存储到Cache中地址映象规则规定的位置；Cache负责保存每个块对应的主存块块号。,CacheCPU层次管理：Cache通过地址映像规则、查找方法、地址变换机构，将(CPU请求的)主存地址转换为Cache内部地址，再按内部地址处理请求；传输粒度为CPU访问请求的
7、数据大小；,转上页,转下页,转10页,14,地址变换失败时，Cache负责调进CPU请求所对应的主存块，Cache中无空闲位置时，根据替换算法先替换出某个块；Cache根据更新策略决定何时将数据写到主存中。,回上页,回29页,回30页,15,二、相关技术,1、地址映像及变换,（1）全相联映像及变换主存地址构成：页号+页内块号+块内偏移；映像：主存任意块可映像到Cache中任意块位置；候选位置：目录表所有行；性能：命中率最高，实现最复杂。,回下页,16,（2）直接映像及变换主存地址构成：区号+区内块号+块内偏移映像：主存任意块只映像到Cache中区内块号对应位置；候选位置：目录表区内块号那一行；
8、性能：命中率最低，实现最简单。,（3）组相联映像及变换 主存地址构成：区号+区内组号+组内块号+块内偏移映像：组内全相联映象，组间直接映象；候选位置：目录表区内组号那一组所有行；性能：命中率较高，实现较简单。-较多采用,转上页,17,2、查找方法为提高查找速度，一般采用并行查找方法。,(1)采用相联存储器进行相联查找,(2)采用单体多字存储器(每行为一个组)进行按地址、快速查找(多个比较器),Cache容量较小时一般用相联查找，否则用快速地址查找。,18,3、替换策略,RAND算法：替换的块由随机数发生器产生，命中率随机。FIFO算法：替换块时只考虑访问的时间次序，未考虑重复访问频率，命中率随
9、机。,LRU算法：即近期最久未使用算法，遵循了访存局部性原理，属堆栈型算法。,例1：分析地址序列为2、11、2、9、7、6、4、3的容量为4块的Cache的LRU替换算法使用情况。,访问次序： 1 2 3 4 5 6 7 8 地址流块号： 2 11 2 9 7 6 4 3 块分配情况：,操作状态： 调进 调进 命中 调进 调进 替换 替换 替换,19,例2：证明LRU算法为堆栈型算法。,设：n为分配给地址流块数，Lt为地址流中相异块数，Bt(n)为t时刻Cache中块号集合，命中率为H(n)。,LRU算法有：Bt(n+1)Bt(n)，即H(n+1)H(n) 。,所以：LRU算法为堆栈型算法。,
10、所有Cache均采用LRU算法。,20,4、更新策略,写策略：全写法(写直达法)CPU写Cache时，Cache同时将数据写到主存；写回法-CPU写Cache时，Cache在块被替换时才将数据写回主存。,写丢失策略：不按写分配法CPU写Cache不命中时，直接将数据写到主存，不将该块调入Cache；按写分配法CPU写Cache不命中时，除直接将数据写到主存外，将该块调入Cache。,配对：全写法采用不按写分配法，写回法采用按写分配法。,连接主存的Cache一般采用写回法+按写分配法。,21,三、Cache性能分析,1、命中率H影响因素：地址映像规则、替换策略、Cache容量、块大小、组大小、地
11、址流等。,地址映像规则：全相联映像时H最高、组相联映像次之；考虑性能/价格，一般采用组相联映像。,替换策略：采用LRU算法时H最佳，故基本均采用LRU算法。,Cache容量：增加容量时H均可提高，但不能仅靠此提高H。,块大小：增加块大小可提高H，固定容量时并非永远如此。,组大小：增加组大小可提高H，固定容量时并非永远如此。,22,2、平均访问时间TATA=HTA1+(1-H)TA2，或TA=命中时间+失效率*失效开销，命中时间包含查找时间影响因素：命中率(失效率)、命中时间、失效开销等。,失效类型：强制(冷启动)失效、容量失效、冲突失效。,强制失效：只与块大小有关；容量失效：只与Cache容量
12、、软件的工作集有关；冲突失效：与地址映像、Cache容量、块大小等有关。,3、改进Cache性能降低失效率；减少失效开销；减少Cache命中时间。,Cache设计参数:空间、块大小、组大小、相关算法实现等。,23,四、降低Cache失效率方法,1、增加Cache块大小测试结果：失效率先下降、后上升；容量越大，最低失效率的块越大。,问题：增加Cache块大小降低失效率以增加失效开销为代价。,块大小的选择：目标同时使失效率和失效开销较小；,从失效率角度考虑选择失效率最小点的一定范围内的块大小作为候选区域(Cache主要性能为TA，非H)；,从失效开销角度考虑与下级存储器延迟和带宽有关，低延迟、高带
13、宽时选择候选区域内较大的块，否则选择候选区域内较小的块。,24,2、提高相联度(组内块数)测试结果：相联度越大，失效率越低；8路组相联与全相联失效率基本一致；容量为N的直接映像的失效率与容量为N/2的2路组相联的失效率相近。,问题：提高相联度降低失效率以增加命中时间为代价；即相联度高的Cache，在不同容量时TA并不一定低。,相联度的选择：目标-失效率、命中时间同时较低(TA最低)；方法采用对测试程序测试方法进行；结果小容量Cache(32K)，相联度越高TA越低，大容量Cache，相联度为4时TA最低。,25,3、Victim Cache,组成：容量较小(一般为15个块)；采用全相联策略。,
14、降低失效率原理：在Cache不命中时，访问Victim Cache，代替访问下级存储器，类似于增加了一级全相联存储器。,减小失效开销原理：访问Cache与访问Victim Cache并行。,测试结果：Cache为4K、Victim Cache为4块时，可减少失效率的20%90%。,回47页,26,4、软硬件支持的预取技术实现机构：硬件预取-一般由Cache之外的硬件完成；软件预取-由编译器利用预取指令完成。,预取信息的存放：少量(4个左右)流式缓冲器(大小为1个块)。,降低失效率原理：在Cache不命中时，访问预取缓冲器；预取利用存储器的空闲频带，不影响正常失效的处理。,软硬件预取的特点：硬件
15、预取预取效率与算法实现延迟、预取有效性相关，需要硬件成本、不需要软件介入；软件预取预取效率较高、无算法延迟，需编译器介入。,27,五、减少Cache失效开销方法,1、实现技术对CPU的请求(命中/失效时)的处理采用等待方式，非程序切换方式，以减少命中时间和失效开销。,2、读失效优先于写,对写直达Cache：-不按写分配零等待写实现增设写缓冲区，MEM带宽空闲时写；应用需求-读失效时所读单元在写缓冲中；减少失效开销原理读失效时检查写缓冲器的内容。,对写回法Cache：-按写分配零等待写实现增设写回缓冲区，MEM带宽空闲时写；应用需求-读失效时所读单元在写回缓冲区中；减少失效开销原理读失效时检查写
16、回缓冲器内容。,28,3、子块放置技术实现原理：将Cache块分成几个子块，每个子块赋予一个有效位，说明该子块中数据是否有效。,减少失效开销原理：失效时只从下级存储器调入一个子块，其余子块利用预取方法调入。,与小块Cache比较：减少了保存多个主存块号的存储空间，增加了相应个有效位。,29,4、请求字处理技术减少失效开销原理：从下级存储器调入块时，一旦CPU所请求的字到达后，立即发送给CPU，让等待的CPU尽早继续执行。(见Cache结构图),应用：只有当块较大时才采用该技术。,转14页,30,5、旁侧式Cache技术贯通式Cache：-传统存储层次结构,特点：失效开销大、不影响命中时间、降低总线使用率。,旁侧式Cache：-优化的存储层次结构,特点：降低失效开销、影响命中时间、没有明显降低总线使用率。(见Cache结构图),
