第五章 存储层次 5.1 存储器的层次结构 5.2 高速缓冲存储器基本知识 5.3 降低Cache不命中率的方法

Presentation on theme: "第五章 存储层次 5.1 存储器的层次结构 5.2 高速缓冲存储器基本知识 5.3 降低Cache不命中率的方法"— Presentation transcript:

1 第五章 存储层次 5.1 存储器的层次结构 5.2 高速缓冲存储器基本知识 5.3 降低Cache不命中率的方法
5.1 存储器的层次结构 5.2 高速缓冲存储器基本知识 5.3 降低Cache不命中率的方法 5.4 减少Cache不命中开销 5.5 减少Cache命中时间 5.6 主存 5.7 虚拟存储器 在程序执行过程中，中央控制器所需要的指令从存储器中取。 运算器所需要的原始数据要通过程序中的访问存储器指令从存储器中取。 运算结果在程序执行完成之前必须全部写到存储器中。 各种输入输出设备也直接与存储器交换数据。 在计算机运行过程中，存储器是各种信息存储和交换的中心。

2 5.1 存储器的层次结构 一.存储系统的基本构成 存储系统由两部分构成: 1. 存放程序和数据的存储器 2. 控制存储器工作的存储控制部件
其中, 控制部件包括硬件设备和软件程序。 处理机 存储器 控制器 M1 M2 Mn (T1,S1,C1) (T2,S2,C2) (Tn,Sn,Cn) ，价格降低 容量增大 速度提高

3 5.1 存储器的层次结构 二. 存储系统的性能指标 1.存储容量S 评价存储系统性能的主要指标有三个，即速度T、容量S、和价格C。
存储系统的容量是处理机能直接寻址的存储器容量。 (T1,S1,C1) M1 M2 (T2,S2,C2) 处理机 存储系统 由两个存储体构成的存储系统

4 5.1 存储器的层次结构 2.单位容量的平均价格C 3. 访问周期T 存储系统每位的平均价格为： 其中，S为容量，C为单位容量价格。
也被称为平均访存时间或等效访问时间等。 命中率H被定义为CPU产生的逻辑地址能在M1中访问到（命中）的概率。

5 5.1 存储器的层次结构 精心选择一组有代表性的程序，在执行过程中分别统计对M1存储器的访问成功次数N1和对M1存储器访问不成功的次数N2，则命中率H为： 不命中率F：也称为失效率，是指CPU访存时，在M1中找不到所需信息的概率。

6 平均访存时间T 一般分两种情况来考虑CPU的一次访存： 1）当命中时，访问时间即为T1（命中时间）。
2）当不命中时，在大多数二级存储系统中，若访问的字不在M1中，就必须从M2中把包含所要访问的字的块传送到M1，之后CPU才可在M1中访问到这个字。假设TM为不命中开销，即从向M2发出访问请求到把整个数据块调入M1中所需的时间。则该存储系统的平均访存时间为：

7 0.25ns 1ns 100ns 8ms 存储器的层次结构 CPU内部 通用寄存器堆 第一层 存储容量递增并每位价格递减方向
第四层 CPU内部 通用寄存器堆 指令与数据缓冲栈 高速缓冲存储器 第一层 第二层 第三层 主存储器 ( DRAM ) 联机外部存储器 ( 硬磁盘机 ) 脱机外部存储器 (磁带、光盘存储器等) 第五层 第六层 访问速度递增方向 存储容量递增并每位价格递减方向 0.25ns 1ns 100ns 8ms

8 5.1 存储器的层次结构 三. 层次式存储系统 局部性原理是解决问题的基本思路
1980年以来存储器和CPU性能随时间而提高的情况（以1980年时的性能作为基准） 局部性原理是解决问题的基本思路

9 5.1 存储器的层次结构 局部性原理：从大量的统计中得到的一个规律是，程序中对于存储空间90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在存储空间的其余90%的区域中。这就是通常说的局部性原理。访存的局部性规律包括两个方面： 时间局部性:如果一个存储项被访问,则该存储项可能很快再次被访问. 空间局部性:如果一个存储项被访问,则该项及其相邻项可能很快被一起访问. 解决思路： 时间局部——把经常用的放入M1（快速的） 空间局部——把相邻的放入M1

10 5.1 存储器的层次结构 1.“Cache—主存”层次 目的：弥补主存速度的不足 2.“主存—辅存”层次 目的：弥补主存容量的不足

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

12 5.1 存储器的层次结构 由此，形成了两种存储系统： Cache存储系统：由Cache和主存储器构成
虚拟存储系统：由主存储器和磁盘存储器构成

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

14 5.2 高速缓冲存储器（Cache） Cache具有与CPU相匹配的存取速度，是界于CPU和主存之间的一个子系统。 一. 基本概念
根据其结构可分为： 1.一体化Cache 指程序和数据公用一个Cache。 2. 分离Cache 指程序和数据高速缓冲存储器分别独立设置。

15 5.2 高速缓冲存储器（Cache） 二. 基本工作原理 主存储器 块号B 块内地址W 主存-Cache 地址变换 命中 未命中 块号b
替换算法 已满 未满 调出块 装入块 一个字数据 送CPU 地址 来自CPU 主存地址 Cache地址

16 5.2 高速缓冲存储器（Cache） 三.地址映象与地址变换 地址映象
是指把主存储器地址空间映象到Cache地址空间，具体地说，就是把存放在主存储器中的指令和数据按照某种规则装入Cache中，并建立主存储器地址与Cache地址之间的对应关系。 地址变换 则是指当程序已经装入到Cache中之后，在实际运行过程中，将主存储器地址转换为Cache地址的过程。

