计算机系统结构.ppt

1、计算机系统结构,主讲 蔡启先,第3章 存储系统,3.1 存储系统原理,3.2 虚拟存储系统,3.3 高速缓冲存储器Cache,第 3 章 存 储 系 统,3.4 三级存储系统,3.7 存储域网络（SAN）,3.5 并行存储器,3.6 RAID系统,本章重点,存储系统原理和层次结构 虚拟存储器的概念、基本结构、地址变换、替换算法 Cache的概念、基本结构、设计与地址变换、替换算法,3.1 存储系统原理,3.1.1 存储系统的概念,3.1.2 存储器的层次结构,一个存储器的性能通常有三个主要参数：容量、价格和速度。 存储器容量SM=Wlm。 其中，W为存储体的字长(单位为位或字节)，l为每个存储

2、体的字数，m为并行工作的存储体个数。,3.1.1 存储系统的概念,存储器的速度可以用访问时间TA、存取周期TM和频宽(也称带宽)Bm来描述。 TA是存储器从接到访存读申请，到信息被读到数据总线上所需的时间。这段时间是处理机在启动访存申请后必须等待的时间。 TM则是连续启动一个存储体所需要的间隔时间，它一般总比TA大。,存储器频宽是存储器可提供的数据传送速率，一般用每秒钟传送的信息位数(或字节数)来衡量，又分最大频宽(或称极限频宽)和实际频宽。 最大频宽Bm是存储器连续访问时能提供的频宽。单体的Bm=W/TM。m个存储体并行工作时可达到的最大频宽Bm=Wm/TM。由于存储器不一定总能连续满负荷地

3、工作，所以，实际频宽往往要低于最大频宽。,存储器的价格可以用总价格C或每位价格c来表示。具有SM位的存储器每位价格c=C/SM。存储器价格包含了存储单元本身及为该存储器操作所必须的外围电路的价格。,计算机系统总希望存储器能在尽可能低的价格下，提供尽量高的速度和尽量大的存储容量。在速度上应尽量和CPU匹配，容量上应尽可能放得下所有系统软件和多个用户软件及其运行时所需的空间。 只用一种存储器无法解决上述高速度、大容量、低价格的要求。 有两个途径，一个是用多种类型的存储器组成具有一定层次的存储系统，组合实现存储器的大容量、高速度和低价格要求，一个是发展并行存储体系，通过并行访存来提高存储器的性能。,

4、存储系统的定义,多个性能各不相同的存储器用硬件或软件方法连接成一个系统。这个系统对应用程序员透明。在应用程序员看来，它是一个存储器，其速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等或接近，单位容量的价格接近最便宜的那个存储器。,设n个存储器M1(T1,S1,C1)、M2(T2,S2,C2)、Mn(Tn,Sn,Cn)构成一个存储器系统， 从外部看： 该存储器的存储周期 Tmin(T1,T2,Tn) 存储器的容量 Smax(S1,S2,Sn) 存储器每位的价格 Cmin(C1,C2,Cn),从外部看 T,S,C,M1 (T1,S1,C1),M2 (T2,S2,C2),Mn (Tn

5、,Sn,Cn),例：两种存储系统,Cache存储系统：由Cache与主存储器构成，目标是提高速度，全部采用硬件调度，对系统程序员透明。 虚拟存储系统：由主存储器与外存储器构成，目标是扩大存储容量，采用软硬件结合方法调度，对应用程序员透明。,对S、C、T的讨论,设M1和M2构成一个存储器，其中： S1C2 T1T2 存储容量 S=S2（选择大容量存储器进行编址） 单位容量的平均价格CC2,3. 访问周期T,1）命中率H：在M1（较高速度存储器）中访问到的概率 设N1、N2分别为访问M1、M2的次数，则 H=N1/(N1+N2) 2) 存储系统的访问周期T T=HT1+(1-H) T2 H为命中率

6、 当H1时，TT1 3) T与T1接近程度用访问效率e表征,e=f(H,T2/T1),说明：要使T接近T1，一是提高命中率，二是两个存储器速度之比不能过大 改进方法： 对虚拟存储器，加大调用块与改进替换算法等 对Cache存储系统，采用多级Cache、加大Cache、预取技术、改进替换算法等,CPU 内部,通用寄存器堆 指令和数据缓冲栈,主存,脱机外存,联机外存,Cache,访 问 速 度 、 每 位 价 格,存 储 容 量,3.1.2 存储器的层次结构,存储层次之间的关系,工作速度：TiCi+1,虚拟存储系统：主存与联机外存共同组成 主存：DRAM，容量小、速度快、价格高 外存：磁盘，容量大

7、、速度慢、价格低 虚拟存储器完成主存-辅存的存储层次工作。 目标：增加快速的存储器容量。 虚拟存储器的建立和管理主要基于软件，因此对系统程序员是不透明的。,3.2 虚拟存储系统,3.2.1 虚拟存储器的工作原理 3.2.2 地址映象及地址变换 3.2.3 页面替换算法 3.2.4 提高主存命中率的方法,3.2 虚拟存储系统,3.2.1 虚拟存储器的工作原理,虚拟存储器的地址空间有三种： 虚地址空间，它是应用程序员编程的地址空间，这个地址空间非常大； 主存地址空间，又称实存地址空间； 辅存地址空间，即磁盘地址空间。,以页式虚存为例 页（Page）：固定大小的块（116KB） 主存分页：实页 虚存

