用于多核处理器的一致性维护装置及一致性交互方法

摘要

本发明公开了一种用于多核处理器的一致性维护装置及一致性交互方法，主要用于解决现有多核处理器Cache一致性协议在处理读缺失和写缺失的一致性交互过程中目录访问延迟大的技术问题。本发明将多核处理器的所有内核划分为并列关系的多个节点，每个节点包含多个内核。在发生读、写缺失时根据节点预测Cache直接预测访问与读、写缺失内核最近的有效数据副本节点，并将更新目录步骤推迟到数据访问结束以后进行，从而完全隐藏目录访问延迟，提升了访存效率；双层目录结构将目录存储开销由指数级增长转化为线性增长，更具可扩展性；由于以节点为单位进行粗粒度预测，相对以内核为单位进行的细粒度预测节省了预测信息的存储开销。

说明书

【技术领域】

本发明涉及计算机技术领域，尤其涉及多核处理器Cache一致性维护的相关装置和一致性交互方法。

【背景技术】

良好的可扩展性和对芯片面积的高效利用促使CMP处理器(Chip Multi-Processor)被广泛使用。然而， 芯片上连线的电气特性不可能与半导体工艺等比例缩放，线延迟问题已经成为未来CMP设计的重要限制因 素。研究者提出延迟非一致的Cache访问(Non-Uniform Cache Access，NUCA)结构来减轻线延迟对访问 Cache延迟的负面影响，如D-NUCA，NuRAPID，Victim Replication等。在NUCA结构下，访存延迟依赖 于请求内核与目标数据之间的具体物理距离。如果目标数据存在于请求内核附近内核中，则平均数据访问 延迟就能够被减少，这一特性同样适用于Cache一致性问题。

Cache一致性协议是CMP处理器正确运行的保证，考虑到扩展性问题，相对于总线监听协议来说，基 于目录的Cache一致性协议是大规模CMP更合适的选择。目录能够跟踪全局的一致性状态和L2 Cache中 数据所有共享者的标识。缺失内核将通过网络把消息发送到相应目录内核中进行处理。然而，不断提升的 线延迟和多个内核间复杂的一致性交互直接导致了访存延迟的提升。如何为深亚微米工艺下的多核处理器 设计高效、可扩展的Cache一致性协议已经成为体系结构领域研究的重要内容。

通过研究已有的基于目录的Cache一致性协议，我们发现发生读缺失内核需要访问目录内核来间接得 到一致性信息，这将增加Cache读缺失延迟。更重要的是，在较为常用的瓦片式CMP结构下，这种间接性 将导致更多的Cache缺失。原因是目录信息通常是通过物理地址映射关系分布在这些瓦片式的内核中，而 不考虑内核可能访问任何一个数据块，因此需要访问远程Cache的可能性大大增加。间接性的读操作将在 以下两方面对性能产生负面影响：首先，相对于写操作来说，读操作的效率能够在更大程度上影响系统的 整体性能。其次，在多个请求同时访问目录的情况下，目录访问会发生拥塞，多个读操作不得不被排队依 次响应，从而增加了读缺失的平均访存延迟。与读缺失类似，写操作也存在同样的间接性。

为了减少一致性交互延迟，文献1“Stefanos Kaxiras and Georgios Keramidas.2010.SARC Coherence： Scaling Directory Cache Coherence in Performance and Power.IEEE Micro 30，5(September 2010)，54-65.”提出 Writer一致性协议，该协议的创新在于使用基于预测的透明读操作，能够使一部分读操作在获得数据后不在 目录中保留“踪迹”，而是在同步操作时自作废，后续写操作不用作废这些透明读数据。这降低了一致性状态 转换频率(E或M→S)，简化了写操作一致性交互过程，但同时也削弱了已经建立的数据局部性。写操作 同样基于历史预测，但如果预测错误需要增加额外的一致性交互延迟。另外，这种协议需要弱顺序存储模 型和复杂的软件同步策略，限制了其应用范围。

文献2“Alberto Ros，Manuel E.Acacio，and Jose M.Garcia.2010.A Direct Coherence Protocol for  Many-Core Chip Multiprocessors.IEEE Transaction of Parallel and Distributed System.21，12(December 2010)， 1779-1792.”提出DiCo-CMP一致性协议，通过将目录信息集成在数据拥有者内核中，DiCo-CMP能直接将 请求发送到数据的拥有者，而不是先发送到目录内核，再转发到数据拥有者，避免了间接数据访问。相对 于普通目录协议，DiCo-CMP能够使访存延迟平均减少6％左右。DiCo-CMP只考虑到直接提供有效数据， 由于集成目录的数据拥有者内核位置固定，而无法兼顾到该有效数据是否距离请求内核最近，事实上可能 存在距离请求内核更近的有效数据，因此访存延迟仍有降低空间。

文献3“Hongbo Zeng；Jun Wang；Ge Zhang；Weiwu Hu；An interconnect-aware power efficient cache  coherence protocol for CMPs，Parallel and Distributed Processing，2008.IPDPS 2008.IEEE International  Symposium on，vol.，no.，pp.1-11，14-18 April 2008”提出了基于片上网络拓扑结构的Cache一致性协议，这种 协议不从目录内核返回数据，而是通过目录内核将请求转发至距离请求内核最近的目标数据副本内核，使 之响应请求并发送数据。这种机制最小化了数据在连线上的传输距离，能使网络链路功耗减少9.3％；并且 通过减少链路拥塞加快通信速度，使整体性能提升1.4％。该协议虽然能提供距离最近的数据副本，有效降 低功耗，但仍需要先访问目录，间接事件仍然存在，一致性交互延迟难以降低。

【发明内容】

本发明的目的在于提供一种用于多核处理器的一致性维护装置及一致性交互方法，能偶有效隐藏多核 处理器一致性交互过程中的目录访问延迟，从而提升访存效率。

为了实现上述目的，本发明一种用于多核处理器的一致性维护装置采用如下技术方案：

一种用于多核处理器的一致性维护装置，包括N个处理器内核、片上网络和主存；所述主存和N个处 理器内核均连接片上网络；所述N个处理器内核构成包含多个节点的二位网络矩阵；每个节点包含2ⁿ个处 理器内核，n为大于等于1的正整数，N为2ⁿ的整数倍；

