计算机系统结构chap5-2015-0513

第五章存储层次Copyright©2012,ElsevierInc.Allrightsreserved.Introduction程序员希望存储器容量无限大，延迟无限小越小的硬件速度越快，造价越高解决方法:存储系统的层次化结构越小越快的存储器，速度越接近处理器时间局部性（temporallocality）和空间局部性（spatiallocality）保证了最近访问的内容可以在较小存储器中找到Temporallocality：最近访问过的内容很可能在不久的将来再次被访问。Spatiallocality：地址邻近的内容可能在一定时间内被连续访问。Introduction5.1.1从单级存储器到多级存储器从用户的角度来看，存储器的三个主要指标是：

容量，速度，价格(每位价格)5.1存储器的层次结构2.人们对这三个指标的期望:5.1存储器的层次结构速度快价格高容量大价格低容量大速度慢5.1存储器的层次结构3.这三个指标相互矛盾:4.解决方法：

采用多种存储器技术，构成存储层次目标：高速度、低价格（成本）、大容量5.1存储器的层次结构达到目标的依据：指令和数据访问的局部性原理5.1存储器的层次结构Copyright©2012,ElsevierInc.Allrightsreserved.MemoryHierarchyIntroduction5.1.2存储层次的性能参数C，S，TA设：

S──容量

TA──访问时间

C──每位价格下面仅考虑由M1和M2构成的两级存储层次：

M1

的参数：S1，TA1，C1M2

的参数：S2，TA2，C21.每位价格CC＝─────如果S1<<S2，CC2C1S1＋C2S2S1＋S25.1存储器的层次结构5.1存储器的层次结构Cache命中当处理器在Cache中找到要访问的数据项时，称为Cache命中Cache缺失当处理器在Cache中找不到要访问的数据项时，称为Cache缺失2.M1的命中率H和失效率F

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

H＝N1/(N1＋N2)

N1

──访问M1的次数

N2──访问M2的次数失效率F

：

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

F＝1－H5.1存储器的层次结构3.平均访问时间TA5.1存储器的层次结构由于

TA＝HTA1＋(1－H)(TA1+TM)于是

TA＝TA1＋(1－H)TM

或

TA＝TA1＋F

TM

TA1

──命中时间

TM

──失效开销5.1存储器的层次结构5.1.3“Cache－主存”和“主存－辅存”层次5.1存储器的层次结构

一般来说：

“Cache－主存”层次：弥补主存速度的不足

“主存－辅存”层次：弥补主存容量的不足1.“Cache－主存”层次5.1存储器的层次结构主存与CPU的速度差距35%55%7%5.1存储器的层次结构“Cache-主存”层次的实现：主要借助于辅助硬件。5.1存储器的层次结构2.“主存－辅存”层次

“主存－辅存”层次的实现：主要借助于辅助软硬件。5.1存储器的层次结构存储层次CPU对第二级的

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

访问速度的比值

(第一级和第二级)典型的块(页)大小失效时CPU是否切换“Cache－主存”层次“主存－辅存”层次为了弥补主存速度的不足为了弥补主存容量的不足主要由专用硬件实现主要由软件实现几比一几百比一几十个字节几百到几千个字节可直接访问均通过第一级不切换切换到其他进程两者的比较“Cache－主存”与“主存－辅存”5.1存储器的层次结构5.1.4存储层次的四个问题当把一个块调入高一层(靠近CPU)存储器时，

可以放在哪些位置上?

(映象规则)当所要访问的块在高一层存储器中时，如何

找到该块?

(查找算法)3.

当发生失效时，应替换哪一块？

(替换算法)4.

当进行写访问时，应进行哪些操作?

(写策略)1.

2.5.1存储器的层次结构5.2Cache基本知识5.2.1映象规则1.全相联映象

全相联：主存中的任一块可以被放置到

Cache中的任意一个位置。特点：

空间利用率最高，冲突概率最低，

实现最复杂。5.2Cache基本知识实际：Cache常包含几百个块，主存常包含几百万个块。5.2Cache基本知识2.直接映象：直接映象：主存中的每一块只能被放置到

Cache中唯一的一个位置。特点：

空间利用率最低，冲突概率最

高，实现最简单。例如：对于主存的第

i块，若它映象到Cache的

第j块，则:

j＝imod(M)

（M

为Cache的块数）

5.2Cache基本知识(循环分配)5.2Cache基本知识组相联：主存中的每一块可以被放置到Cache

中唯一的一个组中的任何一个位置。

设M＝2m，则当表示为二进制数时，j实际上就是

i的低m位：3.组相联映象：m位j5.2Cache基本知识主存块地址

i：5.2Cache基本知识组相联是直接映象和全相联的一种折衷5.2Cache基本知识组的选择常采用位选择算法

若主存第i块映象到第k组，则:

k＝imod（G）（G为Cache的组数）

设G＝2g，则当表示为二进制数时，k实际