8、分页：虚页 主存地址A 虚地址Av,内部地址变换 U、Pp,外部地址变换（查外页表） U、P外存实地址,联机外存地址,主存页面表,页面替 换算法,I/O通道,启动脱机外存,命中 访问主存,选主存页,页内 地址,主存,未 命 中,未命中,访联机外存,主存页面失效，查内页表,命中,主存未 满，有 空页号,主存 满,主存页号,调入页,被替换页,选页,页式虚存的工作过程,虚地址Av 内部地址变换未命中 外部地址变换查外页表 命中 得到P对应的实地址 无 实页号p、d 查内页表 启动脱机外存 访问主存 有空页号 无空页号 调入主存 替换调入,3.2.2 地址映象及地址变换,地址映像：程序装入时，建立用户

9、虚地址与主存实地址的对应关系，便于取指令。 地址变换：程序运行时，用户虚地址变换为主存实地址(内部地址变换)或辅存地址(外部地址变换) ，便于数据存取。 三种类型的虚存：（1）段式虚拟存储器 （2）页式虚拟存储器 （3）段页式虚拟存储器,1。段式虚拟存储器,基本原理: 按程序内容分段，长度可长可短。 建立段表（段号、段长、段起始地址、段访问方式及标志） 地址映像方法（示意） 地址变换过程（示意） ：,0段,1段,2段,3段,0,1,2,3,段号,8K,16K,9K,30K,起始地址,程序段通过段表与主存中的区域唯一对应 如第i程序段对应段表中段号为i的一行，由起始地址和段长即可找到主存中对应的

10、段。,1K,500,200,200,段长,0 8K 9K 16K 30K,0 1K 0 500 0 200 0 200,程序空间,段表,主存储器,地址映像方法,虚地址U、S、D段表基址寄存器堆 该用户或作业的段表主存实地址,地址变换过程,用户号U,段号S,段内偏移D,6,As,段表基址寄存器,一个用户（一道作业）的段表,多用户虚地址,主存实地址,+,+,U=6,S=3,As,段表有关字段作用： 起始地址、段长：位置保护 访问方式：保护级别 装入位：程序段是否在主存中 标志：是否修改,段式虚存的主要优点： 程序的模块化性能好 便于程序和数据的共享 程序的动态链接和调度比较容易 便于实现信息保护

11、段式虚存的主要缺点： 地址变换费时 主存利用率低 对辅存管理较困难,2。页式虚拟存储器,页：虚实地址空间分为固定大小的块，Page,一般为0.5kB的整数倍，116kB 地址映像方法 地址变换过程：,0页,1页,2页,3页,0,1,2,3,页号,主存页号,程序分页页表映像主存页,地址映像方法,虚地址U、P、D页表基址寄存器堆该用户或作业的页表主存实地址,地址变换过程,用户号U,虚页号P,页内偏移D,Pa,页表基址寄存器,页表,多用户 虚地址Av,实页号p,+,Pa,主存实地址A,页内偏移d,页式虚拟存储器主要优点 主存利用率高 页表简单 地址映象与变换速度快 对辅存管理容易 页式虚拟存储器主要

12、缺点 程序的模块化性能不好 页表很长,3。 段页式虚拟存储器,段页式虚存： 用户虚存采用分段管理，主存采用分页管理 地址映像方法 程序分段、页查段表查该段页表主存页,页表地址,程序分段、页查段表查该段页表主存页,段页式虚存地址映像方法,0段(12K),1段(10K),2段(5K),用户程序,页表地址,3,3,2,0段0页,0段1页,0段2页,段表,0段页表,1段0页,1段1页,1段2页,1段页表,2段0页,2段1页,2段页表,主存,地址变换： 多用户虚地址：用户号U，段号S，虚页号P，页内偏移D 段表基址寄存器 该用户或作业的段表 该用户或作业的页表 主存实地址：实页号p，页内偏移d,多用户虚

13、地址U、S、P、D段表基址寄存器 该用户或作业的段表相应的页表主存实地址,段页式虚存地址变换过程,用户号U,段号S,页内偏移D,段表基址寄存器,多用户页表,多用户虚地址,+,+,主存地址A,As,虚页号P,As,多用户段表,页内偏移d,实页号p,Ap,段页式虚拟存储器主要优点 程序的模块化较好 主存利用率高 对辅存管理容易 段页式虚拟存储器主要缺点 访主3次：访段表页表各1次，再访主存实地址，查表速度有待改进,4. 内部地址变换方法的改进,（1）虚存速度降低的原因 多次访主（多次查表） 页表或段表容量超过一个页面大小时，相加求地址方法不成立,（2） 减小页表的解决办法：,多级页表：树型结构的多

14、级页表,页表基地 址寄存器,第1级页表,第2级页表,设虚存空间Nv，页大小Np，页表存储字大小Nd，则页表级数g： 如：设虚拟存储空间Nv=4GB，页面大小Np=1KB，页表存储字大小Nd=4B，则： 做法：一级页表驻内存，二级相关页表调入内存，其它放外存,（3）加快查表的方法,1）目录表 压缩页表的存储容量，页表只含有已经在主存的虚页号，以便用Cache存放页表,虚地址U、P拼接目录表实页号主存实地址,采用目录表的地址变换过程,用户号U,虚页号P,页内偏移D,目录表（按内容访问的相联存储器）,多用户 虚地址Av,实页号p,相联访问,主存实地址A,页内偏移d,2）快慢表 U、P拼接的快表在Ca