17 5.2 高速缓冲存储器（Cache） 1．全相联映象及变换 全相联映象方式 主存储器中的任意一块可以映象到Cache中的任意一块上。 块0
块1 ┇ 块N-1 主存储器 块M-1 块i 主存储器中的任意一块可以映象到Cache中的任意一块上。

18 5.2 高速缓冲存储器（Cache） 全相联映象方式的地址变换过程 命中 Cache地址 主存地址 相联比较 目录表（存放在相联存储器中）
块号B 块内地址W 块号b 块内地址w B b 1 主存块号B Cache块号b 有效位 为“1”，表示映象关系有效；为“0”，表示映象关系无效。

19 5.2 高速缓冲存储器（Cache） 当CPU要访问Cache时送出主存地址，Cache的控制逻辑用主存地址中的块号B与目录表中的主存块号字段进行相联比较。 如果发现有相等的，表示要访问的数据已经被装入到Cache里了，称为命中。 如果在相联比较中没有发现相等，表示要访问的那个块不在Cache中，也称为未命中。 优点：块冲突小，控制简单，Cache的利用率高。 缺点：需相联存储器。

20 5.2 高速缓冲存储器（Cache） 2．直接映象方式及其地址变换 直接映象方式 主存储器 区0 块N Cache 块N+1 块0 区1
块1 块N-1 块N 块N+1 块2N-1 块KN 块KN+1 块(K+1)N-1 区0 区1 区K Cache 主存储器

21 5.2 高速缓冲存储器（Cache） 直接映象方式的地址变换过程 区号 区表存储器 相等 有效位 E 1 相等比较 区号E 块号B
块内地址W 块内地址w 块号b 主存地址 Cache地址 块失效 若比较结果相等且有效位为“1”， 则用Cache地址访问Cache。 读出的数据送CPU。

22 5.2 高速缓冲存储器（Cache） Cache地址与主存地址的低位完全相同。 需增加：区表存储器。
优点：硬件实现简单，不需相联存储器，并且只需比较区号，速度较快。 缺点：块的冲突率较高。

23 5.2 高速缓冲存储器（Cache） 3．组相联映象及其地址变换 组相联映象方式 主存储器 Cache 块0 区0 组0 块V-1 块V
块(K-1)V 块KV-1 组0 组1 组K-1 区0 块(t-1)×KV 块(t-1)×KV+V-1 块(t-1)×KV+V 块(t-1)×KV+2V-1 块(tK-1)V 块tKV-1 组(t-1)K 组(t-1)K+1 组tK-1 区t-1 主存储器 Cache

24 5.2 高速缓冲存储器（Cache） 组相联映象方式的地址变换过程 块表 区号E 组号G 组内块号B 块内地址W 主存地址 Cache地址
相等比较 不等 相等 V个字

25 5.2 高速缓冲存储器（Cache） 分组方式并不改变主存与Cache之间以块为单位调入调出的基本操作方式。 增加：块表存储器。
优点：块的冲突率大大降低，块的利用率大大提高，并且实现比全相联方式容易。

26 5.2 高速缓冲存储器（Cache） 四. Cache置换策略
Cache的容量总是比主存储器小得多，因此，必然会出现CPU需要访问的数据不在Cache中的情况。这时，就要从主存中调入新的数据块。如果这时可以装入新块的几个Cache块都已经装满时，就必须淘汰其中某块中的数据以装入新数据，选择被淘汰块的方法称为Cache置换策略（替换算法）。 在直接映象方式下，不存在块替换的算法，因为每一块的位置映象是固定的，需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题，就是要选择替换到哪一个Cache块。 置换策略直接影响Cache—主存体系的命中率。

27 5.2 高速缓冲存储器（Cache） 1．随机法 2．先进先出法（FIFO）
随机数产生器产生一个随机数，以此确定要被替换的块。 2．先进先出法（FIFO） 这种算法的思想是这样的，不管已调入块的使用频率如何，选择最早调入的块作为替换的对象。 3．最近最少使用法（LRU） 这种算法又称为最久未使用法。选择近期最久没有被访问的块作为被替换的块.

28 5.2 高速缓冲存储器（Cache） LRU算法的实现方法： 1）寄存器栈法：
块访问时，从栈顶向栈底顺序查找该块的块号，如果找到，将该块号抽出来放在栈顶，如果没有找到，栈顶压入该块块号，栈底的块号出栈。

29 5.2 高速缓冲存储器（Cache） 找到 没找到 寄存器栈法示意图 11，6 访问时： 2 11 9 7 11 2 9 7 2 11 9
寄存器栈法示意图 11，6 访问时： 2 11 9 7 11 2 9 7 11 找到 2 11 9 7 6 2 11 9 6 没找到

30 5.2 高速缓冲存储器（Cache） 2）计数法： 为Cache中每个块设置一个计数器，按一定的周期自动计数。当某一块数据被访问时，其对应的计数器清零。 计数值表示上一次访问后经过的时间，替换选择计数值最大的块替换出去。

31 5.2 高速缓冲存储器（Cache） 由于计数器存在最大长度，计数满后溢出，造成时间最小。因此，改进方法就是采用相对计数值。

