计算机体系结构第五章-2课件

一.三种类型的不命中（3C）1.强制性不命中（强制性失效，Compulsorymiss）当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。（也称为冷启动失效或首次访问失效。）2.容量不命中（容量失效，Capacitymiss）

如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。5.3

降低Cache不命中率3.冲突不命中（冲突失效，Conflictmiss）

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

降低Cache不命中率减少三种失效的方法强制性失效：增加块大小，预取（本身很少）容量失效：增加容量

（抖动现象）冲突失效：提高相联度（理想情况：全相联）许多降低失效率的方法会增加命中时间或失效开销5.3

降低Cache不命中率二.增加Cache块大小当Cache的容量一定时，块的大小对命中率的影响非常大。下图表示随着Cache块由小到大的变化，命中率H上升和下降的规律。

最佳1

初始

块大小命中率H增强了空间局部性，减少了强制性不命中

减少了Cache中块的数目，可能会增加冲突不命中5.3

降低Cache不命中率措施：适当增加块的大小，但不能增大到使不命中率上升的程度。各种块大小情况下Cache的不命中率块大小（字节）Cache容量（字节）1K4K16K64K256K1615.05%8.57%3.94%2.04%1.09%3213.34%

7.24%2.87%1.35%0.70%6413.76%7.00%

2.64%

1.06%0.51%12816.64%7.78%2.77%1.02%

0.49%

25622.01%9.51%3.29%1.15%0.49%负面影响，增加块大小会减少块的数目，可能会增加冲突失效。

平均访存时间＝命中时间＋不命中率×不命中开销当失效开销超过了不命中率下降带来的好处，平均访存时间就会增加。各种块大小情况下Cache的平均访存时间

块大小（字节）不命中开销（时钟周期）Cache容量（字节）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.870

4.1862.2631.5941.30864487.6054.3602.2671.509

1.245

1285610.3185.3572.5511.5711.2742567216.8477.8473.3691.8281.353另外，增加块大小同时也会增加不命中开销。三.提高相联度

1.相联度（n值）

在组相联映像中，如果每组中有n个块，则称该映像规则为n路组相联。n的不同取值构成了一系列不同相联度的组相联。5.3

降低Cache不命中率当n=1时，为直接映像。当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块0块V-1块V块2V-1块(K-1)V块KV-1组0组1组K-1组(t-1)K组(t-1)K+1组tK-1区t-1主存储器Cache2.相联度越高（即n值越大），Cache空间的利用率就越高，块冲突概率就越低，因而Cache的不命中率就越低。同时，提高相联度则可能以增加命中时间为代价。5.3

降低Cache不命中率例:假定提高相联度会按下列比例增大处理器时钟周期：

时钟周期2路＝1.10×时钟周期1路时钟周期4路＝1.12×时钟周期1路时钟周期8路＝1.14×时钟周期1路假定命中时间为一个时钟周期，直接映象情况下失效开销为50个时钟周期，而且假设不必将失效开销取整。使用表5.5中的失效率，试问当Cache容量一定时，各种相联度下的平均访存时间为多少？（是否相联度越大平均访存时间越短）5.3

降低Cache不命中率解在各种相联度的情况下，平均访存时间分别为：平均访存时间8路

=命中时间8路

+失效率8路×失效开销8路

=1.14＋失效率8路×50

平均访存时间4路

=1.12＋失效率4路×50

平均访存时间2路

=1.10＋失效率2路×50

平均访存时间1路

=1.00＋失效率1路×50

把一定容量Cache相应的失效率代入上式，即可得平均访存时间。例如，1

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

=1.00＋0.133×50＝7.65

128

KB的8路组相联Cache的平均访存时间为：平均访存时间8路＝1.14＋0.006×50＝1.445.3

降低Cache不命中率Cache容量（KB）相联度（路）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.44在各种容量和相联度情况下Cache的平均访存时间采用相联度超过8的方法实际意义不大。2:1Cache经验规则：容量为N

的直接映象Cache失效率≈容量为N/2的两路组相联Cache失效率。提高相联度是以增加命中时间为代价：

