cache 浅析

1. Cache
Cache一词来源于法语，其原意是“藏匿处，隐秘的地方”，而自从被应用于计算机科学之后，就已经成为了英语中的一个计算机体系结构专有名词。
Sun Microsystems的前首席科学家Billy Joy，作为BSD unix，csh，vi，NFS，java，TCP/IP等的发明者，他曾经说过，在计算机科学领域，如果没有了cache的发明，其他的一切发明都将失去意义。而正是他，将给予分页的虚拟内存系统引入了Unix，影响了之后所有的新操作系统开发。
Cache的出现是为了解决CPU日益增长的核心时钟频率以及系统主内存日益落后的素质之间的矛盾。
Cache的基本原理是局部性原理，局部性原理简单说起来就是在前一段时间经常用到的代码，在将来会被再次使用的几率也很高。
我们可以想象倒水这件事，有些水桶只有一个小小的进水口，可是这样会给倒水的人造成烦恼，拿着瓢往里倒水的时候要很仔细地对准，并且还要让水流不太急以避免超出进水口的接受能力。小心地倒完一瓢再去舀一瓢，周而复始。
于是有人说，要解决这个问题！就有聪明人发明了漏斗，上面的口很大，并且能够容纳一部分液体，下面的口较小保证流出的水不超出水桶口的范围。这样就可以舀一瓢水，“哗”地倒进漏斗里，歇会儿等水流差不多了再舀一瓢倒进去，这样即简化了对倒水人的技能要求（要不就得跟卖油翁一样），又提高了效率，可以让操作者节省出来时间去做其他的事情。
Cache对CPU的意义是类似的，主存就是那个带有瓶颈的水桶，如果cpu始终要等待对内存的操作完成然后再进行下一个环节，那么在所有跟内存操作相关的指令执行时，CPU就自动降为接近内存的速度。也许你会认为很多指令是寄存器指令，内存读写在整个程序中所占的比例并不大，但是请不要忘记很恐怖的一点是，所有的指令都在内存中，也就是说每执行一条指令都要去读内存。有了这个前提，我们可以想象，在程序执行的时候，cpu会随时随刻地从内存中读取代码，整条总线会被cpu占住，这样的话总线上的其他master（比如说DMA控制器，I2C-Slave等）就将全部受到影响，由此可见没有Cache的结果就将是灾难性的。有些cache还会跟读写fifo紧密配合，不过目的都是一致的，解决内存瓶颈问题。有人可能会有疑问，多数ARM7内核的芯片是没有cache的，为什么依然能够运行得很快，这是因为IC designer在设计总线结构时动了手脚，将CPU取指的总线同其他部分总线隔离，以避免CPU对其他总线设备的干扰。


Cache按写操作模式来分又分为写穿（write through）和写回（write back）两种，由于写穿模式的效率要比写回模式低很多，所以目前绝大多数应用中都是采用的写回模式。


按用途来说，cache分为ICache和DCache，分别作为指令和数据缓存，在某些老的架构中，指令和数据混用一个cache。


Cache的最小操作单位是行（line），也就是说每次cache的操作必须是以32个字节为单位，不能只选择其中某个字节。而且这32个字节数据的首地址必须是32字节对齐的。每一行的大小并不是一定的，在其发展历史中曾经有过很多种选择，目前比较通用的一个选择是每行32个字节，对于32位risc来说就是4个word。


Cache的每一行有tag和index域用来寻址，这个tag和index的功用会在后面详细介绍。


按寻址方式分，cache可以分为全相联映射，直接映射和多路组相联映射cache，所谓的全相联映射指的是任意一行地址中的数据可以放到任意一个cache line中，cpu都可以根据tag和index准确地寻址到。
举个例子来说明这种方式，比如说从地址0x3100 0000到地址0x3100 001F的这32个字节的数据，如果想做到它可以放到任一行中，那么我们就必须得保证针对于任一行数据，都要提供给它唯一的一个标识符，也就是说在32位系统中，由于地址是32位的，行本身是32个字节，表示行内偏移占用了5位，那么必须得提供27位的标识符（针对本例，这个标识符就得是0x188000），才能保证任一行数据可以放置到任一cache行中，并能够被正确寻址。
而全相联cache的问题不仅仅是需要硬件连线比较多，而且它的效率比较低，在极端情况下可能找一个数据需要寻址整个cache。


 
            图一  全相联Cache的结构示意图
直接映射Cache
为了简化cache的设计并提高效率，提出了直接映射的概念，直接映射cache中，对于任一地址，它在cache中有且只有一个line会与之匹配，并且这个line的index是固定的，大大简化了cpu对cache的操作和寻址流程。

还是拿上面那个地址为例，假设cache是4k bytes大小的，每一行还是32 bytes，那么0x3100 0000这个地址就肯定出现在cache的第一行（或者说index为0），0x XXXX X020这个地址出现在cache的第二行（index为1）， 0x XXXX Xfff这个地址就一定出现在cache的第128行（index为127），这样的话对于任一地址，cpu只需到相应的行上去坚持tag是否符合来决定是hit还是miss。
 
            图二    直接映射Cache的结构示意图
      
但是这种直接映射的方式也出现了另外一个问题，我们写一个简单的程序来说明（假设CPU内核对读写内存的策略一样，都要经过cache）：
Int demo_copy(int* dst, int* src, uint length)
{
    int i = 0;
    
    for(i = length; i > 0; i --)
{
*dst = * src;
    dst ++;
    src ++;
}
}
而如果dst和src的差恰好是4k的整数倍（假设cache是4k大小），而这个拷贝的动作实际上是首先将src的数据load进来，然后再store进dst里面去，而他们的在cache中的index是一样的，就导致了cache行的频繁失效，极大降低了系统的效率。有些人可能认为这只是一种特例，但是随着系统越来越庞大，指令和数据发生这种巧合的可能性大大增加，于是必须在设计中考虑对这种情况的处理。