上就是i

的低g

位。g

位k主存块地址

i：5.2Cache基本知识◆上述的j

（直接映象）和k

（组相联）通

常称为索引◆标志字段：给出块地址，通过比较来判断是否发生命中◆块内偏移：用于从块中选出需要的数据相联度一定是越大越好？◆绝大多数计算机的Cache:n≤4◆n路组相联：每组中有n

个块(n＝M/G

)

n称为相联度。

相联度越高，Cache空间的利用率就越高，

块冲突概率就越低，失效率也就越低。

全相联直接映象组相联n

(路数)G

(组数)MM111＜n＜M1＜G＜M5.2Cache基本知识5.2.2查找方法所要解决的问题：如何确定Cache中是否有所要访问的块？若有的话如何确定其位置？

5.2Cache基本知识目录表的结构：标志字段：给出块地址，通过比较来判断是否发生命中有效位：用于确定块中是否包含有效信息5.2Cache基本知识查找范围：候选位置所对应的目录表项5.2Cache基本知识并行查找与顺序查找5.2Cache基本知识提高性能的重要思想：主候选位置(MRU块)5.2Cache基本知识并行查找的实现方法：

▲

相联存储器

▲

单体多字存储器＋比较器5.2Cache基本知识直接映象Cache的查找过程5.2Cache基本知识举例：４路组相联并行标识比较5.2Cache基本知识４路相联Cache的查找过程5.2Cache基本知识5.2.3替换算法所要解决的问题：当新调入一块，而Cache

又已被占满时，替换哪一块？2.FIFO（先进先出）3.LRU（最近最少使用）1.随机法5.2Cache基本知识5.2Cache基本知识2.FIFO（先进先出）将最早进入Cache的块作为替换块。3.LRU（最近最少使用）优点：失效率低利用历史信息来预测未来使用情况，被替换的块是最长时间内没有被访问Cache的块。需要记录块的访问次数。利用局部性原理推论。

随机法

优点：硬件实现简单为了均匀地分配，候选块将被随机选择。系统产生伪随机数块号。LRU和随机法的失效率的比较

（VAX地址流，块大小16字节）5.2Cache基本知识5.2.4写策略1.“写”操作所占的比例

Load指令：26％

Store指令：10％

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

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

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

10％/(26％＋10％)≈28％5.2Cache基本知识“读”操作可以在标志位读和比较的同时进行；“写”操作必须在确认是命中后才可进行（当标志位有效且地址命中时，块才能被修改）“写”操作有可能导致Cache和主存内容的不一致5.2Cache基本知识5.2Cache基本知识4．两种写策略

◆

写直达

执行“写”操作时，不仅写入Cache，而且

也写入下一级存储器。

◆

写回法

执行“写”操作时，只写入Cache。仅当

Cache中相应的块被替换时，才写回主存。

(设置“污染位”/“重写位”/“脏位”，dirtybit)问题：当发生缺失需要替换时，干净的块是否需写回？5.2Cache基本知识5．两种写策略的比较◆写直达的优点：

易于实现，一致性好。◆写回法的优点：

写操作速度快，对存储器的速度要求较低；（对同一块中的多次写操作仅需要对下层存储器一次操作，因此所需存储带宽较小）利用写回法减少访问的通信量，写直达保证存储器层次结构中Cache和低层存储器数据的一致性。5.2Cache基本知识6.写缓存技术（用于减少写停顿的优化策略）8.写策略与调块

写回法──

按写分配写直达──

不按写分配7.“写”操作时的调块

◆

按写分配(写时取)

写失效时，先把所写单元所在的块调入

Cache，再行写入。

◆

不按写分配(绕写法)

写失效时，直接写入下一级存储器而不调块。5.2Cache基本知识5.2.5Cache举例例子：DEC的AlphaAXP21064中的内部数据Cache。1.简介

容量：8KB

块大小：32B

块数：256

调块：不按写分配映象规则：直接映象“写”策略：写直达写缓冲器大小：4个块5.2Cache基本知识2.结构图5.2Cache基本知识5.2Cache基本知识5.2Cache基本知识3.失效情况下的操作读失效:

Cache向CPU发出一个暂停信号,通知它等 待，并从下一级存储器中读取32个字节， 填入对应的Cache块。写失效:

CPU不对Cache进行操作。5.2Cache基本知识4.写缓冲的结构5.2Cache基本知识写合并:

当把数据写入写缓冲器时，判断本次所写

入单元的块地址是否与写缓冲器中某个有效块

的地址相同，若是，则把新数据与该块合并。5.2Cache基本知识5.混合Cache与分离Cache访存操作：

指令访问(读指令)

数据访问(读写数据)分离Cache：

指令Cache+数据Cache混合（一体）Cache：

单一的Cache优缺点：

(1)

实现成本

(2)

结构冲突例：当执行一条load或store指令时，处理器会同时请求一个数据字和一个指令字。

