基于符号模拟的电路中错误诊断方法研究
时间：10-22
来源：EDN
点击：
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探测不出区域中的任何错误；否则说明区域中存在错误并将该区域作为一个错误候选者。
错误诊断是集成电路验证后期一个非常重要的阶段，它帮助设计者在一个错误芯片中预测错误点，因此可以减轻整个调试过程中的工作量。经过许多年的研究工作，组合电路的错误诊断正趋于成熟和实用化。这些方法主要分为两类：基于模拟的方法和符号方法。基于模拟的方法在每个错误向量对电路的模拟中，通过过滤掉非错误点而使含有错误点的区域逐渐被限定下来。符号方法不用明确列举错误向量，而是主要依赖于二叉决策图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探测不出区域中的任何错误；否则说明区域中存在错误并将该区域作为一个错误候选者。