32 5.2 高速缓冲存储器（Cache） 3）比较对法：
让各个Cache块成对组合，用一个触发器的状态表示该比较对内两块被访问的时间的远近程度，再经门电路可找到LRU块。 如：A、B、C三块，TAB、TAC、TBC分别表示各对中数据块被访问的顺序，TAB为1表示块A比块B更近被访问过。最近未被访问的数据块表示为： CLRU=TAC·TBC BLRU=TAB·TBC ALRU=TAB·TAC

33 5.2 高速缓冲存储器（Cache） 五．主存更新策略
CPU Cache 主存储器 I/O设备 X X’ （b） I/O写主存 （a）CPU写Cache 由于I/O操作时，有新的数据送入主存中，而Cache中还是原来装入的内容。

34 5.2 高速缓冲存储器（Cache） 1. 写策略： ⑴ 写回法（Write-back）
这种方法的要点有二，一是当CPU写数据时，只写Cache，不写主存；二是当已改写的块被替换出Cache 时，将其内容写回主存。 Cache 中每块增设“改写位”。 ⑵ 写直通法（Write-through） 也叫写贯穿法，这种方法所实行的是，当CPU进行写操作时，在写Cache的同时也将内容写入到相应的主存单元中，即两个内容同时改写。

35 5.2 高速缓冲存储器（Cache） 两种方案比较:
（1）写直通法是在每次写Cache时都有写主存的操作，但能始终保持数据块的一致性。写回法则仅在数据块被置换时写入主存，可减少访问主存的开销，但存在Cache块与主存块的瞬间不一致。 （2）写直通法一次写入一个字，仅需一个奇/偶校验位；而写回法一次写入一个数据块，需要多个校验位。 （3）写直通法需要较多的缓冲寄存器存放需要写入主存的数据；而写回法相应要简单些。

36 5.2 高速缓冲存储器（Cache） 2. “写”操作时的调块 3. 写策略与调块 （1）按写分配法(写时取)：
2. “写”操作时的调块 （1）按写分配法(写时取)：　　 写不命中时，先把所写单元所在的块调入Cache，再行写入。 （2）不按写分配法(绕写法) ： 写不命中时，直接写入下一级存储器而不调块。 3. 写策略与调块 写回法 ── 按写分配 写直达法 ── 不按写分配

37 练 习 有一个 “Cache-主存”存储层次。主存共分为8个块（0~7），Cache为4个块（0~3），采用直接映像方式。

38 根据块地址计算出每一主存块在Cache中的块号： 块地址 1 2 4 1 3 7 0 1 2 5
解： 块0 块1 块3 块4 块5 块7 区0 区1 Cache 主存储器 块2 块6 根据块地址计算出每一主存块在Cache中的块号： 块地址 块号

39 （1）根据块地址计算出每一主存块在Cache中的块号： 块地址 1 2 4 1 3 7 0 1 2 5
块地址 块号 时间： 块地址流： Cache：块0 块1 块2 块3 4 4 4 4 1 1 1 1 1 1 1 1 1 5 2 2 2 2 2 2 2 2 2 3 7 7 7 7 7 命中 命中 命中 （2）命中率为：3/10

40 5.2 高速缓冲存储器（Cache） 六. Cache性能分析 1．Cache系统的加速比
通常，在存储系统中，平均访存时间（又称为AMAT）为： 平均访存时间=命中时间+不命中率×不命中开销 假设Cache的访问周期为TC，主存储器的访问周期为Tm，Cache的命中率为H。那么Cache系统的等效访问周期T可以用下式来表示：

41 5.2 高速缓冲存储器（Cache） 将主存储器的访问周期Tm与Cache系统的等效访问周期T之比，定义为Cache系统的加速比Sp，其表示式为： 把上两式相结合,可以得到： 通过上式可知，H越大，Sp越大。因此通过提高命中率可提高加速比。

42 5.2 高速缓冲存储器（Cache） 2．CPU时间 执行一个程序所需的CPU时间能更好地反映存储系统的性能。
存储器停顿周期数近似为： 存储器停顿周期数 = 访存次数×不命中率×不命中开销

43 5.2 高速缓冲存储器（Cache） 则： CPU时间 =（ CPU执行周期数+访存次数×不命中率×不命中开销）×时钟周期时间 进一步：
CPU时间 = IC×（ CPIexecution+每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间 其中，IC为指令条数

44 例. 假设执行一段包含100条指令的程序，不命中开销50个时钟周期，所有指令执行时间都为2个时钟周期，CACHE不命中率2%，平均每条指令访存1.33次。分析CACHE对性能的影响。
解：由于CPU时间 = IC×（ CPIexecution+每条指令的平均访存次数×不命中率×不命中开销）×时钟周期时间 1）加入CACHE后： CPU时间 = 100（2+1.33*2%*50）=333时钟周期 2）加入CACHE前（不命中100%）： CPU时间 = 100（2+1.33*100%*50）=6850时钟周期

45 5.2 高速缓冲存储器（Cache） 3．改进Cache性能 平均访存时间=命中时间+不命中率×不命中开销
因此，可以从以下三个方面进行改进： 1）降低不命中率 2）减少不命中开销 3）减少命中时间 本文介绍了17种Cache优化技术 8种用于降低不命中率 5种用于减少不命中开销 4种用于减少命中时间

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

47 5.3 降低Cache不命中率 3. 冲突不命中（冲突失效，Conflict miss） 在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。这就是发生了冲突失效。（碰撞失效，干扰失效）