所述处理器内核包括：全局目录，以粗向量的方式跟踪数据所在节点；节点目录片段，负责在节点内 跟踪数据副本所在的内核位置；一个节点内的所有节点目录片段构成该节点完整的节点目录；目录控制器， 包括节点目录控制器和全局目录控制器，用于接收、发送一致性交互消息，控制全局目录和节点目录维护 数据一致性；节点预测Cache，用于保存距离请求内核节点最近的有效目标数据副本节点，为发生缺失时的 直接访问提供历史信息依据；节点共享历史信息Cache，用于保存节点对数据的共享历史向量，为节点预测 Cache的更新提供历史信息依据；节点挂起指针，用于在读缺失过程中暂存读缺失节点指针，为隐藏目录访 问延迟提供支持；最后写节点指针，用于在基于读缺失的节点预测Cache更新过程中指明共享历史向量所 在节点位置；私有L1 Cache；共享L2 Cache片段。

本发明进一步的改进在于：处理器内核还包括一个路由器，所述处理器内核通过路由器连接所述片上 网络；所述路由器连接全局目录控制器、共享L2 Cache片段和节点目录控制器；所述全局目录控制器连接 所述全局目录、共享L2 Cache片段和节点目录控制器；所述节点目录控制器连接私有L1 Cache、节点挂起 指针、节点目录片段、节点预测Cache和节点共享历史信息Cache；L1 Cache连接共享L2 Cache片段。

本发明进一步的改进在于：一个节点内的2ⁿ个处理器内核使用n位二进制数进行节点内编码索引。

为了实现上述目的，本发明一种用于多核处理器的一致性交互方法采用如下技术方案：

一种用于多核处理器的一致性维护装置进行一致性交互的方法，包括节点目录访问方法，所述节点目 录访问方法包括：

将节点目录分成2ⁿ个片段，每个内核存储一个节点目录片段，按照数据地址末段与节点中内核编码相 对应的方式将节点内的数据共享信息分布到所有节点中内核的节点目录片段上；

访问节点目录时第一步首先根据数据地址的末n位访问对应编码内核的节点目录片段，如果访问命中， 则结束访问；如果在该节点目录片段没有命中，则第二步同时访问本节点内剩余的节点目录片，如果仍然 不命中，说明该数据在该节点中不存在，则节点目录访问结束。

本发明进一步的改进在于：某一处理器内核发生读缺失时，该处理器内核首先根据缺失数据地址采用 节点目录访问方法访问本节点的节点目录，如果节点目录命中，则直接从本节点的其它处理器内核中获得 缺失数据副本，并更新节点目录；

如果节点目录不命中，则根据缺失数据地址查找本节点内对应的节点预测Cache预测信息，如果节点 预测Cache也不命中，则按照3-hops读操作流程访问缺失数据地址对应的全局目录，由该全局目录通知缓 存有效数据副本且距离最近的节点向读缺失处理器内核发送数据，读缺失处理器内核收到数据后根据数据 地址更新相应的节点目录片段，同时全局目录加入读缺失节点共享信息；

如果节点目录不命中，但节点预测Cache命中，则根据节点预测Cache中的最近节点指针向预测节点 发出读数据请求；被预测访问节点首先访问节点内目录，如果不命中则将该请求转发至该请求数据的全局 目录，然后按照3-hops读操作流程，由该全局目录通知缓存有效数据副本且距离最近的节点向读缺失处理 器内核发送数据，读缺失处理器内核收到数据后根据数据地址更新相应的节点目录片段，同时全局目录加 入读缺失节点共享信息；

如果节点预测Cache命中，且被预测访问节点的节点内目录也命中，说明预测节点预测Cache预测正 确，则被预测访问的节点在向读缺失节点发送数据副本前先将节点挂起指针指向读缺失节点，将读缺失节 点挂起；然后向读缺失节点发送数据副本，并同时通知全局目录加入读缺失节点信息；全局目录更新完毕 后，被预测访问的节点清除节点挂起指针，节点挂起过程结束；如果在挂起过程结束前数据被作废，则被 预测访问的节点在收到全局目录的作废消息后，根据节点挂起指针将读缺失节点刚收到的数据副本作废掉。

本发明进一步的改进在于，包括以下步骤：

对处于I状态的写缺失数据将从下一级存储器先读入数据，再进行修改；

发生写缺失时，写缺失处理器内核首先根据缺失数据地址访问对应节点预测Cache，如果节点预测Cache 不命中，则向全局目录发送请求，然后按照3-hops写缺失流程，由该全局目录向所有缓存该数据副本的节 点发送作废请求，距离写缺失处理器内核最近且接收到作废请求的节点向写缺失处理器内核发送缺失数据 副本，所有接收到作废请求的节点作废自身的数据副本；写缺失处理器内核收到数据后根据数据地址更新 相应的节点目录片段，所有接收到作废请求的节点根据数据地址更新相应的节点目录片段，同时全局目录 加入写缺失节点共享信息并删除被作废节点的共享信息；

如果节点预测Cache命中，则根据最近节点指针进行直接预测访问，写缺失处理器内核向全局目录和 预测节点同时发出两个访问请求，根据写缺失数据所处状态的不同，分为以下两种情况处理：

1)、当写缺失数据是M或E状态时，发往全局目录的请求查询到写缺失数据状态为M或E后，全局 目录忽略该请求；而发往预测节点的请求在最近节点指针预测正确的情况下将直接作废掉处于M或E状态 的唯一写缺失数据副本；而在最近节点指针预测错误的情况下请求将被错误预测节点转发到全局目录进行 处理；

2)、发往全局目录的请求查询到写缺失数据的状态为S后，按照4-hops写缺失流程，由该全局目录向 所有缓存该数据副本的节点发送作废请求，距离写缺失处理器内核最近且接收到作废请求的节点向写缺失 处理器内核发送缺失数据副本，所有接收到作废请求的节点作废自身的数据副本；写缺失处理器内核收到 数据后根据数据地址更新相应的节点目录片段，所有接收到作废请求的节点根据数据地址更新相应的节点 目录片段，同时全局目录加入写缺失节点共享信息并删除被作废节点的共享信息；而发往最近节点指针预 测节点的请求在预测正确的情况下将查询到写缺失数据的状态为S，此后该被预测访问节点将忽略该请求； 在最近节点指针预测错误的情况下，请求将被错误预测节点转发到全局目录，而全局目录将忽略该转发的 请求。