TTL或ECL板级Cache，两路组相联：增加10％CMOSCache,两路组相联：增加2％四.增加Cache容量Cache的容量是影响命中率的主要因素，在地址映象方式确定后，Cache的容量越大，命中率也就越高。根据模拟测试的结果，在一般情况下，命中率H和Cache容量S的关系可近似地表示为:

当Cache容量比较小时，随着Cache容量的增加，命中率提高得非常快；但命中率达到一定值后，随着Cache容量的增加，命中率提高的速度渐渐放慢了；当Cache的容量增加到无穷大时，命中率达到100%，但这没有实际意义。5.3

降低Cache不命中率5.4减少Cache不命中开销一、采用两级Cache应把Cache做得更快？还是更大？答案：二者兼顾，再增加一级Cache第一级Cache(L1)足够小而快第二级Cache(L2)容量足够大性能分析

平均访存时间＝命中时间L1＋不命中率L1×不命中开销L1不命中开销L1＝命中时间L2＋不命中率L2×不命中开销L2平均访存时间＝命中时间L1＋不命中率L1×（命中时间L2＋不命中率L2×不命中开销L2）

（L2平均访存时间）局部不命中率与全局不命中率局部不命中率＝该级Cache的不命中次数/到达该级Cache的访问次数例如：上述式子中的不命中率L2全局不命中率＝该级Cache的不命中次数/CPU发出的访存的总次数第二级Cache的全局不命中率为：

全局不命中率L2＝不命中率L1×不命中率L2

评价第二级Cache时，应使用全局不命中率这个指标。它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。5.4减少Cache不命中开销

例.假设在1000次访存中，第一级Cache不命中40次，第二级Cache不命中20次。试问：在这种情况下，该Cache系统的局部不命中率和全局不命中率各是多少？解:

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

平均访存时间＝命中时间L1＋不命中率L1×不命中开销L1

不命中开销L1

＝命中时间L2＋不命中率L2×不命中开销L2考虑第二级Cache的参数（可用前面的方法减少第二级cache的失效率）例如：容量第二级Cache的容量一般比第一级的大许多。如512KB，1024KB相联度第二级Cache可采用较高的相联度或伪相联方法。（L2平均访存时间）5.4减少Cache不命中开销

例：给出有关第二级Cache的以下数据：（1）2路组相联使命中时间增加10%×CPU时钟周期（2）对于直接映象，命中时间L2

＝10个时钟周期（3）对于直接映象，局部失效率L2

＝25%

（4）对于2路组相联，局部失效率L2＝20%

（5）失效开销L2

＝

50个时钟周期试问第二级Cache的相联度对失效开销的影响如何？5.4减少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路组相联优于直接映象。5.4减少Cache不命中开销二、请求字处理技术请求字从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。应尽早把请求字发送给CPU尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。5.4减少Cache不命中开销

平均访存时间＝命中时间＋不命中率×不命中开销

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器时钟频率的提高。

一.容量小、结构简单的Cache

小容量Cache有利于减少命中时间。应使Cache足够小，以便可以与CPU一起放在同一块芯片上。硬件越简单，速度就越快。5.5减少命中时间二、虚拟Cache1.将Cache、主存储器、磁盘存储器组织成“Cache-主存”和“主存-磁盘”两个独立的存储系统，又称为：物理地址Cache存储系统。CPU

虚拟地址

物理地址

MMU数据或指令

高速缓冲Cache

主存储器存储管理部件5.5减少命中时间2.将Cache、主存和磁盘三个存储器组织在一起，构成一个“Cache-主存-磁盘”存储系统。又称为：虚拟地址Cache存储系统。

如Intel公司的i860等处理机采用这种组织方式

主存储器CPU

虚拟地址数据或指令MMUCache物理地址数据或指令

能够接受虚拟地址的访问5.7虚拟存储器一.基本工作原理

