基于多级一致性协议的多核处理器WCET分析方法

朱怡安 史先琛 姚 烨 李 联 任鹏远 董威振 李佳钰

1 （西北工业大学计算机学院 西安 710072）

2 （西北工业大学软件学院 西安 710072）

3 （西北工业大学伦敦玛丽女王大学工程学院 西安 710072） （zhuya@nwpu.edu.cn）

嵌入式实时系统广泛存在于生产和生活当中，例如航空航天、轨道交通、无人驾驶、互联通信等.在实时系统中，其正确性不仅仅依赖于逻辑结果的正确性，同时还依赖于结果产生的时间[1].实时系统中的任务执行时间具有严格的约束，如果错过任务截止时间将会导致灾难性后果.因此，实时系统在任务调度设计和可调度性分析时都必须保证任务的执行在一个安全的时间上界之内，此上界的计算方法即任务的最坏情况执行时间（worst-case execution time，WCET）分析.当前主流的WCET分析方法分为静态分析和动态分析，动态分析也称为基于测试的分析方法，通过大量的测试用例来获取精确的WCET分析结果，由于无法穷尽所有的测试用例，动态分析无法保证分析结果的安全性，工业界通常会在分析结果的基础上增加一定的裕量（例如20%）[2]作为最终的WCET分析结果.静态分析方法则是通过对处理器硬件结构和程序流信息进行分析估算程序的WCET值，静态分析方法能够保证分析结果的安全性，并且不需要运行程序便可获得WCET结果，所以大多数WCET分析工具都采用静态分析方法.单核处理器WCET分析方法经过多年的研究已经取得较高的分析精度，然而多核处理器中加速部件的使用和共享资源干扰的存在，导致原有的单核处理器WCET分析方法无法直接适用于多核处理器，这对于多核处理器的WCET分析提出了新的挑战.

在硬件结构方面，多核处理器的WCET分析主要考虑Cache、内存、核间互联和流水线等部件的影响[3]，Rapita Systems公司的实验表明，由于 L3 Cache的争用导致YOLO算法的帧率降低90%左右.当前对于Cache的研究主要集中在指令Cache带来的干扰分析[4-7]，并已经获得了较高的分析精度，而对于数据Cache的关注则不足，其原因有2方面：1）处理器寻址方式的不同导致数据Cache的访问地址分析更加困难；2）数据Cache在循环的不同轮次中访问的数据不同，正是由于数据Cache和指令Cache在时空特性上的差异，造成数据Cache的分析更加复杂.如果简单将指令Cache的分析技术套用到数据Cache上，会导致分析结果过于悲观[8].对于数据Cache的分析除了以上问题之外，另一个需要特别关注的影响因素就是数据一致性协议.有研究表明，由于Cache一致性协议的影响，并行程序执行比串行程序慢74%[9].但是相关的调研表明[10]，极少数研究人员关注Cache一致性造成的干扰.

针对现有多核处理器WCET分析方法对数据Cache一致性协议考虑不足的问题，本文主要研究一种基于多级一致性协议的多核处理器WCET分析方法.该方法通过建立多级一致性域，抽象出一致性协议嵌套的共享数据管理机制，分别从一致性域内部、跨一致性域2个层面来分析内存访问延迟，从而实现对多核处理器中数据Cache的精确分析.

1 相关工作

Ferdinand等人[11]提出基于抽象解释理论[12]的Cache行为分析方法，由于其具有较高的精确度和效率，在基于Cache的WCET分析中占据了统治地位[8].如图1所示，基于抽象解释的Cache分析方法对Cache的物理状态和替换策略进行抽象，得到抽象缓存状态（abstract cache state）和函数Join、函数Update，通过May分析、Must分析和Persistence分析3种方法得出 Cache的“Cache命中/失效分类”（cache hit miss classification, CHMC），从而确定 Cache 的访问延迟.Huynh等人[13]经过分析证明了原有的Persistence分析方法存在不安全性，其原因在于更新函数未将可能被替换出去的内存块的年龄进行增加，导致分析结果不正确.为解决此问题，该小组提出Younger Set的概念，并将Younger Set引入到函数Join和函数Update中，保证了Persistence分析的安全性.在过去的20多年，研究人员对Persistence分析进行了广泛的研究，仍然不能保证其发现所有的 Persistent Cache块，直到 Stock[14]给出Exact Persistence分析方法，才使得Persistence分析趋于完善.

