基于门级电路仿真的关键节点提取方法

摘要

本发明公开了一种基于门级电路仿真的关键节点提取方法。主要解决现有技术搜索效率低下、恢复节点状态范围不准确和重复率过高的问题。其包括：获取门级电路的连接关系；通过对门级电路进行仿真，生成相应的门级节点的状态，计算关键节点0、1状态的比率；提取门级电路的频繁子电路；由频繁子电路中提取的D触发器DFF节点恢复门级电路节点；结合D触发器DFF节点恢复节点数目和0、1状态比率，计算加权值，提取出加权值最大的D触发器DFF节点；以提取的D触发器DFF节点为基础，依次进行后续关键节点提取。本发明降低了恢复节点的重复率，提高了搜索效率和关键节点恢复节点状态范围，可用于门级电路检错，实现对内部信号的跟踪。

说明书

技术领域

本发明属于电路处理技术领域，特别涉及一种门级电路的关键节点提取的方法,可用于检测门级电路中存在的错误，实现对内部信号的跟踪。

背景技术

随着芯片规模和复杂度的不断提高，仅靠仿真或者形式验证等硅前验证技术来验证芯片的正确性耗时过长，且无法充分保证首次流片的正确性。为了在芯片推向市场前，消除硅前验证阶段无法发现的错误，首次流片后的硅调试是非常必要的。

硅调试技术分为基于扫描链和基于跟踪信号两种技术。基于扫描链的硅调试技术主要通过某一具体的触发信号对内部电路节点的状态进行捕获，然后由扫描链将捕获到的数据传至片外进行分析。但该技术致命的缺陷在于，每次将捕获的数据外传时，都需要停止正常工作模式，因此无法对内部信号进行实时监测和验证内部信号中存在的一些延时性错误。然而基于跟踪信号的硅调试技术能很好的解决实时监测的问题。基于跟踪信号技术的关键是提取特定的关键节点，来用于内部信号的跟踪和恢复。

门级电路关键节点的提取即在门级电路D触发器DFF节点中筛选出一定数量恢复节点状态范围最大的D触发器DFF节点。而恢复节点状态过程分为正向和反向两个方向，其中：

门级电路节点正向恢复：是通过门级电路当前门节点输入状态及自身正向逻辑关系得出其输出状态，同时由当前门节点输出所连接的其他门节点的输入，可以得到对应门节点的输入状态，最后通过得到的门节点的输入状态及其正向逻辑关系继续进行正向恢复，进而恢复出正向连接中可以恢复的各节点状态。

门级电路节点反向恢复：是通过门级电路当前门节点的输出状态及自身反向逻辑关系得出其输入状态，同时由当前门节点输入所连接的其他门节点的输出，可以得到对应门节点的输出状态，最后通过得到的门节点的输出状态及其反向逻辑关系继续进行反向恢复，进而恢复出反向连接中可以恢复的各节点状态。

最后以门级电路中D触发器DFF节点恢复出的其他D触发器DFF节点数目为参考， 筛选出恢复节点状态范围最大的D触发器DFF节点，作为门级电路的关键节点。

由于传统关键节点的提取是以单个D触发器DFF节点为分析对象，通过对每个节点及其相邻电路进行分析，一方面搜索空间很大，甚至会存在一些冗余搜索，进而导致算法的复杂度过高搜索效率低下；另一方面没有考虑多个D触发器DFF节点共同恢复节点状态的情况，导致恢复节点状态范围不准确或重复率过高。

发明内容

本发明的目的在于针对上述已有技术的不足，提出一种基于门级电路仿真的关键节点提取的方法，以降低关键节点提取的复杂度和恢复节点的重复率，提高关键节点恢复节点状态范围。

为了实现上述目的，本发明采用了以下方案：

(1)获取门级电路中节点的连接关系，得到门级电路内部的连接方式；

(2)对门级电路进行仿真，生成相应的门级电路节点状态即输出状态，所述门级节点状态用于关键节点提取时，计算关键节点0、1状态的比率；

(3)设定门级电路最小支持度t及生成链状模板的长度上限m，对门级电路的频繁子电路进行提取；

(4)将提取的频繁子电路中的D触发器DFF节点选为候选节点，再以D触发器DFF节点为起点，正向或反向恢复门级电路节点；

(5)通过D触发器DFF节点恢复的其他D触发器DFF节点数目加权值，进行排序找到恢复D触发器DFF节点数最多的D触发器DFF节点；