本发明进一步的改进在于：

(a)替换处于M或E状态的数据时，包括如下具体步骤：

当被替换的数据处于M或E状态时，一致性维护装置上只存在唯一数据副本，发生替换的处理器内核 先发送消息剔除该数据所在节点目录中的内核信息和全局目录中对应的节点信息；

发生替换的处理器内核收到确认消息后进行替换操作；

M状态数据替换前还需要写回主存；

(b)替换处于S状态的数据时，包括如下具体步骤：

所在的节点中存在多个副本，只需要通知节点目录剔除发生替换操作的内核信息后进行替换，而无需 通知全局目录；

(c)替换操作所引起节点预测Cache预测访问的扑空，在读、写缺失时，该类扑空均按照节点预测Cache 预测错误处理。

本发明进一步的改进在于：

对共享同一数据的节点在全局目录中留下的共享信息的处理包括以下情况：

1)、对一个节点来说，每当数据发生I→S、I→E、M→S或E→S的状态转换时，生成新的全局目录共 享信息；

2)、对一个节点来说，每当数据发生S→M或E→M的状态转换时，也就是写操作发生时，当前全局 目录中的共享信息将由写操作节点回收，并与之前的共享历史向量信息进行“或”操作产生新的共享历史向量 信息，存储在写操作节点的节点共享历史信息Cache中；

3)、没有发生过写操作的数据不存在共享历史向量信息，对一个节点来说，当数据第一次发生I→M、 S→M或E→M的状态转换时生成共享历史向量信息；在后续发生写操作时根据全局目录共享信息生成新的 共享历史向量信息，并在发生写操作的节点间传递，从而实现了节点共享历史信息的保存；

4)、对一个节点来说，每当数据发生S→I、E→I或M→I的状态转换时，说明其它节点进行了写操作， 该数据的全局目录共享信息被作废掉。

本发明进一步的改进在于，基于写操作的节点预测Cache历史信息更新方法包括以下情况：

1)、发生写缺失时，当数据处于E状态，对应共享历史向量信息还未生成，无需进行历史信息更新；

2)、发生写缺失时，当数据处于M状态，数据副本唯一并且与对应共享历史向量信息一起存储在上一 个写操作节点中，写缺失节点根据节点预测Cache预测信息进行预测访问；在最近节点指针预测正确的情 况下，上一个写操作节点收到访问请求，并根据本节点中存储的共享历史向量信息对历史共享节点中的节 点预测Cache信息进行更新，使最近节点指针指向写缺失节点；在最近节点指针预测错误的情况下，请求 将由全局目录中转到达上一个写操作节点，并根据本节点中存储的共享历史向量信息对历史共享节点中的 节点预测Cache信息进行更新，使最近节点指针指向写缺失节点；

3)、发生写缺失且数据处于S状态时，数据副本不唯一，共享历史向量信息与其中一个数据副本一起 存储在上一个写操作节点中；全局目录响应写缺失节点的请求，并根据目录信息向数据副本所在节点发出 作废消息；存有写缺失数据对应共享历史向量信息的数据共享节点收到消息后不仅要作废自身数据副本， 还要根据共享历史向量信息对历史共享节点中的节点预测Cache信息进行更新，使最近节点指针指向写缺 失节点；其它共享节点只需作废数据即可；

4)、发生写命中时，如果上一个写操作节点与当前写操作节点相同，则无需更新历史信息；如果上一 个写操作节点与当前写操作节点不同，且当数据处于E、M、S状态时，更新过程分别与对应的上述1)、2)、 3)中写缺失更新过程相同。

本发明进一步的改进在于，基于读操作的节点预测Cache历史信息更新方法包括以下情况：

1)、读缺失内核的数据状态变化为I→E时，数据从下一级存储器中取入，共享历史向量信息不存在， 无须更新节点预测Cache；

2)、读缺失内核的数据状态变化为I→S，且数据由一致性维护装置上处于E状态节点提供时，共享历 史向量信息不存在，无须更新节点预测Cache；

3)、读缺失内核的数据状态变化为I→S，且数据由一致性维护装置上处于M或S状态节点提供时，共 享历史向量信息已经存在，节点预测Cache更新过程包括以下两种情况：

3.1)、当读缺失节点的节点预测Cache命中时，上一个写操作节点利用自身存储的共享历史向量信息和 当前全局目录共享信息进行两次过滤操作，生成最终需要更新的历史共享节点信息，并根据该最终共享历 史向量进行节点预测Cache的更新；更新节点预测Cache时，检查更新前后历史共享节点与其预测节点间 的距离变化情况，只在距离缩短的情况下才更新历史共享节点的节点预测Cache；

3.2)、当读缺失节点的节点预测Cache不命中或命中但预测错误时，除需要全局目录转发请求外，更新 过程与节点预测Cache命中相同；

4)、如果最后写节点指针指向的上一个写操作节点中读缺失数据副本和对应共享历史向量信息已经被 替换出去，则本次节点预测Cache更新终止。

与现有技术相比，本发明主要具有以下优点：本发明公开了一种用于多核处理器的一致性维护装置及 一致性交互方法，主要用于解决现有多核处理器Cache一致性协议在处理读缺失和写缺失的一致性交互过 程中目录访问延迟大的技术问题。本发明将多核处理器的所有内核划分为并列关系的多个节点，每个节点 包含多个内核。在发生读、写缺失时根据节点预测Cache直接预测访问与读、写缺失内核最近的有效数据 副本节点，并将更新目录步骤推迟到数据访问(读操作或作废操作)结束以后进行，从而完全隐藏目录访 问延迟，提升了访存效率；双层目录结构将目录存储开销由指数级增长转化为线性增长，更具可扩展性； 由于以节点为单位进行粗粒度预测，相对以内核为单位进行的细粒度预测节省了预测信息的存储开销；另 外，还配套设计了节点预测Cache的动态更新算法来保证其预测精确性，减少了由于预测错误或不准确造 成的额外延迟。

【附图说明】

图1是基准多核处理器结构图；

图2是多核处理器的节点划分示例图；

图3是本发明一致性维护装置中的目录组织结构图；

图4是本发明一致性维护装置相对于基准多核结构的变化图；

