基于符号模拟的电路中错误诊断方法研究

0 引 言
    错误诊断是集成电路验证后期一个非常重要的阶段，它帮助设计者在一个错误芯片中预测错误点，因此可以减轻整个调试过程中的工作量。经过许多年的研究工作，组合电路的错误诊断正趋于成熟和实用化。这些方法主要分为两类：基于模拟的方法和符号方法。基于模拟的方法在每个错误向量对电路的模拟中，通过过滤掉非错误点而使含有错误点的区域逐渐被限定下来。符号方法不用明确列举错误向量，而是主要依赖于二叉决策图BDD，并提出错误源定位的充分必要条件。依据此充分必要条件，可直接定位错误点。该方法由于使用BDD技术，因而存在内存爆炸的隐患。
    Boppana为错误诊断提出了一个概括的基于区域的模型，该模型可以被扩展来定位多错误，并且可以用于解决时序电路的错误诊断。Shi-Yu Huang提出了利用符号模拟来优化拜占庭式错误诊断的过程。Boppana介绍了一个基于Xlists模拟的诊断算法。N．Sridhar提出一种诊断技术，它通过可区分的X来消减错误候选者区域。李光辉介绍了基于验证技术的错误诊断方法，该方法将三值模拟与SAT技术相结合，以消减错误空间，提高诊断结果。
    在此，提出一种利用符号模拟技术来优化基于区域模型错误诊断过程的方法。该方法首先使用基于区域模型错误诊断方法中电路划分方法对所要诊断的电路进行区域划分，然后在其基础上利用符号模拟技术并使用两个测量标准对各个区域的可疑度进行等级排序。可疑度越高的区域包含错误点的可能性越大。由于使用符号模拟技术，不需要对向量空间进行明确列举，因而所提出的方法在时间上是有效的。

1 定 义
    在此，将规范和实现分别表示为C1和C2，其中实现表示为一个组合的门级电路。规范和实现的主要输入(PI)信号都表示为{x1，x2，…，xm)，其中m表示主要输入的个数。规范和实现的主要输出(PO)信号分别表示为{S1，S2，…，Sn}和{I1，I2，…In}，其中n表示主要输出的个数。另外，假设预先生成的测试向量集合为T={v1，v2，…，vt}。
    定义1 (Si，Ii)被称为一个输出对，其中1≤i≤n。 
    定义2 如果存在一个输入测试向量v，使得v对规范和实现电路分别进行模拟时，实现电路的输出Ii与规范中相对应的输出Si的值不同，称Ii为错误输出或不匹配输出，(Si，Ii)为不匹配输出对。
    定义3 如果一个输入向量能使任何输出对之间产生不匹配现象，则称该输入向量为错误输入向量。
    定义4 对一个不匹配输出Ii的处理涉及到这样一个机制，即对实现中某些信号注入二进制值可以使Ii的响应同规范中与它相对应的输出响应相同。
    错误诊断是基于一个被称为可治愈性的概念进行的。在搜索错误候选者的过程中，为了对每个信号的可疑度进行等级排序，需要对每个信号进行两方面的测量：可治疗的输出数和可治疗的向量数。
    定义5 假设实现电路在错误输入向量v，的模拟下，第i个主要输出是不匹配输出。令A是一个有着k个输出{a1，a2，…，ak}的区域。如果在主要输出Ii处的不匹配可以通过在{a1，a2，…ak}的一个注入组合来修正，则称Ii足在v的模拟下区域A的一个可治疗输出，用符号表示为Ii∈region_curable_output(A，v)。
    该定义说明了可以通过对一个区域输出进行处理来纠正C2中出现的不匹配输出。这里处理的方法是在区域输出点注入某些二进制值。由经验可知，一个区域的可治疗输出的个数越多，则它成为包含错误点区域的可能性越大，因为对这个区域输出值的改变会影响到较多的不匹配输出。另外，除了这个测量标准，可以利用一个被称为可治疗向量的测量标准来进一步有效地检查错误点。
    定义6 如果实现电路C2在一个错误输入向量v的模拟下所产生的每个不匹配输出可以同时通过在区域A的输出{a1，a2，…，ak}处一个注入组合来纠正，并且不会产生新的不匹配输出的话，则称这个错误输入向量v为区域A的可治疗向量，用符号表示为Ii∈region_curable_vector(A)。如果这样一个注入存在，则称它为区域A的一个可治疗注入。
    基于这两个测量标准，结合排序准则，对每个区域的可疑度进行等级排序。排序准则如下：有较多可治疗向量的区域，其成为错误候选者的可疑度就越大。对于有相同数目可治疗向量的区域，考虑它们的可治疗输出数目，即把可治疗向量作为第一层测量标准使用，把可治疗输出作为第二层测量标准考虑。

2 区域模型介绍
    定义7电路中的任一门元件g与它的直接扇入门或者直接扇出门之间的距离称为一个结构距离。
    定义8 给定d为一个固定化的结构距离，g为电路的任一门元件，则以g为中心，以d为半径的区域是集合D(g)={h|dis(g，h)≤d}。
    例如，门g周围半径为1的区域集合中包括g，g的直接扇出以及它的直接扇入。电路中的每个门都可以形成一个区域，因此电路中有多少个门就有多少个重叠区域。文献[3]中介绍的基于区域模型的诊断方法是在模拟过程中，首先将区域中所有输出结点设置为未知值X，以掩盖发生在该区域中的任何错误。如果对于一个给定向量v，没有X可以传播到一个主要输出，则可以判定向量v探测不出区域中的任何错误；否则说明区域中存在错误并将该区域作为一个错误候选者。

