05 第5章 存储层次.pptx

第1页：存储层次封面

存储层次封面

存储层次

第2页：存储层次目录

存储层次目录

• 5.1 存储器的层次结构
• 5.2 Cache基本知识
• 5.3 降低Cache失效率的方法
• 5.4 减少Cache失效开销
• 5.5 减少命中时间
• 5.6 主存
• 5.7 虚拟存储器
• 5.8 进程保护和虚存实例
• 5.9 Alpha AXP

第3页：从用户的角度来看，存储器的三个主要指标

从用户的角度来看，存储器的三个主要指标

从用户的角度来看，存储器的三个主要指标

容量、速度和价格（指每位价格）

• 人们对这三个指标的要求容量大、速度快、价格低
• 三个要求是相互矛盾的
  • 速度越快，每位价格就越高；
  • 容量越大，每位价格就越低；
  • 容量越大，速度越慢。5.1.1从单级存储器到多级存储器

第4页：解决方法采用多种存储器技术

解决方法采用多种存储器技术

• 解决方法采用多种存储器技术，构成所谓的存储层次。演示Ⅰ演示Ⅱ(局部性原理)多级存储层次

第5页：H，TA假设

H，TA假设

H，TA假设

S ──容量TA──访问时间C ──每位价格下面仅考虑由M1和M2构成的两级存储层次：

第6页：每位价格C2.命中率H和失效率F

每位价格C2.命中率H和失效率F

命中率

CPU访问存储系统时，在M1中找到所需信息的概率。

失效率

F＝1－H

• 每位价格C2.命中率H和失效率F

第7页：平均访问时间TATA＝HTA1＋

平均访问时间TATA＝HTA1＋

失效开销TM

从向M2发出访问请求到把整个数据块调入M1中所需的时间。

• 平均访问时间TATA＝HTA1＋（1－H）（TA1＋TM）＝TA1＋（1－H）TM或TA＝TA1＋FTM分两种情况来考虑CPU的一次访存
  • 当命中时，访问时间即为TA1（命中时间）
  • 当不命中时，情况比较复杂。不命中时的访问时间为：TA2＋TB＋TA1＝TA1＋TMTM＝TA2＋TB
• 传送一个信息块所需的时间为TB。

第8页：“Cache－主存”层次

“Cache－主存”层次

“Cache－主存”层次

弥补主存速度的不足

• 主存与CPU的速度差距
• “Cache-主存”层次2.“主存－辅存”层次5.1.3“Cache－主存”和“主存－辅存”层次

第9页：1980年以来存储器和CPU性能随时间而

1980年以来存储器和CPU性能随时间而

• 1980年以来存储器和CPU性能随时间而提高的情况（以1980年时的性能作为基准）

第10页：存储器的层次结构

存储器的层次结构

第11页：级的访问方式比较项目目的存储管理实现访问

级的访问方式比较项目目的存储管理实现访问

• 级的访问方式比较项目目的存储管理实现访问速度的比值(第一级和第二级)典型的块(页)大小失效时CPU是否切换“Cache－主存”层次“主存－辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现主要由软件实现几比一几百比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其他进程“Cache－主存”与“主存－辅存”层次的区别

第12页：当把一个块调入高一层(靠近CPU)存储器

当把一个块调入高一层(靠近CPU)存储器

• 当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映像规则）
• 当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）
• 当发生失效时，应替换哪一块？（替换算法）
• 当进行写访问时，应进行哪些操作?（写策略）

第13页：存储空间分割与地址计算2.Cache和主

存储空间分割与地址计算2.Cache和主

全相联

主存中的任一块可以被放置到Cache中的任意一个位置。举例

对比

阅览室位置──随便坐

特点

空间利用率最高，冲突概率最低，实现最复杂。

• 存储空间分割与地址计算2.Cache和主存分块5.2 Cache的基本知识5.2.1映象规则1.全相联映象

第14页：Cache基本知识：识

Cache基本知识：识

• 识

第15页：识2.直接映象

识2.直接映象

直接映象

主存中的每一块只能被放置到Cache中唯一的一个位置。举例（循环分配）

对比

阅览室位置──只有一个位置可以坐

特点

空间利用率最低，冲突概率最高，实现最简单。

• 识2.直接映象
• 对于主存的第i块，若它映象到Cache的第j块，则j＝imod (M)（M为Cache的块数）

第16页：设M=2m，则当表示为二进制数时

设M=2m，则当表示为二进制数时

• 设M=2m，则当表示为二进制数时，j实际上就是i的低m位:ji：m位识

第17页：Cache基本知识：识

Cache基本知识：识

• 识

第18页：Cache基本知识：组相联映象

Cache基本知识：组相联映象

组相联

主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。举例

• 组相联映象
• 组相联是直接映象和全相联的一种折中

第19页：Cache基本知识：识

Cache基本知识：识

• 识
• 组的选择常采用位选择算法
  • 若主存第i块映象到第k组，则k＝imod（G）（G为Cache的组数）
  • 设G＝2g，则当表示为二进制数时，k实际上就是i的低g位:
• 低g位以及直接映象中的低m位通常称为索引。ki：g位

第20页：Cache基本知识：识

Cache基本知识：识

n路组相联

每组中有n个块(n＝M/G)。n称为相联度。相联度越高，Cache空间的利用率就越高，块冲突概率就越低，失效率也就越低。

绝大多数计算机的Cache:n≤4想一想

相联度一定是越大越好？全相联直接映象组相联n(路数)G(组数)MM111＜n＜M1＜G＜M

• 识

第21页：查找算法：识

查找算法：识

• 识
• 当CPU访问Cache时，如何确定Cache中是否有所要访问的块？
• 若有，如何确定其位置？1.通过查找目录表来实现
• 目录表的结构
  • 主存块的块地址的高位部分，称为标识。
  • 每个主存块能唯一地由其标识来确定

第22页：Cache基本知识：识

Cache基本知识：识

提高性能的重要思想

主候选位置(MRU块)（前瞻执行）3.并行查找的实现方法

• 识
• 只需查找候选位置所对应的目录表项2.并行查找与顺序查找
• 相联存储器
• 单体多字存储器＋比较器
  • 举例：４路组相联并行标识比较（比较器的个数及位数）
  • ４路组相联Cache的查找过程
  • 直接映象Cache的查找过程

第23页：Cache基本知识：识

Cache基本知识：识

• 识

第24页：识1.所要解决的问题

识1.所要解决的问题

识1.所要解决的问题

当新调入一块，而Cache又已被占满时，替换哪一块？

随机法优点

实现简单

• 直接映象Cache中的替换很简单因为只有一个块，别无选择。
• 在组相联和全相联Cache中，则有多个块供选择。2.主要的替换算法有三种
• 先进先出法（FIFO）