图5是节点挂起技术的工作流程图；其中图5(a)为节点挂起读操作流程，图5(b)节点挂起读操作 中加入写操作的作废流程；

图6是本发明对读缺失的一致性交互方法图；

图7是本发明对M、E状态写缺失数据的一致性交互方法图；其中图7(a)为基于CNP正确预测的M、 E状态数据的2-hops写缺失处理流程；图7(b)为基于CNP错误预测的M、E状态数据的4-hops写缺失 处理流程；

图8是本发明对S状态写缺失数据的一致性交互方法图；其中图8(a)为基于CNP正确预测的S状态 数据写缺失处理流程；图8(b)为基于CNP错误预测的S状态数据写缺失处理流程；

图9是“签名”与SHV信息的流向与变化图；其中图9(a)为“签名”信息的生成、作废和回收图；图9 (b)为以图2为例SHV信息的产生、传递过程图；

图10是M、S状态数据基于写缺失的NPC更新流程图；

图11是基于读缺失的NPC更新算法图；

图12是全映射目录与本发明的读缺失一致性交互过程对比图；其中图12(a)为2³×2³个内核CMP中 全映射目录协议的3-hops读缺失处理图，包括以下步骤：(1)P55发生缺失，向目录发出读请求，(2)目 录通知距离P55最近的P62提供数据，(3)P62向P55发送数据，同时向目录发确认消息；图12(b)为对 2³×2³内核、节点规模22内核CMP的读缺失处理图，包括以下步骤：(1)P55发生缺失，向节点目录发出 读请求，(2)P55所在节点16的节点目录未命中，访问P56中NPC，根据CNP预测访问节点15的节点目 录，(3)在P54节点目录片段命中，将NHP指向节点16，并通知P62向P55提供数据；同时向全局目录 发出目录更新请求，(4)P62向P55发送数据，并更新P56节点目录片段，(5)P54收到全局目录更新确认 消息后将NHP清除；

图13是现有的全映射目录协议读缺失一致性交互过程图；其中图13(a)为4-hops读缺失处理流程， 图13(b)为3-hops读缺失处理流程；

图14是现有的全映射目录协议写缺失一致性交互过程图；其中图14(a)为M、E状态数据4-hops写 缺失处理流程，图14(b)为M、E状态数据3-hops写缺失处理流程，图14(c)为S状态数据4-hops写 缺失处理流程；

图15本发明一致性维护装置多个功能部件的连接关系图。

【具体实施方式】

请参阅图1至图15所示，本发明一种用于多核处理器的一致性维护装置，包括全局目录、节点目录、 目录控制器、节点预测Cache、节点共享历史信息Cache、最后写节点指针和节点挂起指针。包括以下方面：

(a)节点划分方法

片上所有内核被划分为多个节点，每个节点包含2ⁿ(n≥1)个内核，假设片上有N个内核(N为2ⁿ的整 数倍)，则该处理器包含个节点，N个内核构成2-D MESH阵列。一个节点内的2ⁿ个内核使用n位二进 制数进行节点内编码索引，如n＝2时，节点内的4个内核分别编码为00、01、10、11。多个节点间是同一 层次并列关系，如图2。

(b)双层目录结构

如图3所示，全局目录以粗向量的方式跟踪数据所在节点。由于数据地址以静态的方式映射到所有L2 Cache片段，因此全局目录只负责跟踪其对应L2 Cache片段中数据副本。节点目录采用全映射位向量目录， 负责在节点内跟踪数据副本所在的内核位置。

(c)节点目录的两步访问方法

将节点目录分成多个片段，每个内核存储一个目录片段，简称为NDS(Node Directory Slice)，按照数 据地址末段与节点中内核编码相对应的方式将节点内的数据共享信息分布到所有节点中内核的目录片段 上。

设节点规模为M，则访问节点目录时第一步首先根据数据地址的末n位访问对应编码内核的NDS，如 果数据确实存在于该节点中，则访问将在该目录命中。如果在该NDS没有命中，则第二步同时访问剩余的 M-1个NDS，如果仍然不命中，说明该数据在该节点中不存在。举例来说，假设节点包含4个内核，即n＝2。 使用2位二进制数对节点中内核进行编码，分别是00、01、10、11，共享数据地址末两位为11的数据首先 将其共享信息存储在编码为11内核的NDS中。如果该内核的NDS已满，再写入其它三个内核的NDS中， 其它数据以此类推。访问节点目录时首先根据数据地址的末两位访问对应编码内核的NDS，如果不命中再 访问其它三个内核的NDS。

(d)目录控制器

与目录集成在一起，用于对两级目录进行控制，接收和发送一致性交互消息，并对一致性交互过程进 行管理。

(e)节点预测Cache

如图4，节点预测Cache-NPC(Node Predicting Cache)，用于保存距离请求内核节点最近的有效目标 数据副本节点，为发生缺失时的直接访问提供历史信息依据；NPC条目中除tag外还保存了最近节点指针 CNP(Closest Node Pointer)，该指针指向距离请求内核节点最近的有效目标数据副本节点。发生读、写缺 失时，内核根据NPC中存储的CNP信息就能够直接进行访问，而不需要访问目录。

与节点目录类似，每个内核的NPC只存储地址末n位与该内核n位节点内二进制编码相同的数据的预 测信息，也就是说发生读、写缺失的内核需要根据缺失数据的地址末n位来访问该数据CNP预测信息所在 的NPC。

(f)节点共享历史信息Cache

如图4，节点共享历史信息Cache-SHC(Sharing History Cache)，用于保存节点对数据的共享历史向 量，为节点预测Cache的更新提供历史信息依据；CNP的有效性和准确性需要更新算法来保证，为了保证 更新算法的精确性，SHC中保存了共享历史向量SHV(Sharing History Vector)，用来保证更新时只对那些 曾经缓存数据副本的节点发出更新请求，避免造成网络拥塞和不完整更新。

(g)最后写节点指针

如图11，SHV存在于最后发生写操作的节点中，为了在数据处于S状态时能跟踪SHV信息的位置， 为全局目录的每个条目增加一个最后写节点指针LWP(Last Writer Pointer)来跟踪上一个写操作节点。LWP 指针在每次发生写操作时被更新一次，始终指向最后发生写操作的节点。

(h)节点挂起指针