48 5.3 降低Cache不命中率 二. 增加Cache块大小
当Cache的容量一定时，块的大小对命中率的影响非常大。下图表示随着Cache块由小到大的变化，命中率H上升和下降的规律。 减少了Cache中块的数目，可能会增加冲突不命中 最佳 1 初始 块大小 命中率 H 增强了空间局部性，减少了强制性不命中

49 但是，增加块大小同时也会增加不命中开销。
措施：适当增加块的大小，但不能增大到使不命中率上升的程度。 各种块大小情况下Cache的不命中率 块大小 （字节） Cache容量（字节） 1K 4K 16K 64K 256K 16 15.05% 8.57% 3.94% 2.04% 1.09% 32 13.34% 7.24% 2.87% 1.35% 0.70% 64 13.76% 7.00% 2.64% 1.06% 0.51% 128 16.64% 7.78% 2.77% 1.02% 0.49% 256 22.01% 9.51% 3.29% 1.15% 但是，增加块大小同时也会增加不命中开销。

50 平均访存时间 ＝ 命中时间＋不命中率×不命中开销当其超过了不命中率下降带来的好处，平均访存时间就会增加。
各种块大小情况下Cache的平均访存时间 块大小 （字节） 不命中开销（时钟周期） Cache容量（字节） 1K 4K 16K 64K 256K 16 42 7.321 4.599 2.655 1.857 1.458 32 44 6.870 4.186 2.263 1.594 1.308 64 48 7.605 4.360 2.267 1.509 1.245 128 56 10.318 5.357 2.551 1.571 1.274 256 72 16.847 7.847 3.369 1.828 1.353

51 5.3 降低Cache不命中率 三. 提高相联度 1. 相联度：
在组相联映像中，如果每组中有n个块，则称该映像规则为n路组相联。 n的不同取值构成了一系列不同相联度的组相联。

52 当n=M（Cache的块数）时，为全相联映像。
块0 块V-1 块V 块2V-1 块(K-1)V 块KV-1 组0 组1 组K-1 区0 块(t-1)×KV 块(t-1)×KV+V-1 块(t-1)×KV+V 块(t-1)×KV+2V-1 块(tK-1)V 块tKV-1 组(t-1)K 组(t-1)K+1 组tK-1 区t-1 主存储器 Cache 当n=1时，为直接映像。 当n=M（Cache的块数）时，为全相联映像。

53 5.3 降低Cache不命中率 2. 相联度越高（即n值越大）， Cache空间的利用率就越高，块冲突概率就越低，因而Cache的不命中率就越低。 但是，提高相联度则可能以增加命中时间为代价。

54 5.3 降低Cache不命中率

55 5.3 降低Cache不命中率

56 不同相联度下的 平均访存时间 Cache容量 （K字节） 相联度（路） 1 2 4 8 7.65 6.60 6.22 5.44 5.90
4.90 4.62 4.09 4.60 3.95 3.57 3.19 3.30 3.00 2.87 2.59 16 2.45 2.20 2.12 2.04 32 2.00 1.80 1.77 1.79 64 1.70 1.60 1.57 1.59 128 1.50 1.45 1.42 1.44 1） 采用相联度超过8的方法实际意义不大 2） 2:1 Cache经验规则：容量为N 的直接映象Cache失效率 ≈容量为N/2的两路组相联Cache失效率 3） 提高相联度是以增加命中时间为代价 ： TTL或ECL板级Cache，两路组相联：增加10％ CMOS Cache, 两路组相联：增加2％ 不同相联度下的 平均访存时间

57 5.3 降低Cache不命中率 四. 增加Cache容量
Cache的容量是影响命中率的主要因素，在地址变换方式确定后，Cache的容量越大，命中率也就越高。根据模拟测试的结果，在一般情况下，命中率H和Cache容量S的关系可近似地表示为: 当Cache容量比较小时，随着Cache容量的增加，命中率提高得非常快；但命中率达到一定值后，随着Cache容量的增加，命中率提高的速度渐渐放慢了；当Cache的容量增加到无穷大时，命中率达到100%，但这没有实际意义。

58 5.3 降低Cache不命中率 五. Victim Cache
1. 基本思想：在Cache和它与下一级存储器的数据通路之间设置一个全相联的小Cache （称为Victim Cache），用于存放因冲突从Cache中被替换出去的块。当访问不命中时，先检查Victim Cache是否有所需的块，如果有，就将该块与Cache中某块交换。 通常，把在Victim Cache中找到数据也算作命中。 2. 作用： 对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。 例如，项数为4的Victim Cache: 使4KB Cache的冲突失效减少20%～90%

59 5.3 降低Cache不命中率 六.伪相联映像Cache 1. 直接映象 vs．组相联 2. 伪相联Cache
优　点 缺　点 直接映象 组相联 命中时间小 命中时间大 不命中率高 不命中率低 2. 伪相联Cache 取直接映象及组相联两者的优点： 命中时间小，不命中率低

60 基本思想及工作原理 在逻辑上把直接映象Cache的空间上下平分为两个区。伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。

61 5.3 降低Cache不命中率 七. Cache预取 预取是指在用到某信息块之前就将其预取进Cache或缓冲器中。
分为：硬件预取和编译器控制（在编译时加入预取指令）的预取。

62 5.3 降低Cache不命中率 八. 编译器优化 1. 基本思想 在编译时，对程序中的指令和数据进行重新组织，以降低Cache不命中率。
1. 基本思想 在编译时，对程序中的指令和数据进行重新组织，以降低Cache不命中率。 McFaring 发现：通过对指令进行重新排序，可有效地降低指令Cache的不命中率。 2KB Cache: 降低50％ 8KB Cache：降低75%