Fig.1 Cache analysis based on abstract interpretation图1 基于抽象解释的Cache分析方法

模型检测[15]方法是另一个广泛研究的Cache行为分析方法，模型检测作为实时系统中常用的时序验证手段，将各类时序分析问题转化为时间自动机的可达性问题，从而实现对问题的求解.Wilhelm[16]讨论了模型检测技术在WCET分析中的优缺点，Metzner[17]认为模型检测方法能够提高分析结果的精度.Dalsgaard等人[18]基于模型检测方法实现了模块化任务执行时间分析框架；Gustavsson等人[19]的研究表明，UPPAAL可以用于多核处理器中并行任务的WCET分析，Cassez等人[20]将WCET分析问题转换为寻找最长路径的问题，并通过扩展模型检测工具UPPAAL实现了一个任务WCET分析工具WUPPAAL；Lü等人[21]在开源工具Chronos的基础上，将模型检测的方法用于Cache的行为分析，实现了一个多核处理器WCET分析工具McAiT；陈芳园等人[22]改进多核处理器中Cache冲突分析方法，在取指阶段考虑取指操作之间的时序关系，该方法能够排除部分非干扰状态，使得WCET计算精度最高提高12%.上述对于Cache行为分析多是针对指令Cache展开的，而对于数据Cache的分析研究较少，尤其是对于多核处理器中Cache一致性协议的讨论更为少见.直到2015年，Uhrig等人[23]研究数据Cache对多核处理器WCET分析的影响，并研究了基于监听的一致性协议和TDMA总线对多核处理器中延迟时间的影响，最终得出结论：采用写失效的基于总线监听的一致性协议不具备可预测性，而采用写更新双通道直接映射的bus-snarfing一致性协议配合TDMA总线能够实现时间可预测.但文献[23]未对Cache一致性协议带来的内存访问延迟进行更为细致的分析.而Hassan等人[24]的分析也得出了基于总线监听MSI一致性协议配合TDMA总线的多核处理器的WCET值不具有可预测性，重点分析了TDMA总线导致的不可预测性，而对于多核处理器中基于MESI一致性协议的WCET估计，同样未给出详细的分析方法.Tsoupidi[25]针对对称多处理器，提出一种考虑Cache一致性协议的WCET分析方法，该方法在计算共享Cache读访问延迟时认为上述情况仅发生在Cache使用写回（write-back）策略时，对于写直达（writethrough）策略，数据同时存在于私有Cache和共享Cache中，该计算方式存在较大的悲观性，且该文仅仅讨论了单级一致性协议下的WCET分析方法，而对于多核处理器中存在多级Cache一致性协议的情况，尚未见到相关的研究.

为此，本文针对数据Cache中共享数据的访问，提出了基于多级一致性协议的多核处理器WCET分析方法，解决多级一致性协议嵌套情况下的WCET分析问题，完善了多核处理器Cache的分析框架，并实 现 一 个 基于 MESI（modify exclusive shared invalid）协议的高精度多核处理器WCET分析工具，为多核实时系统的WCET分析提供了支撑.

2 基于MESI协议的跨一致性域WCET分析方法

本节的核心工作在于提出一种多级一致性域的WCET分析方法，实现对多核处理器中多级一致性域的WCET分析.通过对一致性域内部的Cache访问延迟和状态转换情况进行分析，得出一致性域内部的分析结果，根据是否进行跨域数据访问决定下一步是否需要进行跨域分析，从而实现一致性协议嵌套情况下的共享数据访问延迟分析.本文将该方法与当前主要考虑指令Cache的分析方法相结合，增加了数据Cache中共享数据的访问分析，扩展了多核处理器中Cache的干扰分析框架，进一步完善了多核处理器WCET分析方法.

2.1 Cache组织结构

共享存储结构是当前应用最为广泛的多核处理器架构，此种结构对于每一个内核而言都是对等的，每一个内核的访问时间都是相同的，因此多核处理器属于对称多处理器（symmetric multi-processor，SMP）.最初的多核处理器中只存在私有Cache和共享Cache，随着CPU制造工艺的发展，当前多核处理器已集成多级Cache.