(6)以提取的关键D触发器DFF节点所恢复节点状态为基础，依次进行关键节点提取，直到提取的关键D触发器DFF节点数目达到n个或提取完频繁子电路中所有D触发器DFF节点为止。

本发明相对于现有技术具有以下优点：

1.本发明通过仿真获取各关键D触发器DFF节点0、1状态的比率，避免了因某些关键D触发器DFF节点状态较小概率为0或者1而导致关键节点提取出现偏差的问题；

2.本发明通过门级电路频繁子电路的提取缩小了关键节点提取的范围，提高了关键节点提取的搜索效率；

3.本发明在恢复节点过程中，通过标记已恢复的节点，避免了节点的重复恢复，加快了节点恢复的过程；

4.本发明对关键节点的提取由于充分考虑了多个关键节点共同恢复节点的情况，相较于单个关键节点的提取，提取的关键节点所恢复的节点数更多。

附图说明

图1为本发明使用的门级电路图；

图2为本发明的实现流程图；

图3为本发明中D触发器DFF节点正向恢复节点的方向图；

图4为本发明中D触发器DFF节点反向恢复节点的方向图。

具体实施方式

为使本发明目的、技术方案以及优点更加清楚明白，以下参照附图并举实施例，对本发明进行近一步的详细说明。

参照图1，本发明针对的门级电路，包括4个外部输入端G0、G1、G2、G3，6个D触发器DFF节点DFFG4、DFFG5、DFFG6、DFFG7、DFFG8、DFFG9，3个非门NOT节点NOTG15、NOTG16、NOTG20，1个与门AND节点ANDG19，2个或门OR节点ORG17、ORG18，4个或非门NOR节点NORG11、NORG12、NORG13、NORG14，1个与非门节点NANDG10和2个外部输出G21、G22。

参照图2，本发明基于门级电路仿真的关键节点提取方法，包括以下步骤：

步骤1：获取门级电路中节点的连接关系，得到门级电路内部连接关系。

(1a)将门级电路以字符的形式存入第一缓存数组buf[]；

(1b)初始化存放门级电路外部输入、外部输出和内部节点信息的结构体；

(1c)分别从外部输入、外部输出及内部节点三个方面，遍历整个门级电路，通过对第一缓存数组buf[]中特定的字符进行检索，获取门级电路的外部输入、外部输出以及内部节点的连接关系，并存入对应结构体中。

步骤2：对门级电路进行仿真。

(2a)对整个门级电路进行复位，将门级电路中所有D触发器DFF节点输入置0；

(2b)将仿真周期设定为64；

(2c)初始化整个门级电路，将所有门级电路节点标记为未更新状态；

(2d)由随机函数产生长度为4的0,1随机序列，并分别赋值给门级电路的外部输入端G0、G1、G2、G3；

(2e)遍历门级电路中所有D触发器DFF节点DFFG4、DFFG5、DFFG6、DFFG7、 DFFG8、DFFG9，由各D触发器DFF节点输入，更新其节点状态，并将其节点状态标记为已更新状态；

(2f)对外部输入端和D触发器DFF节点输出端所连接的各门级电路节点的输入状态进行更新，并将所有输入端已更新的门级电路节点的仿真周期更新为当前仿真周期：

(2f1)遍历所有外部输入端G0、G1、G2、G3，分别找到各外部输入端所连接内部节点输入进行更新；

(2f2)通过各D触发器DFF节点的输出连接关系，找到各D触发器DFF节点所连接的内部节点输入进行更新；

(2f3)遍历所有节点状态未更新的门级电路节点，找到所有输入端已更新的第三与非门节点NORG13、第一非门节点NOTG15、第三非门节点NOTG20，将其仿真周期更新为当前仿真周期；

(2g)对处于当前仿真周期的第三与非门节点NORG13、第一非门节点NOTG15、第三非门节点NOTG20，通过其自身的逻辑关系，更新其节点状态，并将其节点状态标记为已更新状态；

(2h)由节点状态已更新的第三与非门节点NORG13、第一非门节点NOTG15、第三非门节点NOTG20，更新其输出所连接的内部节点输入；

(2i)遍历所有节点状态未更新的门级电路节点，找到所有输入已更新的第四与非门节点NORG14、第一或门节点ORG17，将其仿真周期更新为当前仿真周期；

(2j)对处于当前仿真周期的第四与非门节点NORG14、第一或门节点ORG17通过其自身的逻辑关系，更新其节点状态，并将其节点状态标记为已更新状态；