15、che中，采用与目录表相同的相联方式访问，慢表（页表）在主存储器中。快、慢表同时查。若快表找到则终止慢表查询，否则访问慢表。 3）散列函数 把多用户虚页号Pv变成快表地址Ah Ah=H(Pv) 若发生散列冲突，则查慢表,5。 外部地址变换,1）外部地址变换：在内部地址变换未命中时（即发生页面失效），找到辅存实地址，把所需页或段调入主存中 2）严重页面失效故障及其解决： 严重页面失效故障：在指令跨页、执指跨页时可能发生，作为异常故障处理 处理关键：保存和恢复故障点的现场 3种方法： 硬件缓冲寄存器：保存现场，处理后完整恢复 保存部分现场：处理后，再从头执行未完成的指令 指令预判技术：经预判，事先

16、做好页面失效处理,3）磁盘存储器的格式 4）外部地址变换过程 用软件实现，以页式为例 用户号U外页表始地址 虚页号P外页表记录（存储字） 装入位为1可得磁盘实地址 装入位为0须将脱机外存调入 可采用多级页表技术 若无需脱机外存装入，则内页表和外页表可合二为一,用户号U外页表始地址，虚页号P外页表记录（存储字）,外部地址变换过程,用户号U,虚页号P,页内偏移D,外部地址变换 （用软件实现）,外页表,多用户 虚地址Av,磁盘实地址,找到该用户程序 的外页表首址,找到与该页对 应的存储字,装入位为1可得磁盘实地址，装入位为0须将脱机外存调入,3.2.3 页面替换算法,页面替换要解决的问题： 由于虚拟

17、存储空间的页数大大多于主存空间的页数，一般主存空间必然全占用，因此当发生页面失效时，必须从辅存中调入新页替换主存中不常用的页。 评价页面替换算法的主要标准： 命中率高 算法容易实现,1。页面替换算法,常用的页面替换算法 1）随机算法RAND（random algorithm）： 由随即函数决定替换页，最简单，但命中率低 2）先进先出算法FIFO（first-in first-out algorithm）： 替换最先调入的页，容易实现，但未反映程序的局部性,3）近期最少使用算法LRU（least recently used algorithm）： 选择近期最少使用的页进行替换，算法能比较正确地反

18、映程序的局部性。最初为每页设一个计数器，定时计数，调换时选计数时间最长的页替换，实现较复杂，且计数器字长很长，占空间。实际用到的LRU算法简化了计数方式，实现时在页表或目录表中对每一页增设一个“使用次数”计数器字段，某页调入时，该字段清0。这一页被访问一次，该页的计数器字段加1。计数值最小也即访问次数最少的页就是替换页，LRU算法较合理，也较易实现，被广泛采用。 4）最优替换算法OPT（optional replacement algorithm）： 理想算法，常用于做替换算法比较基准,例3.1 设某一道程序有15个虚页，程序执行时的访存的页地址流为：P1-P2-P1-P5-P4-P1-P3-

19、P4-P2- P4。若主存页面数为3，请分别采用FIFO、LRU、OPT算法说明对这3页的使用和替换过程，并分别算出命中率。,例4.3 FIFO、LFU、OPT算法比较,程序执行的页地址流： P1-P2-P1-P5-P4-P1-P3-P4-P2-P4 主存页面数为3 LFU算法的命中率接近OPT算法，说明算法较好,解：分别采用FIFO、LRU、OPT算法对主存3页的使用和替换过程如图3-12所示。其中用“*”号标记的虚页是由该替换算法确定的被替换页，“入”、“换”、“中”分别表示页的调入、替换和命中情况。该程序访存共10次，各算法的命中率如下： FIFO法：H=2/10=0.2 LRU法：H=

20、4/10=0.4 OPT法：H=5/10=0.5 比较可知，LRU算法的命中率接近OPT算法，说明算法较好。,2。堆栈型替换算法,定义：对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有mn。如果在任何时刻t，主存页面数集合都满足关系： 则这类算法称为堆栈型替换算法 特点：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降 LFU、LRU、OPT算法都是堆栈型算法 FIFO算法不是堆栈型算法,例3.2 设某一道程序有15个虚页，程序执行时的访存的页地址流为：1，2，3，4，1，2，5，1，2，3，4，5。求出分配给该程序的主存页面数分别为3页和

21、4页时的使用和替换过程，请分别采用FIFO、LRU、OPT算法进行对比说明。,例4.3 FIFO、LFU、OPT算法比较,程序执行的页地址流： P1-P2-P1-P5-P4-P1-P3-P4-P2-P4 主存页面数为3 LFU算法的命中率接近OPT算法，说明算法较好,例4.3 FIFO、LFU、OPT算法比较,程序执行的页地址流： P1-P2-P1-P5-P4-P1-P3-P4-P2-P4 主存页面数为3 LFU算法的命中率接近OPT算法，说明算法较好,解：分别采用FIFO、LRU、OPT算法对主存3页的使用和替换过程如图3-13所示。将主存页面数由3页改为4页，仍然采用3种算法分别对主存4页

22、使用和替换，如图3-14所示。比较二图，可知随着主存页数由3页增加到4页，LRU、OPT算法的命中率增加了，而FIFO算法的命中率不增加反而减少了。可见LRU、OPT替换算法属于堆栈型替换算法，而FIFO算法不是堆栈型替换算法。,3.2.4 提高主存命中率的方法,为何要提高主存命中率？ 对公式 T=HT1+(1-H)T2 分析，必须提高H 影响主存命中率的主要因素 程序执行中的页地址流分布 所采用的页面替换算法 页面大小 主存容量 所采用的页面调度方法,（1）页面大小的选择 页面大小Sp与主存容量S、命中率H的关系曲线。 主存大，命中率高 页面大小应适当,H 1,2S,S,Sp,（2）主存容量