第25页：Cache基本知识：识

Cache基本知识：识

• 识
• 最近最少使用法LRU
  • 选择近期最少被访问的块作为被替换的块。（实现比较困难）
  • 实际上：选择最久没有被访问过的块作为被替换的块。
  • 优点：失效率低。
• LRU和随机法的失效率的比较

第26页：法分别因其失效率低和实现简单而被广泛采用

法分别因其失效率低和实现简单而被广泛采用

• 法分别因其失效率低和实现简单而被广泛采用。

第27页：识1.“写”在所有访存操作中所占的比例

识1.“写”在所有访存操作中所占的比例

“写”在所有访存操作中所占的比例

9％/(100％＋26％＋9％)≈7％

“写”在访问Cache操作中所占的比例

9％/(26％＋9％)≈25％

• 识1.“写”在所有访存操作中所占的比例
• 统计结果表明，对于一组给定的程序
  • load指令：26％
  • store指令：9％

第28页：Cache基本知识：识

Cache基本知识：识

• 识
• “写”操作必须在确认是命中后才可进行
• “写”访问有可能导致Cache和主存内容的不一致
• 两种写策略写策略是区分不同Cache设计方案的一个重要标志。
• 写直达法
  • 执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。
• 写回法（也称为拷回法）
  • 执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。(设置“修改位”)

第29页：识5.两种写策略的比较

识5.两种写策略的比较

写回法的优点

速度快，所使用的存储器带宽较低。

写直达法的优点

易于实现，一致性好。6.采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写停顿。

减少写停顿的一种常用的优化技术

采用写缓冲器

• 识5.两种写策略的比较

第30页：识7.“写”操作时的调块

识7.“写”操作时的调块

• 识7.“写”操作时的调块
• 按写分配(写时取)写失效时，先把所写单元所在的块调入Cache，再行写入。
• 不按写分配(绕写法)写失效时，直接写入下一级存储器而不调块。8.写策略与调块
• 写回法──按写分配
• 写直达法──不按写分配

第31页：Cache的结构：识例

Cache的结构：识例

识例

DEC的Alpha AXP21064中的内部数据Cache1.简介

容量

8KB

块大小

32B

块数

256

映象方法

直接映象

“写”策略

写直达

写缓冲器大小

4个块构

• 采用不按写分配

第32页：Cache的结构：结构图

Cache的结构：结构图

• 结构图

第33页：识3.工作过程

识3.工作过程

• 识3.工作过程
• “读”访问命中
• “写”访问命中
• 失效情况下的操作4.混合Cache与分离Cache
• 优缺点
• 失效率的比较

第34页：Cache基本知识数据表

Cache基本知识数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

识16 KB容量1 KB2 KB4 KB8 KB32 KB指令Cache3.06%失效率的比较64 KB128 KB数据Cache混合Cache2.26%1.78%1.10%0.64%0.39%0.15%0.02%24.61%20.57%15.94%10.19%6.47%4.82%3.77%2.88%13.34%9.78%7.24%4.57%2.87%1.99%1.36%0.95%

第35页：识1.失效率

识1.失效率

• 识1.失效率
• 与硬件速度无关
• 容易产生一些误导2.平均访存时间平均访存时间＝命中时间＋失效率×失效开销析

第36页：例5.1 假设Cache的命中时间为1个

例5.1 假设Cache的命中时间为1个

• 识例5.1假设Cache的命中时间为1个时钟周期，失效开销为50个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加1个时钟周期（因为混合Cache只有一个端口，无法同时满足两个请求，会导致结构冲突），根据表5.4所列的失效率，试问指令Cache和数据Cache容量均为16KB的分离Cache和容量为32KB的混合Cache相比，哪种Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？

第37页：述，约75%的访存为取指令。因此

述，约75%的访存为取指令。因此

• 述，约75%的访存为取指令。因此，分离Cache的总体失效率为：（75%×0.64%）＋（25%×6.47%）＝2.10%根据表5.4，容量为32KB的混合Cache的失效率略低一些，只有1.99%。平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间＝指令所占的百分比×（指令命中时间＋指令失效率×失效开销）＋数据所占的百分比×（数据命中时间＋数据失效率×失效开销）

第38页：Cache基本知识数据表

Cache基本知识数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

以，两种结构的平均访存时间分别为：平均访存时间分离＝75%×（1+0.64%×50）+25%×（1+6.47%×50）＝（75%×1.32）+（25%×4.325）＝0.990+1.059＝2.05平均访存时间混合＝75%×（1+1.99%×50）+25%×（1+1+1.99%×50）＝（75%×1.995）+（25%×2.995）＝1.496+0.749＝2.24因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构冲突。

第39页：识3.程序执行时间CPU时间＝

识3.程序执行时间CPU时间＝

• 识3.程序执行时间CPU时间＝（CPU执行周期数+存储器停顿周期数）×时钟周期时间其中
• 存储器停顿时钟周期数＝“读”的次数×读失效率×读失效开销＋“写”的次数×写失效率×写失效开销
• 存储器停顿时钟周期数＝访存次数×失效率×失效开销

第40页：例5.2 我们用一个和Alpha

例5.2 我们用一个和Alpha

• 识例5.2我们用一个和Alpha AXP类似的机器作为第一个例子。假设Cache失效开销为50个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0个时钟周期，访问Cache失效率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。解CPU时间＝IC×(CPIexe＋────────)×时钟周期时间存储器停顿周期数指令数

第41页：Cache基本知识数据表

Cache基本知识数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

e的失效后，性能为：CPU时间有cache＝IC×（2.0＋1.33×2 %×50）×时钟周期时间＝IC×3.33×时钟周期时间实际CPI：3.333.33/2.0 = 1.67(倍)CPU时间也增加为原来的1.67倍。但若不采用Cache,则：CPI＝2.0＋50×1.33＝68.5

第42页：识4.Cache失效对于一个CPI较小而

识4.Cache失效对于一个CPI较小而

• 识4.Cache失效对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的
• CPIexecution越低，固定周期数的Cache失效开销的相对影响就越大。
• 在计算CPI时，失效开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的失效开销较大，其CPI中存储器停顿这部分也就较大。因此Cache对于低CPI、高时钟频率的CPU来说更加重要。

第43页：例5.3

例5.3

识例5.3考虑两种不同组织结构的Cache

直接映象Cache和2路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设：(1)理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。(2)两种Cache容量均为64KB，块大小都是32字节。(3)图5.8说明，在组相联Cache中，必须增加一个多路选择器，用于根据标识匹配结果从相应组的块中选择所需的数据。因为CPU的速度直接与Cache命中的速度紧密相关，所以对于组相联Cache，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。