3 符号模拟优化过程
    接下来介绍如何将符号模拟技术应用到区域模型上，并计算在错误输入向量v同时，对规范和实现电路进行模拟的情况下，v是否为区域A的一个可治疗向量。另外，需要确定在v的模拟下该区域有多少个可治疗输出。计算分四个主要步骤：无错误逻辑模拟、符号注入、符号传播及可治疗性检查。
   无错误逻辑模拟简单确立了在输入向量v的模拟下，每个信号线的无错误逻辑值。下面要讨论的其他3个步骤是针对区域模型等级排序提出的。
3．1 符号注入
    首先，将要考虑区域的输出与区域之间的连接断开，接着把这些输出信号线抽出来，将其中每一个信号线都视为一个伪主要输入，最后对每个输出端aj注入一个符号变量xj，其中1≤j≤k，k是区域A的输出数量。注意：A输出的扇出区域中每个信号都会受到注入变量的影响。图1给出了注入符号前及注入符号后电路的基本情况。

3．2 符号传播
    符号注入的作用是通过函数向主要输出方向传播来对区域A输出的扇出区域中的信号进行赋值。符号传播的过程类似于错误模拟过程，不同之处在于符号传播中一个信号的值不再是逻辑值0／1，而是用所注入的布尔变量{x1，x2，…，xk}表示的一个布尔函数。图2所示为符号传播过程。
    在符号传播过程中可以采取两项技术来加速该过程。一个是有序二叉决策图(OBDD)的使用，另一个是事件驱动的模拟。BDD的使用有可能造成内存爆炸，但是这里由于诊断过程中不需要特征化电路的全局函数，因此避免了上述内存爆炸问题。在事件驱动模拟中，许多门元件由于不受符号注入的影响，不需要进行再次模拟，因此在符号传播的一次单一运行中，CPU的处理时间不会因为电路规模的增大而迅速增加。
3．3 可治疗性检查
    符号传播过程的最后可以在实现电路的每个主要输出得到一个布尔函数，称为作用函数。一个作用函数包含它对区域输出{a1，a2，…，ak}的一个注入起怎样反应的相关信息。通过对这些信息的获得可以计算区域中可治疗输入和可治疗输出的个数。
    定义9 令Ii是第i个主要输出。v是一个错误输入向量，A是一个待检查的错误候选者区域。在向量v对实现电路进行模拟以及对区域A的输出进行符号注入和符号传播过程后，Ii的作用函数表示为Reacti(v，a，X)，其中X是执行符号注入时所使用的布尔变量{x1，x2，…，xk}的集合。
    命题1 当且仅当下面式子成立时，错误输入向量v是区域A的一个可治疗向量。Si(v)表示在向量v模拟下规范的第i个输出响应，n是输出的总个数。

   
    证明 如果存在{x1，x2，…，xk}的一个注入组合，使得注入后对于每一个主要输出索引i，实现电路的Reacti(v，a，X)的响应同规范Si(v)的响应值相同，则该注入组合被称为区域可治疗注入，同时也证明了在区域A的输出处注入的组合使得错误输入向量v不再引起任何输出对之间的不匹配现象，即v不再是实现电路的一个错误输入向量。
    如果存在一个注入组合，使得一个不匹配输出的逻辑值变为与它对应的完全相同的值，则称该不匹配输出为一个区域可治疗输出(区域可治疗输出的规则)：如果下面的条件成立，则对于向量v，一个不匹配输出Zic称为通过区域输出信号a的可治疗输出。

   
    例如(区域可治疗注入)考虑图中的规范和实现，在一个输入向量v的模拟下，规范的输出响应为(0，O，0，0，0)，而实现的响应为(0，0，0，1，1)。第四和第五个输出为不匹配输出。通过执行符号注入和传播，每个主要输出作用函数的集合为{0，0，x3，x1，(x1x2)'}。
    前两个输出对是匹配的，因此只进行后三个输出的可治疗性检查。为了检查可治疗向量，注入需满足(x3三0)，(x1三O)和[(x1x2)'三0]。因为第二个和第三个条件互相冲突，可得出结论：区域A不能通过注入来治疗错误输入向量v。

    另一方面，为可治疗输出检查每个作用函数。在注入前只需要关注于第4和第5个不匹配输出。第4个输出的作用函数是x1，只需要在注入时使x1为0，就可使输出从1变为0，即通过此方法解决了第4个输出的不匹配问题，因此第4个输出是一个可治疗输出。类似地，第5个输出也是可治疗输出。因此该区域A共有两个可治疗输出。在这个例子中，两个不匹配输出可以分别独立地进行治疗纠正；然而在治疗最后一个输出时将不可避免地在第3个输出点引出一个新的不匹配问题，这也是给定的错误输入向量不能通过区域A来治疗纠正的原因。利用符号模拟技术可以优化基于区域模型进行错误诊断的过程，依据区域可治疗向量和区域可治疗输出两个测量标准对候选的各个区域进行包含错误点的可疑度等级排序，可疑度等级越高的区域，包含错误点的可能性也越大。

4 实验结果与结论
    在此选取几个简单的组合电路，每个电路随机注入一个门置换错误，利用符号模拟技术对每个电路进行错误诊断。从方法执行的CPU时间来看，这里提出的优化方法并不是每次都比原始基于区域模型的方法运行速度快，但是从整体来看，因为该优化方法极大地减少了所要处理候选区域的个数，因此总运行时间还是比较理想的。
    这里提出将符号模拟技术应用到基于区域模型的错误诊断方法中的新方法。该方法采用符号模拟技术对候选区域进行处理，包括符号的注入，符号的传播，可治疗性检查三步。另外，用符号模拟的方法对区域进行处理后得到的部分处理信息可以应用到后面的纠错过程中，这点是原始基于区域模型方法中所不具有的。利用符号模拟的错误诊断方法也可以扩展应用到具有多错误的电路中，但是尚需进一步研究与实现。