为隐藏读缺失目录访问延迟，为每个节点目录片段(NDS)增加一个节点挂起指针-NHP(Node Hanging  Pointer)。被预测访问的节点在向读缺失节点发送数据副本前先将NHP指向读缺失节点，将读缺失节点挂起。 然后向读缺失节点发送数据副本，并同时通知全局目录加入读缺失节点信息。全局目录更新完毕后，被预 测访问的节点清除NHP指针，节点挂起过程结束。

如果在挂起过程结束前数据被作废，则被预测访问的节点在收到全局目录的作废消息后，根据NHP指 针也将读缺失节点刚收到的数据副本作废掉。

一致性维护装置进行一致性交互的方法，包括以下两方面：

(a)读缺失一致性交互

发生读缺失时，读缺失内核首先根据缺失数据地址访问本节点目录，如果节点目录命中，则直接从本 节点的其它内核中获得缺失数据副本，并更新节点目录。

如果节点目录不命中，则根据缺失数据地址查找本节点内对应的NPC预测信息，如果NPC也不命中， 则按照图13中现有的3-hops读操作流程访问全局目录，由全局目录通知缓存有效数据副本且距离最近的节 点向读缺失内核发送数据，读缺失内核收到数据后根据数据地址更新相应的NDS，同时全局目录加入读缺 失节点共享信息。

如果节点目录不命中，但NPC命中，则根据NPC中的CNP向预测节点发出读数据请求。被预测访问 节点首先访问节点内目录，如果不命中则将将该请求转发至该请求数据的全局目录，剩余流程与现有3-hops 读操作流程相同。

如果NPC命中，且被预测访问节点的节点内目录也命中，说明预测NPC预测正确，则被预测访问的节 点在向读缺失节点发送数据副本前先将NHP指向读缺失节点，将读缺失节点挂起。然后向读缺失节点发送 数据副本，并同时通知全局目录加入读缺失节点信息。全局目录更新完毕后，被预测访问的节点清除NHP 指针，节点挂起过程结束。

如果在挂起过程结束前数据被作废，则被预测访问的节点在收到全局目录的作废消息后，根据NHP指 针也将读缺失节点刚收到的数据副本作废掉。

(b)写缺失一致性交互

在写命中的情况下，仍需访问全局目录将其它副本作废。

对处于I状态的写缺失数据将从下一级存储器先读入数据，再进行修改。

发生写缺失时，写缺失内核首先根据缺失数据地址访问对应NPC，如果NPC不命中，则向全局目录发 送请求，执行图14中现有的3-hops写缺失流程。

如果NPC命中，则根据CNP进行直接预测访问，写缺失内核向全局目录和预测节点同时发出两个访问 请求，根据写缺失数据所处状态的不同，分为以下两种情况处理：

●当写缺失数据是M或E状态时，发往全局目录的请求查询到写缺失数据状态为M或E后，全局 目录忽略该请求。而发往预测节点的请求在CNP预测正确的情况下将直接作废掉处于M或E状态的 唯一写缺失数据副本。而在CNP预测错误的情况下请求将被错误预测节点转发到全局目录进行处理

●发往全局目录的请求查询到写缺失数据的状态为S后，按照图14中4-hops交互流程处理。而发往 CNP预测节点的请求在预测正确的情况下将查询到写缺失数据的状态为S，此后该被预测访问节点将 忽略该请求。在CNP预测错误的情况下，请求将被错误预测节点转发到全局目录，而全局目录将忽略 该转发的请求。

(3)一种利用一致性维护装置进行的保证中节点预测访问准确性的历史信息更新方法，包括以下几方面：

(a)“签名”信息回收技术

本发明基于MESI数据状态转换协议和如图1所示的多核处理器基准结构进行说明，在采用如MSI、 MOESI等其它数据状态转换协议和其它多核处理器结构但仍符合本发明权利要求范围的情况下，也属于本 发明的范畴。本发明将曾经共享同一数据的节点在全局目录中留下的共享信息称为“签名”信息，对“签 名”信息的处理包括如下步骤：

如图9(a)，对一个节点来说，每当数据发生I→S、I→E、M→S、E→S的状态转换时，生成新的“签 名”信息。

对一个节点来说，每当数据发生S→M、E→M的状态转换时，也就是写操作(包括缺失和命中)发生 时，当前全局目录中的“签名”信息将由写操作节点回收，并与之前的SHV信息(如果有的话)进行“OR” 操作产生新的SHV信息，存储在写操作节点的SHC中。

如图9(b)，没有发生过写操作的数据不存在SHV信息，对一个节点来说，当数据第一次发生I→M、 S→M、E→M的状态转换时生成SHV信息。在后续发生写操作时根据“签名”信息生成新的SHV信息， 并在发生写操作的节点间传递，从而实现了节点共享历史信息的保存。

对一个节点来说，每当数据发生S→I、E→I、M→I的状态转换时，说明其它节点进行了写操作，该数 据的“签名”信息被作废掉。

替换操作也会改变“签名”信息的内容，但本发明认为发生替换的节点重用该数据的可能性不强，对 其历史信息不予保存。

(b)基于写操作的历史信息更新方法

利用权利要求3(a)的“签名”信息回收技术，本发明实现了基于写操作的节点预测Cache历史信息 更新方法，其特征在于包括以下步骤：

发生写缺失时，当数据处于E状态，对应SHV信息还未生成，无需进行历史信息更新。

发生写缺失时，当数据处于M状态，数据副本唯一并且与对应SHV信息一起存储在上一个写操作节点 中，写缺失节点根据NPC预测信息进行预测访问。在CNP预测正确的情况下，上一个写操作节点收到访问 请求，并根据本节点中存储的SHV信息对历史共享节点中的NPC信息进行更新，使CNP指向写缺失节点。 在CNP预测错误的情况下，请求将由全局目录中转到达上一个写操作节点，并开始相同的历史信息更新过 程。

发生写缺失且数据处于S状态时，数据副本不唯一，SHV信息与其中一个数据副本一起存储在上一个 写操作节点中。全局目录响应写缺失节点的请求，并根据目录信息向数据副本所在节点发出作废消息。存 有写缺失数据对应SHV信息的数据共享节点收到消息后不仅要作废自身数据副本，还要根据SHV信息更 新历史共享节点中的NPC信息进行更新，使CNP指向写缺失节点。其它共享节点只需作废数据即可。