采用SMP架构的多处理器需要支持共享数据的Cache，通过读写共享数据实现内核之间的通信.在缓存共享数据时，可能会存在多个内核对共享数据的争用，也可能会在多个Cache中复制共享数据，导致多个数据副本不一致，因此共享数据Cache引入了一个新的问题——Cache一致性问题，需要引入一致性协议保证数据一致性.

MESI是一种典型的Cache一致性协议，也被称为Illinois MESI协议，是在原MSI协议的基础上引入E状态，用于表示独占状态.在写入一个共享数据块时，通常有2种写策略：写直达和写回.对于图2所示的多级Cache组织结构，由于写回策略对存储器的带宽要求低，能够支持更多、更快速的处理器，所以最外层级别（簇（cluster）间）通常采用写回策略[3]；而对于簇内的写入共享数据的策略，如果采用写回策略，会造成簇内L1 Cache中数据和L2 Cache中的数据不一致的情况，在维护簇内数据一致性的同时，还要考虑簇间一致性，造成一致性协议非常复杂，不利于硬件的实现，因此簇内采用写直达的策略.

Fig.2 Multi-level Cache arrangement图2 多级Cache组织结构

写直达和写回适用于访问命中的情况，当访问缺失时所采用的写策略为写分配（write allocation）和非写分配（no write allocation）两种方式，通常写回与写分配策略配合使用，写直达和非写分配策略配合使用.

2.2 一致性域

多核处理器任务调度时存在多个内核共同完成一个任务，或者将某些关键等级高的任务映射到特定的内核上，因此，这些任务之间的数据交换仅仅在特定内核之间进行，如果使用一个一致性协议维护所有内核的数据副本，将会产生大量的数据交互操作，造成网络拥塞，降低执行效率, 一种可行的方法是将所有的内核进行区域划分[26]，每个区域使用独立的一致性协议管理数据副本，该方法既能充分利用局部性原理，又能降低网络负载.

定义1.一致性域.使用相同一致性协议管理数据副本的内核集合，称之为一致性域.

一致性域的示意图如图3所示.

一致性域具有2个性质：

性质1.一致性域具有独立性，即任意2个一致性域之间不存在交集.

性质2.一致性协议在一致性域内具有唯一性.

Fig.3 Coherence domain图3 一致性域

2.3 多级一致性域

由于一致性协议只能维护域内数据的一致性，当存在跨域数据交互时，会导致无法保证域间数据的一致性，需要使用多级一致性协议进行数据维护，相应地，需要定义多级一致性域.多级一致性域采用分层划域的思想，下层一致性域是上层一致性域的一个结点（clump）.

针对如图2所示的硬件架构，根据一致性域的定义，簇内为1级一致性域，整个多核处理器构成2级一致性域.处理器内核在访问数据时，首先会访问私有Cache，如果访问缺失，则会访问下一级共享Cache，即簇内共享Cache，此时数据访问范围仍在一致性域内.如果访问命中，只需进行域内WCET分析即可；如果访问缺失，根据存储器层次结构访问次序，则需要进行跨一致性域WCET分析.

2.4 关键参数说明

在进行多核处理器的Cache行为分析时，假设总线是完美的并且不存在读和写队列的限制，在此基础上分析Cache一致性协议对内存访问时间的影响.

首先假设处理器拥有私有Cache、共享Cache和内存，Cache采用写回和写分配策略，Cache的访问分为读和写，读和写都会出现访问命中或缺失，我们从读和写2个方面对Cache行为进行分析，在开始分析之前定义如下符号：

1） ψR(m,m′)/ψW(m,m′).表示域内 Cache 读/写访问时间延迟和状态转换情况，m表示被访问的数据，m'表示被访问数据的副本.

2）HLi.表示在第i级Cache访问命中时间延迟.

3）LLi→Lj.表示数据从第i级Cache加载到第j级Cache的时间延迟.

4）Hmemory.表示主存访问命中时间延迟.

5）Inv/Inv′.表示 域内/跨 域使其 他数据副本 失效的时间延迟.

6） ψ′R(m,m′)/ψ′W(m,m′).表示跨域 Cache 读/写访问时间延迟和状态转换情况.

7）ms/m′s.表示本地/远程Cache状态.

8） Replacement /¬ Replacement.表示被访问共享数据被替换出Cache，导致替换缺失发生/未发生.

