CPU设计之Cache -- 目录式一致性协议
文摘
科技
2023-12-30 14:00
北京
缓存一致性协议消息传播有两种方式：广播/监听式和目录式（Directory-based）。前文分析过广播式，接下来看看目录式。基于广播式协议，发起请求的缓存控制器将请求广播给总线；其它的缓存控制器监听到请求后，根据其缓存块的状态发出响应。这种广播/监听机制会占用大量的互连总线带宽，对于核心数很多的处理器来说，互连总线会被一致性消息占满，从而影响芯片性能。如果能够通过检索目录的方式，找出保存该缓存块副本的缓存控制器，将一致性消息仅发给这些缓存控制器，而不是发送给全部的缓存控制器，那就有可能大大降低互连总线带宽的占用率。开始之前，我们先来构建一个示例。下图中展示有4个处理器核心，假设当前是0xA地址的数据块在core2和core3中有副本，均为share状态。目录中记录了0xA块的缓存状态为SH，以及core2和core3拥有副本。![]()
- core0中的缓存控制器向目录发起了ExclusiveReq请求；
- 目录控制器检索到core2和core3拥有副本，想core2和core3发起InvalidateReq请求；
- Core2和core3响应目录发出的请求，无效掉自己保存的副本，并返回InvalidateResp给目录；
- 目录收到core2和core3的响应，从主存中读取0xA地址的数据块；
- 目录返回响应ExclusiveResp给core0，并修改目录中的信息，同时core0也修改其缓存中的信息
![]()
在本例中，第5步从主存中读取数据，以及第6步将数据发送给core0仅是为了展示一个完整的过程，具体的实现取决于协议设计。从上面的例子可以看出，目录必须知道哪些缓存保存了数据块的副本，以及这个数据块在每个缓存中是以何种状态来保存的。首先来看第一个问题，目录要想知道哪些缓存保存了数据块并不难，难的是如何存储这些信息，也就是存储代价及目录存储空间是否不足从而导致信息溢出。最直观的存储格式是为每个核心的缓存保留一个bit，用来指示该数据块是否在该核心的缓存中。这种格式被称为“全位向量（full bit
vector）”。这种格式的缺点是，目录的存储开销太大，尤其是大型系统。假设系统中有1024个处理器核心，目录中为了存储一个数据块的信息就需要1024-bit，比数据块本身可能还大（缓存数据块大小通常为64-byte或128-byte）。为了降低目录存储代价，一个简单的办法是用1-bit来表示一组缓存，而不是一个缓存。如果这一组缓存只要有一个保存数据块副本，就把目录中对应的bit置1；只有当这组缓存全都没有数据块副本的情况下才把对应的bit置0。这种格式被称为“粗粒度位向量（coarse bit vector）”。这种格式的代价是会增加互连网络的流量。还有一种降低目录存储开销的方法是“受限指针（limited pointer）”，顾名思义，目录中保存一定数量的指针，指向共享数据块的缓存。除此之外，还有很多降低目录存储代价的方法，感兴趣的朋友可以去搜一些文章看看。需要说明的是，在设计实现时，可以采用多种的目录格式，比如受限指针和粗粒度位向量相结合，让指针指向一组核心的缓存。对于目录需要知道数据块在缓存中的状态，这个并不难，可以将缓存中的状态复制过来。比如，缓存使用MESI协议，目录也应该保存一个MESI的状态。实际上，当一个缓存中数据块是E状态时，该缓存可以直接修改此数据块，而不必发出消息通知目录。也就是说，目录无法区分缓存中的数据块是E状态还是M状态，因此目录中可以将E和M合并为一个状态EM（后面会具体讲解一致性协议）。目录设计中还有一个比较重要的问题，就是目录的位置。目录可以是集中式的，即系统中只包含一个目录，但这种方式对于大型系统并不友好，因为所有核心的缓存都要与这一个目录通信，目录的可伸缩能力将会降低。一个解决办法是采用分布式目录设计。下图展示了一个采用分布式目录设计的多核处理器，每个核心有自己的L1和L2缓存，所有的L2使用目录协议保持一致性，L3是分布式的且被所有的处理器核心共享。目录也是采用分布式设计，并于L3同时部署。当L2缓存发生缺失（miss），则查询目录，如果该数据块没有被缓存，则去L3中寻找。看到这里，熟悉ARM多核体系的朋友是不是想起了什么？如果L2和L3是包含关系（inclusive），还可以将目录和L3的tag阵列合并，以降低L2缺失的时延和L3的命中/缺失时延。![]()
接下来，我们看看目录式缓存一致性协议的实现细节。简化起见，我们假设缓存使用MSI一致性协议，每一个缓存块的状态包含：1. Modified（M）：缓存块有效，并且其数据与主存中的原始数据不同，这个缓存块是“dirty”的。
2. Shared（S）：缓存块是有效的且有可能被其他处理器共享，这个缓存块是“clean”的。
3. Invalid（I）：缓存块无效。
1. PrRd：处理器请求从缓存块中读出；
2. PrWr：处理器请求像缓存块中写入。
1. ShReq：目录发出的共享请求；
2. ExReq：目录发出的独占请求；
3. WbReq：目录发出的写回请求；
4. InvReq：目录发出的无效请求；
5. DownReq：目录发出的降级请求，用于将缓存从M降级到S；
6. InvResp：核心发出的不带数据的无效响应；
7. InvRespD：核心发出的带数据的无效响应；
8. DownResp：核心发出的不带数据的降级相应；
9. DownRespD：核心发出的带数据的降级响应。
假设使用写分配和写无效缓存一致性策略。写回缓存的MSI一致性策略有限状态机如下图所示。其中蓝色表示缓存控制器从核心侧接收到的请求（斜线前）和向目录侧发出相应的请求（斜线后）；红色表示从目录侧接收到的请求（斜线前）和向目录侧发出的响应（斜线后）；黄色表示Eviction和向目录侧发出的请求。之所以将状态转换分成三部分，是为了更好的解释说明，在设计实现时只有一个状态机。![]()
举例说明，当缓存中的数据块为M状态，此时从核心接收到PrRd或PrWr，都不需要向目录发出任何请求；而如果从目录侧接收到DownReq，则需要返回响应，并将“脏”数据发送给目录（或者是发给其它请求独占的缓存控制器），这里之所以要将数据发出去而不是直接丢弃掉，是因为其它请求独占的缓存控制器可能想修改的是数据块中的不同字节。再来看目录，也应该保存相同的状态。我们将目录中的状态定义为EM，SH和UN，与缓存中的状态加以区分，以免混淆。有限状态机的状态转换如下图所示。![]()
以上的状态仅是为了说明一致性协议，在具体的实现中，还存在很多的瞬时状态（transient states）。其实上面分析的协议过于简单了，在设计实现时，还需要考虑其它的问题，比如缓存之间的竞争处理。限于篇幅，以后有时间再分析，今天就先到这里吧。休息，休息一会儿~~