63 5.3 降低Cache不命中率 数据对存储位置的限制比指令的少，更便于优化。
1） 数组合并 举例： /* 修改前 */ int val [SIZE]; int key [SIZE]; /* 修改后 */ struct merge { int val ; int key ; } ; struct merge merged_array[size];

64 5.3 降低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];

65 （3） 循环融合 举例： /* 修改前 */ 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]; }

66 （4）分块 把对数组或整列访问改为按块进行。 /* 修改前 */ for （ i = 0; i<N; i = i+1 ）
/* 修改前 */ 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;

67 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;

68 /* 修改后 */ 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;

69 /* 修改后 */ 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;

70 5.4 减少Cache不命中开销 一. 让读不命中优先于写 Cache中的写缓冲器导致对存储器访问的复杂化。
写缓冲器进行的写入操作是滞后进行的，所以该缓冲器也被称为后行写数缓冲器。 例 考虑以下指令序列： STORE R3, 512（R0） ；M[512]←R3 LORD R1, 1024（R0） ；R1←M[1024] LORD R2, 512（R0） ；R2←M[512]

71 5.4 减少Cache不命中开销 解决问题的方法(读不命中的处理) 1）推迟对读不命中的处理 缺点：读不命中的开销增加，如50％
2）让读不命中优先于写： 检查写缓冲器中的内容，如果没有冲突（即没有地址相同）而且存储器可访问，就可以继续处理读不命中。

72 5.4 减少Cache不命中开销 二.写缓冲合并 提高写缓冲器的效率 写直达Cache 依靠写缓冲来减少对下一级存储器写操作的时间。

73 5.4 减少Cache不命中开销 如果写缓冲器为空，就把数据和相应地址写入该缓冲器。
如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。 如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。 如果写缓冲器满且又没有能进行写合并的项，就必须等待。

74 5.4 减少Cache不命中开销 通过写合并可提高写缓冲器的空间利用率，而且还能减少因写缓冲器满而要进行的等待时间。

75 5.4 减少Cache不命中开销 三、采用两级Cache 应把Cache做得更快？还是更大？ 性能分析 答案：二者兼顾，再增加一级Cache
第一级Cache(L1)足够小而快 第二级Cache(L2)容量足够大 性能分析 平均访存时间 ＝ 命中时间L1＋不命中率L1×不命中开销L1 不命中开销L1 ＝ 命中时间L2＋不命中率L2×不命中开销L2 平均访存时间 ＝ 命中时间L1＋不命中率L1× （命中时间L2＋不命中率L2×不命中开销L2）

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

77 5.4 减少Cache不命中开销 对于第二级Cache，我们有以下结论：
在第二级Cache比第一级 Cache大得多的情况下，两级Cache的全局不命中率和容量与第二级Cache相同的单级Cache的不命中率非常接近。 局部不命中率不是衡量第二级Cache的一个好指标，在评价第二级Cache时，应用全局不命中率这个指标。

78 5.4 减少Cache不命中开销 例.假设在1000次访存中，第一级Cache不命中40次， 第二级Cache不命中20次。试问：在这种情况下，该Cache系统的局部不命中率和全局不命中率各是多少？ 解: 第一级Cache的不命中率（全局和局部）是40/1000，即4%； 第二级Cache的局部不命中率是20/40，即50%； 第二级Cache的全局不命中率是20/1000，即2%。

79 5.4 减少Cache不命中开销 四、请求字处理技术 请求字 从下一级存储器调入Cache的块中，只有一个字
是立即需要的。这个字称为请求字。 应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。 请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。

80 5.4 减少Cache不命中开销 五、非阻塞Cache技术 Cache不命中时仍允许CPU进行其他的命中访问。即允许“不命中下命中”。
进一步提高性能： “多重不命中下命中” “不命中下不命中” （存储器必须能够处理多个不命中） 同时处理的不命中个数越多，所能带来的性能上的提高就越大。

81 对浮点程序，重叠失效个数越多，性能提高就越多
对整数程序，重叠次数对性能提高影响不大

82 5.5 减少命中时间 一. 容量小、结构简单的Cache
硬件越简单，速度就越快。 应使Cache足够小，以便可以与CPU一起放在同一块芯片上。

83 5.5 减少命中时间 二、虚拟Cache 1.将Cache、主存储器、磁盘存储器组织成“Cache-主存”和“主存-磁盘”两个独立的存储系统，又称为：物理地址Cache存储系统 CPU 虚拟地址 物理地址 MMU 数据或指令 高速缓冲 Cache 主存储器 CPU要访问存储器时，给出一个虚拟地址。由存储器管理部件（MMU）判断该数据所在的页（或段）是否在主存，如果不在，发出页面缺失请求，从磁盘中把所需页装入主存。如果在，则由MMU中地址变换部件把虚拟地址变换成物理地址。由此访问Cache。

84 2.将Cache、主存和磁盘三个存储器组织在一起，构成一个“Cache-主存-磁盘”存储系统。又称为：虚拟地址Cache存储系统
主存储器 CPU 虚拟地址 数据或指令 MMU Cache 物理地址 CPU要访问存储器时，把虚拟地址直接送往存储器管理部件（MMU）和Cache。 Cache能够直接接受虚拟地址的访问，如果Cache命中，CPU直接访问Cache中的数据或指令。如果Cache不命中，产生块缺失，则由MMU判断该数据所在的页（或段）是否在主存，如果不在，发出页面缺失请求，从磁盘中把所需页装入主存。如果在，则由MMU中地址变换部件把虚拟地址变换成物理地址。 能够接受虚拟地址的访问 如Intel公司的i860等处理机采用这种组织方式