23、 主存容量S增加到一定程度，命中率H提高变缓。,H 1,S,（3）页面调度方式 分页式： 整个程序链接装入主存后才运行，命中率100%，但主存利用率低，程序长度必须小于主存安排空间 请求页式： 发生页面失效时，才进行页面调换 预取式调度 预先调入相关页面，防止程序挂起后重新运行时频繁调入页面,一种动态页面调度方法：页面失效频率法PFF(Page Fault Frequency)： 动态给每个程序分配主存页面数。命中率低于某个限定值，则增加分配页面数，否则减少分配的主存页面数。使命中率和主存利用率都能提高。,3.3 高速缓冲存储器Cache,问题的提出： CPU与主存速度相差100倍左右 采用的

24、解决办法 CPU中设计寄存器堆，缓解访存压力 先行缓冲存储器，速度差缩小30倍 采用Cache存储系统,Cache与虚存的比较,3.3 高速缓冲存储器Cache,3.3.1 基本工作原理,3.3.2 Cache的一致性及性能分析,3.3.3 11种先进的Cache性能优化方法,3.3.1 基本工作原理,主存与Cache之间以块为单位进行数据交换 主存地址： Cache地址：,地址变换过程,Bb,命中？,CPU,访存,调入Cache,替换,Cache,Cache满？,Y,N,Y,N,1。 地址映象与变换方法,地址映像：把主存地址空间映像到Cache地址空间，即建立主存地址与Cache地址的对应关

25、系，以便程序装入Cache 地址变换：程序装入Cache后，运行中如何将主存地址变换成Cache地址 （1）全相连映象及其变换 （2）直接映象及其变换 （3）组相连映象及其变换 （4）位选择组相连映象及其变换（略） （5）段相连映象及其变换（略）,（1）全相连映象及其变换,任意B可映象到任意b，映象关系共有CbMb种。,查目录表： 命中，以b访问Cache；未命中，以主存地址访存，备份装入Cache,全相联地址变换,块号B,块内地址W,目录表（由相联存储器构成，共Cb个字）,主存地址,块号b,相联比较,Cache地址,块内地址w,查到相等 的块号,有效位 为1表示 映像有效,全相联映象及其变换

26、 优点：块冲突率最小 缺点：相联比较费时 （为虚存采用）,（2）直接映象及其变换,直接映象： 主存中1块只映象到Cache的特定块中 b=B mod Cb Mb应是Cb的整数倍。 主存分区：Me=Cb，分区中的块号Be与Cache中的块号b相同 主存地址： Cache地址：,直接相联映象方式,区0,区1,区Me-1,直接相联地址变换,块号B,块内地址W,区表存储器（共Cb个字）,主存地址,块号b,相等,Cache地址,块内地址w,区号E,相等比较,块失效,访问Cache,若相等且有效位为1，即 命中，以Cache地址访问Cache；读出数据送往CPU。,以块号B访问区表，读出区号进行比较,不等

27、,（3）组相联映象及其变换,组相联映象：主存、Cache分组，每组块数同。 主存组对Cache组直接映像，组内全相联映像 地址变换过程： 主存地址： Cache地址：,组相联映像方式地址变换,组内块号B,块内地址W,块表,主存地址,组内块号b,相等,Cache地址,块内地址w,组号G,相联比较,块失效,若相等即 命中，以g,b,w组成Cache地址访问Cache；读出数据送往CPU。,以组号B访问块表，读出一组字与E,B进行比较,不等,区号E,组号g,加快访问的方法： Cache地址变换与访Cache并行 多块同时比较 优缺点介于直接映象和全相联映像之间 当每组块容量Gb为1时，成直接映像方式

28、 当每组块容量Gb与Cache的块容量Cb相等时，成全相联映像方式。 一般， Gb越大，块的冲突概率和块失效率越低，但组内映像关系就越复杂，实现成本越高。应注意合理分配组的块容量,2。 Cache替换算法,直接映像方式实际上不需替换算法 全相联映像替换算法最复杂 在组相联和位选择组相联映象及地址变换方式中要考虑替换算法 Cache替换算法用硬件实现。 两种基于LRU算法的全硬实现方法： （1）比较对法 （2）堆栈法,比较对法,LRU算法实际上要把同一组内的各个块按照被访问过的时间顺序排序，从而找出最久没有被访问的块。一个两态的器件（如RS触发器）能够记录上两块之间的先后顺序，多个块之间的先后顺

29、序可用多个两态器件的组合来实现。 以三个块 (分别命名为A、B、C块)为例。设TAB表示B块比A块更久没有被使用过，其它类似。则A、B、C三块共有6种排列：,比较对法,如果访问过的次序为A B C，A为最近访问过的块，C为最久未被访问过的块，则此时必有TAB=1, TAC=1, TBC=1。 因此以最久未被访问过的块C作为被替换掉的块的话，用布尔代数式必有 同理，,当每组的块数达到8个时，需要的触发器个数为28个，与门的输入端个数为7，硬件成本增大，可采用分级办法解决，但同时要考虑分级带来的迟延。 比较法的特点是 用LRU法块失效率比较低； 全硬件工作速度比较高； 当每组块数较多时，硬件实现相

