1、引言

近年来，由于工艺和功耗的限制，摩尔定律的延续变得愈发困难[1]，通用微处理器不再追求更高的时钟频率，提高单核处理器的性能变得日渐困难，处理器发展的重心转向片上多核，更多地去开发线程级并行所带来的性能提升。此外，处理器与存储器之间的速度差异导致“内存墙”问题依然存在。在多核环境下，私有缓存与共享末级缓存（LLC）共存产生复杂的访存行为，使得缓存一致性的维护面临更加严峻的挑战。随着核数的不断增加，多核的互连结构也逐步由传统的总线互连向片上网络（NoC）发展[2]。互连结构的变革，使得适用于传统多核总线的侦听一致性协议等不再适应新的NoC环境，亟需进一步改进以及新的一致性协议的发展。

本文针对多核NoC环境下缓存一致性协议的发展进行了综述，论述了多核缓存一致性问题的由来，分析了多核互连结构变化对缓存一致性协议提出的新要求，总结了当前国内外针对传统缓存一致性协议的改进思路以及其他新型缓存一致性解决方案的发展，指出了现有设计各自存在的问题，并给出了进一步研究发展的思路与展望。

2、互连结构的发展对缓存一致性协议的挑战

在多核系统中，不仅拥有与单核相同的垂直的存储层次结构，同时由于每个核私有缓存的存在，各个处理器核对这些私有缓存的写操作可能会导致同一地址在不同私有缓存中展现出不一样的数据，从而导致存储一致性错误。

针对多核的缓存一致性，目前有多种定义，GHARACHORLOO等对其定义[3]如下：