85 Cache优化技术总结 “＋”号：表示改进了相应指标。 “－”号：表示它使该指标变差。 空格栏：表示它对该指标无影响。
复杂性：0表示最容易，3表示最复杂。

86 Cache优化技术总结 优化技术 不命中 率 开销 命中 时间 硬件 复杂度 说 明 增加块大小 + 
实现容易；Pentium 4 的第二级Cache采用了128 B的块 增加Cache容量 被广泛采用，特别是第二级Cache 提高相联度 1 被广泛采用 Victim Cache 2 AMD Athlon采用了8个项的Victim Cache 伪相联Cache MIPS R10000的第二级Cache采用

87 优化技术 不命中 率 开销 命中 时间 硬件 复杂度 说 明 用编译技术减少Cache不命中次数 + 向软件提出了新要求；有些机器提供了编译器选项 使读失效 优先于写  1 在单处理机上实现容易，被广泛采用 写缓冲归并 与写直达合用，广泛应用，例如21164，UltraSPARC Ⅲ 非阻塞Cache 3 在支持乱序执行的CPU中使用

88 优化技术 不命中 率 开销 命中 时间 硬件 复杂度 说 明 两级Cache + 2 硬件代价大；两级Cache的块大小不同时实现困难；被广泛采用 容量小且结构简单的Cache  实现容易，被广泛采用

89 全Cache系统： 没有主存储器， 由Cache和磁盘组成存储系统 多处理机系统中的全Cache存储系统

90 5.6 主存 主存的主要性能指标：延迟和带宽 几种能提高主存性能的存储器组织技术: 一 . 增加存储器宽度

91 5.6 主存 二. 采用简单的多体交叉存储器 在存储系统中采用多个DRAM，并利用它们潜在的并行性。

92 5.6 主存 假设四个存储体的地址是在字一级交叉的，即存储体0中每个字的地址对4取模都是0，体1中每个字的地址对4取模都是1，依此类推。 4
4 8 12 地址 体0 1 5 9 13 地址 体1 2 6 10 14 地址 体2 3 7 11 15 地址 体3

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

94 5.6 主存 四. 避免存储体冲突 体冲突：两个请求要访问同一个体。 减少体冲突次数的一种方法：采用许多体 解决体冲突的方法
例如，NEC SX/3最多可使用128个体 解决体冲突的方法 软件方法(编译器) 循环交换优化 扩展数组的大小，使之不是2的幂 硬件方法 使体数为素数 体内地址＝地址 mod (存储体中的字数) 可以直接截取

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

96 5.7 虚拟存储器 一. 基本工作原理 1. 基本概念 虚拟存储器是对物理主存的扩展,由软件来实现。这样，从程序员的角度来看，存储空间扩大了。在虚拟存储结构方式下，程序员编制程序时所使用的地址与主存地址是不同的。 通常，把程序使用的地址称为虚拟地址，或称为逻辑地址，这些地址的集合称为虚存空间； 实际主存的地址称为实地址，或物理地址。所有实地址的集合称为存储空间，其范围就是整个主存的容量。

97 5.7 虚拟存储器 在采用虚拟存储器的计算机中，程序是与虚存空间相联系的，而执行程序的CPU则是和主存所用的存储空间相联系的。系统为了让CPU执行程序，必须要把虚存空间变换成存储空间，也就是要把程序的逻辑地址变为CPU可以寻址的主存地址。 虚拟存储器根据地址映象方式的不同分为段式、页式和段页式虚拟存储器。

98 5.7 虚拟存储器 2. 虚拟存储器的地址构成 以页式虚拟存储器为例，在页式虚拟存储器中，把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块（称为页），每一页中包含有固定长度的存储单元。 主存储器的页称为实页，虚拟存储器的页称为虚页。

99 5.7 虚拟存储器 地址构成： （a） 主存地址A的组成 实页号p 页内偏移d 用户号U 虚页号P 页内偏移D 磁盘号 磁头号 磁道号
记录号 （b） 多用户虚拟存储器地址Av的组成 （c） 磁盘存储器物理地址的组成

100 3.页式虚拟存储器工作原理 U P D p d 内部地址变换 虚拟页号→主存实地址 主存页面失效 磁盘存储器地址 外部地址变换
虚拟页号→磁盘实地址 内部地址变换 虚拟页号→主存实地址 U P D I/O处理机 未命中 命中 Av多用户虚拟地址 主存地址 p d 主存页面 主存满 主存未满 页面替换 算 法 主存页号 I/O通道 主存储器 磁盘存储器 调入页 调出页 选页 0页 1页 2p-1页 U P D 内部地址变换 虚拟页号→主存实地址 p d

101 5.7 虚拟存储器 二. 虚拟存储器的地址映象和地址变换 虚拟存储器中有三种地址空间： 存储器地址空间、虚拟地址空间和磁盘存储器地址空间。
地址映象： 虚拟存储器的地址映象是把虚拟地址空间映象到主存储器地址空间，也就是在程序的虚拟地址与主存储器实地址间建立对应关系。 地址变换： 而地址变换是在程序装入主存储器后，在实际运行时，把程序的虚拟地址变换成主存储器的实地址（内部地址变换）或磁盘存储器地址（外部地址变换）。

