存储层次课件

5.1.1从单级存储器到多级存储器1.从用户的角度来看，存储器的三个主要指标是：

容量，速度，价格(每位价格)5.1存储器的层次结构

存储层次

2.

人们对这三个指标的期望:3.

这三个指标相互矛盾:4.解决方法

采用多种存储器技术，构成存储层次:5.1.2

存储层次的性能参数

C，S，TA设：S

──容量

TA──访问时间

C

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

M1的参数：S1，TA1，C1

M2的参数：S2，TA2，C21.每位价格CC＝─────如果S1<<S2，CC2C1S1＋C2S2S1＋S22.命中率H和失效率F

命中率H

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

H＝N1/(N1＋N2)

N1

──访问M1的次数

N2

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

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

F＝1－H3.平均访问时间TA对大部分系统：

TM＝TA2＋TB由于

TA＝H

TA1＋(1－H)(TA1+TM)于是

TA＝TA1＋(1－H)TM

或

TA＝TA1＋F

TM

TA1──命中时间

TM

──失效开销5.1.3“Cache－主存”和“主存－辅存”层次

一般来说：

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

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

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

访问速度的比值

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

层次的区别5.1.4存储层次的四个问题当把一个块调入高一层(靠近CPU)存储器时，

可以放在哪些位置上?(映象规则)当所要访问的块在高一层存储器中时，如何

找到该块?

(查找算法)3.

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

(替换算法)4.

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

(写策略)1.

2.5.2Cache基本知识5.2.1映象规则1.全相联映象

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

Cache中的任意一个位置。特点：空间利用率最高，冲突概率最低，

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

Cache中唯一的一个位置。◆特点：空间利用率最低，冲突概率最

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

块，若它映象到Cache的

第j

块，则:

j＝imod(M)

（M为Cache的块数）

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

中唯一的一个组中的任何一个位置。◆设M＝2m，则当表示为二进制数时，j实际

上就是i的低m位：3.组相联映象：m位ji：组相联是直接映象和全相联的一种折衷◆上述的j

和k

通常称为索引◆

组的选择常采用位选择算法

若主存第i块映象到第k

组，则:

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

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

上就是i的低g位：g

位k主存块地址i：相联度一定是越大越好？◆绝大多数计算机的Cache:n≤4◆

n路组相联：每组中有n个块(n＝M/G)

n

称为相联度。

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

块冲突概率就越低，失效率也就越低。全相联直接映象组相联n

(路数)G

(组数)MM111＜n＜M1＜G＜M5.2.2查找方法1.如何确定Cache中是否有所要访问的块？

若有的话如何确定其位置？

◆目录表的结构◆查找范围：候选位置所对应的目录表项◆并行查找与顺序查找提高性能的重要思想：主候选位置(MRU块)◆并行查找的实现方法：

▲

相联存储器

▲

单体多字存储器＋比较器举例：４路组相联并行标识比较◆直接映象Cache的查找过程◆

４路相联Cache的查找过程5.2.3替换算法

所要解决的问题：当新调入一块，而Cache

又已被占满时，替换哪一块？2.FIFO3.LRU

优点：失效率低1.随机法

优点：实现简单LRU和随机法的失效率的比较5.2.4写策略1.“写”操作所占的比例

Load指令：26％

Store指令：9％“写”在所有访存操作中所占的比例：

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

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

9％/(26％＋9％)≈25％3．“写”访问有可能导致Cache和主存内容的不一致2.“写”操作必须在确认是命中后才可进行4．两种写策略

◆

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

也写入下一级存储器。

◆

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

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

(设置“污染位”)5．两种写策略的比较

◆写回法的优点：速度快，所使用的存储器频

带较低；

◆写直达法的优点：易于实现，一致性好。6.写缓冲器8.写策略与调块

写回法──按写分配

写直达法

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

◆

按写分配(写时取)

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

Cache，再行写入。