(1）任意缓存行的每一次写操作对所有核可见；

(2）写操作是顺序化的，且所有核观察记录到的对同一地址的写操作是按照相同顺序进行的。

随着多核系统集成密度的不断增加，核间通信对带宽要求也越来越高。片上互连结构的研究是提高多核通信带宽的一个重要方向。当前流行的片内互连方式主要可以分为总线互连和片上网络NoC互连两大类架构[4]。

共享总线由于仲裁排队的通信方式，使得所有节点对缓存的写请求在发送前就自动完成排序，同时易于广播的结构，能够确保每一次写操作即缓存状态的更新都能及时被所有的节点侦听到，因此总线缓存一致性协议的实现相对简单。但随着电路集成度的不断增加，片上多核系统的节点数也在不断增长，使得每次总线占用只能处理一个节点的请求，这种协议方式效率低下，无法适应高并发与大通信量的应用场景。

片上网络与传统总线在通信方式和拓扑结构上都有巨大差异。其模拟计算机系统中的通信网络，采用分组路由的方式通信，在传输数据时，不需要对互连网络申请独占，不同节点随机发出的数据包在节点之间路由传递，分时复用链路资源，最终到达目的节点，完成核间通信，因此其具有高并发性的特点，能较好地满足多核系统对互连网络带宽和吞吐率的要求。

片上网络采用相比总线仲裁独占更为复杂的分组路由的通信方式，虽然提高了网络整体的带宽和吞吐率，但更为复杂的互连结构与通信方式对一致性协议提出了更高的挑战：

(1）不同于总线，片上网络是无序互连，其核间消息的传递是并发的，如何满足NoC环境下写更新操作对所有核可见的顺序一致是保证一致性协议正确性的首要挑战。

(2）片上网络不再采取总线独占的通信方式，使得一致性协议的广播/多播操作变得复杂，高效的实现或者减少广播/多播操作是对NoC环境下一致性协议的性能要求。

(3）相对于总线结构，片上网络更具有扩展性。因此一致性协议的实现需要满足片上网络的可扩展性，不能随着核数的增加有指数型的存储消耗和片上流量资源的占用。

除以上提到的挑战之外，片上网络的一致性协议还需面对与片上网络包转递丢失等导致的更复杂的容错与异常处理等挑战。

3、多核NoC环境下缓存一致性协议的发展

当前NoC环境下缓存一致性协议发展主要呈现三种方向：一是对传统应用于总线的侦听一致性协议进行改进，以使其适应片上网络无序互连、广播难的特点；二是不断优化目录协议，降低其片上资源的消耗，简化其一致性事务流程，提高其缓存一致性消息传递的效率；三是设计不同于传统的MESI状态编码的更适应片上网络拓扑结构的新型协议。

3.1 侦听一致性协议的改进

侦听一致性协议最早是基于总线实现的。请求者通过申请占用总线来进行广播，同时总线仲裁占用也扮演了事务定序的角色，所有的一致性事务都是按顺序串行进行，保证了一致性协议对写操作的顺序性要求。而对于片上网络互连结构，高并行度允许不同节点可以同时发出消息，由于不同核之间路径长度和链路的实时拥塞状况不同，因此不同节点接收到的同一消息到达时间不一致，造成顺序性的要求不满足，导致一致性错误，如图1所示。因此侦听一致性协议应用于片上网络的首要难题便是定序问题。

图1片上网络结构中缓存一致性消息的排序难题

此外，由于缺少缓存共享者信息，一致性事务的发起者通常只能广播消息，对于片上网络结构，消息发起者需要向每个节点发送一份相同消息，而这样会造成片上网络的带宽浪费、网络拥塞，因此如何有效解决广播问题是侦听一致性协议应用于片上网络的又一难题。

3.1.1 解决排序问题

对于环形的片上网络，一种基于固定定序点的方式被提出。所有需要广播的请求消息首先被发送到同一个定序点，然后按固定方向转发出去，因此所有的消息都是有序的，但随着核数的增长，花费在请求消息到定序点的间接延迟也越来越高，同时所有消息发送至同一个定序点，也会导致网络拥塞。由此AGARWAL提出了INSO[5]，为每一个节点分配一组不同的定序号，当一个节点需要向网络注入一个请求的时候，就从自己所拥有的定序号中选出一个最小的未被使用的号码，分配给这个请求，接收节点通过识别定序号的大小来保证全局的顺序一致，由此完成消息的定序。这样虽然避免了间接的延迟，但对于一直没有请求注入的节点，其拥有定序号未被使用，就需要设置过期窗口来保证网络的性能，而过多的过期消息又会导致网络功耗和带宽浪费。

DAYA等提出的SCORPIO[6]采用双层网络组合结构，主网络负责广播一致性请求和传递回应消息，通知网络用于广播通知消息，对于每一个注入的一致性请求，都会有一个通知消息被广播到通知网络，以通知其他节点该节点的请求消息正在被传递和需要被排序。同时，接收节点对一段时间窗内接收到的所有通知消息进行轮询优先级排序，在此后的一个时间窗内按照排序对接收到的请求进行处理。这样的设计由于排序时间窗的存在，会额外增加一致性事务处理的基础延迟，当负载较小的时候会导致网络利用率低下。

3.1.2 解决广播问题

AGARWAL提出了一致性过滤器的方式，每个节点路由器都有一个过滤器用来记录当前请求通过该节点的出口是否能访问到目的节点[7]。ANIRUDDHA提出了一种层级总线的方式，如图2(a）所示，将网络切割为多个区域，每个区域内部采用子总线的方式进行广播，同时各个区域之间采用中心总线连接并进行广播，如此避免全网络的广播[8]。ZHAO提出了一种混合的NoC设计，如图2(b）所示，对每一个节点不仅有一个路由器，还配备有一个总线开关，通过控制开关来切换总线模式和路由器模式，由此多个节点就能建立一条总线路径用于广播消息，避免了无用的广播[9]。MASING等针对区域粒度的缓存一致性，在电路交换与包交换的混合NoC架构中设计了类似于旁路的In-NoC电路[32]，减少了区域间的远程一致性消息的延迟，但是消耗了更多的存储资源。ZHANG设计的双层架构混合协议根据处理器核间数据相关性强弱，分别使用总线侦听协议与目录协议，提高了一致性的维护效率[10]。

图2新型总线结构设计

3.2 目录一致性协议

随着核数逐渐增加到上百甚至上千个，进入到众核系统，通常只能采用目录协议来维护缓存一致性[18]。目录一致性协议的核心是建立中心目录来记录数据的共享状态，并担当定序点与多播转发的角色，所有的一致性事务都需要经过目录节点，如此解决了一致性事务排序问题，同时有效降低了无用广播。但随着核数的不断增多，目录信息记录的存储消耗呈指数增长，使得面积开销变得不可扩展，因此减少目录存储消耗是目录一致性协议优化的重要方向。此外，由于中心节点目录的存在，一致性事务的处理流程比侦听协议更为复杂，导致一致性协议流量增加，减少一致性维护对网络流量的过多占用也是目录协议优化的重要议题。

3.2.1 减少目录存储消耗

最原始的目录协议是在LLC中所有的缓存行都有一个对应的目录项，目录所占面积是相当大的。因此BARROSO等提出了复制标记目录，只维护当前被私有缓存的数据所对应的一致性信息[11]。目录复制所有被私有缓存存储的缓存行的标记，并存储状态信息。随着核数的不断增多，复制标记目录依然存在着重复存储标记导致的目录浪费，由此稀疏目录[12,13,14]用一个位向量记录多个共享者，只需要存储一个标记，可以有效避免标记重复记录。但由于其相联度随着核数呈线性增长导致目录的查询功耗越来越高，使得稀疏目录缺少可扩展性。降低相联度又会引起替换失效，然而通过提供组数以提高目录容量来缓解替换失效，则会导致多余的硬件开销。

层次化目录的提出是一种面积可扩展的方式，GUO提出了一种层次结构目录对多核进行逻辑分组的方案[15]，其采用多级目录来记录共享信息，高层的目录记录低层目录的一致性信息，相比传统目录组织结构，能够将一致性交互事务局部化，以此减少存储开销，降低延迟，但是却大大增加了协议的复杂度。

无标记目录[16]采用布隆过滤器阵列的组织方式来代替有标记目录存储一致性信息以减少面积开销，如图3所示，每个布隆过滤器由k个哈希函数和对应的k个位向量组成。每个布隆过滤器对应一个核中的一组缓存信息。由于位向量比标记的开销小得多，由此达到节省面积的目的。但由于其查找功耗会随着核数呈线性增长，导致可扩展性降低，其存在的假阳性错误判断导致的额外的一致性操作也使得协议设计变得复杂以及性能损失。

图3布隆过滤器结构与组织方式[16]

cuckoo目录[12]在稀疏目录的基础之上，采用一种迭代“插入-替换”的策略，在不增加目录容量的同时，解决稀疏目录在降低相联度时所导致的目录项组冲突问题。其核心是通过迭代插入打破存储冲突的传递，如图4所示。但是当高负载的时候，可能会频繁达到迭代阈值导致功耗高且性能低。

图4cuckoo哈希插入操作[12]

stash目录[17]发现被独占的数据当目录项被替换出时，并不需要无效，这并不会引起功能错误，且能够避免由此导致的缓存缺失和重新装载的操作，因此在目录中将缓存的缓存块划分为“共享”和“独占”两种状态，对于“独占”状态被替换出时，只丢掉目录项，而不无效对应缓存块，为了保证协议的正确，其还设计了广播找回机制。这样充分降低了目录项冲突导致的性能损失，也能降低目录的容量消耗。

SCD目录[18]将有限指针目录与层次化目录相结合提出了一种可伸缩的一致性目录，对于只被单个或者少许几个核共享的缓存行，采用有限指针格式逐个记录，当被多个核共享时采用层次化目录格式，划分为根目录和叶子目录，根目录记录各个叶子目录的共享信息，叶子目录记录各个成员的共享信息，如此能够减少目录消耗的面积。VALLS提出了可扩展的PS目录[19]，通过观察大部分数据负载都是私有的，将目录分别组织为私有目录和共享目录，各自记录共享数据和私有数据的信息，由于私有目录通常只有在替换出和重新载入时才会被访问，因此采用了速度更低但相同面积容量更大的EDRAM来记录，如此能够显著减少目录的硬件消耗。ALISAFAEE观察到一段地址区域的数据在同一时间被多个核访存的概率实际是很小的，由此提出了SCT协议[20]，使用双粒度追踪机制，其目录结构如图5所示，对于暂时处于私有状态的数据，采用区域粒度（粗粒度），当区域内某块数据被多核同时共享时，转化为块粒度，由此可以大量节省目录的面积。SPACE协议[21]基于程序的局部性发现对于一个具体应用通常访存的都是相同的几个核的组合，对应对于同一数据的共享也通常是相同的组合模式。于是采用记录组合模式的方法，对于被共享的缓存块由指针指向一个组合，当记录的组合超过了目录的容量时，则将相似组合融合，转为粗粒度的记录。

图5SCT双粒度目录结构[19]

DAVIDE根据访存行为的变化提出了混合目录一致性协议模型[34]。其根据维护一致性的层级分为非一致模型、全一致模型和末级缓存一致模型。采用非一致模型时跳过缓存，直接通过DMA访问内存；全一致模型则和普通目录一致性操作一样，维护所有私有缓存的一致；末级缓存一致模型则处于两者中间，只需维护与末级缓存之间的数据一致。通过访存行为特点，变换一致性模型，避免一直使用全一致性，以减少目录面积，同时加快访存的速度。

MENEZO从目录协议与侦听协议混合的角度提出了FLASK混合协议[36]。对于非共享数据，其不存储于目录中，而是通过令牌计数来保证其一致性正确，并监管其共享状态，目录只管理经常处于共享状态的数据，从而大幅降低了维护一致性的目录存储消耗。

这几种基于数据共享特点进行优化设计的目录协议虽然都能减小目录的硬件开销，但对于频繁变化的数据共享状态的程序负载，则会显得效率低下。

3.2.2 目录协议流量优化

在传统的目录一致性协议中，一致性事务通常会经历4个阶段。Ros提出的直接一致性协议DiCo-CMP[22]通过在缓存块的标记中增加owner域，请求节点可以直接向数据拥有者发送请求，与传统目录协议的对比如图6所示，节省了由目录转发的步骤。这是一个用缓存面积换取效率的策略，在访存延迟降低的同时增加了所有L1的标记域所占用的面积。

图6协议流程对比[22]

由于目录一致性协议中目录的请求转发通常会在NoC中产生大量多播事务，如果直接采用多单播包的发送方案，大量重复的单播流量会导致网络拥塞，CHAVES在一个3×2的MPSoCs中的实验表明采用多播数据包而非多单播包的方式能提高32%的系统性能[33]。因此LU等提出了基于路径的多播方式[23]，当源节点需要发送一个多播消息时，在NoC中建立一条多播路径，多播包会按照多播路径顺序依次传递到目的节点，只有在经过目的节点路由器时会进行复制，整个链路中的每个多播消息只有一个多播数据包。但由于路径末端的节点接收到多播包的延迟较大，导致一致性协议效率低下。于是JERGER等提出了一种建立多播树的方式[24]，源节点先发送一个“建立包”，用于提前建立多播树，之后再顺着建立的多播树发送并传递多播包，能够避免无意义的广播，但也由于增加了多播树的建立操作，会消耗额外的路由器面积开销并增加延时，TIWARI等提出了动态分区的方法构造多播树，避免在建立操作的同时增加了链路复用[25]。

除多播通信之外，共享节点在向源节点回应消息时还会产生聚合通信[26]。为减少这些消息所占用的链路资源，MA等提出了消息组合归约的策略[27]，如图7所示，多播消息在传递过程中建立起一棵逻辑树，在逻辑树中的路由节点上设置消息组合表用以记录接收到的返回消息，当一个节点接收到所有的叶子节点的返回消息之后，再聚合成一个回应消息返回给其根节点，如此完成归约聚合。

图7归约消息组合[27]

3.3 其他一致性协议

不论是侦听一致性协议还是目录一致性协议，大多都是基于MESI协议编码实现的。面对MESI协议实现的种种问题，一些学者也提出了采用其他一致性状态分类或者不采用状态编码的一致性协议[28]。

PUGSLEY提出了一种SWEL协议[29]来减少一致性操作的步骤。SWEL分别代表Shared、Written、ExclusivityLevel3种状态。SWEL的核心思想在于将私有和只读数据块与共享数据块分开存储，通过监测数据块的状态，然后将其移动至对应的缓存中即可，这样的设计虽然避免目录结构的使用，却可能会造成频繁的远程访问L2缓存，导致系统效率低下。RSWEL是针对SWEL的一种优化，其L2中的共享数据块在特定时刻能重新缓存到L1缓存中，避免频繁的远程访问[29]。Token协议[30]不同于MESI与SWEL，不再采用专门的状态位记录缓存块状态，而是为每一个共享缓存块分配固定数量的令牌，当一个核拥有至少一个令牌时，才能读取该共享数据块，当其拥有所有的令牌时，才能对该数据块进行写操作，由此保证了同一时刻只有一个写操作者或者多个读操作者，且当一个核进行写操作时，其余所有的数据副本都是无效的，确保了一致性协议的正确性。可以看出，Token协议中的令牌拥有数目与MESI协议的各种状态具有对应关系，Token协议却避免了目录的使用，因此能有效避免网络热点，提高链路利用率，其持续请求机制也能避免请求过多时的请求饥饿现象[31]。为了提高NoC中的存储资源利用率，HAN等提出了RMCC缓存机制[35]，并增加了消息传递缓冲区的管理状态，实现数据缓存与消息缓冲的可配置功能，从而减少硬件消耗。

虽然以MESI编码基础下的目录和侦听协议依然是主流，要研发一整套新型的协议难度较大，方案较少，但这些新型协议也逐渐显露出更适应片上网络环境的特点，值得持续关注。

4、存在的问题与进一步研究的方向

片上多核系统已经成为未来高性能计算机的发展趋势，而缓存一致性问题一直是困扰多核体系结构发展的难题之一，学者们针对目录协议的组织已经有多种结构的研究，从层次化的角度和混合粒度的角度，缩小单个条目的角度等都能在一定程度上提高目录的可扩展性，取得了一定的进展，而当前主流的一致性协议设计仍然面临许多问题，主要可以归纳如下。

(1）消息排序问题。请求消息的排序问题是确保协议功能正确性的必要条件，不论是采用改进型侦听协议的分布式排序[5]还是时间窗排序[6]都会导致网络流量的浪费，而采用类似目录中心节点排序则会导致网络热点。

(2）广播/聚合问题。在维护缓存一致性过程中难免产生大量的广播与聚合消息[29]，重复的数据包占用了大量的片上链路资源，如何从路由或一致性协议的角度去减少重复的广播/聚合包对片上资源的占用是当下所有协议所面临的问题。

(3）存储消耗。采用状态编码的一致性协议多用位向量[13]或指针[18]等方式来存储每个核缓存的缓存状态，因此随着核数的不断增多，其存储消耗会呈指数增长，如何进一步降低一致性协议存储开销是将来会一直面临的问题。

(4）共享的发掘与预测。对共享数据的发掘和预测能够有效提高缓存一致性维护的效率，同时降低一致性协议的开销[19,20,21]，如何在不消耗过多额外硬件开销的前提下完成准确数据类型预测与归类，是值得研究的方向。

在这些问题中，问题（1）是协议正确性的保证，是首要的；问题（2）是协议效率的要求，是协议实用化需要迈过的门槛；问题（3）是协议可扩展性的体现，会存在于未来发展的时时刻刻；问题（4）则是辅助协议实现一致性的重要策略，需要更多更广泛的研究。

5、结束语

片上多核系统已经成为计算机体系结构设计的主流发展方向。本文聚焦于片上多核系统的缓存一致性维护进行综述，分析了多核一致性问题的产生，阐述了缓存一致性的定义，并进一步分析了多核发展导致的互连结构变革对传统一致性协议提出的挑战。针对研究最为广泛的传统侦听协议和目录一致性协议，归纳阐述了各自在NoC环境下的发展成果，此外还介绍了不同于MESI的其他协议，最后总结了缓存一致性协议当下需要解决的问题以及未来发展方向。如何设计可扩展的高效缓存一致性协议是未来多核处理器亟待解决的关键问题。

参考文献：

[1]戴锦文,缪小勇.摩尔定律的过去､现在和未来[J].电子与封装,2015,15(10):30-34.

[2]赵宝功,徐玉洁,屈凌翔.基于NOC技术的多核研究[J].电子与封装,2015,15(11):34-38.

[4]汪健,张磊,王少轩,等.多核处理器核间高速通讯架构的研究[J].电子与封装,2011,11(6):46-53.

[10]张阿敏.基于片上网络的众核高速缓存一致性研究[D].合肥:合肥工业大学,2018.

[14]吴健虢,陈海燕,刘胜,等.多核Cache稀疏目录性能提升方法综述[J].计算机工程与科学,2019,41(3):5-12.

[27]马胜.Cache一致性片上网络路由算法和流控机制优化关键技术研究[D].长沙:国防科学技术大学,2014.

陈家豪,黄乐天,谢暄,魏敬和.基于片上网络互连的多核缓存一致性研究综述[J].电子与封装,2020,20(11):3-10.

基金:国家自然科学基金(61701095).