102 5.7 虚拟存储器 1. 段式虚拟存储器 段式虚拟存储器地址映象关系 段表 起始地址 段号 段长 1 2 4K 2K 8K 0K 12K
1 2 4K 2K 8K 0K 12K 20K 主程序 （0段） 1段 2段 程序空间 主存储器 程序按逻辑关系分 为大小不同的段

103 5.7 虚拟存储器 段式虚拟存储器地址变换过程 若为 “0”,表示要访问的段不在主存里,其他项可用来存放该段在磁盘存储器中的起始地址等信息
多用户虚地址 用户号U 段号S 段内偏移D 主存实地址 段表基地址寄存器堆 N 7 段表基地址 段表长度 B 段号 起始地址 装入位 段长 访问方式 段表（每个用户或作业） 1 2 3 4 5 6 若为 “0”,表示要访问的段不在主存里,其他项可用来存放该段在磁盘存储器中的起始地址等信息

104 5.7 虚拟存储器 段式虚拟存储器优点： 段式虚拟存储器缺点： ⑴ 适宜于编制相对独立的模块化程序。 ⑵ 便于实现程序和数据的共享。
⑶ 程序的动态链接和调度比较容易。 ⑷ 便于实现信息保护。 段式虚拟存储器缺点： ⑴ 调入调出时容易产生碎片，使主存储器空间利用不充分。 ⑵ 对磁盘存储器的管理比较困难。 ⑶ 地址变换所花费的开销比较大。

105 5.7 虚拟存储器 2. 页式虚拟存储器 页式虚拟存储器把虚拟地址空间等分成大小相同的块，每块称为一页，相应地，也把主存储器的地址空间等分成和页大小相同的块（页）。

106 5.7 虚拟存储器 页式虚拟存储器地址变换过程 装入位 修改位 主存页号 各种标志 页内偏移d 实页号p 主存 实地址 p 用户号U
虚地址 多用户 Pa 1 页表基址寄存器 页表

107 5.7 虚拟存储器 与段式虚拟存储器相比，页式虚拟存储器的主要优点有： ⑴ 主存储器的利用率比较高。 ⑵ 与段表相比，页表相对比较简单。
⑶ 地址映象和变换的速度比较快。 ⑷ 因为页的大小为磁盘存储器物理块大小的整数倍，对磁盘存储器的管理和操作比较容易。 与段式虚拟存储器相比，页式虚拟存储器也存在着如下缺点： ⑴ 程序的模块化性能不好。 ⑵ 页表太大，要占用很大的存储空间。

108 5.7 虚拟存储器 3. 段页式虚拟存储器 基本思想是： 对用户用来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的实地址空间采用分页的方法管理。 在段页式虚拟存储器中，主存储器按固定大小分成页，称为实页；用户仍然按照逻辑的段来编写程序，但每一个段又被分成若干个固定大小的页，页的大小和主存储器的页是一样的。

109 5.7 虚拟存储器 段页式虚拟存储器地址映象关系 主存储器 页表长度 页表首址 2 3 段表 0段（8KB） 1段（11KB） 用户程序
0段0页 0段1页 0段页表 1段0页 1段1页 1段2页 1段页表 每页4KB

110 段页式虚拟存储器地址变换过程 装入位 修改位 标志 页表长 页表地址 实页号 Ap 1 p 0/1 段表基址寄存器 As 多用户虚地址AV
用户号U 段号S 虚页号P 页内偏移D 实页号p 页内偏移d 多用户段表 多用户页表

111 5.7 虚拟存储器 三. 虚拟地址快速变换法 1.快速目录表法 基本思想:
压缩页表的规模，在页表中，只为已经装入到主存储器中的那些页面建立虚页号与主存的实页号之间的关系，也就是页表中存放着正在执行程序中最近访问的页在主存中的页面地址。 用高速相联存储器代替主存存放页表。

112 5.7 虚拟存储器 目录表法的地址变换过程: 多用户虚拟地址 用户号U 虚页号P 页内偏移D 页内偏移d 实页号p 主存实地址 相联访问
0/1 多用户虚页号(U,P) 实页号 修改位 目录表(按内容访问的相联存储器) 其他标志

113 5.7 虚拟存储器 2. 快表与慢表法 基本思想: 通过对实际查表过程的分析，可以发现，由于程序局部性的特点，对目录表内各行的使用并不是随机的，而具有明显的簇聚性。也就是说，实际上在一段时间内，对页表的访问只是局限在少数几行内。根据这一特点，用快速硬件构成一个小容量的页表，这个小容量的页表被称为快表，Pentium处理机中将其称为TLB（translation lookaside buffer）。与快表相对应，存放在主存储器中的页表称为慢表。慢表是一个全表，而快表只是慢表中的一小部分副本。

114 5.7 虚拟存储器 采用快慢表地址变换过程: 同时查找 多用户虚地址 主存实地址 用户号U 虚页号P 页内偏移D 页内偏移d 实页号p 快表
1 装入位 多用户虚页号（U，P） 慢表（按地址访问） 快表（按内容相联访问） 同时查找