2.5 考虑一致性协议的WCET分析框架

现有工作对于Cache的分析主要集中在指令Cache，对于数据Cache的分析也仅限于本地数据的分析.本文在基于抽象解释的多级Cache分析框架基础上，扩展了共享数据分析这一功能.

如图4所示，该分析框架的输入为待分析程序和Cache模型.其中待分析程序提供控制流、地址信息，Cache模型中包括了Cache组织结构、替换策略、读写策略以及一致性协议，这些参数作为分析框架的输入信息，提供给Cache分析方法.Cache的分析可分为2部分：数据Cache和指令Cache，其中数据Cache中共享数据的分析为本文的主要工作，将在后文中详细介绍.最后，根据分析结果得出内存访问的分类以及访问的时间延迟，从而得出WCET的分析结果.

Fig.4 WCET analysis framework based on coherence protocol图4 基于一致性协议的WCET分析框架

2.6 域内WCET分析

2.6.1 域内读访问

当内核发出读数据m的读请求时，如果m存在于L1中，其状态可能为E或者S并且未发生替换缺失，在L1中能够读命中，数据访问延迟为HL1，所有Cache块的状态不会发生改变.

如果数据m在域内，m的状态为E或者S但是发生替换缺失，此时数据访问延迟为读取L2中数据的时间，同时需要将数据从L2 Cache加载到本地L1 Cache中，考虑连贯性要求，数据访问延迟为max(,LL2→L1)，Cache状态不发生变化，如图5 (a)(b)所示.

如果数据m在域内，m的状态为I，且副本m'的状态为E或者S时，此时数据访问延迟为读取L2中数据的时间，同时需要将数据从L2 Cache加载到本地L1 Cache中，考虑连贯性要求，数据访问延迟为max(,LL2→L1)，m的状态转换为S，副本m'的状态转换为 S，如图5 (c)所示.

如果数据m不在域内，在L2 Cache中会出现访问缺失，假定访问L2 Cache的时间为对于的取值我们将在2.7.1节中进行分析.此时m的状态由I转换为E，L2 Cache的状态需要根据L2的一致性协议进一步分析，如图5(d)所示.

根据以上分析，可以得出Cache域内读访问时间延迟和状态转换的状态更新函数：

2.6.2 域内写访问

当内核发出写m的请求时，如果m仅存在本地L1 Cache且状态为E时，此时会发生Cache写命中.首先需要将数据写入到L1中，由于使用写直达策略，需要同时写入到L2当中，因此数据访问时间为HL1+，Cache状态不发生改变，如图6(a)所示；如果m存在于L1 Cache中且状态为S时，此时会发生Cache写命中，数据访问延迟为HL1+，状态转换为E，由于采用写失效的一致性协议，因此需要将副本的状态修改为I，考虑连贯性要求，数据访问最终的延迟为 m ax(HL1+,Inv)，如图6(b)所示.

如果数据m位于本地L1 Cache中，m的状态为E或者S，并且发生替换缺失，此时会出现写缺失.如果m的状态为E，此时数据访问时间为，并且状态转换为I，如图6(c)所示；如果m的状态为S，在进行L2 Cache写操作之后，需要对其他副本进行写失效，所以访问时间为 m ax(ψ′W,Inv)，m和副本m'的状态都转换为I，如图6(d)所示.

Fig.5 Read-visit latency and state transition diagram of intra-domain图5 域内读访问时间延迟及状态转换图

Fig.6 Write-visit latency and state transition diagram of intra-domain图6 域内写访问时间延迟及状态转换图

如果数据m在域内,m的状态为I且副本m'的状态为E或者S时，此时会对L2进行写操作, 并将其他副本中的数据写失效, 考虑数据连贯性要求, 数据的写延迟为 m ax(ψ′W,Inv), 由于采用非写分配的方式, 本地L1的状态不发生改变，其他副本的状态从E/S转换为 I, 如图6(e)所示.

如果数据m不在域内，类比读访问的情况，假定写L2 Cache的访问时间为.由于域内采用非写分配法，所以此时m的状态不发生任何变化，如图6(f)所示.

根据以上分析，可以得出Cache域内写访问时间延迟和状态转换的状态更新函数：

2.7 跨域WCET分析

2.7.1 跨域读访问

