由于多核处理器优越的计算性能，现已广泛应用在嵌入式实时系统中，相对单核处理器，多核处理器存在资源共享、并行任务干扰等因素，尤其是缓存一致性问题，导致任务最坏情况执行时间（worst case execution time）的预测更加困难。
提出基于多级一致性协议的多核处理器WCET分析方法，该方法针对多级一致性协议体系架构，首次提出多级一致性域的概念，将多核处理器的数据访问分为域内访问和跨域访问2个层次。
根据Cache读写策略和MESI（modify exclusive shared invalid）一致性协议，得出一致性域内部和跨一致性域的Cache状态更新函数，从而实现多级一致性协议嵌套情况下的WCET分析。
嵌入式实时系统广泛存在于生产和生活当中，例如航空航天、轨道交通、无人驾驶、互联通信等。
在实时系统中，其正确性不仅仅依赖于逻辑结果的正确性，同时还依赖于结果产生的世界。实时系统中的任务执行时间具有严格的约束，若错过任务截止时间，将导致灾难性结果。
所以，实时系统在任务调度设计和可调度性分析时都必须保证任务的执行在一个安全的时间上界之内，此上界的计算方法即任务的WCET分析，当前主流的WCET分析方法分为静态分析和动态分析。
- 动态分析也称为基于测试的分析方法，通过大量的测试用例来获取精确的WCET分析结果，由于无法穷尽所有的测试用例，动态分析无法保证分析结果的安全性，工业界通常会在分析结果的基础上增加一定的裕量（例如20%）作为最终的WCET分析结果。
- 静态分析方法则是通过对处理器硬件结构和程序流信息进行分析估算程序的WCET值，静态分析方法能够保证分析结果的安全性，并且不需要运行程序便可获得WCET结果，所以大多数WCET分析工具都采用静态分析方法，单核处理器WCET分析方法经过多年的研究已经取得较高的分析精度。多核处理器中的加速部件的使用和共享资源干扰的存在，导致原有的单核处理器WCET分析方法无法直接适用于多核处理器，这对多核处理器的WCET分析提出了新的挑战。
- 在硬件结构方面，多核处理器的WCET分析主要考虑Cache、内存、核间互联和流水线等部件的影响。由于L3 Cache的争用导致YOLO算法的帧率降低90%左右。
- 当前对于Cache的研究主要集中在指令Cache带来的干扰分析，并以及获得了较高的分析精度，而对于数据Cache的关注则不足。
- 处理器寻址方式的不同导致数据Cache的访问地址分析更加困难，数据Cache在循环的不同轮次中访问的数据不同。
- 正是由于数据Cache和指令Cache在时空特性上的差异，造成数据Cache的分析更加复杂。
- 如果简单将指令Cache的分析结果套用到数据Cache上，会导致分析结果过于悲观。
- 对于数据Cache，还需要考虑影响因素是数据一致性协议，由于Cache一致性协议的影响，并行程序执行比串行程序慢74%。
- 所以提出了基于多级一致性协议的多核处理器WCET分析方法。该方法通过建立多级一致性域，抽象出一致性嵌套的共享数据管理机制，分别从一致性域内部，跨一致性域2个层面来分析内存访问延迟，从而实现对多核处理器中数据Cache的精确分析。
- 模型检测方法是另一个广泛研究的Cache行为分析方法，模型检测作为实时系统中常用的时序验证手段，将各类时序分析问题转换为时间自动机的可达性问题，从而实现对问题的求解。
- 所以，针对数据Cache中共享数据的访问，提出了基于多级一致性协议嵌套情况下的WCET分析问题，完善了多核处理器Cache的分析框架，并实现一个基于MESI协议的高精度多核处理器WCET分析工具，为多核实时系统的WCET分析提供了支持。
基于MESI协议的跨一致性域WCET分析方法
本节的核心工作在于提出一种多级一致性域的WCET分析方法，实现对多核处理器中多级一致性域的WCET分析。通过对一致性域内部的Cache访问延迟和状态转换情况进行分析，得出一致性域内部的分析结果，根据是否进行跨域数据访问决定下一步是否需要进行跨域分析，从而实现一致性协议嵌套情况下的共享数据访问延迟分析。
Cache组织结构
- 共享存储结构是当前应用最为广泛的多核处理器架构，此种结构对于每一个内核而言都是对等的，每一个内核的访问时间都是相同的，因此多核处理器属于对称多处理器（symmetric multi-processor,SMP）.最初的多核处理器只存在私有Cache和共享Cache，但现在多核处理器已集成多级Cache。
- 采用SMP架构的多处理器需要支持共享数据的Cache，通过读写共享数据实现内核之间的通信。在缓存共享数据时，可能会存在多个内核对共享数据的争用，也可能会在多个Cache中复制共享数据，导致多个数据副本不一致，因此共享数据Cache引入了一个新的问题：Cache一致性问题，需要引入一致性协议保证数据一致性。
- MESI是一种典型的Cache一致性协议。在写入一个共享数据块时，通常有两种写策略：写直达（write through）和写回（write back）.
- 写直达（write through）：每次数据都要写入主内存里。写入前会判断数据是否已经在Cache里，如果数据在Cache里，先将Cache里的数据进行更新，再写入到主内存里面。如果数据不在Cache里，直接更新主内存即可。缺点：速度慢，无论数据是否在cache中，都需要把数据同步到主内存中。
- 写回（write back）：如果要写入的数据，就在CPU cache里面，那么只需要更新Cache里的数据，同时会标记Cache里的这个Block是脏（Dirty）的——Cache中Block的数据与内存中不一致。如果写入数据对应的Cache Block里存放的是别的内存地址的数据，就要判断此数据有没有被标记成脏的。如果是脏的，就要先把这个数据写入到内存中，然后更新Cache里的数据，再把Cache Block标记为脏的。
- 对于多级Cache组织结构，由于写回策略对存储器的宽带要求低，能够支持更多、更快速的处理器，所以最外层级别（簇间）通常采用写回策略；而对于簇内的写入共享数据策略，如果采用写回策略，会造成簇内L1 Cache中数据和L2 Cache中的数据不一致的情况，在维护簇内数据一致性的同时，还要考虑簇间一致性，造成一致性协议非常复杂，不利于硬件的实训，因此簇内采用写直达策略。
- 写直达和写回适用于访问命中的情况，当访问缺失时所采用的写策略是写分配和非写分配。
- 写回法与写分配策略配合使用，写直达和非写分配策略配合使用。
一致性域
- 多核处理器任务调度时存在多个内核共同完成一个任务，或者将某些高关键等级的任务映射到特定的内核上，因此，这些任务之间的数据交换仅仅在特定内核之间进行。
- 如果使用一个一致性协议维护所有内核的特定数据副本，将会产生大量的数据操作，造成网络拥塞，降低执行效率，一种可行的方法是将所有的内核进行区域划分，每个区域使用独立的一致性协议管理数据副本，该方法既能充分利用局部性原理，又能降低网络负载。
- 使用相同一致性协议管理数据副本的内核集合，称为一致性域。
- 一致性域具有独立性，即两个任意一致性域之间不存在交集。
- 一致性协议在一致性域内具有唯一性。
- 由于一致性协议只能维护域内数据的一致性，当存在跨域数据交互时，会导致无法保证域间数据的一致性，需要使用多级一致性协议进行数据维护。
- 多级一致性协议需要定义多级一致性域，多级一致性域采用分层划域的思想，下层一致性域是上层一致性域的一个结点。
- 簇内为1级一致性域，整个多核处理器构成2级一致性域。处理器内核在访问数据时，首先会访问私有Cache，如果访问缺失，会访问下一级共享Cache，即簇内共享Cache，此时数据访问范围仍在一致性域内，如果访问命中，只需进行域内WCET分析即可。如果访问缺失，根据存储器层次结构访问次序，需要进行跨一致性域WCET分析。
- 在进行多核处理器的Cache行为分析时，假设总线是完美的并且不存在读和写队列的限制，在此基础上分析缓存一致性协议对内存访问时间的影响。
- 首先假设处理器拥有私有Cache、共享Cache和内存，Cache采用写回和写分配策略，读和写都会出现访问命中或缺失。