5.2Cache基本知识16KB容量1KB2KB4KB8KB32KB指令Cache3.06%表5－4失效率的比较64KB128KB数据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%5.2Cache基本知识6.分离Cache与混合Cache平均失效率的比较前提：指令Cache容量+数据Cache容量

=混合Cache容量

5.2Cache基本知识分离Cache平均失效率的计算：访问指令Cache的百分比×指令Cache的失效率＋访问数据Cache的百分比×数据Cache的失效率访问指令Cache的百分比：

100％/(100％＋26％＋10％)≈74％

访问数据Cache的百分比：

(26％＋10％)/(100％＋26％＋10％)≈26％5.2Cache基本知识5.2.6性能分析2.平均存储器访问时间

平均访问时间＝命中时间＋失效率×失效开销3.CPU时间CPU时间＝(CPU执行周期数＋存储器停顿周期数)

×时钟周期时间1.失效率（缺失率）5.2Cache基本知识例

假设Cache的命中时间为1个时钟周期，失效开销为50

个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期(因为混合Cache只有一个端口，无法同时满足两个请求。按照前一章中有关流水线的术语，混合Cache会导致结构冲突)，根据表5－4所列的失效率，试问指令Cache和数据Cache容量均为16KB

的分离Cache和容量为32KB的混合Cache相比，哪种Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？5.2Cache基本知识解：

如前所述，约74%的访存为取指令。因此，

分离Cache的总体失效率为：

(74%×0.64%)＋(26%×6.47%)＝2.16%

根据表5－4，容量为32KB的混合Cache的失效率略低一些，只有1.99%.另外：平均访存时间公式可以分为指令访问和数据

访问两部分：5.2Cache基本知识平均访存时间＝指令所占的百分比×

(指令命中时间＋指令失效率×失效开销)＋

数据所占的百分比×

(数据命中时间＋数据失效率×失效开销)所以根据表5－4，两种结构的平均访存时间分别为：平均访存时间分离＝74%×(1＋0.64%×50)＋

26%×(1＋6.47%×50)

＝(74%×1.32)＋(26%×4.235)

=2.05.2Cache基本知识平均访存时间混合＝74%×(1＋1.99%×50)

＋26%×(1＋1＋1.99%×50)

＝(74%×1.995)＋(26%×2.995)

＝1.476＋0.779＝2.263.CPU时间

在考虑存储器对系统性能影响时，可以将系统性能描述为：

CPU时间＝(CPU执行周期数＋存储器停顿周期数)

×时钟周期时间5.2Cache基本知识其中，存储器停顿周期数＝

“读”的次数×读失效率×读失效开销

+“写”的次数×写失效率×写失效开销如果读、写失效率以及读、写失效开销相差不大，

存储器停顿周期数＝访存次数×失效率×失效开销于是

CPU时间＝IC×[CPIexe＋访存次数/指令数×

失效率×失效开销]×时钟周期时间5.2Cache基本知识例我们用一个和AlphaAXP类似的机器作为第一个例子。假设Cache失效开销为50

个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是2.0

个时钟周期，Cache的失效率为2%，平均每条指令访存1.33

次。试通过CPI分析Cache对性能的影响。5.2Cache基本知识解：考虑Cache的失效后，性能为，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.55.2Cache基本知识例考虑两种不同组织结构的Cache:直接映象Cache和两路组相联Cache，试问它们对CPU的性能有何影响？分析时用以下假设：(1)理想Cache(命中率为100%)情况下CPI为2.0，时钟周期为2ns，平均每条指令访存1.3次。(2)两种Cache的容量均为64KB,块大小32字节(3)对于组相联Cache，CPU的时钟周期增加到原来的1.1倍(4)失效开销都是70ns(5)命中时间为1个时钟周期，64KB直接映象Cache的失效率为1.4%，64KB两路组相联Cache的失效率为1.0%5.2Cache基本知识解：(1)平均访存时间=命中时间+失效率×失效开销平均访存时间直接

=1.0×2+(1.4%×70)=2.98ns平均访存时间组相联=1.0×2×1.10+(1.0%×70)=2.90ns(2)CPU时间＝IC×[CPIexe＋访存次数/指令数×

失效率×失效开销]×时钟周期时间

5.2Cache基本知识CPU时间直接

=IC×(2.0×2+1.3×1.4%×70) =5.27×IC(ns)

CPU时间组相联=IC×(2.0×2×1.1+1.3×1.0%×70) =5.31×IC(ns)5.2Cache基本知识平均访存时间＝命中时间＋失效率×失效开销可以从三个方面改进Cache的性能：(1)降低失效率(2)减少失效开销

(3)减少Cache命中时间下面介绍15

种Cache优化技术5.2.7改进Cache性能5.2Cache基本知识(1)强制性失效(Compulsorymiss)

当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。

(冷启动失效，首次访问失效。)(2)容量失效(Capacitymiss)