当内核发出读数据m的读请求时，如果需要对L2 Cache进行读访问，此时将会由上级一致性协议管理共享数据.

如果数据m存在于域内，并且位于本地L2 Cache中，对应域内读访问的图5(a)~(c)，此时数据访问时间为HL2，域间所有的Cache的状态都不发生变化，如图7(a)所示.

当被访问数据m存在于L2 Cache中并且发生替换缺失，对应域内读访问的图5(d)，此时数据访问延迟为HL3，同时需要将数据加载到L1 Cache中，考虑到连贯性要求，数据访问的延时为 m ax（HL3,LL3→L1），如果m的状态为M或者E，则状态会转换为E，如果m的状态为S，则状态不发生改变，副本m'的状态不发生改变，如图7(b)(c)所示.

如果被访问数据m不存在于域内，对应域内读访问的图5(d)，存在2种可能性：1）数据m本身不存在Cache中；2）数据m存在于其他域的Cache中.如果数据m不存在Cache中，此时需要通过内存来读取数据m，数据访问延迟为Hmemory，同时需要将数据从内存中写回到L1 Cache中，考虑连贯性要求，数据访问延迟为 m ax(Hmemory,Lm→L1)，L2的状态从I转换为E，如图7(d)所示.

如果数据存在于其他域中，即存在数据副本m'，如果其状态是M，首先要将数据从其他域的L2 Cache中加载到本地域的L2中，然后再加载到L1中，最后从L1中读取数据，其访问延迟为LL2→L2+LL2→L1+HL1，此时L2中数据m的状态从I转换为S，其他域L2中数据副本m'状态从M转换为S，如图7(e)所示.

如果数据副本m'的状态为E或者S，将会在L3中读取命中数据，此时数据访问延迟为HL3，与此同时，数据将会加载到L1中，考虑连贯性要求，此时数据访问延迟应取 m ax(HL3,LL3→L1)，此时L2中数据m的状态从I转换为S，其他域L2中数据副本m'状态换为S，如图7(f)所示.

根据以上分析，可以得出Cache跨域读访问时间和状态转换的状态更新函数：

2.7.2 跨域写访问

当内核发出写数据m的写请求时，如果需要对L2 Cache进行写访问，此时将由上级一致性协议管理共享数据.

如果数据m在域内（对应域内写访问图6(a)~(e)的情况），并且位于本地L2 Cache中，状态为S，需要将其他副本中的数据写失效，考虑连贯性要求，数据访问时间为 m ax(HL2,Inv′)，状态转换为M，副本的状态由S转换为I，如图8(a)所示；如果m的状态为M或者E，此时数据访问时间为HL2，状态转换为M，其他Cache状态不变，如图8(b)所示.

Fig.7 Read-visit latency and state transition diagram of cross-domain图7 跨域读访问时间延迟及状态转换图

如果被访问数据m不存在于域内（对应域内写访问图6(f)的情况）, 存在2种可能性：1）数据m本身不存在Cache中；2）数据m存在于其他域的Cache中.如果数据m不存在Cache中, 由于域间采用写分配，首先要将数据从内存加载到L2 Cache中, 然后在L2 Cache中修改数据, 此时数据访问延迟为HL2+Lm→L2，L2 Cache 的状态从 I转换为 M, 如图8(c)所示.

如果数据存在于其他域内，数据m的状态为I，如果数据副本m'的状态为M，首先要将数据从其他域加载到本地L2中，然后修改本地L2 Cache中的数据，状态转换为M，并且要将其他副本写失效，考虑连贯性要求，数据访问延迟为 m ax(HL2+LL2→L2,Inv′)，其他副本的状态转换为I，如图8(d)所示；如果副本的状态为E或者S，此时需要将数据从L3 Cache加载到本地L2 Cache中，状态转换为M，并且要将其他副本写失效，考虑连贯性要求，数据访问延迟为max(HL2+LL3→L2,Inv′)，副本的状态准换为I，如图8(e)所示.

如果m为M,E,S状态并且发生替换缺失时（对应域内写访问图6(f)的情况）, 此时会发生Cache写缺失.首先将数据从 L3 Cache 加载到 L2 Cache, 然后执行写操作.对于m的状态为M和E的情况, 此时数据访问延迟为HL2+LL3→L2,m的状态转换为M, 如图8(f)所示；如果m的状态为S, 需要将其他副本中的数据写失效, 考虑连贯性要求, 数据访问延迟为max(HL2+LL3→L2,Inv′),m的 状 态 由 S变 为 I, 如 图8(g)所 示.