◆

不按写分配(绕写法)

写失效时，直接写入下一级存储器而不调块。5.2.5Cache举例例子：DEC的AlphaAXP21064中的内部数据

Cache。1.简介

容量：8KB

块大小：32B

块数：256

调块：不按写分配映象方法：直接映象“写”策略：写直达写缓冲器大小：4个块2.结构图3.失效情况下的操作读失效:Cache向CPU发出一个暂停信号,通知它等 待，并从下一级存储器中读如32个字节， 填入对应的Cache块。写失效:CPU不对Cache进行操作。4.写缓冲的结构写合并:当把数据写入写缓冲器时，判断本次所写

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

的地址相同，若是，则把新数据与该块合并。5.混合Cache与分离Cache访存操作： 指令访问(读指令)

数据访问(读写数据)分离Cache： 指令Cache+数据Cache混合Cache： 单一的Cache优缺点： (1)实现成本

(2)结构冲突

16KB容量1KB2KB4KB8KB32KB指令Cache3.06%失效率的比较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%分离Cache平均失效率的计算：访问指令Cache的百分比×指令Cache的失效率＋访问数据Cache的百分比×数据Cache的失效率访问指令Cache的百分比：

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

访问数据Cache的百分比：

(26％＋9％)/(100％＋26％＋9％)≈25％6.分离Cache与混合Cache平均失效率的比较前提：指令Cache容量+数据Cache容量

=混合Cache容量

5.2.6性能分析2.平均访问时间

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

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

开销为50个时钟周期，在混合Cache中一次load

或store操作访问Cache的命中时间都要增加一个

时钟周期(因为混合Cache只有一个端口，无法同

时满足两个请求。按照前一章中有关流水线的术

语，混合Cache会导致结构冲突)，根据表5－4所

列的失效率，试问指令Cache和数据Cache容量均1.失效率解：

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

分离Cache的总体失效率为：

(75%×0.64%)＋(25%×6.47%)＝2.10%

根据表5－4，容量为32KB的混合Cache的失

效率略低一些，只有1.99%.为16KB的分离Cache和容量为32KB的混合Cache相

比，哪种Cache的失效率更低？又假设采用写直达

策略，且有一个写缓冲器，并且忽略写缓冲器引

起的等待。请问上述两种情况下平均访存时间各

是多少？平均访存时间公式可以分为指令访问和数据

访问两部分：平均访存时间＝指令所占的百分比×

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

数据所占的百分比×

(数据命中时间＋数据失效率×失效开销)所以根据表5－4，两种结构的平均访存时间分别为：平均访存时间分离＝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.243.程序执行时间

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

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

×时钟周期时间其中，

存储器停顿周期数＝“读”的次数×读失效率×读失效开销

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

存储器停顿周期数＝访存次数×失效率×

失效开销于是

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

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

我们用一个和AlphaAXP类似的机器作为

第一个例子。假设Cache失效开销为50个时钟

周期，当不考虑存储器停顿时，所有指令的

执行时间都是2.0个时钟周期，Cache的失效

率为2%，平均每条指令访存1.33次。试分析

Cache对性能的影响。考虑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.5例5.3

考虑两种不同组织结构的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%解：平均访存时间=命中时间+失效率×失效开销平均访存时间直接=2.0+(0.014×70)=2.98ns平均访存时间组相联=2.0×1.10+(0.010×70)=2.90nsCPU时间＝IC×[CPIexe＋访存次数/指令数×

失效率×失效开销]×时钟周期时间＝IC×[CPIexe×时钟周期时间＋访存次数/指令数×失效率×失效开销

×时钟周期时间]CPU时间直接=IC×(2.0×2+(1.3×0.014×70))=5.27×ICCPU时间组相联=IC×(2.0×2×1.10+(1.3×0.010×70))=5.31×IC平均访存时间＝命中时间＋失效率×失效开销可以从三个方面改进Cache的性能：(1)降低失效率(2)减少失效开销