30、对复杂，需要很多的触发器。,堆栈法,堆栈法用栈顶至栈底的先后次序来记录Cache同一组内的各个块被访问的先后顺序。栈顶是最近访问过的，栈底是最久没有被访问过的。替换时，从栈顶压入新的块，而栈底的块自然就被挤出。该方法有自己的管理规则，并不与FIFO法相同。,堆栈法管理规则 把本次访问的块号与堆栈中保存的所有块号进行相联比较，如发现有相等的，则表示命中。其压入方式如图3-25所示，并非压到栈底。 如果相联比较没有发现相等，则Cache块失效。这时，从栈顶压入将栈底挤出。 这样，栈底永远保存着最久没有被访问过的块号，也即下次要被替换的块号。 堆栈法的特点是 用LRU法命中率较高； 硬件实现相对简单

31、； 由于逐级下压，速度相对较慢。,3.3.2 Cache的一致性及性能分析,1。Cache的一致性 2。Cache的取算法 3。Cache的性能分析,1。Cache的一致性,问题的提出 对Cache块的修改，未及时更新相应主存块 解决办法：选择合适的Cache更新算法 （1）写回法（write back） 指写Cache时不写主存，而当Cache数据被替换出去时，才写回主存。采用写回法，Cache块表中一般要设一个“修改位”。一旦块被修改，该块的修改位就被置1，否则保持为0。这样替换该块时，若修改位是1，则必须把该块写回主存，并更新主存中的原块。若修改位是0，则不必写回，直接调入新块。,（2）

32、写直达法（write through） 即写操作时将数据既写入Cache同时又写入主存。 写回法若不发生块失效，速度比写直达法要快；CPU对Cache中的一个数据块的多次写操作只需一次写入主存，减少了主存的写操作次数。但Cache中的数据在未替换时，可能与主存中的相应数据不一致，可靠性不如写直达法。同时，CPU如果读Cache发生块失效的话，将引起数据块的写回操作。 采用写直达法，Cache块表中无需设“修改位”，块替换时，无需把被替换块写回主存，因此写直达法比写回法简单，控制容易；但是写直达法的硬件代价高，因为为了节省同时写主存的时间，通常要增设一个高速小容量的缓冲存储器来暂存写主存的数据和

33、地址。,当出现写Cache不命中时，是否要把包括所写字在内的一个块从主存读入Cache问题，有按写分配法和不按写分配法等两种处理方法。 按写分配法是指发生写Cache不命中时，先把所要写的字写入主存，再把包括所写字在内的一个块从主存读入Cache，此法可以提高Cache的命中率。 不按写分配法则在写Cache不命中时，只把所要写的字写入主存，而不把包括所写字在内的一个块读入Cache，此法可简化Cache结构，省掉了将数据块读入Cache的操作。 一般在写回法中采用按写分配法，在写直达法中为了减少同时写主存的开销而采用不按写分配法。,采用写直达法还是写回法与系统应用有关。 单处理机系统多数采用

34、写回法以节省成本， 共享主存的多处理机系统为保证各处理机经主存交换信息时不出错，多采用写直达法。,2。Cache的取算法,基本的Cache取算法是按需取。即在访问Cache不命中时，根据访问的局部性原理，把包括所访问的字在内的一个块从主存读入Cache。如果进一步采用某种预取算法就能较大地提高Cache命中率。具体算法有2种。 （1）恒预取。当CPU访问Cache时，无论是否命中，都把紧接着访问字所在块的下一块从主存读入Cache。 （2）不命中预取。仅仅在Cache不命中时，才把访问字所在块及其邻接的下一块从主存读入Cache。,影响预取法效果的因素： （1）块的大小。每块的字节数最好不超过

35、256。 （2）预取开销。要预取就要有访主存开销和将它取进Cache的访Cache开销，还要加上把被替换块写回主存的开销。 模拟结果表明，恒预取法使不命中率降低75%80%，而不命中预取法使不命中率降低30%40%。但前者所引起的Cache、主存间传输量的增加要比后者大得多。,3. Cache系统的性能分析,（1）Cache系统的加速比 设 Cache的等效访问周期T， Cache访问周期Tc，主存访问周期Tm T=HTc+(1-H)Tm Cache系统的加速比 Sp=Tm/T =1/(1-H)+HTc/Tm)=f(H,Tm/Tc) 对Sp的分析：Tm、Tc由器件决定，最有效的途径是提高H,一

36、般H0.9，达0.99以上，Sp接近Tm/Tc,Cache的加速比Sp与命中率H的关系,影响Cache命中率的因素分析,影响Cache命中率的因素 程序执行过程中的地址流分布 替换算法 Cache容量 组相联映象方式中块的大小和分组数目 Cache预取算法,1）Cache命中率与容量的关系,关系曲线近似为H=1-S-0.5 S达到一定程度后，H提高很少,Cache命中率H与容量S的关系,2） Cache命中率与块大小的关系,存在最佳块大小，H达到最大,初始,最佳,3）Cache命中率与组数的关系 组数增加（512），H降低明显,3.3.3 11种先进的Cache性能优化方法,可从三个方面来优化

37、Cache性能，即减少命中时的访问时间（简称命中时间）、降低缺失率（不命中率）和减小缺失代价（即不命中时付出的开销），总结了11种先进的Cache性能优化方法,1小而简单的Cache减少命中时间 现代计算机中，一级Cache应尽可能小，这样块表小，查表速度快；同时也应使二级Cache尽可能小，使之能与CPU处于同一芯片内，避免片外时间代价。在快速时钟频率下，通过动态执行隐藏一级Cache缺失和使用二级Cache来避免直接访问主存。 2路预测(way predicting)减少命中时间 路预测要求Cache块中预留一个块预测位，用来预测下一次访问Cache时可能用到的方式或块，以便提前使用多路选