如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。5.3降低Cache失效率的方法1.三种失效(3C)(3)冲突失效(Conflictmiss)

在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。

(碰撞失效，干扰失效)5.3降低Cache失效率的方法2.三种失效所占的比例(SPEC92)5.3降低Cache失效率的方法5.3降低Cache失效率的方法可以看出：(1)

相联度越高，冲突失效就越少；(2)

强制性失效和容量失效不受相联度的影响；(3)

强制性失效不受Cache容量的影响，但容

量失效却随着容量的增加而减少；(4)

表中的数据符合2:1的Cache经验规则，即

大小为N的直接映象Cache的失效率约等于

大小为N/2的两路组相联Cache的失效率。5.3降低Cache失效率的方法强制性失效：增加块大小，预取

(本身很少)容量失效：增加容量

(抖动现象)冲突失效：提高相联度

(理想情况：全相联)3.减少三种失效的方法4.许多降低失效率的方法会增加命中时间或失效开销5.3降低Cache失效率的方法5.3.1增加Cache块大小增加块容量会降低强制失效率更大的块可能会导致冲突失效率如果Cache容量较小时会增加容量失效率5.3降低Cache失效率的方法2.增加块大小会增加失效开销1.失效率与块大小的关系

(1)对于给定的Cache容量，当块大小增加

失效率开始是下降，后来反而上升了；

(2)Cache容量越大，使失效率达到最低的

块大小就越大。3.例题5.3降低Cache失效率的方法例假定存储系统在延迟40个时钟周期后，每2

个时钟周期能送出16

个字节。即:经过42

个时钟周期，它可提供16

个字节；经过44

个时钟周期，可提供32

个字节；依此类推。试问对于表5-6中列出的各种容量的Cache，在块大小分别为多少时，平均访存时间最小？解：平均访存时间为：

平均访存时间＝命中时间＋失效率×失效开销5.3降低Cache失效率的方法

假设命中时间与块大小无关，为1个时钟，那么对于一个块大小为16字节，容量为1KB的Cache来说：

平均访存时间＝1＋（15.05%×42）＝7.321个时钟周期

而对于块大小为256B的大小为256KB的Cache来说，平均访存时间为：

平均访存时间＝1＋（0.49%×72）＝1.353个时钟周期

表5.7列出了在这两种极端情况之间的各种块大小和各种Cache容量的平均访存时间。5.3降低Cache失效率的方法块大小（字节）失效开销(时钟周期)Cache容量（字节）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.8704.1862.2631.5941.30864487.6054.3602.2671.5091.2451285610.3185.3572.5511.5711.2742567216.8477.8473.3691.8281.3535.3.2提高相联度1.采用相联度超过8的方法实际意义不大

8路组相联和相同容量的全相联Cache在降低失效率方面同样有效2.2:1Cache经验规则

容量为N

的直接映象Cache失效率

≈容量为N/2的两路组相联Cache失效率5.3降低Cache失效率的方法5.3.2提高相联度3.提高相联度是以增加命中时间为代价

例如：

TTL或ECL板级Cache，两路组相联：

增加10％定制的CMOSCache,两路组相联：

增加2％5.3降低Cache失效率的方法4.例题

假定提高相联度会按下列比例增大处理器

时钟周期：

时钟周期2路＝1.10×时钟周期1路

时钟周期4路＝1.12×时钟周期1路时钟周期8路＝1.14×时钟周期1路

假定命中时间为1个时钟，失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表5－5中的失效率，试问当Cache为多大时，以下不等式成立？5.3降低Cache失效率的方法平均访存时间8路

<平均访存时间4路平均访存时间4路

<平均访存时间2路平均访存时间2路

<平均访存时间1路解：

在各种相联度的情况下，平均访存时间分别为：

平均访存时间8路=命中时间8路+失效率8路×失效开销8路

=1.14＋失效率8路×50

平均访存时间4路

=1.12＋失效率4路×50

平均访存时间2路

=1.10＋失效率2路×50

平均访存时间1路

=1.00＋失效率1路×505.3降低Cache失效率的方法

在每种情况下的失效开销相同，都是50个时钟周期。把相应的失效率代入上式，即可得平均访存时间。

例如，1KB的直接映象Cache的平均访存时间为：

平均访存时间1路＝1.00＋(0.133×50)

＝7.65容量为128KB的8路组相联Cache的平均访存时间为：

平均访存时间8路＝1.14＋(0.006×50)

＝1.445.3降低Cache失效率的方法Cache容量（K字节）相联度（路）124817.656.606.225.4425.904.904.624.0944.603.953.573.1983.303.002.872.59162.44322.001.801.771.79641.701.601.571.591281.501.451.421.441.基本思想

在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块(称为Victim)，以备重用。5.3.3VictimCache5.3降低Cache失效率的方法5.3降低Cache失效率的方法

对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。例如，项数为4的VictimCache:

使4KBCache的冲突失效减少20%～90%2.作用5.3降低Cache失效率的方法1.直接映象vs组相联5.3.4伪相联Cache(列相联)2.伪相联Cache优点缺点直接映象组相联命中时间小命中时间大失效率高失效率低取直接映象及组相联两者的优点：

命中时间小，失效率低5.3降低Cache失效率的方法(1)基本思想及工作原理

在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。(2)快速命中与慢速命中

要保证绝大多数命中都是快速命中。5.3降低Cache失效率的方法3.例题例5.6

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

平均访存时间伪相联

＝命中时间伪相联＋失效率伪相联×失效开销伪相联由于：

失效率伪相联＝失效率2路

命中时间伪相联＝命中时间1路＋伪命中率伪相联×2；

伪命中率伪相联＝命中率2路－命中率1路＝(1－失效率2路)－(1－失效率1路)

＝失效率1路－失效率2路解：5.3降低Cache失效率的方法故：

平均访存时间伪相联

＝命中时间1路＋(失效率1路－失效率2路)×2

＋失效率2路×失效开销1路将表5－5中的数据代入上面的公式，得：

平均访存时间伪相联，2KB

＝1＋(0.098－0.076)×2＋(0.076×50)

＝4.844

平均访存时间伪相联，128KB

＝1＋(0.010－0.007)×2＋(0.007×50)

＝1.3565.3降低Cache失效率的方法根据上一个例子中的表5－8，对于2KBCache，

可得：

平均访存时间1路＝5.90个时钟平均访存时间2路＝4.90个时钟对于128KB的Cache有，可得：

平均访存时间1路＝1.50个时钟平均访存时间2路＝1.45个时钟可见，对于这两种Cache容量，伪相联Cache

都是速度最快的。缺点：多种命中时间5.3降低Cache失效率的方法5.3.5硬件预取技术依据：空间局部性思想：在Cache访问失效时，不但从内存中取入对应的块，而且将它的邻近块(通常为后继块)取入一个速度快于主存的缓冲器中，这样当对后继块的访问发生时，可通过访问该缓冲器进行块替换。1.指令和数据都可以预取2.预取内容既可放入Cache，也可放在外缓冲器(速度快于主存)中

例如：指令流缓冲器5.3降低Cache失效率的方法3.预取效果

(1)Jouppi的研究结果

◆指令预取：(4KB，直接映象Cache,块大小＝16字节)5.3降低Cache失效率的方法1个块的指令流缓冲器：捕获15％～25％的失效4个块的指令流缓冲器：捕获50％16个块的指令流缓冲器：捕获72％◆数据预取：(4KB,直接映象Cache)

1个数据流缓冲器：捕获25％的失效还可以采用多个数据流缓冲器(2)Palacharla和Kessler的研究结果

流缓冲器：既能预取指令又能预取数据对于两个64KB四路组相联Cache来说：

8个流缓冲器能捕获50％～70％的失效。5.3降低Cache失效率的方法4.例题例5.7

AlphaAXP21064采用指令预取技术，其实际

失效率是多少？假设从预取缓冲器中找到所需指令(并进行替换)需多花1个时钟周期。5.3降低Cache失效率的方法假设：

预取命中率＝25％

命中时间＝1个时钟周期失效开销＝50个时钟周期5.3降低Cache失效率的方法由表5－4可知，

8KB指令Cache的失效率＝1.10％

平均访存时间预取＝1＋(1.10%×25%×1)＋

(1.10%×(1－25%)×50)

＝1＋0.00275＋0.4125＝1.415

由公式：

平均访问时间＝命中时间＋失效率×失效开销解：

平均访存时间预取

＝命中时间＋失效率×预取命中率×1

＋失效率×(1－预取命中率)×失效开销可得相应的失效率为：失效率＝(平均访问时间－命中时间)/失效开销

＝(1.451－1)/50＝0.83％8KBCache

带预取的

8kBCache失效率1.10％0.83％16KBCache0.64％关键：预取应建立在存储器的空闲频带5.3降低Cache失效率的方法5.3.6由编译器控制的预取1.预取的类型

◆寄存器预取：把数据取到寄存器中◆Cache预取：只将数据取到Cache中◆故障性预取：预取时，若出现虚地址故障或违反访问权限，就会发生异常。◆非故障性预取：预取时，若出现虚地址故障或违反访问权限，并不会导致异常，只是转变为“不预取”。由编译器加入预取指令，在数据被用到之前发出预取请求。5.3降低Cache失效率的方法4.例题2.在预取数据的同时，处理器应能继续执行

只有这样，预取才有意义。非阻塞Cache(非锁定Cache)——指Cache在等待预取数据返回时,还能继续提供指令和数据.3.循环是预取优化的主要对象

失效开销小时：循环体展开1～2次失效开销大时：循环体展开许多次5.3降低Cache失效率的方法例5.8

对于下面的程序，判断哪些访问可能会导致数据Cache失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：