(3)减少Cache命中时间下面介绍15种Cache优化技术5.2.7改进Cache性能(1)强制性失效(Compulsorymiss)

当第一次访问一个块时，该块不在

Cache中，需从下一级存储器中调入Cache，

这就是强制性失效。

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

如果程序执行时所需的块不能全部调

入Cache中，则当某些块被替换后，若又5.3降低Cache失效率的方法1.三种失效(3C)

重新被访问，就会发生失效。这种失效称

为容量失效。(3)冲突失效(Conflictmiss)

在组相联或直接映象Cache中，若太多

的块映象到同一组(块)中，则会出现该组

中某个块被别的块替换(即使别的组或块有

空闲位置)，然后又被重新访问的情况。这

就是发生了冲突失效。

(碰撞失效，干扰失效)2.三种失效所占的比例(SPEC92)可以看出：(1)相联度越高，冲突失效就越少；(2)强制性失效和容量失效不受相联度的影响；(3)强制性失效不受Cache容量的影响，但容

量失效却随着容量的增加而减少；(4)表中的数据符合2:1的Cache经验规则，即

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

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

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

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

(理想情况：全相联)3.减少三种失效的方法4.许多降低失效率的方法会增加命中时间或

失效开销5.3.1增加Cache块大小2.增加块大小会增加失效开销1.失效率与块大小的关系

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

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

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

块大小就越大。3.例题例5.4

假定存储系统在延迟40个时钟周期后，每2个

时钟周期能送出16个字节。即:经过42个时钟周期，

它可提供16个字节；经过44个时钟周期，可提供32

个字节；依此类推。试问对于表5-6中列出的各种

容量的Cache，在块大小分别为多少时，平均访存

时间最小？解：平均访存时间为：平均访存时间＝命中时间＋失效率×失效开销

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

平均访存时间＝1＋（15.05%×42）＝7.321个时钟周期而对于块大小为256B的大小为256KB的Cache来说，平均访存时间为：

平均访存时间＝1＋（0.49%×72）＝1.353个时钟周期表5.7列出了在这两种极端情况之间的各种块大小和各种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的方法实际意义不大2.2:1Cache经验规则

容量为N

的直接映象

Cache≈容量为N/2的两路组相联Cache3.提高相联度是以增加命中时间为代价

例如：

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

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

增加2％4.例题

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

时钟周期：

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

时钟周期4路＝1.12×时钟周期1路时钟周期8路＝1.14×时钟周期1路假定命中时间为1个时钟，失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表5－5中的失效率，试问当Cache为多大时，以下不等式成立？例5.5平均访存时间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路×50

在每种情况下的失效开销相同，都是

50个时钟周期。把相应的失效率代入上式，

即可得平均访存时间。

例如，1KB的直接映象Cache的平均

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

＝7.65

容量为128KB的8路组相联Cache的平均

访存时间为：平均访存时间8路

＝1.14＋(0.006×50)

＝1.44表5-8Cache容量（K字节）相联度（路）124817.656.606.225.4425.904.904.624.0944.603.953.573.1983.303.002.872.59162.452.202.122.04322.001.801.771.79641.701.601.571.591281.501.451.421.441.基本思想

在Cache和它从下一级存储器调数据

的通路之间设置一个全相联的小Cache，

用于存放被替换出去的块(称为Victim)，

以备重用。工作过程5.3.3VictimCache

对于减小冲突失效很有效，特别是对

于小容量的直接映象数据Cache，作用尤其

明显。

例如，项数为4的VictimCache:

使4KBCache的冲突失效减少20%～90%2.作用1.直接映象vs．组相联5.3.4伪相联Cache(列相联)2.伪相联Cache优点缺点直接映象组相联命中时间小命中时间大失效率高失效率低取直接映象及组相联两者的优点：命中时间小，失效率低(1)基本思想及工作原理