第44页：(4)这两种结构Cache的失效开销都是

(4)这两种结构Cache的失效开销都是

• (4)这两种结构Cache的失效开销都是70ns。（在实际应用中，应取整为整数个时钟周期）(5)命中时间为1个时钟周期，64KB直接映象Cache的失效率为1.4%，相同容量的2路组相联Cache的失效率为1.0%。

第45页：Cache基本知识：识

Cache基本知识：识

• 识

第46页：Cache基本知识：间为

Cache基本知识：间为

间为

平均访存时间＝命中时间＋失效率×失效开销因此，两种结构的平均访存时间分别是：平均访存时间1路＝2.0＋（0.014×70）＝2.98ns平均访存时间2路＝2.0×1.10＋（0.010×70）＝2.90ns2路组相联Cache的平均访存时间比较低。CPU时间＝IC×(CPIexe＋每条指令的平均存储器停顿周期数)×时钟周期时间＝IC×(CPIexe×时钟周期时间＋每条指令的平均存储器停顿时间)

第47页：Cache基本知识数据表

Cache基本知识数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

此：CPU时间1路＝IC×(2.0×2＋(1.3×0.014×70))＝5.27×ICCPU时间2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))＝5.31×IC5.31×ICCPU时间1路─────＝─────＝1.015.27×ICCPU时间2路直接映象Cache的平均性能好一些。

第48页：识1.平均访存时间＝命中时间＋失效率×失

识1.平均访存时间＝命中时间＋失效率×失

• 识1.平均访存时间＝命中时间＋失效率×失效开销2.可以从三个方面改进Cache的性能
• 降低失效率
• 减少失效开销
• 减少Cache命中时间3.下面介绍17种Cache优化技术
  • 8种用于降低失效率
  • 5种用于减少失效开销
  • 4种用于减少命中时间

第49页：三种失效(3C)

三种失效(3C)

• 三种失效(3C)
• 强制性失效(Compulsory miss)
  • 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。(冷启动失效，首次访问失效)
• 容量失效(Capacity miss )
  • 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。

第50页：冲突失效(Conflict miss)

冲突失效(Conflict miss)

• 冲突失效(Conflict miss)
  • 在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。(碰撞失效，干扰失效)2.三种失效所占的比例
• 图示I(绝对值)
• 图示Ⅱ(相对值)

第51页：降低Cache失效率的方法

降低Cache失效率的方法

第52页：降低Cache失效率的方法

降低Cache失效率的方法

第53页：降低Cache失效率的方法

降低Cache失效率的方法

• 可以看出
  • 相联度越高，冲突失效就越少；
  • 强制性失效和容量失效不受相联度的影响；
  • 强制性失效不受Cache容量的影响，但容量失效却随着容量的增加而减少；
  • 表中的数据符合2:1的Cache经验规则，即大小为N的直接映象Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。

第54页：减少三种失效的方法

减少三种失效的方法

• 减少三种失效的方法
  • 强制性失效：增加块大小，预取（本身很少）
  • 容量失效：增加容量（抖动现象）
  • 冲突失效：提高相联度（理想情况：全相联）
• 许多降低失效率的方法会增加命中时间或失效开销

第55页：失效率与块大小的关系

失效率与块大小的关系

• 失效率与块大小的关系
• 对于给定的Cache容量，当块大小增加时，失效率开始是下降，后来反而上升了。原因
  • 一方面它减少了强制性失效；
  • 另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突失效。
• Cache容量越大，使失效率达到最低的块大小就越大。

第56页：降低Cache失效率的方法

降低Cache失效率的方法

第57页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

各种块大小情况下Cache的失效率Cache容量（字节）块大小（字节）256K64K16K4K1K1.09%2.04%3.94%8.57%15.05%160.70%1.35%2.87%7.24%13.34%320.51%1.06%2.64%7.00%13.76%640.49%1.02%2.77%7.78%16.64%1280.49%1.15%3.29%9.51%22.01%256

第58页：增加块大小会增加失效开销例5.4假定存储

增加块大小会增加失效开销例5.4假定存储

• 增加块大小会增加失效开销例5.4假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节。即，经过42个时钟周期，它可提供16个字节；经过44个时钟周期，可提供32个字节；依此类推。请问对于表5.6中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？解解题过程1KB、4KB、16KB Cache:块大小＝32B64KB、256KB Cache:块大小＝64B

第59页：降低Cache失效率的方法：情况

降低Cache失效率的方法：情况

• 情况下Cache的平均访存时间Cache容量（字节）失效开销（时钟周期）块大小（字节）256K64K16K4K1K1.4581.8572.6554.5997.32142161.3081.8572.2634.1866.87044321.2451.5942.2674.3607.60548641.2741.5092.5515.35710.318561281.3531.5713.3697.84716.84772256

第60页：采用相联度超过8的方案的实际意义不大

采用相联度超过8的方案的实际意义不大

• 采用相联度超过8的方案的实际意义不大。2.2:1 Cache经验规则容量为N的直接映象Cache的失效率和容量为N/2的2路组相联Cache的失效率差不多相同。3.提高相联度是以增加命中时间为代价。例如
  • TTL或ECL板级Cache，2路组相联：增加10％
  • 定制的CMOS Cache, 2路组相联：增加2％

第61页：例5.5 假定提高相联度会按下列比例增大

例5.5 假定提高相联度会按下列比例增大

• 例5.5假定提高相联度会按下列比例增大处理器时钟周期：时钟周期2路＝1.10×时钟周期1路时钟周期4路＝1.12×时钟周期1路时钟周期8路＝1.14×时钟周期1路假定命中时间为一个时钟周期，直接映象情况下失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表5.5中的失效率，试问当Cache为多大时，以下不等式成立？平均访存时间8路<平均访存时间4路平均访存时间4路<平均访存时间2路平均访存时间2路<平均访存时间1路

第62页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

联度的情况下，平均访存时间分别为：平均访存时间8路=命中时间8路+失效率8路×失效开销8路= 1.14＋失效率8路×50平均访存时间4路= 1.12＋失效率4路×50平均访存时间2路= 1.10＋失效率2路×50平均访存时间1路= 1.00＋失效率1路×50把相应的失效率代入上式，即可得平均访存时间。例如，1KB的直接映象Cache的平均访存时间为：平均访存时间1路= 1.00＋0.133×50＝7.65128KB的8路组相联Cache的平均访存时间为：平均访存时间8路＝1.14＋0.006×50＝1.44

第63页：相联度（路）Cache容量84215.4

相联度（路）Cache容量84215.4