(1)我们用的是一个容量为8KB、块大小为16B的直接映象Cache，它采用写回法并且按写分配。

(2)a、b分别为3×100(3行100列)和101×3的双精度浮点数组，每个元素都是8个字节。当程序开始执行时，这些数据都不在Cache内。5.3降低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];解：(1)计算过程(2)失效情况

数组a数组b

总的失效次数＝251次

(3)改进后的程序(设预取的开销比较大，需提

前7次循环进行)5.3降低Cache失效率的方法5.3降低Cache失效率的方法for(j＝0，j＜100；j＝j＋1){prefetch(b[j＋7][0]);

/*

预取7次循环后所需的b(j,0)*/prefetch(a[0][j＋7]);

/*

预取7次循环后所需的a(0,j)*/a[0][j]＝b[j][0]*b[j＋1][0]}for(i＝1;i<3;i＝i＋1)for(j＝0;j<100;j＝j＋1){prefetch(a[i][j＋7]);

/*

预取7次循环后所需的a(i,j)*/a[i][j]＝b[j][0]*b[j＋1][0];}5.3降低Cache失效率的方法失效情况

总的失效次数＝(7+4)+4+4=19次避免的失效次数

=251-19=232次5.3降低Cache失效率的方法例5.9

在以下条件下，计算例5.8中所节约的时间：

(1)忽略指令Cache失效，并假设数据Cache无冲突失效和容量失效。

(2)假设预取可以被重叠或与Cache失效重叠执行，从而能以最大的存储带宽传送数据。

(3)不考虑Cache失效时，修改前的循环每7个时钟周期循环一次。修改后的程序中，第一个预取循环每9个时钟周期循环一次，而第二个预取循环每8个时钟周期循环一次(包括外层for循环的开销)。

(4)一次失效需50个时钟周期。5.3降低Cache失效率的方法解：

修改前：

循环时间＝300×7＝2100

总失效开销＝251×50＝12550

总运行时间＝2100＋12550＝146505.3降低Cache失效率的方法

修改后：

循环时间＝100×9＋200×8＝2500

总失效时间＝19×50＝950

总运行时间＝2500＋950＝3450

加速比＝14650/3450＝编译器优化2KBCache:降低50％8KBCache：降低75%1.基本思想

在编译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。2.McFaring发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。（例如：转移校正）5.3降低Cache失效率的方法3.数据对存储位置的限制比指令的少，因此更便于优化。通过把数据重新组织，使得在一块数据被从Cache替换出去之前，能最大限度利用其中的数据(访问次数最多)(1)数据合并//提高空间局部性

举例：

/*修改前*/intval[SIZE];intkey[SIZE];5.3降低Cache失效率的方法(2)内外循环交换//提高空间局部性举例：

/*修改前*/以100个字为步长跳跃式访问存储器for(j＝0;j<100;j＝j＋1)for(i＝0;i<5000;i＝i＋1)x[i][j]＝2*x[i][j];

/*修改后*/structmerge{intval;intkey;};structmergemerged_array[size];5.3降低Cache失效率的方法(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];/*修改后*/在访问了一个Cache块中的所有字后才去访问下一个Cache块for(i＝0;i<100;i＝i＋1)for(j＝0;j<5000;j＝j＋1)x[i][j]＝2*x[i][j];5.3降低Cache失效率的方法

/*修改后*/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];}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];5.3降低Cache失效率的方法

举例：

/*

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

}5.3降低Cache失效率的方法(4)分块//提高时间局部性把对数组的整行或整列访问改为按块进行。最坏情况下失效次数：2N3＋N2/*修改后*/B为分块因子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+N25.3降低Cache失效率的方法最坏情况下失效次数：2N3/B＋N25.4.1让读失效优先于写5.4减少Cache失效开销1.因为Cache中的写缓冲器中可能包含读缺失时所需的更新数据，导致写缓冲器对存储器访问的复杂化2.解决问题的方法(读失效的处理)

◆推迟对读失效的处理，直到写缓冲器为空

(缺点：读失效的开销增加，如50％)

◆检查写缓冲器中的内容，如果没有冲突且存储器可访问，就让读缺失继续。3.在写回法Cache中，如采用写缓冲器，也可以采用类似方法（检查写缓冲器中的内容）5.4.2子块放置技术1.为减少标识位的消耗，可采用增加块大小的方法，但这会增加失效开销，故应采用子块放置技术。2.子块放置技术：把Cache块进一步划分为更小的块(子块)，并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效。

Cache与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位。5.4减少Cache失效开销3.举例

(图示)5.4减少Cache失效开销5.4.3请求字处理技术1.请求字

从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字（又称关键字）。2.应尽早把请求字发送给CPU◆尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。◆请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。使得CPU在装入块的其他字的同时能够继续执行。5.4减少Cache失效开销3.这种技术在以下情况下效果不大：◆Cache块较小◆下一条指令正好访问同一Cache块的另一部分。5.4减少Cache失效开销5.4.4非阻塞Cache技术1.非阻塞Cache：Cache失效时仍允许CPU进行