根据以上分析，可以得出Cache跨域写访问时间和状态转换的状态更新函数：

Fig.8 Write latency and state diagram of cross-domain图8 跨域写访问时间延迟及状态转换图

3 实验评估

3.1 实验参数设置

本文在实验室原有多核处理器WCET分析工具的基础上，扩展其中数据Cache的分析方法，增加了对MESI一致性协议的支持，设计并实现了一个支持Cache一致性协议的多核处理器WCET分析工具Roban.通过该工具对多核处理器进行WCET分析，并将分析结果与GEM5仿真工具模拟执行得到的时间进行对比，从而验证分析方法的有效性.

实验针对4核处理器展开分析，每2个内核组成1簇，即2个1级一致性域和1个2级一致性域，处理器存储结构参照图2，关键参数配置如表1所示.从Mälardalen大学WCET研究小组测试用例集中选取典型测试用例进行测试.

Table 1 Parameters Configuration of Multi-Core Processor表1 多核处理器参数配置

3.2 实验结果与分析

实验一共分为2组，第1组Cache相联度为4路组相联，第2组Cache相联度为8路组相联.分别调整 L1，L2，L3 Cache的容量，得出在不同 Cache配置情况下的WCET值，结果如图9所示.

从图9可以看出, Roban工具得到的WCET分析结果均大于GEM5仿真得到的结果,证明了本文方法的安全性.

为了验证本文方法的有效性，采用Spearman相关性分析法对图9中Roban分析结果与GEM5仿真结果进行相关性分析，得出的相关性系数矩阵如图10所示，其中横坐标为Roban分析工具对应的测试结果，纵坐标表示GEM5仿真结果.从图10中可以看出，带有数字标签的矩阵元素为相同测试用例在不同Cache参数配置情况下得到WCET结果的相关性系数，相关性系数不小于0.98，说明Roban和GEM5两种工具得出的结果显著相关，同时表明了图9中的曲线变化趋势基本一致.

Fig.9 Comparison of GEM5 simulation results and analysis results图9 GEM5仿真结果与分析结果对比

Fig.10 Correlation coefficient matrix diagram of GEM5 and Roban图10 GEM5与Roban相关性系数矩阵图

为了验证本文提出分析方法的精确性，采用过估计率这一指标对分析结果进行评估，过估计率 R 计算方式为

过估计率的统计结果如图11所示.由图11可知，本文方法分析得出的过估计率最大值为1.476，最小值为1.158，平均值为1.30，对比瑞典皇家理工学院[25]设计实现的 WCET分析工具 KTA（KTH’s timing analysis），其平均过估计率为2.08，本文方法的过估计率降低了0.78.

Fig.11 Statistical results of over estimation rate图11 过估计率统计结果

4 结 论

本文通过分析多级一致性协议体系架构下的Cache状态转换和内存访问延迟，得出多级一致性域WCET分析方法.实验表明，本文方法能够精确估算出多核处理器任务WCET，在改变Cache配置参数的情况下，GEM5仿真结果与本文工具Roban分析结果相关性系数不低于0.98，表明本文方法分析结果的变化趋势与GEM5仿真结果一致；通过与当前分析方法进行对比，证明本文方法相比现有方法的过估计率降低了0.78.

本文在进行Cache行为分析时，将总线假设为理想状态，而在实际的一致性协议中，如果存在大量的数据交互，将会导致总线发生阻塞，在以后的工作中，应将Cache之间共享总线纳入到分析范围中，进一步提高WCET分析结果的准确性.另外本文在考虑一致性协议时仅考虑了MESI协议，而在实际工程领域存在多种一致性协议，如Intel i7使用的MESIF协议、AMD Opteron使用的MOESI协议等，在后续的工作中将针对不同的一致性协议展开分析.

作者贡献声明：朱怡安提出研究思路和指导意见；史先琛提出了算法并撰写论文；姚烨、李联负责实现算法并设计实验方案；任鹏远、董威振、李佳钰参与实验方案设计并整理实验数据.