发生写命中时，如果上一个写操作节点与当前写操作节点相同，则无需更新历史信息。如果上一个写 操作节点与当前写操作节点不同，则更新过程与发生写缺失时相同。

(c)基于读缺失的历史信息更新方法

利用权利要求3(a)的“签名”信息回收技术，本发明实现了基于读操作的节点预测Cache历史信息 更新方法，其特征在于包括以下步骤：

读缺失内核的数据状态变化为I→E时，数据从下一级存储器中取入，SHV信息不存在，无须更新NPC。

读缺失内核的数据状态变化为I→S，且数据由片上处于E状态节点提供时，SHV信息不存在，无须更 新NPC。

读缺失内核的数据状态变化为I→S，且数据由片上处于M或S状态节点提供时，SHV信息已经存在， NPC更新过程的特征在于包括以下步骤：

●当读缺失节点NPC命中时，上一个写操作节点利用自身存储的SHV信息和当前“签名”信息进 行两次过滤操作，生成最终需要更新的历史共享节点信息，并根据该最终SHV进行NPC的更新。

●更新NPC时，检查更新前后历史共享节点与其预测节点间的距离变化情况，只在距离缩短的情况 下才更新历史共享节点NPC中存储的CNP指针。

●当读缺失节点NPC不命中或命中但预测错误时，除需要全局目录转发请求外，更新过程与NPC 命中相同。

如果LWP指向的上一个写操作节点中读缺失数据副本和对应SHV信息已经被替换出去，则本次NPC 更新终止。

下面结合附图1至15和具体的实施例对本发明做进一步详细描述。

对于本发明所提出的用于多核处理器的一致性维护装置及一致性交互方法，如无特别说明，后文均基 于规模为4的节点、MESI数据状态转换协议和Inclusive两级Cache层次关系结合附图进行实例详细说明。

本发明所提出的一致性维护装置是为了保持CMP处理器的存储系统一致性而设计的。因此，为了能够 清楚的说明本发明的技术方案，首先对CMP处理器的存储系统结构作说明。如图1和图3所示，本发明所 基于的CMP处理器的存储系统具有以下特征：

片上网络(Network on Chip，NoC)是CMP处理器广泛使用的内核互联方式，NOC以阵列的方式将多 个同一尺寸内核连接起来。本发明基于2-D MESHNOC互连和MESI状态转换协议进行说明；

所有内核私有L1 Cache，共享L2 Cache和主存；

共享L2 Cache以多个片段的方式分布在所有内核中，整个L2 Cache在物理上分布放置。

片上两级Cache间采用Inclusive模式。因此，目录用来维护一个共享的L2 Cache与多个私有L1 Cache 之间的数据一致性。

目录跟踪每个L1 Cache数据块的状态。目录和关联的一致性控制器也与它们控制的私有L1 Cache和共 享L2 Cache片段在片上分布放置。

本发明提供的用于多核处理器的一致性维护装置包括如下功能部件：

●全局目录(Global Directory)，以粗向量的方式跟踪数据所在节点；

●节点目录(Node Directory)，负责在节点内跟踪数据副本所在的内核位置；节点目录片段，负责 在节点内跟踪数据副本所在的内核位置；一个节点内的所有节点目录片段构成该节点完整的节点 目录；

●目录控制器，包括节点目录控制器和全局目录控制器，用于接收、发送一致性交互消息，控制两 级目录维护数据一致性。

●节点预测Cache-NPC(Node Predicting Cache)，用于保存距离请求内核节点最近的有效目标数据 副本节点，为发生缺失时的直接访问提供历史信息依据；

●节点共享历史信息Cache-SHC(Sharing History Cache)，用于保存节点对数据的共享历史向量， 为节点预测Cache的更新提供历史信息依据；

●节点挂起指针-NHP(Node Hanging Pointer)，用于在读缺失过程中暂存读缺失节点指针，为隐藏 目录访问延迟提供支持；

●最后写节点指针-LWP(Last Writer Pointer)，用于在基于读缺失的NPC更新过程中指明SHV向 量所在节点位置。当数据处于S态，并且该S态是从M态转换而来时，存有SHV信息的上一个 写操作节点已经“淹没”在多个S态节点中，导致无法定位SHV信息的位置。本发明为全局目录增 加一个LWP指针来跟踪上一个写操作节点。

本发明一致性维护装置所包含的多个功能部件的连接关系如图15所示：

(1)处理器内核与私有L1 Cache的连接用于访存指令的数据访问；

(2)私有L1 Cache与节点目录控制器之间的连接用于在L1 Cache缺失时传送缺失数据地址、访问节点目 录片段、跟踪L1 Cache中的数据副本状况；

(3)节点目录控制器与多个节点目录片段的连接用与控制节点目录对L1 Cache中数据的跟踪；

(4)节点目录控制器与节点预测Cache间的连接用与数据在本节点内所有L1 Cache中均未命中时，获取 有效数据所在的最近节点的指针，根据该指针能够进行直接数据访问；

(5)节点目录控制器与路由器之间的连接用于传送与节点内其它内核的节点目录片段交互的控制信号、 接收发送SHV信息、来自全局目录的共享向量和更新NPC的信息等；

(6)节点目录控制器与节点共享历史信息Cache-SHC之间的连接用于在发生写操作时传送来自其它节点 的SHV信息和当前全局目录向量；

(7)节点目录控制器与本内核全局目录控制器之间的连接用于传送当前全局目录向量；

(8)私有L1 Cache与共享L2 Cache片段之间的连接用于L1 Cache缺失时访问共享L2 Cache；

(9)L2 Cache片段与路由器之间的连接用于访问其它共享L2 Cache片段或者在共享L2 Cache缺失时访 问主存；

(10)L2 Cache片段与全局目录控制器之间的连接用于传送缺失数据地址、访问全局目录、跟踪L2 Cache 片段中的数据副本状况；

(11)全局目录与全局目录控制器之间的连接用于控制全局目录对L2 Cache片段中数据的跟踪；

(12)全局目录控制器与路由器之间的连接用于传送与其它节点的节点目录连接的一致性交互的控制信 号、缺失时提供的全局目录信息和更新NPC时需要的当前目录向量。

基于本发明提供的一致性维护装置，本发明还提供了一致性维护方法，具体实施方式包括以下步骤：