38、择器来选择所需的块。若预测正确，则有最快的命中时间，若失败，将选择其它的块。模拟表明对于2路组相联来说，组预测的精度有85%。Pentium 4使用了路预测技术。,3踪迹Cache（trace cache）减少命中时间 在指令级并行的情况下，踪迹Cache的应用为转移预测提供了方便。踪迹Cache更好地利用了指令Cache中的长块，在它的块中包含了对已执行指令的动态跟踪信息，而不是在存储器中的静态指令序列。Pentium 4采用了踪迹Cache，并使用译码微操作，节省了译码时间。但是踪迹Cache成本较高，硬件复杂，其它处理器几乎没有用到它。 4流水线Cache访问 此方法将流水线、Cache

39、访问、使一级Cache命中时的有效时延分散到几个时钟周期。它提供了较短的周期和高带宽，但是命中时间长。若流水线产生阻塞，可能有更多的时钟周期代价。,5利用非阻塞Cache（lockup-free cache）增加Cache带宽 对于允许乱序执行的流水线机器（见第5章）来说，处理器是不需用在Cache缺失时停顿的。比如处理器在等待数据Cache返回数据的同时，可以继续从指令Cache中取指令。非阻塞Cache在缺失时继续保持Cache命中，减少了缺失代价。如果Cache能重叠多个缺失，则会进一步降低缺失代价，实现“多重缺失仍命中”或“缺失时仍缺失”。通常，乱序执行的处理器若能在二级Cache中命

40、中，则能隐藏一级Cache所产生的缺失代价。 6利用多组Cache增加Cache带宽 此法类似对存储器的并行存取，将Cache分为若干个独立的存储体以支持并发访问，增加Cache带宽。如AMD Opteron的二级Cache有2个存储体，Sun的Niagara有4个存储体。,7关键字优先和提前重启动以减小缺失代价 此技术来源于经验数据：处理器在同一时刻只需要块中的一个字，因此不必等到全部块装入就将所需字送出，然后重新启动处理器访问。具体有两种策略： （1）关键字优先。首先向主存请求缺失的字，一旦它到达即送处理器，使得处理器在装入其它字的同时能够继续执行。 （2）提前重启动。以正常顺序获取字，块

41、中所需字一旦到达即送处理器，使得处理器在装入其它字的同时能够继续执行。 一般上述技术只适用于较大Cache块的情况。因为在填充剩余块的时候，Cache还会继续支持其它块的访问。,8合并写缓冲区（merging write buffers）以降低缺失代价 采用写直达法的Cache要有一个写缓冲区，写回法Cache在替换块时也要用到一个简单的写缓冲区。如果写缓冲区为空，可将被替换掉的数据和地址放到写缓冲区中，写操作即结束，写缓冲区准备将数据写回存储器时，处理器可继续工作。如果写缓冲区里还有其它修改过的数据，应检查新数据的地址是否与写缓冲区中的某一合法项数据地址相匹配。若匹配，新数据就合并到该项中，

42、这就是写合并。此法可一次写多个字，并减少了因写缓冲区已满而产生的访Cache停顿。,9编译器优化以降低缺失率 此法试图采用软件方法来优化Cache性能。在编译器中设法在不影响程序正确性的前提下进行程序代码和数据重组，以改善空间局部性。 10指令和数据硬件预取以降低缺失代价或缺失率 将Cache的预取算法发展到多个流缓冲区中。例如Pentium 4能从8个分别来自不同的4KB页面的流中，预取数据到二级Cache。,11编译控制预取降低缺失代价或缺失率 此法利用编译器来插入预取指令，提前发出数据请求。有寄存器预取（把数据与渠道寄存器中）和Cache预取（只把数据预取到Cache中）两种方式。目前大

43、多数处理器采用非故障性Cache预取技术。当然编译控制预取的目的是使指令执行和预取数据能够重叠进行，循环程序就很适宜预取优化。 然而生成预取指令会带来指令的开销，因此应谨慎使用以保证开销在可接受的范围内。,Cache-主存-磁盘三级存储系统 组织方式 1）两个存储系统组织方式 Cache-主存存储系统和主存-磁盘存储系统,CPU,MMU,Cache,主存储器,数据或指令,数据或指令,虚拟地址,物理地址,物理地址,存储管理部件，能将虚拟地址变换为主存物理地址,若未命中Cache，则访问主存,块替换,3.4 三级存储系统,2）一个存储系统组织方式 Cache-主存-磁盘存储系统,CPU,MMU,C

44、ache,主存储器,3）全Cache系统 Cache-磁盘存储系统 （无主存储器） 在嵌入式系统中较多应用。,3.5 并行存储器,3.5.1 存储器的频带平衡,3.5.2 并行存储器,3.5.1 存储器的频带平衡,计算机运行中至少有4种访问源，即访存取指令、访存取操作数、访存写结果，I/O设备也要与主存交换数据。 如何让存储器访问速度跟得上系统的需要，一直是设计者关注的问题。现代计算机普遍采用指令并行技术，对存储器的频带宽度提出了更高的要求。 存储器的频带：访问源对存储器访问的速度，用MW/S（百万字每秒）或MB/S （百万字节每秒）表示 存储器频带宽度的计算：各访问源的频带之和 存储器的频带

