浅析访问局部性原理在cache存储系统中的作

《浅析访问局部性原理在cache存储系统中的作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2005年1月第29卷第1期安徽大学学报(自然科学版)JournalofAnhuiUniversityNaturalScienceEditionJanuary2005Vol.29No.1浅析访问局部性原理在Cache存储系统中的作用王恒娜(安徽财经大学计算机系,安徽蚌埠233041)摘要:简单介绍了Cache存储系统的工作原理以及它在提高系统性能方面的作用;由此引出了Cache存储系统设计的理论基础访问局部性原理,并进一步讨论了访问局部性的强弱对Cache存储系统中的命中率以及存取有效性的影响。关键词:Cac

2、he存储系统;访问局部性原理;命中率;存取有效性中图分类号:TP311文献标识码:A文章编号:1000-2162(2005)01-0027-04所谓Cache,即高速缓冲存储器,是位于CPU和主存储器DRAM(动态存储器)之间的容量较小但速度很高的存储器,通常由SRAM构成。SRAM静态存储器,它采用了与制作CPU相同的半导体工艺,因此与DRAM比较,SRAM的存取速度快。鉴于动态RAM组成的主存储器的读写速度低于CPU速度,而CPU每执行一条指令都要访问一次或多次主存,所以CPU总 是要处于等待状态,大大降低了

3、系统的效率。因此,人们采用了Cache存储系统[2]:也就是由一个相对容量较大,但速度较慢的主存与一个容量较小而速度较快的Cache相连而成的一种存储系统。其工作原理概括如下:在Cache中保存着主存储器内容的部分副本,CPU在读写数据时,首先访问Cache。由于Cache的速度与CPU相当,因此CPU就能在零等待状态下迅速地完成数据的的读写。只有Cache中不含有CPU所需的数据时,CPU才去访问内存。CPU在访问Cache时找到所需的数据称为命中,否则称为未命中。因此,访问Cache的命中率则成了提高效率的关键。图1Ca

4、che存储系统工作原理显然,Cache的容量较小,可以存放的数据也较少,势必会影响到Cache的命中率。而我们并不采用更大容量的Cache。它的原因很多,比如:(1)SRAM每个存储单元的结构复杂因此体积较大导致集成度较低,价格偏高;(2)Cache全部由硬件来调度,所以Cache越大,寻址门数越多,由于逻辑门的延迟反而导致大容量的Cache比小容量的Cache速度稍慢;(3)Cache收稿日期:2004-01-11作者简介:王恒娜(1976),女,安徽蚌埠人,安徽财经大学讲师.28安徽大学学报(自然

5、科学版)第29卷命中率达到一定高度以后,大容量的Cache并不能明显提高系统性能等等,这些都是减小Cache容量的原因,而其中最关键的原因是它的理论基础访问局部性原理。1访问局部性原理所谓访问局部性原理[1],就是CPU在短时间内要访问的数据多集中在某几个固定的簇。因此一旦CPU在Cache中命中一次以后,在后续的多次访问中,都会在Cache中命中。那么,从宏观上来看,访问局部性原理的意义可以简单理解为CPU要访问的数据绝大多数都可以在Cache中命中。因而也就使得这种Cache存储系统的速度接近单个Cache的速

6、度。显然,程序的局部性越高,相应的Cache命中率也越高。要得到这个结论,数据的分析如表1-3所示。表1高级语言操作的相对动态额度[3-6]研究者语言循环调用判断赋值转移其他 HuckPascal4120742- KnuthFortran33116797Pascal5152945-6Patterson和SequinC312433831TanenbaumSal4123642-6众所周知,高级语言程序在编译以后才能执行。编译以后一条循环语句对应一条转移语句和一条判断语句(忽略其循环次数,因为循环体中的基本语句仍然是调用、赋值、判

7、断等语句,若考虑循环次数,其他语句也同等增加,所以这基本不影响我们的统计数据);一条调用语句对应两个转移语句。因此,表1可以简化成表2。表2编译后语句频度研究者判断语句赋值语句转移语句其他语句总语句数 Huck24748-106 Knuth14671871063445356120Patterson和Sequin4638301115Tanenbaum4042286116汇总15826611920563下面,用概率与数理统计的方法来揭示以上数据的含义。令:随机变量X表示程序中的不同语句;即:X=1表示判断语句,X=2表示赋值语句

8、;X=3表示转移语句。X=4表示其他语句;从上面的数据表,进一步分析:(1)X的数学期望(即X变化的平均值),界于赋值语句和判断语句之间且非常接近赋值语句;(2)X的方差Dx反映了X取值的密集程度,也就是说:Dx越小,X的取值就越集中在X数学期望的附近。从上表可见程序中大多数