(1)读缺失一致性交互

(a)为每个节点目录片段(NDS)增加一个节点挂起指针NHP(Node Hanging Pointer)，在全局目录加 入读缺失节点信息前在数据提供节点中临时保留读缺失节点的“踪迹”，该“踪迹”的存在是数据提供节点发送 请求数据的前提条件。如图5(a)，设节点A中某内核缓存了节点B请求的数据D副本，节点挂起的具体 步骤包括：

●当节点A收到来自节点B的数据请求时，则将对应NDS关联的NHP指向节点B(挂起节点B)；

●然后向节点B发送数据D的同时也向全局目录发送目录更新请求；

●全局目录收到请求并加入节点B信息后返回一个确认消息；

●节点A收到该确认消息后清除对应NHP指针，节点挂起过程结束；

●节点挂起只针对来自读缺失节点的数据请求，对于来自全局目录的请求不予挂起。

(b)由于全局目录收到节点A的目录更新请求前并没有被锁定，仍可能处理其它写操作。如果这时产 生了一个对该请求数据的写操作，则利用节点挂起指针进行作废操作。如图5(b)所示，具体步骤包括：

●由于节点A存有请求数据副本，节点A会收到来自全局目录的作废消息；

●节点A在作废节点内数据副本的同时根据相应NHP的内容也向节点B转发该作废消息；

●节点B作废掉刚得到的数据副本后向节点A返回作废确认消息；

●节点A收到来自节点B的作废确认后向全局目录发送作废确认消息，至此写作废过程结束。

(c)如图6，当内核发生读缺失时，一致性交互包括如下具体步骤：

●发生读缺失的节点B内核根据缺失数据地址按照权利要求(1)(c)的两步目录访问方案访问节点B 目录；

●如果在节点目录命中，则访问节点B中内核，并更新节点目录；

●如果节点目录不命中，则查找节点B内对应NPC的预测信息，如果NPC不命中，则按照图13 中3-hops读操作流程访问全局目录，由全局目录通知缓存有效数据副本的节点向请求内核发送数 据，请求内核收到数据后根据数据地址更新相应的NDS，同时全局目录加入节点B共享信息。

●如果NPC命中，则根据CNP向预测节点A发出读数据请求。节点A按照两步目录访问方案访问 节点内目录；

●如果节点A内目录不命中则节点A将该请求转发至该请求数据的全局目录，剩余流程与3-hops 读操作相同；

●如果在节点A内目录命中，则按照图5的节点挂起流程进行处理。

(d)当片上Cache中不存在被请求数据副本时访问主存获得数据。

(2)写缺失一致性交互

(a)当写缺失数据处于M、E状态，NPC命中，且对应CNP预测正确时，能将写缺失一致性交互过程 缩短为2-hops。当NPC不命中时，按照3-hops流程处理。如图7，包括如下具体步骤：

●写缺失内核同时向全局目录和NPC预测节点发出两个访问请求；

●发往全局目录的请求查询到数据D状态为M或E后，全局目录忽略该请求，如图7中的1a消息；

●根据NPC中CNP预测发出的请求在预测正确的情况下将直接作废掉处于M或E状态的唯一数据 D副本，实现了2-hops写缺失一致性交互，如图7(a)；

●在NPC中CNP预测错误的情况下请求将被错误预测节点转发到全局目录进行处理，整个过程为 4-hops交互，错误预测代价为1-hops，如图7(b)。

(b)对处于S状态的写缺失数据仍维持4-hops交互，只是交互过程稍有不同。如图8，包括如下具体步 骤：

●对于状态为S的写缺失数据，写缺失内核也同时向全局目录和NPC预测节点发出两个访问请求；

●发往全局目录的请求查询到数据D的状态为S后，继续按照图14中4-hops交互流程处理；

●发往NPC预测节点的请求在预测正确的情况下将查询到数据D的状态为S，此后该数据D共享 节点将忽略该请求，如图8(a)中1b消息。

●在NPC预测错误的情况下，请求将被错误预测节点转发到全局目录，而全局目录将忽略该转发的 请求，如图8(b)中2c消息。

(c)对处于I状态的写缺失数据将从下一级存储器先读入数据，再进行修改。

(d)在写命中的情况下，仍需访问全局目录将其它副本作废。

(3)替换

(a)替换处于M或E状态的数据时，包括如下具体步骤：

●当被替换的数据处于M或E状态时，片上只存在唯一数据副本，发生替换的内核先发送消息剔除 该数据所在节点目录中的内核信息和全局目录中对应的节点信息；

●发生替换的内核收到确认消息后进行替换操作；

●M状态数据替换前还需要写回主存。

(b)替换处于S状态的数据时，根据节点中被替换数据的副本数量分为两种情况。包括如下具体步骤：

●第一种情况，所在的节点中只存在唯一副本，替换过程与E状态类似；

●第二种情况，所在的节点中存在多个副本。只需要通知节点目录剔除发生替换操作的内核信息后 进行替换，而无需通知全局目录。

(c)替换操作可能引起NPC预测访问的扑空。在读、写缺失时，该类扑空均按照NPC预测错误处理。

基于本发明提供的一致性维护装置，本发明还为一致性维护方法配套提供了历史信息更新算法，具体 实施方式包括以下步骤：

(1)基于读缺失的NPC更新

当发生读缺失时，新出现的数据共享节点将缩短部分历史共享节点与有效数据副本节点的最小距离， 而另一部分则保持不变。本发明只对前者的NPC内容进行精确更新，不会发出多余的更新消息，保证更新 后历史共享节点与其预测节点间的距离小于其与所有当前数据共享节点间的距离。如图9，根据读缺失内核 的两种数据状态变化：I→E和I→S，NPC更新包括以下具体步骤：

(a)当读缺失内核的数据状态变化为I→E时，数据从下一级存储器中取入，SHV信息还未生成，无须更 新NPC；

(b)当读缺失内核的数据状态变化为I→S时，如果数据由片上处于E状态节点提供时，SHV信息不存 在，也无须更新NPC；

(c)当读缺失内核的数据状态变化为I→S时，如果数据由片上处于M或S状态(该S状态由M状态，而 非E状态转换而来)节点提供时，SHV信息已经存在，故本发明只对该情况下发生的读缺失进行NPC更新， 包括以下具体步骤：