(2k)遍历所有节点状态未更新的门级电路节点，找到节点状态已更新的门级电路节点，更新其输出所连接内部节点输入，将所有输入已更新的门级电路节点再通过其自身逻辑关系，更新其节点状态，直到所有门级电路节点状态均已处于已更新状态为止，结束当前仿真周期；

(2l)重复上述步骤(2c)到(2k)的过程，完成剩下63个仿真周期的门级电路仿真；

(2m)统计64个仿真周期内各D触发器DFF节点0,1状态，并计算每个D触发器DFF节点0、1状态的比率。

步骤3：对门级电路进行频繁子电路提取。

(3a)设定频繁子电路最小支持度t为2和频繁子电路规模上限m为3；

频繁子电路支持度t即门级电路中与当前频繁子电路同构的子电路的数目，而门级电路中大于等于频繁子电路最小支持度的候选子电路称为频繁子电路；所有支持度小于频繁子电路最小支持度的候选子电路称为非频繁子电路。

引入最小支持度阈值t和生成频繁子电路规模上限m概念，可限定所提取的频繁子电路的最小支持度及规模，使得规模最大或支持度最高的频繁子电路优先提取，避免传统规律性提取常常将所有频繁子电路全部提取从而导致算法复杂度过高的情况，其具体实现如下：

(3b)以D触发器DFF节点为根节点，对门级电路进行检索，提取满足最小支持度t的二元频繁子电路结构，排除不能提取二元频繁子电路的根节点，降低根节点的个数；

(3b1)统计门级电路中根节点D触发器DFF节点数目为6；

(3b2)子电路结构规模扩展为2后，得到二元频繁子电路为DFFG→NORG、NORG→DFFG，其中DFFG→NORG包括DFFG5→NORG12、DFFG7→NORG13，NORG→DFFG包括NORG11→DFFG5、NORG12→DFFG6、NORG13→DFFG8、NORG14→DFFG7，同时可以删除不能提取二元频繁子电路的根节点第一D触发器DFF节点DFFG4、第六D触发器DFF节点DFFG9；

(3c)对提取的二元频繁子电路规模进行前向或后向扩展，子电路结构规模扩展为3后，可以得到频繁子电路为DFFG→NORG→DFFG、NORG→DFFG→NORG、NORG→NORG→DFFG，其中DFFG→NORG→DFFG包括DFFG5→NORG12→DFFG6、DFFG7→NORG13→DFFG8，NORG→DFFG→NORG包括NORG11→DFFG5→NORG12、NORG→DFFG→NORG，NORG→NORG→DFFG包括NORG12→NORG11→DFFG5、NORG13→NORG14→DFFG7，此时频繁子电路规模达到设计的规模上限m，结束对子电路结构规模的扩展，并将频繁子电路DFFG→NORG→DFFG、NORG→DFFG→NORG对应的节点存入第二缓存数组buf2[]。

步骤4：以D触发器DFF节点为起点，正向或反向恢复门级电路节点。

(4a)在第二缓存数组buf2[]中，提取D触发器DFF节点第二D触发器DFF节点DFFG5；

(4b)初始化整个门级电路，将所有门级电路节点标记为未恢复状态；

(4c)由第二D触发器DFF节点DFFG5输出方向恢复节点；

参照图3，本步骤具体实现如下：

(4c1)当第二D触发器DFF节点DFFG5节点状态为1时，由门级电路内部节点连接关系，得出第二或非门节点NORG12的输入状态为1；

(4c2)由第二或非门节点NORG12的自身逻辑关系，得到第二或非门节点NORG12的节点状态为0，并将第二或非门节点NORG12入队，其节点状态标记为已恢复状态；

(4c3)将第二或非门节点NORG12出队，由门级电路内部连接关系，得到与第二或非门节点NORG12相连的第一或非门节点NORG11、第三D触发器DFF节点DFFG6、第二非门节点NOTG16的输入状态都为0；

(4c4)分别由第一或非门节点NORG11、第三D触发器DFF节点DFFG6、第二非门节点NOTG16的自身逻辑关系，得到第一或非门节点NORG11节点状态未知即不能恢复出第一或非门节点NORG11的节点状态，第三D触发器DFF节点DFFG6节点状态为0，第二非门节点NOTG16节点状态为1，并将第三D触发器DFF节点DFFG6和第二非门节点NOTG16均入队，其节点状态标记为已恢复状态；

(4c5)分别将第三D触发器DFF节点DFFG6和第二非门节点NOTG16出队，由门级电路内部连接关系，得到第三D触发器DFF节点DFFG6所连接第三非门节点NOTG20输入状态为0，第二非门节点NOTG16所连接第一D触发器DFF节点DFFG4和第一与门节点ANDG19的输入状态都为1；