多路组相联cache的出现就是为了应对这种状况，多路组相联的概念就是将多个并行的直接映射cache集成到一起，这样对于一个index就会有多个行与之相对应，比较每行的tag是否与想要的地址相符合，这样就会大大增加命中的几率，避免了一小段程序中频繁cache失效的问题。
 


            图三  组相联直接映射Cache的结构示意图
即使是多路组相联的cache也面临着替换的问题，随着系统运行时间的增加，所有的cache行都会被占满，这时再有新地址的数据请求进来，就要将已有的数据替换出去，而将哪一组的相应行替换出去又成为了一个问题，过去采用的方式有轮转替换，随机替换等，目前较多采用的方式被称为LRU（least recently used），也就是将最近最少使用的行替换掉，这也是对局部性原理的一种应用。


按照工作原理来分，cache又有physical index physical tagged, virtual index virtual tagged, physical index virtual tagged等几种分法，我们来一一了解一下。
Physical index physical tagged是一种最容易理解的操作方式，cache针对物理地址进行操作，简单粗暴，而且不会有歧义。但是这种方式的缺陷也很明显，在多进程操作系统中，每个进程拥有自己独立的地址空间，指令和代码都是以虚拟地址的方式存在，cpu发出的memory access的指令都是以虚拟地址的方式发出，这样的话，对于每一个memory access的操作，都要先等待MMU将虚拟地址翻译为物理地址，这是一种串行的方式，效率较低。


Virtual index virtual tagged是纯粹用虚拟地址来寻址，这种方式带来了更多的问题，每一行数据在原有tag的基础上都要将进程标识加上以区分多个进程之间的相同地址，而在处理共享内存时也比较麻烦，共享内存在不同的进程中的虚拟地址不相同，如何同步是个问题。


现在比较多的是采用virtual index physical tagged的方式，virtual index的含义是当cpu发出一个地址请求之后，低位地址去和cache中的index匹配， physical tagged是指虚拟地址的高位地址去和mmu中的页表匹配以拿到物理地址（index和取物理地址这两个过程是并行的），然后用从mmu中取到的物理地址作为tag（或者tag的一部分）去和cache line的tag位匹配，这样既保证了同一地址在cache中的唯一性（有个例外，cache alias）又能将mmu和cache并行工作，提高了效率。这种方式带来的唯一问题就是cache alias，cache alias主要发生在cache大小同内存页框大小不一致时，比如说每路cache的大小是8k，而现在较为常用的页框大小是4k，这两个数字说明的问题分别是这样的：
页框大小为4k意味着mmu在划分虚拟空间时是以4k为粒度，每一个4k对齐的内存区域作为内存分配的最小单位，于是就有了这样的结果，虚拟地址和物理地址的低12位是相同的，因为低12位地址是作为其在4k页框内的偏移，不管它的虚拟地址是什么，它在4k页面内的偏移是一定的。
Cache大小为8k，意味着cache index是用依据13位地址来运算的，而如果以虚拟地址来寻址cache，低13位中就包含了一位虚拟地址，所以这种方式称为virtual index。问题出现了，一个物理地址当它被不同进程使用时，由于mmu分页机制仅能保证其低12位相同，那么第13位很有可能是不同的，这样就造成了一个物理地址在cache中有两个副本，可能会造成同步问题。
针对于cache alias问题，目前的方案是由操作系统来保证，对于同一物理地址在不同进程空间的虚拟地址，他们的虚拟地址的差一定是cache大小的整数倍，也就是说他们的第13位一定是相同的。同时已经有些cpu厂商在开发监视模块，试图在硬件层面解决类似的同步问题。
图例说明：
龙芯2F 一级指令Cache 采用虚地址索引和物理地址标志的四路组相联结构
 
如图 4-3所示，地址的低14位被用作指令Cache的索引。其中13:5位用于索引512个项。其中每个项中又包含四个64位的双字，使用4:3位在这四个双字中进行选择。 
当对Cache索引时，从Cache中取出四个块中的Data和相应的物理地址Tag，同时，高位地址通过指令TLB(Instruction Translation Look-aside Buffer，简称ITLB)进行转换，将转换后的地址与取出的四个组中的Tags进行比较，若存在一个Tag与其匹配，则使用该组中的数据。这就被称为一次“一级Cache命中(Hit)”。若四组的Tag都不与其匹配，那么中止操作，并开始访问二级Cache。这就被称为“一级Cache失效(miss)”。


写策略
1：命中，又分两种策略
（1）写回法：只写本级cache，暂时不写数据到主存或下一级cache，等到该行被替换出去时，才将数据写回到主存或下一级cache。
（2）写直达：写本级cache，同时写数据到主存或下一级cache，等到该行被替换出去时，就不用写回数据了。
2：失败，又分两种策略
（1）按写分配，又分两种：[1]先写数据到主存或下一级cache，并从主存或下一级cache读取刚才修改过的数据，即：先写数据，再为所写数据分配cache line；[2]先分配cache line给所写数据，即：从主存中读取一行数据到cache，然后直接对cache进行修改，并不把数据到写到主存或下一级cache，一直等到该行被替换出去，才写数据到主存或下一级cache。
（2）写不分配：直接写数据到主存或下一级cache，并且不从主存或下一级cache中读取被改写的数据，即：不分配cache line给被修改的数据。
读策略
1：命中，则从cache中读相应数据到CPU或上一级cache中。
2：失败，则从主存或下一级cache中读取数据，并替换出一行数据，通常采用LRU算法