计算机系统结构.ppt

计算机系统结构 主讲蔡启先 第3章存储系统 3 1存储系统原理 3 2虚拟存储系统 3 3高速缓冲存储器Cache 第3章存储系统 3 4三级存储系统 3 7存储域网络 SAN 3 5并行存储器 3 6RAID系统 本章重点 存储系统原理和层次结构虚拟存储器的概念 基本结构 地址变换 替换算法Cache的概念 基本结构 设计与地址变换 替换算法 3 1存储系统原理 3 1 1存储系统的概念 3 1 2存储器的层次结构 一个存储器的性能通常有三个主要参数 容量 价格和速度 存储器容量SM W l m 其中 W为存储体的字长 单位为位或字节 l为每个存储体的字数 m为并行工作的存储体个数 3 1 1存储系统的概念 存储器的速度可以用访问时间TA 存取周期TM和频宽 也称带宽 Bm来描述 TA是存储器从接到访存读申请 到信息被读到数据总线上所需的时间 这段时间是处理机在启动访存申请后必须等待的时间 TM则是连续启动一个存储体所需要的间隔时间 它一般总比TA大 存储器频宽是存储器可提供的数据传送速率 一般用每秒钟传送的信息位数 或字节数 来衡量 又分最大频宽 或称极限频宽 和实际频宽 最大频宽Bm是存储器连续访问时能提供的频宽 单体的Bm W TM m个存储体并行工作时可达到的最大频宽Bm W m TM 由于存储器不一定总能连续满负荷地工作 所以 实际频宽往往要低于最大频宽 存储器的价格可以用总价格C或每位价格c来表示 具有SM位的存储器每位价格c C SM 存储器价格包含了存储单元本身及为该存储器操作所必须的外围电路的价格 计算机系统总希望存储器能在尽可能低的价格下 提供尽量高的速度和尽量大的存储容量 在速度上应尽量和CPU匹配 容量上应尽可能放得下所有系统软件和多个用户软件及其运行时所需的空间 只用一种存储器无法解决上述高速度 大容量 低价格的要求 有两个途径 一个是用多种类型的存储器组成具有一定层次的存储系统 组合实现存储器的大容量 高速度和低价格要求 一个是发展并行存储体系 通过并行访存来提高存储器的性能 存储系统的定义 多个性能各不相同的存储器用硬件或软件方法连接成一个系统 这个系统对应用程序员透明 在应用程序员看来 它是一个存储器 其速度接近速度最快的那个存储器 存储容量与容量最大的那个存储器相等或接近 单位容量的价格接近最便宜的那个存储器 设n个存储器M1 T1 S1 C1 M2 T2 S2 C2 Mn Tn Sn Cn 构成一个存储器系统 从外部看 该存储器的存储周期T min T1 T2 Tn 存储器的容量S max S1 S2 Sn 存储器每位的价格C min C1 C2 Cn 从外部看T S C M1 T1 S1 C1 M2 T2 S2 C2 Mn Tn Sn Cn 例 两种存储系统 Cache存储系统 由Cache与主存储器构成 目标是提高速度 全部采用硬件调度 对系统程序员透明 虚拟存储系统 由主存储器与外存储器构成 目标是扩大存储容量 采用软硬件结合方法调度 对应用程序员透明 对S C T的讨论 设M1和M2构成一个存储器 其中 S1 C2T1 T2存储容量S S2 选择大容量存储器进行编址 单位容量的平均价格C C2 3 访问周期T 1 命中率H 在M1 较高速度存储器 中访问到的概率设N1 N2分别为访问M1 M2的次数 则H N1 N1 N2 2 存储系统的访问周期TT H T1 1 H T2H为命中率当H 1时 T T13 T与T1接近程度用访问效率e表征 e f H T2 T1 说明 要使T接近T1 一是提高命中率 二是两个存储器速度之比不能过大改进方法 对虚拟存储器 加大调用块与改进替换算法等对Cache存储系统 采用多级Cache 加大Cache 预取技术 改进替换算法等 CPU内部 通用寄存器堆指令和数据缓冲栈 主存 脱机外存 联机外存 Cache 访问速度 每位价格 存储容量 3 1 2存储器的层次结构 存储层次之间的关系 工作速度 TiCi 1 虚拟存储系统 主存与联机外存共同组成主存 DRAM 容量小 速度快 价格高外存 磁盘 容量大 速度慢 价格低虚拟存储器完成主存 辅存的存储层次工作 目标 增加快速的存储器容量 虚拟存储器的建立和管理主要基于软件 因此对系统程序员是不透明的 3 2虚拟存储系统 3 2 1虚拟存储器的工作原理3 2 2地址映象及地址变换3 2 3页面替换算法3 2 4提高主存命中率的方法 3 2虚拟存储系统 3 2 1虚拟存储器的工作原理 虚拟存储器的地址空间有三种 虚地址空间 它是应用程序员编程的地址空间 这个地址空间非常大 主存地址空间 又称实存地址空间 辅存地址空间 即磁盘地址空间 以页式虚存为例页 Page 固定大小的块 1 16KB 主存分页 实页虚存分页 虚页主存地址A虚地址Av 内部地址变换U P p 外部地址变换 查外页表 U P 外存实地址 联机外存地址 主存页面表 页面替换算法 I O通道 启动脱机外存 命中访问主存 选主存页 页内地址 主存 未命中 未命中 访联机外存 主存页面失效 查内页表 命中 主存未满 有空页号 主存满 主存页号 调入页 被替换页 选页 页式虚存的工作过程 虚地址Av 内部地址变换 未命中 外部地址变换 查外页表 命中得到P对应的实地址无 实页号p d查内页表启动脱机外存 访问主存有空页号无空页号 调入主存替换调入 3 2 2地址映象及地址变换 地址映像 程序装入时 建立用户虚地址与主存实地址的对应关系 便于取指令 地址变换 程序运行时 用户虚地址变换为主存实地址 内部地址变换 或辅存地址 外部地址变换 便于数据存取 三种类型的虚存 1 段式虚拟存储器 2 页式虚拟存储器 3 段页式虚拟存储器 1 段式虚拟存储器 基本原理 按程序内容分段 长度可长可短 建立段表 段号 段长 段起始地址 段访问方式及标志 地址映像方法 示意 地址变换过程 示意 0段 1段 2段 3段 0 1 2 3 段号 8K 16K 9K 30K 起始地址 程序段通过段表与主存中的区域唯一对应如第i程序段对应段表中段号为i的一行 由起始地址和段长即可找到主存中对应的段 1K 500 200 200 段长 08K9K16K30K 01K050002000200 程序空间 段表 主存储器 地址映像方法 虚地址U S D 段表基址寄存器堆 该用户或作业的段表 主存实地址 地址变换过程 用户号U 段号S 段内偏移D 6 As 段表基址寄存器 一个用户 一道作业 的段表 多用户虚地址 主存实地址 U 6 S 3 As 段表有关字段作用 起始地址 段长 位置保护访问方式 保护级别装入位 程序段是否在主存中标志 是否修改 段式虚存的主要优点 程序的模块化性能好便于程序和数据的共享程序的动态链接和调度比较容易便于实现信息保护段式虚存的主要缺点 地址变换费时主存利用率低对辅存管理较困难 2 页式虚拟存储器 页 虚实地址空间分为固定大小的块 Page 一般为0 5kB的整数倍 1 16kB地址映像方法地址变换过程 0页 1页 2页 3页 0 1 2 3 页号 主存页号 程序分页 页表映像 主存页 地址映像方法 虚地址U P D 页表基址寄存器堆 该用户或作业的页表 主存实地址 地址变换过程 用户号U 虚页号P 页内偏移D Pa 页表基址寄存器 页表 多用户虚地址Av 实页号p Pa 主存实地址A 页内偏移d 页式虚拟存储器主要优点主存利用率高页表简单地址映象与变换速度快对辅存管理容易页式虚拟存储器主要缺点程序的模块化性能不好页表很长 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 多用户虚地址U S P D 段表基址寄存器 该用户或作业的段表 相应的页表 主存实地址 段页式虚存地址变换过程 用户号U 段号S 页内偏移D 段表基址寄存器 多用户页表 多用户虚地址 主存地址A As 虚页号P As 多用户段表 页内偏移d 实页号p Ap 段页式虚拟存储器主要优点程序的模块化较好主存利用率高对辅存管理容易段页式虚拟存储器主要缺点访主3次 访段表页表各1次 再访主存实地址 查表速度有待改进 4 内部地址变换方法的改进 1 虚存速度降低的原因多次访主 多次查表 页表或段表容量超过一个页面大小时 相加求地址方法不成立 2 减小页表的解决办法 多级页表 树型结构的多级页表 页表基地址寄存器 第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拼接的快表在Cache中 采用与目录表相同的相联方式访问 慢表 页表 在主存储器中 快 慢表同时查 若快表找到则终止慢表查询 否则访问慢表 3 散列函数把多用户虚页号Pv变成快表地址AhAh H Pv 若发生散列冲突 则查慢表 5 外部地址变换 1 外部地址变换 在内部地址变换未命中时 即发生页面失效 找到辅存实地址 把所需页或段调入主存中2 严重页面失效故障及其解决 严重页面失效故障 在指令跨页 执指跨页时可能发生 作为异常故障处理处理关键 保存和恢复故障点的现场3种方法 硬件缓冲寄存器 保存现场 处理后完整恢复保存部分现场 处理后 再从头执行未完成的指令指令预判技术 经预判 事先做好页面失效处理 3 磁盘存储器的格式4 外部地址变换过程用软件实现 以页式为例用户号U 外页表始地址虚页号P 外页表记录 存储字 装入位为1可得磁盘实地址装入位为0须将脱机外存调入可采用多级页表技术若无需脱机外存装入 则内页表和外页表可合二为一 用户号U 外页表始地址 虚页号P 外页表记录 存储字 外部地址变换过程 用户号U 虚页号P 页内偏移D 外部地址变换 用软件实现 外页表 多用户虚地址Av 磁盘实地址 找到该用户程序的外页表首址 找到与该页对应的存储字 装入位为1可得磁盘实地址 装入位为0须将脱机外存调入 3 2 3页面替换算法 页面替换要解决的问题 由于虚拟存储空间的页数大大多于主存空间的页数 一般主存空间必然全占用 因此当发生页面失效时 必须从辅存中调入新页替换主存中不常用的页 评价页面替换算法的主要标准 命中率高算法容易实现 1 页面替换算法 常用的页面替换算法1 随机算法RAND randomalgorithm 由随即函数决定替换页 最简单 但命中率低2 先进先出算法FIFO first infirst outalgorithm 替换最先调入的页 容易实现 但未反映程序的局部性 3 近期最少使用算法LRU leastrecentlyusedalgorithm 选择近期最少使用的页进行替换 算法能比较正确地反映程序的局部性 最初为每页设一个计数器 定时计数 调换时选计数时间最长的页替换 实现较复杂 且计数器字长很长 占空间 实际用到的LRU算法简化了计数方式 实现时在页表或目录表中对每一页增设一个 使用次数 计数器字段 某页调入时 该字段清0 这一页被访问一次 该页的计数器字段加1 计数值最小也即访问次数最少的页就是替换页 LRU算法较合理 也较易实现 被广泛采用 4 最优替换算法OPT optionalreplacementalgorithm 理想算法 常用于做替换算法比较基准 例3 1设某一道程序有1 5个虚页 程序执行时的访存的页地址流为 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4 若主存页面数为3 请分别采用FIFO LRU OPT算法说明对这3页的使用和替换过程 并分别算出命中率 例4 3FIFO LFU OPT算法比较 程序执行的页地址流 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4主存页面数为3LFU算法的命中率接近OPT算法 说明算法较好 解 分别采用FIFO LRU OPT算法对主存3页的使用和替换过程如图3 12所示 其中用 号标记的虚页是由该替换算法确定的被替换页 入 换 中 分别表示页的调入 替换和命中情况 该程序访存共10次 各算法的命中率如下 FIFO法 H 2 10 0 2LRU法 H 4 10 0 4OPT法 H 5 10 0 5比较可知 LRU算法的命中率接近OPT算法 说明算法较好 2 堆栈型替换算法 定义 对任意一个程序的页地址流作两次主存页面数分配 分别分配m个主存页面和n个主存页面 并且有m n 如果在任何时刻t 主存页面数集合都满足关系 则这类算法称为堆栈型替换算法特点 随着分配给程序的主存页面数增加 主存的命中率也提高 至少不下降LFU LRU OPT算法都是堆栈型算法FIFO算法不是堆栈型算法 例3 2设某一道程序有1 5个虚页 程序执行时的访存的页地址流为 1 2 3 4 1 2 5 1 2 3 4 5 求出分配给该程序的主存页面数分别为3页和4页时的使用和替换过程 请分别采用FIFO LRU OPT算法进行对比说明 例4 3FIFO LFU OPT算法比较 程序执行的页地址流 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4主存页面数为3LFU算法的命中率接近OPT算法 说明算法较好 例4 3FIFO LFU OPT算法比较 程序执行的页地址流 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4主存页面数为3LFU算法的命中率接近OPT算法 说明算法较好 解 分别采用FIFO LRU OPT算法对主存3页的使用和替换过程如图3 13所示 将主存页面数由3页改为4页 仍然采用3种算法分别对主存4页使用和替换 如图3 14所示 比较二图 可知随着主存页数由3页增加到4页 LRU OPT算法的命中率增加了 而FIFO算法的命中率不增加反而减少了 可见LRU OPT替换算法属于堆栈型替换算法 而FIFO算法不是堆栈型替换算法 3 2 4提高主存命中率的方法 为何要提高主存命中率 对公式T HT1 1 H T2分析 必须提高H影响主存命中率的主要因素程序执行中的页地址流分布所采用的页面替换算法页面大小主存容量所采用的页面调度方法 1 页面大小的选择页面大小Sp与主存容量S 命中率H的关系曲线 主存大 命中率高页面大小应适当 H1 2S S Sp 2 主存容量主存容量S增加到一定程度 命中率H提高变缓 H1 S 3 页面调度方式分页式 整个程序链接装入主存后才运行 命中率100 但主存利用率低 程序长度必须小于主存安排空间请求页式 发生页面失效时 才进行页面调换预取式调度预先调入相关页面 防止程序挂起后重新运行时频繁调入页面 一种动态页面调度方法 页面失效频率法PFF PageFaultFrequency 动态给每个程序分配主存页面数 命中率低于某个限定值 则增加分配页面数 否则减少分配的主存页面数 使命中率和主存利用率都能提高 3 3高速缓冲存储器Cache 问题的提出 CPU与主存速度相差100倍左右采用的解决办法CPU中设计寄存器堆 缓解访存压力先行缓冲存储器 速度差缩小30倍采用Cache存储系统 Cache与虚存的比较 3 3高速缓冲存储器Cache 3 3 1基本工作原理 3 3 2Cache的一致性及性能分析 3 3 311种先进的Cache性能优化方法 3 3 1基本工作原理 主存与Cache之间以块为单位进行数据交换主存地址 Cache地址 地址变换过程 B b 命中 CPU 访存 调入Cache 替换 Cache Cache满 Y N Y N 1 地址映象与变换方法 地址映像 把主存地址空间映像到Cache地址空间 即建立主存地址与Cache地址的对应关系 以便程序装入Cache地址变换 程序装入Cache后 运行中如何将主存地址变换成Cache地址 1 全相连映象及其变换 2 直接映象及其变换 3 组相连映象及其变换 4 位选择组相连映象及其变换 略 5 段相连映象及其变换 略 1 全相连映象及其变换 任意B可映象到任意b 映象关系共有Cb Mb种 查目录表 命中 以b访问Cache 未命中 以主存地址访存 备份装入Cache 全相联地址变换 块号B 块内地址W 目录表 由相联存储器构成 共Cb个字 主存地址 块号b 相联比较 Cache地址 块内地址w 查到相等的块号 有效位为1表示映像有效 全相联映象及其变换优点 块冲突率最小缺点 相联比较费时 为虚存采用 2 直接映象及其变换 直接映象 主存中1块只映象到Cache的特定块中b BmodCbMb应是Cb的整数倍 主存分区 Me Cb 分区中的块号Be与Cache中的块号b相同主存地址 Cache地址 直接相联映象方式 区0 区1 区Me 1 直接相联地址变换 块号B 块内地址W 区表存储器 共Cb个字 主存地址 块号b 相等 Cache地址 块内地址w 区号E 相等比较 块失效 访问Cache 若相等且有效位为1 即命中 以Cache地址访问Cache 读出数据送往CPU 以块号B访问区表 读出区号进行比较 不等 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时 成直接映像方式当每组块容量Gb与Cache的块容量Cb相等时 成全相联映像方式 一般 Gb越大 块的冲突概率和块失效率越低 但组内映像关系就越复杂 实现成本越高 应注意合理分配组的块容量 2 Cache替换算法 直接映像方式实际上不需替换算法全相联映像替换算法最复杂在组相联和位选择组相联映象及地址变换方式中要考虑替换算法Cache替换算法用硬件实现 两种基于LRU算法的全硬实现方法 1 比较对法 2 堆栈法 比较对法 LRU算法实际上要把同一组内的各个块按照被访问过的时间顺序排序 从而找出最久没有被访问的块 一个两态的器件 如RS触发器 能够记录上两块之间的先后顺序 多个块之间的先后顺序可用多个两态器件的组合来实现 以三个块 分别命名为A B C块 为例 设TAB表示B块比A块更久没有被使用过 其它类似 则A B C三块共有6种排列 比较对法 如果访问过的次序为ABC A为最近访问过的块 C为最久未被访问过的块 则此时必有TAB 1 TAC 1 TBC 1 因此以最久未被访问过的块C作为被替换掉的块的话 用布尔代数式必有同理 当每组的块数达到8个时 需要的触发器个数为28个 与门的输入端个数为7 硬件成本增大 可采用分级办法解决 但同时要考虑分级带来的迟延 比较法的特点是 用LRU法块失效率比较低 全硬件工作速度比较高 当每组块数较多时 硬件实现相对复杂 需要很多的触发器 堆栈法 堆栈法用栈顶至栈底的先后次序来记录Cache同一组内的各个块被访问的先后顺序 栈顶是最近访问过的 栈底是最久没有被访问过的 替换时 从栈顶压入新的块 而栈底的块自然就被挤出 该方法有自己的管理规则 并不与FIFO法相同 堆栈法管理规则 把本次访问的块号与堆栈中保存的所有块号进行相联比较 如发现有相等的 则表示命中 其压入方式如图3 25所示 并非压到栈底 如果相联比较没有发现相等 则Cache块失效 这时 从栈顶压入将栈底挤出 这样 栈底永远保存着最久没有被访问过的块号 也即下次要被替换的块号 堆栈法的特点是 用LRU法命中率较高 硬件实现相对简单 由于逐级下压 速度相对较慢 3 3 2Cache的一致性及性能分析 1 Cache的一致性2 Cache的取算法3 Cache的性能分析 1 Cache的一致性 问题的提出对Cache块的修改 未及时更新相应主存块解决办法 选择合适的Cache更新算法 1 写回法 writeback 指写Cache时不写主存 而当Cache数据被替换出去时 才写回主存 采用写回法 Cache块表中一般要设一个 修改位 一旦块被修改 该块的修改位就被置1 否则保持为0 这样替换该块时 若修改位是1 则必须把该块写回主存 并更新主存中的原块 若修改位是0 则不必写回 直接调入新块 2 写直达法 writethrough 即写操作时将数据既写入Cache同时又写入主存 写回法若不发生块失效 速度比写直达法要快 CPU对Cache中的一个数据块的多次写操作只需一次写入主存 减少了主存的写操作次数 但Cache中的数据在未替换时 可能与主存中的相应数据不一致 可靠性不如写直达法 同时 CPU如果读Cache发生块失效的话 将引起数据块的写回操作 采用写直达法 Cache块表中无需设 修改位 块替换时 无需把被替换块写回主存 因此写直达法比写回法简单 控制容易 但是写直达法的硬件代价高 因为为了节省同时写主存的时间 通常要增设一个高速小容量的缓冲存储器来暂存写主存的数据和地址 当出现写Cache不命中时 是否要把包括所写字在内的一个块从主存读入Cache问题 有按写分配法和不按写分配法等两种处理方法 按写分配法是指发生写Cache不命中时 先把所要写的字写入主存 再把包括所写字在内的一个块从主存读入Cache 此法可以提高Cache的命中率 不按写分配法则在写Cache不命中时 只把所要写的字写入主存 而不把包括所写字在内的一个块读入Cache 此法可简化Cache结构 省掉了将数据块读入Cache的操作 一般在写回法中采用按写分配法 在写直达法中为了减少同时写主存的开销而采用不按写分配法 采用写直达法还是写回法与系统应用有关 单处理机系统多数采用写回法以节省成本 共享主存的多处理机系统为保证各处理机经主存交换信息时不出错 多采用写直达法 2 Cache的取算法 基本的Cache取算法是按需取 即在访问Cache不命中时 根据访问的局部性原理 把包括所访问的字在内的一个块从主存读入Cache 如果进一步采用某种预取算法就能较大地提高Cache命中率 具体算法有2种 1 恒预取 当CPU访问Cache时 无论是否命中 都把紧接着访问字所在块的下一块从主存读入Cache 2 不命中预取 仅仅在Cache不命中时 才把访问字所在块及其邻接的下一块从主存读入Cache 影响预取法效果的因素 1 块的大小 每块的字节数最好不超过256 2 预取开销 要预取就要有访主存开销和将它取进Cache的访Cache开销 还要加上把被替换块写回主存的开销 模拟结果表明 恒预取法使不命中率降低75 80 而不命中预取法使不命中率降低30 40 但前者所引起的Cache 主存间传输量的增加要比后者大得多 3 Cache系统的性能分析 1 Cache系统的加速比设Cache的等效访问周期T Cache访问周期Tc 主存访问周期TmT H Tc 1 H TmCache系统的加速比Sp Tm T 1 1 H H Tc Tm f H Tm Tc 对Sp的分析 Tm Tc由器件决定 最有效的途径是提高H 一般H 0 9 达0 99以上 Sp接近Tm Tc Cache的加速比Sp与命中率H的关系 影响Cache命中率的因素分析 影响Cache命中率的因素程序执行过程中的地址流分布替换算法Cache容量组相联映象方式中块的大小和分组数目Cache预取算法 1 Cache命中率与容量的关系 关系曲线近似为H 1 S 0 5S达到一定程度后 H提高很少 Cache命中率H与容量S的关系 2 Cache命中率与块大小的关系 存在最佳块大小 H达到最大 初始 最佳 3 Cache命中率与组数的关系组数增加 512 H降低明显 3 3 311种先进的Cache性能优化方法 可从三个方面来优化Cache性能 即减少命中时的访问时间 简称命中时间 降低缺失率 不命中率 和减小缺失代价 即不命中时付出的开销 总结了11种先进的Cache性能优化方法 1 小而简单的Cache减少命中时间现代计算机中 一级Cache应尽可能小 这样块表小 查表速度快 同时也应使二级Cache尽可能小 使之能与CPU处于同一芯片内 避免片外时间代价 在快速时钟频率下 通过动态执行隐藏一级Cache缺失和使用二级Cache来避免直接访问主存 2 路预测 waypredicting 减少命中时间路预测要求Cache块中预留一个块预测位 用来预测下一次访问Cache时可能用到的方式或块 以便提前使用多路选择器来选择所需的块 若预测正确 则有最快的命中时间 若失败 将选择其它的块 模拟表明对于2路组相联来说 组预测的精度有85 Pentium4使用了路预测技术 3 踪迹Cache tracecache 减少命中时间在指令级并行的情况下 踪迹Cache的应用为转移预测提供了方便 踪迹Cache更好地利用了指令Cache中的长块 在它的块中包含了对已执行指令的动态跟踪信息 而不是在存储器中的静态指令序列 Pentium4采用了踪迹Cache 并使用译码微操作 节省了译码时间 但是踪迹Cache成本较高 硬件复杂 其它处理器几乎没有用到它 4 流水线Cache访问此方法将流水线 Cache访问 使一级Cache命中时的有效时延分散到几个时钟周期 它提供了较短的周期和高带宽 但是命中时间长 若流水线产生阻塞 可能有更多的时钟周期代价 5 利用非阻塞Cache lockup freecache 增加Cache带宽对于允许乱序执行的流水线机器 见第5章 来说 处理器是不需用在Cache缺失时停顿的 比如处理器在等待数据Cache返回数据的同时 可以继续从指令Cache中取指令 非阻塞Cache在缺失时继续保持Cache命中 减少了缺失代价 如果Cache能重叠多个缺失 则会进一步降低缺失代价 实现 多重缺失仍命中 或 缺失时仍缺失 通常 乱序执行的处理器若能在二级Cache中命中 则能隐藏一级Cache所产生的缺失代价 6 利用多组Cache增加Cache带宽此法类似对存储器的并行存取 将Cache分为若干个独立的存储体以支持并发访问 增加Cache带宽 如AMDOpteron的二级Cache有2个存储体 Sun的Niagara有4个存储体 7 关键字优先和提前重启动以减小缺失代价此技术来源于经验数据 处理器在同一时刻只需要块中的一个字 因此不必等到全部块装入就将所需字送出 然后重新启动处理器访问 具体有两种策略 1 关键字优先 首先向主存请求缺失的字 一旦它到达即送处理器 使得处理器在装入其它字的同时能够继续执行 2 提前重启动 以正常顺序获取字 块中所需字一旦到达即送处理器 使得处理器在装入其它字的同时能够继续执行 一般上述技术只适用于较大Cache块的情况 因为在填充剩余块的时候 Cache还会继续支持其它块的访问 8 合并写缓冲区 mergingwritebuffers 以降低缺失代价采用写直达法的Cache要有一个写缓冲区 写回法Cache在替换块时也要用到一个简单的写缓冲区 如果写缓冲区为空 可将被替换掉的数据和地址放到写缓冲区中 写操作即结束 写缓冲区准备将数据写回存储器时 处理器可继续工作 如果写缓冲区里还有其它修改过的数据 应检查新数据的地址是否与写缓冲区中的某一合法项数据地址相匹配 若匹配 新数据就合并到该项中 这就是写合并 此法可一次写多个字 并减少了因写缓冲区已满而产生的访Cache停顿 9 编译器优化以降低缺失率此法试图采用软件方法来优化Cache性能 在编译器中设法在不影响程序正确性的前提下进行程序代码和数据重组 以改善空间局部性 10 指令和数据硬件预取以降低缺失代价或缺失率将Cache的预取算法发展到多个流缓冲区中 例如Pentium4能从8个分别来自不同的4KB页面的流中 预取数据到二级Cache 11 编译控制预取降低缺失代价或缺失率此法利用编译器来插入预取指令 提前发出数据请求 有寄存器预取 把数据与渠道寄存器中 和Cache预取 只把数据预取到Cache中 两种方式 目前大多数处理器采用非故障性Cache预取技术 当然编译控制预取的目的是使指令执行和预取数据能够重叠进行 循环程序就很适宜预取优化 然而生成预取指令会带来指令的开销 因此应谨慎使用以保证开销在可接受的范围内 Cache 主存 磁盘三级存储系统组织方式1 两个存储系统组织方式Cache 主存存储系统和主存 磁盘存储系统 CPU MMU Cache 主存储器 数据或指令 数据或指令 虚拟地址 物理地址 物理地址 存储管理部件 能将虚拟地址变换为主存物理地址 若未命中Cache 则访问主存 块替换 3 4三级存储系统 2 一个存储系统组织方式Cache 主存 磁盘存储系统 CPU MMU Cache 主存储器 3 全Cache系统Cache 磁盘存储系统 无主存储器 在嵌入式系统中较多应用 3 5并行存储器 3 5 1存储器的频带平衡 3 5 2并行存储器 3 5 1存储器的频带平衡 计算机运行中至少有4种访问源 即访存取指令 访存取操作数 访存写结果 I O设备也要与主存交换数据 如何让存储器访问速度跟得上系统的需要 一直是设计者关注的问题 现代计算机普遍采用指令并行技术 对存储器的频带宽度提出了更高的要求 存储器的频带 访问源对存储器访问的速度 用MW S 百万字每秒 或MB S 百万字节每秒 表示存储器频带宽度的计算 各访问源的频带之和存储器的频带平衡 存储器速度与系统需要相适应 3 5 1存储器的频带平衡 例如 设一台计算机的执行速度为200MIPs 2亿指令 秒 要求 CPU取指令速度为200MW S 设每条指令的长度为一个字 CPU取 存操作数速度为400MW S 平均每条指令访问周期2个操作数 各种I O设备访问存贮器速度为5MW S 可求得存贮器的总频宽应为605MW S 即要求访存周期T 16 5ns 目前DRAM的访存周期是达不到这一要求的 解决存储器频带平衡的三条途径 并行存储器缓冲存储器Cache存储系统 3 5 2并行存储器 并行存储器 多个独立的存储器并行工作 同一存储周期内可访问多个数据 有三种并行存储器 1单体多字并行存储器2交叉访问存储器3无冲突访问存储器 1单体多字并行存储器 原理 增加存储器字长 实现同时读写多个字原m w字改为m n nw字m 存储单元数 w 字长访问方法 地址码高位访问存储单元 低位控制多路选择器选择其中数据 一般存储器访问 设存储器为1MB 每字8位即220字 8位数据寄存器MBR为8位地址寄存器MAR为20位 单体多字并行存储器访问 设存储器为1MB 每字64位即220 8字 8 8位 217字 64位数据寄存器MBR为8个字节地址寄存器MAR若仍为20位 则MAR高17位选字MAR低3位控制多路选择器8中选1 并行访问寄存器分析 主要优点 简单容易主要缺点 访问的冲突大取指令冲突 例如转移时同时读出的指令 后面的指令将可能无用 概率小读操作数冲突 同时读出的数据不一定都有用 概率大写数据冲突 只写1个或2个字节时需读出再写入 需专门控制 读写冲突 读写同一个存储字内的内容无法在同一周期内完成 需专门控制 原因 只有一套地址寄存器和控制逻辑 如果每个存储体都有独立的地址寄存器和控制逻辑 即由多个存储体组成存储器 显然 没有写数据冲突和读写冲突 其它冲突也会缓解 这时 对存储器的访问通常采用交叉方式 2交叉访问存储器 主存储器由多个模块构成 假设主存储器包含m 2a个存储器模块 每个模块包含w 2b个存储单元 字 则总存储容量为字地址位数为a b 两种组织方式交叉访问的存储器可以分为两种 1 高位交叉方式 2 低位交叉方式 1 高位交叉访问存储器存储器地址的高a位作为存储器模块地址 邻接的存储器单元被分配在同一个存储器模块中 在每个存储器周期内 只能对各模块存取一个字 所以不支持邻接单元的成块存取 高位n路交叉存取如下图 各个存储模块有独立的控制部件 地址码高位指示存储体号 地址码低位是各存储体的体内地址 高位译码选体 设 m 存储体容量n 存储体个数j 体内地址0 m 1k 存储体体号0 n 1存储单元地址A m k j若已知A 则存储体体内地址 Aj Amodm存储体体号 对多任务多用户 可提高访问速度 对单任务可扩大容量 向下取整 2 低位交叉访问存储器存储器地址的低a位用来指明存储器模块 高b位是每个模块内的字地址 低位n路交叉存取如下图 字地址译码器 各个存储模块有独立的控制部件 地址码低位指示存储体号 地址码高位是各存储体的体内地址 低位译码选体 存储单元地址 A n j k存储体体内地址 存储体体号 Ak Amodn 向下取整 如8路交叉 n 8 m 8 a b 3 8路低位交叉存取如下图 分时启动 启动间隔Tm 存储体访问周期低位交叉以流水线方式支持成块存取 低位交叉流水线方式示意图 时间 Tm为主周期 t Tm n为小周期 n为交叉存取度 低位交叉访问有可能将速度提高n倍 实际上低于n 因为存在访问冲突 低位交叉访问存储器访问冲突分析 设每个存储周期只能取到k个有效字 k 1 n p k 是k的概率密度函数 N是k的平均值 又称并行存储器的加速比 g为程序的转移概率 则 讨论 1 g 0即不发生转移 N n2 g 1即每条指令都是转移指令且转移成功 N 1 同单个存储体结论 必须把并行和交叉访存与Cache存储系统配合起来才能组成高速主存 3无冲突访问存储器 略 产生冲突的原因 程序转移和数据的随机性一种解决方法 主存储器的存储体个数为质数 3 6RAID系统 在服务器中为了提高磁盘存储器的容量和机器可靠性 通常采用磁盘阵列 DiskArray 或者称为独立冗余磁盘阵列 RAID RedundantArrayofIndependentDisks RAID系统采用多个低成本硬盘 以阵列形式排列 能够提供一个独立的大型存储设备解决方案 它将数据分散展开在多台磁盘上进行并行的读写操作 类似于存储器中的宽字存储器和多体交叉技术 提高了数据传输的带宽和磁盘操作的处理能力 RAID系统具有容量大 数据传输率高 可靠性高 数据安全 易于磁盘管理等优点 3 6RAID系统 RAID的关键技术是对多台磁盘机进行数据的同步控制 包括使用缓冲器使数据同步 采用冗余技术提高可靠性 RAID技术经过不断的发展 现在已拥有了从RAID0到RAID6七种基本的RAID级别 不同RAID级别代表着不同的存储性能 数据安全性和存储成本 1 RAID0 非冗余的磁盘阵列RAID0是把N块同样的硬盘用硬件的形式通过磁盘控制器或用操作系统中的磁盘驱动程序以软件的方式串联在一起创建一个大的卷集 在使用中电脑数据依次写入到各块硬盘中 它的最大优点就是可以整倍地提高硬盘的容量 此方式成本低 效率高 RAID0没有提供冗余或错误修复能力 其最大的缺点在于任何一块硬盘出现故障 整个系统将会受到破坏 可靠性仅为单独一块硬盘的1 N 1 RAID0 非冗余的磁盘阵列RAID0的另一种模式是在N块硬盘上选择合理的带区来创建带区集 其原理就是将原先顺序写入的数据被分散到所有的N块硬盘中同时进行读写 N块硬盘的并行操作使同一时间内磁盘读写的速度提升了N倍 但是频繁进行读写操作时 很容易使控制器或总线的负荷超载 可增加磁盘控制器 最好每一块硬盘都配备一个专门的磁盘控制器 RAID0一般用于要求容量大但对数据安全性要求不高的情况 2 RAID1 镜像磁盘冗余阵列磁盘镜像的原理是数据在写入一块磁盘的同时 会在另一块配对的磁盘上生成镜像文件 这种磁盘配对有主从式结构 数据优先读写主盘 再读写备份盘 也有对等式结构 这两种方式都能使一个盘读 写时 另一个盘作校验工作 这就在不影响性能情况下 最大限度地保证系统的可靠性和可修复性 当然 成本也会明显增加 磁盘利用率为50 另外 出现硬盘故障的RAID系统不再可靠 应当及时的更换损坏的硬盘 否则剩余的镜像盘也出现问题 那么整个系统就会崩溃 更换新盘后原有数据会需要很长时间同步镜像 外界对数据的访问不会受到影响 只是这时整个系统的性能有所下降 因此 RAID1多用在保存关键性的重要数据的场合 3 RAID2 采用海明码纠错冗余的磁盘阵列它将数据按位交叉 分别写入不同的磁盘中 成倍提高了数据传输率 阵列中专门设置了几个磁盘存放海明码纠错信息 访问时进行按位的出错校验 它比镜像磁盘阵列的冗余度小 但增加了海明码的编码和解码开销 一般适合于大量顺序数据访问 4 RAID3 采用奇偶校验冗余的磁盘阵列它也采用数据按位交叉 使用一个专门的磁盘用于存储其他n个磁盘上对应字节的异或 XOR 这个第n 1个磁盘被称为奇偶盘 如果任何一个磁盘发生了故障 可以通过对其他磁盘上的对应位执行异或来重构故障磁盘的每一位 这种阵列冗余度小 特别是磁盘较多时 RAID3所存在的最大一个不足是校验盘很容易成为整个系统的瓶颈 对于那些经常需要执行大量写入操作的应用来说 校验盘的负载将会很大 因此 RAID3更适合于那些写操作较少 读操作较多的应用环境 例如数据库和WEB服务器等 5 RAID4 独立传送磁盘阵列与RAID3不同之处是它将数据按块而不是按位交叉存储在多个磁盘上 且校验数据以块为单位存放在一个校验盘上 在数据不冲突时 多个磁盘可并行独立读 写 和RAID3一样 校验盘为整个系统的瓶颈 而且对于只写一个磁盘的少量数据访问操作 校验数据的计算需要根据原数据计算出差值 这需要对磁盘上的原数据进行读操作 再读取校验盘上数据 然后将数据写入数据盘 并计算出新的校验数据 最后写入校验盘 需要4次访问磁盘的操作 因此虽然RAID4适合于小块数据的读 写 但用得较少 6 RAID5 另一种独立传送磁盘阵列它与RAID4一样采用数据按块交叉存储 这种拆分方式对某些应用来说可能更加高效 例如 如果有很多并发执行的事务 每个事务需要读取数据的一段 则可以并行地满足这些数据读取请求 但与RAID4不同的是 奇偶校验信息本身被拆分并依次存储在每个盘上 避免了把所有奇偶信息存储在一个独立的奇偶盘上而导致的瓶颈 RAID5的冗余度小 这种方式也适合于小块数据的读 写 但对控制器要求较高 7 RAID6 高效容错的磁盘阵列该阵列采用两级数据冗余和新的数据编码以解决数据恢复问题 其最大特点是能实现两个磁盘容错 即有两个磁盘出故障时仍能正常工作 在进行写操作时 RAID6分别进行两个独立的校验核算 形成两个独立的冗余数据 写入两个磁盘 比如在Intel的80333IOP芯片中 有一种称为P Q的冗余技术 采用两种不同分组大小的 Reed Solomon 循环码编码 可以在两个磁盘同时出故障时恢复数据 校验数据还可以采用二维的算法 将数据组织成矩阵格式后 分别按行按列计算 生成冗余数据 另外 还有一些基本RAID级别的组合形式 如RAID10 RAID0 1 RAID50等 RAID10是先组织成镜像备份的RAID1 再将两个RAID1组织成扩展容量的RAID0 RAID0 1则先组织成RAID0 再组成RAID1 RAID0 1在具有RAID0的高性能的同时也具有RAID1的冗余和镜像能力 RAID10模式同RAID0 1模式一样具有良好的数据传输性能 但却比RAID0 1具有更高的可靠性 它们的磁盘利用率都为50 且至少由4个硬盘驱动器构成 RAID系统中的关键部件是RAID控制器 它根据主机的访问要求将数据读 写操作分解成多个磁盘的操作 目前 RAID控制器只对数据进行拆分 磁盘容错管理和校验 并不对数据请求事务进行合并 调度和优化处理 这些工作由操作系统完成 RAID只进行先来先服务的操作方式 RAID通常采用嵌入式固件方式实现 RAID系统实现了将多个物理磁盘构成一个逻辑上统一的虚拟磁盘存储系统 其原理是将磁盘的扇区地址映射为一个与物理位置无关的线性逻辑块地址 这个工作由RAID控制器担任 这样 软件上就可以以 卷 为单位对磁盘空间进行管理 RAID技术早期被用于高级服务器内应用SCSI接口的硬盘系统中 随着近年PC机的CPU速度进入GHz时代 IDE接口的硬盘也相继推出了ATA66和ATA100硬盘 这就使得RAID技术被应用于中低档甚至个人PC机上成为可能 RAID通常是由在硬盘阵列中的RAID控制器或电脑中的RAID卡来实现的 3 7存储域网络 SAN 数据管理的实质是存储管理 完善的存储策略既要全面支持现有社会环境中开放式多平台存储环境 又要应付当今业务应用中数据的飞速增长 这就要求存储管理创建一种独立于LAN 统一的 扩展性很好的存储架构 存储域网络 SAN Storage areanetwork 就应运而生 SAN通常是由服务器 存储设备 磁带机 磁盘阵列 CD ROM库等 交换机及光纤通道连接而成的存储网络 利用光纤通道 主机可以通过SCSI与存储设备对话 目前 光纤通道支持的数据传输速率已达到千兆位及以上带宽 分布式SAN可以把多台不同的服务器与多台存储设备连接起来 在SAN中 不同平台的服务器可以对多个存储设备进行存储 存储设备之间也可以不通过服务器而相互备份 SAN使得存储设备不再附属于某个服务器 而是直接联到网络上 形成存储域网络 从而减少对服务器CPU的占用 提高了存储效率 SAN采用后端的网络连接存储 服务器通过光纤通道与存储接口而不是网络接口与存储设备互连 这个网络可以是共享式网络 也可以是交换式网络 在SAN的存储模式中 存储资源的动态分配 空闲资源的回收和再分配操作不会影响主机应用程序的运行 主机系统可以使用多重路径来连接同一个存储设备以避免单点故障 客户机与服务器组成的局域网 LAN 属于前端网络 在这个面向客户的前端网络中 每个服务器可以在它所在的LAN中为客户端提供服务 在SAN的后端网络中有一个主动合并部件 可实现数据合并和统一的数据备份和检索 并保证数据的完整性和可靠性 SAN在扩大共享存储空间的同时 还实现了文件系统的虚拟化 它基于存储系统的虚拟化 以数据块为单位跨越整个存储网络构成分布式虚拟存储空间 从而建立起全局的分布式文件系统 或者代理文件系统 这种虚拟化的文件系统将访问不同文件系