115 5.7 虚拟存储器 四.页面替换算法（置换策略） 虚拟存储器是包括主存—磁盘存储器两级存储器在内的存储系统，主存的容量总是比磁盘存储器小得多。因此，必然会出现CPU要访问的信息所在页不在主存储器内的情况，这称为“页缺失”或“页故障”。这时，要从磁盘存储器上把新的页调入主存储器。如果主存的所有页面都已经被占用，则要从主存储器中淘汰一个不常用的页面，以便腾出主存空间来存放新调入的页面。按照什么规则替换主存储器中的页面，这就是页面替换算法要解决的问题。

116 5.7 虚拟存储器 评价一个页面算法优劣的标准主要有两个方面: 一是页面的命中率要高， 二是算法的实现不能太复杂。
1. 随机算法（RAND算法） 利用硬件或软件的随机数发生器来产生主存储器中被替换的页面号。 2. 先进先出算法（FIFO算法） 选择最早调入主存储器的页面作为被替换出去的页面。

117 5.7 虚拟存储器 3. 最久未使用算法（LRU算法，least recently used algorithm）
选择最近最久没有被CPU访问的页面作为被替换的页面。 例：在页式虚拟存储器中，假定各虚页面按如下的顺序请求访问：12，14，2，34，56，23，14，56，12，12。并且主存只能容纳4个页面。试列出使用LRU替换算法时，每个页面调度操作后主存中的页面，并指出什么时刻发生页面失效。 解：LRU算法：选择最近最久未被CPU访问的页面作为被替换的页面。

118 时间： 页地址流： 主存： 页0 页1 页2 页3 12 12 12 12 12 56 56 56 56 56 56 14 14 14 14 14 23 23 23 23 23 2 2 2 2 2 14 14 14 14 34 34 34 34 34 34 12 12 命中 命中 页失效的时刻为：1，2，3，4，5，6，7，9

119 5.7 虚拟存储器 4. 最优替换算法（OPT算法） 前面几种页面替换算法的主要依据是主存储器中页面调度情况的历史信息，其出发点是假设将来主存储器的页面调度情况与过去一段时间内的情况是相同的。显然这一种假设不一定总是正确的，最好的算法是选择将来最久不被访问的页面作为被替换的页面。 例：设有一个循环程序分为1~5个虚页，程序执行时访问存储器的虚页地址流为：2、3、2、1、5、2、4、5、3、2、5、2，操作系统能分配给该程序的实页只有3个，试画出使用FIFO、LRU和OPT三种置换算法对3个实页的使用与置换过程，并计算各自的访存命中率。

120 解： 时间： 页地址流： 2 3 2 3 2 3 1 2 3 1 5 2 1 5 2 4 5 2 4 5 2 4 3 2 4 3 4 5 3 5 2 3 FIFO： H=3/12 命中 命中 命中 2 3 2 3 2 3 1 2 5 1 2 5 1 2 5 4 2 5 4 2 5 4 3 5 2 3 2 5 3 5 2 3 LRU： H=5/12 命中 命中 命中 命中 命中 2 3 2 3 2 3 1 2 3 5 2 3 5 2 3 5 4 3 5 4 3 5 4 3 5 2 5 3 2 3 5 2 OPT： H=6/12 命中 命中 命中 命中 命中 命中

121 练 习 1．虚拟存储器中，（ ），主存的命中率越高 A）页面越大 B）主存容量越大 C）段越长 D）辅存容量越大
1．虚拟存储器中，（ ），主存的命中率越高 A）页面越大 B）主存容量越大 C）段越长 D）辅存容量越大 2．全相联地址映象是指（ ）。 A）任何主存页都可装入Cache中任何页的位置 B）一个虚页只装进固定的主存实页位置 C ） 组之间是固定的，而组内任何主存页可以装入任何Cache页位置 D） 组间可任意装入，组内是固定装入

122 练 习 3．段表中设置装入位是为了判断数据是否（ ） A）有效 B）装入主存 C）装入Cache D）需要写回
3．段表中设置装入位是为了判断数据是否（ ） A）有效 B）装入主存 C）装入Cache D）需要写回 4. 用Cache、主存和磁盘组成一个三级存储系统有2种组织方式，分别称为 存储系统 和 存储系统 。 5. 由容量为C的Cache和容量为M的主存储器构成的存储系统的总容量为 。 6．在具有虚拟存储器的系统中，CPU根据程序指令生成的地址是 地址。

123 练 习 7．在Cache块替换算法中，下述哪种说法是错误的（ ）。 A）直接映象产生块失效时，无需进行选择即可直接替换
B）全相联映象产生块失效时，可使用随机算法 C）组相联映象产生块失效时，组内可使用随机算法 D）全相联和组相联解决块失效时都不能采用随机算法

124 练 习 8．以下哪几种操作可以提高Cache命中率（ ）（多选）。 A）增大分组的数目 B）增大Cache块的大小 C）增大Cache的容量
D）使用适当的预取算法 9. “多体交叉存储器主要解决扩充容量问题”该说法是正确的吗?

125 答案 1．B 2．A 3. B 4. 物理地址Cache, 虚拟地址Cache 5. M 6. 逻辑地址（虚拟地址） 7. D 8. C D
9. 错误

126 作 业 1. 对于下述访存地址序列（字地址）： 1，4，8，5，20，17，19，56，9，11，4，43，5，6，9，17。
假定Cache是直接映象的，每块4字。Cache的容量是16字，初始时Cache为空，标出每次访问的Cache命中情况以及最后Cache的内容。

127 作 业 2. Cache-主存系统， Cache有4页，主存有8页。采用组相联变换，每组有2页，LRU替换算法。根据下列页地址流，画出调页情况，并计算命中率。 T: 页地址流：