内存

要想理解cache，先理解内存。内存的简单表示如下图，内存里面的内容的查找是根据地址来进行的，也就是说内存包含两点①地址②内存的内容（存的数据），根据地址来找数据。

上图的0000~0008是地址，A~I是存的数据，cpu根据地址去寻找数据。图中的一个字母代表一个字节的数据。

CACHE 

cache和数据的三种映射关系

cache中的数据就是物理内存中的数据的子集，那么对于物理内存的一个数据，根据cache中可以放置这个数据位置的多少，可以分为三种：

1. 这个数据只能放在cache的某一个位置，称为直接映射的cache
2. 这个数据可以放在cache任一位置，称为全相连的cache
3. 这个数据可以放在cache某几个位置，称为组相连的cache

cache 结构

cache的结构其实和内存的结构类似，也包含地址和内容，只是cache的内容除了存的数据（data）之外，还包含存的数据的物理内存地址信息（tag），因为CPU发出的寻址信息都是针对物理内存发出的，所以cache中除了要保存数据信息之外，还要保存数据对应的地址，这样才能在cache中根据物理内存的地址信息查找物理内存中对应的数据。（当然为了加快寻找速度，cache中一般还包含一个有效位（valid），用来标记这个cache line是否保存着有效的数据）。一个tag和它对应的数据组成的一行称为一个cache line。如下图所示，下表中的一行就是一个cache line。

一个物理内存地址只存储一个字节数据，但是一个cache line可以存储多个字节数据，

 物理内存地址被分为tag、index 和 block offset。

举例来讲，对于一段物理内存（block），该物理内存上每个字节的地址划分为以下几段：

block offset占2bit，所以一个cache line存储4字节数据

直接映射(Direct Mapping)

物理内存中的数据到cache的映射关系如下图所示，block offset占4bit

 物理内存的每个数据只能映射到某个cache line。

上图的映射原则就是：根据物理地址的中间三位（index字段）来定位当前数据应该在cache的哪一行，把物理地址的tag字段和该地址对应的内容放入对应的cache line的tag字段和data字段，并把相应的valid位置1。那么在之后进行cache寻找的时候就可以根据cache line的tag字段来辨认当前line中的数据是哪个数据block的。

缺点：Cache Miss率极高？

全相连映射(Fully Associative Mapping)

全映射就是所有cache line可以对应所有地址，即物理内存数据可以存在任一cache line，index所占bit数为0。这样Cache就不会造成冷热不均，Cache Miss减小了很多，但与此同时带来了另外的问题，那就是查找Cache命中与否的代价(Over head)很高。不能通过index分组，只根据要寻址的地址的tag来逐一与cache中的tag字段比较，如果有与之匹配的cache line，也就是cache hit了，如果遍历整个cache，也没有找到匹配的cache line，那就是cache miss了。

n 路组相联映射(n-ways Set-Associative mapping)

组相联映射实际上是直接映射和全相联映射的折中方案，主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同，组间采用直接映射，组内采用全相联映射。

主存块存放到哪个组是固定的，至于存到该组哪一块则是灵活的。

n way 中的 n 常用的有 2、4、8、16，这里的含义就是，每组（set）含有几个 Cache line，比如，8KB 大小的 Cache，一个 Cache Line 为 16 Bytes，4-way set 相关的情况下，那么一个 Set=4*16=64 Bytes，整个 Cache 被分为了 8KB/64Bytes=128组（Set）：

可以看出和直接映射很像，不同点在于一个在一组中，第一个没找到，可以找下一个，直到该组的最后一个。这样，可以结合两者的优点。

现实的选择

n-ways Set-Associative，这个n=1，就是直接映射；n=cache大小，就是全相关映射。我们从上面知道两者都不好，而n最好取中间某个值。那么n到底该选几呢？这比较复杂，和Cache的速度和大小、内存的速度、主频等等很多都相关，在很多情况下都是个经验值，也是大量pre-silicon实验的结果。

带 Cache 的 CPU 内存读写

在CPU与主存之间增加了Cache之后，便存在数据在CPU和Cache及主存之间如何存取的问题。读写各有2种方式。

1. 贯穿读出式(Look Through)

该方式将Cache隔在CPU与主存之间，CPU对主存的所有数据请求都首先送到Cache，由Cache自行在自身查找。如果命中，则切断CPU对主存的请求，并将数据送出；不命中，则将数据请求传给主存。

该方法的优点是降低了CPU对主存的请求次数，缺点是延迟了CPU对主存的访问时间。

2. 旁路读出式(Look Aside)

在这种方式中，CPU发出数据请求时，并不是单通道地穿过Cache，而是向Cache和主存同时发出请求。由于Cache速度更快，如果命中，则 Cache在将数据回送给CPU的同时，还来得及中断CPU对主存的请求；不命中，则Cache不做任何动作，由CPU直接访问主存。

它的优点是没有时间延迟，缺点是每次CPU对主存的访问都存在，这样，就占用了一部分总线时间。

3. 写穿式(Write Through)

任一从CPU发出的写信号送到Cache的同时，也写入主存，以保证主存的数据能同步地更新。

它的优点是操作简单，但由于主存的慢速，降低了系统的写速度并占用了总线的时间。

4. 回写式(Copy Back)

为了克服贯穿式中每次数据写入时都要访问主存，从而导致系统写速度降低并占用总线时间的弊病，尽量减少对主存的访问次数，又有了回写式。

它是这样工作的：数据一般只写到Cache，这样有可能出现Cache中的数据得到更新而主存中的数据不变(数据陈旧)的情况。但此时可在Cache 中设一标志地址及数据陈旧的信息，只有当Cache中的数据被再次更改时，才将原更新的数据写入主存相应的单元中，然后再接受再次更新的数据。这样保证了 Cache和主存中的数据不致产生冲突。

ARM cache 策略

Cache的写策略分为直写策略和回写策略。同时向cache行和相应的主存位置写数据，同时更新这两个地方的数据的方法称为直写策略 （writethrough），把数据写入cache行，不写入主存的或者只有当cache被替换时或清理cache行时才写入主存的策略称为回写策略 （writeback）。采用回写策略时，当处理器cache命中，只向cache存储器写数据，不写入主存，主存里的数据就和cache里不一 致，cache里的数据是最新的，主存里的数据是早前的。这就用cache存储器信息状态标志位了，当向cache存储器里某行写数据时，置相应行的信息 标志脏位为1，那么主控制器下次访问cache存储器就知道cache里有主存没有的数据了，把数据写回到主存中去。

当一个cache访问失效时，cache控制器必须从当前有效行中取出一个cache行存储从主存中取到的信息，被选中替换的cache行称为丢弃者，如 果这个cache行中脏位为1则应把该cache行中的数据回写到主存中，而替换策略决定了那个cache行会被替换，在arm926ejs中ARM支持 两种策略：轮转策略和伪随机策略。轮转策略就是取当前cache行的下一行，伪随机策略是控制器随机产生一个值。

当cache失效时，ARM采取两种方式分配cache行，一种是读操作（read-allocate）还有一种是读-写分配策略（read- write-allocate），当cache未命中时对于读操作策略，在对cache存储器读操作时才会分配cache行