在逻辑上把直接映象Cache的空间上下

平分为两个区。对于任何一次访问，伪相联

Cache先按直接映象Cache的方式去处理。若

命中，则其访问过程与直接映象Cache的情

况一样。若不命中，则再到另一区相应的位

置去查找。若找到，则发生了伪命中，否则

就只好访问下一级存储器。(2)快速命中与慢速命中要保证绝大多数命中都是快速命中。3.例题例5.6

假设当在按直接映象找到的位置处没有发

现匹配、而在另一个位置才找到数据(伪命中)

需要2个额外的周期。仍用上个例子中的数据，

问：当Cache容量分别为2KB和128KB时，直接

映象、两路组相联和伪相联这三种组织结构中，

哪一种速度最快？首先考虑标准的平均访存时间公式：

平均访存时间伪相联

＝命中时间伪相联＋失效率伪相联×失效开销伪相联由于：失效率伪相联＝失效率2路命中时间伪相联＝命中时间1路＋伪命中率伪相联×2；伪命中率伪相联＝命中率2路－命中率1路＝(1－失效率2路)－(1－失效率1路)

＝失效率1路－失效率2路解：故：平均访存时间伪相联

＝命中时间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.356根据上一个例子中的表5－8，对于2KBCache，

可得：平均访存时间1路＝5.90个时钟平均访存时间2路＝4.90个时钟对于128KB的Cache有，可得：平均访存时间1路＝1.50个时钟平均访存时间2路＝1.45个时钟可见，对于这两种Cache容量，伪相联Cache

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

外缓冲器(速度快于主存)中例如：指令流缓冲器3.预取效果

(1)Jouppi的研究结果

◆指令预取：(4KB，直接映象Cache,

块大小＝16字节)1个块的指令流缓冲器：捕获15％～25％

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

8个流缓冲器能捕获50％～70％的失效。4.例题例5.7AlphaAXP21064采用指令预取技术，其实际

失效率是多少？若不采用指令预取技术，Alpha

APX21064的指令Cache必须为多大才能保持平均访

存时间不变？解：假设从预取缓冲器中找到所需指令(并进行替换)需多花1个时钟周期。

平均访存时间预取

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

＋失效率×(1－预取命中率)×失效开销假设：

预取命中率＝25％

命中时间＝1个时钟周期失效开销＝50个时钟周期由表5－4可知，8KB指令Cache的失效率＝1.10％故平均访存时间预取＝1＋(1.10%×25%×1)＋

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

＝1＋0.00275＋0.4125

＝1.415

由公式：

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

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

带预取的

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

◆寄存器预取：把数据取到寄存器中

◆

Cache预取：只将数据取到Cache中

◆故障性预取：预取时，若出现虚地址故障

或违反访问权限，就会发生异常。

◆非故障性预取：预取时，若出现虚地址故

障或违反访问权限，并不会导致异常，只

是转变为“不预取”。由编译器加入预取指令，在数据被用到之前

发出预取请求。4.例题2.在预取数据的同时，处理器应能继续执行

只有这样，预取才有意义。非阻塞Cache(非锁定Cache)3.

循环是预取优化的主要对象

失效开销小时：循环体展开1～2次失效开销大时：循环体展开许多次例5.8

对于下面的程序，判断哪些访问可能会导致

数据Cache失效。然后，加入预取指令以减少失

效。最后，计算所执行的预取指令的条数以及通

过预取避免的失效次数。假定：

(1)我们用的是一个容量为8KB、块大小为

16B的直接映象Cache，它采用写回法并

且按写分配。

(2)a、b分别为3×100(3行100列)和101×3

的双精度浮点数组，每个元素都是8个

字节。当程序开始执行时，这些数据都

不在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次循环进行)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．9

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

(1)忽略指令Cache失效，并假设数据Cache

无冲突失效和容量失效。

