计算机高速缓冲存储器(Cache)命中率的分析

席红旗

(河南教育学院信息技术系，河南郑州 450046)

计算机高速缓冲存储器(Cache)命中率的分析

席红旗

(河南教育学院信息技术系，河南郑州 450046)

从Cache的容量、空间逻辑组织结构的组大小、块大小、数据的替换算法和写入Cache的数据地址流对Cache命中率的影响进行分析，选择合适的参数可提高Cache的命中率，有效地提高计算机的运算速度.

存储器;Cache命中率;组大小;块大小;替换算法

0 引言

提高计算机的存取速度除了从计算机硬件介质上解决外，更多的是从数据存取方法上不断地提出新的方法.处在计算机多级存储层次的计算机高速缓冲存储器(Computer Cache Memory，以下简称Cache)，直接解决了CPU和主存速度不匹配的问题，Cache的大小、容量的组织方式、访问方法等直接影响了CPU处理数据的速度.

1 计算机存储器体系层的次结构介绍

计算机的存储体系是为了满足人们对计算机存储器“容量大、速度快、价格低”的要求而设计的.存储体系的层次结构如图1所示，其中M1，M2，M3，…，Mn为不同技术实现的存储器.最靠近CPU的M1速度最快，但单位存储容量的价格最高.Mn离CPU最远，这一层的存储器速度最慢，容量最大，单位容量价格最低.存储体系在工作时，以块或者页面为单位进行数据传递.对用户来说，使用计算机时，存储数据的速度接近M1，而存储容量相当于Mn，整体的存储器的价格相对较低，这就满足了最初存储体系设计目的.在当前的计算机存储系统中，通常为三级存储器体系，即高速缓冲存储器(Cache)、主存和外存.

2 高级缓冲存储器的工作原理

高级缓冲存储器是存在于CPU和主存之间的存储体，用于弥补主存速度的不足.从CPU看来，整个存储体系的速度接近Cache，而容量却接近主存.CPU在取数据时，先从Cache中寻找数据，如果要找的数据存在于Cache中，就称为命中，否则称为不命中.命中的次数与总的访问次数的比称为命中率［1］.此时CPU把数据从Cache中取出进行处理.如果没有在Cache中找到需要的数据，就直接到主存中查找，然后对找到的数据进行处理，同时把这些数据回写到Cache中，以备下次使用时直接从Cache中取数据.因为Cache的存取速度比主存的存取速度高得多，所以提高了存储数据的速度.如果CPU从Cache中查找数据的命中次数提高，也就是命中率高，就可大大地提高计算机的存储速度，从而提高计算的性能.

图1 存储器的层次结构Fig.1Hierarchical structure of memory

3 影响Cache命中率的因素分析

Cache命中率的高低主要与Cache中块的大小、组的大小、Cache容量和Cache中数据的替换算法和地址流的簇聚性有关.

3.1 Cache命中率与Cache容量的关系

如果CPU每次需要访问的数据都存在于Cache中，也就是每次访问Cache都命中，那么Cache的容量就要足够大，如果容量达到和存储体系末端存储体的容量一样大，那么CPU每次都能在Cache中找到需要的数据，Cache的命中率是100%.而事实上Cache的容量不可能有这么大，因为它违背了存储体系“容量大、速度快、价格低”的设计中“价格低”的要求，目前市场上的计算机的Cache大小为几十MB.但我们可以看到，Cache容量的大小直接影响到Cache的命中率，命中率的大小与Cache的容量的关系如图2所示，Hc为命中率，s为Cache的容量，它符合关系式

3.2 Cache命中率与Cache中块的大小的关系

为了存取方便，把Cache的存储空间分为若干大小相等的小空间，这些小的空间就称为块.当CPU访问Cache时，查找需要的数据是否存在于块内，如果存在，则命中该块.由于Cache的设计是基于存储器数据的局部性［2］而设计的，如果块的空间过小，存放数据过少，造成部分数据不存在，存储空间的局部性就没有得到很好的利用，命中率就不会很高.这样，当块达到一定大小的时候，块内存储的数据能满足CPU的需求，命中率就会提高，当块的大小继续扩大时，Cache内包括的总块数就会减少，这也降低了CPU对Cache块的命中率，所以存在一个平衡点，在该平衡点附近，Cache的命中率最高，命中率和块的大小关系如图3所示.