45、平衡：存储器速度与系统需要相适应,3.5.1 存储器的频带平衡,例如，设一台计算机的执行速度为200MIPs(2亿指令/秒)，要求： CPU取指令速度为200MW/S（设每条指令的长度为一个字)； CPU取/存操作数速度为400MW /S（平均每条指令访问周期2 个操作数）； 各种I/O设备访问存贮器速度为5MW /S； 可求得存贮器的总频宽应为605MW /S，即要求访存周期T16.5ns。目前DRAM的访存周期是达不到这一要求的。,解决存储器频带平衡的三条途径： 并行存储器 缓冲存储器 Cache存储系统,3.5.2 并行存储器,并行存储器：多个独立的存储器并行工作，同一存储周期内可访问多

46、个数据。 有三种并行存储器： 1 单体多字并行存储器 2 交叉访问存储器 3 无冲突访问存储器,1 单体多字并行存储器,原理：增加存储器字长，实现同时读写多个字 原mw字 改为 m/n nw字 m：存储单元数，w：字长 访问方法：地址码高位访问存储单元，低位控制多路选择器选择其中数据,一般存储器访问,设存储器为1MB，每字8位 即220字8位 数据寄存器MBR为8位 地址寄存器MAR为20位,单体多字并行存储器访问,设存储器为1MB， 每字64位 即 220/8字88位 = 217字64位 数据寄存器MBR 为8个字节 地址寄存器MAR 若仍为20位，则 MAR高17位选字 MAR低3位控制多

47、路选择器8中选1,并行访问寄存器分析,主要优点：简单容易 主要缺点：访问的冲突大 取指令冲突（例如转移时同时读出的指令，后面的指令将可能无用）：概率小 读操作数冲突（同时读出的数据不一定都有用）：概率大 写数据冲突。（只写1个或2个字节时需读出再写入，需专门控制） 读写冲突（读写同一个存储字内的内容无法在同一周期内完成，需专门控制） 原因：只有一套地址寄存器和控制逻辑,如果每个存储体都有独立的地址 寄存器和控制逻辑，即由多个存 储体组成存储器，显然，没有写 数据冲突和读写冲突，其它冲突 也会缓解。这时，对存储器的访 问通常采用交叉方式。,2 交叉访问存储器,主存储器由多个模块构成。 假设主存储

48、器包含m=2a个存储器模块，每个模块包含w=2b个存储单元（字），则总存储容量为 字地址位数为a+b,两种组织方式 交叉访问的存储器可以分为两种： (1)高位交叉方式 (2)低位交叉方式,1）高位交叉访问存储器 存储器地址的高a位作为存储器模块地址，邻接的存储器单元被分配在同一个存储器模块中，在每个存储器周期内，只能对各模块存取一个字。所以不支持邻接单元的成块存取。 高位n路交叉存取如下图：,各个存储模块有独立的控制部件，地址码高位指示存储体号，地址码低位是各存储体的体内地址（高位译码选体） 设：m:存储体容量 n: 存储体个数 j: 体内地址 0m-1 k: 存储体体号 0n-1 存储单元地

49、址 A=mk+j 若已知A，则存储体体内地址： Aj=A mod m 存储体体号： 对多任务多用户，可提高访问速度，对单任务可扩大容量,向下取整,2) 低位交叉访问存储器 存储器地址的低a位用来指明存储器模块，高b位是每个模块内的字地址。 低位n路交叉存取如下图：,字地址译码器,各个存储模块有独立的控制部件，地址码低位指示存储体号，地址码高位是各存储体的体内地址（低位译码选体） 存储单元地址：A=nj+k 存储体体内地址： 存储体体号：Ak=A mod n,向下取整,如8路交叉，n=8，m=8，a=b=3， 8路低位交叉存取如下图：,分时启动，启动间隔 Tm：存储体访问周期 低位交叉以流水线方

50、式支持成块存取,低位交叉流水线方式示意图：,时间,Tm为主周期，t= Tm/n为小周期，n为交叉存取度,低位交叉访问有可能将速度提高n倍，实际上低于n，因为存在访问冲突,低位交叉访问存储器访问冲突分析,设每个存储周期只能取到k个有效字（k=1n），p(k)是k的概率密度函数，N是k的平均值，又称并行存储器的加速比，g为程序的转移概率，则：,讨论： 1）g=0即不发生转移，N=n 2) g=1即每条指令都是转移指令且转移成功，N=1,同单个存储体 结论：必须把并行和交叉访存与Cache存储系统配合起来才能组成高速主存,3 无冲突访问存储器（略）,产生冲突的原因：程序转移和数据的随机性 一种解决方

51、法：主存储器的存储体个数为质数,3.6 RAID系统,在服务器中为了提高磁盘存储器的容量和机器可靠性，通常采用磁盘阵列（Disk Array），或者称为独立冗余磁盘阵列（RAID，Redundant Array of Independent Disks）。 RAID系统采用多个低成本硬盘，以阵列形式排列，能够提供一个独立的大型存储设备解决方案。它将数据分散展开在多台磁盘上进行并行的读写操作，类似于存储器中的宽字存储器和多体交叉技术，提高了数据传输的带宽和磁盘操作的处理能力。 RAID系统具有容量大、数据传输率高、可靠性高、数据安全，易于磁盘管理等优点。,3.6 RAID系统,RAID的关键技术

52、是对多台磁盘机进行数据的同步控制，包括使用缓冲器使数据同步，采用冗余技术提高可靠性。 RAID技术经过不断的发展，现在已拥有了从 RAID 0 到 RAID 6七种基本的RAID级别。不同RAID 级别代表着不同的存储性能、数据安全性和存储成本。,（1）RAID 0：非冗余的磁盘阵列 RAID 0是把N块同样的硬盘用硬件的形式通过磁盘控制器或用操作系统中的磁盘驱动程序以软件的方式串联在一起创建一个大的卷集。在使用中电脑数据依次写入到各块硬盘中，它的最大优点就是可以整倍地提高硬盘的容量。此方式成本低、效率高。RAID 0没有提供冗余或错误修复能力，其最大的缺点在于任何一块硬盘出现故障，整个系统将

