ARM920T的Cache(介绍Cache最好的一篇文章)

ARM920T有16K的数据Cache和16K的指令Cache，这两个Cache是基本相同的，数据Cache多了一些写回内存的机制，后面我们以数据Cache为例来介绍Cache的基本原理。我们已经知道，Cache中的存储单位是Cache Line，ARM920T的一个Cache Line是32字节，因此16K的Cache由512条Cache Line组成。要了解Cache的基本原理，我们从如何设计Cache这个问题入手。

设计Cache的一种最朴素的想法是，把VA分成以32字节为单位，从任何一个对齐到32字节地址边界的VA开始连续的32个字节（比如0x00-0x1f，0x20-0x3f，0x40-0x5f等等）都可以缓存到512条Cache Line中的任何一条。那么一条Cache Line中的32个字节怎么知道是来自哪个VA的呢？这就需要把VA也保存在Cache中，由于这32字节的起始地址是对齐到32字节地址边界的，末5位全为0，因此只需要保存VA[31:5]即可，这称为VA Tag[4]，Tag是VA的一部分，是Cache Line中数据的标识，表明这32字节数据来自哪个VA。这样设计的Cache称为全相联Cache（Fully Associative Cache），图示如下：

图 1. 全相联Cache

给定一个VA，如何在Cache中查找对应的数据呢？首先到Cache中比较查找哪一行的Tag等于VA[31:5]，找到对应的Cache Line后，再根据VA[4:0]决定要访问的是该Cache Line缓存的32个字节中的哪一个字节。由于有512条Cache Line，如果这个VA没有缓存在Cache中则需要比较512次才知道，这是最坏的情况，也是最常见的情况，下面我们要改进Cache的设计来解决这个问题。

全相联Cache的特点是任何VA都可以缓存到任何一条Cache Line，给定一个VA做查找时，由于它有可能缓存在512条Cache Line中的任何一条，就只好全部都找一遍了。如果限定某一个VA只允许缓存在某一条Cache Line中，那么查找的过程就快多了：检查一下应该缓存这个VA的那条Cache Line，看Tag一致不一致，如果一致就是Cache Hit，如果不一致就是Cache Miss，可以直接访问物理内存而不必再找其它Cache Line了。这种设计称为直接映射Cache（Direct Mapped Cache），如下图所示：

图 2. 直接映射Cache

地址0~31应该缓存在第1条Cache Line中，地址32~63应该缓存在第2条Cache Line中，依此类推，地址16352~16383应该缓存在第512条Cache Line中，下一个地址应该是16384（16K）了，我们又回到开头，地址16K~16K+31应该缓存在第1条Cache Line中，地址16K+32~16K+63应该缓存在第2条Cache Line中，依此类推，再次回到开头的地址应该是32K，32K~32K+31应该缓存在第1条Cache Line中，32K+32~32K+63应该缓存在第2条Cache Line中，依此类推。读者应该可以总结出规律了：给定一个VA，将它除以16K得的余数决定了它应该缓存在哪一条Cache Line中，那么除以16K的商数部分就应该是VA Tag，用以区别Cache Line中缓存的到底是0还是16K还是32K地址上的数据。那么除以16K的商数和余数怎么表示呢？VA[31:14]就是除以16K的商数，VA[13:0]就是余数，所以上图的Tag处标着VA[31:14]。余数VA[13:0]是16K Cache里的一个字节偏移量，而Cache是按32字节一个Cache Line组织的，所以余数中的高位VA[13:5]决定了是第几条Cache Line，余数中的低位VA[4:0]决定了Cache Line内的字节偏移量。验算一下，VA[13:5]一共是9位，作为Cache Line的编号可以表示的Cache Line数目正是512条。

直接映射Cache虽然查找速度很快，但也有缺点。比如，地址0~31、16K~16K+31、32K~32K+31都应该缓存到第1条Cache Line中，假如我们程序第一次访问地址30，地址0~31的数据就从内存加载到第1条Cache Line，以便下次访问能更快一些，但是我们程序第二次访问的却是地址32770，地址32K~32K+31的数据就要从内存加载到第1条Cache Line，把Cache Line里原来存的地址0~31的数据替换掉，以便下次访问能更快一些，但是我们程序第三次访问的却是地址16392……这样下去，Cache起不到任何加速作用，形同虚设，这种问题称为Cache抖动（Cache Thrash）。全相联Cache就不会有这种问题，因为任何VA都可以缓存到任何一条Cache Line，可以把先后几次访问的VA缓存到不同的Cache Line，就不会相互冲突。

全相联Cache和直接映射Cache各有优缺点，全相联Cache查找很慢，但没有抖动问题，直接映射Cache则正相反。为了得到更好的性能，实际CPU的Cache设计是取两者的折衷，把所有Cache Line分成若干个组，每一组有n条Cache Line，称为n路组相联Cache（n-way Set Associative Cache）。ARM920T采用64路组相联Cache，如下图所示：

图 3. 64路组相联Cache

有了前面两种Cache概念的基础