1.基本概念虚拟存储器是对物理主存的扩展,由软件来实现。这样，从程序员的角度来看，存储空间扩大了。在虚拟存储结构方式下，程序员编制程序时所使用的地址与主存地址是不同的。通常，把程序使用的地址称为虚拟地址，或称为逻辑地址，这些地址的集合称为虚存空间；实际主存的地址称为实地址，或物理地址。所有实地址的集合称为存储空间，其范围就是整个主存的容量。在采用虚拟存储器的计算机中，程序是与虚存空间相联系的，而执行程序的CPU则是和主存所用的存储空间相联系的。系统为了让CPU执行程序，必须要把虚存空间变换成存储空间，也就是要把程序的逻辑地址变为CPU可以寻址的主存地址。虚拟存储器根据地址映象方式的不同分为段式、页式和段页式虚拟存储器。5.7虚拟存储器2.虚拟存储器的地址构成以页式虚拟存储器为例，在页式虚拟存储器中，把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块（称为页），每一页中包含有固定长度的存储单元。主存储器的页称为实页，虚拟存储器的页称为虚页。5.7虚拟存储器地址构成：（a）主存地址A的组成实页号p页内偏移d

用户号U

虚页号P

页内偏移D磁盘号磁头号磁道号记录号页内偏移D（b）多用户虚拟存储器地址Av的组成（c）磁盘存储器物理地址的组成5.7虚拟存储器3.页式虚拟存储器工作原理UPD内部地址变换虚拟页号→主存实地址pd二.虚拟存储器的地扯映象和地址变换虚拟存储器中有三种地址空间：

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

起始地址

段号

段长0124K2K8K0K12K20K0主程序（0段）004K2K8K1段2段程序空间0K2K12K4K20K8K主存储器程序按逻辑关系分为大小不同的段5.7虚拟存储器段式虚拟存储器地址变换过程

多用户虚地址

用户号U

段号S

段内偏移D

主存实地址段表基地址寄存器堆0N7

段表基地址

段表长度B

段号

起始地址

装入位

段长

访问方式

段表（每个用户或作业）B0123456

若为“0”,表示要访问的段不在主存里,其他项可用来存放该段在磁盘存储器中的起始地址等信息。5.7虚拟存储器段式虚拟存储器优点：⑴适宜于编制相对独立的模块化程序。⑵便于实现程序和数据的共享。⑶程序的动态链接和调度比较容易。⑷便于实现信息保护。段式虚拟存储器缺点：⑴调入调出时容易产生碎片，使主存储器空间利用不充分。⑵对磁盘存储器的管理比较困难。⑶地址变换所花费的开销比较大。5.7虚拟存储器2.页式虚拟存储器页式虚拟存储器把虚拟地址空间等分成大小相同的块，每块称为一页，相应地，也把主存储器的地址空间等分成和页大小相同的块（页）。5.7虚拟存储器页式虚拟存储器地址变换过程

装入位

修改位

主存页号

各种标志

页内偏移d

实页号p主存实地址p

用户号U

虚页号P

页内偏移D

虚地址

多用户PaPa1页表基址寄存器页表5.7虚拟存储器

与段式虚拟存储器相比，页式虚拟存储器的主要优缺点：优点：

⑴主存储器的利用率比较高。⑵与段表相比，页表相对比较简单。⑶地址映象和变换的速度比较快。⑷因为页的大小为磁盘存储器物理块大小的整数倍，对磁盘存储器的管理和操作比较容易。缺点：

⑴程序的模块化性能不好。⑵页表太大，要占用很大的存储空间。5.7虚拟存储器3.段页式虚拟存储器基本思想是：对用户用来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的实地址空间采用分页的方法管理。在段页式虚拟存储器中，主存储器按固定大小分成页，称为实页；用户仍然按照逻辑的段来编写程序，但每一个段又被分成若干个固定大小的页，页的大小和主存储器的页是一样的。5.7虚拟存储器段页式虚拟存储器地址映象关系主存储器页表长度页表首址23段表0段（8KB）1段（11KB）用户程序0段0页0段1页0段页表1段0页1段1页1段2页1段页表每页4K