●如图9(a)，当读缺失节点NPC命中时，全局目录向数据提供节点发出目录更新确认消息的同时也 将GDV信息发送到LWP指向的OldWriter节点，在那里将进行两次过滤操作；

●第一次过滤先用GDV与SHV信息进行“AND”操作，再将结果与SHV信息进行“XOR”操作，过 滤掉当前已经缓存数据副本的历史共享节点；

●第二次过滤对SHV指向的历史共享节点与数据提供节点和读缺失节点之间的距离进行计算，过滤 掉所有与读缺失节点间距离大于与数据提供节点间距离的历史共享节点。节点间距离的计算方法 如下：对于一个有2ⁿ×2ⁿ个节点的2-D MESH CMP来说，需要2n位二进制数对节点进行编码。编 码的高n位指明节点位于哪一行，低n位指明节点位于哪一列。设节点A和B的编码分别为 a_2n-1a_2n-2...a₁a₀和b_2n-1b_2n-2...b₁b₀，则节点A与B之间的距离为|b_2n-1b_2n-2...b_n- a_2n-1a_2n-2...a_n|+| b_n-1b_n-2...b₀-a_n-1a_n-2...a₀|；

●这两次过滤操作可并行进行，最后将两次过滤的结果进行“AND”操作生成最终需要更新的历史共 享节点信息，如图9(a)；

●OldWriter节点(上一个写操作节点)根据该最终SHV进行NPC的更新。更新时OldWriter节点 将读缺失节点编码发送到需要更新的历史共享节点中；

●历史共享节点节点收到更新消息后用读缺失节点编码与自身NPC中存储的CNP节点编码做距离 比较。如果读缺失节点与历史共享节点间的距离小于CNP节点与历史共享节点间的距离，则用读 缺失节点编码更新历史共享节点NPC中存储的CNP指针，否则，保持原CNP内容不变。如图9(b) 中，假设S状态节点S1是距离读缺失节点R最近的有效数据节点，则所有深色区域节点与R节 点的距离均小于与S1节点的距离，所有位于深色区域且未缓存读缺失数据副本的HS节点都应更 新其NPC信息，如HS3(CNP＝S2)、HS4(CNP＝S1)和HS5(CNP＝S1)。更新时发现HS3虽 然位于深色区域，但HS3与其存储的CNP指向的S2节点间距离仍小于HS3与R间的距离，故 保持HS3节点原先存储的CNP不变；

●当读缺失节点NPC不命中或命中但预测错误时，全局目录响应请求并通知距离读缺失节点最近的 有效数据副本节点发送数据。数据发送节点向全局目录返回确认消息后，全局目录根据LWP向 OldWriter节点发送GDV，并开始与NPC命中相同的更新过程；

●如果LWP指向的OldWriter节点中读缺失数据副本和对应SHV信息已经被替换出去，则本次NPC 更新终止；

●如果LWP为空，当前读缺失数据处于S状态，这说明该S是由E状态转换而来，SHV信息不存 在，本次NPC更新终止。

(2)基于写操作的NPC更新

(a)如图10(a)(b)，当数据D处于M状态时，NPC更新包括以下具体步骤：

●OldWriter节点在收到NewWriter节点(当前写缺失节点)的请求后，作废自身数据D副本并在本 节点对应NPC中分配空间，将CNP指向NewWriter节点；

●接着根据OldWriter节点对应SHC中的SHV信息更新历史共享节点，将它们的数据D CNP信息 更新为NewWriter节点；

●OldWriter节点将SHV信息传递给NewWriter节点；

●NewWriter节点将收到来自全局目录的数据D当前共享信息GDV(Global Directory Vector)和来 自OldWriter节点的SHV信息，NewWriter节点将这两者做“OR”操作，将结果作为新的SHV存储 在节点SHC中。

(b)如图10(c)，当数据D处于S状态时，NPC更新包括以下具体步骤：

●当数据D处于S状态时，NPC的更新流程与M状态时类似。不同的是，在有多个S状态节点时， 需要这些S状态节点同时访问自身的SHC，并从发生命中的OldWriter节点中取出SHV送往 NewWriter节点；

●如果所有S状态节点的SHC均未命中，说明OldWriter节点中所有数据D副本和对应SHV已经 被替换出L1 Cache和SHC，这时则不用向NewWriter节点发送SHV；

●NewWriter节点直接将收到的GDV作为新的SHV信息；

●S状态时如果CNP预测错误，由错误节点转发的请求不会被全局目录响应，因此NPC更新流程 与CNP预测正确时相同。

(c)当数据D处于E状态时，NPC更新包括以下具体步骤：

●当数据D处于E状态时，数据D的SHV信息没有生成，如果这时发生数据D写操作，缓存数据 D唯一副本的节点收到NewWriter节点的请求后不用进行历史共享节点的NPC更新，也不用进行 自身SHV信息的传递。

●数据副本所在节点只需作废自身数据D副本并在本节点对应NPC中分配空间，将CNP指向 NewWriter节点即可；

●NewWriter节点只会收到来自数据D全局目录的GDV信息，并直接将其作为新的SHV信息。

(d)发生写命中时，如果上一个写操作节点与当前写操作节点相同，则无需更新历史信息。如果上一个 写操作节点与当前写操作节点不同，则更新过程与发生写缺失时相同。

(3)NPC更新时的CNP与SHV

(a)当一个数据D副本存在于某节点的L1 Cache中时，该节点对应的NPC中无需保存该数据的CNP 信息，因为其本身就是该有效数据的最近节点；

(b)只有当节点中所有数据D副本都被作废掉(替换操作不分配CNP)时才在NPC中为数据D分配 CNP指针，这样能提升NPC空间的利用率；

(c)对数据D来说，其对应SHV信息在数据D发生第一个写操作时首次出现，并随后续写操作节点传 递；

(d)当发生替换操作，并且被替换数据与其对应SHV信息位于同一内核时，SHV信息也从SHC中被替 换；

(e)对L1 Cache进行替换操作时，优先替换那些没有在SHC中缓存对应SHV信息的数据。

以上实施方式仅用于说明本发明，而非对本发明的限制，相关技术领域的科研人员，在不脱离本发明 精神和范围的情况下，还可以做出各种变化和变型，因此，所有等同的技术方案也属于本发明的范畴，本 发明的专利保护范围应由权力要求限定。