高级检索
何子键, 吕涛, 李华伟, 李晓维. 基于SAT的快速电路时延计算[J]. 计算机辅助设计与图形学学报, 2011, 23(3): 480-487.
引用本文: 何子键, 吕涛, 李华伟, 李晓维. 基于SAT的快速电路时延计算[J]. 计算机辅助设计与图形学学报, 2011, 23(3): 480-487.
He Zijian, Lu: Tao, Li Huawei, Li Xiaowei. Fast Circuit Delay Calculation Based on SAT Solvers[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(3): 480-487.
Citation: He Zijian, Lu: Tao, Li Huawei, Li Xiaowei. Fast Circuit Delay Calculation Based on SAT Solvers[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(3): 480-487.

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

Fast Circuit Delay Calculation Based on SAT Solvers

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

     

    Abstract: Traditional time unrolling based circuit delay calculation method is inefficient in the case that large circuits are analyzed or accurate delay models are adopted.In order to speedup circuit delay calculation, an improved method by sub-circuit extraction is proposed in this paper.On one hand, a sub-circuit is constructed by analyzing output constraints and extracting related logic cones from the unrolled circuit.The circuit delay is checked on the extracted sub-circuit instead of the unrolled circuit, thus the calculation process is speeded up.On the other hand, the concept of abstract circuit is proposed and preprocess is applied on it to find out the shared structures among extracted sub-circuits.The learning clauses derived from preprocessing can be utilized to speed up SAT solving at each checking step.Experimental results on ISCAS85 and ISCAS89 benchmark demonstrate that the proposed approach can improve the efficiency of circuit delay calculation by about 8 times over the traditional method on average.

     

/

返回文章
返回