(4c6)分别由第三非门节点NOTG20、第一与门节点ANDG19、第一D触发器DFF节点DFFG4的自身逻辑关系，得到第三非门节点NOTG20节点状态为1，第一与门节点ANDG19节点状态未知即不能恢复出其节点状态，第一D触发器DFF节点DFFG4节点状态为1，并将第三非门节点NOTG20、第一D触发器DFF节点DFFG4入队，其节点状态标记为已恢复状态；

(4c7)分别将第三非门节点NOTG20、第一D触发器DFF节点DFFG4出队，由门级电路内部连接关系，得到第三非门节点NOTG20所连接的第一与非门节点NANDG10的输入状态为1，而第一D触发器DFF节点DFFG4所连接的是外部输出G21即无法恢复其他节点状态；

(4c8)由第一与非门节点NANDG10自身逻辑关系，得到第一与非门节点 NANDG10节点状态未知即不能恢复出第一与非门节点NANDG10的节点状态，无法继续正向恢复节点；

(4c9)第二D触发器DFF节点DFFG5节点状态为0时，第二D触发器DFF节点DFFG5输出方向无法恢复其它节点状态；

(4c10)统计步骤(4c1)到(4c9)中所有入队节点，得到第二D触发器DFF节点DFFG5节点输出方向能恢复的节点有第二或非门节点NORG12、第二非门节点NOTG16、第三D触发器DFF节点DFFG6、第三非门节点NOTG20、第一D触发器DFF节点DFFG4五个节点；

(4d)再次初始化整个门级电路，将所有门级电路节点标记为未恢复状态；

(4e)由第二D触发器DFF节点DFFG5输出反方向恢复节点；

参照图4，本步骤具体实现如下：

(4e1)当第二D触发器DFF节点DFFG5节点状态为1时，由其自身反向逻辑关系，得出第二D触发器DFF节点DFFG5节点输入状态为1；

(4e2)由门级电路内部节点连接关系，得到第二D触发器DFF节点DFFG5所连接第一或非门节点NORG11的节点状态为1，并将第一或非门节点NORG11入队，其节点状态标记为已恢复状态；

(4e3)由第一或非门节点NORG11自身反向逻辑关系，可以得出第一或非门NORG11所有输入状态均为0；

(4e4)由门级电路内部节点连接关系，得到第一或非门节点NORG11所连接第一非门节点NOTG15和第二或非门NORG12节点状态为0，并将第一非门节点NORG15和第二或非门节点NORG12入队，其节点状态标记为已恢复状态；

(4e5)分别由第一非门节点NOTG15和第二或非门节点NORG12的自身反向逻辑关系，得到节点第一非门节点NOTG15输入状态为1；而第二或非门节点NORG12输入状态未知即不能继续沿第二或非门节点NORG12输出反方向恢复节点；

(4e6)由第一非门节点NOTG15输入连接了外部输入，结束反方向恢复节点，最终得到第二D触发器DFF节点DFFG5输出反方向恢复节点有第一非门节点NOTG5、第二或非门节点NORG12和第一或非门节点NORG11三个节点。

(4f)当第二D触发器DFF节点DFFG5节点状态为0时，第二D触发器DFF节点DFFG5输出反方向无法恢复其它节点状态；

(4g)参照步骤(4b)到(4g)完成对buf2[]中第三D触发器DFF节点DFFG6正向或反向的门级电路节点恢复，可得第三D触发器DFF节点DFFG6能正向恢复出节点第三非门节点NOTG20、第一与非门节点NANDG10、第二或非门节点NORG12三个节点，反向恢复出第一或非门节点NORG11、第二或非门节点NORG12、第二D触发器DFF节点DFFG5、第一与非门节点NAND10、第三非门节点NOTG20、第二或门节点ORG18六个节点；

(4h)参照步骤(4b)到(4g)完成对buf2[]中第四D触发器DFF节点DFFG7正向或反向的门级电路节点恢复，可得第三D触发器DFF节点DFFG7能正向恢复出第三或非门节点NORG13和第四D触发器DFF节点DFFG8两个节点，反向恢复出第四或非门节点NORG14、第三或非门节点NORG13；

(4i)参照步骤(4b)到(4g)完成对buf2[]中第五D触发器DFF节点DFFG8正向或反向的门级电路节点恢复，得到第五D触发器DFF节点DFFG8能正向恢复出第二或门节点ORG18，反向恢复出第三或非门节点NORG13、第三D触发器DFF节点DFFG7和第四或非门节点NORG14三个节点。