3.3 Cache命中率与Cache中组数的关系

Cache中的组是指把Cache中的连续的块组合在一起，形成一个新的逻辑存储空间，这些空间就是称为Cache的组.在Cache和主存映射关系中，组与组的映射关系是一种很重要的映射关系，也是存储体系实现“容量大、速度快、价格低”的方法.在组相连映射方式中，如果Cache的组数过多，就像块分得越多一样，组的空间就会越小，直接映像的成分增加，映射到Cache中的块数减少，命中率下降;反之，命中率增加［3］.

3.4 Cache命中率与替换算法的关系

由于Cache的容量是有限的，主存中的内容不可能全部映射到Cache中，为了利用存储器数据的局部性，采用一种方法把某时间段内常用的数据存放到Cache中，替换掉原来的数据，这就是Cache数据的替换算法，常见的替换算法有随机法(Random，RAND)、先进先出(First-In-First-Out，FIFO)算法、最近最少使用(Least Recently Used，LRU)算法［1，4］.随机法没有固定规律可循，随机替换掉Cache中的数据，高的命中率很难保证;先进先出算法不能突出存储器数据的局部性，即使使用频率不高的数据也会被新调用的数据替换掉，命中率也不会高;最近最少使用算法最能突出存储器数据的局部性，在某一时段内，用新的数据把使用次数最少的数据替换掉，这样Cache中存储的数据总是最近使用频率最高的数据，CPU在调用数据时在Cache中找到的几率也会高，也就是命中率较高.

3.5 Cache命中率与地址流的关系

地址流是指写入Cache中的数据地址的集合.在写入Cache的过程中，如果地址流具有局部性，即有些数据反复写入Cache，特别是在LRU替换方法下，具有较高局部性的地址流能够有效提高Cache的命中率.如果地址流的数量过小，也就是Cache的块容量过大的情况下，就不能很好地体现出地址流的局部性，此时Cache的命中率就会降低.所以地址流对Cache命中率的影响是在Cache的替换方法和块大小确定的情况下才能够衡量.

通过以上分析，Cache命中率和Cache容量的大小、组的大小、块的大小、替换算法和地址流的簇聚性都有关系.只有选择合适的参数，才能提高Cache的命中率，有效地提高计算机的运算速度.

4 小结

Cache命中率的高低直接影响到计算机处理数据的速度，不仅用逻辑方法从数据的处理上提高Cache的命中率，比如数据的替换方法等，还可以从物理上改进Cache存储器的存取速度，比如Cache的材质、存取电路的改进等，从而进一步提高计算机的性能.

［1］陈建铎.计算机系统结构教程［M］.北京:电子工业出版社，2006.

［2］陆鑫达，翁楚良.计算机系统结构［M］.2版.北京:高等教育出版社，2008.

［3］李学干.计算机系统结构［M］.西安:西安交通大学出版社，2006.

［4］NULL L，LOBUR J.计算机组成与体系结构［M］.黄河，译.北京:机械工业出版社，2006.

Analysis on Hit Rate of Computer Cache Memory(Cache)

XI Hong-qi

(Department of Information Technology，Henan Institute of Education，Zhengzhou 450046，China)

The factors affecting the hit ratio of Cache，which include the capacity of Cache，the group size，block size of logic of space structure，data replacement algorithm and address stream of writing data to Cache，were analyzed.The proper parameter was selected to raise the hit ratio of Cache，and the computer operation speed can be raised.

memory;hit ratio of Cache;group size;block size;replacement algorithm

O172.2

A

1007－0834(2012)03－0031－02

10.3969/j.issn.1007－0834.2012.03.010

2011－11－24

席红旗(1975—)，男，河南叶县人，河南教育学院信息技术系讲师.