其它的命中访问。即允许“失效下命中”2.进一步提高性能：“多重失效下命中”，

“失效下失效”

(存储器必须能够处理多个失效)3.重叠失效个数对平均访问时间的影响5.4减少Cache失效开销8KB的数据Cache在当前缺失数量变化时，Cache缺失所需的平均时钟周期数非阻塞Cache平均存储器等待时间与阻塞Cache的比值12浮点程序76％51％6439％整数程序81％78％78％重叠失效个数5.4减少Cache失效开销

对于图5.18所描述的Cache，在两路组相联和

“一次失效下命中”这两种措施中，哪一种对浮

点程序更重要？对整数程序的情况如何？

假设8KB数据Cache的平均失效率为：

对于浮点程序，直接映象Cache为11.4%，两路

组相联Cache为10.7%；

对于整数程序，直接映象Cache为7.4%，两路

组相联Cache为6.0%。

并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期。例5.115.4减少Cache失效开销对于浮点程序，平均存储器等待时间为：失效率直接映象×失效开销＝11.4%×16＝1.82

失效率两路组相联×失效开销＝10.7%×16＝1.711.71/1.82＝0.94>76%

对于整数程序，平均存储器等待时间为：失效率直接映象×失效开销＝7.4%×16＝1.18

失效率两路组相联×失效开销＝6.0%×16＝0.960.96/1.18=0.81=81%结论:对浮点运算采用“一次失效下命中”的直接映象措施比采用“两路组相联”技术更有效.对整数运算两种策略有相同性能。解：5.4减少Cache失效开销5.4.5两级Cache1.应把Cache做得更快？还是更大？

答案：二者兼顾，再增加一级Cache◆第一级Cache(L1)小而快◆第二级Cache(L2)容量大2.性能分析平均存储器访问时间

＝命中时间L1＋失效率L1×失效开销L1

＝命中时间L1＋失效率L1×

(命中时间L2＋失效率L2×失效开销L2)5.4减少Cache失效开销3.局部失效率与全局失效率局部失效率＝该级Cache的失效次数/到达

该级Cache的访问次数例如：上述式子中的失效率L1，失效率L2全局失效率＝该级Cache的失效次数/CPU

发出的访存的总次数

全局失效率L2＝失效率L1×失效率L2全局失效率L1＝失效率L1

局部失效率一般不能反映对提高系统实际运行性能所发挥的作用,因此评价第二级Cache时，一般使用全局失效率这个指标。5.4减少Cache失效开销4.当第二级Cache比第一级Cache大得多时，两

级Cache的全局失效率和第二级Cache相同的

单级Cache的失效率非常接近。5.4减少Cache失效开销5.第二级Cache的参数

第二级Cache不会影响CPU的时钟频率，仅影响一级Cache的缺失代价，因此其设计有更大的考虑空间。

两个问题：

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

◆成本是多少？

(1)容量

第二级Cache的容量一般比第一级的大许多，如512KB（如果第二级Cache的容量仅大一点，局部缺失率会很高）5.4减少Cache失效开销(2)相联度

第二级Cache可采用较高的相联度或伪相联方法例5.12

给出有关第二级Cache的以下数据：⑴两路组相联使命中时间增加10%×CPU时钟周期⑵对于直接映象，命中时间L2＝10个时钟周期⑶对于直接映象，局部失效率L2＝25%⑷对于两路组相联，局部失效率L2＝20%⑸失效开销L2＝50个时钟周期试问第二级Cache的相联度对第一级Cache失效开销的影响如何？5.4减少Cache失效开销解：

对于一个直接映象的第二级Cache来说，第一级Cache的失效开销为：失效开销直接映象，L1

＝10＋25%×50＝22.5个时钟周期

对于两路组相联第二级Cache来说，命中时间增加了10%(0.1)个时钟周期，故第一级Cache的失效开销为：失效开销两路组相联，L1

＝10.1＋20%×50＝20.1个时钟周期

故对于第二级Cache来说，两路组相联优于直接映象。5.4减少Cache失效开销(3)块大小第二级Cache可采用较大的块，

如64、128、256字节。

为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。(4)多级包容性

一级Cache的数据总是包含在二级Cache中

优点：数据一致性仅检查二级Cache确定

缺点：不同级别Cache的块大小不同5.4减少Cache失效开销5.5减少命中时间2.应使Cache足够小，以便可以与CPU一起放

在同一块芯片上。

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

当今的许多计算机中，往往是Cache的访问时间

限制了处理器的时钟频率。1.硬件越简单，速度就越快；5.5.1容量小、结构简单的Cache1.虚拟Cache

访问Cache的索引以及Cache中的标识都是虚拟地址(一部分)。

