3.3.4 Cache存储系统的加速比 Cache存储系统的主要目标 Cache存储系统的加速比 Cache存储系统的一致性问题 l、加速比与命中率的关系 Cache存储系统的加速比Sp( Speedup)为: +(1一 其中:Tm为主存储器的访问周期,T为 Cache的访问周期,T为 Cache存 储系统的等效访问周期,H为命中率。 提高 Cache存储系统加速比的最好途径是提高命中率 实际上, Cache存储系统的加速比Sp能够接近于它的期望值rm。 Sp期望值 6 4 命中率H Cache存储系统的加速比Sp与命中率H的关系 命中率H主要与如下几个因素有关: 程序在执行过程中的地址流分布情况 所采用的替换算法 Cache的容量 在组相联映象方式中,块的大小 在组相联映象方式中,分组的数目 所采用的 Cache预取算法 2、 Cache命中率与容量的关系 Cache的命中率随它的容量的增加而提高 关系曲线可以近似地表示为H=1-S-05
3—1 3.3.4 Cache 存储系统的加速比 • Cache 存储系统的主要目标： Cache 存储系统的加速比 Cache 存储系统的一致性问题 1、加速比与命中率的关系 • Cache 存储系统的加速比 SP（Speedup）为： S T T T H T H T H H T T f H T T p m m c m c m m c = = + − = − + = ( ) ( ) ) ( , ) 1 1 1 其中：Tm 为主存储器的访问周期，Tc 为 Cache 的访问周期，T 为 Cache 存 储系统的等效访问周期，H 为命中率。 • 提高 Cache 存储系统加速比的最好途径是提高命中率 实际上，Cache 存储系统的加速比 SP 能够接近于它的期望值 T T m c 。 0 2 4 6 8 SP期望值 1 命中率 H SP max =Tm／Tc Cache 存储系统的加速比 SP 与命中率 H 的关系 • 命中率 H 主要与如下几个因素有关： 程序在执行过程中的地址流分布情况 所采用的替换算法 Cache 的容量 在组相联映象方式中，块的大小 在组相联映象方式中，分组的数目 所采用的 Cache 预取算法 2、Cache 命中率与容量的关系 Cache 的命中率随它的容量的增加而提高。 关系曲线可以近似地表示为 H＝1－S －0.5
命中率H →>容量S 命中率H与它的容量S的关系 3、 Cache命中率与块大小的关系 在组相联映象方式中,块的大小对命中率的影响非常敏感 块很小时,命中率很低 随着块大小的增加,由于程序的局部性,命中率增加。 当块非常大时,进入 Cache中的许多数据可能用不上。 当块大小等于 Cache的容量时,命中率将趋近于零。 命中率H 初始 最佳 块大小 Cache的命中率与块大小的关系 4、 Cache命中率与组数的关系 在组相联映象中,分组的数目对命中率的影响很明显 随着组数的增加, Cache的命中率要降低。 当组数不太大时(512组以下),命中率的降低相当少, 当组数超过一定数量时,命中率的下降非常快 3.3.5 Cache的一致性问题 本节讨论的内容仅限于单处理机、单存储器。 造成 Cache与主存的不一致的原因 (1)由于CPU写 Cache,没有立即写主存 (2)由于IO处理机或IO设备写主存
3—2 容量 S 命中率 H 1 命中率 H 与它的容量 S 的关系 3、Cache 命中率与块大小的关系 在组相联映象方式中，块的大小对命中率的影响非常敏感 块很小时，命中率很低。 随着块大小的增加，由于程序的局部性，命中率增加。 当块非常大时，进入 Cache 中的许多数据可能用不上。 当块大小等于 Cache 的容量时，命中率将趋近于零。 块大小 命中率 H 1 初始 最佳 Cache 的命中率与块大小的关系 4、Cache 命中率与组数的关系 在组相联映象中，分组的数目对命中率的影响很明显。 随着组数的增加，Cache 的命中率要降低。 当组数不太大时(512 组以下)，命中率的降低相当少， 当组数超过一定数量时，命中率的下降非常快。 3.3.5 Cache 的一致性问题 本节讨论的内容仅限于单处理机、单存储器。 • 造成 Cache 与主存的不一致的原因： (1) 由于 CPU 写 Cache，没有立即写主存 (2) 由于 IO 处理机或 IO 设备写主存
CPU 1/0 CPU I/O 主存储器 主存储器 (a)CPU写 Cache (b)I/O写主存 Cache与主存不一致的两种情况 Cache的更新算法 (1)写直达法,又称写通过法,wT( Write-through) CPU在执行写操作时,把数据同时写入 Cache和主存。 (2)写回法,又称为抵触修改法,WB( Write-Back) CPU的数据只写入 Cache,不写入主存 仅当替换时,才把修改过的 Cache块写回到主存。 写回法与写直达法的优缺点比较 (1)可靠性,写直达法优于写回法。 (2)与主存的通信量,写回法少于写直达法 例如:写操作占总访存次数的20%, Cache的命中率为99%,每块为4个 字。当 Cache发生块替换时,有30%块需要写回到主存,其余的块因为没有被 修改过而不必写回主存 则对于写直达法,写主存次数占总访存次数的20% 而对于写回法,(1-99%×30%×4=1.2% 因此,与主存的通信量,写回法要必写直达法少10多倍 (3)控制的复杂性,写直达法比写回法简单。 (4)硬件实现的代价,写回法要比写直达法好。 写 Cache的两种方法 (1)不按写分配法:在写 Cache不命中时,只把所要写的字写入主存。 (2)按写分配法:在写 Cache不命中时,还把一个块从主存读入 Cache 目前,在写回法中采用按写分配法,在写直达法中采用不按写分配法。 3.3.6 Cache的预取算法 预取算法有如下几种: 1、按需取。在出现 Cache不命中时,把一个块取到 Cache中来。 2、恒预取。无论 Cache是否命中,都把紧接着的下一块取到 Cache中。 3、不命中预取。当 Cache不命中,把本块和下一块取到 Cache中 主要考虑因素:命中率的提高和 Cache与主存之间通信量的增加 从模拟实验的结果看: 采用恒预取能使 Cache的不命中率降低75~85%
3—3 CPU I/O CPU I/O Cache X’ Cache X 主存储器 X 主存储器 X’ (a) CPU 写 Cache (b) I/O 写主存 Cache 与主存不一致的两种情况 • Cache 的更新算法 (1) 写直达法，又称写通过法，WT（Write-through） CPU 在执行写操作时，把数据同时写入 Cache 和主存。 (2) 写回法，又称为抵触修改法，WB（Write-Back） CPU 的数据只写入 Cache，不写入主存。 仅当替换时，才把修改过的 Cache 块写回到主存。 • 写回法与写直达法的优缺点比较： (1) 可靠性，写直达法优于写回法。 (2) 与主存的通信量，写回法少于写直达法。 例如：写操作占总访存次数的 20％，Cache 的命中率为 99％，每块为 4 个 字。当 Cache 发生块替换时，有 30％块需要写回到主存，其余的块因为没有被 修改过而不必写回主存。 则对于写直达法，写主存次数占总访存次数的 20％ 而对于写回法，(1－99％)×30％×4＝1.2％。 因此，与主存的通信量，写回法要必写直达法少 10 多倍。 (3) 控制的复杂性，写直达法比写回法简单。 (4) 硬件实现的代价，写回法要比写直达法好。 • 写 Cache 的两种方法： (1) 不按写分配法：在写 Cache 不命中时，只把所要写的字写入主存。 (2) 按写分配法：在写 Cache 不命中时，还把一个块从主存读入 Cache。 目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。 3.3.6 Cache 的预取算法 • 预取算法有如下几种： 1、按需取。在出现 Cache 不命中时，把一个块取到 Cache 中来。 2、恒预取。无论 Cache 是否命中，都把紧接着的下一块取到 Cache 中。 3、不命中预取。当 Cache 不命中，把本块和下一块取到 Cache 中。 • 主要考虑因素：命中率的提高和 Cache 与主存之间通信量的增加 从模拟实验的结果看： 采用恒预取能使 Cache 的不命中率降低 75～85％
采用不命中预取能使 Cache的不命中率降低30~40% 3.4三级存储系统 在大部分计算机系统中,既有虚拟存储器,也有 Cache存储系统 存储系统可以有多种构成方法。 不同的构成只是实现技术不同。 Cache 主存储器 主存储器「磁盘存储器 个系统程序员看: 个应用程序员看: 速度接近 Cache 速度接近主存储器, 存储容量等于主存, 存储容量是虚拟地址空间, 每位价格接近主存储器。 每位价格接近磁盘存储器。 Cache存储系统 虚拟存储系统 存储系统的几种组织方式 、两个存储系统的组织方式: 物理地址 Cache存储系统 目前的大部分处理机均采用这种两级存储系统。 虚拟地址」MMU物理地址」高速缓存物理地址 CPU Cache据或指创主存储器 数据或指令 物理地址 Cache存储系统 个存储系统组织方式 虚拟地址 Cache存储系统 如 Intel公司的i860等处理机采用这种组织方式 MMU CPU 主存储器 数据或推令 Cache I数据或指令 虚拟地址 Cache存储系统 3、全 Cache系统
3—4 采用不命中预取能使 Cache 的不命中率降低 30～40％。 3.4 三级存储系统 在大部分计算机系统中，既有虚拟存储器，也有 Cache 存储系统。 存储系统可以有多种构成方法。 不同的构成只是实现技术不同。 系统程序员看： 应用程序员看： 速度接近 Cache， 速度接近主存储器， 存储容量等于主存， 存储容量是虚拟地址空间， 每位价格接近主存储器。 每位价格接近磁盘存储器。 Cache 存储系统 虚拟存储系统 存储系统的几种组织方式： 1、两个存储系统的组织方式： 物理地址 Cache 存储系统 目前的大部分处理机均采用这种两级存储系统。 虚拟地址 MMU 物理地址 高速缓存 物理地址 CPU Cache 数据或指令 主存储器 数据或指令 物理地址 Cache 存储系统 2、一个存储系统组织方式： 虚拟地址 Cache 存储系统 如 Intel 公司的 i860 等处理机采用这种组织方式。 虚拟地址 MMU 物理地址 CPU 主存储器 数据或指令 Cache 数据或指令 虚拟地址 Cache 存储系统 3、全 Cache 系统。 Cache 主存储器 主存储器 磁盘存储器
没有主存储器,“ Cache一磁盘”存储系统。 Cache k主存储器k磁盘存储器 Cache k磁盘存储器 一种三级存储系统 种新的二级存储系统 3.4.1虚拟地址 Cache 虚拟存储器采用位选择组相联映象和地址变换方式 虚拟存储器中的一页恰好等于主存储器的一个区 用虚拟地址中的虚页号访问快表。 虛拟地址匚。虚页号P区内块号B块内地址W 「查快表了 按地址访问块表 读出区号 命中 修改组内块 地址比较1的使用状态 选择要替换保存虚地 修改快表页 的快表字 到页表中的使用状态 命中 中 未命中 把虚页号变 用实地址访问Cahe 换成实页号 访问主存 读出一块 调一页到主 存,并选择「用虚、实页 装入或替换选择一个字 要替换的页[号修改快表 送往CPU 种虚拟地址 Cache的地址变换过程 如果快表命中,把块表中的主存区号E与快表中的主存实页号P进行比较 若比较结果相等,则 Cache命中。 从块表中读出 Cache的组内块号b,并用B、b、W拼接得到 Cache地址。 若 Cache不命中,则用主存实页号P、及B和W拼接,得到主存实地址 如果快表没有命中,通过软件去查存放在主存中的慢表 3.4.2全 Cache存储系统 从系统结构看,存储系统的速度接近 Cache,容量等于虚拟地址空间
3—5 没有主存储器，“Cache—磁盘”存储系统。 3.4.1 虚拟地址 Cache 虚拟存储器采用位选择组相联映象和地址变换方式。 虚拟存储器中的一页恰好等于主存储器的一个区。 用虚拟地址中的虚页号访问快表。 虚拟地址 虚页号 P 区内块号 B 块内地址 W 查快表 按地址访问块表 读出区号 命中？ Y N 修改组内块 地址比较 的使用状态 选择要替换 保存虚地址 修改快表页 的快表字 到页表中 的使用状态 命中？ Y 命中 N 未命中 把虚页号变 换成实页号 用实地址 访问主存 访问 Cache 读出一块 调一页到主 存，并选择 要替换的页 用虚、实页 号修改快表 装入或替换 Cache 选择一个字 送往 CPU 一种虚拟地址 Cache 的地址变换过程 如果快表命中，把块表中的主存区号 E 与快表中的主存实页号 P 进行比较。 若比较结果相等，则 Cache 命中。 从块表中读出 Cache 的组内块号 b，并用 B、b、W 拼接得到 Cache 地址。 若 Cache 不命中，则用主存实页号 P、及 B 和 W 拼接，得到主存实地址。 如果快表没有命中，通过软件去查存放在主存中的慢表。 3.4.2 全 Cache 存储系统 从系统结构看，存储系统的速度接近 Cache，容量等于虚拟地址空间。 一种三级存储系统 一种新的二级存储系统 Cache 主存储器 磁盘存储器 Cache 磁盘存储器
这个存储器如何构成,具体分成几级来实现,只是具体的实现方法 随着硬件和软件技术的发展,存储系统的实现技术也在不断改变。 最直接的实现方法是:用一个速度很高,存储容量很大的存储器来实现。 全 Cache( all-Cache)存储系统是一种理想的存储系统。 多处理机系统中的一种全 Cache存储系统方案。 处理机P P2 IOP1… O 局部 Cache1 共享 Cache C 多处理机系统中的全 Cache存储系统 本章重点: 1、存储系统的定义及主要性能。 2、并行存储器和无冲突访问存储器的工作原理。 3、虚拟存储系统的工作原理。 4、虚拟存储器中加快地址变换的方法。 5、虚拟存储系统的页面替换算法。 6、 Cache存储系统的地址映象及变换方法 7、 Cache存储系统的块替换算法 8、 Cache存储系统的一致性问题 习题 3.23.53.83.133.143.203.23
3—6 这个存储器如何构成，具体分成几级来实现，只是具体的实现方法。 随着硬件和软件技术的发展，存储系统的实现技术也在不断改变。 最直接的实现方法是：用一个速度很高，存储容量很大的存储器来实现。 全 Cache（all-Cache）存储系统是一种理想的存储系统。 多处理机系统中的一种全 Cache 存储系统方案。 处理机 P1 P2 …… Pn IOP1 …… IOPm 局部Cache C1 C2 …… Cn Cio1 …… Ciom 共享Cache Cg 多处理机系统中的全 Cache 存储系统 本章重点： 1、存储系统的定义及主要性能。 2、并行存储器和无冲突访问存储器的工作原理。 3、虚拟存储系统的工作原理。 4、虚拟存储器中加快地址变换的方法。 5、虚拟存储系统的页面替换算法。 6、Cache 存储系统的地址映象及变换方法。 7、Cache 存储系统的块替换算法。 8、Cache 存储系统的一致性问题。 习题： 3.2 3.5 3.8 3.13 3.14 3.20 3.23