(2)假设预取可以被重叠或与Cache失效重

叠执行，从而能以最大的存储带宽传送

数据。

(3)不考虑Cache失效时，修改前的循环每7

个时钟周期循环一次。修改后的程序中，失效情况

总的失效次数＝(7+4)+4+4=19次解：

修改前：循环时间＝300×7＝2100

总失效开销＝251×50＝12550

总运行时间＝2100＋12550＝14650

第一个预取循环每9个时钟周期循环一次，

而第二个预取循环每8个时钟周期循环一

次(包括外层for循环的开销)。

(4)一次失效需50个时钟周期。

修改后：循环时间＝100×9＋200×8＝2500

总失效时间＝19×50＝950

总运行时间＝2500＋950＝3450

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

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

重新组织，以降低Cache失效率。2.McFaring

发现：通过对指令进行重新排序，

可有效地降低指令Cache的失效率。3.数据对存储位置的限制比指令的少，因此

更便于优化。

通过把数据重新组织，使得在一块数

据被从Cache替换出去之前，能最大限度

利用其中的数据(访问次数最多)(1)数据合并

举例：

/*修改前*/

int

val[SIZE];

intkey[SIZE];(2)内外循环交换

举例：

/*

修改前*/

for(j＝0;j<100;j＝j＋1)for(i＝0;i<5000;i＝i＋1)x[i][j]＝2*x[i][j];

/*修改后*/

structmerge{

int

val;

intkey;

};

structmergemerged_array[size];(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<100;i＝i＋1)for(j＝0;j<000;j＝j＋1)x[i][j]＝2*x[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];}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];(4)分块

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

举例：

/*

修改前*/

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/*

修改后*/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.4.1让读失效优先于写5.4减少Cache失效开销1.Cache中的写缓冲器导致对存储器访问的

复杂化2.解决问题的方法(读失效的处理)

◆推迟对读失效的处理

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

◆检查写缓冲器中的内容3.在写回法Cache中，也可采用写缓冲器5.4.2子块放置技术1.为减少标识的位数，可采用增加块大小的

方法，但这会增加失效开销，故应采用子

块放置技术。2.子块放置技术：把Cache块进一步划分为更

小的块(子块)，并给每个子块赋予一位有

效位，用于指明该子块中的数据是否有效。

Cache与下一级存储器之间以子块为单位传

送数据。但标识仍以块为单位。3.举例

(图示)5.4.3请求字处理技术1.请求字

从下一级存储器调入Cache的块中，只有

一个字是立即需要的。这个字称为请求字。

2.应尽早把请求字发送给CPU◆尽早重启动：调块时，从块的起始位置开

始读起。一旦请求字到达，就立即发送给

CPU，让CPU继续执行。

◆请求字优先：调块时，从请求字所在的位

置读起。这样，第一个读出的字便是请求

字。将之立即发送给CPU。3.这种技术在以下情况下效果不大：

◆

Cache块较小

◆下一条指令正好访问同一Cache块的另

一部分。5.4.4非阻塞Cache技术1.非阻塞Cache：Cache失效时仍允许CPU进行

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

“失效下失效”

(存储器必须能够处理多个失效)3.重叠失效个数对平均访问时间的影响非阻塞Cache平均存储器等待时间

与阻塞Cache的比值12浮点程序76％51％6439％整数程序81％78％78％重叠失效个数

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

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

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

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

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

组相联Cache为10.7%；

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

组相联Cache为6.0%。并且假设平均存储器等待时

间是失效率和失效开销的积，失效开销为16个时钟

周期。例5.10对于浮点程序，平均存储器等待时间为：失效率直接映象×失效开销＝11.4%×16＝1.82

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

对于整数程序：失效率直接映象×失效开销＝7.4%×16＝1.18