• 相联度（路）Cache容量84215.446.226.607.6514.094.624.905.9023.193.573.954.6042.592.873.003.3082.042.122.202.45161.791.771.802.00321.591.571.601.70641.441.421.451.50128在各种容量和相联度情况下Cache的平均访存时间

第64页：e容量不超过16KB时

e容量不超过16KB时

• e容量不超过16KB时，上述三个不等式成立。从32KB开始，对于平均访存时间有：4路组相联的平均访存时间小于2路组相联的;2路组相联的小于直接映象的;但8路组相联的却比4路组相联的大。

第65页：最直接的方法是增加Cache的容量

最直接的方法是增加Cache的容量

• 最直接的方法是增加Cache的容量
• 缺点:
  • 增加成本
  • 可能增加命中时间2.这种方法在片外Cache中用得比较多

第66页：一种能减少冲突失效次数而又不影响时钟频率

一种能减少冲突失效次数而又不影响时钟频率

• 一种能减少冲突失效次数而又不影响时钟频率的方法。2.基本思想
• 在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。
• 工作过程

第67页：m Cache在存储层次中的位置

m Cache在存储层次中的位置

• m Cache在存储层次中的位置

第68页：降低Cache失效率的方法：作用

降低Cache失效率的方法：作用

• 作用
• 对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。
• 例如项数为4的Victim Cache:能使4KBCache的冲突失效减少20%～90%

第69页：多路组相联的低失效率和直接映象的命中速度

多路组相联的低失效率和直接映象的命中速度

• 多路组相联的低失效率和直接映象的命中速度2.伪相联Cache的优点
• 命中时间小
• 失效率低联命中时间小命中时间大失效率高失效率低

第70页：基本思想及工作原理（动画演示）在逻辑上把

基本思想及工作原理（动画演示）在逻辑上把

• 基本思想及工作原理（动画演示）在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。4.快速命中与慢速命中要保证绝大多数命中都是快速命中。

第71页：例5.6 假设当在按直接映象找到的位置处

例5.6 假设当在按直接映象找到的位置处

• 例5.6假设当在按直接映象找到的位置处没有发现匹配，而在另一个位置才找到数据（伪命中）需要2个额外的周期。仍用上个例子中的数据，问：当Cache容量分别为2KB和128KB时，直接映象、2路组相联和伪相联这三种组织结构中，哪一种速度最快？解首先考虑标准的平均访存时间公式：平均访存时间伪相联＝命中时间伪相联＋失效率伪相联×失效开销伪相联

第72页：失效率伪相联＝失效率2路命中时间伪相联＝

失效率伪相联＝失效率2路命中时间伪相联＝

• 失效率伪相联＝失效率2路命中时间伪相联＝命中时间1路＋伪命中率伪相联×2伪相联查找的命中率等于2路组相联Cache的命中率和直接映象Cache命中率之差。伪命中率伪相联＝命中率2路－命中率1路＝（1－失效率2路）－（1－失效率1路）＝失效率1路－失效率2路综合上述分析，有：平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×2＋失效率2路×失效开销1路

第73页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

中的数据代入上面的公式，得：平均访存时间伪相联，2KB＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844平均访存时间伪相联，128KB＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356根据上一个例子中的表，对于2KBCache，可得：平均访存时间1路＝5.90个时钟平均访存时间2路＝4.90个时钟

第74页：128KB的Cache有，可得

128KB的Cache有，可得

128KB的Cache有，可得

平均访存时间1路＝1.50个时钟平均访存时间2路＝1.45个时钟可见，对于这两种Cache容量，伪相联Cache都是速度最快的。5.缺点：多种命中时间

第75页：指令和数据都可以预取

指令和数据都可以预取

1个块的指令流缓冲器

捕获15％～25％的失效

4个块的指令流缓冲器

捕获50％

16个块的指令流缓冲器

捕获72％

• 指令和数据都可以预取
• 预取内容既可放入Cache，也可放在外缓冲器中。例如：指令流缓冲器
• 指令预取通常由Cache之外的硬件完成
• 预取效果
• Joppi的研究结果
  • 指令预取(4KB，直接映象Cache，块大小＝16B)

第76页：数据预取(4KB,直接映象Cache)

数据预取(4KB,直接映象Cache)

1个数据流缓冲器

捕获25％的失效

• 数据预取(4KB,直接映象Cache)
• 还可以采用多个数据流缓冲器
• Palacharla和Kessler的研究结果
  • 流缓冲器：既能预取指令又能预取数据
  • 对于两个64KB四路组相联Cache来说
• 8个流缓冲器能捕获50％～70％的失效

第77页：例5.7 Alpha AXP 21064

例5.7 Alpha AXP 21064

• 例5.7Alpha AXP 21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，Alpha AXP 21064的指令Cache必须为多大才能保持平均访存时间不变？解假设当指令不在指令Cache里，而在预取缓冲器中找到时，需要多花一个时钟周期。下面是修改后的公式：平均访存时间预取＝命中时间＋失效率×预取命中率×1＋失效率×（1－预取命中率）×失效开销

第78页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

中率为25%，命中时间为2个时钟周期，失效开销为50个时钟周期。查表可知8KB指令Cache的失效率为1.10%。则：平均访存时间预取＝2＋（1.10 %×25 %×1）＋1.10 %×（1－25 %）×50＝2＋0.00275＋0.413＝2.415为了得到相同性能下的实际失效率，由原始公式得：平均访存时间＝命中时间＋失效率×失效开销失效率＝（平均访存时间－命中时间）/失效开销＝（2.415－2）/50＝0.83 %

第79页：入预取指令，在数据被用到之前发出预取请求

入预取指令，在数据被用到之前发出预取请求

寄存器预取

把数据取到寄存器中。

Cache预取

只将数据取到Cache中。

故障性预取

在预取时，若出现虚地址故障或违反保护权限，就会发生异常。

非故障性预取

在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。

• 入预取指令，在数据被用到之前发出预取请求。1.预取有以下几种类型

第80页：ache预取都是非故障性的

ache预取都是非故障性的

失效开销小时

循环体展开1～2次

失效开销大时

循环体展开许多次

• ache预取都是非故障性的，也称非绑定预取。
• 在预取数据的同时，处理器应能继续执行。只有这样，预取才有意义。非阻塞Cache (非锁定Cache)
• 编译器控制预取的目的使执行指令和读取数据能重叠执行。
• 循环是预取优化的主要对象

第81页：例5.8 对于下面的程序

例5.8 对于下面的程序

