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

摘要：

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

关键词：可满足性、电路时延、电路展开

所属期刊栏目：23

分类号：TP391.72(计算技术、计算机技术)

资助基金：国家自然科学基金60776031,60633060,60906013,60921002,60831160526;国家"九七三"重点基础研究发展计划项目2011CB302503

在线出版日期：2011-06-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：480-487