失效率两路组相联×失效开销＝6.0%×16＝0.960.96/1.18=0.81结论:对浮点运算采用“一次失效下命中”措施比采用“两路组相联”技术更有效.解：5.4.5两级Cache1.应把Cache做得更快？还是更大？

答案：二者兼顾，再增加一级Cache

◆第一级Cache(L1)小而快

◆第二级Cache(L2)容量大2.性能分析

平均访问时间

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

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

(命中时间L2＋失效率L2×失效开销L2)3.局部失效率与全局失效率

局部失效率＝该级Cache的失效次数/到达

该级Cache的访问次数例如：上述式子中的失效率L2

全局失效率＝该级Cache的失效次数/CPU

发出的访存的总次数

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

局部失效率一般不能反映对提高系统实际运行性能所发挥的作用,因此评价第二级Cache时，一般使用全局失效率这个指标。

4.当第二级Cache比第一级Cache大得多时，两

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

单级Cache的失效率非常接近。5.第二级Cache的参数

第二级Cache不会影响CPU的时钟频率，

因此其设计有更大的考虑空间。

两个问题：

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

◆成本是多少？

(1)容量第二级Cache的容量一般比第一级的

大许多，如512KB

(2)相联度第二级Cache可采用较高的相联度或伪

相联方法例5.12

给出有关第二级Cache的以下数据：

⑴两路组相联使命中时间增加10%×CPU时钟周期

⑵对于直接映象，命中时间L2＝10个时钟周期

⑶对于直接映象，局部失效率L2＝25%⑷对于两路组相联，局部失效率L2＝20%⑸失效开销L2＝50个时钟周期试问第二级Cache的相联度对失效开销的影响如何？解：对于一个直接映象的第二级Cache来说，

第一级Cache的失效开销为：

失效开销直接映象，L1

＝10＋25%×50＝22.5个时钟周期对于两路组相联第二级Cache来说，命中

时间增加了10%(0.1)个时钟周期，故第一级

Cache的失效开销为：

失效开销两路组相联，L1

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

故对于第二级Cache来说，两路组相联优于直接映象。(3)块大小

第二级Cache可采用较大的块，

如64、128、256字节。

为减少平均访存时间，可以让容量较小

一的第一级Cache采用较小的块，而让容量较

大的第二级Cache采用较大的块。5.5减少命中时间2.应使Cache足够小，以便可以与CPU一起放

在同一块芯片上。

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

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

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

访问Cache的索引以及Cache中的标识都

是虚拟地址(一部分)。2.并非人人都采用虚拟Cache原因一：不同进程虚地址空间的相同。3.解决方法：(1)进程切换时清空虚拟Cache。(2)在地址标识中增加PID字段(进程标识符)。三种情况下失效率的比较：

单进程，PIDs，清空

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

PIDs与清空相比：－0.6％～－4.3%5.5.2虚拟Cache4.原因二：同义和别名(不同虚地址对应相同实地址情况)

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

(Cache索引和虚实地址转换同时进行)局限性：Cache容量受到限制

直接映象：Cache容量≤页大小组相联映象：Cache容量≤页大小×相联度5.5.3将写操作流水化以加快写命中

读写命中一般包含两步：(1)判断是否命中。(2)(如果命中)对Cache进行读写。对读操作：两步可并行进行。对写操作：两步必须串行进行。解决方法:将写操作的两步操作流水化.

优化技术失效率失效开销命中时间硬件复杂度评价增加块大小+-

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主要关心延迟，I/O主要关心带宽3.现在：Cache关心两者(由于二级Cache使用较大的块)5.6主存1.存储器延迟：访问时间，存储周期2.地址线复用：行选通和列选通3.DRAM与SRAM

容量：4～8：1

存储周期：8～16:1

价格：1：8～16

一般来说：

主存：DRAMCache：SRAM4.Amdahl经验规则为了保持系统平衡，存储容量和性能应随CPU速度的提高而线性增加。5.各代DRAM的典型时间参数:年份芯片容量行选通(RAS)最慢的DRAM最快的DRAM列选通