• 例5.8对于下面的程序，首先判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：(1)我们用的是一个容量为8KB、块大小为16B的直接映象Cache，它采用写回法并且按写分配。(2) a、b分别为3×100（3行100列）和101×3的双精度浮点数组，每个元素都是8B。当程序开始执行时，这些数据都不在Cache内。for（i = 0 ; i < 3 ; i = i + 1）for（j = 0 ; j < 100 ; j = j + 1）a [ i ][ j ] = b[ j ][ 0 ] * b[ j+1 ][ 0 ];

第82页：降低Cache失效率的方法：计算过程

降低Cache失效率的方法：计算过程

• 计算过程
• 失效情况总的失效次数＝251次
• 改进后的程序
  • 假设失效开销很大，预取必须至少提前7次循环进行。

第83页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

= 0; j < 100; j = j+1）{prefetch（b[ j+7 ][ 0 ]）;prefetch（a[ 0 ][ j+7 ]）;}for（i = 1; i < 3; i = i+1）{for（j = 0; j < 100; j = j+1）prefetch（a [ i ][ j+7 ]）;a [ i ][ j ] = b[ j ][ 0 ] * b[ j+1 ][ 0 ];}

第84页：失效情况总的失效次数＝19次

失效情况总的失效次数＝19次

• 失效情况总的失效次数＝19次

第85页：例5.9 在以下条件下

例5.9 在以下条件下

• 例5.9在以下条件下，计算例5.8中所节约的时间：(1)忽略指令Cache失效，并假设数据Cache无冲突失效和容量失效。(2)假设预取可以被重叠或与Cache失效重叠执行，从而能以最大的存储带宽传送数据。(3)不考虑Cache失效时，修改前的循环每7个时钟周期循环一次。修改后的程序中，第一个预取循环每9个时钟周期循环一次，而第二个预取循环每8个时钟周期循环一次（包括外层for循环的开销）。(4)一次失效需50个时钟周期。

第86页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

修改前：循环时间＝300×7＝2100失效开销＝251×50＝12550/146502100＋12550＝14650修改后：循环时间＝100×9＋200×8＝2500失效时间＝19×50＝9502500＋950＝3450加速比＝14650/3450＝4.2

第87页：在编译时，对程序中的指令和数据进行重新组

在编译时，对程序中的指令和数据进行重新组

• 在编译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。McFaring发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。
  • 2KB Cache:降低50％
  • 8KB Cache：降低75%数据对存储位置的限制比指令的少，因此更便于优化。

第88页：通过把数据重新组织

通过把数据重新组织

举例

int val [ SIZE ];int key [ SIZE ];

• 通过把数据重新组织，使得一块数据在被从Cache替换出去之前，能最大限度利用其中的数据(访问次数最多)。1.数组合并

