Cache知识点

Cache结构
目前，计算机系统中常用的三级存储体系是Cache、主存、辅存。存储体系结构包括不同层次上的存储器，通过适当的硬件、软件有机地组合在一起形成计算机的存储体系结构。现在大多数人都将高性能计算机的存储体系结构描述成如下图所示的三层存储器层次结构。
三级存储结构包括高速缓存(Cache）、主存储器（MM）和辅助存储器（外存储器）。也有人将存储器层次分为4层，是将CPU内部的寄存器也看做是存储器的一个层次。

Cache计算方式
（1）随机算法。这是最简单的替换算法。随机法完全不管cache块过去、现在及将来的使用情况，简单地根据一个随机数，选择一块替换掉。
（2）先进先出（First In and First Out，FIFO）算法。按调入cache的先后决定淘汰的顺序，即在需要更新时，将最先进入cache的块作为被替换的块。这种方法要求为每块做一记录，记下它们进入cache的先后次序。这种方法容易实现，而且系统开销小。其缺点是可能会把一些需要经常使用的程序块（如循环程序）替换掉。
（3）近期最少使用（Least Recently Used，LRU）算法。LRU算法是把CPU近期最少使用的块作为被替换的块。这种替换方法需要随时记录cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需要对每一块设置一个称为“年龄计数器”的硬件或软件计数器，用以记录其被使用的情况。
（4）最不经常使用页置换（Least Frequently Used (LFU)）算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。LFU的复杂度以及计数器规模都比LRU大，LRU只关注近期访问情况，而LFU会统计累计访问次数作为淘汰的依据。

Cache与内存映射关系
高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多，接近于CPU的速度。 Cache的功能是用来存放那些近期需要运行的指令与数据。Cache与内存之间的映射有三种不同的方式：全相联方式、直接相联方式、组相联方式。
1、全相联方式
地址映象规则：主存的任意一块可以映象到Cache中的任意一块。
（1）主存与缓存分成相同大小的数据块。
（2）主存的某一数据块可以装入缓存的任意一块空间中。
2、直接相联方式
地址映象规则： 主存储器中一块只能映象到Cache的一个特定的块中。
（1）主存与缓存分成相同大小的数据块。
（2）主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数与缓存的总块数相等。
（3）主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。
3、组相联映象方式
（1）主存和Cache按同样大小划分成块。
（2）主存和Cache按同样大小划分成组。
（3）主存容量是缓存容量的整数倍，将主存空间按缓冲区的大小分成区，主存中每一区的组数与缓存的组数相同。
（4）当主存的数据调入缓存时，主存与缓存的组号应相等，也就是各区中的某一块只能存入缓存的同组号的空间内，但组内各块地址之间则可以任意存放，即从主存的组到Cache的组之间采用直接映象方式；在两个对应的组内部采用全相联映象方式。
这三种方式中，直接相联的实现最为简单，但由于直接相联中，内存块调入Cache时，只能进入特定块，这使得块冲突的可能性变得比较大。相比之下全相联中，内存块调入Cache并无限制，只要Cache中有空闲区，都能调入，所以块冲突可能性最小。组相联是全相联与直接相联的折中，所以排在中间。