基于SAT的快速电路时延计算

摘要

针对现有的基于时间展开电路求解时延算法在电路规模较大或者时延模型精度较高时效率较低的问题,提出一种基于子电路抽取的电路时延计算方法.基于展开电路,通过分析输出端约束找到相关的输出端,利用回溯抽取与这些输出端相关的逻辑锥子电路,并在子电路而不是在展开电路上进行求解,由于抽取的子电路的规模远小于展开电路的规模,加速了求解过程;同时提出了抽象电路的概念,并分析了抽取子电路的同构特性,通过在抽象电路上进行预处理得到学习子句,从而可以利用学习子句加速每一次的SAT求解过程.在ISCAS85和ISCAS89电路上的实验结果表明,采用文中方法使得电路时延的求解效率平均提高了约8倍.