53、会受到破坏，可靠性仅为单独一块硬盘的1/N。,（1）RAID 0：非冗余的磁盘阵列 RAID 0的另一种模式是在N块硬盘上选择合理的带区来创建带区集。其原理就是将原先顺序写入的数据被分散到所有的N块硬盘中同时进行读写。N块硬盘的并行操作使同一时间内磁盘读写的速度提升了N倍。但是频繁进行读写操作时，很容易使控制器或总线的负荷超载。可增加磁盘控制器。最好每一块硬盘都配备一个专门的磁盘控制器。 RAID 0一般用于要求容量大但对数据安全性要求不高的情况。,（2）RAID 1：镜像磁盘冗余阵列 磁盘镜像的原理是数据在写入一块磁盘的同时，会在另一块配对的磁盘上生成镜像文件。这种磁盘配对有主从式结构，数据

54、优先读写主盘，再读写备份盘；也有对等式结构。这两种方式都能使一个盘读/写时，另一个盘作校验工作。这就在不影响性能情况下，最大限度地保证系统的可靠性和可修复性。当然，成本也会明显增加，磁盘利用率为50%。另外，出现硬盘故障的RAID系统不再可靠，应当及时的更换损坏的硬盘，否则剩余的镜像盘也出现问题，那么整个系统就会崩溃。更换新盘后原有数据会需要很长时间同步镜像，外界对数据的访问不会受到影响，只是这时整个系统的性能有所下降。因此，RAID 1多用在保存关键性的重要数据的场合。,（3）RAID 2：采用海明码纠错冗余的磁盘阵列 它将数据按位交叉，分别写入不同的磁盘中，成倍提高了数据传输率。阵列中专门

55、设置了几个磁盘存放海明码纠错信息，访问时进行按位的出错校验。它比镜像磁盘阵列的冗余度小，但增加了海明码的编码和解码开销，一般适合于大量顺序数据访问。,（4）RAID 3：采用奇偶校验冗余的磁盘阵列 它也采用数据按位交叉，使用一个专门的磁盘用于存储其他n个磁盘上对应字节的异或（XOR），这个第n1个磁盘被称为奇偶盘。如果任何一个磁盘发生了故障，可以通过对其他磁盘上的对应位执行异或来重构故障磁盘的每一位。这种阵列冗余度小，特别是磁盘较多时。 RAID 3所存在的最大一个不足是校验盘很容易成为整个系统的瓶颈。对于那些经常需要执行大量写入操作的应用来说，校验盘的负载将会很大。因此，RAID 3更适合于

56、那些写操作较少、读操作较多的应用环境，例如数据库和WEB服务器等。,（5）RAID 4：独立传送磁盘阵列 与RAID 3不同之处是它将数据按块而不是按位交叉存储在多个磁盘上，且校验数据以块为单位存放在一个校验盘上。在数据不冲突时，多个磁盘可并行独立读/写。和RAID 3一样，校验盘为整个系统的瓶颈。而且对于只写一个磁盘的少量数据访问操作，校验数据的计算需要根据原数据计算出差值，这需要对磁盘上的原数据进行读操作，再读取校验盘上数据，然后将数据写入数据盘，并计算出新的校验数据，最后写入校验盘，需要4次访问磁盘的操作。因此虽然RAID 4适合于小块数据的读/写，但用得较少。,（6）RAID 5：另一

57、种独立传送磁盘阵列 它与RAID 4一样采用数据按块交叉存储，这种拆分方式对某些应用来说可能更加高效。例如，如果有很多并发执行的事务，每个事务需要读取数据的一段，则可以并行地满足这些数据读取请求。但与RAID 4不同的是，奇偶校验信息本身被拆分并依次存储在每个盘上，避免了把所有奇偶信息存储在一个独立的奇偶盘上而导致的瓶颈。RAID 5的冗余度小，这种方式也适合于小块数据的读/写，但对控制器要求较高。,（7）RAID 6：高效容错的磁盘阵列该阵列 采用两级数据冗余和新的数据编码以解决数据恢复问题，其最大特点是能实现两个磁盘容错，即有两个磁盘出故障时仍能正常工作。在进行写操作时，RAID 6分别进

58、行两个独立的校验核算，形成两个独立的冗余数据，写入两个磁盘。比如在Intel的80333IOP芯片中，有一种称为P+Q的冗余技术，采用两种不同分组大小的“Reed-Solomon”循环码编码，可以在两个磁盘同时出故障时恢复数据。校验数据还可以采用二维的算法，将数据组织成矩阵格式后，分别按行按列计算，生成冗余数据。,另外，还有一些基本RAID级别的组合形式，如RAID 10、RAID 0+1、RAID 50等。 RAID 10是先组织成镜像备份的RAID 1，再将两个RAID 1组织成扩展容量的RAID 0。RAID 0+1则先组织成RAID 0，再组成RAID 1。 RAID 0+1在具有RAID 0的高性能的同时也具有RAID 1的冗余和镜像能力。RAID 10模式同RAID 0+1模式一样具有良好的数据传输性能，但却比RAID 0+1具有更高的可靠性。它们的磁盘利用率都为50，且至少由4个硬盘驱动器构成。,RAID系统中的关键部件是RAID控制器，它根据主机的访问要