虚拟地址是访问硬盘上的虚拟存储器的地址。2.并非人人都采用虚拟Cache原因一：不同进程虚地址空间的相同。5.5.2虚拟Cache5.5减少命中时间3.解决方法：(1)进程切换时清空虚拟Cache。(2)在地址标识中增加PID字段(进程标识符)。三种情况下失效率的比较：

单进程，PIDs，清空

PIDs与单进程相比：＋0.3％～＋0.6％

PIDs与清空相比：－0.6％～－4.3%5.5减少命中时间4.原因二：同义和别名(不同虚地址对应相同实地址情况)

可能导致同一数据在虚拟Cache中存在两个副本。

解决方法：(1)反别名法——用硬件来保证每一个Cache块对应唯一实地址（物理地址）。(2)页着色——Sun公司的UNIX系统要求所有有别名的地址最后18位相同，而直接映象Cache的索引来自于这最后18位(Cache容量不超过218字节)，这使得所有别名映象到同一Cache块位置。5.5减少命中时间5.根据页内位移(这部分虚实地址相同)进行Cache索引(同时进行虚实地址转换)，用实地址判断是否命中。优点：兼得虚拟Cache和物理Cache的好处(Cache索引和虚实地址转换同时进行)局限性：Cache容量受到限制

直接映象：Cache容量≤页大小组相联映象：Cache容量≤页大小×相联度5.5减少命中时间5.5.3将写操作流水化以加快写命中读写命中一般包含两步：(1)判断是否命中。(2)(如果命中)对Cache进行读写。对读操作：两步可并行进行。对写操作：两步必须串行进行。解决方法:将写操作的两步操作流水化.5.5减少命中时间优化技术失效率失效开销命中时间硬件复杂度评价增加块大小+-

0实现容易；RS/6000550采用了128字节提高相联度+

-1MIPSR10000为4路组相联VictimCache+

2HP7200中采用了类似的技术伪相联Cache+

2已应用于MIPSR10000的第二级Cache硬件预取指令和数据+

2数据预取比较困难；仅被几台机器采用，如：Alpha21064编译器控制的预取+

3需采用非阻塞cache；有几种机器支持它用编译技术减少Cache失效次数+

0向软件提出了新要求；有些机器提供了编译器选项使读失效优先级高于写

+

1在单处理机上实现容易，被广泛使用子块调入

+

1主要用于减少标识的数目尽早重启动和关键字优先

+

2已应用于MIPSR10000和IBM620非阻塞Cache

+

3已应用于Alpha21064和R10000中第二级Cache

+

2硬件代价大；两级Cache的块大小不同时实现困难；被广泛采用容量小且结构简单的Cache-

+0实现容易，被广泛使用虚拟Cache

+2对于小容量Cache来说实现容易，已应用于Alpha21064流水化写

+1已应用于Alpha210645.6.1存储器技术1.主存的主要性能指标：延迟和带宽2.以往：

Cache主要关心存储器延迟（直接影响了Cache失效开销），I/O主要关心存储器带宽现在：Cache关心两者(由于二级Cache使用较大的块)5.6主存1.存储器延迟的参数：访问时间，存储周期2.地址线复用：行选通（RAS）和列选通（CAS）5.6.1存储器技术存储器延迟的参数：访问时间，存储周期访问时间：从发出读请求到返回被请求数据之间的时间。存储周期：连续两次存储器请求所需要的最小时间间隔。注：通常，由于必须在地址线稳定后才能进行下一次存储器访问，所以存储周期大于访问时间。地址线复用（多路复用）：在行选通（RAS）方式下传送前一半地址，而后在列选通（CAS）方式下传送后一半地址。5.6主存3.DRAM（存储器）与SRAM（Cache）DRAM：DynamicRandomAccessMemory，即动态随机访问存储器，最为常见的系统内存。DRAM只能将数据保持很短的时间。为了保持数据，DRAM使用电容存储，所以必须隔一段时间刷新（refresh）一次，如果存储单元没有被刷新，存储的信息就会丢失。（关机就会丢失数据）SRAM：StaticRandomAccessMemory，静态随机访问存储器，它是一种具有静止存取功能的内存，速度快，不需要刷新电路即能保存它内部存储的数据。但集成度低，功耗较大，相同的容量体积较大，而且价格较高，少量用于关键性系统以提高效率。容量：4～8：1存储周期：8～16:1价格：1：8～165.6主存年份芯片容量行选通(RAS)最慢的DRAM最快的DRAM列选通

(CAS)周期时间19801983198619891992199564K位256K位1M位4M位16M位64M位180ns150ns120ns100ns80ns65ns150ns120ns100ns80ns60ns50ns75ns50ns25ns20ns15ns10ns250ns220ns190ns165ns120ns90ns4.Amdahl经验规则

为了保持系统平衡，存储容量和性能应随CPU速度的提高而线性增加。5.各代DRAM的典型时间参数:5.6.2提高主存性能的