Cache(高速缓存)技术详解

计算机系统一般都采用多级存储器结构，如寄存器、主存、磁盘、光盘、磁带等。这种多级存储器的特点是从外存储器到CPU中的寄存器逐级向上，存储容量逐级减小，而存取速度逐级提高。由于上下两级存储器的速度可以相差l-2个数量级或者更高，因此，上一级和下一级存储器的数据交换常常成为系统瓶颈，大大降低了系统的性能。为了解决这个问题，通常采用的办法是在两级存储器之间增加一个高速缓冲存储器Cache。

所谓Cache是一个速度等于或者接近上一级存储器访问速度的小容量存储器，其中保存了下级存储器中部分当前所需的数据，因此CPU可以直接从Cache中取得所需的数据，而不必访问下一级存储器。由于Cache的速度与上一级存储器相当，因此保证了系统效率不会降低。Cache的设计依据是程序存取局部性原理，通常程序存取的一批数据总是存放在存储器相邻的单元中，只要把这一批数据同时调入cache中，即可保证近期内需要的数据都能在Caclle中访问成功。为了实现上述目标，在设计Cache时必须做到以下两点：

1．保证访问Cache有较高的命中率；
2．访问Cache与访问下级存储器的方式不变、容量不减。因此对于编程人员来说，Cache是完全透明的，也就是说，他们感觉不到Cache的存在。

由于Cache的容量比下级存储器小l-2个数量级、要做到上述两点，则必须考虑以下问题：

1．如何组织Cache，使得下级存储器的每个部分都能够在需要时调入Cache
2．采用何种替换策略、使得访问cache的命中率最高；
3．采用什么方法使得Cache和下级存储器的数据具有-致性，即修改Cache后保证下级存储器的内容也随之修改(或者相反)。

通过上面的介绍，我们知道Cache也是一种存储器，其工作速度很高，如Ll和L2 Cache就是为了解决PU和DRAM主存之间的速度匹配而设置的。因此主存Cache也可以看作是高速CPU和低速DRAM之间的接口。或者说，把Cache看成一个适配器来解决CPU和DRAM之间的速度匹配问题。

当CPU要从存储器中读取一个数据字时，它首先在Cache中查找。如果找到了，则立即从Cache中读取并送到CPU中；如果在Cache中找不到，则用一个存储器读周期的时间从主存个读出这个数据字送到CPU、并且把包含这个数据字的整个内存数据块都从主存送到Cache中。之所以要把包含被读数据字的整个内存数据块都从主存送到Cache中是因为对存储器的访问具有局部性，也就是说连续读取的数据宇一般在内存中都是连续存放的；调入一个数据块后，将使得以后若干次的访存都可以通过访问Cache来完成。如果调度算法得当，Cache的命中率可以很高。这样，从用户的角度看来，整个存储器(Cache+DRAM)就变成了既有Cache这样高的速度，又有DRAM这样的大容量的存储系统了。这对于解决存储器这个瓶颈是十分有效的。

综上所述，Cache具有以下一些特点：

·Cache虽然也是一类存储器．但是不能由用户直接访问。
·Cache的容量不大，其中存放的只是主存储器中某一部分内容的拷贝，称为存储器映象。
·为了保证CPU访问时有较高的命中率，Cache中的内容应该按一定的算法更换。
·Cache中的内容应该与主存中对应的部分保持一致。也就是说，如果主存守的内容在调入Cache之后发生了改变，那么它在Cache中的拷贝也应该随之改变。反过来，如果CPU修改了Cache中的内容，也应该修改主存中的相应内容。

现代的Cache系统常常采用分级组织的方法，在CPU中集成了一级Cache(L1)，也称为片内Cache；在主板上配置二级Cache(L2)。CPU中的片内Cache虽然容量较小，但是能够以CPU相同的工作频率工作，因此速度极快。一般情况下在L1未命中时，才在L2中查找。从赛扬处理器开始，甚至已经把L2集成到CPU内部了(K6-3处理器也内置了二级缓存，而这时相应的Socket 7主板上的二级缓存就成为"三级"缓存了)。

所谓存储器映像问题就是如何组织Cache．使得下级存储器的每个部分都能够在需要时调入Cache，并且确定调入的内容放在Cache中的什么地方，以便于准确迅速地查找。存储器映像的方法主要有全相联映像法、直接映象法和组相联映象法。

全相联映像法的基本思想是把一个主存块的地址(块号)和块的内容都拷贝到Cache行中；由于块地址也保存在Cache中，因此可以拷贝到Cache中的任意位置。此法的优点是灵活，但是查找比较困难，而且硬件的实现较为困难。

直接映像法的基本思想是一个主存块只能拷贝到Cache中固定的行内。该按硬件成本低，但是由于一个Cache行要对应多个主存块，在使用中当这些主存块需要同时调入Cache时将发生冲突、增加调入调出的开销。

组相联映像法是上述两种方法的折衷方案。其基本思想是把Cache分为m个组，每个组分为n行。主存块分配时对组是固定的、而在组内的位置可以任意。这样就综合了两者的优点，这是目前最常用的方法。

由于Cache的容量总是远小于下一级存储器的容量，因此Cache中只能是下级存储器的部分映像。为了使下级存储器的内容都能在需要时拷贝到Cache中，必须随时替换Cache内容：即把当前不需要的内容调出Cache，腾出空间，调入当前需要的内存块。在这种调入调出方法中，最重要的是替换的策略，即在需要时选择Cache中的哪些行调出，再调入所需的内存块。这种替换策略通常称为调度算法，它是由硬件实现的。如果算法选择不当，将大大增加调入调出的频度。例如把一个当前不需要但是很快就将使用的行调出，必然会降低系统的效率。

常用算法有最不经常使用算法、最近最少使用算法。

最不经常使用算法(LFU算法)的思想是把最近一段时间内被访问次数最少的行调出。因此需要对每一个行设置一个计数器，对该行的访问次数计数、在需要时比较各个计数器的值，淘汰计数次数最少的数据行。这种算法的问题是明显的、那些在程序前期被频繁访问而在后期不再使用的行，可能会在相当长的时间内不被淘沈而那些刚刚调入并将继续反复使用的行则可能因为其计数器中的值较小而频道淘汰。这将严重影响系统的效率。

另一种较常用的算法是最近最少使用算法(LRU算法)。LRU算法的思想是将最近一段时间内最少被访问过的行淘汰出局。因此也需要为每行设置一个计数器、但是计数方法与LFU算法不同。LRU算法是把命中行的计数器清零、其它各行计数器加1。当需要替换时淘汰行计数器计数值最大的数据行出局。

此外还有一些算法，鉴于篇幅不再赘述。

由于Cache中的内容只是主存中相应单元的"拷贝"。因此必须保持这两处的数据绝对一致，否则就会产生错误。造成Cache和相应主存单元数据不一致的原因来自两个方面。一是CPU读人Cache数据作了修改后再写入Cache，而主存中相应单元的内容并未随之变化二是在有多个设备对主存访问的情况下造成的。如多处理器或有DMA的系统，它们直接访问主存储器，修改了其中的内容，而cache中的相应数据却末随之修改。