集成电路工艺的开展使得芯片的集成度不断进步，一种新式体系结构——CMP(Chip Multiprocessor ——片上多处理器)应运而生，经过在一个芯片上集成多个微处理器中心来进步程序的并行性。多个微处理器中心能够并行地履行程序代码，具有较高的线程级并行。由于CMP选用了相对简略的单线程微处理器作为处理器中心，使得CMP具有高主频、规划和验证周期短、操控逻辑简略、扩展性好、易于完成、功耗低、子通讯推迟低一级长处。此外，CMP还能充分利用不同使用的指令级并行和线程级并行，成为处理器体系结构开展的一个首要趋势。
在CMP中，多个处理器中心对单一内存空间的同享使得处理器和主存储器之间的速度距离的对立愈加杰出，因而CMP规划有必要选用多级高速缓存Cache，经过层次化的存储结构来缓解这一对立。图1给出了同享内存的CMP体系模型。与惯例SMP体系相似，CMP体系有必要处理由此而引发的Cache一起性问题以及一起性验证问题。选用什么样的Cache一起性模型与它的验证办法都将对CMP的全体规划与开发发生重要影响。
从CMP中Cache一起性协议的验证技能的开展来看，现在使用比较广的验证办法有状况罗列法[1]、模型查验法[2][3]、符号状况模型法[4]三种。本文结合CMP的特色，树立了依据MESI一起性协议的CMP验证模型，并在此模型基础上剖析了这三种验证办法的基本原理，每一种办法的杂乱性剖析及优缺陷。
1 Cache一起性协议的建模
从本质上看Cache一起性协议是由一些进程组成的，这些进程包括Cache与内存操控器之间交流信息以及对处理器作业做出的反响。因而用有限状况机模型来描绘Cache一起性协议是一件很天然的作业。Cache一起性协议能够在三种不同的层次上树立验证建模。最高层次是对整个协议行为的笼统，中心层次是在体系/音讯传递一级进行笼统，最低层次则是在结构模型一级进行笼统，表1给出了这三个层次的笼统模型的特色[5]。
现在对Cache一起性协议验证研讨中，首要是对一起性协议在体系级进行模型笼统。这首要有三方面的原因：首要，在行为级的笼统中把一切的状况转化操作都看作是原子操作是不切合实践的。其次，在行为级层次上进行的验证实践效果不大。最终，由于体系杂乱性的急剧添加，在结构模型的层次上验证一个Cache一起性协议是不可行的。
在体系级上对Cache一起性协议进行验证具有相对适中的杂乱性。在这个层次上，能够经过有限状况机之间的音讯传递来描绘各个组件间的操作，加深对体系各个组件间相互效果的了解。此外，依据有限状况机的模型使得咱们能够使用层次性验证的办法。即首要在体系级的层次上验证协议的正确性，之后就能够进入到愈加初级的层次去验证详细的完成了。
2 Cache一起性协议的验证办法
2.1 体系模型
为了要点阐明验证办法原理，削减详细验证进程的杂乱性，本文所用的验证剖析模型由两个相同的处理器组成，每个处理器有一个Cache；每个Cache有一个Cache行，使用MESI一起性协议。Cache的有限状况机具有四个状况[6]：M：修正状况，E：独占状况，S：同享状况， I：无效状况。图2给出了验证模型，图3给出了MESI一起性协议的有限状况机。
应该指出，树立只需一个Cache行的体系模型关于大多数的Cache协议验证都是满意的。这是由于协议履行的粒度是Cache行。而关于履行粒度是word的Cache协议，就有必要树立起每一个Cache行有几个word的模型，可是验证的基本原理都是相同的。
2.2 状况罗列法(State Enumeration)
状况罗列法[1][7]研讨整个体系的状况空间。首要用有限状况机来描绘协议中组件的模型，并界说大局状况由一切组件的状况组成。然后推导体系一切的可达状况，推导进程从一个初始的大局状况动身，进行每一种或许的转化，这将发生出一些新的状况。新的状况假如是第一次呈现，将被刺进到作业行列，重复这个进程直到再没有新的状况发生停止。在得到一切的可达状况调集后，需求验证关于每一个可达的大局状况。若一切Cache中的数据都是一起的，即可阐明要验证的协议的正确性。在咱们的验证模型中，大局状况用(s1,s2)表明，其间s1,s2∈[M E S I]。能够从初始状况(I，I)动身，逐渐得到悉数可达状况调集。表2给出了一切大局状况，其间有下划线的为不可达状况。在一切可达状况下，Cache间的数据都是一起的，然后验证了在本文模型下MESI一起性协议的正确性。
由于体系的大局状况是由各个处理器的Cache状况一起组成的。若一个体系有n个处理器，Cache状况有m个，有k个与状况转化有关的操作，那么体系的状况空间巨细是mn，有k*mn个状况转化操作。跟着处理器数目与Cache协议杂乱性的添加，验证作业的作业量也呈指数级添加。由于状况罗列法是选用穷举体系状况的办法进行验证，所以其完成杂乱性是O(mn)。即便考虑到大局状况之间的等价联系，把等价的状况用一个状况表明，这虽然能够大大削减要验证状况的数目，但其完成杂乱性依然是O(mn)。
状况罗列法的长处是办法的概念比较简略，易于了解和完成；协议的模型能够跟着规划的变化而快速的修正，在协议规划初期能够快速地找出规划中的过错；能够方便地用程序规划言语对Cache协议进行建模，并能够使用主动化的东西进行验证。状况罗列法的首要缺乏是跟着处理器数目的添加，状况空间会急剧地以指数级胀大，因而它的适用性被约束在规划较小的体系中。
2.3 模型查验法(Model Checking)
模型查验便是验证某个体系的规划是否满意某种标准，体系的标准用时态逻辑公式来描写。而经过对体系可达状况空间的遍向来证明规划契合标准。验证时的输入是体系规划与要满意的标准。假如给定的模型满意给定标准，那么验证输出为是，不然能够找出违反了标准的反例，经过反例能够了解规划无法满意标准的原因，精确地定位规划缺陷。
能够用来描写模型的标准化言语不是仅有的，这儿以CTL(Computation Tree Logic 运算树逻辑)[2]为例来界说模型和进行验证。CTL是常用的布尔出题逻辑(BPL)的扩展，除了支撑惯例的逻辑操作外，还支撑辅佐的时序操作和途径操作符。在运算树逻辑中，一条途径是一个无限的状况序列(s0,s1，…)，其间存在着由si到si+1的转化。这种办法首要要得到体系的大局状况图，由体系一切可达的大局状况及状况间的转化操作构成。图4给出了咱们的验证模型的大局状况图。要证明体系满意数据一起性的性质用AGf表明，这儿f为数据坚持一起性的出题。并且要求在体系中的一切途径上的一切状况都要满意出题f。在本例中条件满意，这就阐明本文模型下MESI一起性协议的正确性。
除了上面的CTL逻辑以外，还能够用其它的时序逻辑公式来描绘Cache协议[3][8]。不同的时态逻辑公式描绘办法有所不同，但一般都要先对Cache一起性协议进行笼统，得到一个简略的模型然后再验证。
前期模型查验东西选用显式的办法来表明状况空间。由于这种办法的验证进程也是经过关于大局状况空间的遍历完成的，所以也存在着状况空间胀大的问题。其完成杂乱性与状况罗列法相同也是O(mn)。虽然后来在符号模型查验[3][9]中选用了将状况空间转化为布尔函数的办法，使用了ORBDD(ordered reduced binary decision diagram)来表明状况空间，存储BDD节点所需求的空间依然与所表达的体系的规划呈指数联系。
模型查验办法的长处在于时序逻辑强壮的表达能力，与状况罗列法比较，找到满意Cache一起性性质的表达办法要简略得多。模型查验办法的一个首要缺陷是树立体系模型的进程非常杂乱，常常需求包括一些不用要的协议细节，并且要树立主动查验程序也是很困难的。别的在符号状况查验中BDD的巨细对布尔变量的次序灵敏，不同布尔变量次序对BDD巨细影响是明显的。
2.4 符号状况模型法(SSM Symbolic State Model)
SSM[4][10][11]法与前面评论的状况罗列法的不同在于对大局状况的表明。SSM办法对体系的大局状况进行了笼统，这种笼统是由以下调查引发的：首要若体系的各个组件的状况机是相同的，则一切处于相同状况的有限状况机能够集成在一起成为一个集成状况。其次在一切协议中，不是经过写更新，便是经过写无效来完成数据的一起性。而处于Shared状况复制的详细数目与协议正确性无关，关键是对某一个特定状况存在的复制的数目是0、1仍是多个，然后能够把大局状况用更笼统的状况来映射，而不深究处于某一个状况的Cache的详细数目。界说如下表明符：
0：表明有0个实例；
1：表明有且只需一个实例；
*：表明0个，1个或许多个实例；
+：表明1个或许多个实例。
经过这些符号，能够构建杂乱状况的简明表明，例如能够用(I+，S*)来表明一个或多个Cache处于无效状况，0、1或许多个Cache处于同享状况。一个体系的大局状况能够用(q1r1，q2r2，…，qnrn)来表明，这儿n是Cache有限状况机的状况数目，ri归于[0，1，+，*]。依据其表明的内容，这些表明符号的次序为1＜+＜*，0＜*。并界说一个状况集S2包括另一个状况集S1的条件为：qr1∈S1，qr2∈S2，有qr1≤qr2，即r1≤r2，其间q为Cache状况，ri归于[0，1，+，*]。包括联系的重要性在于，假如S2包括S1，那么S2所表明的状况是S1所表明的状况的一个超集，只需验证了S2的正确性，就能够不用再去验证S1的正确性。这是由于关于S1所进行的下一次的状况转化所构成的状况集必定包括在对S2所进行的下一个的状况转化所构成的状况集之中。
在SSM中，状况集的发生是与状况罗列办法相同的。首要经过当时能够进行的转化发生新的状况，然后是一个聚合进程，把处于相同状况的Cache归为一类，最终再查看包括的状况，关于本文的体系模型，从初始的(I+)状况开端的状况扩张进程，最终构成的状况转化图如图5[4]所示。能够看出在状况扩张进程结束时，只发生了别的的四种状况：(E，I*)、(M，I*)、(S，I+)和(S+，I*)。在这五个状况中，Cache都是一起的，然后验证了MESI协议的正确性。SSM办法发现协议过错的办法与状况罗列法相同。
由于SSM验证办法发生的状况空间与要验证的体系的规划无关，关于协议的验证也与体系的规划无关，这是SSM办法最首要的一个长处，由于大局状况数目比较小，相关于传统的其他办法在状况遍历时的开支要小得多。并且由于它关于不同规划的体系模型做到了100%的覆盖率，验证的成果也是牢靠的。其首要缺乏在于树立的模型过于笼统，别的SSM的状况表达办法也有或许将一些存在过错的状况也引进到可达的调集中，例如(D*，…)和(D，S*)。别的一个缺陷便是无法关于组件不同的体系进行验证。
本文总述了CMP体系中Cache一起性协议的验证办法。其间状况罗列法在概念上是最简略的，但存在着状况空间胀大的问题。模型查验能够验证任何用时序逻辑表述的性质，但状况空间胀大的问题也约束了它的使用，并且在详细的程序规划时的作业量也非常大。SSM办法把多个状况用一个笼统后的状况表明，然后大大地减缩了体系的状况空间，并且验证所得到的成果也是能够信赖的，可是并不是一切的协议的状况笼统进程都是直接明晰的。这些办法的首要不同在于对协议的建模办法和状况扩张进程中的选用的减缩状况空间的办法。
跟着CMP的研讨的不断开展，在片上集成的处理器数目将越来越多，音讯的传递途径也由总线开展为片上网络。怎么给出愈加适用于CMP结构、且高效易用的Cache一起性验证办法，将是往后CMP的Cache一起性验证问题的研讨方向。