第89页：*修改后*/struct merge {

*修改后*/struct merge {

• *修改后*/struct merge {int val ;int key ;} ;struct merge merged_array [ SIZE ];

第90页：降低Cache失效率的方法数据表

降低Cache失效率的方法数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

2.内外循环交换举例：for（j = 0 ; j < 100 ; j = j+1）for（i = 0 ; i < 5000 ; i = i+1）x [ i ][ j ] = 2 * x [ i ][ j ];for（i = 0 ; i < 5000 ; i = i+1）for（j = 0 ; j < 100 ; j = j+1）x [ i ][ j ] = 2 * x [ i ][ j ];

第91页：循环融合

循环融合

• 循环融合for（i = 0 ; i < N ; i = i+1）for（j = 0 ; j < N ; j = j+1）a [ i ][ j ] = 1/ b [ i ][ j ] * c [ i ][ j ];for（i = 0 ; i < N ; i = i+1）for（j = 0 ; j < N ; j = j+1）d [ i ][ j ] = a [ i ][ j ] + c [ i ][ j ];for（i = 0 ; i < N ; i = i+1）for（j = 0 ; j < N ; j = j+1）{a [ i ][ j ] = 1/ b [ i ][ j ] * c [ i ][ j ];d [ i ][ j ] = a [ i ][ j ] + c [ i ][ j ];}

第92页：分块把对数组的整行或整列访问改为按块进行

分块把对数组的整行或整列访问改为按块进行

• 分块把对数组的整行或整列访问改为按块进行。for（i = 0; i<N; i = i+1）for（j = 0; j < N; j = j+1）{r = 0;for（k = 0; k < N; k = k+1）{r = r + y[ i ][ k ] * z[ k ][ j ];}x[ i ][ j ] = r;}计算过程（失效次数：2N3＋N2）

第93页：降低Cache失效率的方法

降低Cache失效率的方法

第94页：*修改后*/

*修改后*/

• *修改后*/for（jj = 0; jj < N; jj = jj+B）for（kk = 0; kk < N; kk = kk+B）for（i = 0; i < N; i =i+1）for（j = jj; j < min（jj+B-1, N）; j = j+1）{r = 0;for（k = kk; k < min（kk+B-1, N）; k = k+1）{r = r + y[ i ][ k ] * z[ k ][ j ];}x[ i ][ j ] = x[ i ][ j ] + r;}计算过程(失效次数：2N3/B＋N2)

第95页：降低Cache失效率的方法

降低Cache失效率的方法

第96页：Cache中的写缓冲器导致对存储器访问的

Cache中的写缓冲器导致对存储器访问的

• Cache中的写缓冲器导致对存储器访问的复杂化写缓冲器进行的写入操作是滞后进行的，所以该缓冲器也被称为后行写数缓冲器。例5.10考虑以下指令序列：SW R3, 512（R0）；M[512]←R3（Cache索引为0）LW R1, 1024（R0）；R1←M[1024]（Cache索引为0）LW R2, 512（R0）；R2←M[512]（Cache索引为0）

第97页：解决问题的方法(读失效的处理)

解决问题的方法(读失效的处理)

推迟对读失效的处理（缺点

读失效的开销增加，如50％）

• 解决问题的方法(读失效的处理)
• 检查写缓冲器中的内容3.在写回法Cache中，也可采用写缓冲器。5.4.2写缓冲合并1.提高写缓冲器的效率2.写直达Cache依靠写缓冲来减少对下一级存储器写操作的时间。

第98页：如果写缓冲器为空，就把数据和相应地址写入

如果写缓冲器为空，就把数据和相应地址写入

• 如果写缓冲器为空，就把数据和相应地址写入该缓冲器。从CPU的角度来看，该写操作就算完成了。
• 如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。
• 如果写缓冲器满且又没有能进行写合并的项，就必须等待。提高了写缓冲器的空间利用率，而且还能减少因写缓冲器满而要进行的等待时间。

第99页：减少Cache失效开销

减少Cache失效开销

第100页：请求字从下一级存储器调入Cache的块中

请求字从下一级存储器调入Cache的块中

尽早重启动

调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。

请求字优先

调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。

• 请求字从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。2.应尽早把请求字发送给CPU

第101页：这种技术在以下情况下效果不大

这种技术在以下情况下效果不大

• 这种技术在以下情况下效果不大
  • Cache块较小
  • 下一条指令正好访问同一Cache块的另一部分

第102页：非阻塞Cache

非阻塞Cache

非阻塞Cache

Cache失效时仍允许CPU进行其他的命中访问。即允许“失效下命中”。2.进一步提高性能：

• “多重失效下命中”
• “失效下失效”（存储器必须能够处理多个失效）3.重叠失效个数对平均访问时间的影响

第103页：

第104页：例5.11 对于上图描述的Cache

例5.11 对于上图描述的Cache

• 例5.11对于上图描述的Cache，在2路组相联和“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？假设8KB数据Cache的平均失效率为：对于浮点程序，直接映象Cache为11.4%，而2路组相联Cache为10.7%；对于整数程序，直接映象Cache为7.4%，2路组相联Cache为6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期。

第105页：减少Cache失效开销数据表

减少Cache失效开销数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

，平均存储器等待时间为：失效率直接映象×失效开销＝11.4 %×16＝1.84失效率2路组相联×失效开销＝10.7 %×16＝1.711.71/1.84≈0.93对于整数程序：失效率直接映象×失效开销＝7.4 %×16＝1.18失效率2路组相联×失效开销＝6.0 %×16＝0.960.96/1.18≈0.81“失效下命中”方法有一个潜在优点：它不会影响命中时间，而组相联却会。

第106页：应把Cache做得更快？还是更大？答案

应把Cache做得更快？还是更大？答案

应把Cache做得更快？还是更大？答案

二者兼顾，再增加一级Cache

第107页：局部失效率与全局失效率

局部失效率与全局失效率

• 局部失效率与全局失效率
• 局部失效率＝该级Cache的失效次数/到达该级Cache的访问次数例如：上述式子中的失效率L2
• 全局失效率＝该级Cache的失效次数/CPU发出的访存的总次数
• 全局失效率L2＝失效率L1×失效率L2评价第二级Cache时，应使用全局失效率这个指标。它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。

第108页：例5.12 假设在1000次访存中

例5.12 假设在1000次访存中

• 例5.12假设在1000次访存中，第一级Cache失效40次，第二级Cache失效20次。试问：在这种情况下，该Cache系统的局部失效率和全局失效率各是多少？解第一级Cache的失效率（全局和局部）是40/1000，即4%；第二级Cache的局部失效率是20/40，即50%；第二级Cache的全局失效率是20/1000，即2%。

第109页：对于第二级Cache

对于第二级Cache

• 对于第二级Cache，我们有以下结论
• 在第二级Cache比第一级Cache大得多的情况下，两级Cache的全局失效率和容量与第二级Cache相同的单级Cache的失效率非常接近。
• 局部失效率不是衡量第二级Cache的一个好指标，因此，在评价第二级Cache时，应用全局失效率这个指标。5.第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间。
• 两个问题

第110页：它能否降低CPI中的平均访存时间部分？

它能否降低CPI中的平均访存时间部分？

• 它能否降低CPI中的平均访存时间部分？
  • 它的成本是多少？6.第二级Cache的参数
• 容量第二级Cache的容量一般比第一级的大许多。如512KB，1024KB
• 相联度第二级Cache可采用较高的相联度或伪相联方法。

第111页：例5.13 给出有关第二级Cache的以

例5.13 给出有关第二级Cache的以

• 例5.13给出有关第二级Cache的以下数据
  • 2路组相联使命中时间增加10%×CPU时钟周期
  • 对于直接映象，命中时间L2＝10个时钟周期
  • 对于直接映象，局部失效率L2＝25%
  • 对于2路组相联，局部失效率L2＝20%
  • 失效开销L2＝50个时钟周期试问第二级Cache的相联度对失效开销的影响如何？

第112页：象的第二级Cache来说

象的第二级Cache来说

• 象的第二级Cache来说，第一级Cache的失效开销为：失效开销直接映象，L1＝10＋25%×50＝22.5个时钟周期对于2路组相联第二级Cache来说，命中时间增加了10%（0.1）个时钟周期，故第一级Cache的失效开销为：失效开销2路组相联，L1＝10.1＋20%×50＝20.1个时钟周期把第二级Cache的命中时间取整，得10或11，则：失效开销2路组相联，L1＝10＋20%×50＝20.0个时钟周期失效开销2路组相联，L1＝11＋20%×50＝21.0个时钟周期故对于第二级Cache来说，2路组相联优于直接映象。

第113页：减少Cache失效开销：块大小

减少Cache失效开销：块大小

• 块大小
  • 第二级Cache可采用较大的块如64B、128B、256B
  • 为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。
  • 多级包容性需要考虑的另一个问题：第一级Cache中的数据是否总是同时存在于第二级Cache中。

第114页：命中时间直接影响到处理器的时钟频率

命中时间直接影响到处理器的时钟频率

• 命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率。5.5减少命中时间5.5.1容量小、结构简单的Cache1.硬件越简单，速度就越快。2.应使Cache足够小，以便可以与CPU一起放在同一块芯片上。

第115页：减少命中时间：案

减少命中时间：案

案

把Cache的标识放在片内，而把Cache的数据存储器放在片外。5.5.2虚拟Cache1.虚拟Cache访问Cache的索引以及Cache中的标识都是虚拟地址(一部分)。2.物理Cache使用物理地址的传统Cache。

第116页：并非都采用虚拟Cache(为什么?)

并非都采用虚拟Cache(为什么?)

PIDs与单进程相比

＋0.3％～＋0.6％

PIDs与清空相比

－0.6％～－4.3%

同义和别名解决方法

反别名法、页着色

• 并非都采用虚拟Cache(为什么?)
• 虚拟Cache的清空问题
  • 解决方法：在地址标识中增加PID字段(进程标识符)
  • 三种情况下失效率的比较
• 单进程，PIDs，清空

第117页：减少命中时间

减少命中时间

第118页：虚拟索引＋物理标识

虚拟索引＋物理标识

优点

兼得虚拟Cache和物理Cache的好处

局限性

Cache容量受到限制(页内位移)Cache容量≤页大小×相联度5.举例：IBM3033的Cache

• 虚拟索引＋物理标识
• 页大小＝4KB相联度＝16页地址地址标识页内位移索引块内位移3112 110

第119页：Cache容量＝16×4KB＝64KB6

Cache容量＝16×4KB＝64KB6

• Cache容量＝16×4KB＝64KB6.另一种方法：硬件散列变换5.5.3 Cache访问流水化1.对第一级Cache的访问按流水方式组织2.访问Cache需要多个时钟周期才可以完成例如
  • Pentium访问指令Cache需要一个时钟周期
  • Pentium Pro到Pentium Ⅲ需要两个时钟周期
  • Pentium 4则需要4个时钟周期

第120页：开发指令级并行性所遇到的一个挑战是

开发指令级并行性所遇到的一个挑战是

开发指令级并行性所遇到的一个挑战是

当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的。2.一个解决方法：采用Trace Cache存放CPU所执行的动态指令序列包含了由分支预测展开的指令，该分支预测是否正确需要在取到该指令时进行确认。e

第121页：减少命中时间：优缺点

减少命中时间：优缺点

• 优缺点
  • 地址映象机制复杂。
  • 相同的指令序列有可能被当作条件分支的不同选择而重复存放。
  • 能够提高指令Cache的空间利用率。5.5.5 Cache优化技术总结
  • “＋”号：表示改进了相应指标。
  • “－”号：表示它使该指标变差。
  • 空格栏：表示它对该指标无影响。
  • 复杂性：0表示最容易，3表示最复杂。

第122页：说明硬件复杂度命中时间失效开销失效率优化

说明硬件复杂度命中时间失效开销失效率优化

• 说明硬件复杂度命中时间失效开销失效率优化技术实现容易；Pentium 4的第二级Cache采用了128 B的块0+增加块大小被广泛采用，特别是第二级Cache+增加Cache容量被广泛采用1+提高相联度AMD Athlon采用了8个项的Victim Cache2+Victim CacheMIPS R10000的第二级Cache采用2+伪相联Cache许多机器预取指令，UltraSPARC Ⅲ预取数据2～3+硬件预取指令和数据Cache优化技术总结

第123页：说明硬件复杂度命中时间失效开销失效率优化

说明硬件复杂度命中时间失效开销失效率优化

• 说明硬件复杂度命中时间失效开销失效率优化技术需同时采用非阻塞Cache；有几种微处理器提供了对这种预取的支持3+编译器控制的预取向软件提出了新要求；有些机器提供了编译器选项0+用编译技术减少Cache失效次数在单处理机上实现容易，被广泛采用1+使读失效优先于写与写直达合用，广泛应用，例如21164，UltraSPARCⅢ1+写缓冲归并被广泛采用2+尽早重启动和关键字优先在支持乱序执行的CPU中使用3+非阻塞Cache

第124页：说明硬件复杂度命中时间失效开销失效率优化

说明硬件复杂度命中时间失效开销失效率优化

• 说明硬件复杂度命中时间失效开销失效率优化技术硬件代价大；两级Cache的块大小不同时实现困难；被广泛采用2+两级Cache实现容易，被广泛采用0+容量小且结构简单的Cache对于小容量Cache来说实现容易，已被Alpha21164和UltraSPARC Ⅲ采用2+对Cache进行索引时不必进行地址变换被广泛采用1+流水化Cache访问Pentium 4采用3+Trace Cache

第125页：主存的主要性能指标

主存的主要性能指标

主存的主要性能指标

延迟和带宽

现在

Cache关心两者

• 以往
  • Cache主要关心延迟，I/O主要关心带宽。
• 下面讨论几种能提高主存性能的存储器组织技术
  • 我们以处理Cache失效为例来说明各种存储器组织结构的好处。

第126页：在下面的讨论中，假设基本存储器结构的性能

在下面的讨论中，假设基本存储器结构的性能

• 在下面的讨论中，假设基本存储器结构的性能为
  • 送地址需要4个时钟周期
  • 每个字的访问时间为24个时钟周期
  • 传送一个字（32位）的数据需4个时钟周期如果Cache块大小为4个字，则
  • 失效开销为4×（4＋24＋4）＝128个时钟周期
  • 存储器的带宽为每个时钟周期1/8（16/128）字节

第127页：增加存储器的宽度

增加存储器的宽度

• 增加存储器的宽度
• 性能举例(参照前面的假设)
  • 当宽度为4个字时
• 失效开销＝1×32(周期)
• 带宽＝0.5(字节/周期)
• 缺点
  • 增加CPU和存储器之间的连接通路的宽度
  • CPU和Cache之间有一个多路选择器
  • 扩充主存的最小增量增加了相应的倍数
  • 写入有可能变得复杂
• 举例
  • DEC的Alpha Axp21064：256位宽

第128页：主存

主存

第129页：采用简单的多体交叉存储器

采用简单的多体交叉存储器

性能举例

(参照前面的假设)

• 采用简单的多体交叉存储器
• 在存储系统中采用多个DRAM，并利用它们潜在的并行性。
• 存储器的各个体一般是按字交叉的交叉存储器（interleaved memory）
  • 通常是指存储器的各个体是按字交叉的
  • 字交叉存储器非常适合于处理：Cache读失效，写回法Cache中的写回

第130页：主存

主存

第131页：主存数据表

主存数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

叉的，即存储体0中每个字的地址对4取模都是0，体1中每个字的地址对4取模都是1，依此类推。04812地址体015913地址体1261014地址体2371115地址体3

第132页：例5.14

例5.14

• 例5.14假设某台计算机的特性及其Cache的性能为：(1)块大小为1个字；(2)存储器总线宽度为1个字；(3) Cache失效率为3%；(4)平均每条指令访存1.2次；(5) Cache失效开销为32个时钟周期；(6)平均CPI（忽略Cache失效）为2。试问多体交叉和增加存储器宽度对提高性能各有何作用？

第133页：为2个字时，失效率降为2%

为2个字时，失效率降为2%

• 为2个字时，失效率降为2%；块大小变为4个字时，失效率降为1%。根据前面给出的访问时间，求在采用2路、4路多体交叉存取以及将存储器和总线宽度增加一倍时，性能分别提高多少？解在改变前的计算机中，Cache块大小为一个字，其CPI为：2＋（1.2×3%×32）= 3.15
• 当将块大小增加为2个字时，在下面三种情况下的CPI分别为
  • 32位总线和存储器，不采用多体交叉：2＋（1.2×2%×2×32）＝3.54

第134页：主存数据表

主存数据表

本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。

32位总线和存储器，采用多体交叉：2＋1.2×2%×（4＋24＋8）＝2.86性能提高了10%64位总线和存储器，不采用多体交叉：2＋（1.2×2%×1×32）= 2.77性能提高了14%将块大小增加到4个字节，可以得到以下数据：32位总线和存储器，不采用多体交叉：2＋（1.2×1%×4×32）＝3.5432位总线和存储器，采用多体交叉：2＋1.2×1%×（4＋24＋16）＝2.53性能提高了25%

第135页：64位总线和存储器，不采用多体交叉

64位总线和存储器，不采用多体交叉

64位总线和存储器，不采用多体交叉

2＋（1.2×1%×2×32）= 2.77性能提高了14%

• 存储器中应该含有多少个体呢？向量计算机采用以下衡量标准：体的数目≥访问体中一个字所需的时钟周期数
  • 存储系统的设计目标对于顺序访问，每个时钟周期都能从一个存储体中送出一个数据。

第136页：主存：独立存储体

主存：独立存储体

• 独立存储体
• 设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存。
• 例如
  • 一台输入设备可能会使用某个存控，访问某个存储体；
  • Cache读操作可能在使用另一个存控，访问另一个存储体；
  • Cache写操作则可能在使用第三个存控，访问第三个存储体。
• 每个体需要有独立的地址线和独立的数据总线。

第137页：非阻塞Cache与多体结构

非阻塞Cache与多体结构

体冲突

两个请求要访问同一个体。

减少体冲突次数的一种方法

采用许多体例如，NEC SX/3最多可使用128个体

• 非阻塞Cache与多体结构
• 采用多体结构的另一个原因共享公共存储器多处理机系统的需求
• 独立存储体和按字交叉的多体结合起来使用
  • 将存储器分为若干个独立的存储体；
  • 而每个独立存储体内部又划分为若干个按字交叉方式工作的体。4.避免存储体冲突

第138页：假如有128个存储体

假如有128个存储体

• 假如有128个存储体，按字交叉方式工作，并执行以下程序：int x [ 256 ][ 512 ]；for（j = 0；j < 512；j = j+1）for（i = 0；i < 256；i = i+1）x [ i ][ j ] = 2 * x [ i ][ j ]；因为512是128的整数倍，同一列中的所有元素都在同一个体内，无论CPU或存储系统多么高级，该程序都会在数据Cache失效时暂停。

第139页：解决体冲突的方法

解决体冲突的方法

• 解决体冲突的方法
  • 软件方法(编译器)
• 循环交换优化
• 扩展数组的大小，使之不是2的幂
  • 硬件方法
• 使体数为素数体内地址＝地址mod (存储体中的字数)可以直接截取
• 举例

第140页：体内地址存储体顺序交叉取模交叉01234

体内地址存储体顺序交叉取模交叉01234

• 体内地址存储体顺序交叉取模交叉012345顺序交叉和取模交叉的地址映象举例670 1 20 1 20 1 20 16 83 4 56 7 89 10 1112 13 1421 22 2315 16 1718 19 209 1 1718 10 23 19 1112 4 2021 13 56 22 1415 7 23

第141页：DRAM专用交叉结构

DRAM专用交叉结构

• DRAM专用交叉结构
• 介绍几种利用DRAM特性的技术
• 对DRAM的访问分为行访问和列访问
• 三种优化方式
  • Nibble方式：每次进行行访问时，DRAM除能够给出所需的位以外，还能给出其后的3位。
  • Page方式：缓冲器以SRAM的方式工作：通过改变列地址，可以随机地访问缓冲器内的任一位。
  • Static column方式：和Page方式类似，只是在列地址改变时，无需触发列访问选通线。

第142页：虚拟存储器是“主存－辅存”层次进一步发展

虚拟存储器是“主存－辅存”层次进一步发展

虚拟存储器可以分为两类

页式和段式

映象规则

全相联

查找算法

页表，段表，TLB

替换算法

LRU

写策略

写回法

• 虚拟存储器是“主存－辅存”层次进一步发展的结果。
• 有关虚拟存储器的四个问题

第143页：用页表实现虚拟地址到物理地址的映射

用页表实现虚拟地址到物理地址的映射

• 用页表实现虚拟地址到物理地址的映射

第144页：5.7.2快表（TLB）1.地址变换缓冲

5.7.2快表（TLB）1.地址变换缓冲

• 5.7.2快表（TLB）1.地址变换缓冲器TLB
• TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项；
• TLB中的内容是页表部分内容的一个副本；
• TLB也利用了局部性原理。2.Alpha Axp 21064的地址转换过程3.TLB一般比Cache的标识存储器更小、更快

第145页：虚拟存储器

虚拟存储器

第146页：最简单的保护机制是用一对寄存器来检查每一

最简单的保护机制是用一对寄存器来检查每一

检测条件

基地址≤地址≤上界地址5.8进程保护与虚存实例进程：程序呼吸的空气和生存的空间。也就是说，一个正在运行的程序加上它继续执行所需的任何状态就是进程。

• 最简单的保护机制是用一对寄存器来检查每一个地址，以确保地址在两个界限之间。
• 基地址上界地址

第147页：进程保护和虚存实例：例

进程保护和虚存实例：例

• 例
• 在有些系统中，地址被看作是无符号的整数。检测条件就变为：（基地址＋地址）≤上界地址2.计算机硬件设计者为操作系统设计者提供支持
• 提供至少两种模式
  • 区分正在运行的进程是用户进程还是操作系统进程
  • 称后者为内核进程、超级用户进程或管理进程
• 使CPU状态的一部分成为用户进程，可读但不可写包括：基地址/上界地址寄存器用户/管理模式位异常许可/禁止位

第148页：进程保护和虚存实例：例

进程保护和虚存实例：例

• 例
• 提供一种机制，使得CPU能从用户模式进入管理模式和从管理模式进入用户模式3.虚拟存储器
• 给每个页或段增加许可标志4.环形保护5.加锁和解锁

第149页：体系结构采用段页相结合的方式

体系结构采用段页相结合的方式

Alpha的页表项(PTE)例

Alpha Axp的存储管理和21064的TLB

• 体系结构采用段页相结合的方式1.Alpha的地址空间分为3段
  • kseg(地址最高两位：10) (内核)
  • seg0(最高位：0) (用户)
  • seg1(最高两位：11) (用户)
• sego和seg1的布局2.Alpha采用三级页表
• 地址变换过程

第150页：进程保护和虚存实例：例

进程保护和虚存实例：例

• 例

第151页：进程保护和虚存实例：例

进程保护和虚存实例：例

• 例

第152页：例3 .Alpha AXP 21064

例3 .Alpha AXP 21064

• 例3.Alpha AXP 21064 TLB的存储层次参数参数描述块大小命中时间平均失效开销TLB容量块替换策略写策略块映象策略1 PTE (8B)1个时钟周期20 PTE (8B)随机不适用全相联指令TLB：8个PTE用于大小为8KB的页，4个PTE用于大小为4MB的页(共96B)数据TLB：32个PTE用于大小为8KB、64KB、512KB何4MB的页(共256个字节)

第153页：简介2.工作过程P 21064存储层次

简介2.工作过程P 21064存储层次

• 简介2.工作过程P 21064存储层次

第154页：