步骤5通过D触发器DFF节点恢复的其他D触发器DFF节点数目加权值，进行排序，找到恢复其他D触发器DFF节点数最多的D触发器DFF节点。

(5a)由步骤4节点恢复过程可知，第二D触发器DFF节点DFFG5恢复的D触发器DFF节点数目为2，第三D触发器DFF节点DFFG6恢复的D触发器DFF节点数目为1，第四D触发器DFF节点DFFG7恢复的D触发器DFF节点数目为1，第五D触发器DFF节点DFFG8恢复的D触发器DFF节点数目为1；

(5b)通过D触发器DFF节点0、1状态的比率和D触发器DFF节点分别在0、1状态下恢复节点的数目，计算各D触发器DFF节点恢复其他D触发器DFF节点的加权值；

加权公式如下：

score＝dff[i].one_cnt*dff[i].one_rate+(1.0-dff[i].one_rate)*dff[i].zero_cnt；

其中，变量score为D触发器DFF节点的加权值；变量dff[i].one_cnt和变量dff[i].zero_cnt分别为第i个D触发器DFF节点的状态为1和0时，恢复D触发器DFF节点的数目；变量dff[i].one_rate为第i个D触发器DFF节点在64个仿真周期内状态为1的比率。

(5d)对所得加权值进行快速排序，将各D触发器DFF节点的加权值从大到小排序，找出加权值最大的第二D触发器DFF节点DFFG5，作为提取的第一个关键D触发器DFF节点。

步骤6以提取的关键D触发器DFF节点所恢复节点状态为基础，依次进行关键节点提取，直到提取的关键D触发器DFF节点数目达到n个或提取完频繁子电路中所有D触发器DFF节点为止。

(6a)设定提取的关键D触发器DFF节点数目n为4；

(6b)以第二D触发器DFF节点DFFG5恢复的节点状态为基础，选取第三D触发器DFF节点DFFG6，进行门级电路节点恢复；

(6c)由第二D触发器DFF节点DFFG5恢复的节点状态可知，第二或非门节点NORG12节点状态为1；而第三D触发器DFF节点DFFG6进行门级电路节点恢复，可得第一与非门节点NAND10节点状态为1；

(6d)由第二或非门节点NORG12和第一与非门节点NANDG10输出均为节点第一与门节点ANDG19的输入，因而可以得到第一与门节点ANDG19节点状态为1；

(6e)由门级电路内部节点连接关系，得出第一与门节点ANDG19所连接第五D触发器DFF节点DFFG9节点状态为1，进而相较于单个第三D触发器DFF节点DFFG6的节点恢复过程，能够多恢复出第五D触发器DFF节点DFFG9的节点状态。

(6f)第四D触发器DFF节点DFFG7再以第二D触发器DFF节点DFFG5恢复的节点状态为基础，进行门级电路节点恢复，其恢复D触发器DFF节点数目与单个第四D触发器DFF节点DFFG7恢复D触发器DFF节点数目相同；

(6g)第五D触发器DFF节点DFFG8再以第二D触发器DFF节点DFFG5恢复的节点状态为基础，进行门级电路节点恢复，其恢复D触发器DFF节点结果与单个第五D触发器DFF节点DFFG8的节点恢复过程相同；

(6h)参照步骤(6b)到(6g)各D触发器DFF节点恢复的其他D触发器DFF节点数目和各D触发器DFF节点0、1状态的比率计算加权值，找出加权值最大的第三D触发器DFF节点DFFG6，作为提取的第二个关键D触发器DFF节点；

(6i)以第二D触发器DFF节点DFFG5、第三D触发器DFF节点DFFG6恢复的节点状态为基础，参照步骤(6b)到(6h)，提取第四D触发器DFF节点DFFG7，作为第三个关键D触发器DFF节点；

(6j)以第二D触发器DFF节点DFFG5、第三D触发器DFF节点DFFG6、第四D触发器DFF节点DFFG8恢复的节点状态为基础，参照步骤(6b)到(6h)，提取第五D触发器DFF节点DFFG8，作为第四个关键D触发器DFF节点，并结束关键节点提取过程。

除了本实施例，本发明还能对大型门级网表进行关键节点的提取，进而加快大型门级网表正确性的验证和检错。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不限于此，任何熟悉该技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的改变或替换，都涵盖在本发明的保护范围内。