(CAS)周期时间19801983198619891992199564K位256K位1M位4M位16M位64M位180ns150ns120ns100ns80ns65ns150ns120ns100ns80ns60ns50ns75ns50ns25ns20ns15ns10ns250ns220ns190ns165ns120ns90ns表5-10各代DRAM的典型时间参数5.6.2提高主存性能的存储器组织结构1.增加存储器的宽度2.采用简单的多体交叉存储器3.独立存储体◆设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存。◆每个体有独立的地址线◆非阻塞Cache与多体结构◆超体:多体交叉存储器+独立存储体4.避免存储体冲突

◆体冲突：两个请求要访问同一个体

◆减少冲突：采用许多体例如：NECSX/3最多128个体

问题仍旧存在：例：

intx[256][512];for(j=0;j<512;j++)for(i=0;i<256;i++)

x[i][j]=2*x[i][j]◆解决体冲突的方法：

▲

软件方法(编译器)

1.循环交换优化例：

intx[256][512];for(i=0;i<256;i++)for(j=0;j<512;j++)

x[i][j]=2*x[i][j]

2.扩展数组的大小，使之不是2的幂。

▲

硬件方法使体数为素数以减少体冲突机会。一般取：

体号=地址mod体数体内地址=地址/体数当存储体数为素数，且为2的幂减1时，取

体号=地址mod体数体内地址＝地址mod存储体中的字数(可以直接载取)根据中国剩余定理，可有以下一一对应：地址

(体号，体内地址)◆举例

体内地址存储体顺序交叉取模交叉012345表5-11顺序交叉和取模交叉的地址映象举例6701201201201683456789101112131421222315161718192091171810231911124202113562214157235.DRAM专用交叉结构

◆三种方式

▲Nibble方式每次访问时，除给出所需位外，还能给出其后3位。

▲

Page方式行选通(RAS)后，整个一行内容并行输出到缓冲器，随后可以SRAM速度随几访问其中的任意一位。

▲

Staticcolumn方式与Page方式类似，只是在列地址改变时，数据线内容跟随变化而无需触发列访问选通线。◆

RAMBUS

用总线方式取代RAS/CAS能自己完成刷新能在一次访存期间(发送地址到返回数据)通过总线接受另一次访存请求数据宽度一个字节最高2ns传送一个字节。

5.7虚拟存储器提出于1961年解决应用程序对主存容量的越来越高要求以及主存难以满足这一问题.从程序覆盖技术发展而来1.基本想法外存作为基本存储器,存放执行中的程序和数据为每个进程分配一个独立的逻辑空间(虚拟空间),在这个空间中每条指令和数据都分配一个逻辑地址(虚拟地址)5.7.1虚拟存储器基本原理指令与指令、指令与数据的访问关系用逻辑地址来表达指令和数据在被访问到时被调入内存,相应的从逻辑地址到物理地址(主存地址)的映射被建立，然后按照这种映射关系在指令运行时把逻辑地址转化成物理地址，实现实际的访问。2.虚拟存储器的特点

◆多个进程可以共享主存空间

◆

程序员不必做存储管理工作

◆采用动态再定位，简化了程序的装入3.虚拟存储器的分类按照空间管理单位

◆页式

把空间分成大小相同的块(4KB

64KB)，称为页面

◆段式

把空间分成可变长的块，称为段，段的大小可根据程序的逻辑意义来确定，一般是程序模块。4.有关虚拟存储器的四个问题◆映象规则

全相联(失效开销太大)◆查找算法

页表，段表页表每一项对应一个虚页号每一项一般有这样一些域

(1)该页是否已在主存中

(2)该页在主存中的起始地址(物理页号)(3)其他信息(如保护信息等)

页表通常非常大◆替换算法

LRU

主存的每个页面设置一个使用位◆写策略

写回法(磁盘不支持单