CPU设计之Cache-一致性初探

夫人惟气之盛者,能舍人之所不能舍,而为人之所不能为。

-- 李鸿章

什么是缓存一致性（cache coherency）

我们知道cache只是一块缓存，暂时备份数据以加速CPU运行。既然是临时的存储空间，那么就涉及到了一致性问题。通常涉及两个方面，一个是空间上，需要缓存一致性协议来保证；另一个是时间上，需要同步机制。今天先说一致性协议。

Cache一致性一般涉及几个方面，首先是cache与内存之间的一致性。如果有其他的模块更改了内存中的数据，那么cache中缓存的数据就与内存中的不一致了。比如DMA进行数据搬移时，那么后续CPU读取该内存数据时候，若cache命中，则可能读取到的数据不是DMA搬移后的数据。所以在进行DMA搬移之前，先进行cache Invalidate操作，这样CPU下次读取这条cache line里的数据的时候，才能知道这些数据不是最新的，需要从内存更新。保证后续CPU读取到的数据是DMA真正搬移的数据。如下图，红色代表数据块被更新过。

图1 内存数据比cache新

对于采用write-back策略的cache，当CPU更改了某条cache line中的数据，则该cache line中的数据比对应内存中的数据新，此时需要将这条cache line标记为modified。一般只有在该cache line被替换时才会把新数据更新到内存。但在某些时候，CPU可能需要清除cache，这时候需要执行flush操作，把cache的新数据写回到内存。

图2 cache数据比内存新

上面提到的cache与内存之间的一致性问题不管是单核还是多核系统都会存在，相对简单。而比较麻烦的是多核系统中的cache之间的一致性问题。我们常说的cache一致性协议通常就是解决多核处理器设计中的一致性问题。

通常在多核处理器系统中，每个处理器核有自己独享的cache，只有LLC是所有处理器核共享。如果多个处理器核同时在自己的私有cache缓存了同一段内存的数据，这时候某一个处理器核修改了其中的数据，那么就与其它核心的cache数据不一致了。其它的处理器核需要知道自己cache中的数据已经不是最新的了。

图3 多核cache一致性问题示意图

缓存一致性协议的具体作用就是把某个处理器核新写的数据传播给其他处理器核，以确保所有处理器核看到一致的共享存储内容。缓存一致性协议需要解决两个问题，一是如何传播新值，二是传播给谁。从如何传播的角度看，缓存一致性协议可以分为写无效（Write Invalidate）协议和写更新（Write Update）协议。写无效协议就是当一个处理器核要把对某一单元新写的值传播给其它处理器核时，使其它处理器核中该单元的备份无效，这样当其它处理器核使用该备份时需要重新获得新值。写更新协议就是当一个处理器核要把对某一单元新写的值传播给其它处理器核时，把拥有该备份的其它处理器核中的数据直接更新为新值。写无效的优点是，一旦某处理器核使某一变量在所有拥有该备份的缓存中无效后，它就取得了对此变量的独占权，随后对此变量的更新不必再通知其它处理器核，直到其它处理器核请求访问此变量而导致独占权被取消；缺点是，当某变量在一个处理器核中的备份无效后，此处理器核再访问该变量会引起cache miss，当一个共享块被多个处理器核频繁访问时会导致“乒乓”效应，导致性能严重下降。写更新的优点是，一旦某cache缓存了某一个共享变量，它就会一直拥有此变量的最新备份；缺点是，当某一共享变量被更新时，所有拥有该变量的处理器核的备份都会被更新，哪怕这些处理器已经不需要这个变量了。写无效协议适用于顺序共享（Sequential Sharing）的程序；写更新协议适用于紧密共享（Tight Sharing）的程序。

从传播给谁的角度看，在缓存一致性协议中，一致性消息可以被发送到所有缓存，也可以被发送到特定缓存。根据这种区别可以把一致性协议分为广播/侦听式和基于目录式。总的说来，协议设计的越复杂，消耗的带宽越低，实现起来也越困难。

在多核SoC设计中，所有处理器核与内存之间是通过总线连接的。基于RISC的处理器读写内存都是通过load/store指令来完成的，不管是load还是store都需要经过总线的传输，总线的一次传输被称为传输事务（transcation）。

广播/侦听式的原理就是当一个处理器核修改了cache line之后，将广播通知到总线上其他所有的核心，而所有核心需要一个硬件单元来负责侦听总线上的事务广播。但是要时刻监听总线上的一切活动没有必要，所有处理器核之间共享的内存数据毕竟只占少数，大部分监听可以说是无用的，所以又引入了一个用于侦听过滤器（snoop filter）。过滤的标准就是看自家的核心有没有缓存这个传输事务涉及到的内存位置，或者说有没有对应的cache line。

总线方式天然的支持广播式协议，而基于总线的缓存一致性协议是所有广播/侦听式协议中较为容易实现的，因为总线为所有的一致性事务提供了串行化点（Point of Serialization）。举个例子，假设有四个CPU核心P0-3。它们从内存中读了一个共享数据到各自的cache中，然后P0修改了这个数据，随后P1也修改了同样的数据，接下来对于P2和P3来说看到的应该是P0修改后的数据还是P1修改后的数据呢？如果P2看到是P0，而P3看到的是P1，那就产生了不一致。这时必须要保证各个处理器核对内存同一位置的store和load的操作是序列化的（sequenced），也就是store和load的顺序应该和线程执行的顺序一致。广播/侦听方式会占用比较大的总线带宽，尤其是处理器核心数目很多的时候。

基于目录式的原理是点对点的方式进行传播，每个总线事务只会发给相关的核心。所谓相关，就是拥有这个事务所涉及内存位置对应的cache line。那怎么知道哪些核心是相关的呢？基于目录的主要思想是，为每一个cache line维护一个目录项，该目录项记录所有当前持有此备份的处理器核心号以及此行是否被改写等信息。当一个处理器核写某一个cache line且可能引起数据不一致时，它就根据目录内容只向持有此备份的那些核心发出写使无效/写更新信号，从而避免了广播。典型的目录组织方式是位向量目录。位向量目录中的每一个目录项都有一个N位的向量，N是系统中的处理器核心数。位向量中的第i位为1表示第i个处理器核心持有该备份。每一目录项还有一个改写位表示某核心独占并改写此行。相比广播/侦听，目录式占用较少的总线带宽。但是目录式的缺点很明显，如果处理器核心多且共享存储容量大的时候，目录的存储开销非常大。另外，每次传输事务都要查询目录表项，也就造成了一些延迟。

今天就到这里吧，下周继续~~